Codeforces Round #475 Div. 2 A B C D

A - Splits
に言及
1つの正の整数をいくつかの正の整数の和に分割し、最初の数字と同じ数の個数がこの分割の重みになります.
問(n)のすべての分割の異なる重みの可能な個数.
構想
すべて1に分解し、2つの1を1つの2に交換します.つまり、2つの数を1つ増やします.
全部で1+n/2種あります.
Code

#include 
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
int main() {
    int n;
    scanf("%d", &n);
    printf("%d
", n/2+1);
    return 0;
}

B - Messages
に言及
メッセージを受信した時刻のメッセージ価値はAであり,その後毎秒B減少する.ある時点であるメッセージを読むと、そのメッセージの価値が得られる.また、毎秒得る固定収益は、現在のメッセージ数*Cである.
最大収益を聞く.
構想
問題の意味を理解すればいい:各新聞の価値、すなわち毎秒Bを減らし、Cを増やす.
そのため、BとCを比較するだけで、Bが大きいと、すべての新聞がすぐに読みます.さもないと全部最後まで積み上げて読みます.
Code

#include 
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
int main() {
    int n,a,b,c,T;
    scanf("%d%d%d%d%d",&n,&a,&b,&c,&T);
    int x, sum=0;
    F(i, 0, n) scanf("%d", &x), sum += x;
    LL ans = n*a;
    if (c>b) ans += 1LL*(c-b)*(n*T-sum);
    printf("%d
", ans);
    return 0;
}

C - Alternating Sum
に言及
演算(sumlimits_{i=0}^{n}s_{i}a^{n-i}b^{i})は、係数(s)は(pm 1)のみをとる、周期関数であり、周期は(T=frac{n+1}{k})である.
構想
すなわち(sumlimits_{i=0}^{k-1}s_{i}a^{n-i}b^{i}cdotfrac{q^{frac{n+1}{k}-1}{q-1})を計算する、特判(q=1)に注意する.
Code

#include 
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
const LL mod = 1e9+9;
LL poww(LL a, LL b) {
    LL ret = 1;
    while (b) {
        if (b & 1) (ret *= a) %= mod;
        (a *= a) %= mod;
        b >>= 1;
    }
    return ret;
}
inline LL mul(LL a, LL b) { return a * b % mod; }
inline LL add(LL a, LL b) { return (a+b+mod) % mod; }
#define maxn 100010
char s[maxn];
int main() {
    int n, a, b, k;
    scanf("%d%d%d%d", &n, &a, &b, &k);
    scanf("%s", s);
    LL aa = poww(a, n), bb = 1, inva = poww(a, mod-2), ans = 0;
    F(i, 0, k) {
        int sign = s[i]=='+' ? 1 : -1;
        ans = add(ans, sign*mul(aa, bb));
        aa = mul(aa, inva);
        bb = mul(bb, b);
    }
    LL q = mul(poww(b, k), poww(inva, k));
    int cnt = (n+1) / k;
    if (q == 1) ans = mul(ans, cnt);
    else ans = mul(ans, mul(poww(q, cnt)-1, poww(q-1, mod-2)));
    printf("%I64d
", ans);
    return 0;
}

D - Destruction of a Tree
に言及
ツリー上で点を削除し、その点の度数が偶数である場合にのみ削除し、図中のすべての点を削除できるかどうかを尋ね、操作シーケンスを与えるように要求します.
構想
葉から下から上へ考えると、明らかに葉は直接削除できないので、葉を削除するには必ず父のノードを削除した後に行う必要があります.
父親は直接削除できますか?奇数人の子供(削除されていない)がいる場合は、ノード(関連するエッジが奇数人の子供+父親に続く偶数のエッジであるため)を直接削除し、以前削除されていなかった部分を下に削除することができます.そうしないと、その削除作業は必ず父親が削除された後に行われます.(注意、リーフノードもこの特性に合致する.リーフノードの子供数は0が偶数であるため)
従って、dfsは、各ノードに何人の子供が削除されていないかを下から上へ考える.奇数個であれば、ノードを削除し(子供を削除しながら)、親ノードの度数への寄与を無視します.そうでなければ、上へ進みます.
Code

#include 
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 200010
using namespace std;
typedef long long LL;
struct Edge {
    int to, ne;
}edge[maxn<<1];
int ne[maxn], tot, rt;
bool flag[maxn];
vector ans;
void add(int u, int v) {
    edge[tot] = {v, ne[u]};
    ne[u] = tot++;
}
void collect(int u, int fa) {
    ans.push_back(u);
    flag[u] = true;
    for (int i = ne[u]; ~i; i = edge[i].ne) {
        int v = edge[i].to;
        if (v == fa || flag[v]) continue;
        collect(v, u);
    }
}
int dfs(int u, int fa) {
    int tot = 0;
    for (int i = ne[u]; ~i; i = edge[i].ne) {
        int v = edge[i].to;
        if (v == fa) continue;
        tot += dfs(v, u);
    }
    if ((u==rt&&!(tot&1)) || (u!=rt&&tot&1)) collect(u, fa);
    return !(tot&1);
}
int main() {
    memset(ne, -1, sizeof ne);
    int n, x;
    scanf("%d", &n);
    F2(i, 1, n) {
        scanf("%d", &x);
        if (!x) rt = i;
        else add(i, x), add(x, i);
    }
    if (dfs(rt, -1)) {
        puts("YES");
        for (auto x : ans) printf("%d
", x);
    }
    else puts("NO");
    return 0;
}

転載先:https://www.cnblogs.com/kkkkahlua/p/8970242.html