可以在棋盘上横向或纵向移动任意步数，找出车的所有走法
直接输出横向和纵向车能移动的位置即可
void solve()
{
string s; cin >> s;
string s1, s2;
s1 = s2 = s;
vector<string> vec;
for (int i = 0; i < 8; i++) {
s1[0] = char(i + 'a');
s2[1] = char(i + '1');
vec.push_back(s1);
vec.push_back(s2);
}
for (auto x : vec) {
if (x == s) continue;
cout << x << endl;
}
}
按顺序输入字符串，遇到 ′ B ′ 'B' ′B′ 删除输入的字符串中最右侧的大写字母，没有则不做改变，输入到 ′ b ′ 'b' ′b′，删除输入的字符串中最右侧的小写字母，没有则不改变
类似于队列，维护大写字母和小写字母最优侧下标，那么我们则将小标与对应的字符存储在一起，按照顺序输入，操作。
PII a[N];
void solve()
{
string s; cin >> s;
//维护序列当中最右边大写小写字母
vector<PII> lc, uc;
for (int i = 0; i < (int)s.size(); i++) {
char x = s[i];
if (x == 'b') {
if (lc.size()) lc.pop_back();
}
else if (x == 'B') {
if (uc.size()) uc.pop_back();
}
else if (isupper(x)) {
uc.push_back({ i,x });
}
else lc.push_back({ i,x });
}
vector<PII> vec;
for (auto it : lc) {
vec.push_back(it);
}
for (auto it : uc) {
vec.push_back(it);
}
sort(vec.begin(), vec.end());
for (auto it : vec) {
cout << char(it.second);
}
cout << endl;
}
给出一个字符串，满足任意删除相邻的一对不同字符，求出最短的字符串
模拟发现，最后的状态一定不存在字符或者只存在一个字符，因此考虑将其余字符删除，能将字符变得多短
void solve()
{
int cnt = 0;
int n; cin >> n;
string s; cin >> s;
map<int, int> mp;
for (int i = 0; i < (int)s.size(); i++) {
mp[s[i]]++;
cnt = max(mp[s[i]], cnt);
}
cout << n - min(n / 2, n - cnt) * 2 << endl;
}
给出 n n n 个线段，第 i i i 次移动要在第 i i i 个线段上面，可以在 k k k 范围内任意距离移动，求最小的 k k k
二分答案。每一次移动范围内，存在移动范围与下一个下段有交集即合法。
bool check(int k)
{
int l = 0, r = 0;
for (auto it : a) {
int L = max(0, l - k), R = r + k;
if (L > it.second || R < it.first) return 0;
l = max(L,it.first),r = min(R,it.second);
}
return 1;
}
void solve()
{
int n; cin >> n;
a = b;
for (int i = 0; i < n; i++) {
int l, r;;
cin >> l >> r;
a.push_back({ l,r });
}
int l = 0, r = 2e9;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
}
给出一个整数 n n n,满足三个非负整数 a 、 b 、 c a、b、c a、b、c之和为 n n n，并且他们的数位之和等于 n n n 的数位之和的方案数。
若要满足条件，三个数是不能进位。因此每一位是不受其他位影响，将每一数的每一位贡献相乘即可
int pre[10];
void solve()
{
int n; cin >> n;
ll ans = 1;
while (n) {
ans *= pre[n % 10];
n /= 10;
}
cout << ans << endl;
}
int main()
{
for (int i = 0; i <= 9; i++) {
for (int j = 0; i + j <= 9; j++) {
for (int k = 0; i + k + j <= 9; k++) {
pre[i + j + k]++;
}
}
}
int t; cin >> t;
while (t--) solve();
return 0;
}
给出一个数组 a a a,可以进行两种操作
移位：将最后一个数组移到首位
反转：将整个数组反转
将数组变成环，遍历找到递增的或者递减的，模拟操作即可
void solve()
{
int n; cin >> n;
vector<int> a(2 * n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i + n] = a[i];
}
int ans = -1;
for (int i = 0; i < n; i++) {
int st = i;
int cnt = 1;
while (i < 2 * n - 1 && a[i] >= a[i + 1]) {
cnt++;
i++;
}
if (cnt >= n) {
ans = min(st + 1, n - st + 1);
}
}
for (int i = 0; i < n; i++) {
int st = i;
int cnt = 1;
while (i < 2 * n - 1 && a[i] <= a[i + 1]) {
cnt++;
i++;
}
if (cnt >= n) {
if (ans == -1) {
ans = min(n - st, st + 2);//移动多少个，翻转两次，一次时移动多少个
}
else {
ans = min(ans, min(n - st, st + 2));
}
if (st == 0) ans = 0;
}
}
cout << ans << endl;
}
有 n n n 盏灯和 n n n 个开关，改变 i i i 的状态，也会改变 a i a_i ai? 状态。求出最少开关关掉所有的灯，不可能输出 -1。
建边后发现是一颗基环树，环外的边的操作固定，用拓扑排序处理非环上的点。环的部分，如果剩余亮着的灯数量为奇数，则无法全部熄灭。
void solve()
{
int n; cin >> n;
vector<int> in(n + 5), e(n + 5);
string s; cin >> s;
s = " " + s;
for (int i = 1; i <= n; i++) {
int u = i, v;
cin >> v;
e[u] = v;
in[v] ++;
}
queue<int>q;
for (int i = 1; i <= n; i++) {
if (in[i] == 0) q.push(i);
}
vector<int>ans;
while (!q.empty()) {
int x = q.front();
q.pop();
if (s[x] == '1') {
s[x] = '0';
ans.push_back(x);
if (s[e[x]] == '1') {
s[e[x]] = '0';
}
else s[e[x]] = '1';
}
in[e[x]] --;
if (in[e[x]] == 0) {
q.push(e[x]);
}
}
for (int i = 1; i <= n; i++) {
if (in[i]) {
int j = i;
int t = 0;
int len = 0;
int res = 0;
while (in[j]) {//环
if (s[j] == '1') {
t ^= 1;
}
res += t;
in[j] = 0;
len++;
j = e[j];
}
if (t == 1) {
cout << -1 << endl;
return;
}
for (int k = 0; k < len; k++) {
if (s[j] == '1') {
t ^= 1;
}
if (t == (res < len - res)) ans.push_back(j);
j = e[j];
}
}
}
cout << ans.size() << endl;
for (auto it : ans) cout << it << ' ';
cout << endl;
}