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;
}
- Beginner AtCoder Contest 299 abcbeginner atcoder contest 299 beginner atcoder contest abc atcoder abcdefg abc 299 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328