CF1714.

最近摸得有点厉害，主要是被自己菜到了，心态有点差……

老年人也就看看 Div 3 了。

A. Everyone Loves to Sleep

转化成分钟乱搞即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t, n, H, M, D, ans, h[15], m[15], d[15];
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(), H=read(), M=read();
	D=H*60+M;
	ans=1<<30;
	for(int i=1;i<=n;++i) {
		h[i]=read(), m[i]=read();
		d[i]=h[i]*60+m[i];
		if(d[i]<D) d[i]+=24*60;
	}
	for(int i=1;i<=n;++i) ans=min(ans,d[i]-D);
	printf("%lld %lld\n",ans/60,ans%60);
}
signed main() {
	t=read();
	while(t--) solve();
}

B. Remove Prefix

从后往前寻找第一个重复数字出现的位置即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int t, n, ans, a[N];
map<int,int> 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() {
	n=read();
	p.clear(), ans=0;
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=n;i;--i) {
		++p[a[i]];
		if(p[a[i]]>1) { ans=i; break; }
	}
	printf("%lld\n",ans);
}
signed main() {
	t=read();
	while(t--) solve();
}

C. Minimum Varied Number

注意到 \(t \in [1,45]\)，说明答案最大就是 \(123456789\)，那么要求数字最小只要贪心从后往前依次放置即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t, n, ans[100];
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();
	memset(ans,0,sizeof(ans));
	for(int i=9;i;--i) if(n>i) {
		n-=i; ans[i]=i;
	} else { ans[i]=n; break; }
	for(int i=1;i<=10;++i) if(ans[i]) printf("%lld",ans[i]);
	puts("");
}
signed main() {
	t=read();
	while(t--) solve();
}

D. Color with Occurrences

注意到颜色是可以覆盖的，所以也可以理解为“无后效性吧”。

那么设 \(f(i)\) 为将 \([1,i]\) 染色用的最小次数，那么对于一个字符串 \(j\) \[ f(i) = \min_{k \in [i-l_j,i-1]}{ \{ f_k + 1} \} \] 其中 \(l_j\) 是 \(j\) 的长度，且必须满足 \(i \ge l_j\) 且 \(t[i-l_j+1,i] = a_j\)。

为啥不把 \(j\) 加入状态呢？复杂度是不会变化的，是冗余信息。

考虑输出方案。一开始我竟然用了一个 SB 二维数组乱搞，结果还真的过了样例和第一个点，但是会 WA #2。仔细一想，输出方案实际上是把 DP 的过程重现一遍，那么输出方案时需要的信息应当与状态相同，但是由于不仅要输出决策点，还要输出所用的字符串编号，所以要用两个数组。我一开始就是把这两个合一了。

设 \(g_1(i)\) 表示决策点，\(g_2(i)\) 表示将 \(i\) 染色用的字符串编号。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=105, M=15;
int t, n, m, f[N], l[M], g1[N], g2[N];
string s, a[M];
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 print(int i) {
    // i表示染色的位置
	if(!i) return;
	print(g1[i]);
    // i的决策点，也就是上一个染色的位置
	printf("%lld %lld\n",g2[i],i-l[g2[i]]+1);
    // 用的字符串编号的染色的位置
}
void solve() {
	memset(f,0x3f,sizeof(f));
	memset(l,0,sizeof(l));
	memset(g1,0,sizeof(g1));
	memset(g2,0,sizeof(g2));
	cin>>s; n=read();
	m=s.length(), s=" "+s;
	for(int i=1;i<=n;++i) cin>>a[i], l[i]=a[i].length();
	f[0]=0;
	for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) if(i>=l[j]) {
		if(s.substr(i-l[j]+1,l[j])==a[j]) {
			int p=m+1;
			for(int k=i-l[j];k<i;++k) if(f[p]>f[k]) p=k;
			if(f[i]>f[p]+1) f[i]=f[p]+1, g1[i]=p, g2[i]=j;
		}
	}
	printf("%lld\n",f[m]<=m? f[m]:-1);
    // 不难发现只要能够全部染色，次数绝不会超过m
	if(f[m]<=m) print(m);
}
signed main() {
	t=read();
	while(t--) solve();
}

E. Add Modulo 10

注意到如果某个数模 \(10\) 为 \(0\)，那么它就不会变化，如果模 \(10\) 为 \(5\)，那么它只会改变一次。

它们可以归为一类——因为它们的终态都能计算出来，姑且称之为 \(\alpha\) 类，其他称之为 \(\beta\) 类。如果既有 \(\alpha\) 类又有 \(\beta\) 类，那么绝对不可能全部相等。

否则如果只有 \(\alpha\) 类，那么直接算出来判断是否全部相等即可。

未经特殊声明，下面的数都是模 \(10\) 之后的结果。

考虑这样一条路径，\(1 \rightarrow 2 \rightarrow 4 \rightarrow 8\)。

\(3 \rightarrow 6 \rightarrow 2\)，\(7 \rightarrow 4\)，\(9 \rightarrow 8\)，这些操作都能让本不属于这条路径的数字加入路径，且最终都会达到 \(8\)，那么可以知道一定能做到让所有的数模 \(10\) 相同，但是一定能全部相等吗？

注意到 \(8\) 和 \(28\)，将 \(8\) 进行变成 \(28\) 需要 \(4\) 次操作，但是根本无法让 \(28\) 变成 \(38\)。这是因为路径中 \(8\) 变成 \(8\) 要进位两次，所以只有个位是 \(8\) 的两个数的差是 \(10\) 的偶数倍才能满足条件。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int t, n, a[N], f1, f2;
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;
}
bool pd(int a,int b) {
	int d=abs(a-b);
	return (d/10)%2;
}
void solve() {
	n=read();
	f1=f2=0;
	for(int i=1;i<=n;++i) {
		a[i]=read();
		if(a[i]%10==0||a[i]%10==5) f1=1;
		else f2=1; 
	}
	if(f1&&f2) { puts("No"); return; }
	else if(f1) {
		for(int i=1;i<=n;++i) {
			if(a[i]%10==5) a[i]+=5;
			if(i>1&&a[i]!=a[i-1]) { puts("No"); return; }
		}
		puts("Yes"); return;
	} else {
		for(int i=1;i<=n;++i) {
			if(a[i]%10==1||a[i]%10==2||a[i]%10==4) {
				a[i]-=a[i]%10, a[i]+=8;
			}
			else if(a[i]%10==3||a[i]%10==6||a[i]%10==7||a[i]%10==9) {
				a[i]-=a[i]%10, a[i]+=18;
			}
			if(i>1&&pd(a[i],a[i-1])) { puts("No"); return; }
		}
		puts("Yes"); return;
	}
}
signed main() {
	t=read();
	while(t--) solve();
}

F. Build a Tree and That Is It

没看，不会。😢

G. Path Prefixes

维护树上前缀和，记为 \(sa\)，\(sb\)。

在一条路径上，找到第一个严格大于 \(sa_x\) 的 \(sb_y\)，那么 \(sa_x\) 一定严格大于之前的每一个 \(sb\)，于是 \(y-1\) 即为答案。\(x\) 与 \(y\) 都是路径上节点的编号。由于 \(sb\) 显然是单调增的，可以二分查找。

在更新更新完 \(x\) 的所有子节点之后还原 \(sa_x\)，\(sb_x\) 即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int t, n,  sa, sb, a[N], b[N], ans[N];
int tot, h[N], to[2*N], nxt[2*N];
vector<int> ssb;
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 add(int x,int y) {
	to[++tot]=y, nxt[tot]=h[x], h[x]=tot;
}
void dfs(int x,int fa) {
	sa+=a[x], sb+=b[x];
	ssb.push_back(sb);
	ans[x]=upper_bound(ssb.begin(),ssb.end(),sa)-ssb.begin()-1;
	for(int i=h[x];i;i=nxt[i]) {
		int y=to[i];
		if(y!=fa) dfs(y,x);
	}
	sa-=a[x], sb-=b[x];
	ssb.pop_back();
}
void solve() {
	n=read();
	tot=sa=sb=0;
	ssb.clear();
	for(int i=1;i<=n;++i) h[i]=0;
	for(int i=2;i<=n;++i) {
		int p=read();
		a[i]=read(), b[i]=read();
		add(p,i), add(i,p);
	}
	dfs(1,0);
	for(int i=2;i<=n;++i) printf("%lld%c",ans[i]," \n"[i==n]);
}
signed main() {
	t=read();
	while(t--) solve();
}