A - Magical Sticks

题意：给一个数n，现有1、2、……、n这n个数，可以选择任意两个数求和，求最后最多能有几个数相等 我们可以想：1+n-1=n,2+n-2=n,……, 若n为奇数，则存在(n-1)/2+(n-1)/2+1=n，此时有(n+1)/2个数相等 若n为偶数，则会有一个数凑不成n，所以，此时有(n-2)/2+1=n/2个数相等 总结起来答案是n/2+(n%2)

t=input() t=int(t) while t>0: t-=1 n=input() n=int(n) print(n//2+n%2)

B - Magical Calendar

题意：给矩形的宽度限制r，要你涂满矩形中的n个格子，形成一个图形，各个矩形连通块之间需要有公共边，求能形成的图形种类。 注：两个图形不同的条件是：不能通过平移涂满的连通块得到另一种图形 可以发现，n>d(d为现在矩形的宽度)的时候，他肯定能国行并且能够出现共享边，这时候，我们选择图形再头一行的起点，则有d种, 当n==d的时候，会出现两个矩形没有共享边，不符合题意（见样例打x处），这时候，涂满的矩形只能在一行中，因此，只有1种图形。 在符合n>d的范围内，我们可以用等差数列前n项和求解。当n=d的时候，只需多加个1就行了。 可能爆ll，所以，我选择python

t=input() t=int(t) while t>0: t-=1 n,r=input().split() n=int(n) r=int(r) lim=min(r,n-1) ans=((1+lim)*(lim))//2 if(r>=n):ans+=1 print(ans)

C - A Cookie for You

考虑极限情况发现：一类型见到能吃就吃，二类型永远只吃少的那一份，因此，才一个结论：一类人只需要我们只要能提供n的饼干就行，二类人需要min(a,b)>m才行，因此，Yes条件为:a+b>=n+m&&min(a,b)>=m

#include <iostream> #include <map> #include <ctime> #include <vector> #include <climits> #include <algorithm> #include <random> #include <cstring> #include <cstdio> #include <map> #include <set> #include <bitset> #include <queue> #define inf 0x3f3f3f3f #define IOS ios_base::sync_with_stdio(0); cin.tie(0); #define rep(i, a, n) for(register int i = a; i <= n; ++ i) #define per(i, a, n) for(register int i = n; i >= a; -- i) #define ONLINE_JUDGE using namespace std; typedef long long ll; const int mod=1e9+7; template<typename T>void write(T x) { if(x<0) { putchar('-'); x=-x; } if(x>9) { write(x/10); } putchar(x%10+'0'); } template<typename T> void read(T &x) { x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();} while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f; } ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} ll lcm(ll a,ll b){return a/gcd(a,b)*b;}; ll ksm(ll a,ll n){//看是否要mod ll ans=1; while(n){ if(n&1) ans=((ans%mod)*(a%mod))%mod; a=((a%mod)*(a%mod))%mod; n>>=1; } return ans%mod; } //============================================================== ll t,a,b,n,m; bool check(){ if(a+b<n+m) return false; if(min(a,b)<m) return false; return true; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif //=========================================================== read(t); while(t--){ read(a),read(b),read(n),read(m); if(check()){ puts("Yes"); } else{ puts("No"); } } //=========================================================== return 0; }

D - Grid-00100

要让f(a)最小，就要让最大和最小的差值小，因此，我们每次放1需要均匀地在每一行每一列，考虑对角线放就行了。

#include <iostream> #include <map> #include <ctime> #include <vector> #include <climits> #include <algorithm> #include <random> #include <cstring> #include <cstdio> #include <map> #include <set> #include <bitset> #include <queue> #define inf 0x3f3f3f3f #define IOS ios_base::sync_with_stdio(0); cin.tie(0); #define rep(i, a, n) for(register int i = a; i <= n; ++ i) #define per(i, a, n) for(register int i = n; i >= a; -- i) #define ONLINE_JUDGE using namespace std; typedef long long ll; const int mod=1e9+7; template<typename T>void write(T x) { if(x<0) { putchar('-'); x=-x; } if(x>9) { write(x/10); } putchar(x%10+'0'); } template<typename T> void read(T &x) { x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();} while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f; } ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} ll lcm(ll a,ll b){return a/gcd(a,b)*b;}; ll ksm(ll a,ll n){//看是否要mod ll ans=1; while(n){ if(n&1) ans=((ans%mod)*(a%mod))%mod; a=((a%mod)*(a%mod))%mod; n>>=1; } return ans%mod; } //============================================================== #define int ll int t,n,k; int mp[305][305]; int c[305],r[305]; signed main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif //=========================================================== read(t); while(t--){ memset(mp,0,sizeof(mp)); memset(r,0,sizeof(r)),memset(c,0,sizeof(c)); read(n),read(k); int num=0; while(k){ rep(i,1,n){ int posy=i+num; if(posy>n) posy%=n; mp[i][posy]=1; k--; if(k==0) break; } num++; } int maxc=-inf,minc=inf,maxr=-inf,minr=inf; rep(i,1,n){ rep(j,1,n){ if(mp[i][j]){ c[i]++,r[j]++; } } } rep(i,1,n){ rep(j,1,n){ maxc=max(maxc,c[i]); minc=min(minc,c[i]); maxr=max(maxr,r[j]); minr=min(minr,r[j]); } } write((maxc-minc)*(maxc-minc)+(maxr-minr)*(maxr-minr)),putchar('\n'); rep(i,1,n){ rep(j,1,n){ write(mp[i][j]); } putchar('\n'); } } //=========================================================== return 0; }

E1-Asterism (Easy Version)

要求的是为good的数有哪些。good的条件为：符合题意的排列数%p不为0 先考虑特殊情况： 若x<min(a[i])，则f(x)一定为0 若x>=max(a[i]),则f(x)为n!，modp一定为0 要想能够通过整个数组，那么，至少需要的数值x至少满足：x+n-1>=max(a[i])，既x>=max(a[i])+1-n. 因为是全排列，所以a的原始顺序不重要，考虑先排序。 之后，因为数据范围只有2e3，考虑计算每个f(x)。 对于一个值a[i]，若a[i]<=x，则a[i]可以放在任意位置。若a[i]>x，则它能放的位置为后面的n-(x-a[i])个位置。 考虑有限制的先放，我们从大的放起。 若a[i]>x,则可放位置有left-(x-a[i])个（left为n-刚才已经安排了的各大的数的数量） 若a[i]<=x，则可放在left的位置 因为是分步，符合乘法原理，最后结果为相乘。 若最后结果%p为0，则该数not good，否则，good

#include <iostream> #include <map> #include <ctime> #include <vector> #include <climits> #include <algorithm> #include <random> #include <cstring> #include <cstdio> #include <map> #include <set> #include <bitset> #include <queue> #define inf 0x3f3f3f3f #define IOS ios_base::sync_with_stdio(0); cin.tie(0); #define rep(i, a, n) for(register int i = a; i <= n; ++ i) #define per(i, a, n) for(register int i = n; i >= a; -- i) #define ONLINE_JUDGE using namespace std; typedef long long ll; const int mod=1e9+7; template<typename T>void write(T x) { if(x<0) { putchar('-'); x=-x; } if(x>9) { write(x/10); } putchar(x%10+'0'); } template<typename T> void read(T &x) { x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();} while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f; } ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} ll lcm(ll a,ll b){return a/gcd(a,b)*b;}; ll ksm(ll a,ll n){//看是否要mod ll ans=1; while(n){ if(n&1) ans=((ans%mod)*(a%mod))%mod; a=((a%mod)*(a%mod))%mod; n>>=1; } return ans%mod; } //============================================================== const int maxn=2e3+10; int n,p,a[maxn]; vector<int> ans; bool check(int x){ int pos=n,ans=1; rep(i,1,n){ if(x<a[i]){ if(pos-a[i]+x<0) return false; ans=(ans*(pos-a[i]+x))%p; } else{ ans=(ans*pos)%p; } pos--; } if(ans)return true; return false; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif //=========================================================== read(n),read(p); rep(i,1,n) read(a[i]); sort(a+1,a+1+n,greater<int>()); int ma=a[1]; rep(i,ma+1-n,ma-1){ if(check(i)) ans.push_back(i); } write(ans.size());putchar('\n'); rep(i,0,int(ans.size()-1)){ if(i) putchar(' '); write(ans[i]); } putchar('\n'); //=========================================================== return 0; }