1001 HDU4320 Arcane Numbers 1
GCD 0MS 无压力
代码：
View Code 
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #define LL __int64
5 using namespace std;
6 LL gcd(LL a,LL b)
7 {
8 return b==0?a:gcd(b,a%b);
9 }
10 int main()
11 {
12 LL a,b,c;
13 int t,k=0;
14 scanf("%d",&t);
15 while(t--)
16 {
17 k++;
18 scanf("%I64d%I64d",&a,&b);
19 c=gcd(a,b);
20 while(c>1)
21 {
22 a/=c;
23 c=gcd(a,b);
24 }
25 printf("Case #%d: ",k);
26 if(a==1)
27 puts("YES");
28 else
29 puts("NO");
30 }
31 return 0;
32 }
33
2 #include <cstdio>
3 #include <cstring>
4 #define LL __int64
5 using namespace std;
6 LL gcd(LL a,LL b)
7 {
8 return b==0?a:gcd(b,a%b);
9 }
10 int main()
11 {
12 LL a,b,c;
13 int t,k=0;
14 scanf("%d",&t);
15 while(t--)
16 {
17 k++;
18 scanf("%I64d%I64d",&a,&b);
19 c=gcd(a,b);
20 while(c>1)
21 {
22 a/=c;
23 c=gcd(a,b);
24 }
25 printf("Case #%d: ",k);
26 if(a==1)
27 puts("YES");
28 else
29 puts("NO");
30 }
31 return 0;
32 }
33
1005 HDU4324 Trangle LOVE
人人上有个神人说 直接计算每个点出度，没有两个出度相等的情况下为NO，其他为YES，就过了。果然如此。。。。
代码：
View Code 1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6 int main()
7 {
8 int a[2001];
9 int i,j,k=0,t,n,flag;
10 char b;
11 scanf("%d",&t);
12 while(t--)
13 {
14 memset(a,0,sizeof(a));
15 flag=0;
16 k++;
17 scanf("%d",&n);
18 for(i=0;i<n;i++)
19 {
20 getchar();
21 for(j=0;j<n;j++)
22 {
23 b=getchar();
24 if(b=='1')
25 {
26 a[i]++;
27 }
28 }
29 }
30 sort(a,a+n);
31 for(i=0;i<n-1;i++)
32 {
33 if(a[i]==a[i+1])
34 {
35 flag=1;
36 break;
37 }
38 }
39 printf("Case #%d: ",k);
40 if(flag)
41 puts("Yes");
42 else
43 puts("No");
44 }
45 return 0;
46 }
47
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6 int main()
7 {
8 int a[2001];
9 int i,j,k=0,t,n,flag;
10 char b;
11 scanf("%d",&t);
12 while(t--)
13 {
14 memset(a,0,sizeof(a));
15 flag=0;
16 k++;
17 scanf("%d",&n);
18 for(i=0;i<n;i++)
19 {
20 getchar();
21 for(j=0;j<n;j++)
22 {
23 b=getchar();
24 if(b=='1')
25 {
26 a[i]++;
27 }
28 }
29 }
30 sort(a,a+n);
31 for(i=0;i<n-1;i++)
32 {
33 if(a[i]==a[i+1])
34 {
35 flag=1;
36 break;
37 }
38 }
39 printf("Case #%d: ",k);
40 if(flag)
41 puts("Yes");
42 else
43 puts("No");
44 }
45 return 0;
46 }
47
1006 HDU4325 Flowers
比较裸的区间更新的线段树
代码：
View Code 1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 using namespace std;
5 #define lson l,m,rt<<1
6 #define rson m+1,r,rt<<1|1
7 #define LL __int64
8 const int N=100002;
9 LL add[N<<2];
10 LL sum[N<<2];
11 void pushup(LL rt)
12 {
13 sum[rt]=sum[rt<<1]+sum[rt<<1|1];
14 }
15 void pushdown(LL rt,LL m)
16 {
17 if(add[rt])
18 {
19 add[rt<<1]+=add[rt];
20 add[rt<<1|1]+=add[rt];
21 sum[rt<<1]+=add[rt]*(m-(m>>1));
22 sum[rt<<1|1]+=add[rt]*(m>>1);
23 add[rt]=0;
24 }
25 }
26 void build(LL l,LL r,LL rt)
27 {
28 add[rt]=0;
29 if(l==r)
30 {
31 sum[rt]=0;
32 return ;
33 }
34 int m=(l+r)>>1;
35 build(lson);
36 build(rson);
37 pushup(rt);
38 }
39 void update(LL L,LL R,LL c,LL l,LL r,LL rt)
40 {
41 if(L<=l&&r<=R)
42 {
43 add[rt]+=c;
44 sum[rt]+=(LL)c*(r-l+1);
45 return ;
46 }
47 pushdown(rt,r-l+1);
48 LL m=(l+r)>>1;
49 if(L<=m)
50 update(L,R,c,lson);
51 if(m<R)
52 update(L,R,c,rson);
53 pushup(rt);
54 }
55 LL query(LL L,LL R,LL l,LL r,LL rt)
56 {
57 if(L<=l&&r<=R)
58 {
59 return sum[rt];
60 }
61 pushdown(rt,r-l+1);
62 LL m=(l+r)>>1;
63 LL ret=0;
64 if(L<=m)
65 ret+=query(L,R,lson);
66 if(m<R)
67 ret+=query(L,R,rson);
68 return ret;
69 }
70 int main()
71 {
72 int t,k=0;
73 scanf("%d",&t);
74 while(t--)
75 {
76 k++;
77 int i,j;
78 __int64 a,b,c,d;
79 scanf("%I64d%I64d",&a,&b);
80 build(1,N,1);
81 for(i=0;i<a;i++)
82 {
83 scanf("%I64d%I64d",&c,&d);
84 update(c,d,1,1,N,1);
85 }
86 printf("Case #%d:\n",k);
87 for(j=0;j<b;j++)
88 {
89 scanf("%I64d",&c);
90 printf("%I64d\n",query(c,c,1,N,1));
91 }
92 }
93 return 0;
94 }
95
2 #include <cstring>
3 #include <iostream>
4 using namespace std;
5 #define lson l,m,rt<<1
6 #define rson m+1,r,rt<<1|1
7 #define LL __int64
8 const int N=100002;
9 LL add[N<<2];
10 LL sum[N<<2];
11 void pushup(LL rt)
12 {
13 sum[rt]=sum[rt<<1]+sum[rt<<1|1];
14 }
15 void pushdown(LL rt,LL m)
16 {
17 if(add[rt])
18 {
19 add[rt<<1]+=add[rt];
20 add[rt<<1|1]+=add[rt];
21 sum[rt<<1]+=add[rt]*(m-(m>>1));
22 sum[rt<<1|1]+=add[rt]*(m>>1);
23 add[rt]=0;
24 }
25 }
26 void build(LL l,LL r,LL rt)
27 {
28 add[rt]=0;
29 if(l==r)
30 {
31 sum[rt]=0;
32 return ;
33 }
34 int m=(l+r)>>1;
35 build(lson);
36 build(rson);
37 pushup(rt);
38 }
39 void update(LL L,LL R,LL c,LL l,LL r,LL rt)
40 {
41 if(L<=l&&r<=R)
42 {
43 add[rt]+=c;
44 sum[rt]+=(LL)c*(r-l+1);
45 return ;
46 }
47 pushdown(rt,r-l+1);
48 LL m=(l+r)>>1;
49 if(L<=m)
50 update(L,R,c,lson);
51 if(m<R)
52 update(L,R,c,rson);
53 pushup(rt);
54 }
55 LL query(LL L,LL R,LL l,LL r,LL rt)
56 {
57 if(L<=l&&r<=R)
58 {
59 return sum[rt];
60 }
61 pushdown(rt,r-l+1);
62 LL m=(l+r)>>1;
63 LL ret=0;
64 if(L<=m)
65 ret+=query(L,R,lson);
66 if(m<R)
67 ret+=query(L,R,rson);
68 return ret;
69 }
70 int main()
71 {
72 int t,k=0;
73 scanf("%d",&t);
74 while(t--)
75 {
76 k++;
77 int i,j;
78 __int64 a,b,c,d;
79 scanf("%I64d%I64d",&a,&b);
80 build(1,N,1);
81 for(i=0;i<a;i++)
82 {
83 scanf("%I64d%I64d",&c,&d);
84 update(c,d,1,1,N,1);
85 }
86 printf("Case #%d:\n",k);
87 for(j=0;j<b;j++)
88 {
89 scanf("%I64d",&c);
90 printf("%I64d\n",query(c,c,1,N,1));
91 }
92 }
93 return 0;
94 }
95
附：
官方题解：
1001
检查A中的质因子 是否都在 B中被包含。
1002
按位统计计算，如果枚举 那么复杂度就是 64 * N
第一条
当统计第K位的时候 可以注意到 第 B+T*A 和 B+（T+2^（K+1））*A 位是相同的
那么 第K位的时候 只需要统计2^K 次就可以了
第二条
当统计第K位的时候 可以注意到 连续的 (2^K)/A都是连续的0 或者连续的1 所以可以考虑直接连续记录(2^K)/A个结果。
那么 第K位的时候 只需要统计N / ((2^K)/A)次就可以了
综合 第一条 第二条 那么 第K位的时候 只需要统计 2^K/((2^K)/A) 复杂度 变为O(A)
总复杂度为64*A
1003
【题目大意】
有N颗糖果和M个小孩，老师现在要把这N颗糖分给这M个小孩。每个小孩i对每颗糖j都有一个偏爱度Aij，如果他喜欢这颗糖，Aij = k，否则Aij = 1。小孩i觉得高兴当且仅当ΣCij×Aij >= Bi，j=1,2,…,N，若他分得了糖j，Cij = 1，否则Cij = 0。问能否合理分配这N颗糖，使得每个小孩都觉得高兴。
【建模方法】
（最大费用最大流）
本题有一个突破点就是：他喜欢这颗糖，Aij = k，否则Aij = 1，关键在于如果他不喜欢这个糖分给他一样可以获得1点的欢乐值。也就是说如果之前分配了的糖给了小孩一定的欢乐值，不够bi，可以直接用随意的糖去填满。
首先我们要求欢喜值>=bi，是否可以认为当我获得欢喜值为bi后，多余欢喜值对这个结果的满足是没有贡献的。也就是说，你可以用一个容量来控制分配糖对小孩欢喜值的控制，让获得欢喜值最多为bi。如果不够，最后用一些1的糖来填满。
而这个容量就是bi/c，获取贡献为k，bi%c（>1）的也是可以用一个能让这个小孩欢喜的糖来贡献，但是其费用只为bi%c。
对于小孩来说，最大费用最大流后，糖分配的贡献值为最大费用，剩余糖就是（n-最大流），然后用这些糖去填不满的，只要满足总和大于Σbj。就可以分配了。
具体建模方案1：
(s,i,1,0);
(i,j,1,0);
(j,t,bj/k,k);
If(bj%k>1)
(j,t,1,bj%k)
Ans = 费用 + N – 最大流 >= Σbj 则满足要求
具体建模方案2：
(s,I,1,0)
(I,j,1,0)
(j,t,bj/k,k-1);
If(bj%k>1)
(j,t,1,bj%k-1);
Ans = 费用+N >= Σbj 则满足要求
当k = 2时候，可以不用费用流，最大流即可。
一种最直观的想法就是每颗糖i作为一个点并连边(s, i, ?)，每个小孩j作为一个点并连边(j, t, Bj)。若小孩j喜欢糖果i则连边(i, j, 2)，否则连边(i, j, 1)，然后求一次最大流看是否等于ΣBj。但是问题也很明显，我们还没有给与源点关联的边确定容量。实际上我们无法确定它们的容量，因为最大流无法实现这样一种控制：一个点有若干条出边，容量不尽相同，现在要求经过该点的流可以任选一条出边流走，且一旦选定之后就只能从这条边流而不能再进入其他的出边。因此我们无法确定与源关联的边的容量，因为经过每颗糖i的流无法在出边容量有1又有2的情况下作出正确的选择。
那么是否就没有办法了呢？虽然流无法在容量有1又有2的情况下作出正确的选择，但却可以在容量有1又有0的情况下最自然地作出正确的选择，流过去就表示选择了那条出边，且因为容量为1，不会再有流进入其他的出边。那么此题的构图方法也就出来了：每颗糖i作为一个点并连边(s, i, 1)，每个小孩j作为一个点并连边(j, t, floor(Bj/2))，若小孩j喜欢糖果i则连边(i, j, 1)，否则连边(i, j, 0)或者干脆不连边，效果一样。设最大流为ans，若ans+N >= ΣBj则可以满足要求。为什么？因为每颗糖迟早都要分给某个小孩，它一定会为总权值贡献1，只不过如果它分给了喜欢它的小孩就再额外贡献1。现在我只考虑这额外的1单位贡献究竟能送出去多少，最后加上基值N并与ΣBj比较即可。
1004
这道题求两个字符串编辑距离的部分用动态规划就可以了，如果不加任何优化，总的复杂度是1500*1000*10*10，时间给了1s，如果写的效率比较高，有可能可以水过。
标程的用到了一个叫做BK-Tree的数据结构优化一下，其实原理很简单，可以参考wiki http://en.wikipedia.org/wiki/BK-tree和matrix67的blog http://www.matrix67.com/blog/archives/333
1005
题目描述：
2000个点的有向图，保证任意两点间仅有一条有向边。
解题报告：
增量算法，充分利用“任意两点间仅有一条有向边”的性质。
假设前面已经加入了N个点，现在来了第N+1个点。
那么一定能将N个点分成left和right两部分，使得N+1号点到left有边，right到N+1号点右边（因为任意两点间都有边），那么，如果left的任意一个点l到right任意一个点r有边的话，那么就有答案N+1->l->r->N+1这样一个长度为3的环。
那么每次加入N+1号点后，用O(N)的复杂度求出左边的数量leftnum，右边的数量rightnum，left的出度和leftout，left的入度和leftin。
如果left没有一条到right的边，则一定满足：
leftin = leftout + leftnum * rightnum（left和right任意两点右边，如果没有左到右的，那么leftnum*rightnum条边都是右到左的）
那么，如果leftin != leftout + leftnum * rightnum，则暴力枚举左点，右点即可得到答案。
总体复杂度O(n^2)
附加一份其他人的解题报告
lengxiang解题报告：
我稍微的看了下出题人的解题报告，没咋看懂。稍微有所启发。写了一个不一样的代码，数据同样通过。
归结为1个条件，任何两人都有边，要么出要么入。
对于有向三元环，我们知道找到：A->B->C->A ，B->C->A->B ，C->A->B->C 是一样的，这给0(n^2)的算法提供了基础。
对于每次枚举i，我们在(0~i-1)的范围看下有多少个i指向的点(剩下的就是指向i的点)，同时算下i指向的点的出度和。就可以知道这些 i指向的点 指向 指向i的点（剩下的点）的数目，如果
num * (num - 1) / 2 < sumout 那么就是被指向的点有指出去了，这样就形成了3元环。
否则，剩下的就是更新下出度即可，继续执行下一个节点。
1006
这个题就是比较裸的区间更新，单点查询的线段树。一开始需要把要查询的点和花开的时间和花谢的时间一起离散化了，这样查询的时候就方便多了。
1007
本题题意很简单，给出n个人每次4人进行比赛其他人等待，胜者继续，负者排到最后，连续或得m次胜利的人成为最终的赢家，求第k个人最终获得胜利的概率是多少？
对于这题，我们首先确立一个这样的模型： x1先赢了i局，正在于x2,x3,x4赌斗，后面依次有x5,x6,……,xn等待。用P[i][j]表示x1先赢了i局的情况下，当前的xj获胜的概率。
不难得到以下的一些式子：
i < m
P[i][j] = P[i + 1][j] * 1/4 + P[1][n - 2] * 3/4 j = 1
P[i + 1][n - 2] * 1/4 + P[1][1] * 1/4 + P[1][n - 1] * 2/4 j = 2
P[i + 1][n - 1] * 1/4 + P[1][1] * 1/4 + P[1][n - 1] * 1/4 + P[1][n] * 1/4 j = 3
P[i + 1][n] * 1/4 + P[1][1] * 1/4 + P[1][n] * 2/4 j = 4
P[i + 1][j - 3] * 1/4 + P[1][j - 3] * 3/4 j>=4
i = m
P[i][j] = 1 j = 1
0 j != 1
于是我们得到了一个未知数为n*m个的方程组。用高斯消元法解之即可。
值得注意的是，以上思想并不难想到，但是普通的高斯消元法会由于舍入误差使得结果出现很大的偏差，这里我们采用的是分数形式的高斯消元的解法。
1008
首先利用旋转卡壳计算出每个点的凸包，由于密度公式非常特殊，则利用公式微积分即可算得每个点落到上面的概率。具体详见代码
1009
本题主要考察DP状态转移以及数据结构的使用。相邻块不能相同的最长周长的正方形，直接用O(1)转移的二维dp可以实现，g[i][j]表示右下角选为（i，j）的周长最长正方形，根据图像特性，g[i][j] = min( g[i-1][j] , g[i][j-1] ) or g[i][j] = min( g[i-1][j] , g[i][j-1] ) + 1，是否需要加1取决于对于块的颜色与map(i,j)上的颜色是否相同。
对于周长最长的同色矩形，首先O(n)枚举矩形的下底，然后从左至右O(m)依次枚举相应左右边界的最大值，枚举工作使用队列提速，询问过程涉及到区间更新区间查询的功能，使用线段树优化查询效率，复杂度O(n * m * lg(n)); 从左至右O(m)枚举时，也可以使用栈来保存每一列连续颜色的高度，同时可以求周长的最大值，复杂度(n * m)。
1010
本题是一道简单的模拟题，关键点是看懂题目绕口的定义，然后按照题目所给的公式求解即可。实现过程可以使用map来判断检索出的url是否为相关文件，使用istringstream处理字符串操作。具体如何实现都行，总之本题考察读题和基本字符串处理。
1011
搜索+剪枝
如果遇到已经100%的情况就直接break
一开始可以不去考虑不会补充新的棋子的情况 如果有100%的情况 那也可以直接break了。