9月24日YLOI总结

题目做过，真棒！
分数：100 + 100 + 100 + 0 = 300

本场考试个人评价好，就是T4细节错误，导致暴力没拿到分，以后做题还需更加细心。

用Code凑个字数吧

T1 100pts答案

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int Mod = 998244353;
const int MAX_N = 250;
int n, dp[MAX_N * MAX_N];
LL ans = 1;

LL FastPow(LL a, LL k) {
    LL res = 1;
    while(k) {
        if(k & 1) res = (res * a) % Mod;
        a = (a * a) % Mod;
        k >>= 1;
    }
    return res;
}

int main() {
    freopen("set.in", "r", stdin);
    freopen("set.out", "w", stdout); 
    
    scanf("%d", &n);
    dp[0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = n * (n + 1) / 2; j >= i; j--) {
            dp[j] = (dp[j] + dp[j - i]) % (Mod - 1);
        }
    }
    for(int i = 1; i <= n * (n + 1) / 2; i++) {
        ans = (ans * FastPow(i, dp[i])) % Mod;
    }
    printf("%lld", ans);
	return 0;
}

T2 100pts答案

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

#define ls(pos) pos << 1
#define rs(pos) pos << 1 | 1 

struct Node{LL pre, suf, maxx, sum; };

const int MAX_N = 5e5 + 50;
int n, m, d;
LL k;
Node tr[MAX_N << 2]; 

void build(int pos, int l, int r, int L, int R) {
    tr[pos] = (Node){-k, -k, -k, -k * (r - l + 1)};
    if(l == r) return ;
    
    int mid = (l + r) / 2;
    if(L <= mid) build(ls(pos), l, mid, L, R);
    if(mid + 1 <= R) build(rs(pos), mid + 1, r, L, R);
}

void change(int pos, int l, int r, int inx, int val) {
    if(l == r) {
        tr[pos].pre += val;
        tr[pos].suf += val;
        tr[pos].maxx += val;
        tr[pos].sum += val;
        return ;
    }
    
    int mid = (l + r) / 2;
    if(inx <= mid) change(ls(pos), l, mid, inx, val);
    else change(rs(pos), mid + 1, r, inx, val);
    
    tr[pos].pre = max(tr[ls(pos)].pre, tr[ls(pos)].sum + tr[rs(pos)].pre);
    tr[pos].suf = max(tr[rs(pos)].suf, tr[rs(pos)].sum + tr[ls(pos)].suf);
    tr[pos].maxx = max(max(tr[ls(pos)].maxx, tr[rs(pos)].maxx), max(max(tr[pos].pre, tr[pos].suf), tr[ls(pos)].suf + tr[rs(pos)].pre));
    tr[pos].sum = tr[ls(pos)].sum + tr[rs(pos)].sum; 
}

int main() {
    freopen("hire.in", "r", stdin);
    freopen("hire.out", "w", stdout);
    
    scanf("%d %d %lld %d", &n, &m, &k, &d);
    build(1, 1, n, 1, n);
    
    while(m--) {
        int x, y;
        scanf("%d %d", &x, &y);
        change(1, 1, n, x, y);
        if(tr[1].maxx <= k * d) puts("YES");
        else puts("NO");
    }
	return 0;
}

T3 100pts答案

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const LL INF = 0x3f3f3f3f3f3f3f3f; 
const int MAX_N = 100050;
int n, m, s[MAX_N], back[MAX_N];
LL dp[MAX_N], ans = -INF;
vector<int> e[MAX_N];
map<pair<int,int>, bool> mp;

bool Find(int x, int y) {
    return mp[make_pair(x, y)] || mp[make_pair(y, x)];
} 

void dfs(int u) {
    back[u] = u;
    for(int i = 0; i < s[u]; i++) {
        int v = e[u][i];
        dfs(v);
        bool flag = dp[v] > 0 && !(!i && Find(u, v));
        if(flag && i && Find(back[u], v)) {
            if(dp[v] > dp[back[u]]) {
                dp[u] -= max(dp[back[u]], 0LL);
            }else {
                flag = false;
            }
        }            
        if(flag && s[v] && Find(v, e[v][0])) {
            dp[v] -= max(dp[e[v][0]], 0LL);
        }
        if(flag) {
            dp[u] += dp[v];
            back[u] = back[v];
        }else {
            dp[v] = -INF;
        }
    }
    ans = max(ans, dp[u]);
}

int main() {
    freopen("block.in", "r", stdin);
    freopen("block.out", "w", stdout);
    
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &dp[i]);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        for(int j = 0; j < s[i]; j++) {
            int v;
            scanf("%d", &v);
            e[i].push_back(v);
        }
    }
    
    while(m--) {
        int u, v;
        scanf("%d %d", &u, &v);
        mp[make_pair(u, v)] = true;
    }
    dfs(1);
    printf("%lld", ans);
	return 0;
}

T4 20pts答案

#include <bits/stdc++.h>
using namespace std;

const int Mod = 1e9 + 7;
const int MAX_N = 550;
string s, t;
int n, c[MAX_N][MAX_N], ans;

void dfs(int inx) {
    if(inx >= n) {
        int cnt1 = 0, cnt2 = 0;
        for(int i = n - 1; ~i; i--) {
            if(t[i] == '0') {
                cnt2++;
            }else if(i){
                if(t[--i] == '0') cnt2++;
                else cnt1++;
            }
        }
        ans = (ans + c[cnt1 + cnt2][cnt1]) % Mod;
        return ;
    }
    
    if(s[inx] != '?') {
        dfs(inx + 1);
    }else {
        t[inx] = '0';
        dfs(inx + 1);
        t[inx] = '1';
        dfs(inx + 1);
    }
}

int main() {
    freopen("checkers.in", "r", stdin);
    freopen("checkers.out", "w", stdout);
    
    cin >> n >> s;
    for(int i = 0; i <= n * 2 + 1; i++) {
        for(int j = 0; j <= i; j++) {
            if(!i || !j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % Mod;
        }
    }
    
    t = s; dfs(0);
    cout << ans;
	return 0;
}