A题都没做出来(被自已菜晕
A. Ternary Decomposition
A - Ternary Decomposition (atcoder.jp)
题意
给定一个正整数\(N\),问是否存在\(K\)个整数,使得\(N=3^{m_1}+3^{m_2}+...+3^{m_k}\)
思路
首先对于一个正整数\(N\),最多有\(N\)个整数使得正式成立,即\(m_i\)全为0。再对\(N\)进行三进制拆分,可得到最少使得原式成立的个数。
在三进制拆分后,所有指数不为0的项都能再拆分为三项,使项数加二。因此,\(k\)如果在最大值和最小值之间,并且奇偶性与\(N\)相同就存在,否则不存在。
代码
void solve() {
ll k, n;
cin >> n >> k;
ll mx = n, mn = 0;
while(n) {
mn += n % 3;
n /= 3;
}
if(k >= mn && k <= mx && k % 2 == mx % 2) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
B. Switching Travel
B - Switching Travel (atcoder.jp)
题意
给定一个无向图,每个节点为白色或黑色。只有当边的两端节点颜色不一样时,才能移动,且每离开一个节点,该节点的颜色就会变成另一种颜色。可以随便选择一个节点作为起点,求能否回到起点。
思路
如果图中存在一个环,起点和终点颜色相同,其余节点颜色交替出现,则说明能回到起点。
遍历边,如果一条边的两端节点颜色不同,合并到一个集合中。之后再遍历一次边,如果边两端的节点颜色相同,则查询它们是否在同一集合中,如果是,则说明存在一个满足条件的环。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p;
DSU(int n) : p(n) {iota(p.begin(), p.end(), 0);}
int find(int x) {
while(x != p[x]) x = p[x] = p[p[x]];
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if(x == y) return false;
p[y] = x;
return true;
}
bool same(int x, int y) {return find(x) == find(y);}
};
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<pair<int, int>> e(m);
for(int i = 0; i < m; i++) {
cin >> e[i].first >> e[i].second;
}
vector<int> c(n + 1);
for(int i = 1; i <= n; i++) {
cin >> c[i];
}
DSU D(n + 1);
for(int i = 0; i < m; i++) {
if(c[e[i].first] != c[e[i].second]) {
D.merge(e[i].first, e[i].second);
}
}
for(int i = 0; i < m; i++) {
if(c[e[i].first] == c[e[i].second] && D.same(e[i].first, e[i].second)) {
cout << "Yes\n";
return 0;
}
}
cout << "No\n";
return 0;
}
c. Reversible Card Game
C - Reversible Card Game (atcoder.jp)
题意
给定若干张牌,牌的正反两面写有数字。Alice的回合会把场上某一张牌翻转,Bob的回合会把场上一张牌拿走并获得该牌朝上的数字。Alice想要Bob获得的数字之和最小,Bob想要获得的数字之和最大。求Bob最终能获得多少数字。
思路
Bob到最后会拿走所有的牌,为了使Bob获得的值减少,Alice每次翻转正面减反面差值最大的牌,而Bob会拿走差值最大的牌不让Alice翻,因此用一个优先队列模拟即可。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct node {
int a, b;
bool operator <(const node &T) const {return a - b < T.a - T.b;}
};
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
priority_queue<node> q;
for(int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
q.push({a, b});
}
ll ans = 0;
while(!q.empty()) {
int x = q.top().a, y = q.top().b;
q.pop();
q.push({y, x});
ans += q.top().a;
q.pop();
}
cout << ans << "\n";
return 0;
}
- AtCoder Regular Contest 164atcoder regular contest 164 atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 167 atcoder regular contest builder subsegments atcoder regular contest inversion atcoder regular contest