A. Codeforces Checking
网速题，一个字符查看是否在"Codeforces"里包含。
#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("test.in", "r", stdin);
int tt;
cin >> tt;
string s = "codeforces";
while(tt -- )
{
char c;
cin >> c;
bool f = false;
for(auto t : s)
if(c == t) f = true;
cout << (f ? "YES" : "NO") << endl;
}
return 0;
}B. Following Directions
直接暴力实现
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
string str;
int x = 0, y = 0, f = 0;
cin >> n >> str;
for (auto c : str)
{
if (c == 'L') x--;
if (c == 'R') x++;
if (c == 'U') y++;
if (c == 'D') y--;
if (x == 1 && y == 1) f = 1;
}
cout << (f == 1 ? "YES" : "NO") << endl;
}
int main()
{
freopen("test.in", "r", stdin);
int tt;
cin >> tt;
while (tt--)
{
solve();
}
return 0;
}C. Prepend and Append
两种操作，一个前面+1后面+0，另一个前面+0后面+1，现在给定一个最终的串，看初始最短为多长直接暴力循环一下，判断首尾字符
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
string s;
cin >> n >> s;
int cnt = 0;
for(int i = 0, j = n - 1; i < j; i ++ , j -- )
if(s[i] == '0' && s[j] == '1' || s[i] == '1' && s[j] == '0') cnt += 2;
else break;
cout << n - cnt << endl;
}
int main()
{
freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _t = 1;
cin >> _t;
while(_t -- ){
solve();
}
return 0;
}D. Distinct Split
直接枚举断点，然后维护前后两端有几个不同元素，每次更新答案即可
#include <bits/stdc++.h>
using namespace std;
int cnt1[26], cnt2[26];
int l1, l2;
void solve()
{
int n;
string str;
cin >> n >> str;
memset(cnt1, 0, sizeof cnt1);
memset(cnt2, 0, sizeof cnt2);
l1 = l2 = 0;
for (auto c : str)
{
if (cnt2[c - 'a'] == 0)
l2++;
cnt2[c - 'a']++;
}
int maxv = l2;
for (int i = 0; i < n; i++)
{
char c = str[i];
if (cnt2[c - 'a'] == 1)
{
cnt2[c - 'a']--;
l2--;
}
else
cnt2[c - 'a']--;
if (cnt1[c - 'a'] == 0)
{
cnt1[c - 'a']++;
l1++;
}
else
cnt1[c - 'a']++;
// cout << l1 << " " << l2 << endl;
maxv = max(maxv, l1 + l2);
}
cout << maxv << endl;
}
int main()
{
freopen("test.in", "r", stdin);
int tt;
cin >> tt;
while (tt--)
{
solve();
}
return 0;
}E. Negatives and Positives
题意：给一个数组，可以进行操作每次选出两个相邻的数，使它们加负号。这个负号有个性质，可以传递，我们可以把任意两个数变为它们的负数，而使中间的数都不变
故该题需要看数组中有多少个负数，如果是偶数个，直接输出全部元素绝对值的和
如果是奇数个，需要选出一个负数，必然选出绝对值最小的数为负数，所以需要维护一个minv
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve()
{
int n;
cin >> n;
LL ans = 0, cnt = 0;
LL minv = 1e9;
while(n -- )
{
int x;
cin >> x;
ans += abs(x);
if(x < 0) cnt ++ ;
minv = min(minv, (LL)abs(x));
}
if(cnt & 1)
cout << ans - 2 * minv << endl;
else
cout << ans << endl;
}
int main()
{
freopen("test.in", "r", stdin);
int tt;
cin >> tt;
while(tt -- )
{
solve();
}
return 0;
}F. Range Update Point Query
区间修改和单点查询因为每个元素修改的次数是有先的，修改到最终形态后就不在改变
可以使用并查集，把修改好的元素跟右边的元素合并
每次给定L和R，直接找L的祖宗节点X，修改完就修改X+1的祖宗节点，直到超过R
#include<bits/stdc++.h>
using namespace std;
struct DSU
{
vector<int> p, siz;
DSU(int n) : p(n), siz(n, 1) { iota(p.begin(), p.end(), 0); }
int find(int x)
{
while (x != p[x])
x = p[x] = p[p[x]];
return x;
}
bool same(int x, int y) { return find(x) == find(y); }
bool merge(int x, int y)
{
x = find(x), y = find(y);
if (x == y)
return false;
siz[x] += siz[y];
p[y] = x;
return true;
}
int size(int x) { return siz[find(x)]; }
};
int f(int x)
{
int res = 0;
while(x)
{
res += x % 10;
x /= 10;
}
return res;
}
void solve(){
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
for(int i = 1; i <= n; i ++ ) cin >> a[i];
DSU dsu(n + 2); // 需要使用n+1个位置，第n+1个数修改完成后要指向第n+2个数
for(int i = 0; i < q; i ++ )
{
int o;
cin >> o;
if(o == 1)
{
int l, r;
cin >> l >> r;
// l -- ;
int x = dsu.find(l);
while(x <= r)
{
a[x] = f(a[x]);
if(a[x] < 10){
dsu.merge(x + 1, x);
}
x = dsu.find(x + 1);
}
}
else
{
int x;
cin >> x;
// x -- ;
cout << a[x] << "\n";
}
}
}
int main()
{
freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _t = 1;
cin >> _t;
while(_t -- ){
solve();
}
return 0;
}G1. Teleporters (Easy Version)
对于每个传送门的花费都是独立的，可以分别计算每个传送门的花费，排序，从小到大查看能用到第几个
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
void solve()
{
int n, c;
cin >> n >> c;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] += i;
}
sort(a + 1, a + n + 1);
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (c >= a[i])
c -= a[i], ans++;
else
break;
}
cout << ans << endl;
}
int main()
{
freopen("test.in", "r", stdin);
int tt;
cin >> tt;
while (tt--)
{
solve();
}
return 0;
}G2. Teleporters (Hard Version)
传送可以选左边也可以右边，但第一次必须左边
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n, c;
cin >> n >> c;
vector<pair<int, int>> a(n);
for(int i = 0; i < n; i ++ ){
int x;
cin >> x;
a[i] = {min(x + i + 1, x + n - i), x + i + 1};
}
sort(a.begin(), a.end());
vector<long long> s(n + 1);
for(int i = 0; i < n; i ++ ){
s[i + 1] = s[i] + a[i].first;
}
int ans = 0;
for(int i = 0; i < n; i ++ ){
if(a[i].second > c) continue;
int l = 0, r = n;
while(l < r){
int x = (l + r + 1) / 2;
long long val = s[x];
if(x > i){
val -= a[i].first;
}
if(val + a[i].second <= c){
l = x;
}else{
r = x - 1;
}
}
ans = max(ans, l + (l <= i));
}
cout << ans << endl;
}
int main()
{
freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _t = 1;
cin >> _t;
while(_t -- ){
solve();
}
return 0;
}
