CF1702.

A. Round Down the Price

#include<bits/stdc++.h>
using namespace std;
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
int pw[100];
int main() {
	pw[0]=1;
	for(int i=1;i<=10;++i) pw[i]=pw[i-1]*10;
	int t=read();
	while(t--) {
		int n=read();
		int e=log10(n);
		printf("%d\n",n-pw[e]);
	}
}

B. Polycarp Writes a String from Memory

用std::set自动完成去重，随便输出即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t, n;
char s[N];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	string s; cin>>s;
	int ans=1;
	set<char> ss;
	for(auto x:s) {
		ss.insert(x);
		if(ss.size()==4) {
			ss.clear();
			ss.insert(x);
			++ans;
		}
	}
	printf("%d\n",ans);
}
int main() {
	t=read();
	while(t--) solve();
}

C. Train and Queries

如果能从站 \(i\) 到站 \(j\)，当且仅当 \(i\) 第一次出现的位置小于 \(j\) 最后一次出现的位置。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t, n, k;
map<int,int> a, b;
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	n=read(), k=read();
	a.clear(), b.clear();
	for(int i=1;i<=n;++i) {
		int x=read();
		if(!a[x]) a[x]=i, b[x]=i; else b[x]=i;
	}
	while(k--) {
		int x=read(), y=read();
		if(!a[x]) puts("NO");
		else puts(a[x]<b[y]? "YES":"NO");
	}
}
int main() {
	t=read();
	while(t--) solve();
}

D. Not a Cheap String

贪心地删除字典序较大的字母

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t, p;
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	string s, ss; cin>>s;
	ss=s;
	p=read();
	sort(ss.rbegin(),ss.rend());
    // 字典序从大到小排序
	int tot=0;
	for(auto x:s) tot+=x-'a'+1;
	map<char,int> m;
	for(auto x:ss) {
		if(tot>p) ++m[x], tot-=x-'a'+1;
	}
	for(auto x:s) {
		if(!m[x]) printf("%c",x); else --m[x];
	}
	puts("");
}
signed main() {
	t=read();
	while(t--) solve();
}

E. Split Into Two Sets

显然，你可以选择是否根据抽屉原理，得到如果存在 \(a_i = b_i\) 或者某个数字出现了两次以上，那么一定无解。

对于一组 \((a_i,b_i)\)，连边 \((a_i \rightarrow b_i)\)，\((b_i \rightarrow a_i)\)。

以下讨论均不讨论环，断环为链即可。

从一个节点 \(x\) 出发到达 \(y\)，再从 \(y\) 到达 \(z\)，这说明 \(x\) 与 \(z\) 不能在同一组。由于没有自环，所以只要取这一条路径上的点，交替加入两个集合。如果从 \(x\) 出发的最长路径经过的节点个数为奇数，那么一定无解。否则，一定有解。

证明：由于每个节点最多在 dominoes 中出现两次，所以每个节点至多存在两条边。因此，如果 \(x\) 只有一个节点，那么显然是对的，否则由于最长路径上，除了 \(x\) 和最后一个点之外，每个点有连接了两条边，所以 \(x\) 的另一条路径一定只连接了一个点——路径末尾的点，显然也是合法的。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int t, n;
vector<int> p[N];
bool v[N];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
int dfs(int x) {
	v[x]=1;
	for(auto y:p[x]) if(!v[y]) return dfs(y)+1;
	return 1;
}
void solve() {
	n=read();
	memset(v,0,sizeof(v));
	for(int i=1;i<=n;++i) p[i].clear();
	int fg=1;
	for(int i=1;i<=n;++i) {
		int x=read(), y=read();
		p[x].push_back(y), p[y].push_back(x);
		if(x==y||p[x].size()>2||p[y].size()>2) fg=0;
	}
	if(!fg) { puts("NO"); return; }
	fg=1;
	for(int i=1;i<=n;++i) if(!v[i]&&dfs(i)%2) fg=0;
	puts(fg? "YES":"NO");
}
signed main() {
	t=read();
	while(t--) solve();
}

F. Equate Multisets

注意到对于一个奇数，如果把它除以 \(2\) 下取整，那么这个奇数将不复存在。换句话说，对于偶数，两个操作是可逆的，对于奇数则是不可逆的。

因此，对于 \(2 \mid a_i\)，将 \(a_i\) 不断除以二使得 \(a_i\) 是个奇数并加入集合。

这样做之后，如果 \(b\) 能够和 \(a\) 完全相同，那么一定也能变成集合内的数。

对于 \(b_i\)，如果 \(b_i\) 不在集合中，那么不断将 \(b_i\) 除以 \(2\) 下取整，如果直到 \(b_i = 0\) 时仍然没有在集合中出现过，那么就无解。否则有解。

正确性显然。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=2e5+5;
int t, n, a[N], b[N];
multiset<int> st;
void solve() {
	n=read();
	st.clear();
	for(int i=1;i<=n;++i) {
		a[i]=read();
		while(a[i]%2==0) a[i]/=2;
		st.insert(a[i]);
	}
	for(int i=1;i<=n;++i) b[i]=read();
	for(int i=1;i<=n;++i) {
		while(b[i]&&!st.count(b[i])) b[i]/=2;
		if(!b[i]) { puts("NO"); return; }
		else st.erase(st.find(b[i]));
	}
	puts("YES");
}
signed main() {
	t=read();
	while(t--) solve();
}

G. Passable Paths

CF 题面给的图都挺好用的（

对于一个集合 \(p\)，如果能够满足条件，那么将 \(p\) 按照深度排序之后，所有节点一定依次分布在一条简单路径上。

先考虑一条深度单调减的链，举个例子 \(\{5,4,2,1\}\)，它满足深度最大的节点 \(5\) 和其他任何一个节点 \(p_i\) 的 \(lca\) 为 \(p_i\)。

然后是深度不单调减的链，举个例子 \(\{ 5,4,2,3\}\)。

一个想法是找到直径的两端，然后拆成两条链，满足深度单调，分别判断即可，例中为判断 \(\{5,4\}\) 和 \(\{3,2\}\)。 具体做法见代码。

有一种特殊情况，\(lca\) 的父亲节点也在其中，那么这个做法就会 fAKe 掉。一种简单的办法就是判断一下直径两端 \(lca\) 的深度是否小于等于深度最小的节点的深度。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=2e5+5;
int n, q, p[N], dep[N], f[N][19];
int tot, h[N], to[N<<1], nxt[N<<1];
void add(int x,int y) {
	to[++tot]=y, nxt[tot]=h[x], h[x]=tot;
}
void addedge(int x,int y) {
	add(x,y), add(y,x);
}
void dfs(int x,int fa) {
	dep[x]=dep[fa]+1;
	f[x][0]=fa;
	for(int i=1;i<=18;++i) f[x][i]=f[f[x][i-1]][i-1];
	for(int i=h[x];i;i=nxt[i]) {
		int y=to[i];
		if(y==fa) continue;
		dfs(y,x);
	}
}
int lca(int x,int y) {
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=18;~i;--i) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=18;~i;--i) if(f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];
	return f[x][0];
}
bool cmp(int x,int y) { return dep[x]>dep[y]; }
signed main() {
	n=read();
	for(int i=1;i<n;++i) {
		int x=read(), y=read();
		addedge(x,y);
	}
	dfs(1,0);
	q=read();
	while(q--) {
		int m=read();
		for(int i=1;i<=m;++i) p[i]=read();
		sort(p+1,p+m+1,cmp);
		int pos=1;
		vector<bool> s(m+5);
		s[1]=1;
		for(int i=1;i<=m;++i)
			if(lca(p[1],p[i])==p[i]) s[i]=1;
        // 满足这个条件，说明p[i]和p[1]在一条链上
		while(pos<=m&&s[pos]) ++pos;
        // 为什么出现了lca(p[1],p[i])!=p[i]? 因为到了另一条链上了
        // 由于深度已经排序，pos就是另一个端点
		if(pos==m+1) { puts("YES"); continue; }
        // 如果pos==m+1，说明深度单调
		s[pos]=1;
		for(int i=pos+1;i<=m;++i)
			if(lca(p[pos],p[i])==p[i]) s[i]=1;
        // 从另一个端点开始判断
		int ans=1;
		for(int i=1;i<=m;++i) ans&=s[i];
		ans&=dep[lca(p[1],p[pos])]<=dep[p[m]];
        // 特判
		if(ans) puts("YES"); else puts("NO");
	}
}