Codeforces Round 635 (Div.2)

比赛链接 / 官方题解链接

A. Ichihime and Triangle

Solution

用 $b,c,c$ 一定能构成三角形。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int T, a, b, c, d;

int main(){
	for(read(T); T; T--){
		read(a, b, c, d);
		printf("%d %d %d\n", b, c, c);
	}
	return 0;
}

---

B. Kana and Dragon Quest game

Solution

能用第一种操作就用第一种操作，否则用第二种操作。因为如果对于一个数，用第一种操作不能使之减小，那么对于小于它的数，用第一种操作更不可能使之减小。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int T, x, n, m;

int main(){
	for(read(T); T; T--){
		read(x, n, m);
		while(n--){
			if(x / 2 + 10 < x)
				x = x / 2 + 10;
			else	break;
		}
		x -= 10 * m;
		puts(x > 0 ? "NO" : "YES");
	}
	return 0;
}

---

C. Linova and Kingdom

Solution

首先观察出一个结论：如果一个点被选了，那么它的子树所有点一定都会被选，否则的话，选子树中的点显然比选它更优。

于是乎，如果我们现在选了点 $x$，那么答案加上 $dep[x]-(sz[x]-1)$，其中 $dep[x]$ 表示 $x$ 的深度，$sz[x]$ 表示 $x$ 子树大小。所以要使答案最大，把所有点按照 $dep[x]-(sz[x]-1)$ 降序排序即可。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200005;

int n, k;
LL ans;

struct Edge{
	int nxt, to;
}edge[N<<1];
int head[N], edgeNum;
void addEdge(int from, int to){
	edge[++edgeNum] = (Edge){head[from], to};
	head[from] = edgeNum;
}

struct Node{
	LL dep, sz;
	bool operator < (const Node &A) const{
		return dep - sz + 1 > A.dep - A.sz + 1;
	}
}a[N];

void dfs(int x, int f, LL depth){
	a[x].dep = depth;
	a[x].sz = 1;
	for(int i = head[x]; i; i = edge[i].nxt){
		if(edge[i].to == f)	continue;
		dfs(edge[i].to, x, depth+1);
		a[x].sz += a[edge[i].to].sz;
	}
}

int main(){
	read(n, k);
	for(int i = 1; i < n; i++){
		int u, v; read(u, v);
		addEdge(u, v);
		addEdge(v, u);
	}
	dfs(1, 0, 0);
	sort(a+1, a+n+1);
	for(int i = 1; i <= k; i++)
		ans += a[i].dep - a[i].sz + 1;
	printf("%lld\n", ans);
	return 0;
}

---

D. Xenia and Colorful Gems

Solution

固定 $z$，二分找到 $z$ 的左右最近的 $x,y$，更新答案。

根据 $x,y,z$ 的轮换对称性，做 $3$ 次上述过程。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

LL ans;
inline void solve(LL x[], LL y[], LL z[], int nx, int ny, int nz){
	for(int k = 1; k < nz; k++){
		vector<LL> X, Y;
		int j = lower_bound(y+1, y+ny+1, z[k]) - y;
		if(j > 1)	Y.pb(y[j-1]);
		if(j < ny)	Y.pb(y[j]);
		int i = lower_bound(x+1, x+nx+1, z[k]) - x;
		if(i > 1)	X.pb(x[i-1]);
		if(i < nx)	X.pb(x[i]);
		for(auto xx: X)
			for(auto yy: Y)
				ans = min(ans, (xx-yy)*(xx-yy) + (yy-z[k])*(yy-z[k]) + (z[k]-xx)*(z[k]-xx));
	}
}

int T, nx, ny, nz;
LL x[N], y[N], z[N];

int main(){
	for(read(T); T; T--){
		read(nx, ny, nz);
		ans = 2e18;
		for(int i = 1; i <= nx; i++)	read(x[i]);
		for(int i = 1; i <= ny; i++)	read(y[i]);
		for(int i = 1; i <= nz; i++)	read(z[i]);
		sort(x+1, x+nx+1); nx = unique(x+1, x+nx+1) - (x+1);
		sort(y+1, y+ny+1); ny = unique(y+1, y+ny+1) - (y+1);
		sort(z+1, z+nz+1); nz = unique(z+1, z+nz+1) - (z+1);
		x[++nx] = 1e16, y[++ny] = 1e16, z[++nz] = 1e16;
		solve(x, y, z, nx, ny, nz);
		solve(y, z, x, ny, nz, nx);
		solve(z, x, y, nz, nx, ny);
		printf("%lld\n", ans);
	}
	return 0;
}

---

E. Kaavi and Magic Spell

Solution

区间 $dp$.

设 $dp[i][j]$ 表示用 $s[1…j-i+1]$ 匹配了 $t[i…j]$ 这一段字符的方案数，其中，超过 $m$ 的部分任意字符都算作匹配。那么容易写出 $dp$ 方程。

答案就是 $\sum\limits_{i=m}^ndp[1][i]$.

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 3005;
const LL MOD = 998244353;

int n, m, pt;
char s[N], t[N];
LL dp[N][N];

int main(){
	scanf("%s", s+1);
	scanf("%s", t+1);
	n = strlen(s+1), m = strlen(t+1);
	for(int i = 1; i <= n+1; i++)	dp[i][i-1] = 1;
	for(int l = 1; l <= n; l++){
		for(int i = 1; i <= n; i++){
			int j = i + l - 1;
			if(j > n)	break;
			if(s[l] == t[j] || j > m)
				(dp[i][j] += dp[i][j-1]) %= MOD;
			if(s[l] == t[i] || i > m)
				(dp[i][j] += dp[i+1][j]) %= MOD;
		}
	}
	LL ans = 0;
	for(int i = m; i <= n; i++)
		(ans += dp[1][i]) %= MOD;
	printf("%lld\n", ans);
	return 0;
}

---

F. Yui and Mahjong Set

Solution

【参考官方题解】题解讲的挺清楚了，下面仅仅写一写式子罢了。

按照 $n-1,n-2,\cdots,4,3,1,2,1$ 的顺序询问，记录下每次回答的差值 $d_1[i],d_2[i]$，那么：

• 最后一次询问中，$d_1[0]=C_{a_1+1}^2=\cfrac{(a_1+1)a_1}{2}$，

  所以 $a_1=\lfloor\sqrt{d_1[0]\times2}\rfloor$.

• 对于两次询问 $1$，有：$d_2[0]=(a_2+1)(a_3+1),d_2[2]=a_2(a_3+1)$，

  所以 $a_3=d_2[0]-d_2[2]-1,a_2=\cfrac{d_2[2]}{a_3+1}$.

• 对于询问 $2$，有：$d_2[1]=(a_1+1)(a_3+1)+(a_4+1)(a_3+1)$，

  所以 $a_4=\cfrac{d_2[1]-(a_1+1)(a_3+1)}{a_3+1}-1$.

• 对于询问 $i(3\leq i<n-2)$，有：$d_2[i]=a_{i-1}(a_{i+1}+1)+(a_{i+1}+1)(a_{i+2}+1)+a_{i-2}a_{i-1}$，

  所以 $a_{i+2}=\cfrac{d_2[i]-a_{i-1}(a_{i+1}+1)-a_{i-2}a_{i-1}}{a_{i+1}+1}-1$.

• 对于询问 $n-2$，有：$d_2[n-2]=a_{n-3}(a_{n-1}+1)+(a_{n-1}+1)a_n+a_{n-4}a_{n-3}$，

  所以 $a_n=\cfrac{d_2[n-2]-a_{n-3}(a_{n-1}+1)-a_{n-4}a_{n-3}}{a_{n-1}+1}$.

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int n, a[105];
int s1[105], s2[105], d1[105], d2[105];

int main(){
	read(n, s1[0], s2[0]);
	for(int i = n - 1; i >= 0; i--){
		if(i <= 2)	printf("+ %d\n", i % 2 ? 2 : 1);
		else		printf("+ %d\n", i);
		fflush(stdout);
		read(s1[i], s2[i]);
		d1[i] = s1[i] - s1[i+1];
		d2[i] = s2[i] - s2[i+1];
	}
	a[1] = sqrt(2 * d1[0]);
	a[3] = d2[0] - d2[2] - 1;
	a[2] = d2[2] / (a[3] + 1);
	a[4] = (d2[1] - (a[3] + 1) * (a[1] + 1)) / (a[3] + 1) - 1;
	for(int i = 3; i <= n - 2; i++)
		a[i+2] = (d2[i] - a[i-2] * a[i-1] - a[i-1] * (a[i+1] + 1)) / (a[i+1] + 1) - 1;
	a[n]++;
	printf("! ");
	for(int i = 1; i <= n; i++)	printf("%d ", a[i]);
	puts("");
	fflush(stdout);
	return 0;
}