比赛链接
A. Round Down the Price
没啥好说的就是最高位减一。
#include <bits/stdc++.h>
using namespace std;
int T,n;
int main()
{
for(scanf("%d",&T);T;--T){
scanf("%d",&n);
int x=1,y=n;
while(y>=10)x*=10,y/=10;
printf("%d\n",n-x);
}
}B. Polycarp Writes a String from Memory
题意：给定一个字符串，每次只能选择三种字符从前往后按顺序删除，遇到不能就停止，问最少删除几次。
做法同题面，开一个字符桶和一个时间戳，记一个变量存不同字符的个数，到4个更新答案。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int T,n,vis[26],dfn;
char S[N];
int main()
{
for(cin>>T;T;--T){
cin>>S;++dfn;int cnt=0,ans=0;
// puts(S);
int n = strlen(S);
for(int i=0;i<n;++i){
int c=S[i]-'a';
if(vis[c]!=dfn)++cnt,vis[c]=dfn;
if(cnt==4){
++ans;
++dfn;
cnt=1;
vis[c]=dfn;
// printf("#%d\n",i);
}
}
ans+=cnt!=0;
printf("%d\n",ans);
}
}C. Train and Queries
题意：给定火车到站前后顺序（n个），问m次询问，问x站能否到达y站
开两个map分别记录i站的最先出现的下标和最晚出现的下标。
只要判断x最先出现的时间和y站最晚出现的时间的先后关系即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int T,n,Q;
map<int,int>a,b;
int main()
{
for(scanf("%d",&T);T;--T){
scanf("%d%d",&n,&Q);
for(int i=1,x;i<=n;++i){
scanf("%d",&x);
if(a.find(x)==a.end())a[x]=i;
b[x]=i;
}
for(int i=1,x,y;i<=Q;++i){
scanf("%d%d",&x,&y);
if(a.find(x)==a.end()||a.find(y)==a.end()){
puts("NO");
continue;
}
puts(a[x]<b[y]?"YES":"NO");
}
a.clear(),b.clear();
}
}D. Not a Cheap String
题意：一个字符串的代价是所有字符在字母表里的位置的和，("aabb"=1+1+2+2)，问满足删除一些字符后，其他字符按照原串顺序连接的新串代价小于P，的最长字符串。
按照z~a的顺序删除，也就是代价从高到低删除，这样能保证新串最长。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int T,n,d;
char S[N];
struct Node{
int x,id,vis;
}a[N];
int cmp(Node x,Node y){
return x.x>y.x;
}
int cmp2(Node x,Node y){
return x.id<y.id;
}
int main()
{
for(cin>>T;T;--T){
cin>>S+1>>d;
// cout<<"#"<<S+1<<" "<<d<<endl;
n=strlen(S+1);int tot=0;
for(int i=1;i<=n;++i)a[i].x=S[i]-'a',a[i].id=i,tot+=S[i]-'a'+1;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n&&tot>d;++i){
a[i].vis=1,tot-=a[i].x+1;
}
sort(a+1,a+n+1,cmp2);
for(int i=1;i<=n;++i)if(!a[i].vis)putchar(a[i].x+'a');
for(int i=1;i<=n;++i)a[i].vis=0;
puts("");
}
}E. Split Into Two Sets
题意：给定n(even)个数对，问能够拆成2组，满足所有组内的所有数互不重复。
存在相同数之间的数对连边，然后黑白染色，判断有无解。（本质）
注意特判数对内相等和超过2个相同数的情况。
但是这个可以用扩展域并查集写，会简单很多。
为什么这个题我能做1h，而F却只做了20min 🙁 。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int T,n,A[N],cl[N];
struct Node{
int a,b;
}t[N];
int cmp(Node x,Node y){
return x.a<y.a;
}
int head[N],nxt[N<<1],to[N<<1],Cnt;
void Add(int x,int y){
nxt[Cnt]=head[x],to[Cnt]=y,head[x]=Cnt++;
}
int dfs(int x,int nc){
cl[x]=nc;
for(int i=head[x];~i;i=nxt[i]){
if(cl[to[i]]&&cl[to[i]]==cl[x]){
return 0;
}
if(!cl[to[i]]){
int p=dfs(to[i],-nc);
if(!p)return 0;
}
}
return 1;
}
int main()
{
for(scanf("%d",&T);T;--T){
scanf("%d",&n);
for(int i=1;i<=n;++i)head[i]=-1;Cnt=0;
for(int i=1;i<=n;++i){
scanf("%d%d",&t[i].a,&t[i].b);
}
int flg=1;
for(int i=1;i<=n;++i){
if(t[i].a==t[i].b){
flg=0;
break;
}
if(!A[t[i].a])A[t[i].a]=i;
else if(A[t[i].a]!=-1)Add(i,A[t[i].a]),Add(A[t[i].a],i),A[t[i].a]=-1;
else {
flg=0;break;
}
if(!A[t[i].b])A[t[i].b]=i;
else if(A[t[i].b]!=-1)Add(i,A[t[i].b]),Add(A[t[i].b],i),A[t[i].b]=-1;
else {
flg=0;break;
}
}
for(int i=1;i<=n;++i)if(!cl[i]){
if(!dfs(i,1)){
flg=0;break;
}
}
puts(flg?"YES":"NO");
// for(int i=1;i<=n;++i)printf("%d ",cl[i]);puts("");
for(int i=1;i<=n;++i)A[i]=cl[i]=0;
}
}F. Equate Multisets
题意：给定多重集A和B，能对B集合进行两个操作，分别是找一个数乘以2，和找一个数整除2，问B是否能转化成A。
首先对于A和B中每个数的2的幂次的因数来说，都是可以除去的，因为在整除2或者乘以2的时候是没有影响的。
所以我们只要考虑剩下的奇数因子即可。
我们对A和B中的奇数因子排序。
对B从后往前扫，不停整除2，直到找到A中第一个未匹配的相等数。
这样为什么是最优的？
因为保证了较大数匹配较大数，使得匹配空间更大。（贪心）
其实奇数因子的操作也可用优先队列实现，每次取两堆堆顶判断是否相等，不相等就把B的整除2，再把两个放回去。
失败的特征是A优先队列的堆顶大于B的，成功则是两优先队列弹完。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int T,n,a[N],b[N];
map<int,int>ck;
int main()
{
for(scanf("%d",&T);T;--T){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)scanf("%d",&b[i]);
for(int i=1;i<=n;++i){
while(!(a[i]&1))a[i]/=2;
while(!(b[i]&1))b[i]/=2;
}
sort(a+1,a+n+1);
sort(b+1,b+n+1);
for(int i=1;i<=n;++i)ck[a[i]]=ck[a[i]]+1;
int flg=1;
for(int i=n,j;i;--i){
j=b[i];
while((ck.find(j)==ck.end()||!ck[j])&&j)j=j/2;
if(ck.find(j)!=ck.end())--ck[j];
else {
flg=0;break;
}
}
puts(flg?"YES":"NO");
ck.clear();
}
}G. Passable Paths
题意：给定一棵n个点的树，和m次询问，每次询问一个集合，问集合内的点是否能够在一条边不经过两次的情况下全部到达。
首先”集合内的点在一条边不经过两次的情况下全部到达“其实就是表示这些点在树上呈一条链状。
所以我们只要找到集合内深度最深的点u，距离它最远的点v，求他们之间的距离mx，然后判断其他点是否在这条树链上即可。
check点x方法是判断dist(u,x)+dist(x,v)是否等于mx。
树上距离用LCA求。
挂一个比较短的代码：
//By wsyear, contest: Codeforces Round #805 (Div. 3), problem: (G2) Passable Paths (hard version), Accepted
#pragma GCC optimize(2,3,"Ofast")
#include<bits/stdc++.h>
using namespace std;
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define Rof(i,j,k) for(int i=(j);i>=(k);i--)
#define int long long
int n,dep[200010],fa[200010][21];
int k,a[200010];
vector<int> e[200010];
void dfs(int u){
for(int v:e[u]) if(v!=fa[u][0]){
fa[v][0]=u,dep[v]=dep[u]+1,dfs(v);
}
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
int dc=dep[u]-dep[v];
Rof(i,20,0) if(dc&(1<<i)) u=fa[u][i],dc^=(1<<i);
if(u==v) return u;
Rof(i,20,0) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
int dis(int u,int v){
return dep[u]+dep[v]-2*dep[lca(u,v)];
}
signed main(){
cin>>n;
For(i,1,n-1){
int u,v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1);
For(j,1,20) For(i,1,n) fa[i][j]=fa[fa[i][j-1]][j-1];
int q; cin>>q;
while(q--){
cin>>k;
For(i,1,k) cin>>a[i];
int s=-1,t=-1,mx=-1;
For(i,1,k) if(dep[a[i]]>mx) mx=dep[a[i]],s=a[i];
mx=-1;
For(i,1,k) if(dis(a[i],s)>mx) mx=dis(a[i],s),t=a[i];
bool ans=1;
For(i,1,k) if(dis(t,a[i])+dis(s,a[i])!=mx) ans=0;
if(ans) cout<<"YES\n";
else cout<<"NO\n";
}
}