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