Spylft-CSDN博客

原创 Codeforces Round #316 (Div.2)Tree Requests

又是莫名RE系列…首先一个想法,就是把字母转化成一个二进制位,因为如果一个字符出现两次,那么它们就可以被配成一对,也就是说,这两个就和没有是一样的.那这对我们有什么帮助呢?那就和异或一样了,两个状态合并的同时,相同为0,不同为1,这样的话,最后合并出来的状态里有的二进制1的数量必定不大于1,这样的状态才可能被变成回文串.所以加入和删除都是异或操作.接下来就是怎么知道一棵子树下面的某一行的异

2016-11-11 21:07:50 379 1

原创 POI2014 Ant colony

很显然的一个想法就是通过有食蚁兽的那一条边把整棵树分成两棵树.这样就可以两边乱搞了对于一棵子树,我们现在存一下现在的上界r和下界l,遇到一个度为k的节点,分开之后它的上界和下界会变成[l∗k,(r+1)∗k−1][l*k,(r+1)*k-1].然后遇到叶子节点的时候,我们在原序列中询问[l,r][l,r]之间的数有多少个就行了,只用把原序列排个序,二分一下就行了.#include<cstdio>

2016-11-11 11:04:41 448

原创 POI2014 Solar Lamps

第一件要干的事就是把它给你的坐标用它给你的两个向量表示出来,事实上这件事就够令人发狂了…所以开始解方程.我们有 {a∗x1+b∗x2=Xa∗y1+b∗y2=Y\begin{cases}a*x1+b*x2=X\\a*y1+b*y2=Y\end{cases} 解得: ⎧⎩⎨a=X∗y2−Y∗x2x1∗y2−x2∗y1b=X∗y1−Y∗x1x2∗y1−x1∗y2\begin{cases}

2016-11-09 21:11:12 549

首先要想到dp,那么定义dp[i]为走到第i棵树时的最少劳累值.那么dp转移的时候就要考虑到两点之间的高度大小关系,所以要分类讨论.那么这样的dp就是O(n2)O(n^2)的了.所以考虑优化,因为我们发现一个点的dp值只可能够由它的前k个来转移,所以想到使用单调队列来优化dp.然后什么样的值才是最优的呢?首先dp值小的一定更优!因为dp值只能够一个一个地发生变化,所以无论高度差如何,只要dp值小1,

2016-11-08 19:24:16 540

原创 POI2014FarmCraft

大意: 就是给你一棵树,然后树上有n个节点,每条边的边权为1,然后每个节点有一个延时t,当你走过这个节点后,过了t时间之后,这个节点就被加入到已经经过的点的集合中,然后从1节点出发,在1节点结束,且1节点的计时只会在最后一次到1节点的时候开始. 求最少时间,能够经过所有的点.这道题的话,感觉就是一个状态定义出来后就只剩下码代码的树形dp了吧…那就开始定义状态.我们定义dp[i]

2016-11-08 16:36:01 611

原创 POI2014Criminals

这道题的话,首先是一个小贪心,枚举完在哪个点相遇之后,要得到这个点向左走多远才可以完成左边的序列,向右边走多远才可以完成右边的序列.这两个都取最小,然后再看一下两边之外的地方是不是有相同的元素,这样的话就差不多了.但是这样的话预处理比较麻烦.我的话是使用dp,dp[i]定义为现在这个点开始,是到达了需求序列中第i个点的最右边的开始位置.转移也是很扯淡…if(pl!=1)dp[pl]=dp[pl-1]

2016-11-07 22:32:04 418

原创 POI2014Card

这道题的话,想法感觉也是很奇怪的…首先一个想法是如果有了第一个值,那么就可以贪心地去选取数字了,每次都选能选的最小的,这样肯定最优.那么我们就去确定这个数,即可以讨论而得出一段区间右端点最小是什么.我们可以看出,一段区间的左端点,要么是左边的第一个数,要么是左边的第二个数,然后对于一段没有被修改过的区间,它们定下来左端点后,右端点的最小值是固定的.然后用线段树来优化它,每次进行单点更新,区间查询,就

2016-11-07 18:30:37 529

原创 POI2014Bricks

POI2014 Bricks正解的话是贪心,就是先把剩下最多的放到现在这个地方来,如果有多个最多的,那么就把颜色与最后一个颜色相同的取出来,不然就随便放一个.然后用堆来维护这个信息,所以正解是O(nlogn)O(nlogn)的.#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<queu

2016-11-07 15:26:00 374

原创 POI2014Salad Bar

POI2014 Salad Bar这道题的大意就是给你一个字符串,里面只含有p和j,求一个最长的子串,使得从左边开始,p的个数一直比j多,从右边开始也一样.这道题的话,一开始想歪了,就先对每个字符,算出来以它为起点往右最多能在哪里,然后再算出来以它为起点往左最多能走到哪里,这样的话,一个满足条件的子串一定满足R[l]>=r,L[r]<=lR[l]>=r,L[r]<=l,然后按照左边小的排一下序,然后

2016-11-04 20:02:41 401

原创 NOIP复赛的各种模板

一：文件读入输出freopen("Add.in","r",stdin);freopen("Add.out","w",stdout);就是类似于这种,比如一道题目的文件名为Add,那么就可以通过这样的格式来完成读入以及输出.二:读入输出挂void Rd(int &res){ res=0;char p; while(p=getchar(),p<'0'); do{

2016-11-04 15:24:08 1380 2

原创 Topcoder SRM 701 Div2

Topcoder SRM 701 Div2话说终于又回到了Div1的坑里.上一把掉得太惨了啊…黄名掉到绿名…SquareFreeString这题还是很简单的吧(zqh被&和==的优先级坑了呢,重回灰名的他...).这道题就是在一个字符串中找一个子串,如果这个子串为两个相同的串拼接而成,那么这个串就被称为是not square-free,反之,它就是square-free.那么就随便搞搞就行了,枚举一

2016-10-27 18:49:04 733

原创 2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Prefer

2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)话说这场比赛就是被小C叫过来水了一场啊...然后就和机房里的人组了个队(一人rating撑起一片天). 然后就只写了7道题,虽然我只写了4道水题(I题没写出来真是可惜),并且WA了无数次.

2016-10-25 12:41:34 1262 1

原创 [BZOJ2154] Crash的数字表格

[BZOJ2154] Crash的数字表格题目的意思就是求出∑ni=1∑mj=1lcm(i,j)\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j).我们可以把问题进行转换,有: ∑i=1n∑j=1mlcm(i,j)=∑i=1n∑j=1mi∗jgcd(i,j)\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)=\sum_{i=1}^{n}\sum_{j=1

2016-10-20 18:12:00 434

原创莫比乌斯反演

莫比乌斯反演最近学了一下莫比乌斯反演(实际只学了2天,旁边cchyh还一直吵吵吵),所以还是来写写现在能写出来的东西吧.莫比乌斯反演,指的是对于一个数论函数F(n)F(n),有 F(n)=∑d|nf(d)F(n)=\sum_{d|n}{f(d)}这里f(d)f(d)是另一个数论函数,那么就会有 f(n)=∑d|nμ(d)F(nd)f(n)=\sum_{d|n}{\mu(d)F(\frac{n}{

2016-10-20 16:30:42 613

原创 Codeforces Round #376 (Div. 2)

这次还好吧,总算进紫名了(25分比了3场才加上去...也是可以),而且还在这个晚上写完了所有题. 话说这次也太水了,F题和它的难度不成正比,所有题的代码都短的可以,除了WA了两次的D题. E题没看太亏了,几乎一模一样的题都做过… 好了好了开始讲题目… A:Night at the Museum Task: 给你一个转盘,以及一个字符串,一开始的转盘指向’a’,然后求若要输出此字

2016-10-17 07:44:17 628 5

原创 Codeforces Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)

因为自己太水了所以写不出多少题目,昨天只写了3道,至少没掉分嘛对吧.(明明是第4题题目看了好久才看懂……) C Ray Tracing Task: 一个n*m的矩阵中有k个点,你现在有一道从(0,0)向外发射的光线,它能够沿y=x这条直线射,其反射遵从光的反射定律,每秒钟它能够经过2√\sqrt{2}的距离,现在请问每个点被经过的最小时间,若不会被光线经过,则输出-1. S

2016-10-09 16:52:53 447

原创 Codeforces Round #375 (Div. 2)

只写了5题所以只说5题…… A Task: 坐标轴上有三个点,求它们到坐标轴上某个点的距离和的最小值. Solution: 显然只要选个最大值和一个最小值相减的差就是答案了,表示它们在中间相遇. 于是这题就不发代码了. B Task: 给你一个字符串,求括号内的单词数和括号外的最长单词长度,单词被括号(‘(‘,’)’)或下划线(‘_’)分割.

2016-10-04 16:32:00 321

原创 Miller Rabin

正常的素数判定,要么是直接枚举因子,通过根号n的复杂度来完成,这样时间可能不够,又或是先通过打表之后,去查表,可是这样空间复杂度过大.所以说,对于小于1e18的数,这些方法是毫无作用的.那么怎么来判断小于1e18的数是否为素数呢?这里就要用到即将介绍的Miller Rabin素数判定法.这个算法的核心是费马小定理,费马小定理的内容是:if p is a prime then x^(p-1)

2016-10-02 15:07:11 605

原创 Poi2010 Railway

Task: A railroad siding consists of two (dead-end) sidetracks 1 and 2. The siding is entered by track A, and left by track B (see figure below). There are cars on track A, numbered from to

2016-10-02 15:06:46 921

原创 Poi2010 Divine Divisor

Solution:首先我们想到吧所有的数质因子分解,所得到的每个质因子的个数的和的最大值就是要求的k,而我们设这个最大值出现的次数为m,则我们可以知道,任意个这样的质因子的乘积都是可行的一种解,所以第二个答案就是2^m，注意到这个值可能会很大,所以我们要用高精乘法.那么我们再观察一下现在这个数的范围->[1,1e18],根本无法去进行完全的因数分解,但是我们可以知道,如果这个范围内的数有三个或以上的

2016-10-02 15:04:37 600

原创 POI2010 Hamsters

Solution首先可以Hash搞出每个名字连在另一个名字后面所需要增加的字母数量.而有些人会担心搞完这个后就超时了,但是如果这个都会超时,这道题目还有什么写的必要?所以大胆去干就好了.那么下面我们给出不会超时的证明:首先对于两个串A,B,我们需要比较的复杂度是min(A.length(),B.length()),那么我们可以知道,当A,B两个串的长度越接近,我们所要比较的次数越多(min(A.le

2016-10-02 15:03:24 415

原创 Codeforces Round 371 D Animals and Puzzle

Task: 给你一张01图,以及t个询问,每个询问为(x1,y1,x2,y2),指在以(x1,y1)为左下角,以(x2,y2)为右下角的矩形中,最大的全为1的矩形的大小. Sample Input 3 4 1 1 0 1 0 1 1 0 0 1 1 0 5 1 1 2 3 2 1 3 2 3 2 3 4 1 1 3 4 1

2016-09-21 22:18:19 442 1

原创 Codeforces Round 371 C Sonya and Problem Wihtout a Legend

Task: 给你一个长度为n的序列,每次操作能使序列中的数+1或-1,求最少的操作数,使得序列严格递增. Sample Input 5 5 4 3 2 1 Sample Output 12 Hint 1<=n<=3000Solution: 首先我们先明白一件事:我们有A[i]<A[i+1]A[i]<A[i+1],也就可以转化为A[i]−i<=A[i

2016-09-20 13:26:43 598

原创 USACO2014Open Gold Code Breaking

Task: The cows keep getting in trouble by taking rides on Farmer John’s tractor, so he has hidden the keys to the tractor in a fancy new safe in his office. Undeterred, the cows have vowed to

2016-09-19 14:37:39 914

原创 USACO2014Open Gold Cow Optics

Task: Farmer John’s cows would like to host a dance party in their barn, complete with a laser light show. Unfortunately, the only working laser they have found is located far away from the b

2016-09-19 14:35:19 927

原创 USACO2014Open Gold Fair Photography

Task: FJ’s N cows (1 <= N <= 100,000) are standing at various positions along a long one-dimensional fence. The ith cow is standing at position x_i (an integer in the range 0…1,000,000,000) a

2016-09-19 14:32:02 1063

原创 USACO2014Open Silver Odometer

Task: Farmer John’s cows are on a road trip! The odometer on their car displays an integer mileage value, starting at X (100 <= X <= 10^18) miles at the beginning of their trip and ending at

2016-09-19 14:20:14 859

原创 USACO2014Open Silver Dueling GPSs

Task: Farmer John has recently purchased a new car online, but in his haste he accidentally clicked the “Submit” button twice when selecting extra features for the car, and as a result the ca

2016-09-19 14:17:32 534

原创 USACO2014Open Silver Fair Photography

首先我们有一个前缀和的思想,就是说我们定义一个sum为1到n的和,则当sum[i]==sum[j]时(i<=j),i到j的奶牛中黑白奶牛数相同.而既然我们能将白奶牛变成黑奶牛,那么只要求一段最长的连续序列,使白奶牛数量多于黑奶牛就行了,但有一点要保证,就是说奶牛数量要是偶数.那么我们不妨将白奶牛设为1,黑奶牛设为-1,这样,一段合法的区间就是sum[j]-sum[i-1]>=0(i<=j&&(j-i

2016-09-19 14:14:03 491

原创 USACO 2012 March Gold Large Banner

Bessie is returning from a long trip abroad to the Isle of Guernsey, andFarmer John wants to mount a nice “Welcome Home” banner for her arrival. Farmer John’s field has integer dimensions M x N (1 <=

2016-09-13 16:42:15 622

原创 SRM 510 Div1 1000 TheLuckyBasesDivOne

Task:给你一个数N,把N在B进制中的转化存进一个数组S,若能满足S[0]∗B0+S[1]∗B1+S[2]∗B2+...+S[t]∗Bt==NS[0]*B^0+S[1]*B^1+S[2]*B^2+...+S[t]*B^t==N并且S[i]在十进制中的每一个数字为4,要么为7,对于这样的一个B,我们称它为N的Lucky数,求N的Lucky数有多少个,若有无限个,则输出-1.(1<=N<=1e16)S

2016-09-13 16:38:52 441

原创 SRM 510 DIV2 1000 TheLuckyBasesDivTwo

Task:给你一个数N,把N在B进制中的转化存进一个数组S,若能满足S[0]∗B0+S[1]∗B1+S[2]∗B2+...+S[t]∗Bt==NS[0]*B^0+S[1]*B^1+S[2]*B^2+...+S[t]*B^t==N并且S[i]要么为4,要么为7,对于这样的一个B,我们称它为N的Lucky数,求N的Lucky数有多少个,若有无限个,则输出-1.(1<=N<=1e12)Solution:首

2016-09-13 16:35:03 345

原创 SRM 542 DIV1 500 StrangeDictionary2

Task:给你若干个字符串,然后给它们进行排序,但排序依照的位数是一个随机生成的排列(就是你可能对两个长度为三的字符串,先将它们的第2位进行比较,再比较第1位,再比较第3位才能得到它们的大小关系),那么求出每个字符串的期望排序后在第一位(最小)的可能性,(n<=16)Solution:这是一道状压dp题,我们定义dp[S][i]为当前剩下的集合为S,第i个元素可能是最小的可能性,那我们先预处理出如果

2016-09-13 16:33:22 362

原创 SRM 542 DIV2 950 StrangeDictionary

Task:给你若干个字符串,然后给它们进行排序,但排序依照的位数是一个随机生成的排列(就是你可能对两个长度为三的字符串,先将它们的第2位进行比较,再比较第1位,再比较第3位才能得到它们的大小关系),那么求出每个字符串的期望排序后的位置,(n<=50)Solution:对于两个字符串,我们数出第一个中比第二个大的字符有k1个,第二个中比第一个大的有k2个.那么我们就可以将ans[i]+=1.0∗k1/

2016-09-13 16:32:25 356

原创 SRM 570 DIV2 1000 CentaurCompany

Task给你一棵树,求在割去任意条边后,剩下的联通块的个数总和(全空也算是一个),也就是指那些使集内的点能只通过集内的点到达任意一个集内的点的点集.(点数<=50)Solution:我们把这个问题剖分成对于一棵树,在包含它的根时,有多少个这样的点集.那么在不包含它的情况可以递归下去求解. 那么只需要递归地求出儿子的解,然后在父亲上跑一个背包就好了.vector<int>edge[M];LL an

2016-09-13 16:29:16 448

原创 BZOJ 3437 小P的牧场

首先想到dp,我们定义dp[i]为在i造一个控制站,以及之前的最小消费. 所以有dp[i]=min(dp[j-1]+∑k=jib[k]∗(i−k)\sum_{k=j}^{i}b[k]*(i-k))+a[i]. 朴素的方法是O(N2N^2)的. 这显然过不了.所以我们去观察对于一个i,以及j,k这两种决策. 如果k比j优,则有dp[j−1]−dp[k−1]+∑l=jk−1b[l]∗(i−l)>

2016-09-11 13:57:48 389

原创约瑟夫问题

约瑟夫问题大意:有N个人站成一圈,从第一个人开始报数,从1开始报,若报到M的倍数的人,就必须离开游戏.问最后剩下的胜利的人是谁. 首先我们可以很快想到去模拟游戏的过程,并打出如下代码:#include<cstdio>bool mark[30005];int main(){ int n,m; scanf("%d %d",&n,&m); int now=1,last=1,

2016-09-06 16:55:18 519

原创 USACO 2009 Open SkiLessons

我们定义dp[i][j]为当能力为i,时间为j时滑过的最多的次数(也是个很显然的定义嘛)初值为dp[1][0]=0,然后对于每个时间,有上课,滑雪,看小说三个方法,相应的搞一下就好了.把课程捆起来放到vector里,滑雪的时间,我们可以得到一个在能力为i时,花的最少时间Ski[i](当然越少越好)就是以下代码了.#include#include#include

2016-09-01 16:15:38 296

原创 USACO 2009 Dec Bobsledding

先把点按T排个序,再预处理一下,就是如果前一个点的速度减去与前一个点的距离都比这一个点的速度大,则将前一个点的速度改为这一个点的速度+两点距离.预处理完之后,我们有在上一个点的速度和下一个点的速度,先让他们两个速度一样,然后剩下l的时间,除以2加上现在速度v,更新一下答案就好.所以O(N)扫一遍就好了#include#include#include#include#

2016-09-01 15:35:13 652

原创 USACO 2009 Mar CowFrisbeeTeam

既然是求和为F的倍数的方案数,我们定义dp[i][j]为第j 头牛时和为i 的方案数,这是很基础的,我们又很容易得到若使i 模上F,答案并不会有区别,我们就将所有数模上F,同时得到的和也模上F,那么最多就只有1000种和的可能性[0,F-1].然后就是很平常的DP了.(这么简单的题目连Chongkan也写得出来吧……)#include#include#define M 2005

2016-09-01 15:34:23 436

空空如也

空空如也