Taka 和 Aoki 玩了 局游戏，胜负情况由一个长度为 的字符串给出。 T 表示 Taka 赢这一局，A 表示 Aoki 赢了这一局。
求最终赢家：
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin >> s;
int win = n / 2 + n % 2;
int tCnt = 0, aCnt = 0;
for (int i = 1; i <= n; i++)
{
if (s[i - 1] == 'T')
tCnt++;
else
aCnt++;
if (tCnt == win)
{
cout << "T";
return 0;
}
if (aCnt == win)
{
cout << "A";
return 0;
}
}
return 0;
}
给定一个序列 ，任意相邻得两个数都不同。尝试补足数使得整个序列连续。
输出最终补足后的序列。
#include <bits/stdc++.h>
using namespace std;
int n;
int pre, now;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin >> now;
pre = now;
cout << now << " ";
for (int i = 1; i <= n - 1; i++)
{
cin >> now;
if (pre > now)
for (int i = pre - 1; i >= now; i--)
cout << i << " ";
else
for (int i = pre + 1; i <= now; i++)
cout << i << " ";
pre = now;
}
return 0;
}
给定两个字符串 表示两副牌，两副牌的顺序可以随便打乱。牌只包含小写英文字母和 @。@ 可以被替换为 atcoder 这七个字符之一。求是否存在一种替换方法使得两副牌的某种顺序一样。
#include <bits/stdc++.h>
using namespace std;
string a, b;
int aCnt[30], bCnt[30];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> a;
cin >> b;
memset(aCnt, 0, sizeof(aCnt));
memset(bCnt, 0, sizeof(bCnt));
for (char c : a)
{
if (c == '@')
aCnt[26]++;
if ('a' <= c && c <= 'z')
aCnt[c - 'a']++;
}
for (char c : b)
{
if (c == '@')
bCnt[26]++;
if ('a' <= c && c <= 'z')
bCnt[c - 'a']++;
}
for (int i = 0; i <= 25; i++)
{
if (aCnt[i] != bCnt[i] &&
i != 'a' - 'a' &&
i != 't' - 'a' &&
i != 'c' - 'a' &&
i != 'o' - 'a' &&
i != 'd' - 'a' &&
i != 'e' - 'a' &&
i != 'r' - 'a')
{
cout << "No\n";
return 0;
}
if (aCnt[i] > bCnt[i])
bCnt[26] -= aCnt[i] - bCnt[i];
if (aCnt[i] < bCnt[i])
aCnt[26] -= bCnt[i] - aCnt[i];
}
if (aCnt[26] >= 0 && bCnt[26] >= 0)
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
给定一个整数 和一个字符串 。 中只包含字符 0,1,?。
? 可以被随意替换为 0 或 1，求是否存在一个替换方案使得最终字符串对应的二进制数不超过 。如果存在，输出最终值最大的一个替换方案。
先把 格式调整好，然后一位位尽可能取最大的，如果存在会超过 的情况，就找前面最近的一个选了 1，但原数是 0 的问号。让这个问号不再变成 1 ，而是变成 0 即可。如果不存在这样的问号，那说明无解。
需要注意 1 变为 0 后，后面的所有选了 0 的问号就都可以选 1 了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
string s;
string ss;
int n;
int getPos()
{
for (int i = 0; i <= 62; i++)
if (s[i] == '?' && ss[i] == '1' && ((n >> i) & 1))
return i;
return -1;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
reverse(s.begin(), s.end());
// 补足为 63 位二进制整数 (0 ~ 2^{63}-1)
while (s.length() < 63)
s = s + '0';
ss = s;
cin >> n;
bool limit = true; // 从高到低，前面是否顶到了最大值
int ans = 0; // 记录最终答案
for (int i = 62; i >= 0; i--)
{
int dig = ((n >> i) & 1LL);
if (s[i] == '?')
{
if (limit)
{
ans += (dig << i);
ss[i] = ('0' + dig);
}
else
{
ans += (1LL << i);
ss[i] = '1';
}
}
if (s[i] == '0')
{
limit = limit && (dig == 0LL);
}
if (s[i] == '1')
{
if (limit && dig == 0)
{
// 找到最合适撤销的 1
int last = getPos();
if (last == -1)
{
cout << "-1\n";
return 0;
}
// 撤销掉最合适的 1
ans -= (1LL << last);
// 中间所有之前设置为 0 的 ? 都可以设置 1 了
for (int j = last - 1; j > i; j--)
if (s[j] == '?' && ss[j] == '0')
{
ans += (1LL << j);
ss[j] = '1';
}
limit = false;
}
ans += (1LL << i);
}
}
cout << ans << "\n";
return 0;
}
#include <bits/stdc++.h>
#define int long long
using namespace std;
string s;
string ss;
int n;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
reverse(s.begin(), s.end());
// 补足为 63 位二进制整数 (0 ~ 2^{63}-1)
while (s.length() < 63)
s = s + '0';
ss = s;
cin >> n;
// 大开大合！
int ans = 0;
for (int i = 0; i <= 62; i++)
if (s[i] == '1')
ans += (1LL << i);
if (ans > n)
{
cout << "-1\n";
return 0;
}
for (int i = 62; i >= 0; i--)
if (s[i] == '?' && ans + (1LL << i) <= n)
ans += (1LL << i);
cout << ans << "\n";
return 0;
}
给定一个 行 列的二维字符迷宫:
#: 表示围墙.: 表示可以走的位置S: 表示起点G: 表示终点o: 表示可以吃的豆子，最多不超过 个。给定最多走的步数 ，问从起点到终点最多能吃多少个豆子。
数据范围
显然只需要关注豆子和起点终点的位置，由于这些点的数量加一起不超过 个，所以可以 爆搜处理处任意两个点之间的距离。
然后 个点这个数量可以很自然想到状压 ：
定义 为走过了 对应的这些点，且最后一个走的点是 时的最短路程。
决策也是经典的“枚举最后一个点的前一个点 ”，紧接着
假设起点为 号点，终点为 号点，表示 里面有几个 ，显然最终答案为
#include <bits/stdc++.h>
using namespace std;
int h, w, t;
char g[305][305];
int id[305][305];
vector<pair<int, int>> p;
int dis[305][305];
bool vis[305][305];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int pDis[35][35];
void cal(int st, int sx, int sy)
{
memset(vis, false, sizeof(vis));
queue<pair<int, int>> q;
q.push(make_pair(sx, sy));
dis[sx][sy] = 0;
vis[sx][sy] = true;
pDis[st][st] = 0;
while (!q.empty())
{
auto now = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int nx = now.first + dx[i];
int ny = now.second + dy[i];
if (1 <= nx && nx <= h && 1 <= ny && ny <= w &&
g[nx][ny] != '#' && !vis[nx][ny])
{
vis[nx][ny] = true;
dis[nx][ny] = dis[now.first][now.second] + 1;
q.push(make_pair(nx, ny));
if (id[nx][ny] != -1)
pDis[st][id[nx][ny]] = dis[nx][ny];
}
}
}
}
// 从 0 号点出发，走过了 i 这些点，并且最后一个走的点是 j 的最短路程
int f[(1 << 20)][21];
// 计算二进制下 1 的数量
int cnt1(int x)
{
int res = 0;
while (x > 0)
{
res++;
x -= (x & (-x));
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> h >> w >> t;
memset(id, -1, sizeof(id));
p.push_back(make_pair(0, 0));
p.push_back(make_pair(0, 0));
for (int i = 1; i <= h; i++)
for (int j = 1; j <= w; j++)
{
cin >> g[i][j];
// 储存点编号
if (g[i][j] == 'S')
{
p[0] = make_pair(i, j);
id[i][j] = 0;
}
else if (g[i][j] == 'G')
{
p[1] = make_pair(i, j);
id[i][j] = 1;
}
else if (g[i][j] == 'o')
{
p.push_back(make_pair(i, j));
id[i][j] = p.size() - 1;
}
}
// 计算任意两点最短路
memset(pDis, 0x3f, sizeof(pDis));
for (int i = 0; i < p.size(); i++)
cal(i, p[i].first, p[i].second);
// 状压dp
int cnt = p.size();
memset(f, 0x3f, sizeof(f));
f[1][0] = 0;
for (int sta = 2; sta <= ((1 << cnt) - 1); sta++)
{
if (!(sta & 1))
continue;
for (int last = 0; last < cnt; last++)
{
if (!(sta & (1 << last)))
continue;
// 计算 f[sta][last]
int preSta = sta - (1 << last);
for (int preLast = 0; preLast < cnt; preLast++)
{
if (!(preSta & (1 << preLast)))
continue;
f[sta][last] = min(f[sta][last], f[preSta][preLast] + pDis[preLast][last]);
}
}
}
// f[0011][1]: 直达
if (f[3][1] > t)
{
cout << "-1\n";
return 0;
}
int ans = 0;
for (int sta = 1; sta <= ((1 << cnt) - 1); sta++)
{
if (!(sta & 1)) // 0001
continue;
if (!(sta & 2)) // 0010
continue;
if (f[sta][1] <= t)
ans = max(ans, cnt1(sta) - 2);
}
cout << ans << "\n";
return 0;
}