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 2*n + 1 2∗n+1的规律递增 用预处理好的 s u m sum sum数组判断是否符合条件即可

代码

#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 res *= 1 - p res∗=1−p

最终答案为 r e s = 1 − r e s res = 1 - res res=1−res

代码

#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 mid == (max(a[1,2,3,.....]) + min(1,2,3,.....) ) / 2 mid==(max(a[1,2,3,.....])+min(1,2,3,.....))/2

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

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

然后给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 k k 升水 每天消耗 x x x 升 可以加 y y y 升 问是否可以在 t t t 天内 保持在 [ l , r ] [l,r] [l,r] 的范围内

思路

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

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

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

​ 可以分为三种情况：

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

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

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

②： x < = y 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;
}