Educational Codeforces Round 88

比赛链接 / 官方题解链接

A. Berland Poker

Solution

如果 jokers 数量小于等于手牌数量，就把所有 jokers 揽入自己手中；否则，剩余的 jokers 平摊给其他人。

Code

#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, n, m, k;

int main(){
	for(read(T); T; T--){
		read(n, m, k);
		if(m <= n / k)	printf("%d\n", m);
		else{
			m -= n / k;
			int d = m / (k - 1);
			if(m % (k - 1))	d++;
			printf("%d\n", n / k - d);
		}
	}
	return 0;
}

---

B. New Theatre Square

Solution

对每一行单独计算，令 $y=\min\{y, 2x\}$，然后优先放 $1\times2$ 的瓷砖。

Code

#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, y, n, m;
char s[1005];

int main(){
	for(read(T); T; T--){
		read(n, m, x, y);
		if(y > 2 * x)	y = 2 * x;
		LL ans = 0;
		for(int i = 1; i <= n; i++){
			scanf("%s", s+1);
			for(int j = 1; j <= m; j++){
				if(s[j] == '.'){
					if(j < m && s[j+1] == '.'){
						ans += y;
						j++;
					}
					else	ans += x;
				}
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

---

C. Mixing Water

Solution

温度变化为：$h,\frac{h+c}{2},\frac{2h+c}{3},\frac{h+c}{2},\frac{3h+2c}{5},\frac{h+c}{2},\cdots$ 偶数项均为 $\frac{h+c}{2}$，奇数（第 $2k-1$）项为 $\frac{kh+(k-1)c}{2k-1}$.

由于所有温度均大于等于 $\frac{h+c}{2}$，所以如果 $t\leq\frac{h+c}{2}$，那么答案就是 $2$；否则，我们在奇数项中寻找最接近答案的一项。

设第 $k$ 项温度正好是 $t$，那么 $\frac{kh+(k-1)c}{2k-1}=t$，化简得：$k=\frac{t-c}{2t-h-c}$. 由于实际上不会正好等于，我们比较一下 $k-1,k,k+1$ 就好。

Code

#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;
LL c, h, t;

inline double tem(LL k){
	return (double)(k * h + (k-1) * c) / (2*k-1);
}

int main(){
	for(read(T); T; T--){
		read(h, c, t);
		if(t <= 0.5 * (h + c)){
			puts("2");
			continue;
		}
		LL k = (t - c) / (2 * t - h - c);
		LL ans = 2; double mn = t - 0.5 * (h + c);
		if(fabs(tem(k) - t) < mn){
			mn = fabs(tem(k) - t);
			ans = 2 * k - 1;
		}
		k--;
		if(fabs(tem(k) - t) < mn){
			mn = fabs(tem(k) - t);
			ans = 2 * k - 1;
		}
		k += 2;
		if(fabs(tem(k) - t) < mn){
			mn = fabs(tem(k) - t);
			ans = 2 * k - 1;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

---

D. Yet Another Yet Another Task

Solution

注意到 $-30\leq a_i\leq30$ 范围很小，所以枚举最大值 $mx$，然后 $dp$ 寻找最大子段和，且子段中最大值不大于 $mx$.

设 $dp[i]$ 表示以 $a[i]$ 结尾的最大子段和（$a[i]$ 必选），并且要满足这个子段中最大值不大于 $mx$；设 $st[i]$ 表示这个最大子段和的起始位置，那么容易有 $dp$ 方程：$dp[i]=\begin{cases}-INF,&a[i]>mx\\dp[i-1]+a[i],&a[i]\leq mx\and dp[i-1]\geq0\\a[i],&a[i]\leq mx\and dp[i-1]<0\end{cases}$，对应有 $st[i]=\begin{cases}无,&a[i]>mx\\st[i-1],&a[i]\leq mx\and dp[i-1]\geq0\\i,&a[i]\leq mx\and dp[i-1]<0\end{cases}$. 如果 $[i,st[i]]$ 中包含了 $mx$，就用 $dp[i]-mx$ 去更新答案。

Code

#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;

int n, a[N], cnt[N][100], ans = -1e9;

int main(){
	read(n);
	for(int i = 1; i <= n; i++){
		read(a[i]);
		for(int j = -30; j <= 30; j++)
			cnt[i][j+30] = cnt[i-1][j+30];
		cnt[i][a[i]+30]++;
	}
	for(int mx = -30; mx <= 30; mx++){
		vi dp(n+5, -1e9), st(n+5, 0);
		for(int i = 1; i <= n; i++){
			if(a[i] > mx)	continue;
			if(dp[i-1] < 0){
				dp[i] = a[i];
				st[i] = i;
			}
			else{
				dp[i] = a[i] + dp[i-1];
				st[i] = st[i-1];
			}
		}
		for(int i = 1; i <= n; i++){
			if(dp[i] == -1e9)	continue;
			if(cnt[i][mx+30] - cnt[st[i]-1][mx+30] > 0)
				ans = max(ans, dp[i] - mx);
		}
	}
	printf("%d\n", ans);
	return 0;
}

---

E. Modular Stability

Solution

假设我们选取 $x=a_k$，那么取第一个模数为 $a_k$，可以知道答案应为 $0$；此时，若取第一个模数为 $a_1$，那么有：$a_k\bmod a_1=0$，也即 $a_k$ 是 $a_1$ 倍数；同理我们可以证明：$a_2,a_3,\cdots,a_k$ 均是 $a_1$ 的倍数。

至于有没有其他条件约束，我在比赛时没有去证明了（因为可以从样例中得到验证）。

所以我们枚举 $a_1$ 的取值，得到 $[1,n]$ 中 $a_1$ 的倍数的个数，设为 $m$，那么从这 $m-1$ 个数（剔除 $a_1$ 本身）选取 $k-1$ 个数作为 $a_2,a_3,\cdots,a_k$ 即可，所以共有 $C_{m-1}^{k-1}$ 中选法。

Code

#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 LL MOD = 998244353;
const int N = 500005;

LL n, k, ans, fact[N], invfact[N];

inline LL fpow(LL bs, LL idx){
	LL res = 1;
	bs %= MOD;
	while(idx){
		if(idx & 1)	(res *= bs) %= MOD;
		(bs *= bs) %= MOD;
		idx >>= 1;
	}
	return res;
}

inline LL C(LL m, LL r){
	return fact[m] * invfact[r] % MOD * invfact[m-r] % MOD;
}

int main(){
	fact[0] = 1, invfact[0] = 1;
	for(int i = 1; i <= 500000; i++){
		fact[i] = i * fact[i-1] % MOD;
		invfact[i] = fpow(fact[i], MOD - 2);
	}
	read(n, k);
	if(n < k)	return puts("0");
	for(LL i = 1; i <= n; i++){
		LL cnt = n / i;
		if(cnt < k)	break;
		(ans += C(cnt - 1, k - 1)) %= MOD;
	}
	printf("%lld\n", ans);
	return 0;
}

---