A Ginkgo Numbers
直接暴力查找(m,n)是否为(p,q)的因子
1<m^2+n^2<20000 所以直接来个142x142的循环就行
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<map> using namespace std; inline void RD(int &ret) { char c; do { c=getchar(); } while(c<'0'||c>'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); } } inline void OT(int a) { if(a>=10) { OT(a/10); } putchar(a%10+'0'); } int main() { int t,i,j,p,q,x,y,f; RD(t); while(t--) { scanf("%d%d",&p,&q); x=p*p+q*q; if(x<=1) { printf("Cn"); } else { f=0; for(i=-142; i<=142; ++i) { for(j=-142; j<=142; ++j) { y=i*i+j*j; if(y==0||y==1) { continue; } if((abs(i)==abs(p)&&abs(j)==abs(q))||(abs(i)==abs(q)&&abs(j)==abs(p))) { continue; } if((i*p+j*q)%y==0&&(i*q-j*p)%y==0) { f=1; break; } } if(f==1) { break; } } if(f==1) { printf("Cn"); } else { printf("Pn"); } } } return 0; }
B One-Dimensional Cellular Automaton
一道数论题，直接写TLE无疑，只能YY了一下。各种数组保存。。。写得都晕了，居然1A。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #define mem(a,b) memset(a,b,sizeof(a)) #define FOR(a,b,i) for(i=a;i<b;++i) #define For(a,b,i) for(i=a;i<=b;++i) using namespace std; inline void RD(int &ret) { char c; do { c=getchar(); } while(c<'0'||c>'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); } } inline void OT(int a) { if(a>=10) { OT(a/10); } putchar(a%10+'0'); } int s[51],f[51][51][51],q[51][51],tx[51]; int main() { int n,m,a,b,c,t,i,j,k,l,p,tt; while(1) { RD(n); RD(m); RD(a); RD(b); RD(c); RD(t); if(n==0&&m==0&&a==0&&b==0&&c==0&&t==0) { break; } For(1,n,i) { RD(s[i]); } if(t==0)//等于0时没有变化，直接输出 { FOR(1,n,i) { OT(s[i]); printf(" "); } OT(s[n]); printf("n"); } else { For(1,n,i)//三维数组保存 { f[0][i-1][i]=a; f[0][i][i]=b; f[0][i+1][i]=c; } p=0; while(t>1)//转化为2进制进行操作 { tx[++p]=t%2; t=t/2; } For(1,p/2,i) { tt=tx[i]; tx[i]=tx[p-i+1]; tx[p-i+1]=tt; } For(1,p,l) { For(1,n,i) { For(1,n,j) { f[l][i][j]=0; } } For(1,n,k) { For(1,n,i) { For(1,n,j) { f[l][i][j]=(f[l][i][j]+f[l-1][i][k]*f[l-1][k][j])%m; } } } if(tx[l]==1) { For(1,n,i) { For(1,n,j) { q[i][j]=f[l][i][j]; f[l][i][j]=0; } } For(1,n,k) { For(1,n,i) { For(1,n,j) { f[l][i][j]=(f[l][i][j]+q[i][k]*f[0][k][j])%m; } } } } } mem(q,0); For(1,n,k) { For(1,n,i) { For(1,n,j) { q[i][j]=(q[i][j]+s[k]*f[p][k][j])%m; } } } FOR(1,n,i) { OT(q[1][i]); printf(" "); } OT(q[1][n]); printf("n"); } } return 0; }
并查集维护+压缩路径水题。。。int直接能过
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<map> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; inline void RD(int &ret) { char c; do { c=getchar(); } while(c<'0'||c>'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); } } inline void OT(int a) { if(a>=10) { OT(a/10); } putchar(a%10+'0'); } int fa[100001],s[100001]; int n; void init()//初始化 { mem(s,0); int i; for(i=1;i<=n;++i) { fa[i]=i; } } int f(int x)//并查集 { if(fa[x]==x) { return x; } int xx=f(fa[x]); s[x]+=s[fa[x]]; fa[x]=xx; return xx; } int main() { int m,i,j,a,b,w,p,q; char c; while(1) { RD(n); RD(m); if(n==0&&m==0) { break; } init(); while(m--) { scanf("%c",&c); RD(a); RD(b); if(c=='!') { RD(w); p=f(a); q=f(b); fa[p]=q; s[p]=s[b]-s[a]+w; } else if(c=='?') { if(f(a)==f(b)) { printf("%dn",s[a]-s[b]); } else { printf("UNKNOWNn"); } } } } return 0; }
H Beautiful Spacing
寻找最短空隙组中的最长空隙，二分+判断
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<map> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; inline void RD(int &ret) { char c; do { c=getchar(); } while(c<'0'||c>'9'); ret=c-'0'; while((c=getchar())>='0'&&c<='9') { ret=ret*10+(c-'0'); } } inline void OT(int a) { if(a>=10) { OT(a/10); } putchar(a%10+'0'); } int w,n; int a[50001],s[50001],g[50001],h[50001]; bool f(int x) { int i,px=0,py=1,dx; mem(g,0); g[0]=1; h[0]=1; for(i=2;i<=n;++i) { while(px<py&&(s[i]+i-h[px]-s[h[px]-1])>w) { px++; } if(px<py) { if(h[px]!=i) { dx=(w-s[i]+s[h[px]-1]+i-h[px]-1)/(i-h[px]); if(dx<=x) { g[i]=1; h[py]=i+1; py++; } } } } for(i=n;i>=0;--i) { if(g[i]==1&&(s[n]-s[i]+n-i)<=w) { return true; } } return false; } int main() { int m,i,j,l,r; while(1) { RD(w); RD(n); if(w==0&&n==0) { break; } s[0]=0; for(i=1;i<=n;++i) { RD(a[i]); s[i]=s[i-1]+a[i]; } l=0; r=w; while(l+1<r) { m=(l+r)/2; if(f(m)==true) { r=m; } else { l=m; } } OT(r); printf("n"); } return 0; }
最后
以上就是典雅宝贝最近收集整理的关于130811个人赛练习BNU-Regionals 2012, Asia - Tokyo的全部内容，更多相关130811个人赛练习BNU-Regionals内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复