A. Rook
题意：在一个国际象棋棋盘中，横坐标为a-h，纵坐标为1-8，字母在前，数字在后，输入一个棋子的位置，输出该棋子所在的行与列中非棋子本身位置的所有位置。
分析：模拟。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int t, n, m;
ll s[N], f[N];
ll ans, k;
string str;
void sol() {
cin >> str;
for (int i = 0; i < 8; i++) {
char ch = 'a' + i;
if (ch == str[0]) continue;
cout << ch << str[1] << endl;
}
for (int i = 1; i <= 8; i++) {
if (i == str[1] - '0') continue;
cout << str[0] << i << endl;
}
}
int main()
{
t = 1;
cin >> t;
while (t--)
sol();
return 0;
}
B - YetnotherrokenKeoard
题意：给出一串字符串，按顺序输入，但计算机遭到篡改，输入B会删除之前输出的大写字母，输入b会删除之前输出的小写字母，如果没有则不执行，询问最终输出结果
分析：栈的调用，大写字母和小写字母分别调用一个栈，标记删除的位置进行假删除，输出的时候跳过删除的位置即可。
代码：
#include <iostream>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int t, n, m;
ll s[N], f[N];
ll ans, k;
string str;
stack<int> sta, stb;
map<int, int> ma;
void sol() {
cin >> str;
for (int i = 0; i < str.size(); i++) {
if (str[i] == 'b') {
ma[i] = 1;
if (!sta.empty()) {
ma[sta.top()] = 1;
sta.pop();
}
}
else if (str[i] == 'B') {
ma[i] = 1;
if (!stb.empty()) {
ma[stb.top()] = 1;
stb.pop();
}
}
else if (str[i] >= 'a' && str[i] <= 'z') {
sta.push(i);
}
else if (str[i] >= 'A' && str[i] <= 'Z') {
stb.push(i);
}
}
for (int i = 0; i < str.size(); i++) {
if (ma[i]) continue;
cout << str[i];
}cout << endl;
ma.clear();
while (!sta.empty()) sta.pop();
while (!stb.empty()) stb.pop();
}
int main()
{
t = 1;
cin >> t;
while (t--)
sol();
return 0;
}
C - Removal of Unattractive Pairs
题意：给出n，长度为n的字符串合法范围内前后字母不同可以进行消除，问最终最少剩下几个字母(删除顺序不同答案不同，比如cabcc->ccc, cabcc->bcc->c,前者是3，后者是1，显然后者更优)。
分析：最终一定会变为全是某个字母的情况，观察例子发现，该字母一定是字符串中字母最多的那个，分析每次跟字母最多的进行匹配一定更优，假如最多的字母数量为x，如果x>n-x,那么最终答案一定为2*x-n,如果不是，那么一定会两两匹配，只需要判断n的奇偶即可。
代码：
#include <iostream>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int t, n, m;
int s[N], f[N];
ll ans, k;
string str;
stack<int> sta, stb;
map<int, int> ma;
void sol() {
cin >> n;
cin >> str;
for (int i = 0; i < str.size(); i++) {
s[str[i] - 'a']++;
}
int maxn = 0;
for (int i = 0; i < 26; i++) {
maxn = max(maxn, s[i]);
s[i] = 0;
}
if (maxn > str.size() - maxn) {
cout << maxn - (str.size() - maxn) << endl;
} else {
cout << (str.size() & 1) << endl;
}
}
int main()
{
t = 1;
cin >> t;
while (t--)
sol();
return 0;
}
D - Jumping Through Segments
题意：给出n，以下n组，每组给出l, r，最初为于0的位置，每次可以走不超过k的位置，比如在k可以走到[0, 2*k]这个区间范围内任意地方，要求走n步，走第i步必须走到[l[i],r[i]]范围内，求k最小值。
分析：显然二分答案，问题是如何判断k的合法性，如果最初是在[a,b]的范围，那么一步走不超过k的范围，走一步后，范围必定在[a-k,b+k]，如果跟当前要求的范围没有交集，意味着该k过小，不合法，如果有交集，那么因为必须走到要求范围内，所以会取共集，[max(l, a-k), min(r, b+k)]。一路走下去，时间复杂度(O)nlogn。为方便使用，二元组用了pair<int, int>。
代码：
#include <iostream>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e5 + 10, mod = 1e9 + 7;
int t, n, m;
int s[N], f[N];
ll ans, k;
PII p[N];
string str;
stack<int> sta, stb;
map<int, int> ma;
bool judge(int mid) {
PII q = {0, 0};
for (int i = 1; i <= n; i++) {
q.first -= mid;
q.second += mid;
if (q.first > p[i].second)
return false;
if (q.second < p[i].first)
return false;
q.first = max(q.first, p[i].first);
q.second = min(q.second, p[i].second);
}
return true;
}
void sol() {
cin >> n;
for (int i = 1; i <= n; i++) {
int l, r;
cin >> l >> r;
p[i] = {l, r};
}
int l = 0, r = mod;
while (l < r) {
int mid = l + r >> 1;
if (judge(mid))
r = mid;
else
l = mid + 1;
}
cout << l << endl;
}
int main()
{
t = 1;
cin >> t;
while (t--)
sol();
return 0;
}
E - Good Triples
题意：众和数，即一个自然数的各位数字之和，例如345的众和数就是3+4+5=12，以下用digusm(n)表示n的众和数，条件1：a+b+c=n,条件2：digsum(a)+digsum(b)+digsum(c)=digsum(n)，给出n，能找到多少个满足以上两个条件的答案。n≤1e7
分析：t组，n范围这么大，还没说所有的n不超过1e7，均下来每个只有不超过1e4的次数查答案，根号n级别，过题人数上千，考虑找规律，先暴力模拟，找规律。在模拟后发现每一位其实是单独计算的，记f(n)为答案，0-9的答案是直接算出来的，其余都是临时算的，是每一位答案的乘积，比如f(345)＝f(3) * f(4) * f(5)，找到规律后，查找一个的时间复杂度极低，可以通过。至于为什么可以每位单独考虑，在知道答案后分析，可以发现，分别考虑就是每位不进到下一位的情况，如果有进位的情况意味着在本位算数的之后会多10，而众和数那边这个10对不回去，一个数只能有不超过10的大小，且对应的数进位就连锁，不进位该数对于另外的10将毫无贡献，所以每一位只能单独计算，互不影响。
代码：
#include <iostream>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e7 + 10, mod = 1e9 + 7;
int t, n, m;
int s[N], f[N];
ll ans, k;
PII p[N];
string str;
stack<int> sta, stb;
map<int, int> ma;
void init() {
for (int i = 1; i <= 10000000; i++) {
s[i] = s[i / 10] + i % 10;
}
for (int k = 0; k <= 10; k++) {
ans = 0;
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= k - i; j++) {
if (s[i] + s[j] + s[k-i-j] == s[k]) {
ans++;
}
}
}
f[k] = ans;
}
}
void sol() {
cin >> n;
ans = 1;
while (n) {
ans *= f[n%10];
n /= 10;
}
cout << ans << endl;
}
int main()
{
init();
t = 1;
cin >> t;
while(t--)
sol();
return 0;
}
F - Shift and Reverse
题意：给出n，给出长度为n的数组，只能执行两种操作，操作1：整体翻转，操作2：将最后一个元素放到第一个位置，其他位置以此后移，问最少花费多少步操作可以使得非降序排列，恒不成立输出-1。
分析：可以直接看出，但凡能成立的一定是首尾相连后，从某个位置开始已经能非降序排列，或是非升序排列了，也可能两者同时成立，所以分别找，去min，如果是升序，找到最小值理论位于最左的那一个，比如1,1,2,3,4，最小值的最左位置就是第一个，1,1,2,3,1，最小值的最左位置其实就是第五个，说的是成立条件下的，所以要分类讨论一下，相反降序的话，找到最大值理论上最右的那一个，对于升序，找到位置后(当做x)也有两种方式，可以直接执行操作1，就是n-x+1，也可以先反转，就变成了将前面的往后移，最后再翻回来，就是2+x-1，取min（n-x+1,x+1），升序也是一样有两种min(n-x+2,x)。
代码：
#include <iostream>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e6 + 10, mod = 1e9 + 7;
int t, n, m;
int s[N], f[N], g[N];
int ans, k;
PII p[N];
string str;
stack<int> sta, stb;
map<int, int> ma;
void init() {
}
void sol() {
ans = mod;
cin >> n;
int bj = 1;
for (int i = 1; i <= n; i++) {
cin >> s[i];
s[i+n] = s[i];
g[i] = s[i];
}
int ans = mod;
sort(g + 1, g + n + 1);
bool flag = true;
bj = 1;
if (s[1] == g[1]) {
int j = n;
while (s[j] == g[1]) {
bj = j;
j--;
}
} else {
while (s[bj] != g[1]) bj++;
}
for (int i = bj + 1; i < bj + n; i++)
if (s[i] < s[i-1])
flag = false;
if (flag) {
if (bj == 1) ans = min(ans, 0);
else ans = min(ans, min(n - bj + 1, 1 + bj));
}
flag = true;
bj = 1;
if (s[1] == g[n]) {
int j = n;
if (s[j] == g[n])
while (s[j] == g[n]) {
bj = j;
j--;
}
} else {
bj = n;
for (int i = n; i >= 1; i--)
if (s[i] == g[n])
bj = i;
}
for (int i = bj + 1; i < bj + n; i++) {
if (s[i] > s[i-1])
flag = false;
}
if (flag) {
if (bj == 1) ans = min(ans, 1);
else ans = min(ans, min(n - bj + 2, bj));
}
if (ans == mod) ans = -1;
cout << ans << endl;
}
int main()
{
init();
t = 1;
cin >> t;
while(t--)
sol();
return 0;
}