« 上一页下一页 »Current position : 首页 >> 算法 >> 第51页
sequence
给定一个序列，求其所有区间按位异或的值的和题解按位考虑。。。比如说对于每个a[i]的第K位对于一个x，假设得到了i到x-1(i<x)这些区间的异或值。。。即有f0[x-1]个0,f1[x-1]个1，每个1对答案的贡献是1<<(K-1)那么对于i到x，仅仅是对于所有区间加入了a[x]这个元素以及多了仅含a[x]的区间。。所以若a[x]=1的话，f0[x]=f1[x-1]，f1[x]=f0[x-1]+1否则f0[x]=f0[x-1]+1,f1[x]=f1[x-1][crayon-684e978ea8d6b132397529/] ...
「NOIP模拟赛」小象涂色
题目描述：小象喜欢为箱子涂色。小象现在有c种颜色，编号为0~c-1；还有n个箱子，编号为1~n，最开始每个箱子的颜色为1。小象涂色时喜欢遵循灵感：它将箱子按编号排成一排，每次涂色时，它随机选择[L，R]这个区间里的一些箱子（不选看做选0个），为之涂上随机一种颜色。若一个颜色为a的箱子被涂上b色，那么这个箱子的颜色会变成（a*b）modc。请问在k次涂色后，所有箱子颜色的编号和期望为多少？输入描述：第一行为T，表示有T组测...
「NOIP模拟赛」“与”
题目描述：给你一个长度为n的序列A，请你求出一对Ai，Aj（1<=i<j<=n）使Ai“与”Aj最大。Ps：“与”表示位运算and，在c++中表示为&。输入描述：第一行为n。接下来n行，一行一个数字表示Ai。输出描述：输出最大的Ai“与”Aj的结果。样例输入：38102样例输出：8样例解释：8and10=88and2=010and2=2数据范围：20%的数据保证n<=5000100%的数据保证n<=3*10^5，0<=Ai<=10^9题解从最高位开始，如有大等...
「NOIP模拟赛」Hzwer的陨石
题目描述：经过不懈的努力，Hzwer召唤了很多陨石。已知Hzwer的地图上共有n个区域，且一开始的时候第i个陨石掉在了第i个区域。有电力喷射背包的ndsf很自豪，他认为搬陨石很容易，所以他将一些区域的陨石全搬到了另外一些区域。在ndsf愉快的搬运过程中，Hzwer想知道一些陨石的信息。对于Hzwer询问的每个陨石i，你必须告诉他，在当前这个时候，i号陨石在所在区域x、x区域共有的陨石数y、以及i号陨石被搬运的次数z。输入描述：输入...
「NOIP模拟赛」藏宝图
背景Czy爬上黑红树，到达了一个奇怪的地方……题目描述Czy发现了一张奇怪的藏宝图。图上有n个点，m条无向边。已经标出了图中两两之间距离dist。但是czy知道，只有当图中的各个点刚好又是一颗树的节点的时候，这张藏宝图才是真的。如果藏宝图是真的，那么经过点x的边的边权平均数最大的那个x是藏着宝物的地方。请计算这是不是真的藏宝图，如果是真的藏宝之处在哪里。格式输入数据第一行一个数T,表示T组数据。对于每组数据，第一...
「NOIP模拟赛」挖掘机
背景附中机房谁最虚？高二一班***！感觉很顺，是吧？题目描述今天，丧尸czy开着挖掘机去上学(……)。但是他发现他的mz满天下，所以一路上他碰到了好多他的mz。一开始他以1km/min的速度(=60km/h……)开着挖掘机前进。他发现他只会在恰好到达某一时刻或者到达某个距离遇到mz。每次遇到mz，czy都会毫不犹豫的把她们顺路捎走(^_^)。但是他实在是太虚了，以至于当有i个mz时他的速度下降到1/(i+1)。具体说，一开始czy以1km/min速度前进，...
「NOIP模拟赛」Kth
「题目描述」给定一个N(2<=N<=150000)个节点N－1边的树，每条边有一个长度L（1<=L<=1000000）。现在定义：“路径(u,v)长度”表示顶点u到v之间的最短路径“u的第k远路径”表示从顶点u出发的第k长路径。请编写一个程序，计算这棵树中每个顶点的的第k远路径的长度。「输入格式」输入第一行包含一个整数T（T<=50），表示测试数据的组数。在每一组测试数据中，第一行为两个整数N和K(1<=K<=20且K<=N...
「hdu2196」Computer
ProblemDescriptionAschoolboughtthefirstcomputersometimeago(sothiscomputer'sidis1).DuringtherecentyearstheschoolboughtN-1newcomputers.Eachnewcomputerwasconnectedtooneofsettledearlier.ManagersofschoolareanxiousaboutslowfunctioningofthenetandwanttoknowthemaximumdistanceSiforwhichi-thcomputerneedstosendsignal(i.e.lengthofcabletothemostdistantcomputer).Youneedtoprovidethisinformation.Hint:the...
「NOIP模拟赛」Incr
「题目描述」数列A1,A2,...,AN，修改最少的数字，使得数列严格单调递增。「输入格式」第1行，1个整数N第2行，N个整数A1,A2,...,AN「输出格式」1个整数，表示最少修改的数字「样例输入」3132「样例输出」1「数据范围」对于50%的数据，N≤10^3对于100%的数据，1≤N≤10^5,1≤Ai≤10^9题解暴力可以用f[i][j]表示前i个最后一个改为j的方案[crayon-684e978eab023346112864/]ai减去下标求最长上升子序列ans。。。答案是n-an...
「NOIP模拟赛」Graph
「题目描述」给出N个点，M条边的有向图，对于每个点v，求A(v)表示从点v出发，能到达的编号最大的点。「输入格式」第1行，2个整数N,M。接下来M行，每行2个整数Ui,Vi，表示边⟨Ui,Vi⟩。点用1,2,...,N编号。「输出格式」N个整数A(1),A(2),...,A(N)。「样例输入」43122443「样例输出」4434「数据范围」对于60%的数据，1≤N,K≤10^3对于100%的数据，1≤N,M≤10^5。题解反建图bfs[crayon-684e978eab3c9581775432/]&...
「BZOJ3417」POI2013 Tales of seafaring
DescriptionYoungBytenssonlovestohangoutintheporttavern,whereheoftenlistenstotheseadogstellingtheirtalesofseafaring.Initially,hebelievedthemall,howeverincredibletheysounded.Overtimethough,hebecamesuspicious.Hehasdecidedtowriteaprogramthatwillverifyiftheremaybeanygrainoftruthinthosetallstories.Bytenssonreasonedthatwhilehecannottellifthesailorsindeedweatheredallthosestorms,hecanatleastfindouti...
「BZOJ1914」[Usaco2010 OPen] Triangle Counting 数三角形
![「BZOJ1914」[Usaco2010 OPen] Triangle Counting 数三角形](http://www.lydsy.com:808/JudgeOnline/images/1914_1.jpg)
Description在一只大灰狼偷偷潜入FarmerDon的牛群被群牛发现后，贝西现在不得不履行着她站岗的职责。从她的守卫塔向下瞭望简直就是一件烦透了的事情。她决定做一些开发智力的小练习，防止她睡着了。想象牧场是一个X，Y平面的网格。她将N只奶牛标记为1…N(1<=N<=100,000)，每只奶牛的坐标为X_i,Y_i(-100,000<=X_i<=100,000;-100,000<=Y_i<=100,000;1<=i<=N)。然后她脑海里想象着所有可能由奶牛...
近期评论