2020.5.28 Educational Codeforces Round 88 比赛记录

比赛链接

A Berland Poker

简单题

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 0x3f3f3f3f;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == ‘-‘) flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
int main(){
	int T = read();
	int n,m,k,t;
	while (T--){
		n = read(); m = read(); k = read();
		t = n / k;
		if (m <= t) printf("%d\n",m);
		else {
			int ans = t - (int)ceil(1.0 * (m - t) / (k - 1));
			printf("%d\n",ans);
		}
	}
	return 0;
}

B New Theatre Square

简单dp题

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 0x3f3f3f3f;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == ‘-‘) flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
int n,m,x,y,f[maxn],v[maxn],ans;
int main(){
	int T = read();
	while (T--){
		n = read(); m = read(); x = read(); y = read(); ans = 0;
		for (int i = 1; i <= n; i++){
			char c = getchar();
			f[0] = 0;
			for (int j = 1; j <= m; j++){
				while (c != ‘.‘ && c != ‘*‘) c = getchar();
				v[j] = c == ‘.‘ ? 0 : 1;
				if (c == ‘*‘) f[j] = f[j - 1];
				else {
					f[j] = f[j - 1] + x;
					if (j > 1 && !v[j - 1]) f[j] = min(f[j],f[j - 2] + y);
				}
				c = getchar();
			}
			ans += f[m];
		}
		printf("%d\n",ans);
	}
	return 0;
}

C Mixing Water

执行一个流程，在一个无限大的容器中，先倒一杯\(h\)度的热水，再倒一杯\(c\)度冷水水，如此循环，某个时刻容器内水的温度为已倒过的水温的平均值，给定一个温度\(T\)结语\(c\)和\(h\)之间，问第几次倒后第一次最接近这个温度。
由于先倒热水，所以温度适中是大于等于\(\frac{h+c}{2}\)的，如果\(T\)小于这个温度，则第二次温差最小。否则肯定是在某次倒热水后最接近，可以列式\(\frac{(n+1)h+nc}{2n+1}=T\)，其中\(2n+1\)为倒的次数，解出\(n\)，由于\(n\)是整数，在\(n\)上下测试一下找出最值即可。

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 0x3f3f3f3f;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == ‘-‘) flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
int h,c,t;
int main(){
	int T = read();
	while (T--){
		h = read(); c = read(); t = read();
		if (2 * t <= h + c) puts("2");
		else {
			int n = (h - t) / (2 * t - h - c);
			double a = (1.0 * (n + 1) * h + 1.0 * n * c) / (2 * n + 1);
			double b = (1.0 * (n + 2) * h + 1.0 * (n + 1) * c) / (2 * n + 3);
			if (fabs(a - t) <= fabs(b - t)) printf("%d\n",2 * n + 1);
			else printf("%d\n",2 * (n + 1) + 1);
		}
	}
	return 0;
}

D Yet Another Yet Another Task

求最大的区间和减去区间最大值。权值范围\([-30,30]\)
注意到权值范围很小，可以枚举最大值，然后所有值大于这个值的点视作不可取，然后就是简单的最大区间和问题

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 0x3f3f3f3f;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == ‘-‘) flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
int f[maxn],ans,n,a[maxn];
int main(){
	n = read();
	REP(i,n) a[i] = read();
	for (int k = 0; k <= 30; k++){
		for (int i = 1; i <= n; i++){
			if (a[i] > k) f[i] = 0;
			else f[i] = max(a[i],f[i - 1] + a[i]);
			ans = max(ans,f[i] - k);
		}
	}
	printf("%d\n",ans);
	return 0;
}

E Modular stability

求\([1,n]\)中取出\(m\)个互异的数，这些数组成的集合取模稳定，有多少种取法。
其中取模稳定定义为对任意非负数\(x\)，分别对这些数取模，无论如何改变取模顺序，取模结果不变。
经过分析注意到取模稳定当且仅当有一个数是所有其它数的约数。
所以枚举那个约数，就是一个组合数问题了。

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 500005,maxm = 100005,INF = 0x3f3f3f3f,P = 998244353;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == ‘-‘) flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
int fac[maxn],inv[maxn],fv[maxn],n,k;
void init(){
	fac[0] = 1;
	for (int i = 1; i <= 500000; i++) fac[i] = 1ll * fac[i - 1] * i % P;
	inv[0] = inv[1] = 1;
	for (int i = 2; i <= 500000; i++) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
	fv[0] = 1;
	for (int i = 1; i <= 500000; i++) fv[i] = 1ll * fv[i - 1] * inv[i] % P;
}
void work(){
	if (n < k) puts("0");
	else if (k == 1) printf("%d\n",n);
	else {
		int ans = 0;
		for (int i = 1; n / i >= k; i++){
			ans = (ans + 1ll * fac[n / i - 1] * fv[n / i - k] % P * fv[k - 1] % P) % P;
		}
		printf("%d\n",ans);
	}
}
int main(){
	n = read(); k = read();
	init();
	work();
	return 0;
}

2020.5.28 Educational Codeforces Round 88 比赛记录

原文：https://www.cnblogs.com/Mychael/p/12989723.html