记录一下第一次可以写到G1，只剩一道题就可以ak，虽然是div4，不过也值得开心一下。
A - Codeforces Checking
void solve() {
char c;
cin >> c;
string s = "codeforces";
bool flag = 0;
for (auto i :s) if (i == c) {
flag = 1;
}
if (flag) cout << "YES" <<endl;
else cout << "NO" <<endl;
}
B - Following Directions
void solve() {
int n;
cin >> n;
string s;
cin >> s;
int x = 0, y = 0;
bool flag = 0;
for (auto i : s) {
if (i == 'U') {
y ++;
}else if (i == 'D') {
y --;
}else if (i == 'R') {
x ++;
}else if (i == 'L') {
x --;
}
if (x == 1 && y == 1) flag = 1;
}
if (flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
C - Prepend and Append
void solve() {
int n;
cin >> n;
string s;
cin >> s;
int l = 0, r = n - 1;
while (l < r) {
if (s[l] != s[r]) {
n -= 2;
l ++, r --;
}else break;
}
cout << n << endl;
}
D - Distinct Split
题意
给出长度为n的字符串，函数f代表字符串中字符种类数，如f(aba) = 2.问怎么切分可以使给出的字符串两段f之和最大
思路
枚举
用map先将原字符串的字符种类数统计出来作为第二段的种类数，然后从前向后枚举，令0 ~ i为第一段，i + 1 ~ n - 1为第二段。用map统计第一段和第二段的字符种类，然后取最大值即可
void solve() {
int n;
cin >> n;
string s;
cin >> s;
map<int, int> mp, p;
for (int i = 0; i < n; i ++) {
mp[s[i] - 'a'] ++;
}
int x = 0, y = mp.size(), ans = 0;
for (int i = 0; i < n; i ++) {
mp[s[i] - 'a'] --;
p[s[i] - 'a'] ++;
if (mp[s[i] - 'a'] == 0) y --;
if (p[s[i] - 'a'] == 1) x ++;
ans = max(ans, x + y);
}
cout << ans << endl;
}
E - Negatives and Positives
题意
给出长度为n的序列，你可以进行任意次操作，将相邻两个数字的符号变换，即正变负，负变正。问经过操作后序列总和最大值为多少
思路
观察一下变换操作即可得出一下规律，即使不相邻的两个数字也可同时变换符号
如-1 2 2 22 -1
进行若干操作
1 -2 2 22 -1
1 2 -2 22 -1
1 2 2 -22 -1
1 2 2 22 1
这样就简单了。将序列排序，若有负数，负数数量为偶数就可全部变成正数，若数量为奇数，则需要判断是否变换后面那个正数（若还有的话）
若后面那个数的绝对值小于当前负数的绝对值，那么一定是可以取的，否则这个负数就不变换了
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n ;i ++) cin >> a[i];
sort(a.begin() + 1, a.end());
int cnt = 0;
for (int i = 1; i <= n; i ++) {
if (a[i] < 0) cnt ++;
}
if (cnt % 2 == 1) {
if (cnt + 1 <= n && abs(a[cnt + 1]) <= abs(a[cnt])) {
cnt ++;
}else cnt --;
}
LL sum = 0;
for (int i = 1; i <= n; i ++) {
if (i <= cnt) {
a[i] = -a[i];
}
sum += a[i];
}
cout << sum << endl;
}
F - Range Update Point Query
题意
给出长度为n的序列，和q次询问。询问1为将区间[l, r]间的每个数变成他们各自每一位上的数之和，如：123变换之后为1 + 2 + 3 = 6
询问2为查询下标为x的数为多少
思路
这题用树状数组+差分水过去的，看到还有用set模拟的大佬
int tr[N], n;
inline int lowbit(int x)
{
return x & -x;
}
void add(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i))
{
tr[i] += c;
}
}
int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i))
{
res += tr[i];
}
return res;
}
void solve() {
int q;
cin >> n >> q;
memset(tr, 0, sizeof (tr));
vector<int> a(n + 1);
vector<int> p[n + 1]; //存储每个数会变换为什么数
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++) {
int k = a[i];
if (k < 10) p[i].push_back(k);
while (k >= 10) {
int num = 0;
while (k) {
int tt = k % 10;
num += tt;
k /= 10;
}
k = num;
num = 0;
p[i].push_back(k);
}
}
while (q --) {
int x;
cin >> x;
if (x == 1) {
int l, r;
cin >> l >> r;
add(l, 1), add(r + 1, -1);
}else {
int c;
cin >> c;
int sz = p[c].size();
int cnt = sum(c);
if (cnt == 0) {
cout << a[c] << endl;
continue;
}
if (cnt >= sz) {
cout << p[c][sz - 1] << endl;
}else cout << p[c][cnt - 1] << endl;
}
}
}
G1 - Teleporters (Easy Version)
题意
数字线上的点0,1，…，n。在点1、2、…、n中的每个点上都有一个隐形传态器。在点i，可以执行以下操作：
向左移动一个单位：花费1硬币
向右移动一个单位：成本1硬币
在i点使用传送机，如果存在的话：它需要ai币。结果，你传送到0点。一旦你使用了传送器，你就不能再使用它了。
你有c硬币，从0点开始。你能使用的传送机最多有多少？
思路（贪心）
只从一端开始的话，就是对每个ai都加上i为路程耗费，然后将a数组排序，选出符合条件的传送机即可
void solve() {
LL n, c;
cin >> n >> c;
vector<LL> a(n + 1);
for (int i = 1; i <= n; i ++) {
cin >> a[i];
a[i] += i;
}
sort(a.begin() + 1, a.end());
for (int i = 1; i <= n; i ++) {
if (c >= a[i]) c -= a[i];
else {
cout << i - 1 << endl;
return ;
}
}
cout << n << endl;
}
G2 - Teleporters (Hard Version)
题意
跟上题差不多，唯一一点不同在于除了第一次，你可以从n + 1的位置去使用传送器
思路（枚举 + 二分）
找到每个位置上花费最少的费用和若是第一次去该位置要花多少钱记录下来。
然后排序，求前缀和
枚举每个可以作为第一次去的位置，然后二分出最大可以去多少个传送器，若当前位置小于二分出的数量，则该位置上要减去最少费用加上第一次在这个位置需要的钱。
若当前位置大于等于二分出的位置，则将该位置作为前置条件，只需要加上第一次在这个位置的费用即可。
最后需要的传送器个数：若该位置小于二分出的位置，则就是l，否则需要加上前置也就是l + 1
void solve() {
int n, c;
cin >> n >> c;
vector<pair<LL, LL>> a;
for (int i = 1; i <= n; i ++) {
int x;
cin >> x;
a.push_back({min(x + i, x + n - i + 1), x + i});
}
sort(a.begin(), a.end());
vector<LL> sum(n + 1, 0);
for (int i = 1; i <= n; i ++) {
sum[i] = a[i - 1].first + sum[i - 1];
}
int ans = 0;
for (int i = 0; i < n; i ++) {
if (a[i].second <= c) {
int l = 0, r = n, mid;
while (l < r) {
mid = (l + r + 1) >> 1;
LL price = sum[mid];
if (mid > i) {
price -= a[i].first;
}
if (price + a[i].second <= c) {
l = mid;
} else r = mid - 1;
}
ans = max(ans, l + 1 - (l > i));
}
}
cout << ans << endl;
}
总结
本场没什么难度，思维都挺简单地，最难得也就是G2，但是也就是枚举+二分
标签：cout,int,void,Codeforces,cin,++,solve,2.3,Div From： https://www.cnblogs.com/lbzbk/p/17092506.html