A题：给一个字符串，问字符串内字母是否是唯一且能够排列成连续的。
直接sort一遍然后顺序遍历看之前的每个字母和之前那个是否连续【即a[i-1]==a[i]-1?】
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100+7;
int n;
int main()
{
char tmp[maxn];
scanf("%d",&n);
while(n--)
{
scanf("%s",tmp);
bool ans=true;
sort(tmp,tmp+strlen(tmp));
for(int i=1;i<strlen(tmp);i++)
{
if(tmp[i]==tmp[i-1]+1)continue;
else
{
ans=false;
break;
}
}
printf("%s
",ans?"Yes":"No");
}
}
B给一个序列，按照 -奇-偶 或 -偶-奇 的顺序删除数字，问删除到不能删除时剩下数的最小总和是多少
首先统计一下数字奇偶各多少，若差值小于等于1说明是可以彻底删完的。若删不完，那么剩下的肯定是多出来的奇数或偶数，那么排序之后取最小的几个奇数或者偶数求和即可。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2000+7;
int n;
int a[maxn];
int main()
{
scanf("%d",&n);
int o=0,e=0;
for(int i=0; i<n; i++)
{
scanf("%d",&a[i]);
if(a[i]&1)o++;
else e++;
}
if(abs(o-e)<=1)
{
printf("0
");
return 0;
}
sort(a,a+n);
int ans=0;
if(e>o)
{
int tmp=e-o-1;
int i=0;
while(tmp>0&&i<n)
{
if(!(a[i]&1))ans+=a[i],tmp--;
i++;
}
}
else
{
int tmp=o-e-1;
int i=0;
while(tmp>0&&i<n)
{
if(a[i]&1)ans+=a[i],tmp--;
i++;
}
}
printf("%d
",ans);
}
C有俩严格递增和严格递减的序列，将这俩序列合成到一起，现在给你合成的序列，问该序列是否是由两个严格递增和递减的序列生成的，是的话输出俩序列
给序列排序，输入时预处理好每个数字的出现次数，可以知道出现超过2次的，一定有一个序列出现过多次，那么表示一定不是严格递增或递减的，那么直接输出NO，否则，顺序遍历排序好的序列，没出现过的数字扔到递增序列，遇到一个重复出现的数字扔到递减序列，最后正序输出递增，逆序输出递减即可
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2e5+7;
int n;
int a[maxn];
short int vis[maxn];
int main()
{
scanf("%d",&n);
bool flag=true;
for(int i=0; i<n; i++)
{
scanf("%d",&a[i]);
vis[a[i]]++;
if(vis[a[i]]>=3)flag=false;
}
if(!flag)
{
printf("NO
");
return 0;
}
vector<int>up,down;
sort(a,a+n);
for(int i=0; i<n; i++)
{
if(i==0)up.push_back(a[i]);
else
{
if(a[i]>up.back())up.push_back(a[i]);
else down.push_back(a[i]);
}
}
printf("YES
");
printf("%d
",up.size());
if(up.size()==0)printf("
");
else
{
for(int i=0; i<up.size(); i++)printf("%d%c",up[i],i==up.size()-1?'
':' ');
}
printf("%d
",down.size());
if(down.size()==0)printf("
");
else
{
for(int i=down.size()-1; i>=0; i--)printf("%d%c",down[i],i==0?'
':' ');
}
}
D给一个序列，有俩操作，对两个相邻的数字，可以让小的值加上两数差值使其相等，也能让大的值减少两者差值使其相等，问最少要做多少次操作可以使整个序列的值相等。
可以知道的是，这样的操作一定能让整个序列的值相等，然后就是，这样的操作是具有传递性的，那么我们一定是指定了某个数，然后从左到右或从右到左扩散开来这样赋值，如何操作才是步数最少的，明显是让剩下的数都等于开始序列中存在数量最多的数，操作次数是最小的。因此输入时找到出现次数最多的数，记录该数出现的任意一个位置，以该位置为起点左右扩散并输出结果即可。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2e5+7;
int n;
int a[maxn];
int cnt[maxn];
int main()
{
scanf("%d",&n);
int maxcnt=0;
int maxnum=0;
int index=0;
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
cnt[a[i]]++;
if(cnt[a[i]]>maxcnt)maxcnt=cnt[a[i]],maxnum=a[i],index=i;
}
printf("%d
",n-maxcnt);
for(int i=index; i>=1; i--)
{
if(a[i]==maxnum)continue;
int t;
if(a[i]>maxnum)t=2;
else t=1;
printf("%d %d %d
",t,i,i+1);
}
for(int i=index; i<=n; i++)
{
int t;
if(a[i]==maxnum)continue;
if(a[i]>maxnum)t=2;
else t=1;
printf("%d %d %d
",t,i,i-1);
}
}
E两个等长字符串，字符串只用小写字母构成，第一个字符串字典序严格小于第二个字符串，输出按字典序排列下两串的中位串。
若按数字全排列来说，那么两串相隔距离的中间位置串即中位数，换成字母也是如此，即26个字母是26进制的中位数。想想在十进制下是如何计算中位数，（左边界+右边界）/2，那么此处也是这样，从低位到高位模拟26进制加法和除法。当同位两数加和是偶数时，中位数除2即可，若是奇数，那么该位余1，并借位给低位，那么低位是已经做了除2计算的，因此低位借位到的1不当26处理，而当13处理，并加到低位上，于是当前高位可以直接除2，而低位借位后重新计算是否需要进位，并对26取模。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2e5+7;
int main()
{
int n;
char a[maxn],b[maxn],ans[maxn];
scanf("%d%s%s",&n,a,b);
for(int i=n-1;i>=0;i--)
{
char mid=(a[i]+b[i])-194;
if(mid&1)
{
ans[i+1]-='a';
ans[i+1]+=13;
ans[i]=(mid-1)>>1;
ans[i]+=ans[i+1]/26;
ans[i]+='a';
ans[i+1]%=26;
ans[i+1]+='a';
}
else ans[i]=mid/2+'a';
}
ans[n]=' ';
printf("%s
",ans);
}
F给n个点和m条边，每条边都是有向的，输入构成一个图，现在要求改变图中有向边的指向，问能否构成一个从任何点出发，路径长度都小于等于1的有向图。若可以输出YES，并给出m条边的指向，若与输入时指向一样则输出0，否则为1。若该图不能构成任何路径都为1的有向图输出NO
跑一个BFS，得到到达每个节点的时间戳，若两个存在有向边的节点间时间戳 都为偶数，说明比不满足路径长度小于等于1的条件。直接返回false，否则一定有解，根据每个节点的时间戳对节点进行01染色
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2e5+7;
int n,m;
struct edge
{
int id,from,to;
edge(){}
edge(int a,int b,int c)
{
id=a,from=b,to=c;
}
}a[maxn];
vector<edge>mp[maxn];
int dis[maxn];
bool bfs()
{
memset(dis,0x3f,sizeof dis);
queue<pair<int,int> >q;
q.push(make_pair(1,0));
while(!q.empty())
{
pair<int,int> top=q.front();
q.pop();
for(int i=0;i<mp[top.first].size();i++)
{
edge tmp=mp[top.first][i];
if(dis[tmp.to]>=0x3f3f3f3f)
{
dis[tmp.to]=top.second+1;
q.push(make_pair(tmp.to,dis[tmp.to]));
}
else if(dis[tmp.to]%2==top.second%2)return false;
}
}
return true;
}
int main()
{
char ans[maxn];
bool flag=true;
int from,to;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&from,&to);
a[i]=edge(i,from,to);
mp[from].push_back(edge(i,from,to));
mp[to].push_back(edge(i,to,from));
}
if(!bfs()) printf("NO
");
else
{
printf("YES
");
for(int i=1;i<=n;i++)
{
for(int j=0;j<mp[i].size();j++)
{
edge tmp=mp[i][j];
if(tmp.from==a[tmp.id].from)ans[tmp.id]=dis[i]%2?'0':'1';
else ans[tmp.id]=dis[i]%2?'1':'0';
}
}
ans[m+1]=' ';
puts(ans+1);
}
}