Codeforces Round #654 (Div. 2)contest 1371

目录

A Magical SticksB Magical CalendarC A Cookie for YouD Grid-00100E Asterism (Easy/Hard Version)F

ABCDEF√√√√√

（ √：做出； ●：尝试未做出； ○：已补题 ）

---

题目地址：https://codeforces.com/contest/1371

A Magical Sticks

题意：

思路：

代码：

#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,a,b) for(int i=(a);i<=(int)(b);i++) #define REP_(i,a,b) for(int i=(a);i>=(b);i--) #define pb push_back using namespace std; typedef long long LL; typedef vector<int> VI; int read() { int x=0,flag=1; char c=getchar(); while((c>'9' || c<'0') && c!='-') c=getchar(); if(c=='-') flag=0,c=getchar(); while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return flag?x:-x; } int main() { //freopen("input.txt","r",stdin); int T=read(); while(T--) printf("%d\n",(read()+1)/2); return 0; }

B Magical Calendar

题意：

思路：

代码：

#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,a,b) for(int i=(a);i<=(int)(b);i++) #define REP_(i,a,b) for(int i=(a);i>=(b);i--) #define pb push_back using namespace std; typedef long long LL; typedef vector<int> VI; int read() { int x=0,flag=1; char c=getchar(); while((c>'9' || c<'0') && c!='-') c=getchar(); if(c=='-') flag=0,c=getchar(); while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return flag?x:-x; } int main() { //freopen("input.txt","r",stdin); int T=read(); while(T--) { LL n=read(),r=read(); if(n>r) printf("%lld\n",r*(r+1)/2); else printf("%lld\n",n*(n-1)/2+1); } return 0; }

C A Cookie for You

题意：有两种饼干各有 v 和 c 块，有两种客人各有 n 和 m 人。n 人的客人这样吃饼干：如果 v>c，就吃 v 饼干，否则吃 c 饼干；m 人的客人这样吃饼干：如果 v>c，就吃 c 饼干，否则吃 v 饼干。问能否安排一个吃的序列，使得所有客人都能吃到饼干？

思路：可以发现一种客人每次会吃多的，另一种每次会吃少的。那么只存在以下两种不能安排的情况：

客人总数大于饼干总数；吃少的饼干的客人数（m）大于 min(v, c)；

如果不存在以上两种情况，那么都可以先安排吃少的客人吃完之后，再安排吃多的客人吃。

代码：

#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,a,b) for(int i=(a);i<=(int)(b);i++) #define REP_(i,a,b) for(int i=(a);i>=(b);i--) #define pb push_back using namespace std; typedef long long LL; typedef vector<int> VI; int read() { int x=0,flag=1; char c=getchar(); while((c>'9' || c<'0') && c!='-') c=getchar(); if(c=='-') flag=0,c=getchar(); while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return flag?x:-x; } int main() { //freopen("input.txt","r",stdin); int T=read(); while(T--) { LL v,c,n,m; cin>>v>>c>>n>>m; if(n+m>v+c) puts("NO"); else if(m>min(v,c)) puts("NO"); else puts("YES"); } return 0; }

D Grid-00100

题意：给出 n 和 k，要在 n×n 的矩阵中填上 k 个 1（其它都是 0），使得 $(max(R)-min(R){)}^2+(max(C)-min(C){)}^2$ 最小，其中 R 表示每一行的和的数组，C表示每一列的和的数组，最值就是要求这个数组中的最值。输出这个最小值和最终矩阵。

思路：可以发现这么填是最优的：

代码：

#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,a,b) for(int i=(a);i<=(int)(b);i++) #define REP_(i,a,b) for(int i=(a);i>=(b);i--) #define pb push_back using namespace std; typedef long long LL; typedef vector<int> VI; int read() { int x=0,flag=1; char c=getchar(); while((c>'9' || c<'0') && c!='-') c=getchar(); if(c=='-') flag=0,c=getchar(); while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return flag?x:-x; } const int maxn=305; int a[maxn][maxn],n,k; int main() { //freopen("input.txt","r",stdin); int T=read(); while(T--) { int n=read(),k=read(); REP(i,1,n) REP(j,1,n) a[i][j]=0; for(int s=1;s<=n;s++) { if(!k) break; for(int i=1,j=s;i<=n;i++,j=j%n+1) { if(!k) break; k--; a[i][j]=1; } } int maxR=0,maxC=0,minR=n,minC=n; REP(i,1,n) { int x=0; REP(j,1,n) x+=a[i][j]; maxR=max(maxR,x); minR=min(minR,x); } REP(j,1,n) { int x=0; REP(i,1,n) x+=a[i][j]; maxC=max(maxC,x); minC=min(minC,x); } printf("%d\n",(maxR-minR)*(maxR-minR)+(maxC-minC)*(maxC-minC)); REP(i,1,n) { REP(j,1,n) printf("%d",a[i][j]); puts(""); } } return 0; }

E Asterism (Easy/Hard Version)

题意：有 n 个敌人，每个敌人拥有的糖果数为 $a_i$ ，小女孩一开始拥有 x 颗糖果，然后去和敌人对战。和某个敌人对战时，如果小女孩手中的糖果数不小于敌人的糖果数，那么小女孩获胜并且手中糖果数+1 。小女孩想要赢得所有敌人，并且有一个函数 $f(x)$ 表示当小女孩初始拥有糖果数为 x 时，战胜所有敌人的敌人的排列数。现在给出一个质数 p，给出数组 a，输出所有的 x，使得 $f(x)$ 不能被 p 整除。（$2\le p\le n\le 1e5,1\le a_i\le 1e9$）

思路：现在来看对于指定的 x，数组 a 可以怎么重排列：

如果 $a_i\le x$，那么说明这个 $a_i$ 可以放到任意的位置；如果 $a_i\ge x+n-1$ ，那么说明 $a_i$ 放哪里都没用，也就是赢不了；否则，$a_i$ 只能放到后 $n-(a_i-x)$ 个位置。

可以看出 x 满足一定的单调性，x 越大 f(x) 越大，并且当 $x\ge max(a_i)$ 时，$f(x)=n!$ 一定可以被 p 整除；当 $x\le max(a_i)-n+1$ 时，$f(x)=0$ 可不满足；所以我们只用考虑中间部分。可以首先用二分搜索找出满足考虑部分的 x 的最小值 ，然后就可以构造出一个数组 s 记录每个 $a_i$ 可以放的位置数，然后对 s 排序，然后对 s 进行 $s_i=s_i-i$ 的操作（这里 i 从 0 开始），此时 s 数组记录的就是每个位置放置时真正可以放的数目（一定有 $s_i\ge 1$ ）。我们对 x 做增加操作，实际上 s 的每一位也会 +1，直到 $s_i=n-i$ 为止就不再增加了，那么我们的目标就是找到，对于 x 增加的数目 r（$r\ge 0$），r 取哪些值的时候，s 中没有一个数可以被 p 整除。

到了这里我比赛时就开始瞎写了，而且居然过了，虽然跑得很慢……大概是这样做的吧：首先对于 n-i 可以被 p 整除的 i，那么可以更新一个最小值 minx=min(minx, n-i-s[i])，因为 n-i 是那个位置的最大值，而再增加不管多少，它已经可以被 p 整除了。然后对于每一位找到小于 minx 的所有可以被 p 整除的值，把相应的 r 排除在外。说实话我真不知道这么做复杂度到底是多少……

代码：

#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,a,b) for(int i=(a);i<=(int)(b);i++) #define REP_(i,a,b) for(int i=(a);i>=(b);i--) #define pb push_back using namespace std; typedef long long LL; typedef vector<int> VI; int read() { int x=0,flag=1; char c=getchar(); while((c>'9' || c<'0') && c!='-') c=getchar(); if(c=='-') flag=0,c=getchar(); while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return flag?x:-x; } const int maxn=1e5+5; int n,p,a[maxn],t[maxn],v[maxn]; bool can(int x) { VI s; REP(i,1,n) if(a[i]<=x) s.pb(n); else if(a[i]>x+n-1) return false; else s.pb(n-(a[i]-x)); sort(s.begin(),s.end()); REP(i,1,n) if(s[i-1]<i) return false; return true; } int main() { //freopen("input.txt","r",stdin); n=read(),p=read(); REP(i,1,n) a[i]=read(); int l=0,r=1e9,mid; while(l<r-1) { mid=(l+r)>>1; if(can(mid)) r=mid; else l=mid; } //cout<<r<<endl; VI s; REP(i,1,n) if(a[i]<=r) s.pb(n); else s.pb(n-(a[i]-r)); sort(s.begin(),s.end()); int maxadd=0,minx=n; for(int i=0;i<n;i++) { int q=s[i]-i,qq=n-i; maxadd=max(maxadd,qq-q); if(q==qq && q%p==0) return puts("0"),0; if(qq%p==0) { for(int j=qq-q;j<minx;j++) v[j]=1; minx=min(minx,qq-q); } int j=(q/p+1)*p; if(q%p==0) j=q; j-=q; for(j;j<minx && j<=qq-q;j+=p) v[j]=1; } int tot=0; VI ans; for(int i=0;i<=maxadd;i++) if(!v[i]) tot++,ans.pb(r+i); printf("%d\n",tot); for(int i:ans) printf("%d ",i); return 0; }

F

题意：

思路：

代码：