https://atcoder.jp/contests/abc262
C - Min Max Pair ：思维
样例：
4 1 3 2 4 结果：2
题意：给定n个数字，且数字范围是1-n，然后如果满足以下等式则ans++，求ans个数；如图
当a[i]=i时，则a[j]=j;统计所有a[i]=i的点，从中任意选两个，即n*(n-1)/2;
当a[i]!=i,则a[i]=j,a[j]=i;这样的(i,j)是一组答案；
code
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; int a[N]; long long n = 0; long long ans; for (int i=1; i<=N; ++i) { cin >> a[i]; if (i == a[i]) ++n; } ans = ((n-1)*(n-1)+(n-1))/2; int j; for (int i=1; i<=N; ++i) { j = a[i]; if ((a[j] == i) && (i < j)) ++ans; } cout << ans; return 0; }D - I Hate Non-integer Number ：dp
样例：
3 2 6 2 输出：6 2，6，2，均选一个；3 4，2，4，均选2个； 3 10/3非整数；不选
题意：给定一个序列，对于该序列的所有子集，判断所有子集的平均值为整数的子集的有多少个；答案对998244353取模；
用j,k,l,表示；dp(j,k,l)表示前j个数中选k个数，其和%i为 l 的方案数；如果其平均数是整数，则对i取模后结果必为0；即dp(n,i,0)为所有n个数中任取i个数，其和的平均值为整数的方案数；
状态转移方程：不选a[i] : dp(j+1,k,l)+=dp(j,k,l); 选：dp(j+1 , k+1 , ( l+a[i] )%i ) + = dp( j,k,l ); u即l
#include<bits/stdc++.h> using namespace std; #define ll long long const int N=110,mod = 998244353; ll dp[N][N][N]; ll a[N]; int main() { int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; ll res=0; for(int i=1;i<=n;i++)//最多i分 { memset(dp,0,sizeof dp); dp[0][0][0]=1;//初始值 for(int j=0;j<n;j++)//从j个里面选 { for(int k=0;k<=i;k++)//j个里选k个 的情况 { for(int u=0;u<i;u++)//余数 { dp[j+1][k][u]+=dp[j][k][u]%mod;//不选第j个 if(k!=i) { dp[j+1][k+1][(u+a[j])%i]+=dp[j][k][u]; } } } } res+=dp[n][i][0]%mod; } cout<<res%mod<<endl; }E - Red and Blue Graph：逆元求组合数
题意：给定无向图，每个点都可染成红色或蓝色，求满足：有k个点被染成红色；且满足两端点颜色不一样的边的个数为偶数的条件下，可能的方案数；
设两端点均是红色点的边的个数为a，一红一蓝的边数为b；则所有红色点的度之和为：s=2*b+c；故所有的红色点的度之和为偶数；即要找偶数个度数为奇数的点；假设选i个度数为奇数的红色的点，i一定要是偶数，则剩下k-i个点都是度数为偶数的点，才满足所有红色的点的度数和为偶数；
#include<bits/stdc++.h> using namespace std; #define ll long long const int N=2e5+10,mod=998244353; int d[N]; int n,m,k; int odd; ll ans=0; int fact[N],infact[N]; int qmi(int a,int k,int p) { int res=1; while(k) { if(k&1) { res=(ll)res*a%p; } a=(ll)a*a%p; k>>=1; } return res; }//逆元取模 void init() { fact[0]=infact[0]=1; for(int i=1;i<N;i++) { fact[i]=(ll)fact[i-1]*i%mod; infact[i]=(ll)infact[i-1]*qmi(i,mod-2,mod)%mod; } }//初始化，前缀和 ll c(int a,int b) { return (ll)fact[a]*infact[b]%mod*infact[a-b]%mod; }//求组合数 void solve() { init(); cin>>n>>m>>k; while(m--) { int x,y; cin>>x>>y; d[x]++,d[y]++; }//存度数d[]; for(int i=1;i<=n;i++) { if(d[i]&1) odd++; } for(int i=0;i<=k;i+=2)//i必须为偶数； { if(i>odd||k-i>n-odd)continue; ans=(ans+c(odd,i)*c(n-odd,k-i)%mod)%mod;// } cout<<ans%mod<<endl; } int main() { solve(); }4.还是要好好学组合数‘逆元；
F - Erase and Rotate
题意：给定一个序列p，长度为n，进行如下操作：选择任一个p[i]删除；或把最末尾的p[i]移动至最前方；问：最后得到的字典序最小的序列是.....
分析：每次操作使字典序更小；一定会操作k次，考虑两种方案：先找到最小的数字所在的位置：pos
操作纯删除：(pos<=k);则在pos之前的字符要全部删掉，然后剩余可操作的可利用单调栈来维护一个p[pos]打头，字典序最小的就是从最后开始往前删；
删除+旋转(n-pos<=k)：对于一个p[i]，删除+旋转或旋转+删除==删除；所以任一个p[i]要么删除、要么旋转；转完再删；等价于：先把pos之后的全删了，(因为比p[pos]大，转到前面去也不会更优)，p[pos]转到第一个；后续操作和3.单调栈+末尾删除一样；
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int p[N],n,k,pos=-1; vector<int> change1(){//纯删除 vector<int> v1{n+1}; if(pos<=k) { v1.clear(); int res=k-pos; for(int i=pos;i<n;i++) { while(!v1.empty()&&p[i]<v1.back()&&res>0) { res--; v1.pop_back(); } v1.push_back(p[i]); } while(res>0)//剩余次数未删的 { v1.pop_back(); res--; } } return v1; } vector<int> change2()//旋转+删除 { vector<int>v2{n+1}; if(n-pos<=k) { v2.clear(); int res=k-(n-pos);//删除后还剩多少次 for(int i0=0;i0<n;i0++) { int i=(i0+pos)%n; while(!v2.empty()&&p[i]<p[v2.back()]&&res>=(v2.back()<pos)) { res-=(v2.back()<pos);//在删除点之前的，每旋转过的，执行删除操作，在此之后再删等 //于直接删，所以只减1； v2.pop_back(); } v2.push_back(i); } while(res>=(v2.back()<pos)) { res-=(v2.back()<pos); v2.pop_back(); } for(auto &i:v2) { i=p[i]; } } return v2; } int main() { cin>>n>>k; for(int i=0;i<n;i++) cin>>p[i]; for(int i=0;i<n;i++) { if(i<=k||n-i<=k) { if(pos==-1||p[i]<p[pos]) { pos=i; } } } auto ans=min(change1(),change2()); n=ans.size(); for(int i=0;i<n;i++) { cout<<ans[i]<<' '; } cout<<endl; }在这里模拟一个单调堆栈：如果我们有剩余的操作，并且当前尾部大于要添加的下一个数字，我们只需擦除当前尾部即可。我们重复此操作，直到我们没有剩余的操作或当前尾部小于下一个数字。然后我们按下下一个数字。