AtCoder Beginner Contest 240
比赛链接
在这强烈dls的视频讲解
dls的视频讲解及解题过程
A - Edge Checker
Problem Statement
In the figure shown in the image below, are the points numbered
a and b directly connected by a line segment?
Input
Input is given from Standard Input in the following format:
a b
Output
If the points numbered
a and b are directly connected by a line segment, print Yes; otherwise, print No.
The judge is case-sensitive: be sure to print uppercase and lowercase letters correctly.
思路
看两个数字是否在同一条线上。
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 0x3f3f3f3f
#define PII pair<int, int>
#define rep(i, l, r) for (int i = l; i < r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define rep2(i, l, r) for (int i = l; i * i <= r; i++)
#define rep3(i, l, r) for (LL i = l; i * i * i <= r; i++)
#define Min(a, b) a > b ? b : a
#define Max(a, b) a > b ? a : b
#define endl '\n'
#define debug "-----"
using namespace std;
typedef long long LL;
const LL mod = 1e9;
const int N = 1e6 + 10, M = 1050;
LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
int main()
{
IOS;
int a,b;
cin >> a >> b;
if( abs(a-b)==1 || ( a==10&&b==1 ) || (b==10&&a==1) )
cout << "Yes";
else cout << "No";
return 0;
}
B - Count Distinct Integers
思路:
找不同的数字有多少个
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 0x3f3f3f3f
#define PII pair<int, int>
#define rep(i, l, r) for (int i = l; i < r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define rep2(i, l, r) for (int i = l; i * i <= r; i++)
#define rep3(i, l, r) for (LL i = l; i * i * i <= r; i++)
#define Min(a, b) a > b ? b : a
#define Max(a, b) a > b ? a : b
#define endl '\n'
#define debug "-----"
using namespace std;
typedef long long LL;
const LL mod = 1e9;
const int N = 1e6 + 10, M = 1050;
LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
map<int,int>mp;
int ans = 0;
int main()
{
IOS;
int n;
cin >> n;
rep( i , 1 , n+1 ){
int t; cin >> t;
mp[t]++;
if( mp[t] == 1 ) ans++;
}
cout << ans;
return 0;
}
C - Jumping Takahashi
思路
当初自己写这道题的时候用了DFS结果超时了。一直想到了结束,自己还是太菜了QAQ。
在这推荐下dls Atcoder的视频讲解
dls的题解
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 0x3f3f3f3f
#define PII pair<int, int>
#define rep(i, l, r) for (int i = l; i < r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define rep2(i, l, r) for (int i = l; i * i <= r; i++)
#define rep3(i, l, r) for (LL i = l; i * i * i <= r; i++)
#define Min(a, b) a > b ? b : a
#define Max(a, b) a > b ? a : b
#define endl '\n'
#define debug "-----"
using namespace std;
typedef long long LL;
const LL mod = 1e9;
const int N = 1e6 + 10, M = 1050;
LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
bitset<10001>f;
int main()
{
IOS;
f[0] = 1;
int n,x;
cin >> n >> x;
rep( i , 1 , n+1){
int a,b;
cin >> a >> b;
f = ( f<<a )|( f<<b );
}
f[x]?cout << "Yes":cout << "No";
return 0;
}
D - Strange Balls
思路:
模拟及一些优化,感觉有点类似kmp的next
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 0x3f3f3f3f
#define PII pair<int, int>
#define rep(i, l, r) for (int i = l; i < r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define rep2(i, l, r) for (int i = l; i * i <= r; i++)
#define rep3(i, l, r) for (LL i = l; i * i * i <= r; i++)
#define Min(a, b) a > b ? b : a
#define Max(a, b) a > b ? a : b
#define endl '\n'
#define debug "-----"
using namespace std;
typedef long long LL;
const LL mod = 1e9;
const int N = 1e6 + 10, M = 1050;
LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
int s[N],stk[N];
int hh;
int main()
{
IOS;
int n;
cin >> n;
rep( i , 1 , n+1 ){
int t;
cin >> t;
stk[++hh] = t;
if( hh == 1 || stk[hh]!=stk[hh-1] ) s[hh] = 1;
else s[hh] = s[hh-1]+1;
if( s[hh] == t ) hh -= t;
cout << hh << endl;
}
return 0;
}