8 思-卿

尚未进行身份认证

在校学生

等级
博文 609
排名 4k+

*Codeforces Round #202 (Div. 1)*

发烧了,烧了五天,吓死我了,还以为要挂了呢。幸好又活过来了。A.Mafia题意:n个人玩一个游戏,每次要选出来一个主持的,剩下n-1个人玩这个游戏。第i个人想玩ai轮游戏,问最少玩多少轮可以满足所有人的要求。思路:我的思路是二分搜索,先排个序,这样第一个人就是要玩轮数最少的,末尾的就是要玩轮数最多的。对于搜索的每个值,我的策略是先满足要玩轮数最少的那个人,这些轮都是由需要轮数最多的人那个人作为主持

2017-12-13 19:06:15

*Codeforces Round #201 (Div. 1)*

在出题人看到岛娘了,膜一下。感觉这场的题比上一场难了太多了。可能我太菜吧。AAliceandBob思路:连懵带猜做出来的。求出n个数字的gcd,每个数字都除以gcd,然后得到一个新的集合。集合中最大的数字即最终集合中数字的个数。减掉已有数字的个数,即游戏能玩几回合。根据奇偶性判断胜负即可。看了tutorial,才想到思路。假设有两个数字a,b,假设a>b,令d=gcd(a,b),a=xd,b=

2017-11-30 20:55:23

Codeforces Round #200 (Div. 1)

ARationalResistance思路:因为每个电阻的电阻是1,这就很好算了,比如要求的电阻是a/b,假设a>b,则要求电阻个数就是a/b+b/(a%b)+(a%b)/(b%(a%b))…,直到某一步的模运算那里能够整除。我也不知道为啥这样,找了俩数据,算了算是这个规律,那就这样算了。#include<bits/stdc++.h>usingnamespacestd;type

2017-11-25 20:39:35

SGU 106 The equation(扩展欧几里德)

没想起来怎么做参考:https://www.cnblogs.com/zjbztianya/archive/2013/03/12/2956835.html思路还是很简单的,ax+by=c,gcd(a,b)=d,则x=x0+(b/d)*t,y=y0-(a/d)*t,每个t确定一对解,现在已经知道x1<=x<=x2,y1<=y<=y2,代换一下,求出来t的范围即可,有多少个t的整

2017-11-14 19:19:30

poj 2891 Strange Way to Express Integers(一元线性同余方程组)

迭代求解方程组,拿板子就好了#include<stdio.h>typedeflonglongLL;constintN=11110;LLM[N],R[N];LLgcd(LLa,LLb){return!b?a:gcd(b,a%b);}LLextgcd(LLa,LLb,LL&x,LL&y){LLd=a;

2017-11-13 20:34:21

poj 2396 Budget(有源汇上下界可行流)

这题的建图真恶心。好不容易写完后结果还wa了,顿时生无可恋啊,看了下discuss,说不能输出负数,最后不能输出多余的空行,我把这俩都改了,就AC了,虽说那里说这是在zoj不能ac的原因,不过在poj也适用,哈哈。思路:每行为一个点,每列为一个点,给出的限制就是行列之间连线的流的上下界,初始下届为0,上界为INF。然后建好图之后,建立一个虚拟源点和虚拟汇点,源点和边连线,流量上下界为行的和,列和

2017-11-13 13:57:05

zoj 2314 reactor cooling(无源汇有上下界可行流)

初次接触,https://www.cnblogs.com/liu-runda/p/6262832.html,通过这个博客学习的建图方式。建好图后套板子即可。#include<bits/stdc++.h>usingnamespacestd;constintMAXN=300;constintINF=0x7fffffff;structedge{edge(){}

2017-11-12 20:57:46

hdu 3579 Hello Kiki(一元线性同余方程组)

和hdu1573基本一样。注意不能输出0,是最小正整数解#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=110,INF=0x3f3f3f3f;intM[N],R[N];intgcd(inta,intb){return!b?a:gcd(b,a%b)

2017-11-12 14:22:04

hdu 1573 X问题(一元线性同余方程组)

当中国剩余定理中的那些模数不互质的时候怎么解?就像解普通方程组一样,迭代求解同余方程组。思路很简单。过两天重新写个,换掉这个抄来的模板。代码是直接拿的模板,改都没改:http://blog.csdn.net/discreeter/article/details/70318677#include<bits/stdc++.h>usingnamespacestd;typedeflonglon

2017-11-11 19:28:03

poj 2114 Boatherds(树分治)

点分治,和poj1741Tree基本一样,就是统计数量那里不一样。#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd;constintMAXN=10010;constintMAXM=20020;structEdge{intto,w,next;}edg

2017-11-11 12:47:49

poj 1854 Evil Straw Warts Live(分治)

wa了好久,调了好久。。。。。思路:先判断能否形成回文串,然后分治,先让整个串的两端字符相等,找出最少移动次数,然后去掉两端,得到新串,使新串两端相等,找出最小移动次数,这样不停缩小规模,直到搞完整个串。#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd;constintMAXN=

2017-11-09 23:15:20

hdu 6143 Killer Names(第二类斯特林数)

生活总是那么操蛋,(a+b)%mod写成了(a+b%mod),找错找了一个多小时。。思路:m种字符,名字分两部分,都能放下n个字符。先取出名字的一部分,即n个位置。对于这n个位置,能放i种字符,i属于[1,min(m,n)],就是n个元素放进k个盒子里,并且盒子不同,所以要乘阶乘,这对应第二类斯特林数,对于某个i,共Cim∗S[n][i]∗fac[i]C^{i}_{m}*S[n][i]*f

2017-11-09 21:04:46

hdu 2643 Rank(第二类斯特林数)

n个人的名次,因为有并列排名的情况,所以共n种情况,只有1个名次(所有人并列第一)到一共n个名次。对于某种情况,假设现在有x个名次,每个名次不知道多少人,就是有x个盒子,每个盒子内至少分配一个人,即n个数的集合的划分为x个非空集合方法的数目,正好是第二类斯特林数,在这里还要计数不同的排列方式,即这x个集合的不同排列。#include<bits/stdc++.h>usingnamespaces

2017-11-09 13:16:17

hdu 3625 Examining the Rooms(第一类斯特林数)

n个门,最多打爆k个门,也就是最多有k个环(第一类斯特林数)。把1个环到k个环的情况全加起来,每次加的时候还要减去1号自己成环的情况。S[N][i]是n个元素i个环排列,S[N-1][i-1]就是1自己成环的情况。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;LLfac[22];LLS[22][22];

2017-11-09 12:13:20

hdu 4372 Count the Buildings(第一类斯特林数)

从前向后看可以看到F栋楼,去掉中间最高那栋楼,有F-1栋楼,看到的第一栋楼和看到的第二栋楼之间的楼,分给第一栋楼,属于同一组楼,后边的依次类推,共F-1组楼,对于每组楼,假设有X栋楼,去掉我们看到的这一栋楼固定在第一个位置(这一组最高的楼在最靠前的位置),剩下X-1栋楼随意排列,X-1栋楼的的排列就是X栋楼的环排列,这就分成了F-1个环排列,从后向前看的也是这样。这就是N栋楼形成了F+B-2个环排列

2017-11-08 21:40:04

poj 3237 Tree(树链剖分)

wa了半天。。懒惰标记那里要用异或来修改,wa的时候突然想到,万一两次反转相同的区间,反转就取消了,然而我的懒惰标记那里一直col[rt]=1,这样反转就没有取消。。。#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd;constintMAXN=1e5+10;constintIN

2017-11-07 23:12:13

FZU 2082 过路费(树链剖分,边权)

树剖裸题#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd;constintMAXN=5e4+10;structEdge{intto,next;}edge[MAXN*2];inthead[MAXN],tot;inttop[MAXN];intfa[MAXN

2017-11-07 20:10:05

poj 2763 Housewife Wind(树链剖分,边权)

树剖裸题,wa了好久,才发现线段树传错参数了。。。。#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd;constintMAXN=1e5+10;structEdge{intto,next;}edge[MAXN*2];inthead[MAXN],tot;int

2017-11-07 19:53:44

LightOJ 1348 Aladdin and the Return Journey(树链剖分)

树剖裸题,套kuangbin大佬的模板#include<bits/stdc++.h>usingnamespacestd;constintMAXN=30010;structEdge{intto,next;}edge[MAXN*2];inthead[MAXN],tot;inttop[MAXN];intfa[MAXN];intdeep[MAXN];i

2017-11-06 23:21:35

Aoj - 1313 Intersection of Two Prisms(数值积分)

挑战程序设计竞赛例题。。。我就抄了下代码。。。#include<bits/stdc++.h>usingnamespacestd;constintINF=0x7fffffff;constintMAXN=110;intM,N;intX1[MAXN],Y1[MAXN];intX2[MAXN],Z2[MAXN];doublewidth(int*X,int*Y

2017-11-06 20:06:38
奖章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!