题意：两个人分气球，每个人至少有一个且两个人分到的气球个数不相等。 解法：求出sum，找到一个数x，且2*x!=sum ，则把这个气球分给一个人，其他的给另一个人
#include<bits/stdc++.h> using namespace std; #define maxn 100005 int a[maxn]; int main() { ios::sync_with_stdio(false); int n,sum=0; cin>>n; for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i]; if(n==1){ cout<<-1<<endl; return 0; } for(int i=1;i<=n;i++){ if(a[i]*2!=sum){ cout<<1<<endl; cout<<i<<endl; return 0; } } cout<<-1<<endl; return 0; }题意：将一个序列分割成若个段，每一段中保证奇数个数等于偶数个数，每次分割的花费为左右数之差绝对值，求花费不超过B，最多可以分割多少次 解法，显然，每一段都是偶数个数，所以分割点一定实在偶数下标的右边，又题目保证有解，所以无论怎么分割都是合理的。因此，直接把所有的分割花费求出来，排序，找到不超过B花费最多可以分割多少次
#include<bits/stdc++.h> using namespace std; multiset<int>s; int cnt[105],a[105]; int main() { ios::sync_with_stdio(false); int n,B; cin>>n>>B; for(int i=1;i<=n;i++){ cin>>a[i]; cnt[i]=cnt[i-1]+(a[i]&1); } for(int i=2;i<n;i+=2){ if(cnt[i]*2==i) s.insert(abs(a[i]-a[i+1])); } int ans=0; for(auto it:s){ B-=it; if(B<0) break; ans++; } cout<<ans<<endl; return 0; }题意：给出一个01串，两种操作，一种是翻转字串，花费为x，另一种是将连续的0串变为1串，花费为y 解法：可以发现，01串总共有四种形式，0101010, 010101, 1010101, 101010 （中间的0，1表示一个0串或者1串），后面三种两端的1串都可以直接去掉，转化成第一种形式。对于0101010 这种形式，如果不翻转总花费为cnt[0]*y ,翻转一次可以最多减少一个0串，花费为(cnt[0]-1)*y+x 。所以，当x<y 时全部翻转（次数为1串的个数），否则就直接用第二种操作
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn=3e5+5; char s[maxn]; int cnt[2],n; LL x,y,ans; int main() { ios::sync_with_stdio(false); cin>>n>>x>>y; cin>>s; int cur=s[0]-'0'; cnt[cur]++; for(int i=1;s[i];i++){ if(s[i]!=s[i-1]){ cur^=1; cnt[cur]++; } } if(cnt[0]==0) ans=0; else{ if(s[0]=='1'&&s[n-1]=='1'){ cnt[1]-=2; }else if(s[0]=='1'||s[n-1]=='1'){ cnt[1]--; } if(x>y) ans=LL(cnt[0])*y; else ans=LL(cnt[1])*x+y; } // cout<<cnt[0]<<' '<<cnt[1]<<endl; cout<<ans<<endl; return 0; }题意：给出四个罗马数字，求出n个这四种数字可以组合出多少个不同的数字。 解法；没有写出来方程。赛后看题解发现这个题就是找规律，当n大于11后变成了一个等差为49的等差数列。直接暴力打表找出前面的答案
#include<bits/stdc++.h> using namespace std; typedef long long LL; set<int>s[100]; int main() { ios::sync_with_stdio(false); for(int i=0;i<=20;i++){ for(int j=0;j<=20;j++){ for(int k=0;k<=20;k++){ for(int p=0;p<=20;p++){ s[i+j+k+p].insert(i+5*j+10*k+50*p); } } } } //for(int i=1;i<=20;i++) cout<<i<<' '<<s[i].size()<<endl; int n; cin>>n; if(n<=12) cout<<int(s[n].size())<<endl; else{ LL ans=LL(n-12)*49LL+LL(s[12].size()); cout<<ans<<endl; } return 0; }题意：一个n*n的矩阵，有三种颜色，问至少有一行或者一列颜色相同最多有多少种方案 解法：容斥公式，这题不会 http://codeforces.com/blog/entry/60357
#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL mod=998244353; const int maxn=1e6+5; int n; LL c[maxn],p[maxn]; inline LL power(LL a,LL n) { LL ret=1; while(n){ if(n&1) ret=ret*a%mod; a=a*a%mod; n>>=1; } return ret; } inline LL inv(LL x) { return power(x,mod-2); } inline void init() { p[0]=1; for(int i=1;i<=maxn;i++) p[i]=p[i-1]*3LL%mod; c[0]=1; for(int i=1;i<=n;i++) c[i]=(c[i-1]*inv(i)%mod)*(n-i+1)%mod; } int main() { ios::sync_with_stdio(false); cin>>n; init(); LL ans=0; for(int i=1;i<=n;i++){ LL temp=c[i]*p[i]%mod; temp=temp*power(3LL,1LL*n*(n-i))%mod; if((i+1)%2) ans=(ans-temp+mod)%mod; else ans=(ans+temp)%mod; } ans=ans*2%mod; for(int i=0;i<n;i++){ LL temp=3*c[i]%mod; LL t1=power((1-p[i]+mod)%mod,n); LL t2=power((-p[i]+mod)%mod,n); t1=(t1-t2+mod)%mod; temp=temp*t1%mod; if((i+1)%2) ans=(ans-temp+mod)%mod; else ans=(ans+temp)%mod; } cout<<ans<<endl; return 0; }