A题
通过平移线段可以发现其实就是缺少的那一块的大小
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=5e5+10; int main(){ ios::sync_with_stdio(false); ll a,b,c,d; cin>>a>>b>>c>>d; cout<<(a+2)*(b+d+2)-d*(a-c)-a*b-c*d<<endl; return 0; }
B题
思维题，因为我们肯定是最优策略，因此当前两个点的最小值和前面的两个最大值的差值相减，但是要和0取max
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=5e5+10; int a[N],b[N]; int main(){ ios::sync_with_stdio(false); int n; cin>>n; int i; for(i=2;i<=n+1;i++) cin>>a[i]>>b[i]; ll ans=1; a[1]=b[1]=0; n++; for(i=1;i<=n;i++){ ans+=max(0,min(a[i],b[i])-max(a[i-1],b[i-1])+1); if(a[i-1]==b[i-1]) ans--; } cout<<ans<<endl; return 0; }
C题
肯定是先递增后递减最好，因为不是这样，最大值无论移到哪里都会变劣
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=5e5+10; int a[N],b[N]; queue<int> q1; stack<int> q2; int main(){ ios::sync_with_stdio(false); int n; cin>>n; int i,j,k; for(i=1;i<=n;i++){ cin>>a[i]; } sort(a+1,a+1+n); for(i=1;i<=n;i++){ if(i&1) q1.push(a[i]); else q2.push(a[i]); } while(q1.size()){ cout<<q1.front()<<" "; q1.pop(); } while(q2.size()){ cout<<q2.top()<<" "; q2.pop(); } return 0; }
D题
这题显然是比较大小的关系，这容易让我们联想到差分约束建图，虽然差分约束不行，但是建图还是很合理的，我们可以考虑将小点连往大点。但是现在有相同点，这个很好处理，只要考虑并查集，把相同点缩成一个点
之后就是个拓扑图跑一下最长路，问题是可能有环，也就是冲突情况，这种情况这些点不会进入拓扑排序，因此只要判断一下是否全部都进行了拓扑排序
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=2e6+10; int h[N],ne[N],e[N],idx; int ans[N]; int p[N]; int in[N]; int vis[N]; int flag; string s[N]; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int find(int x){ if(x!=p[x]){ p[x]=find(p[x]); } return p[x]; } void topo(int u){ queue<int> q; ans[u]=1; q.push(u); while(q.size()){ int t=q.front(); q.pop(); for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; in[j]--; ans[j]=max(ans[j],ans[t]+1); if(!in[j]){ vis[j]=1; q.push(j); } } } } int main(){ ios::sync_with_stdio(false); int n,m; cin>>n>>m; int i,j; for(i=1;i<=n+m;i++){ p[i]=i; } memset(h,-1,sizeof h); for(i=1;i<=n;i++){ cin>>s[i]; s[i]=" "+s[i]; for(j=1;j<=m;j++){ if(s[i][j]=='='){ int pa=find(i); int pb=find(n+j); if(pa!=pb) p[pa]=pb; } } } for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ int pa=find(i),pb=find(n+j); if(s[i][j]=='>'){ add(pb,pa); in[pa]++; } else if(s[i][j]=='<'){ add(pa,pb); in[pb]++; } } } for(i=1;i<=n+m;i++){ int pa=find(i); if(pa==i&&!in[i]&&!vis[i]){ vis[i]=1; topo(i); } } for(i=1;i<=n+m;i++){ int pa=find(i); if(pa==i&&!vis[i]){ cout<<"No"<<endl; return 0; } } cout<<"Yes"<<endl; for(i=1;i<=n;i++){ int pa=find(i); cout<<ans[pa]<<" "; } cout<<endl; for(i=n+1;i<=n+m;i++){ int pa=find(i); cout<<ans[pa]<<" "; } cout<<endl; return 0; }
E题
想的时候没想到，看到题解觉得顺理成章
主要是观察题目信息，给的信息确实比较明显，因为只考虑单个字符，因此可以使用dp数组记录前i个字符为j的最大子串长度
因为题目要求的是一个当前pi一个之前的串中单个字符之后再一个pi
因此我们仔细观察可以发现前缀和后缀的思路。
之后只要check所有情况取max，注意当当前pi中所有字符相等的时候，要额外考虑，因此其他情况中间都会分割，而这种情况不会，且没有通性。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=2e5+10; ll f[N][30]; string s; int main(){ ios::sync_with_stdio(false); int n; cin>>n; int i,j; memset(f,0,sizeof f); for(i=1;i<=n;i++){ cin>>s; int len=(int)s.size(); s=" "+s; int pre=1; for(j=2;j<=len;j++){ if(s[j]==s[1]) pre++; else break; } int suf=1; for(j=len-1;j>=1;j--){ if(s[j]==s[len]){ suf++; } else break; } for(j=0;j<26;j++){ f[i][j]=(f[i-1][j]>0); } for(j=1;j<=len;j++){ int tmp=j; while(tmp+1<=len&&s[tmp+1]==s[j]) tmp++; f[i][s[j]-'a']=max(f[i][s[j]-'a'],1ll*tmp-j+1); j=tmp; } if(pre==len){ f[i][s[1]-'a']=(f[i-1][s[1]-'a']+1)*len+f[i-1][s[1]-'a']; } else{ f[i][s[1]-'a']=max(f[i][s[1]-'a'],1ll*pre+1ll*(f[i-1][s[1]-'a']>0)); f[i][s[len]-'a']=max(f[i][s[len]-'a'],1ll*suf+1ll*(f[i-1][s[len]-'a']>0)); if(s[1]==s[len]&&f[i-1][s[1]-'a']){ f[i][s[1]-'a']=max(f[i][s[1]-'a'],1ll*pre+suf+1); } } } ll ans=0; for(i=0;i<26;i++){ ans=max(ans,f[n][i]); } cout<<ans<<endl; return 0; }
F题
能看的出是并查集的思路，有两种做法，一种是启发式合并，一种是维护头结点之后跑dfs
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=2e5+10; int p[N]; int n; vector<int> num[N]; int find(int x){ if(x!=p[x]){ p[x]=find(p[x]); } return p[x]; } void dfs(int u){ int i; cout<<u<<" "; for(i=0;i<num[u].size();i++){ int j=num[u][i]; dfs(j); } } int main(){ ios::sync_with_stdio(false); cin>>n; int i; for(i=1;i<=n;i++){ p[i]=i; } for(i=1;i<n;i++){ int a,b; cin>>a>>b; int pa=find(a); int pb=find(b); p[pa]=pb; num[pb].push_back(pa); } for(i=1;i<=n;i++){ if(p[i]==i){ dfs(i); break; } } return 0; }
G题