给定一个只包含 .
、|
、*
的字符串。字符串里刚好只有两个 |
和一个 *
。
问 *
是在两个 |
框定的子区间内部还是外部。
#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 flag = 0;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == '|')
flag++;
if (s[i] == '*')
if (flag == 1)
{
cout << "in\n";
return 0;
}
}
cout << "out\n";
return 0;
}
位玩家编号为 。正在玩卡牌游戏,每个人都出了一张牌。
第 个人出的牌颜色是 ,等级是 。保证 各不相等。请判断谁赢了。
赢牌规则如下:
数据范围:
#include <bits/stdc++.h>
using namespace std;
int n, t;
int c[212345];
int r[212345];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> t;
for (int i = 1; i <= n; i++)
cin >> c[i];
for (int i = 1; i <= n; i++)
cin >> r[i];
// 确认目标颜色
int tt = c[1];
for (int i = 1; i <= n; i++)
if (c[i] == t)
tt = t;
// 确认胜者
int winner = -1;
for (int i = 1; i <= n; i++)
if (c[i] == tt)
if (winner == -1 || r[i] > r[winner])
winner = i;
cout << winner << "\n";
return 0;
}
一个 级别的团子为满足下面要求的字符串:
o
与 -
。-
,其他字符都是 o
。且 -
是第一个字符或者最后一个字符。给定一个只包含 o
和 -
的,长度为 的字符串 ,如果存在某个子串是团子,就输出最高级别的团子值,否则输出 -1
。
数据范围:
如果字符串里面既有 o
又有 -
,答案就是最长的连续 o
的长度。否则答案就是 -1
。
#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;
// 无解
bool hasO = false;
bool has_ = false;
for (int i = 0; i < n; i++)
{
hasO = hasO || s[i] == 'o';
has_ = has_ || s[i] == '-';
}
if (!hasO || !has_)
{
cout << "-1\n";
return 0;
}
// 最长
int cnt = 0; // 当前
int ans = 0; // 答案
for (int i = 0; i < n; i++)
{
if (s[i] == '-')
cnt = 0;
if (s[i] == 'o')
{
cnt++;
ans = max(ans, cnt);
}
}
cout << ans << "\n";
return 0;
}
交互题。
首先输入一个交互器给出的 。交互器想好了一个确定的字符串 ,保证 只包含 0
和 1
,且第一个字符是 0
,最后一个字符是 1
。
你可以最多提 20
个问题,每次询问一个位置,交互器会回答你这个位置的字符。
最后你需要输出哪个位置 满足 。
数据范围:
看这询问数量上限和字符串长度,很容易想到是二分。
显然可以用区间 框定 的范围。初始范围是 。
注意交互题不要忘了刷新缓冲区。
#include <bits/stdc++.h>
using namespace std;
int query(int pos)
{
cout << "? " << pos << "\n";
cout.flush();
cin >> pos;
return pos;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int l = 1, r = n;
while (r - l + 1 > 2)
{
int mid = (l + r) / 2;
int Smid = query(mid);
if (Smid == 0)
l = mid;
else
r = mid;
}
cout << "! " << l << "\n";
cout.flush();
return 0;
}
/*
Judge:
S=0xxxxxxx1
Me:
知道长度
问20个位置的0/1
最终回答一个 p:Sp!=Sp+1
*/
给定一个包含 个点, 条边的简单联通无向图。
需要你给这 个点进行黑白染色。
其中有 个特殊点:。这些点各有一个要求的距离 。
你的染色方案需要满足“所有黑点到 的距离中,最短的那个距离刚好是 ”。
数据范围:
显然每个 只是告诉我们距离 在 的点不允许有黑点。
这个数据范围,直接暴力算距离,暴力标记不允许染黑的点,最后判断是否有解就好了。
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> e[2005];
int k;
int p[2005], d[2005];
int vis[2005]; // vis[j] 上次是谁访问j
int dis[2005][2005]; // i到j的最短距离
queue<int> q;
bool black[2005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
cin >> k;
for (int i = 1; i <= k; i++)
cin >> p[i] >> d[i];
// 预处理距离
for (int i = 1; i <= n; i++)
{
q.push(i);
vis[i] = i;
dis[i][i] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
for (auto v : e[u])
{
if (vis[v] < i)
{
vis[v] = i;
dis[i][v] = dis[i][u] + 1;
q.push(v);
}
}
}
}
// 标记不可变黑的点
for (int i = 1; i <= n; i++)
black[i] = true; // 可以黑
for (int i = 1; i <= k; i++)
for (int j = 1; j <= n; j++)
if (dis[p[i]][j] < d[i])
black[j] = false; // 不准黑
// 找寻方案
for (int i = 1; i <= k; i++)
{
bool flag = false; // i 能不能找到小黑点
for (int j = 1; j <= n; j++)
{
if (black[j] && dis[p[i]][j] == d[i])
{
flag = true;
break;
}
}
if (!flag)
{
cout << "No\n";
return 0;
}
}
cout << "Yes\n";
for (int i = 1; i <= n; i++)
cout << black[i];
cout << "\n";
return 0;
}