AtCoder Beginner Contest 228
A – On and Off
思路分析：
- 如果s < t说明是顺序的，所以只要x小于t并且大于等于s即可。
- 如果s > t说明是逆序的，所以只要x >= s或者x < t即可。
代码如下：
#include
using namespace std;
int main()
{
int s, t, x;
cin >> s >> t >> x;
if (s < t)
{
cout << (s
B – Takahashi’s Secret
思路分析：
- 这题我想的是dfs跑一遍，如果之前跑过这个点那么就退出即可，dfs一次就加一次。
代码如下：
#include
using namespace std;
const int maxn = 1e5 + 10;
vector e[maxn];
bool vis[maxn];
int ans;
void dfs(int u)
{
vis[u] = 1;
ans++;
for (auto x : e[u])
{
if (vis[x])
{
break;
}
else
{
dfs(x);
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, x;
cin >> n >> x;
for (int i = 1; i > v;
e[i].push_back(v);
}
dfs(x);
cout << ans << endl;
return 0;
}
C – Final Day
思路分析：
- 这个题目其实就是先给你每个同学前三天的成绩，问你四天考试结束之后是否能够获得第K名。
- 首先我们贪心，对于当前的同学，我们让他最后一天得到300分，其他的同学得到0分，这样的话我们就可以判断了，假如我都给这位同学300分了，其他同学都给的是0分，他如果都比第K名同学分数少的话，那么他就不可能得到第K名。
代码如下：
#include
using namespace std;
const int maxn = 1e5 + 10;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
k--;
vector sum(n);
vector val(n);
for (int i = 0; i < n; i++)
{
int tmp = 0;
int a, b, c;
cin >> a >> b >> c;
tmp = a + b + c;
sum[i] = tmp;
val[i] = tmp + 300;
}
sort(sum.begin(), sum.end(), greater());
for (int i = 0; i < n; i++)
{
if (val[i] >= sum[k])
{
cout << "Yes" << endl;
}
else
cout << "No" << endl;
}
return 0;
}
D – Linear Probing
思路分析：
- 这题一开始没想到是用并查集，就用vector乱搞了2发RE。
- 用并查集怎么做呢？首先并查集维护的是下一个-1出现的位置，那么在我们每次1操作中，把当前的位置替换后，我们就让它的下标加上1再模上1 << 20就可以得到下一个-1出现的位置了，这样的话时间复杂度O(1)。
代码如下：
#include
using namespace std;
#define ll long long
const ll maxn = 1 << 20;
ll val[maxn];
ll fa[maxn];
void init()
{
for (ll i = 0; i < maxn; i++)
{
fa[i] = i;
val[i] = -1;
}
}
ll find(ll x)
{
return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init();
ll q;
cin >> q;
while (q--)
{
ll opr, x;
cin >> opr >> x;
if (opr == 1)
{
ll y = find(x % maxn);
val[y] = x;
fa[y] = (y + 1) % maxn;
}
else if (opr == 2)
{
cout << val[x % maxn] << endl;
}
}
return 0;
}
Original: https://www.cnblogs.com/csu-yuuki/p/15584687.html
Author: zhy-cx
Title: AtCoder Beginner Contest 228
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/713095/
转载文章受原作者版权保护。转载请注明原作者出处！