ACM新生赛总结，加油！
A
326. CC玩游戏
只需判断$T+\sum_{i=1}^nA[i]\le K$是否成立即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <iostream>
using namespace std;
int main(){
int n,t,k;
cin>>n>>t>>k;
int sum=0;
for(int i=1;i<=n;i++){
int x;
cin>>x;
sum+=x;
}
if(t+sum<=k)cout<<"CCHandsome!\n";
else cout<<"PoorCC!";
return 0;
}
|
B
327. CC的木棍
推出答案的函数表达式，容易看出单调性。
二分求函数零点。
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
| #include <iostream>
#include <cmath>
using namespace std;
double x,y,c;
const double eps=1e-9;
double f(double m){
double tx=(x*x-m*m),ty=(y*y-m*m);
double ans=tx*ty-c*c*(tx+ty+2*sqrt(tx*ty));
return ans;
}
int main(){
cin>>x>>y>>c;
double l=0,r=min(x,y),mid;
int flag=(f(l)>0)?1:0;
while(1){
mid=(l+r)/2.0;
double temp=f(mid);
if(fabs(l-r)<eps)break;
if(fabs(temp)<eps)break;
else if(temp>0){
if(flag)l=mid;
else r=mid;
}else if(temp<0){
if(flag)r=mid;
else l=mid;
}
}
printf("%.8lf\n",mid);
return 0;
}
|
C
328. CC的秘密
先预处理出[1000,9999]范围内所有的素数。
然后写大暴力，把A在12步变动以内所有的数处理一遍，看是否有B。
一开始我也是不确定多少步，通过写暴力数据测试，可以得知。
范围内任意一个素数都可以在10步以内修改得到任意另一个素数。
因此这题的Impossible是不可能出现的情况！
BFS完全没想到啊
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
| #include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
int check[10005],can[15][10005];
int main(){
for(int i=1000;i<=9999;i++){
int f=1;
for(int j=2;j<=int(sqrt(i))+1;j++){
if(i%j==0){
f=0;
break;
}
}
if(f)check[i]=1;
}
int t;
cin>>t;
while(t--){
int a,b;
cin>>a>>b;
if(a==b){
cout<<"0\n";
continue;
}
memset(can,0,sizeof(can));
can[0][a]=1;
int times=0;
for(int i=1;i<=12;i++){
for(int j=1000;j<=9999;j++){
if(can[i-1][j]){
int a1=j/1000,a2=(j/100)%10,a3=(j%100)/10,a4=(j%10);
for(int k=1;k<=9;k++){
if(k==a1)continue;
int temp=k*1000+a2*100+a3*10+a4;
if(check[temp]){
can[i][temp]=1;
}
}
for(int k=0;k<=9;k++){
if(k==a2)continue;
int temp=a1*1000+k*100+a3*10+a4;
if(check[temp]){
can[i][temp]=1;
}
}
for(int k=0;k<=9;k++){
if(k==a3)continue;
int temp=a1*1000+a2*100+k*10+a4;
if(check[temp]){
can[i][temp]=1;
}
}
for(int k=0;k<=9;k++){
if(k==a4)continue;
int temp=a1*1000+a2*100+a3*10+k;
if(check[temp]){
can[i][temp]=1;
}
}
}
if(can[i][b]){
times=i;
break;
}
}
if(times)break;
}
if(times)cout<<times<<endl;
else cout<<"Impossible"<<endl;
}
return 0;
}
|
附上当时考场上写的数据生成程序。
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
| #include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int check[10005];
int main(){
freopen("input.txt","w",stdout);
cout<<"100\n";
for(int i=1000;i<=9999;i++){
int flag=1;
for(int j=2;j<int(sqrt(i))+1;j++){
if(i%j==0){
flag=0;
break;
}
}
if(flag){
check[i]=1;
}
}
int count=0;
for(int i=1000;i<=9999;i++){
for(int j=1000;j<=9999;j++){
if(check[i]&&check[j]){
printf("%d %d\n",i,j);
count++;
}
}
}
cout<<count<<endl;
return 0;
}
|
D
329. CC的画板
E
330. CC锤小兵
当时没想到前缀和+后缀和的做法。
用了一种类似数位dp的方法。
f[i][j][0]表示前i-1个数第j位是否有0
f[i][j][1]表示前i-1个数第j位是否有1
g[i][j]类似表示第i个数后的数。
感觉和前缀后缀类似，但是写法要麻烦一点。
这样可以处理位与和位或。
由于异或的逆元是本身。
故可以先把所有数异或一下，再异或a[i]就可以得到除a[i]外所有数异或的结果。
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
| #include <iostream>
#include <cstdio>
using namespace std;
const int N=100005;
int a[N],p[N],Xor,f[N][12][2],g[N][12][2];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
Xor=a[1];
for(int i=2;i<=n;i++){
Xor=Xor^a[i];
}
for(int i=1;i<=m;i++){
cin>>p[i];
}
for(int i=2;i<=n;i++){
for(int j=0;j<=10;j++){
f[i][j][0]=f[i][j][0]||f[i-1][j][0]||(((a[i-1]>>j)&1)==0);
f[i][j][1]=f[i][j][1]||f[i-1][j][1]||(((a[i-1]>>j)&1)==1);
}
}
for(int i=n-1;i>=1;i--){
for(int j=0;j<=10;j++){
g[i][j][0]=g[i][j][0]||g[i+1][j][0]||(((a[i+1]>>j)&1)==0);
g[i][j][1]=g[i][j][1]||g[i+1][j][1]||(((a[i+1]>>j)&1)==1);
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=10;j++){
f[i][j][0]=f[i][j][0]||g[i][j][0];
f[i][j][1]=f[i][j][1]||g[i][j][1];
}
}
int w=0;
for(int i=1;i<=m;i++){
for(int j=0;j<=10;j++){
if(f[p[i]][j][0]==0){
w+=(1<<j);
}
if(f[p[i]][j][1]==1){
w+=(1<<j);
}
}
w+=Xor^a[p[i]];
}
cout<<w<<endl;
return 0;
}
|
F
331. CC看星星
一个简单又重要的结论：最大的斜率一定在两个x坐标相邻的点连接产生
画图易证。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
using namespace std;
const int N=100005;
struct point{
int x,y;
}a[N];
bool cmp(point x,point y){
return x.x<y.x;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
}
sort(a+1,a+1+n,cmp);
double maxk=-1e9;
for(int i=1;i<n;i++){
double temp=double(a[i].y-a[i+1].y)/(a[i].x-a[i+1].x);
if(temp>maxk)maxk=temp;
}
printf("%.14lf\n",maxk);
return 0;
}
|
G
332. CC的单向路
构造题（(⊙o⊙)…）
边只能从到达点数多的点连向到达点数少的点。
做法参考题解：
先按A[i]排序，从小开始，若某个点到达的点数比A值小于它的点数更大，则无解。
否则连A[i]条单向边指向前A[i]个点。
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
| #include <bits/stdc++.h>
using namespace std;
struct node{
int index,reach;
node(int a,int b):index(a),reach(b){}
};
struct edge{
int u,v;
edge(int u,int v):u(u),v(v){}
};
bool cmp(node x,node y){
return x.reach<y.reach;
}
vector<node> G;
vector<edge> E;
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
G.push_back(node(i,x));
}
sort(G.begin(),G.end(),cmp);
int f=1,m=0;
for(int i=0;i<n;i++){
int order=i;
while(order>0&&G[order].reach==G[order-1].reach)order--;
if(order<G[i].reach){
f=0;
break;
}
for(int j=0;j<G[i].reach;j++){
E.push_back(edge(G[i].index,G[j].index));
m++;
}
}
if(f==0)puts("-1");
else{
printf("%d\n",m);
for(auto i:E){
printf("%d %d\n",i.u,i.v);
}
}
return 0;
}
|
H
333. CC的速度
简单的dp。
显然CC的疲劳值先增后减，并且一定会减到0。
由于最后的疲劳值一定为0，从后往前分析。
0这个状态一定从之前一个0的状态转移而来。
故枚举所有可转移的状态，取最优解。
利用前缀和计算区间和。
f[i]表示在第i分钟结束后，CC的疲劳值一定是0的情况下，最远能冲多远。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=10005;
const int M=505;
int d[N],f[N],sum[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>d[i];
sum[i]=sum[i-1]+d[i];
}
for(int i=1;i<=n;i++){
f[i]=max(f[i],f[i-1]);
for(int j=0;j<=m;j++){
if(i-(j<<1)>=0)f[i]=max(f[i],f[i-(j<<1)]+sum[i-j]-sum[i-(j<<1)]);
}
}
cout<<f[n]<<endl;
return 0;
}
|
I
334. CC好厉害
利用的数学技巧。
主要是对数的两个性质：
$$
\log_ab^n=n\log_ab\\
\log_abc=\log_ab+log_ac
$$
由于任意一个数都可以用科学计数法表示。
如
$10234432=1.0234432 \times 10^7$，则
$\log_{10}(10234432)=\log_{10}(1.0234432)+7$
那么
$\log_{10}(1.0234432)$就是
$\log_{10}(10234432)$的小数部分。
因此，若要计算
$X^n$的前
$k$位，可以先取对数，把指数降成乘积。
$\log_{10}X^n=n\times \log_{10}X$，再取出这个数的小数部分
$Y$（整数部分不影响前
$k$位的值）
计算
$10^Y$，就可以得到用小数表示的结果。
显然
$10^{Y+k-1}$的整数部分就是
$X^n$的前
$k$位。
下面用了fmod(X,1)来求X的小数部分。
1
2
3
4
5
6
7
8
9
10
11
12
| #include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int M=3;
int main(){
long long n,k;
cin>>n>>k;
cout<<int(pow(10,M-1+fmod(k*log10(n),1)))<<endl;
return 0;
}
|
J
335. CC的金手指
容易推出ab可以互换位置，而c无法变化。
故先判断c的数量，再以c为分界点判断每个区间内的ab数量的奇偶性。
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
| #include <bits/stdc++.h>
using namespace std;
char s1[10005],s2[10005];
int main(){
int n;
cin>>n>>s1>>s2;
int c1=0,c2=0;
for(int i=0;i<n;i++){
if(s1[i]=='c')c1++;
if(s2[i]=='c')c2++;
}
if(c1!=c2)puts("No");
else{
int f=1;
s1[n]=s2[n]='c';
int sc1=0,sc2=0;
while(sc1<=n&&sc2<=n){
int a1=0,a2=0,b1=0,b2=0;
while(s1[sc1]!='c'){
if(s1[sc1]=='a')a1++;
else if(s1[sc1]=='b')b1++;
sc1++;
}
while(s2[sc2]!='c'){
if(s2[sc2]=='a')a2++;
else if(s2[sc2]=='b')b2++;
sc2++;
}
if((a1&1)!=(a2&1)||(b1&1)!=(b2&1)){
f=0;
break;
}
sc1++;
sc2++;
}
if(f)puts("Yes");
else puts("No");
}
return 0;
}
|
参考资料
题解
优秀代码
