小白月赛43

比赛链接

A.满意的数字

由题：x[m] == n 且 1 <= ⌊(1+m)/2⌋ <= m一定成立

所以x[⌊(1+m)/2⌋]一定是x[m]的因子，所以每个数字都是满意的数字。

#include <iostream>
using namespace std;
 
int main (void) {
    int t; cin >> t;
    while(t--) {
        int n; cin >> n; cout << n << endl;
    }
    return 0;
}

B.牛牛变魔术

两个瓶子数值分别为A,B, 所以当前不变化可由这两个数值组合出A || B

变化一次可以组合出[0, 2, 4, 6, ..., (A + B)<<1]

#include <iostream>
using namespace std;
using i64 = long long;
 
int main(void) {
    int t; cin >> t;
    while(t--) {
        i64 A, B ,C;
        cin >> A >> B >> C;
        if(A == C || B == C) {
            puts("0"); continue;
        }
        if(C&1) puts("-1");
        else{
            int ans = 0;
            while(A + B < C/2) {
                A = A << 1; B = B << 1;
                ans ++;
            }
            cout << ans + 1 << '\n';
        }
    }
    return 0;
}

C.木棍游戏

暴力搜索：每根棍子有四种选择，[0(不选), 1(当第一条边), 2(当第二条边), 3(当第三条边)]时间复杂度为O(4^n)

三角形面积公式：q = (a + b + c) / 2 s = sqrt(q * (q - a) * (q - b) * (q - c))

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define float double

const int N = 1<<17;
int a[8];
float w[4], ans;
int n;

float func(float a, float b, float c) {
    float p = 0.5 * (a + b + c);
    return sqrt(p * (p - a) * (p - b) * (p - c));
}

bool check(float a, float b, float c) {
    if(a + b <= c || a + c <= b || b + c <= a) return false;
    return true;
}

int st[10];
void dfs(int u) {
    if(u >= n) {
        w[1] = w[2] = w[3] = 0.0;
        for(int i = 0; i < n; i++) {
            w[st[i]] += a[i];
        }
        if(check(w[1], w[2], w[3]))
            ans = max(ans, func(w[1], w[2], w[3]));
        return ;
    }
    for(int i = 0; i < 4; i++) {
        st[u] = i;
        dfs(u+1);
    }
}

int main (void) {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    ans = -1;
    dfs(0);
    if(ans < 0.1) puts("-1");
    else printf("%.1lf\n", ans);
    return 0;
}

D.有趣的区间

所有区间的数量C(n, 2) = (n) * (n + 1) / 2

用所有区间的数量减去区间中只有偶数的区间数量得到答案

只有偶数的区间的数量为每个连续偶数的区间长度len 的 C(len, 2) 的累加和

#include <iostream>
using namespace std;

long long n, ans;

int main (void) {
    scanf("%lld", &n);
    ans = n * (n + 1) / 2;
    int l = 1;
    for(int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        if(x % 2 == 1) l = i + 1;
        else ans -= i - l + 1;
    }
    cout << ans;
    return 0;
}

E.满意的集合

f[i][j]代表只使用[1, i]得到的mod 3 == j的方案数

暴力代码O(k*n)

f[0][0] = 1;
    for(int i = 1; i <= 9; i++) {
        for(int j = 0; j <= a[i]; i++) {
            for(int mod = 0; mod < 3; mod++) {
                f[(i * j + mod) % 3] += f[i - 1][mod];
                f[(i * j + mod) % 3] %= MOD;
            }
        }
    }

发现有规律为：

1*num%3==4*num%3==7*num%3==...==(3*k+1)*num%3

2*num%3==5*num%3==8*num%3==...==(3*k+2)*num%3

0*num%3==3*num%3==6*num%3==...==(3*k+0)*num%3(==0)

两种组合的所有数字相加mod 3 等于 两种组合的mod 3相加再mod 3,所以状态转移可变成f[i][(now_mod+last_mod)%3] += f[i - 1][last_mod]

#include <iostream>
using namespace std;
using i64 = long long;

const int MOD = 1e9 + 7;
int a[10];
i64 f[10][3];

int main (void) {
    for(int i = 1; i <= 9; i++) cin >> a[i];
    f[0][0] = 1;
    for(int i = 1; i <= 9; i++) {
        int now_mod1 = i % 3, now_mod2 = 2 * i % 3, now_mod3 = 0;
        int g1 = (a[i] + 2) / 3, g2 = (a[i] + 1) / 3, g3 = a[i] / 3 + 1;
        for(int last_mod = 0; last_mod < 3; last_mod++) {
            f[i][(now_mod1 + last_mod) % 3] += f[i - 1][last_mod] * g1;
            f[i][(now_mod1 + last_mod) % 3] %= MOD;
            f[i][(now_mod2 + last_mod) % 3] += f[i - 1][last_mod] * g2;
            f[i][(now_mod2 + last_mod) % 3] %= MOD;
            f[i][(now_mod3 + last_mod) % 3] += f[i - 1][last_mod] * g3;
            f[i][(now_mod3 + last_mod) % 3] %= MOD;
        }
    }
    cout << f[9][0] << endl;
    return 0;
}

F.全体集合

染色法：对所有点使用([黑，白]，[1, 2])两种颜色染色，约定相邻点颜色不能相同。

如果可以全体集合，说明最后时刻所有人所在点的颜色相同。

如果颜色结果不能满足约定条件(相邻点颜色不能相同)则可以集合(必然能到达所有人所在点颜色相同的状态)。

如果可以满足约定条件则还需要判断初始状态时，所有人所在点的颜色是否相同,若相同则每一步都可以到达所有人所在点颜色相同的状态，所以可到达全体集合状态。若存在不相同则无论进行怎样的方式移动，必然每一步的状态都存在不相同颜色的点，所以必然不能全体集合。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 2 * 1e5 + 10, M = 5 * 1e5 + 10;
int idx, n, m, k, e[M<<1], ne[M<<1], h[N], p[N], color[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool dfs(int u, int c) {
    color[u] = c;
    for(int i = h[u]; ~i; i = ne[i]) {
        int to = e[i];
        if(!color[to]) {
            if(!dfs(to, 3 - c)) return false;
        } else if(color[to] == color[u]) return false;
    }
    return true;
}

int main (void) {
    memset(h, -1, sizeof h);
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= m; i++) {
        int a, b; scanf("%d%d", &a, &b); add(a, b); add(b, a);
    }
    for(int i = 1; i <= k; i++) scanf("%d", &p[i]);
    
    bool flag = true;
    for(int i = 1; i <= n && flag; i++)
        if(!color[i]) if(!dfs(i, 1)) flag = false;
    if(flag) {
        int c = color[p[1]];
        for(int i = 2; i <= k && flag; i++)
            if(color[p[i]] ^ c) flag = false;
        puts(flag ? "YES" : "NO");
    } else puts("YES");
    return 0;
}