This way

文章目录

A. Magical Sticks：A题解：B. Magical Calendar：B题解：C. A Cookie for YouC题解：D. Grid-00100D题解：E1.Asterism (Easy Version)：E1题解：E2.Asterism (Hard Version)题解：F. Raging Thunder(待定)

A. Magical Sticks：

现在有n个木棒，第i个木棒的长度为i，你每次可以将两根木棒合并，从而得到一根长度为他们长度之和的木棒。最终希望长度相同的木棒最多，问这个答案是多少

A题解：

那么很明显，第一根木棒和最后一根合并，第二根和倒数第二根合并。。。以此类推于是答案就是(n+1)/2

#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int main() { int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); printf("%d\n",(n+1)/2); } return 0; }

B. Magical Calendar：

你可以将一个星期的长度定义为1~r，他现在要涂色连续的n天，如果超过了最后一天，那么就在下一行的第一天开始。他要使得所有涂色过的格子连在一起，问你最终本质不同的涂色方法有多少。

B题解：

那么我们可以知道最大只能取到min(n-1,r)， 然后长度为1时答案是1，长度为2时答案是2…以此类推 超出n-1的部分的答案总共是1，因为都是一条线段。

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=1e5+5; int main() { int t; scanf("%d",&t); while(t--){ ll n,r; scanf("%lld%lld",&n,&r); if(r<n) printf("%lld\n",(1+r)*r/2); else printf("%lld\n",(1+n-1)*(n-1)/2+1); } return 0; }

C. A Cookie for You

有a个香草饼，b个巧克力饼，现在有n个第一种客人，m个第二种客人按照你排好的次序来，每个客人来的时候都会拿一个饼， 如果来的客人是第一种，如果当前a>b，那么他会拿a，否则拿b 来的客人是第二种的话，如果当前a>b，那么他会拿b，否则拿a 如果这个客人没拿到饼，宴会失败。 问你最终宴会是否成功。

C题解：

首先如果a+b<n+m一定失败，然后如果m>min(a,b)的话，由于m每次都会拿比较少的那一个，所以其实m能够拿的数量是min(a,b).

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=1e5+5; int main() { int t; scanf("%d",&t); while(t--){ ll a,b,n,m; scanf("%lld%lld%lld%lld",&a,&b,&n,&m); if(m>min(a,b)||n+m>a+b) printf("NO\n"); else printf("YES\n"); } return 0; }

D. Grid-00100

现在有n*n的格子，每个格子要么是0，要么是1，现在告诉你有k个1，并且定义 要使得f最小，问你构造方法。

D题解：

那么我们要使得f最小，肯定是要尽量让每行的1数量相同，每列的1数量相同，那么我们一次一次斜着放1即可，这样如果k%n=0的话，答案是0，否则答案是2.就像这个样子：

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=3e2+5; bool mp[N][N]; int main() { int t; scanf("%d",&t); while(t--){ memset(mp,0,sizeof(mp)); int n,k; scanf("%d%d",&n,&k); if(k%n) printf("2\n"); else printf("0\n"); while(k){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++,k--){ if(!k)break; mp[j][(j+i)%n]=1; } if(!k)break; } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++) printf("%d",mp[i][j]); printf("\n"); } } return 0; }

E1.Asterism (Easy Version)：

定义f(x)： 你一开始有x颗糖，现在有n个敌人，每个敌人有ai颗糖，你要去按照一个排列去战胜这些敌人，当你的糖的数量>=ai的时候，你就可以战胜他，赢了之后你就可以得到一颗糖。f(x)表示可以赢的排序的数量。 找到一些x使得f(x)不是p的倍数。

E1题解：

当然hard的题解也能用，但是数据范围不同就应该有不同的想法。 首先看到范围就知道是$O(n^2)$的想法，那么我们首先可以选择枚举x，然后再从1到n枚举位置，用一个r维护我们当前右端第一个不能取到的位置，如果r-i是p的倍数，证明不行。

#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N]; vector<int>ans; int main() { int n,p; scanf("%d%d",&n,&p); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); int x=1; for(int i=1;i<=n;i++) x=max(a[i]-i+1,x); for(;x<=a[n];x++){ int r=1,f=0; for(int i=1;i<=n;i++){ while(r<=n&&x+i-1>=a[r]) r++; if((r-i)%p==0){ f=1; break; } } if(!f) ans.push_back(x); } printf("%d\n",ans.size()); for(int i:ans) printf("%d ",i); printf("\n"); return 0; }

E2.Asterism (Hard Version)题解：

它写个hard version，我以为很难啊，没想到原来是个水题？绝了 首先按照a从大到小排序，然后赢过第ai的最少需要的x是ai-i+1.那么从所有中取个最大值 然后我们可以知道，你每次能赢过的人的数量不能大于等于p，因为这样的话，当能取的区间慢慢缩小时，一定能取到p。 对于第i个数，如果你的值>=ai-i+p的话，就是违法的。那么只要在其中取个最小值，然后从左界到右界输出一下即可。

#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N]; int main() { int n,p; scanf("%d%d",&n,&p); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); int l=1,r=1e9; for(int i=1;i<=n;i++) l=max(l,a[i]-i+1); for(int i=p;i<=n;i++) r=min(r,a[i]-i+p); if(l<r){ printf("%d\n",r-l); for(int i=l;i<r;i++) printf("%d%c",i," \n"[i==r-1]); } else printf("0\n"); return 0; }

F. Raging Thunder(待定)