题意：给一个字符串，求是否含有不重叠的子串"AB"和"BA"，长度1e5。
题解：看起来很简单，但是一直错，各种考虑不周全，最后只能很蠢的暴力，把所有的AB和BA的位置求出来，能有一对AB和BA不重叠即可。
#include <bits/stdc++.h>
using namespace std; char a[];
vector<int> ab;
vector<int> ba;
int main()
{
while (~scanf("%s", a)) {
int len = strlen(a);
ab.clear();
ba.clear(); for (int i = ; i < len - ; ++i) {
if (a[i] == 'A' && a[i + ] == 'B') {
ab.push_back(i);
}
if (a[i] == 'B' && a[i + ] == 'A') {
ba.push_back(i);
}
} if (ab.size() == || ba.size() == ) {
puts("NO");
} else if (ab.size() > && ba.size() > ) {
puts("YES");
} else {
int flag = false;
for (int i = ; i < ab.size(); ++i) {
for (int j = ; j < ba.size(); ++j) {
if (!(ab[i] + == ba[j]) && !(ab[i] - == ba[j])) flag = true;
}
}
if (flag) puts("YES");
else puts("NO");
}
}
return ;
}
题意：输入n, l, r, x，代表有n题，每题有一个难度，选其中部分题（大于2题），要求难度和在[l, r]之间，最大难度最小难度的差不超过x。1 ≤ n ≤ 15
题解：暴力，dfs求全部情况。复杂度2^15
#include <bits/stdc++.h> using namespace std; int a[];
int n, l, r, x;
int vis[];
int ans; bool ok()
{
int cnt = ;
for (int i = ; i < n; ++i) if (vis[i]) cnt++;
if (cnt < ) return false;
int low = ;
int high = ;
int sum = ;
for (int i = ; i < n; ++i) {
if (!vis[i]) continue;
low = min(low, a[i]);
high = max(high, a[i]);
sum += a[i];
}
if (high - low >= x && sum <= r && sum >= l) return true;
return false;
} void dfs(int pos)
{
if (pos == n) {
if (ok()) ans++;
return ;
}
vis[pos] = ;
dfs(pos + );
vis[pos] = ;
dfs(pos + );
} int main()
{
while (cin >> n >> l >> r >> x) {
for (int i = ; i < n; ++i) cin >> a[i];
ans = ;
dfs();
cout << ans << endl;
}
return ;
}
题意：给一个不超过100位的没有前导零的非负整数，问可不可能移出一部分数字，事剩下至少一位非负整数能被8整除。
题解：能被8整除的数有一个特性：一个整数的末3位若能被8整除，则该数一定能被8整除。求出所有的三位以内能被8整除的数，分别试一下就ok了。
#include <bits/stdc++.h>
using namespace std; int ans[];
char a[];
//一个整数的末3位若能被8整除，则该数一定能被8整除。
bool ok(int x)
{
int num[];
int cnt = ;
while (x) {
num[cnt++] = x % ;
x /= ;
}
reverse(num, num + cnt);
int len = strlen(a);
int pos = ;
int i;
for (i = ; i < cnt; ++i) {
while (a[pos] - '' != num[i] && pos < len) {
pos++;
}
if (pos >= len) break;pos++;
}
if (i == cnt) return true;
return false;
} int main()
{
int idx = ;
ans[] = ;
for (int i = ; i < ; ++i) {
if (i * > ) break;
ans[idx++] = i * ;
} scanf("%s", a);
for (int i = ; i < idx; ++i) {
if (ok(ans[i])) {
printf("YES\n%d\n", ans[i]);
return ;
}
}
int len = strlen(a);
for (int i = ; i < len; ++i) {
if (a[i] == '') {
printf("YES\n0\n");
return ;
}
}
printf("NO\n"); return ;
}
题意：给一个k(1 ≤ k ≤ 100) ，问是否存在一个无向图至少有一个桥且所有点的度都是k。如果存在给出任意一种解。
题解：对于k+1个点的完全图，所有点的度都是k。考虑两堆k+1的点，然后再用两个点组成桥，每个点和其中一个堆连k-1就可以了。每次桥上的点连堆中两个点，然后删除这两个点的连线，度数不变。同时也可以发现只有k-1为偶数是，即k为奇数时才有解。
#include <cstdio> using namespace std; int main()
{
int k;
while (~scanf("%d", &k)) {
if ((k & ) == ) {
puts("NO");
} else if (k == ) {
puts("YES\n2 1\n1 2");
} else {
puts("YES");
printf("%d %d\n", * k + , k * k + * k);
for (int i = ; i < k; ++i) {
printf("%d %d\n", * k + , i);
printf("%d %d\n", * k + , i + k + );
}
printf("%d %d\n", * k + , * k + );
for (int i = ; i <= k + ; ++i) {
for (int j = i + ; j <= k + ; ++j) {
if (i < k - && (i & ) && i + == j) continue;
printf("%d %d\n", i, j);
printf("%d %d\n", k + + i, k + + j);
}
}
}
}
return ;
}
E. Brackets in Implications（构造）
题意：给定01间运算0->0=1 0->1=1 1->0=0 1->1=1 默认从左到右运算 问能不能通过加括号使得表达式值变为0
题解：很容易发现最后一位必须是0，倒数第二位如果是1，那么不用加括号直接为0。如果倒数第二位为0，那么需要在前面找到一个0，两个0即中间的1组成1，然后同上。两个0和中间的1组成1的方法可以为(0(11...110))。
#include <iostream>
#include <stdio.h> using namespace std; int a[];
int n;
int main()
{
cin >> n;
for (int i = ; i < n; ++i)
scanf("%d", a + i); if (n == ) {
if (a[] == ) puts("YES\n0");
else puts("NO");
} else if (n == ) {
if (a[] == && a[] == ) puts("YES\n1->0");
else puts("NO");
} else if (a[n - ] == ) {
puts("NO");
} else {
if (a[n - ] == ) {
puts("YES");
for (int i = ; i < n - ; ++i) {
printf("%d->", a[i]);
}
puts("");
} else {
int pos = -;
for (int i = n - ; i >= ; --i) {
if (a[i] == ) {
pos = i;
break;
}
}
if (pos == -) puts("NO");
else {
puts("YES");
for (int i = ; i < pos; ++i) {
printf("%d->", a[i]);
}
printf("(0->(");
for (int i = pos + ; i < n - ; ++i) {
printf("%d->", a[i]);
}
puts("0))->0");
}
}
}
return ;
}