A - Treasure Chest
题目大意
给定一个由' | ' ' * '和' . '组成的字符串, 并且保证一定有1个' * '和2个' | ', 检查' * '是否在两个' | '之间;
解题思路
签到题不多嗦了;
但是这里可以注意一下string的find函数; find(char c, int pos)意为从第pos个字符开始找字符c, 返回值是int, pos可以不写, 默认从开头开始找; 而这里我们用到了两个拓展的find函数: find_first_of(char c)和find_last_of(char c), 意为字符c第一次出现的位置和最后一次出现的位置;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5+10;
int n, m,idx;
signed main() {
string s;
cin >> n >> s;
auto a = s.find_first_of('|');
auto b = s.find_last_of('|');
auto c = s.find('*');
if (c >= a && c <= b) {
cout << "in";
}
else cout << "out";
return 0;
}
B - Trick Taking
题目大意
有n个人玩游戏, 每个人都有各自的颜色和序号; 现在给定一个颜色m, 如果有人的颜色也是m, 那么赢家就是这些人里面序号最大的; 如果没有人的颜色是m, 那么赢家就是与1号玩家颜色相同的玩家中序号最大的, 注意1号玩家也有可能是赢家
解题思路
签到题不多嗦了;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5+10;
int n, m,idx;
vector<int> v;
int r[N], c[N];
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> c[i];
if (c[i] == m) v.push_back(i);
}
for (int i = 1; i <= n; i++) cin >> r[i];
int maxn = 0;
if (v.size()) {
for (int x : v) {
if (r[x] > r[maxn]) maxn = x;
}
cout << maxn;
}
else {
for (int i = 1; i <= n; i++) {
if (c[i] == c[1]) {
if (r[i] > r[maxn]) maxn = i;
}
}
cout << maxn;
}
}
C - Dango
题目大意
给定一个只由' o '和' - '组成的字符串, 先定义一种字符串s, s的开头或结尾其中一个必须是' - ', 并且s的长度取决于' o '的个数, 例如" oooo- "的长度为4; 现在从给定的字符串里面找到符合字符串s的要求的子串中最长的长度;
解题思路
以' - '为节点作为结算即可; 算是个签到题;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5+10;
int n, m,idx;
signed main() {
cin >> n;
string s;
cin >> s;
int maxn = 0;
bool f = false;
for (int i = 0; i < n; i++) {
if (s[i] == 'o') idx++;
else {
f = true;
maxn = max(maxn, idx);
idx = 0;
}
}
maxn = max(maxn, idx);
if (maxn == 0) f = false;
if (f) cout << maxn;
else cout <<-1;
}
D - Find by Query
题目大意
本题是一个交互题, 现有一个由01组成长度为n的字符串, 并且s1=0, sn=1; 现在可以最多给出20次询问, 输出" ? x ", x是1~n中的一个, 然后会给出sx的值; 现在需要我们找出一个位置p, 满足sp不等于s(p+1);
解题思路
这还是第一次遇到交互题, 看了看题解发现交互题就是你按规定样式输出后, 网站会根据你的输出, 把对应结果输入到缓冲区, 此时我们用直接用cin输入后就可以得到想要的答案;
这个题是一个二分题, 因为开头是0, 结尾是1, 所以我们先询问一个位置x, 如果为1; 则在1~x-1中一定有一个位置p使得sp=0, s(p+1)=1; 因为n是1e5级别的, 所以20次一定能找到最后答案;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5+10;
int n, m,idx;
signed main() {
cin >> n;
int l = 1, r = n;
while (l < r) {
int mid = l + r+1 >> 1;
cout << "? " << mid << endl;
int res;
cin >> res;
if (res == 1) r = mid-1;
else l = mid;
}
cout << "! " << l << endl;
}
E - Nearest Black Vertex
题目大意
给定一个无向图, 有n个点和m条边; 现在我们需要对其中的点进行黑白两个颜色的染色; 规则如下: 一是至少有一个黑点; 二是题目会给出k组限制, 每组限制包括一个点a和一个距离b, 意为距离a最近的黑点与a之间的距离必须为b; 输出形式以01序列表示, 0表示白点, 1表示黑点;
解题思路
因为n只有2000, 所以可以考虑用bfs; 对于每次限制, 我们都可以用一次bfs, 将与点a距离小于b的点标记一下; 之后我们再对每次限制用bfs来找有没有距离等于b且未被标记的点, 如果有则该点满足条件可以被染为黑色, 否则就不存在合法的染色方式
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2100;
int h[N], e[N], ne[N], d[N];
bool st[N];
int n, m, k, idx;
vector<PII> v;
map<int, int>mp;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void bfs_1(int a, int b) {
memset(d, 0x3f, sizeof d);
memset(st, false, sizeof st);
queue<int> q;
q.push(a);
d[a] = 0;
st[a] = true;
if (d[a] < b) mp[a] = 1;
while (q.size()) {
int x = q.front();
q.pop();
for (int i = h[x]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
d[j] = d[x] + 1;
if (d[j] < b) mp[j] = 1;
q.push(j);
st[j] = true;
}
}
}
}
bool bfs_2(int a, int b) {
bool f = false;
memset(d, 0x3f, sizeof d);
memset(st, false, sizeof st);
queue<int> q;
q.push(a);
st[a] = true;
d[a] = 0;
if (d[a] == b && (mp[a] == 0 || mp[a] == 2)) {
f = true;
mp[a] = 2;
}
while (q.size()) {
int x = q.front();
q.pop();
for (int i = h[x]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
d[j] = d[x] + 1;
q.push(j);
st[j] = true;
if (d[j] == b && (mp[j] == 0 || mp[j] == 2)) {
f = true;
mp[j] = 2;
}
}
}
}
if (f) return true;
else return false;
}
signed main() {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
cin >> k;
bool f = true;
for (int i = 1; i <= k; i++) {
int a, b;
cin >> a >> b;
v.push_back({ a,b });
}
for (auto t : v) {
bfs_1(t.first, t.second);
}
for (auto t : v) {
if (!bfs_2(t.first, t.second)) {
f = false;
break;
}
}
if (f) {
cout << "Yes" << endl;
if (mp.size() == 0) {
for (int i = 1; i <= n; i++) {
if (i == 1) cout << 1;
else cout << 0;
}
}
else {
for (int i = 1; i <= n; i++) {
if (mp[i] == 2) cout << 1;
else cout << 0;
}
}
}
else cout << "No" << endl;
}
F - Square Subsequence
题目大意
待定.....
解题思路
待定....
神秘代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
int w[N],d[N];
int n,m,idx;
bool st[N];
vector<int> v[N];
int dijkstra(){
memset(d,0x3f,sizeof d);
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,1});
d[1]=0;
while(heap.size()){
auto t=heap.top();
heap.pop();
int x=t.second;
if(st[x]) continue;
st[x]=true;
for(int p:v[x]){
if(d[p]>d[x]+w[p]){
d[p]=d[x]+w[p];
heap.push({d[p],p});
}
}
}
if(d[m]==0x3f3f3f3f) return -1;
else return d[m]-1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int k;
cin>>k;
w[i+m] =1;
for(int j=1;j<=k;j++){
int x;
cin>>x;
v[x].push_back(i+m);
v[i+m].push_back(x);
}
}
cout<<dijkstra();
return 0;
}