注意
此处比赛分别为Round462, 463, 464, 466，均为Div2
Round462
A
题面
Tommy有n个灯笼，BanBan有m个灯笼，Tommy拿走一个灯笼，分别从Tommy的和BanBan的选择一个灯笼，求最大乘积，假设双方都使用最优决策。
题解
枚举Tommy拿走的灯笼，及Tommy拿走该灯笼后所选的两个灯笼，求max即可
代码
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<cstdio> #include<iostream> #include<queue> #include<algorithm> #include<climits> const int MAXN=50+5; std::priority_queue<int>pq,pq2,pq3,pq4; int n,m,x,a[MAXN],b[MAXN];long long ans=LLONG_MAX,tmp; int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) scanf("%d",&b[i]); for(int i=1;i<=n;i++) { tmp=LLONG_MIN; for(int j=1;j<=n;j++) { if(i==j) continue; for(int k=1;k<=m;k++) tmp=std::max(tmp,(long long)a[j]*b[k]); } ans=std::min(ans,tmp); } return 0; }
|
B
题面
题面很玄乎。。其实就是求一个数字的形状中有k个圈的数。。
题解
首先排除$k>36$的数，因为不超过$10^18$即使圈数最大，也就36个圈
那么时间复杂度也就很小了。
然后输出8（两个圈）直至$k<2$，然后输出6（一个圈）不住
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| #include<cstdio> int loop[10]={1,0,0,0,1,0,1,0,2,1},k,r; int main() { scanf("%d",&k); if(k>18*2) printf("-1\n"); else { r=k/2; k-=r*2; for(int i=1;i<=k;i++) printf("6"); for(int i=1;i<=r;i++) printf("8"); } return 0; }
|
Round463
A
题面
给出一个字符串S，输出一个新字符串Str，使得S是Str的子串
题解
输出原字符串，再输出字符串的反转串即可
这样，从左往右和从右往左都是先正着再反着读
代码
1 2 3 4 5 6 7 8 9 10 11 12 13
| #include<cstdio> #include<cstring> const int MAXN=1000+5; char c[MAXN];int l; int main() { scanf("%s",c); l=strlen(c); printf("%s",c); for(int i=l-1;i>=0;i--) printf("%c",c[i]); return 0; }
|
B
题面
给定一个函数，输出x在$[l,r]$间该函数参数为x，值=k的参数数量
题解
显然函数结果$<9$，且时间复杂度较低，暴力求出各参数的值，做个二维前缀和即可
代码
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
| #include<cstdio> #include<algorithm> const int MAXN=1000000+5; const int MAXC=9+5; int pfx[MAXC][MAXN],pfxr[MAXC][MAXN]; int g(int x) { if(x<10) return x; int product=1; while(x) { if(x%10) product*=x%10; x/=10; } return g(product); } int main() { for(int i=1;i<=1000000;i++) { pfxr[g(i)][i]++; } for(int i=1;i<=9;i++) for(int j=1;j<=1000000;j++) pfx[i][j]=pfx[i][j-1]+pfxr[i][j]; int q,l,r,k; scanf("%d",&q); for(int i=1;i<=q;i++) { scanf("%d %d %d",&l,&r,&k); printf("%d\n",pfx[k][r]-pfx[k][l-1]); } return 0; }
|
Round464
A
题面
给出各个人的相爱关系，寻找是否有A爱B，B爱C，C爱A
题解
对于每个i
关系坐标三层嵌套，看是否等于i
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| #include<cstdio> const int MAXN=10000+5; int n,list[MAXN]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&list[i]); for(int i=1;i<=n;i++) if(list[list[list[i]]]==i) { printf("YES"); return 0; } printf("NO"); return 0; }
|
B
题面
给出n种箱子，共k个物体，每个箱子必须装满，但是不一定k个物体都要装进去，求最大可装进去的物体数及箱子种类
题解
简单判断
代码
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<cstdio> #include<iostream> const int MAXN=100000+5; int k;long long max,maxcnt,maxid=1,box,n,tmp,r; int main() { std::cin>>n>>k; for(int i=1;i<=k;i++) { scanf("%lld",&r); box=n/r; tmp=box*r; if(tmp>max) { max=tmp; maxid=i; maxcnt=box; } } std::cout<<maxid<<' '<<maxcnt; return 0; }
|
