526互联

【刷题日记】其二

发布时间 2023-10-31 10:39:11作者: 史上最速败犬

2023.10.30 星期一

晚上有场div.2，刷刷思维题

17：21 R1400 思维 T00：25：41

https://codeforces.com/problemset/problem/1605/C
最后还是看题解了，自己做一直WA2，原来少了一种情况
反正就是最少的时候，只有两个a相邻和三个a相邻的情况，都枚举一遍就行

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;

int n;
string s;
void solve() {
	cin >> n >> s;
	s = ' ' + s;

	int ans = inf;
	int cnta, cntb, cntc;
	int l = 1;
	while (l < n) {//判断2个a
		if (s[l] == 'a') {
			cntb = cntc = 0;
			forn(i, l + 1, n) {
				if (s[i] == 'b') cntb++;
				if (s[i] == 'c') cntc++;
				if (s[i] == 'a') {
					if (cntb <= 1 && cntc <= 1) ans = min(ans, i - l + 1);
					break;
				}
			}
		}
		l++;
	}
	l = 1;
	while (l < n) {//判断3个a
		if (s[l] == 'a') {
			cnta = cntb = cntc = 0;
			forn(i, l + 1, n) {
				if (s[i] == 'b') cntb++;
				if (s[i] == 'c') cntc++;
				if (s[i] == 'a') cnta++;
				if (cnta == 2) {
					if (cntb <= 2 && cntc <= 2) ans = min(ans, i - l + 1);
					break;
				}
			}
		}
		l++;
	}

	if (ans == inf) ans = -1;
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	// T=1;

	while (T--) {
		solve();
	}

	return 0;
}

18:15 R1400 思维 二进制 构造 T00：10：17

https://codeforces.com/problemset/problem/1095/C
这题挺简单的，直接贪，有两种情况肯定构造不出来
那么其他情况就可以，用一个队列存二进制数，如果总是小于k，就找一个不是1的拆开，直到总数为k

代码 
// Problem: Powers Of Two
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1095C
// Memory Limit: 250 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;

ll n, k;
int bit[100];
int cnt;
void solve() {
	cin >> n >> k;

	int res = n;
	while (res > 0) {
		bit[++cnt] = res % 2;
		res /= 2;
	}
	int cnt1 = 0;
	forn(i, 1, cnt) if (bit[i] == 1) cnt1++;
	if (n < k || cnt1 > k) {
		cn;
		return;
	}
	cy;
	queue<int> q;
	ll x = 1;
	forn(i, 1, cnt) {
		if (bit[i] == 1) q.push(x);
		x *= 2;
	}
	while (q.size() < k) {
		x = q.front();
		q.pop();
		if (x != 1) {
			q.push(x / 2);
			q.push(x / 2);
		} else
			q.push(x);
	}

	while (!q.empty()) cout << q.front() << ' ', q.pop();
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	T = 1;

	while (T--) {
		solve();
	}

	return 0;
}

18：27 R1400 思维（妙） T00：07：57

https://codeforces.com/problemset/problem/1380/B
我直接贪，因为每一种都有可能，也就是说，对于我出的第i个，对战序列中的每一个，我只需要求出哪一种赢的最多，然后我每个都出这个就行了
（第一次忘了把计数清0了，白WA了一次）

代码 
// Problem: Universal Solution
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1380B
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;

int n;
string s;
void solve() {
	cin >> s;
	n = s.size();
	s = ' ' + s;

	int res, ma = 0;
	char x;
	res = 0;
	forn(i, 1, n) {
		if (s[i] == 'R') res++;
	}
	if (res > ma) {
		ma = res;
		x = 'P';
	}
	res = 0;
	forn(i, 1, n) {
		if (s[i] == 'S') res++;
	}
	if (res > ma) {
		ma = res;
		x = 'R';
	}
	res = 0;
	forn(i, 1, n) {
		if (s[i] == 'P') res++;
	}
	if (res > ma) {
		ma = res;
		x = 'S';
	}
	forn(i, 1, n) cout << x;
	cout << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	// T=1;

	while (T--) {
		solve();
	}

	return 0;
}

18：37 R1400 贪心 （byd蓝桥杯又出cf原题）

https://codeforces.com/problemset/problem/1197/C
https://www.lanqiao.cn/problems/5888/learning/?contest_id=145 （蓝桥杯原题）
这题也简单，原数组有序，拆成2段，把所有相邻的差加起来，找到两个相邻差最大的，然后减掉就行，剩下的就最小
同理k段也是，直接把相邻的差排序，然后减去最大的k-1个即可

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 3e5 + 5;
ll T;

ll n, k;
ll h[N];
ll a[N];
void solve() {
	cin >> n >> k;
	forn(i, 1, n) cin >> h[i];

	forn(i, 1, n - 1) a[i] = h[i + 1] - h[i];
	ll ans = 0;
	sort(a + 1, a + n);
	forn(i, 1, n - k) ans += a[i];
	cout << ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//cin >> T;
	T = 1;

	while (T--) {
		solve();
	}

	return 0;
}

19：08 R1400 贪心很简单 模拟细节多（WA了3次） T忘了记

https://codeforces.com/problemset/problem/363/C
贪心就是，先删连续3个及以上的
然后再判断是不是s[i - 1] == s[i] && s[i - 2] == s[i - 3] （注意可能字符串长度没有4，得特判下）

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;

string s, res;
void solve() {
	cin >> s;
	int n = s.size();
	s = ' ' + s;
	char l1, l2;
	res = s.substr(1, min(2, (int) s.size()));//注意长度可能都没有2，下面同理
	forn(i, 3, n) {//先删三个及以上连一起的
		l1 = s[i - 1], l2 = s[i - 2];
		if (l1 == l2 && l2 == s[i]) continue;
		res += s[i];
	}
	s = res;
	res.clear();

	res = s.substr(0, min(3, (int) s.size()));

	forn(i, 3, s.size() - 1) {//再删这样的
		if (s[i - 1] == s[i] && s[i - 2] == s[i - 3]) {
			s[i] = '?';
			continue;
		}
		res += s[i];
	}

	cout << res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	T = 1;

	while (T--) {
		solve();
	}

	return 0;
}

19：24 R1400 思维 T00：07：50

https://codeforces.com/problemset/problem/1251/B
一眼跟0和1的数量有关，而且还跟字符串长度有关
因为回文，如果长度为奇数就--，因为中间是什么斗无所谓
然后1和0的个数用到的肯定也是偶数，是奇数就--，保证构造时一定消耗偶数个
然后就是贪心，肯定先从长度小的开始构造，排序即可

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e3 + 5;
ll T;

int n;
string s[N];
int len[N];//字符串长度
int c0, c1;//0，1个数
void solve() {
	c0 = c1 = 0;
	cin >> n;
	forn(i, 1, n) {
		cin >> s[i];
		len[i] = s[i].size();
		if (len[i] % 2 == 1) len[i]--;
		for (auto j : s[i]) {
			if (j == '0') c0++;
			else
				c1++;
		}
	}

	if (c0 % 2 == 1) c0--;
	if (c1 % 2 == 1) c1--;
	int ans = 0;
	sort(len + 1, len + n + 1);
	forn(i, 1, n) {
		if (c0 >= len[i]) ans++, c0 -= len[i];
		else if (c1 >= len[i])
			ans++, c1 -= len[i];
		else {
			if (c0 + c1 >= len[i]) {
				len[i] -= c0;
				c0 = 0;
				c1 -= len[i];
				ans++;
			}
		}
	}

	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	// T=1;

	while (T--) {
		solve();
	}

	return 0;
}

19:39 R1400 思维 T00：09：41

https://codeforces.com/problemset/problem/1110/B
太水了
先假设只能贴一段，那么长度就是啊a[n]-a[1]+1,能再贴一段，相当于把这一整段切除一部分，变成两段胶带，直接找相差最大的就行了，推广到k段同理，相邻的距离都求出来，排序即可

代码 
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define ll long long
#define forn(i, l, r) for (int i = l; i <= r; i++)
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define debug(a) cout << #a << "=" << a << endl;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 5;
ll T;

ll n, m, k;
ll ans;
ll a[N], b[N];
void solve() {
	cin >> n >> m >> k;
	forn(i, 1, n) cin >> a[i], b[i] = a[i] - a[i - 1] - 1;

	ans = a[n] - a[1] + 1;
	sort(b + 2, b + n + 1);
	int cnt = n;
	forn(i, 1, min(n - 1, k - 1)) ans -= b[cnt--];

	cout << ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	T = 1;

	while (T--) {
		solve();
	}

	return 0;
}