hzwer.com - Page 39

NOI2009管道取珠
DescriptionInput第一行包含两个整数n,m，分别表示上下两个管道中球的数目。第二行为一个AB字符串，长度为n，表示上管道中从左到右球的类型。其中A表示浅色球，B表示深色球。第三行为一个AB字符串，长度为m，表示下管道中的情形。Output仅包含一行，即为Sigma(Ai^2)i从1到k除以1024523的余数。SampleInput21ABBSampleOutput5HINT样例即为文中(图3)。共有两种不同的输出序列形式，序列BAB有1种产生方式，而...
02014年12月17日3,796递推与动规

NOI2009植物大战僵尸
DescriptionInputOutput仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。SampleInput32100200-100-51001001211000SampleOutput25HINT在样例中,植物P1,1可以攻击位置(0,0),P2,0可以攻击位置(2,1)。一个方案为，首先进攻P1,1,P0,1，此时可以攻击P0,0。共得到能源收益为(-5)+20+10=25。注意,位置(2,1)被植物P2,0保护，所以无法攻击第2行中的任何植物。「大致数据规...
02014年12月17日6,594最小割,拓扑排序
「BZOJ2299」[HAOI2011] 向量
Description给你一对数a,b，你可以任意使用(a,b),(a,-b),(-a,b),(-a,-b),(b,a),(b,-a),(-b,a),(-b,-a)这些向量，问你能不能拼出另一个向量(x,y)。说明：这里的拼就是使得你选出的向量之和为(x,y)Input第一行数组组数t，(t<=50000)接下来t行每行四个整数a,b,x,y (-2*109<=a,b,x,y<=2*109)Outputt行每行为Y或者为N，分别表示可以拼出来，不能拼出来SampleInput32133110110-23SampleOutputYNY题解orzwulala注意...
22014年12月17日4,710最大公约数与最小公倍数
NOI2010海拔
DescriptionYT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为n×n个区域。简单起见，可以将YT市看作一个正方形，每一个区域也可看作一个正方形。从而，YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路（简称道路），每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n=2)，城市被划分为2×2个区域，包括3×3个交叉路口和12条双向道路。小Z作为该市的市长，他根据统计信息得到...
02014年12月17日4,009最小割,STL,dijkstra
「BZOJ2893」征服王
Description虽然春希将信息传递给了雪菜，但是雪菜却好像完全不认得春希了。心急如焚的春希打开了第二世代机能，对雪菜的脑内芯片进行了直连-hack。进入到雪菜内部的春希发现（这什么玩意。。），雪菜的脑部结构被分成了n个块落，并且一些块落之间被有向边连接着。由于四分五裂的脑部，雪菜关于春希的记忆也完全消失，春希为了恋人，启动了inversionprocess.在inversionprocess中，要想使雪菜回到正常状态，需要纳米机器人的帮助。...
02014年12月16日5,415费用流,图的连通
「BZOJ1334」[Baltic2008] Elect
DescriptionN个政党要组成一个联合内阁，每个党都有自己的席位数.现在希望你找出一种方案，你选中的党的席位数要大于总数的一半，并且联合内阁的席位数越多越好.对于一个联合内阁，如果某个政党退出后，其它党的席位仍大于总数的一半，则这个政党被称为是多余的，这是不允许的.Input第一行给出有多少个政党.其值小于等于300下面给出每个政党的席位数.总席位数小于等于100000Output你的组阁方案中最多能占多少个席位.SampleIn...
22014年12月16日3,685背包动规
「BZOJ2431」[HAOI2009] 逆序对数列
Description对于一个数列{ai}，如果有i<j且ai>aj，那么我们称ai与aj为一对逆序对数。若对于任意一个由1~n自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为k的这样自然数数列到底有多少个？Input第一行为两个整数n，k。Output写入一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对10000求余数后的结果。SampleInput样例输入41SampleOutput样例输出3样例说明：下列3个数列逆序...
02014年12月16日3,970递推与动规
「BZOJ1923」[SDOI2010] 外星千足虫
DescriptionInput第一行是两个正整数N,M。接下来M行，按顺序给出Charles这M次使用“点足机”的统计结果。每行包含一个“01”串和一个数字，用一个空格隔开。“01”串按位依次表示每只虫子是否被放入机器：如果第i个字符是“0”则代表编号为i的虫子未被放入，“1”则代表已被放入。后面跟的数字是统计的昆虫足数mod2的结果。由于NASA的实验机器精确无误，保证前后数据不会自相矛盾。即给定数据一定有解。Output在给定数...
02014年12月16日5,316高斯消元
「BZOJ3261」最大异或和
Description给定一个非负整数序列{a}，初始长度为N。有 M个操作，有以下两种操作类型：1、Ax：添加操作，表示在序列末尾添加一个数x，序列的长度N+1。2、Qlrx：询问操作，你需要找到一个位置p，满足l<=p<=r，使得：a[p]xora[p+1]xor...xora[N]xorx最大，输出最大是多少。Input第一行包含两个整数N ，M，含义如问题描述所示。第二行包含N个非负整数，表示初始的序列A。接下来M行，每行描述一个操作，格式如题...
102014年12月16日11,758贪心,可持久化字典树
「BZOJ1954」Pku3764 The xor – longest Path
Description给定一棵n个点的带权树，求树上最长的异或和路径InputTheinputcontainsseveraltestcases.Thefirstlineofeachtestcasecontainsanintegern(1<=n<=100000),Thefollowingn-1lineseachcontainsthreeintegersu(0<=u<n),v(0<=v<n),w(0<=w<2^31),whichmeansthereisanedgebetweennodeuandvoflengthw.OutputForeachtestcaseoutputthexor-lengthofthexor-longestpath.SampleInput4123234246Samp...
02014年12月16日4,765贪心,字典树
「BZOJ3791」作业
Description众所周知，白神是具有神奇的能力的。比如说，他对数学作业说一声“数”，数学作业就会出于畏惧而自己完成；对语文作业说一声“语”，语文作业就会出于畏惧而自己完成。今天，语文老师和数学老师布置了许多作业，同学们纷纷寻找白神寻求帮助。白神作为一个助人为乐的人，便答应下来。回到家，白神将这N份作业按顺序摊开，发现语文作业数学作业混在一起，这就让白神苦恼起来，他如果对连续一段作业喊出“数”，那么里面...
02014年12月15日2,713递推与动规
「BZOJ3158」千钧一发
DescriptionInput第一行一个正整数N。第二行共包括N个正整数，第个正整数表示Ai。第三行共包括N个正整数，第个正整数表示Bi。Output共一行，包括一个正整数，表示在合法的选择条件下，可以获得的能量值总和的最大值。SampleInput43451298309SampleOutput39HINT1<=N<=1000,1<=Ai,Bi<=10^6题解可以证明，任意两个偶数满足2两个奇数满足1(2a+1)^2+(2b+1)^2=2(2a^2+2b^2+2a+2b+1)一定不是完全平方数所以...
12014年12月15日4,456最小割