Problem A: 序列
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 12 Solved: 9[][][]Description
作为一名火星人，你为了占领地球，需要想方设法使地球人失去信心。现在你获得了一项能 力，控制今后n天的天气温度，对于第i天,你能将温度控制在[ai,bi]中任意一个数字，你的 目的是使其中某段时间，温度持续不下降，趁此来攻击地球。现在问你最多可以使连续的多 少天满足温度不下降。
Input
第一行给出一个整数n，表示你能控制的天数。 接下来n行,第i行给出2个整数ai,bi,表示你能控制的天气范围。保证ai<=bi。 3<=n<=1000000，1<=ai,bi<=100000
Output
输出一个整数，表示答案。
Sample Input
41 32 41 13 4
Sample Output
2
HINT
题解：单调队列即可，我们考虑前一段是（ai-1-bi-1) 和（ai-bi） 我们后一段取（min（bi-1，ai)) 更优，
于是我们可知当bi>maxΣ（a[i-1)则这一段可选，于是单调队列或者n2暴力+优化
Problem B: 硬币
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 6 Solved: 5[][][]Description
你有n个硬币，第i个硬币面值为ai，现在总队长想知道如果丢掉了某个硬币，剩下的硬币能 组成多少种价值？（0价值不算）
Input
第一行一个整数n 第二行n个整数：a1,a2…an。 1<=n<=100,1<=ai<=3000
Output
输出n行，第i行表示没有第i个硬币能组成多少种价值。
Sample Input
31 1 3
Sample Output
332
HINT
题解：我们考虑先将所有硬币的方案数球出来，而每次取出一个硬币，相当于在最后放那个硬币
考虑dp方程：f[n][j]=f[n-1][j]( 0<j<k)
f[n][j]=f[n-1][j-k]+f[n-1][j]（k<=j)
Problem C: 小Y的炮
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 9 Solved: 4[][][]Description
小Y最近开发出了批量制造大威力轰山炮的方法。才过去不到几个月，小Y就制造出了M门款 式不同的轰山炮。第i门轰山炮发射一次，能使一座当前高度不高于Ai的山的高度降低Di（ 当然山的高度不能轰到0以下）。应政府要求，小Y要用他开发的轰山炮轰平开发区的几座山 。由于开发区急需土地资源，政府要求小Y轰平尽量多的山（轰平：使山的高度降低至0）。 但是小Y制造的弹药有限，导致他最多只能发射K次。 小Y想知道，他最多能轰平几座山？轰平这些山后，弹药最多还够他发射几次？
Input
第一行三个正整数N,M,K，分别表示山的数目、轰山炮的款式数目、最多发射次数。 接下来N行，每行一个正整数Hi，表示第i座山的高度，输入数据保证Hi是降序的（从大到小 ）。 接下来M行，每行两个正整数Ai,Di，分别表示第i款轰山炮能轰的山的最高高度，和轰掉的 山高度的减少值。 N<=250000,M<=500,K,Hi,Ai<=10^18,Di<=500
Output
一行两个整数Max,Remain,分别表示最多轰平的山的数目和轰平这些山后最多的剩余发射次 数。
Sample Input
3 2 386210 66 5
Sample Output
2 1 题解：我们考虑将我们的炮的类型进行某种排序，最后肯定会留下一种情况：轰的限制高度低，但是轰的数量多或者
轰的限制高度高，但是轰的数量少，于是我们可以利用这个数列进行一些操作即可！
Problem D: tree
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 9 Solved: 5[][][]Description
给你一颗有根树，树上的每一条边都是只能从父亲走向儿子(即所有的路径都是没有转折的) 。给一个整数K，问你树上有多少条路径满足路径上的边权之和为K。
Input
第一行给二个整数n，p，k。n表示树的大小，p表示根,k如题目描述。 接下来n-1行，每行三个整数ai,bi,ci。表示边(ai,bi)，权值ci。 10<=n<=200000。1<=p<=n。1<=ci<=10^5。1<=k<=10^5
Output
输出一个整数，表示满足条件的路径总数。
Sample Input
5 2 22 1 22 3 13 4 13 5 1
Sample Output
3
HINT
题解：开始没看到只能从父亲转移过来，想了树的分治，但是发现复杂度不对，于是仔细读题，
发现题目本意，直接倍增即可，因为到一个点距离为K的只有一个；
Problem E: Poem
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 4 Solved: 3[][][]Description
汉字拼音共含23个声母：b,p,m,f,d,t,n,l,g,k,h,j,q,x,zh,ch,sh,r,z,c,s,y,w；共含24个韵母：a,o,e,i,u,ü,a i,ei,ui,ao,ou,iu,ie,ue,er,an,en,in,un,ün,ang,eng,ing,ong；共含3个介母：i,u,ü,不过ü基本不会出现在 书写格式内。一个汉字可能是单独某个韵母，也可能由某个声母+某个韵母组成的，还可能是由某个声母+某个介母 +某个韵母组成的。押韵在此题中的定义：假如两句话的最后一个字的韵母相同，则称这两句话押韵。 [上为前提知识] 小Y最近很无聊，无聊到了什么事情都不想做，只想用键盘和搜狗拼音打字法随便输一些字母，打出一堆汉字来。 不知不觉中，小Y打出了N个汉字。小Y发现一个很有趣的现象：不改变N个汉字的位置，将其分成若干段，保证每段 的汉字的位置都是连续的，且每段的汉字数目都相同。然后将每段作为一句诗，读出来。当然一般的诗没什么意思 ，小Y想要让诗句能够基本押韵。基本押韵的意思就是，所有诗句中至少要有一半（假如共K句，则一半为[K/2]向 上取整）押韵，即韵母相同。小Y想知道，做到基本押韵的话，他的诗最多能有多少句。
Input
第一行一个正整数N，分别表示汉字的总数。 接下来一行，共N个汉字的拼音，相邻的拼音之间用1个空格隔开。方便起见，所有的ü被v代替。 N<=200，出现的拼音都是现实生活中存在的。
Output
一行一个整数Ans表示最多的句数。
Sample Input
20chuang qian ming yue guang yi shi di shang shuang ju tou wang ming yue di tou si gu xiang
Sample Output
4题解：直接暴力即可，但是觉得写AC自动机好写一点实际上就是trie树毕竟没有fail指针
Problem F: poker
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 6 Solved: 4[][][]Description
一副扑克牌有n张牌。一般你买的一副新扑克牌里除了这n张牌外还会有一些张特殊的牌，如 果你不小心弄丢了n张牌中的某一张，就可以用特殊牌来代替，但是如果你弄丢两张的话就 没有办法了，因为特殊牌上的图案是一样的。 现在你得到了很多扑克牌，准确来说，n种牌你各有a1、a2、……、an张，同时你还有b张特 殊牌，现在你需要从这些牌中整理出若干副牌供大家使用。整理出的一副牌可以由n种普通 牌各一张组成，也可以由n-1种普通牌各一张再加一张特殊牌组成。 请你设计出一种方案，整理出尽可能多的牌。
Input
输入包括2行 第一行给出n和b1 第二行给出a1,a2…an。 1<=n<=1000000牌的数量<=10^6
Output
输出最多能整理出的牌的副数。
Sample Input
5 55 5 5 5 5
Sample Output
6题解:考虑二分答案+抽屉原理即可
Problem G: 国家宝藏
Time Limit: 10 Sec Memory Limit: 1 MBSubmit: 4 Solved: 2[][][]Description
话说ZY日行一善，终于天可怜见，某日他居然进入了传说中的国家宝藏。这个区域是个N*N 的矩形方块。每个方块可能放置的是宝物或者是不可翻越的障碍。当某个方块放的是宝物时 ，如果其上下左右的某个方块放置的亦是宝物时，则两个方块则被认为是互相连通的。ZY想 到所有的宝物都拾走，但单凭他一个人的力量是不行的，此时地也怜见了，从地下冒出这个 矩形方块的地形图，ZY有了这张地图就可以Judge出整个矩形方块被分成了多少个连通块， 哈哈，此时他拿出他心爱的G11，召唤Oi队员来帮他的忙，但到底要叫多少个人来呢？（我 们假设一个人可以占据一个连通块）于是这个光荣的任务就交给你了，ZY和他的Oi队员们今 后能否过上幸福的生活就全看你的了……
Input
第一行一个数字N，代表矩形方块的长，N<=1000 接下来的N行N列，代表宝物的分布，其中0代表宝物，1代表障碍。
Output
请输出有多少个连通块。
Sample Input
【输入样例1】30 0 01 1 10 0 0【输入样例2】30 1 10 0 01 1 0 题解：直接并查集 但是卡内存，所以请小心！
Problem J: 多项式相乘
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1 Solved: 1[][][]Description
多项式相乘的展开是一件相当烦琐的工作，FireDancer快要烦死了。他把这个任务交给了你 。为了简化，他只要你做一种多项式的展开，该种格式为(x+a1)(x+a2)(x+a3)…(x+an-1)(x +an),n的值事先给你。当n=2，展开式为x2+x(a1+a2)+a1a2；当n=3时，展开式为（最上面的 数字为的是让你看清展开式的总长度）。每一个字符（包括"x"、"a"、"（"、"）"、"+"） ，每一个指数的每一个数字，每一个下标的每一个数字长度都为1。如n=3时，总长度为40。
Input
一个整数n（0<n<=1,000,000,000）。
Output
若展开式的总长为t，则输出t mod 10000（t除10000取余）。
Sample Input
3
Sample Output
40
HINT
题解：组合数学随便写，这个东西自己推的比较好
Problem M: 数列计数
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 5 Solved: 2[][][]Description
不仅循环数有美好的性质，单调的数列更有美好的性质。 moreD喜欢单调的数列胜于循环数。所以他决定一天内背上所有长度为N的单调数列。 这个单调数列必须严格不上升或者严格不下降，并且所有的数字必须在[1,n]内。又到了每 日计数的时间了，又要请你帮助moreD计算出有多少符合条件的数列了。
Input
输入第一行仅包含一个整数N,表示数列的长度。N<=1,000,000
Output
输出一行仅包含一个整数，表示符合条件的数列有多少个。当然，数列的个数可能会有很多 ，moreD只需要知道答案mod 2,000,003的值就可以了。
Sample Input
2
Sample Output
4//答案是4，数列有[1,1] [1,2] [2,1] [2,2]
HINT
题解：因为单调递增和单调递减--对应，所以只要求一个再*2-重复的n个，
考虑一个dp方程表示f[i][j]代表第i个选的是j的方案数，f[i+1][j]+=f[i][k](1<=k<=j)
发现这个就是一个前缀和，于是发现就是求n次前缀和，再次发现实际上就是组合数
于是o（n）暴力计算即可
Problem N: 堆蛋糕
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 3 Solved: 2[][][]Description
其实moreD是一个十分犀利的蛋糕师。他最喜欢的食物就是蛋糕。 一天，他自己做出了N个圆柱状的蛋糕，每个蛋糕都有一个底面圆的半径Ri。高度都是一样 的。 moreD在开始享用他的蛋糕大餐之前忽然觉得，圆柱状的蛋糕没有什么诱惑力。moreD看到了 别人结婚用的蛋糕都是很多很多层的，那样的蛋糕才比较给力。但是堆太多层的蛋糕比较困 难，于是moreD想要堆出许多三层的蛋糕，再开始自己的蛋糕大餐。 当然，作为蛋糕师，moreD在堆蛋糕的时候不会对蛋糕的形状有任何破坏，而且，moreD希望 三层蛋糕的半径从上往下严格递增。这才是一个普通的好蛋糕。 但是moreD在考虑一个十分重要的问题，最多可以堆出多少三层蛋糕呢？
Input
输入第一行仅包含一个整数N,表示蛋糕的数量。 接下来N个整数，表示每个蛋糕半径的大小Ri。 N<=3,000,000 Ri<=N
Output
输出一行仅包含一个整数，表示最多可以做成多少个蛋糕。
Sample Input
61 2 3 4 3 2
Sample Output
2
HINT
题解：考虑枚举答案k，凡是出现次数大于k的按k个算，因为抽屉原理，
放k+1放在k里面势必会有一个盒子有两个一样的无法保证严格单调
于是乱搞即可
Problem O: 卡片游戏
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 1 Solved: 1[][][]Description
有N只moreD在玩一个卡片游戏： 首先，桌子上有M张卡片，这M张卡片分别有一个唯一的1～M的编号。N只moreD在桌子上抢牌 。每个人最后的得分是所得的所有卡片编号的乘积(如果一张卡片都没取，得分为1)。 这N只moreD最后报出了自己的得分。你的任务是写一个程序，判断有没有人说谎。
Input
输入第一行一个整数T，表示T组测试数据。 对于每组测试数据： 第一行：两个用空格隔开的整数：N和M，表示moreD的数量和卡片的数量 第二行：有N个正整数Ai，表示每只moreD报出的得分。 N<=5 M<=100 Ai<=50000 t<=10
Output
输出T行，每行输出'Yes'或'No'，表示'Yes'表示不可能没有人说谎 , 'No'表示可能没有人 说谎。
Sample Input
32 32 32 33 62 54 6
Sample Output
NoYesNo//对于第一个数据，存在第一个人抢到编号为2的卡片，第二个人抢到编号为3的卡片就可以满足这样的情形了，所以可能没有人说谎。对于第二个数据，不存在任何一种抢牌方案使得两人的得分满足这样的情形，所以不可能没有人说谎。 题解：考虑暴力dfs每个数给那个人，用判质数来剪枝
Problem P: 泡泡浴
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 1 Solved: 1[][][]Description
其实moreD是一个十分爱干净的孩子，最近moreD迷恋上了泡泡浴。迷恋泡泡浴的原因除了泡泡特别好玩之外，还由 于洗泡泡浴的浴缸十分奇怪，这是个地面参差不齐的浴缸。我们可以把浴缸看成N*M的矩阵，那么矩阵上的每个元 素为该位置浴缸的高度。由于水往低处流，相邻的格子的水面高度不同，高处的水会往低处去。浴缸当然要有出水 口，出水口在某个格子上。而且浴缸的边缘可以看作无穷高。然后大家肯定会发现，洗完泡泡浴后，把水放掉后， 可能有些地方会积水。即水不能通过出水口流出。moreD就是喜欢看看这些积水。moreD测量了一下，自己放水之前 浴缸的所有位置的水面高度均为K(除了浴缸底部高度大于K的格子)。如果浴缸底部高度大于K，那么这个格子没有 水，水面高度可以当作是浴缸底部高度。然后moreD打开了出水口。请你帮moreD预测一下，当出水口不再出水了， 浴缸每个格子的剩余的水高度是多少。(剩余的水的高度=水面高度-浴缸底部高度)
Input
输入第一行仅包含三个整数N,M,K，表示浴缸的大小与初始每个格子的水面高度。 接下来N行，每行M个整数，表示每个格子浴缸底部的高度A[i,j]。 接下来一行两个数r和c，表示出水口的行和列。 N,M<=800 A[I,j]<=10000
Output
输出N行,每行包含M个整数，表示每个格子的剩余水的高度。
Sample Input
3 3 666 9 17 8 16 8 13 2
Sample Output
2 0 71 0 72 0 7
HINT
题解：考虑最小值spfa即可
Problem Q: 树的合并
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 6 Solved: 3[][][]Description
话说moreD经过不懈努力，终于背完了循环整数，也终于完成了他的蛋糕大餐。 但是不幸的是，moreD得到了诅咒，受到诅咒的原因至今无人知晓。 moreD在发觉自己得到诅咒之后，决定去寻找闻名遐迩的术士CD帮忙。 话说CD最近在搞OI，遇到了一道有趣的题目： 给定两棵树，则总共有N*M种方案把这两棵树通过加一条边连成一棵树，那这N*M棵树的直径 (树的直径指的是树上的最长简单路径) 大小之和是多少呢？ CD为了考验moreD是否值得自己费心力为他除去诅咒，于是要他编程回答这个问题，但是这m oreD早就被诅咒搞晕了头脑，就只好请你帮助他了。
Input
第一行两个正整数N,M，分别表示两棵树的大小。 接下来N-1行，每行两个正整数ai,bi,表示第一棵树上的边。 接下来M-1行，每行两个正整数ci,di,表示第二棵树上的边。 N<=10^5,M<=10^5,1<=ai,bi<=N,1<=ci,di<=M
Output
一行一个整数，表示答案。
Sample Input
4 31 22 32 41 32 3
Sample Output
53
HINT
题解：因为直径只有两棵树的直径最大值或者两条最长链之和
于是dp即可，dp记录f，g数组表示最长链和次长链
Problem R: 电费结算
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 2 Solved: 2[][][]Description
WZK最近靠租房发家致富了。作为WZK老同学的你也要租房，于是WZK决定不要房租，但是电 费还得付。以下是用电价格： 
举个例子吧。如果你用电为10123千瓦时，那么要付2 * 100 + 3 * 9900 + 5 * 123 = 3051 5块钱（好贵）。 到结算电费的日子了，可是WZK家里只有一个总电表，也就是统计你和WZK总共用的电量。但 是WZK有办法告诉你以下信息： 1).如果按照总电表来看要交给供电局的钱A。（也就是两个人用电量加起来一起算钱） 2).你和WZK如果分开付的话，你们付的钱的差值B。 现在你想知道如果你单独算钱的话，需要付多少钱。当然，你的用电量不会比WZK多。 举个例子：如果你们一起算钱要付1100，并且如果分开来算，你们的差值是300的话，那么 你用了150kwh，WZK用了250kwh。让我们来验算一下：你们一共用电400kwh，所以要付2 * 1 00 + 3 * 300 = 1100，你单独要付2 * 100 + 3 * 50 = 350，WZK单独要付2 * 100 + 3 * 150 = 650。所以最后，你只需要告诉我你单独要付350元。
举个例子吧。如果你用电为10123千瓦时，那么要付2 * 100 + 3 * 9900 + 5 * 123 = 3051 5块钱（好贵）。 到结算电费的日子了，可是WZK家里只有一个总电表，也就是统计你和WZK总共用的电量。但 是WZK有办法告诉你以下信息： 1).如果按照总电表来看要交给供电局的钱A。（也就是两个人用电量加起来一起算钱） 2).你和WZK如果分开付的话，你们付的钱的差值B。 现在你想知道如果你单独算钱的话，需要付多少钱。当然，你的用电量不会比WZK多。 举个例子：如果你们一起算钱要付1100，并且如果分开来算，你们的差值是300的话，那么 你用了150kwh，WZK用了250kwh。让我们来验算一下：你们一共用电400kwh，所以要付2 * 1 00 + 3 * 300 = 1100，你单独要付2 * 100 + 3 * 50 = 350，WZK单独要付2 * 100 + 3 * 150 = 650。所以最后，你只需要告诉我你单独要付350元。 Input
输入仅一行，包含两个整数A和B（1 ≤ A, B ≤ 10^9），含义同上。 输出描述： 输出仅一 行一个整数，代表你单独算需要付的钱。数据保证解唯一。
Output
输出仅一行一个整数，代表你单独算需要付的钱。数据保证解唯一。
Sample Input
1100 300
Sample Output
350
HINT
题解：傻逼模拟
Problem S: 序列和
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 5 Solved: 4[][][]Description
N个数排成一个环，请选出不超过K段的连续的数，段与段间不能重叠，且使得选出的数和最大。
Input
第一行包含两个正整数N和k。 接下来1行描述这N个数。 K<=10，N<=100000
Output
包含一个数，即要去的最大的和。
Sample Input
9 22 -1 2 -1 2 -4 1 -1 2
Sample Output
7
HINT
题解：不考虑环，直接dp即可，考虑如果答案再存在（1--i）+（j--n)的这种情况，那么最小值一定不存在这种情况
于是不考虑环求一遍最大值Max，和一遍最小值Min，于是答案为max（sum-Min，Max）
Problem T: 计蒜姬
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 3 Solved: 2[][][]Description
兔纸们有一个计蒜姬，奇怪的是，这个计蒜姬只有一个寄存器X。兔纸们每次可以把寄存器 中的数字取出，进行如下四种运算的一种后，将结果放回寄存器中。 1.X=X+X 2.X=X-X 3.X=X*X 4.X=X/X 已知初始时寄存器里的值为A，兔纸们想要知道，是否能通过若干次操作，使得最终寄存器 里的值是B。如果可能，它们还想知道最少的操作次数。
Input
包含两个正整数A，B。
1 ≤ A，B ≤ 1000000000
Output
一个整数，即最少操作次数，如果不存在方案，则输出-1。
Sample Input
3 4
Sample Output
3//第一次：3/3=1第二次：1+1=2第三次：2*2=4
HINT
题解：傻逼dfs
Problem U: 修建道路
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 2 Solved: 1[][][]Description
sub打算修建一条磁悬浮列车的通道连接现代OI王国的首都(编号为1)和sub的家(编号为n)。 当然，现代OI集团的n(1<=n<=1000)座城市之间没有任何的磁悬浮通道，而sub通过实地勘测 发现，一共有p(1<=P<=10000)对城市之间可以建磁悬浮通道。 在这p对城市之中，第i对城市分别为ai,bi，它们间的距离为li(1<=li<=1000000)。数据中 保证每对{ai,bi}最多只出现1次， 现代OI集团决定免费帮sub修建最多k条线路的磁悬浮通道，而sub要花的钱，是他自己负责 修建的那些线路的最长的那条路的长度。 sub当然想花最少的钱......他想知道他最少能花多少钱。
Input
第1行:3个用空格隔开的整数:n,p,以及k 第2..p+1行:第i+1行为3个用空格隔开的整数:ai,bi,li
Output
输出1个整数,为sub在这项工程上的最小支出.如果任务不可能完成,输出-1
Sample Input
5 7 11 2 53 1 42 4 83 2 35 2 93 4 74 5 6//现代OI集团一共有5个城市。城市1不能直接与城市4,5相连。城市5不能直接与城市1,3相连。其余所有城市间均可修建轨道。现代OI集团可以免费为sub修建一条线路。
Sample Output
4//sub选择如下的修建方案:1->3,3->2,2->5，这3条路线的长度分别为4,3,9。sub让现代OI集团免费修建那条长度为9的路线，于是，他所需要花费的钱为4。
HINT
题解：枚举答案+spfa即可