Codeforces Round #407 (Div. 2)#
A. アナスタシアと小石#
貪欲に取れば大丈夫です
ルールは各ポケットには 1 種類の小石しか入れられず、すべての石を取り切る必要があります
つまり、できるだけ詰め込むだけで終わりです
要するに貪欲法です
#include <cstdio>
#include <cstdlib>
using namespace std;
/*
* 20/4=5..0
* 13/4=3..1
*/
int main() {
// freopen("input.txt", "r", stdin);
int n, k;
int a[100005];
int cnt = 0;
scanf("%d %d\n", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (int i = 0; i < n;) {
if (a[i] <= 0) {
i++;
continue;
}
if (a[i] >= (k + k)) {
cnt += a[i] / (k + k);
a[i] %= (k + k);
} else if (a[i] > k) {
a[i]=0;
cnt++;
}else {
cnt++;
a[i]-=k;
a[i+1]-=k;
}
}
printf("%d\n", cnt);
}
B. マーシャと幾何学的抑圧#
簡単に言えば unordered_set と暴力的なシミュレーションを使えば解決できます
int が足りないことを忘れないでください
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
using namespace std;
unordered_set<long long> s;
int main() {
// freopen("input.txt", "r", stdin);
long long b, q, l, m;
scanf("%I64d%I64d%I64d%I64d", &b, &q, &l, &m);
for (int i = 0; i < m; i++) {
long long tmp;
scanf("%I64d", &tmp);
s.insert(tmp);
}
if (abs(b) > l) {
printf("0\n");
return 0;
}
if (b == 0) {
if (s.find(0) != s.end()) {
printf("0\n");
} else {
printf("inf\n");
}
return 0;
}
if (q == 0) {
if (s.find(0) != s.end()) {
if (s.find(b) != s.end())
printf("0\n");
else
printf("1\n");
} else {
printf("inf\n");
}
return 0;
}
if (q == 1) {
if (s.find(b) != s.end()) {
printf("0\n");
} else {
printf("inf\n");
}
return 0;
} else if (q == -1) {
if (s.find(b) != s.end() && s.find(-b) != s.end()) {
printf("0\n");
} else {
printf("inf\n");
}
return 0;
}
int cnt = 0;
for (; abs(b) <= l; b *= q) {
if (s.find(b) != s.end()) {
continue;
}
cnt++;
}
printf("%d\n", cnt);
}
C. 再び関数#
この問題は思考問題と見なされるべきです
まず配列の差分前処理を行い、新しい配列を得ます
次にこの配列を使って正負変換を行います
+ - + - + - +
- + - + - + -
合計でこの 2 種類の配列しかなく、最大化の部分列を求めれば終了です
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
using namespace std;
int a[100009];
int s[100008];
int main() {
// freopen("input.txt", "r", stdin);
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (int i = 0; i < n - 1; i++) {
s[i] = abs(a[i] - a[i + 1]);
}
int f=1;
long long res = 0, now = 0, now2 = 0;
for (int i = 0; i < n - 1; i++) {
int current = s[i] * f;
int current2 = s[i] *(-f);
now += current;
now2 += current2;
if (now < 0)
now = 0;
if(now2<0)
now2=0;
res = max(max(res, now), now2);
f *= -1;
}
printf("%I64d\n", res);
}
D. 奇妙な旅#
この問題も思考問題とオイラー回路です
往復 2 回は 1 つの辺にもう 1 つの辺を追加することを意味します
オイラー回路の奇数度点は 0 または 2 のみです
- 何の共通点もない 2 つの辺を削除 = オイラー回路ではない（奇数度点が 4 つあるため）
- 共通点のある 2 つの辺を削除 = オイラー回路である（奇数度点が 2 つあるため）
- 2 つの自己ループを削除 = オイラー回路である（奇数度点が 0 個あるため）
- 1 つの自己ループと任意の 1 つの辺を削除 = オイラー回路である（奇数度点が 2 つあるため）
これでおおよそ半分は解決しました
最初に連結グラフを判定することを忘れずに、disjoint set を利用します
次に数量を計算します
共通点のある 2 つの辺を削除する場合、各点を列挙し、その点の次数の 2 の組み合わせを取ることができます（すべての次数の辺の合計を列挙）
2 つの自己ループを削除する場合は、すべての自己ループの組み合わせの合計です
1 つの自己ループと任意の 1 つの辺を削除する場合は、すべての自己ループ × すべての辺（つまり自己ループと辺の組み合わせ）です
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <set>
typedef long long ll;
using namespace std;
struct edge {
int x, y;
};
int deg[1000009] = {0};
edge edges[1000009];
int p[1000006];
int vis[1000006] = {0};
int n, m;
int getf(int x) {
return x == p[x] ? x : (p[x] = getf(p[x]));
}
void _union(int x, int y) {
x = getf(x), y = getf(y);
p[x] = y;
}
bool connect() {
for (int i = 0; i < n; i++) {
p[i] = i;
}
for (int i = 0; i < m; i++) {
_union(edges[i].x, edges[i].y);
}
set<int> bag;
for (int i = 0; i < n; i++) {
if (!vis[i])continue;
bag.insert(getf(i));
}
return bag.size() <= 1;
}
ll loops = 0;
int main() {
// freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
int x, y;
scanf("%d %d", &x, &y);
x--;
y--;
edges[i].x = x;
edges[i].y = y;
vis[x] = 1;
vis[y] = 1;
if (x == y) {
loops++;
} else {
deg[x]++;
deg[y]++;
}
}
if (!connect()) {
printf("0\n");
return 0;
}
ll cnt = 0;
cnt += loops * (m - loops);
cnt += loops * (loops - 1) / 2;
for (int i = 0; i < n; i++) {
cnt += (ll) (deg[i]) * (deg[i] - 1) / 2;
}
printf("%I64d", cnt);
}