水题尝试用python写，有时候舍得多用几分钟寻求简易方法实现更重要
A.Array with Odd Sum
题意：
你可以更换两个数，要求和是奇数
分析：
代码：
cpp版
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;cin >> t;
while(t--)
{
int n; cin >> n;
int flag1 = 0, flag2 = 0;// 1 odd 2 even
ll sum = 0;
while(n--)
{
int x; cin >> x;
if(x & 1) flag1 = 1;
else flag2 = 1;
sum += x;
}
if(flag2 && !flag1) cout << "NO" << endl;
else if(flag1 && !flag2)
{
if(sum & 1) cout << "YES" << endl;
else cout << "NO" << endl;
}
else cout << "YES" << endl;
}
}
Python版
for _ in range(int(input())):
n = int(input())
l = list(map(int, input().split()))
odd = False
even = False
for i in l:
if i & 1:
odd = True
else:
even = True
if odd and even or sum(l) % 2 == 1:
print("YES")
else:
print("NO")
B.Food Buying
题意：
你有一些钱，花费10元就可以返还一元，且一元也可以用掉，问你花最多多少钱
分析：
以10元为单位支出，每次支出损失9元。当剩余不足10元时停止，支出剩余钱数。
代码：
cpp版本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cal(ll n)
{
ll res = 0;
while (n >= 10)
{
string tmp = to_string(n);
int len = tmp.length();
res += (tmp[0] - '0') * pow(10, len - 1);
n = n - (tmp[0] - '0') * pow(10, len - 1) + (tmp[0] - '0') * pow(10, len - 1) / 10;//太繁琐
}
res += n;
return res;
}
int main()
{
int t; cin >> t;
while (t--)
{
ll n;
cin >> n;
cout << cal(n) << endl;
}
}
for _ in range(int(input())):
n = int(input())
ans = 0
if n % 9 == 0:
ans += 10 * (n // 9 - 1) + 9
else:
ans += 10 * (n // 9) + n % 9
print(ans)
精简性一目了然
C.Yet Another Walking Robot
题意：
略
分析：
一开始想如何找到最小的区间使得区间的位移和为0，一直在一维上想。后来被指点之后发现可以存储每次移动的二维坐标。每次走一步判断一下是否之前走到过即可。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
char s[maxn];
int main()
{
int t; cin >> t;
while(t--)
{
int n; cin >> n;
map<pair<int, int>, int> vis;
cin >> (s + 1);
int x = 0, y = 0;
vis[make_pair(0, 0)] = 0;
int resl = -1, resr = -1;
for(int i = 1; s[i]; i++)
{
if(s[i] == 'R') x++;
if(s[i] == 'L') x--;
if(s[i] == 'U') y++;
if(s[i] == 'D') y--;
if(vis.count(make_pair(x, y)))
{
if(resl == -1)
resl = vis[make_pair(x, y)], resr = i;
else if(i - vis[make_pair(x, y)] < resr - resl)
resl = vis[make_pair(x, y)], resr = i;
}
vis[make_pair(x, y)] = i;
}
if(resl == -1) cout << -1 << endl;
else cout << resl + 1 << " " << resr << endl;
}
}
D.Fight with Monsters
题意：
略
分析：
贪心即可
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> v;
int main()
{
ll n, a, b, k;
ll res = 0;
cin >> n >> a >> b >> k;
ll sum = (a + b);
for(int i = 1; i <= n; i++)
{
ll ph;
scanf("%lld", &ph);
if(ph % sum == 0) ph = sum;
else ph %= sum;
if(ph > a) v.push_back(ph);
else res++;
}
sort(v.begin(), v.end());
for(int i = 0; i < v.size(); i++)
{
v[i] -= a;
ll cnt = v[i] % a == 0 ? v[i] / a : v[i] / a + 1;
if(k >= cnt) res++, k -= cnt;
else break;
}
cout << res << endl;
}
E2.String Coloring (hard version) | 字符串dp题
题意：
给定一段长度为n的字符串s
你需要给每个字符进行涂色，然后相邻的不同色的字符可以进行交换
需要保证涂色后能通过相邻交换把这个字符串按照字典序排序（a~z）
你可以使用无限种颜色，但是要保证用到的颜色种类最少
从1开始对颜色进行编号，先输出最少使用的颜色种类，再给出涂色方案
分析：
可以引入一个 dp[]数组，开26个空间代表26种字母
这个数组 dp[i] 的值代表 第 i 个字母在前面涂的颜色最大编号是多少，0表示没出现过
遍历这个字符串，再从当前字母后一个位置开始往后再遍历这个数组，即找比当前字母要大的所有字母中编号最大的那个字母的编号
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n;
char s[maxn];
int dp[maxn][27];
int col[maxn];
int main()
{
int n; cin >> n;
int res = 1;
cin >> (s + 1);
memset(dp, -1, sizeof(dp));
dp[1][s[1] - 'a' + 1] = 1;
col[1] = 1;
for(int i = 2; i <= n; i++)
{
memcpy(dp[i], dp[i - 1], sizeof(dp[i]));
int maxcolor = -1;
for(int j = s[i] - 'a' + 2; j <= 26; j++)
maxcolor = max(maxcolor, dp[i - 1][j]);
if(maxcolor == -1) col[i] = 1;
else col[i] = maxcolor + 1;
dp[i][s[i] - 'a' + 1] = max(dp[i][s[i] - 'a' + 1], col[i]);
res = max(res, col[i]);
}
cout << res << endl;
for(int i = 1; i <= n; i++)
printf("%d%c", col[i], i == n ? '\n' : ' ');
}
