1144A.DS
给出一个字符串，只可能包含小写字母，要求不能有重复的字符和里面的字母是一串连续的数字（bcdef...），输出Yes或No。
对字符串排序即可。
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+100; int t; string s; int main () { cin>>t; while (t--) { cin>>s; if (s.length()==1) { printf("Yes "); continue; } if (s.length()>26) { printf("No "); continue; } set<int> st; for (int i=0;i<s.length();i++) st.insert(s[i]); if (st.size()!=s.length()) { printf("No "); continue; } sort(s.begin(),s.end()); int f=1; for (int i=0;i<s.length()-1;i++) if (s[i+1]-s[i]>1) f=0; if (f) printf("Yes "); else printf("No "); } }
1144B.PAD
对一个序列做删除操作，每次删除元素的奇偶性必须与上次删除的元素的奇偶性相反，当找不到奇偶性相反的元素的时候就停止删除，询问序列中剩下元素的最大值。
开两个数组分别存储序列中的奇数和偶数，然后从大到小排序，分别判断奇数多和偶数多两种情况，具体看代码。
#include<bits/stdc++.h> using namespace std; const int maxn=2005; typedef long long ll; int n; int a[maxn]; int main () { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); vector<int> v[2]; for (int i=1;i<=n;i++) { v[a[i]%2].push_back(a[i]); } sort(v[0].begin(),v[0].end()); sort(v[1].begin(),v[1].end()); if (v[0].size()==v[1].size()) { printf("0 "); return 0; } if (v[0].size()>v[1].size()) { ll ans=0; for (int i=0;i<v[0].size()-v[1].size()-1;i++) ans+=v[0][i]; printf("%lld ",ans); return 0; } else { ll ans=0; for (int i=0;i<v[1].size()-v[0].size()-1;i++) ans+=v[1][i]; printf("%lld ",ans); return 0; } }
1144C.TSC
给出一个序列，里面的数字可以打乱顺序，请你组出两个序列，分别严格递增和递减，或者输出不可能。
显然当有一个数字出现次数大于2是无解的。
然后开一个哈希表存储数字，分别正向反向遍历表，枚举出答案。
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+100; int a[maxn]; int cnt[maxn]; int n; int main () { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]),cnt[a[i]]++; for (int i=0;i<maxn;i++) if (cnt[i]>2) { printf("NO "); return 0; } vector<int> v1,v2; for (int i=0;i<maxn;i++) { if (cnt[i]>0) { v1.push_back(i); cnt[i]--; } } for (int i=maxn-1;i>=0;i--) { if (cnt[i]>0) { v2.push_back(i); cnt[i]--; } } printf("YES "); printf("%d ",v1.size()); for (int i=0;i<v1.size();i++) printf("%d ",v1[i]); printf(" "); printf("%d ",v2.size()); for (int i=0;i<v2.size();i++) printf("%d ",v2[i]); printf(" "); }
1144D.ETA
有两种操作，一种是使后面的数和前面的数一样，一种是使前面的数和后面的数一样，询问最少操作数使得整个数组的每个元素相等。
显然使得每个数和出现最多的数字相等操作次数最少。
先枚举出出现次数最多的那个数，然后随便找一个这个数出现的位置，分别向左边和右边做两种操作。
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+100; int n; int a[maxn]; map<int,int> cnt; struct node { int op,i,j; }; int main () { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]),cnt[a[i]]++; int wjm=-1,Max=0; for (auto it=cnt.begin();it!=cnt.end();it++) if (it->second>Max) Max=it->second,wjm=it->first; vector<node> v; int pre=1; for (int i=1;i<=n;i++) { if (a[i]==wjm) { int j; for (j=i-1;j>=1;j--) { if (a[j]<wjm) v.push_back({1,j,j+1}); else if (a[j]>wjm) v.push_back({2,j,j+1}); } for (j=i+1;j<=n;j++) { if (a[j]<wjm) v.push_back({1,j,j-1}); else if (a[j]>wjm) v.push_back({2,j,j-1}); } break; } } printf("%d ",v.size()); for (int i=0;i<v.size();i++) printf("%d %d %d ",v[i].op,v[i].i,v[i].j); }
1144E.MS
给出两个序列s和t，找到他们的字典序的中位数对应的序列。
模拟26进制的相加和除法。
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+100; int n; char s[maxn]; char t[maxn]; int wjm[maxn]; int main () { scanf("%d",&n); scanf("%s",s); scanf("%s",t); for (int i=n-1;i>=0;i--) { int x=t[i]-'a'; int y=s[i]-'a'; if (x-y<0) { //借位 t[i-1]--; x+=26; } if ((x-y)%2==0) wjm[i]=(x-y)/2; else { wjm[i]=(x-y)/2; wjm[i+1]+=13; } } for (int i=n-1;i>=0;i--) { int x=s[i]-'a'; wjm[i-1]+=(x+wjm[i])/26; wjm[i]=(x+wjm[i])%26; } for (int i=0;i<n;i++) printf("%c",wjm[i]+'a'); }
1144F.GWLDP
给出一个无向图，请你把里面的边改成有向的，使得答案有向图不存在大于等于2的路径。
二分图染色一遍就可以。
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+100; struct node { int u,v; }edge[maxn]; vector<int> g[maxn]; int n,m; int c[maxn]; int wjm; void dfs (int u) { for (int v:g[u]) { if (!c[v]) { c[v]=3-c[u]; dfs(v); } else if (c[u]==c[v]) { wjm=0; } } } int main () { scanf("%d%d",&n,&m); wjm=1; for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); edge[i].u=x; edge[i].v=y; } c[1]=1; dfs(1); if (!wjm) { printf("NO "); return 0; } printf("YES "); for (int i=1;i<=m;i++) { if (c[edge[i].u]==1) printf("1"); else printf("0"); } }
1144G.TMS
给出一个序列，请你把它分成两份，一份是严格递增的，一份是严格递减的。
贪心，维护当前递增序列的最后一个元素和递减序列的最后一个元素，然后判断当前元素能加入哪个序列。
如果都可以，就取出后面那个元素，比较当前元素和后面那个元素的大小。思想是使得后面元素的选择空间更大。
//贪心 //维护当前下降序列的最后一个元素和上升序列的最后一个元素 //a[i]>Min&&a[i]<Max无解 //a[i]<Min&&a[i]<Max进入下降序列 //a[i]>Min&&a[i]>Max进入上升序列 #include<bits/stdc++.h> using namespace std; const int maxn=2e5+100; int a[maxn]; int wjm[maxn]; int n; int main () { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); int Min=1e9,Max=-1e9; int f=1; for (int i=1;i<=n;i++) { if (a[i]>=Min&&a[i]<=Max) { f=0;break; } if (a[i]<Min&&a[i]<=Max) { wjm[i]=1; Min=a[i]; continue; } if (a[i]>=Min&&a[i]>Max) { wjm[i]=0; Max=a[i]; continue; } if (a[i]<Min&&a[i]>Max) { if (a[i]>a[i+1]) wjm[i]=1,Min=a[i]; else wjm[i]=0,Max=a[i]; continue; } } if (!f) { printf("NO "); return 0; } printf("YES "); for (int i=1;i<=n;i++) printf("%d ",wjm[i]); }