Codeforces Round #689 Div. 2 （A-E）

A. String Generation

题意

构造一个只包含’a’ ‘b’ 'c’的字符串此字符串中最大回文子串的长度不超过k

思路

'abcabcabc…'这样输出可以保证最大的回文子串的长度为1

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100010;


void solve() {
   
	int n, k; cin >> n >> k;
	
	for (int i = 0; i < n; ++i) {
   
		if (i % 3 == 0)printf("a");
		else if (i % 3 == 1)printf("b");
		else printf("c");
	}

	cout << endl;
}
int main() {
   
	int t; cin >> t;
	while (t--)
		solve();

}

B. Find the Spruce

题意

在图中找出符合条件的”松树“的个数

思路

先预处理每一行中连续的**‘’的个数然后遍历这个图每找到一个‘’**就判断能否构成两层或更多层的松树

每层的**‘*’**以 $2 * n + 1$ 的规律递增用预处理好的 $s u m$ 数组判断是否符合条件即可

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
typedef long long LL;
typedef pair<int, int>PII;
const int N = 600;

int n, m;
char s[N][N];
int sum[N][N];

void solve() {
   

	memset(sum, 0, sizeof sum);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i)cin >> s[i] + 1;

	for (int i = 1; i <= n; ++i) {
    //预处理前缀和
		for (int j = 1; j <= m; ++j) {
   
			if (s[i][j] == '*')
				sum[i][j] = sum[i][j - 1] + 1;
			else sum[i][j] = 0;
		}
	}

	int res = 0;
	for (int i = 1; i <= n; ++i) {
   
		for (int j = 1; j <= m; ++j) {
   
			if (s[i][j] == '*') {
   
				res++;

				for (int k = 1; i + k <= n; ++k) {
   
					if ((j - k - 1 >= 0) && (j + k <= m) && (sum[i + k][j + k] - sum[i + k][j - k - 1] == 2 * k + 1))
						res++;
					else break;
				}
			}
		}
	}

	cout << res << endl;

	
}
int main() {
   
	int t; cin >> t;
	while (t--)
		solve();


	return 0;
}

C. Random Events

题意

给你一个长度为 n 的排列和 m个操作每个操作包括 r 和 p 表示前 r 个数有 p 的概率排好序（递增）

计算这个排列最终变成递增的概率为多少

思路

先找到未按递增顺序排列的最大位置 pos

题目要求求出能按序排列的概率考虑其反面对于位置大于等于pos的操作先求不能按序排列的概率即 $r e s * = 1 - p$

最终答案为 $r e s = 1 - r e s$

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
typedef long long LL;
typedef pair<int, int>PII;
const int N = 100010;

int n, m;
int a[N];
pair<int, double>p[N];
void solve() {
   
	cin >> n >> m;

	for (int i = 1; i <= n; ++i) {
   
		cin >> a[i];
	}

	int pos = 0;
	for (int i = 1; i <= n; ++i) {
   
		if (a[i] != i)
			pos = i;
	}

	for (int i = 0; i < m; ++i) {
   
		cin >> p[i].first >> p[i].second;
	}

	sort(p, p + m);
	if (pos == 0)puts("1.000000");
	else {
   
		double res = 1.0;
		for (int i = 0; i < m; ++i) {
   
			if (p[i].first >= pos)
				res *= 1 - p[i].second;
		}

		res = 1 - res;

		printf("%.6lf\n", res);
	}
	
}
int main() {
   
	int t; cin >> t;
	while (t--)
		solve();


	return 0;
}

D. Divide and Summarize

题意

$m i d = = (m a x (a [1, 2, 3, . . . . .]) + m i n (1, 2, 3, . . . . .)) / 2$

将一个数组按 $m i d$ 分成左右两部分左边是所有不大于 $m i d$ 的数右边是所有大于 $m i d$ 的数

然后选择其中一部分代替原数组继续进行这种操作

然后给q个询问判断在这个过程中数组所有元素之和是否能够等于给出的数

思路

将所有可能出现的值存起来然后查表即可

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
typedef long long LL;
typedef pair<int, int>PII;
const int N = 100010;

int n, q;
LL a[N];
LL sum[N];
set<LL>S;


void solve2(int l,int r) {
   
	if (l > r)return;

	LL mid = (a[r] + a[l]) / 2;
	S.insert(sum[r] - sum[l - 1]);

	int t1 = lower_bound(a + l, a + r + 1, mid) - a;
	int t2 = upper_bound(a + l, a + r + 1, mid) - a;

	if (t2 > r || l == r)return;

	solve2(l, t2 - 1);
	solve2(t2, r);

}
void solve() {
   
	cin >> n >> q;
	S.clear();

	for (int i = 1; i <= n; ++i) {
   
		scanf("%d", &a[i]);
	}
	sort(a + 1, a + n + 1);
	
	for (int i = 1; i <= n; ++i)
		sum[i] = sum[i - 1] + a[i];

	solve2(1, n);


	while (q--) {
   
		int x; cin >> x;
		if (S.count(x))puts("YES");
		else puts("NO");
	}


}
int main() {
   
	int t; cin >> t;
	while (t--)
		solve();


	return 0;
}

E. Water Level

题意

一个水桶最初有 $k$ 升水每天消耗 $x$ 升可以加 $y$ 升问是否可以在 $t$ 天内保持在 $[l, r]$ 的范围内

思路

首先 $k - = x$ $r - = x$ 对答案无影响

然后对 $x$ 进行分类讨论：

①： $x > y$ 时每天的水都是在减少的

可以分为三种情况：

1.第一天加水 $y$ 会超过范围并且消耗 $x$ 后也超过范围这种无解

3.第一天不能加水，除第一天外之后的每一天消耗都是 $x - y$

3.第一天能加水，每一天消耗的都是 $x - y$

②： $x < = y$ 每天加水水会变多

使水桶中的水尽可能少必要的时候再加水

判断刚开始时，桶里的水能用几天

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
typedef long long LL;
typedef pair<int, int>PII;
const int N = 100010;

LL k, l, r, t, x, y;
set<LL>S;
bool solve() {
   
	k -= l;
	r -= l;

	if (x > y) {
   
		LL c = 0;
		if (k + y > r && k - x < l)return false;

		else if (k + y > r) c = 1 + (k - x) / (x - y);
		else c = k / (x - y);

		return c >= t;
	}
	else {
    //y >= x 每次加水 水会变多
		//使得水桶中的水尽可能少 必要的时候再加水
		// 判断刚开始时 水桶里的水能用几天
		LL c = k / x;
		k -= c * x;
		t -= c;
		S.insert(k);
		while (t > 0) {
   
			if (k + y > r)return false;

			t -= (k + y) / x;
			k = (k + y) % x;

			if (S.count(k))return true;
		}
		return true;
	}

}
int main() {
   
	cin >> k >> l >> r >> t >> x >> y;
	if (solve())puts("YES");
	else puts("NO");


	return 0;
}