A:水，直接遍历就好了
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pii pair<int,int> #define C 0.5772156649 #define pi acos(-1.0) #define ll long long #define mod 20090717 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 using namespace std; const double g=10.0,eps=1e-12; const int N=3000+10,maxn=10000+10,inf=0x3f3f3f3f; string s[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++)cin>>s[i]; for(int i=0;i<n;i++) { if(s[i][0]=='O'&&s[i][1]=='O') { cout<<"YES"<<endl; s[i][0]=s[i][1]='+'; for(int j=0;j<n;j++)cout<<s[j]<<endl; return 0; } if(s[i][3]=='O'&&s[i][4]=='O') { cout<<"YES"<<endl; s[i][3]=s[i][4]='+'; for(int j=0;j<n;j++)cout<<s[j]<<endl; return 0; } } cout<<"NO"<<endl; return 0; } /******************** ********************/
B：一个矩阵里只有一个0，找一个正整数填上去，使每行每列和两个对角线之和相同
坑点：忘记判断最后是正数的情况
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pii pair<int,int> #define C 0.5772156649 #define pi acos(-1.0) #define ll long long #define mod 20090717 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 using namespace std; const double g=10.0,eps=1e-12; const int N=3000+10,maxn=10000+10,inf=0x3f3f3f3f; string s[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++)cin>>s[i]; for(int i=0;i<n;i++) { if(s[i][0]=='O'&&s[i][1]=='O') { cout<<"YES"<<endl; s[i][0]=s[i][1]='+'; for(int j=0;j<n;j++)cout<<s[j]<<endl; return 0; } if(s[i][3]=='O'&&s[i][4]=='O') { cout<<"YES"<<endl; s[i][3]=s[i][4]='+'; for(int j=0;j<n;j++)cout<<s[j]<<endl; return 0; } } cout<<"NO"<<endl; return 0; } /******************** ********************/
C：1到n每个为0的格子填充1到m的颜色，求连续区间有k个的最小权值填充情况
看了好久没有一点思路= =， 然后发现居然是O（n^4）的dp。。
转移方程：dp[i][j][k]代表从1到i已经填充好了，i是填j的颜色，有k个连续区间的最小权值
if(c[i]==0)dp[i][j][k]=min(hh,dp[i-1][j][k])+cost[i][j]
else dp[i][c[i]]][k]=min(dp[i-1][c[i]]][k],hh)
hh=dp[i-1][!j][k-1]
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pii pair<int,int> #define C 0.5772156649 #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 using namespace std; const double g=10.0,eps=1e-12; const int N=100+10,maxn=10000+10,inf=0x3f3f3f3f; int c[N],p[N][N]; ll dp[N][N][N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,m,k; cin>>n>>m>>k; for(int i=1;i<=n;i++)cin>>c[i]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>p[i][j]; for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) for(int u=0;u<=k;u++) dp[i][j][u]=1e15; if(!c[1]) { for(int i=1;i<=m;i++)dp[1][i][1]=p[1][i]; } else dp[1][c[1]][1]=0; for(int i=2;i<=n;i++) { if(c[i]!=0) { for(int j=1;j<=m;j++) { for(int u=1;u<=i&&u<=k;u++) { if(j==c[i])dp[i][c[i]][u]=min(dp[i][c[i]][u],dp[i-1][c[i]][u]); else dp[i][c[i]][u]=min(dp[i][c[i]][u],dp[i-1][j][u-1]); } } } else { for(int j=1;j<=m;j++) { for(int u=1;u<=m;u++) { for(int v=1;v<=k&&v<=i;v++) { if(j==u)dp[i][j][v]=min(dp[i][j][v],dp[i-1][j][v]+p[i][j]); else dp[i][j][v]=min(dp[i][j][v],dp[i-1][u][v-1]+p[i][j]); } } } } } ll ans=1e15; for(int i=1;i<=m;i++) // cout<<dp[n][i][k]<<endl, ans=min(ans,dp[n][i][k]); if(ans>=1e15)cout<<-1<<endl; else cout<<ans<<endl; return 0; } /******************** if(c[i]==0)dp[i][j][k]=min(hh,dp[i-1][j][k])+cost[i][k] else dp[i][j][c[i]]=min(dp[i-1][j][c[i]],hh) hh=dp[i-1][j-1][!k] 2 2 2 0 0 1 2 2 1 ********************/
D：给你一个数组，i从i到a【i】有一条边，对于一个有向图如果有环，那么我们叫他混乱的，要求所有翻转边的情况来使得该图不混乱
题解:em首先可以注意到，该图中的环一定是简单环，而且每个联通块一定只有一个环，然后我们分别考虑每一个环（n个点），我们一定有2^n-2种翻转情况，因为需要排除正向环和反向环的情况，然后对于不是环的边，分别乘上去就好了
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pii pair<int,int> #define C 0.5772156649 #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 using namespace std; const double g=10.0,eps=1e-12; const int N=200000+10,maxn=10000+10,inf=0x3f3f3f3f; vector<int>v[N]; int a[N],pre[N]; int sz,en,be; void dfs(int u,int f) { // cout<<u<<" "<<f<<endl; pre[u]=f;sz++; for(int i=0;i<v[u].size();i++) { int x=v[u][i]; if(x==f)continue; if(!pre[x])dfs(x,u); else { be=u;en=x; } } } ll quick(ll a,ll b) { ll ans=1; while(b) { if(b&1)ans=ans*a%mod; a=a*a%mod; b/=2; } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; v[i].pb(a[i]); v[a[i]].pb(i); } ll ans=1; for(int i=1;i<=n;i++) { if(!pre[i]) { sz=en=be=0; dfs(i,n+1); // cout<<en<<" "<<be<<endl; if(en!=0) { int res=1; for(int p=en;p!=be;p=pre[p])res++; ans=ans*(quick(2,res)-2)%mod*quick(2,sz-res)%mod; } else ans=ans*quick(2,sz)%mod; } } cout<<ans<<endl; return 0; } /******************** 5 2 3 1 5 4 ********************/
E。。。待补