NOIP基地校Day1

T1 朴素dp都会吧，上矩阵秒了，但其实复杂度O(极大常数*log_nT)是错的，大样例四秒钟，没被卡掉只能说有点遗憾吧

#include <bits/stdc++.h>
#define rep(i, j, k) for(ll i = (j), _i = (k); i <= _i; i++)
#define drp(i, j, k) for(ll i = (j), _i = (k); i >= _i; i--)
#define ll long long
using namespace std;
#define fo(s) freopen(s ".in","r",stdin),freopen(s ".out","w",stdout)
//-------------------------------------//
ll read() {
    ll x = 0, f = 0; char ch;
    while(!isdigit(ch = getchar())) f |= ch == &#039;-&#039;;
    while(isdigit(ch)) x = (x<<3) + (x<<1) + (ch^48), ch = getchar();
    return f ? -x : x;
}
//-------------------------------------//
static const ll mod = 998244353;
struct Matrix {
    ll a[3][3], n, m;
    Matrix(ll N): n(N), m(N) { 
        rep(i, 1, N) rep(j, 1, N) a[i][j] = 0; rep(i, 1, N) a[i][i] = 1;
    }
    Matrix(ll N, ll M): n(N), m(M) { rep(i, 1, N) rep(j, 1, M) a[i][j] = 0; }
    Matrix() {}
    friend Matrix operator*(Matrix a, Matrix b) {
        Matrix c;
        c = Matrix(a.n, b.m);
        rep(i, 1, a.n) rep(j, 1, b.m) rep(k, 1, a.m) c[i][j] = (c[i][j] + a[i][k] * b[k][j] % mod) % mod; 
        return c;
    }
    ll* operator[](ll x) { return a[x]; }
};
Matrix I, A, B;
ll n, m, ans, mk;

ll qpow(ll x, ll k){ return k ? (ll)pow(x, k&1) * qpow(x * x % mod, k>>1) % mod : 1ll; }

void initMat() {
    I = Matrix(2), A = Matrix(2, 2), B = Matrix(1, 2);
    ll N = (n - 1 + mod) % mod;
    ll k = ((N * N % mod - 1) + mod) % mod;
    A[1][1] = k, A[1][2] = 0, A[2][1] = 2, A[2][2] = n * n % mod, B[1][1] = 1, B[1][2] = 1;
}
ll solve() {
    n = read() % mod, mk = m = read();
    initMat();
    ll inv = qpow(qpow(n * n % mod, m), mod - 2);
    while(mk) { 
        if(mk&1) I = I * A; 
        A = A * A, mk >>= 1; 
    }
    return (qpow(n * n % mod, m) - (B * I)[1][1] + mod) % mod * n % mod * inv % mod;
}
int main() 
{
    fo("poster");
    rep(T, 1, read()) printf("%lld\n",solve());
    return 0;
}

T2 dp[u][0/1/2/3]表示u这个点自己放路由器/只有儿子放路由器/只有父亲放路由器/儿子和父亲都有都有路由器。转移显然

#include <bits/stdc++.h>
#define rep(i, j, k) for(ll i = (j), _i = (k); i <= _i; i++)
#define drp(i, j, k) for(ll i = (j), _i = (k); i >= _i; i--)
#define ll long long
#define Nx 1000050
using namespace std;
#define fo(s) freopen(s ".in","r",stdin),freopen(s ".out","w",stdout)
//-------------------------------------//
ll read() {
    ll x = 0, f = 0; char ch;
    while(!isdigit(ch = getchar())) f |= ch == &#039;-&#039;;
    while(isdigit(ch)) x = (x<<3) + (x<<1) + (ch^48), ch = getchar();
    return f ? -x : x;
}
//-------------------------------------//
static const ll inf = 1e17;
ll n, a[Nx], f[Nx][4];// 0 self 1 son 2 father 3 both
vector<ll> G[Nx];
void dfs(ll u, ll fa) {
    f[u][0] = a[u];
    if(!G[u].size()) {
        f[u][1] = f[u][3] = inf; return ;
    }
    ll sum = 0, mn = inf, flag = 0;
    for(auto v : G[u]) {
        if(v == fa) continue;
        dfs(v, u);
        f[u][0] += min(f[v][0], min(f[v][2], f[v][3]));
        if(f[v][1] != inf) f[u][2] += f[v][1];
        else f[u][2] = inf;
        if(f[v][0] < f[v][1]) flag = 1, sum += f[v][0];
        else sum += f[v][1], mn = min(mn, f[v][0] - f[v][1]);
    }
    f[u][1] = f[u][3] = flag ? sum : sum + mn; 
}
int main() 
{
    fo("router");
    rep(i, 1, n = read()) a[i] = read();
    rep(i, 1, n - 1) {
        ll u = read(), v = read();
        G[u].push_back(v), G[v].push_back(u);
    }
    dfs(1, 0);
    printf("%lld", min(f[1][0], f[1][1]));
    return 0;
}

T3 & T4 不熟