noip2021 训练4

发表于 2021-11-11 更新于 2022-01-26 分类于 OI 阅读次数：本文字数： 3k 阅读时长 ≈ 6 分钟

Link

POI2011 DYN-Dynamite

树形 dp，非常妙

首先不难想到二分答案，对于二分的答案 $x$

设 $f_u$ 表示距 $u$ 最远的未被覆盖的点的距离， $g_u$ 表示 $u$ 到子树内被选的点的最小值。

初值 $f_{rt}=-inf,g_{rt}=inf$

转移也比较显然

$f_u=max\{f_v+1\},g_u=min\{g_v+1\}$

然后还要分类讨论一下

当 $f_u+g_u\le x$ 时，说明子树内的关键点已经可以被完全覆盖了， $f_u=-inf$
当 $g_u>x\ \&\ d_u=1$ ，说明 $u$ 应被覆盖且未被覆盖，可以丢给父亲处理， $f_u=max(f_u,0)$
当 $f_u=x$ 时，说明最远的未被覆盖点到 $u$ 距离为 $x$ 了，所以 $u$ 必选， $f_u=-inf,g_u=0,tot++$

最后要判一下根是否需要再选一个点

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

namespace IO
{
    template <typename T>
    inline void read(T &x)
    {
        x = 0; char c = getchar();
        while(!isdigit(c)) c = getchar();
        while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
        return;
    }

    template <typename T>
    inline void write(T x)
    {
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 3e5 + 5;
int n, m;
bool flag[N];
vector <int> G[N];
int f[N], g[N], tot;

inline void dfs(int u, int fa, int x)
{
    if(tot > m) return;
    f[u] = -INF, g[u] = INF;
    for(auto v : G[u])
    {
        if(v == fa) continue;
        dfs(v, u, x);
        if(tot > m) return;
        f[u] = max(f[u], f[v] + 1);
        g[u] = min(g[u], g[v] + 1);
    }
    if(f[u] + g[u] <= x) f[u] = -INF;
    if(g[u] > x && flag[u]) f[u] = max(f[u], 0);
    if(f[u] == x) f[u] = -INF, g[u] = 0, tot++;
    return;
}

inline bool chk(int x)
{
    tot = 0;
    dfs(1, 0, x);
    if(f[1] >= 0) tot++;
    return tot <= m;
}

int main()
{
    read(n), read(m);
    for(int i = 1; i <= n; i++)
        read(flag[i]);
    for(int i = 1, u, v; i < n; i++)
    {
        read(u), read(v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    int l = 0, r = n, ans;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(chk(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    write(ans), putchar('\n');
    return 0;
}
// A.S.

SCOI2005 骑士精神

$IDA*$ 板子题

Code

#include <iostream>
#include <cstdio>
#define swap(a, b) a ^= b ^= a ^= b

using namespace std;

const int N = 6;
int n, a[N][N];
char s[N][N];
int t[N][N] = {
    0, 0, 0, 0, 0, 0,
    0, 1, 1, 1, 1, 1,
    0, 0, 1, 1, 1, 1,
    0, 0, 0, 2, 1, 1,
    0, 0, 0, 0, 0, 1,
    0, 0, 0, 0, 0, 0,
};
int cnt;
int dx[8] = {-2, -2, -1, 1, 2, 2, 1, -1};
int dy[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
bool flag;

int chk()
{
    int res = 0;
    for(int i = 1; i <= 5; i++)
        for(int j = 1; j <= 5; j++)
            if(a[i][j] != t[i][j]) res++;
    return res;
}

void dfs(int x, int y, int now)
{
    if(flag) return;
    if(now == cnt && !chk())
    {
        flag = 1;
        return;
    }
    if(now + chk() > cnt + 1) return;
    for(int i = 0; i < 8; i++)
    {
        int wx = x + dx[i], wy = y + dy[i];
        if(wx < 1 || wx > 5 || wy < 1 || wy > 5) continue;
        swap(a[x][y], a[wx][wy]);
        dfs(wx, wy, now + 1);
        swap(a[x][y], a[wx][wy]);
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int x, y;
        for(int i = 1; i <= 5; i++)
        {
            scanf("%s", s[i] + 1);
            for(int j = 1; j <= 5; j++)
            {
                if(s[i][j] == '*') x = i, y = j, a[i][j] = 2;
                else a[i][j] = s[i][j] - '0';
            }
        }
        cnt = 0, flag = 0;
        for(cnt = 1; cnt <= 15; cnt++)
        {
            dfs(x, y, 0);
            if(flag) break;
        }
        if(!flag) puts("-1");
        else printf("%d\n", cnt);
    }
    return 0;
}
// A.S.

HNOI2010 合唱队

设 $f_{i,j,0/1}$ 表示区间 $[i,j]$ 最后一个是从左边/右边进来的方案数

然后分类讨论判一下大小，转移即可

Code

#include<iostream>
#include<cstdio>
#define modd(a,b) a=(a+b)%p

using namespace std;

const int N=1010;
const int p=19650827;
int n,a[N];
int f[N][N][2];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),f[i][i][0]=f[i][i][1]=1;
	for(int len=2;len<=n;len++)
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			if(a[i]<a[i+1]) modd(f[i][j][0],f[i+1][j][0]);
			if(i+1!=j&&a[i]<a[j]) modd(f[i][j][0],f[i+1][j][1]);
			if(a[j]>a[j-1]) modd(f[i][j][1],f[i][j-1][1]);
			if(j-1!=i&&a[j]>a[i]) modd(f[i][j][1],f[i][j-1][0]);
		}
	printf("%d\n",(f[1][n][0]+f[1][n][1])%p);
	return 0;
}
// A.S.

HAOI2009 逆序对数列

设 $f_{i,j}$ 表示 $i$ 的排列中，逆序对个数为 $j$ 的方案数。

考虑在 $i-1$ 的排列中插入 $i$

$f_{i,j}=\sum_{k=j-i+1}^jf_{i-1,k}$

考虑优化，因为 $k$ 是从 $0$ 开始的，比较套路的用前缀和优化

令 $sum=\sum_{k=max(j-i+1,0)}^jf_{i-1,k}$

$f_{i,j}=sum$

复杂度 $O(nk)$

Code

#include<iostream>
#include<cstdio>

using namespace std;

const int N=1010;
const int p=10000;
int n,m,f[N][N];

int main()
{
	scanf("%d%d",&n,&m);
	f[1][0]=1;
	for(int i=2;i<=n;i++)
	{
		int sum=0;
		for(int j=0;j<=m;j++)
		{
			sum=(sum+f[i-1][j])%p;
			f[i][j]=sum;
			if(j>=i-1) sum=((sum-f[i-1][j-i+1])%p+p)%p;
		}
	}
	printf("%d\n",f[n][m]);
	return 0;
}
// A.S.

ZJOI2008 生日聚会

见2021.11.6NOIP模拟赛2 赛后总结T1

SCOI2003 严格N元树

高精度板子（？

不过 dp 方程还是挺难想到的

设 $f_i$ 表示深度 $\le i$ 的 $n$ 元树的个数，那么答案即为 $f_d-f_{d-1}$

~~这就是差分的顶级理解~~

考虑如何转移

对于 $f_i$ ，可以理解成 $f_{i-1}$ 再加上一个根，这个根有 $n$ 个子树，每个子树都有 $f_{i-1}$ 种方案，还有一种只有根的。

所以 $f_i=f_{i-1}^n+1$

然后套个高精度即可

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct INT
{
    int a[210];
    
    INT()
    {
        memset(a, 0, sizeof(a));
    }
    
    void rd()
    {
        char s[210];
        scanf("%s", s);
        a[0] = strlen(s);
        for(int i = 1; i <= a[0]; i++)
            a[i] = s[a[0] - i] - '0';
        return;
    }
    
    void print()
    {
        for(int i = a[0]; i >= 1; i--)
            cout << a[i];
        cout << endl;
        return;
    }
    
    INT operator + (const INT &b) const
    {
        INT c;
        c.a[0] = max(a[0], b.a[0]);
        for(int i = 1; i <= c.a[0]; i++)
        {
            c.a[i] += a[i] + b.a[i];
            c.a[i + 1] += c.a[i] / 10;
            c.a[i] %= 10;
        }
        if(c.a[c.a[0] + 1]) c.a[0]++;
        return c;
    }
    
    bool operator < (const INT &b) const
    {
        if(a[0] != b.a[0]) return a[0] < b.a[0];
        for(int i = a[0]; i >= 1; i--)
            if(a[i] != b.a[i]) return a[i] < b.a[i];
        return false;
    }
    
    INT operator - (INT b) const
    {
        INT t;
        memcpy(t.a, a, sizeof(a));
        for(int i = 1; i <= t.a[0]; i++)
        {
            if(t.a[i] < b.a[i]) t.a[i] += 10,  t.a[i + 1]--;
            t.a[i] -= b.a[i];
        }
        while(t.a[0] > 1 && !t.a[t.a[0]]) t.a[0]--;
        return t;
    }
    
    INT operator * (const INT &b) const
    {
        INT c;
        for(int i = 1; i <= a[0]; i++)
        {
            int w = 0;
            for(int j = 1; j <= b.a[0]; j++)
            {
                c.a[i + j - 1] += a[i] * b.a[j] + w;
                w = c.a[i + j - 1] / 10;
                c.a[i + j - 1] %= 10;
            }
            c.a[i + b.a[0]] += w;
        }
        c.a[0] = a[0] + b.a[0];
        if(!c.a[c.a[0]]) c.a[0]--;
        return c;
    }

    INT operator / (const int &b) const
    {
        INT c;
        memcpy(c.a, a, sizeof(a));
        for(int i = a[0]; i > 1; i--)
        {
            c.a[i - 1] += (c.a[i] % b) * 10;
            c.a[i] /= b;
        }
        c.a[1] /= b;
        while(!c.a[c.a[0]]) c.a[0]--;
        return c;
    }

    void operator = (int b)
    {
        while(b) a[++a[0]] = b % 10, b /= 10;
    }
} f[20];

int n, d;

int main()
{
    scanf("%d%d", &n, &d);
    f[0] = 1;
    for(int i = 1; i <= d; i++)
    {
        f[i] = 1;
        for(int j = 1; j <= n; j++)
            f[i] = f[i] * f[i - 1];
        f[i] = f[i] + f[0];
    }
    (f[d] - f[d - 1]).print();
    return 0;
}
// A.S.

ZJOI2008 骑士

基环树上 dp 板子题

只需要在环上断一条边，这条边的两个端点只能选一个，以两个点为根分别 dp，然后将答案取个 $max$ 。

dp 的时候就是没有上司的舞会

注意这是一个基环树森林，所以要枚举一遍每个点。

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 1e18

using namespace std;

namespace IO
{
    template <typename T>
    void read(T &x)
    {
        x = 0; int f = 1; char c = getchar();
        while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
        while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
        x *= f;
    }

    template <typename T>
    void write(T x)
    {
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e6 + 5;
int n, a[N], fa[N];
vector <int> g[N];
bool vis[N];
ll f[N][2], ans;

void dp(int u, int rt)
{
    vis[u] = 1;
    f[u][0] = 0, f[u][1] = a[u];
    for(auto v : g[u])
    {
        if(v == rt)
        {
            f[v][1] = -INF;
            continue;
        }
        dp(v, rt);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
    return;
}

void solve(int x)
{
    vis[x] = 1;
    while(!vis[fa[x]])
    {
        x = fa[x];
        vis[x] = 1;
    }
    dp(x, x);
    ll t = max(f[x][0], f[x][1]);
    x = fa[x];
    dp(x, x);
    ans += max(t, max(f[x][0], f[x][1]));
    return;
}

int main()
{
    read(n);
    for(int i = 1; i <= n; i++)
    {
        read(a[i]), read(fa[i]);
        g[fa[i]].push_back(i);
    }
    for(int i = 1; i <= n; i++)
        if(!vis[i]) solve(i);
    write(ans), putchar('\n');
    return 0;
}
// A.S.

JSOI2008 球形空间产生器

根据， $d=\sqrt{\sum_{i=1}^n(a_i-b_i)^2}$

可得， $d^2=\sum_{i=1}^n(a_i-b_i)^2$

化简得， $d^2=\sum_{i=1}^n(a_i^2+b_i^2-2a_ib_i)$

移项得， $\sum_{i=1}^n(-2a_ib_i)+r^2+\sum_{i=1}^nb_i^2=\sum_{i=1}^na_i^2$

其中 $b_i$ 是未知数

注意到， $r^2+\sum_{i=1}^nb_i^2$ 在每个方程中都有，因此可以设为一个系数为 $1$ 的未知数，这样就会被消掉了。

然后就可以愉快的高斯消元了 OvO

Code

#include <bits/stdc++.h>
#define db double

using namespace std;

const int N = 15;
int n;
db a[N][N];

void gauss()
{
    for(int i = 1; i <= n; i++)
    {
        if(!a[i][i])
        {
            int j;
            for(j = i + 1; j <= n; j++)
                if(a[j][i]) break;
            for(int k = 1; k <= n + 1; k++)
                swap(a[i][k], a[j][k]);
        }
        for(int k = i + 1; k <= n; k++)
            for(int j = n + 1; j >= i; j--)
                a[k][j] -= a[k][i] / a[i][i] * a[i][j];
    }
    for(int i = n; i >= 1; i--)
    {
        for(int j = i + 1; j <= n; j++)
            a[i][n + 1] -= a[i][j] * a[j][n + 1];
        a[i][n + 1] /= a[i][i];
    }
    return;
}

int main()
{
    scanf("%d", &n), n++;
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j < n; ++ j)
        {
            scanf("%lf", &a[i][j]);
            a[i][n + 1] -= a[i][j] * a[i][j];
            a[i][j] *= -2.0;
        }
        a[i][n] = 1;
    }
    gauss();
    for(int i = 1; i < n; ++ i){
        printf("%.3lf",a[i][n + 1]);
        if(i < n - 1) printf(" ");
    }
}
// A.S.

NOI2015 软件包管理器

树剖板子题

链上修改查询、子树修改查询

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#define ls rt<<1
#define rs rt<<1|1

using namespace std;

const int N = 1e5 + 5;

int read()
{
    int x = 0;
    char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x;
}

int n,m;
vector <int> G[N];
int dep[N],siz[N],son[N],fa[N];

void dfs1(int u,int f)
{
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    fa[u] = f;
    for(int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if(v == f) continue;
        dfs1(v,u);
        siz[u] += siz[v];
        if(siz[son[u]] < siz[v]) son[u] = v;
    }
}

int cnt,id[N],top[N];

void dfs2(int u,int tf)
{
    id[u] = ++cnt;
    top[u] = tf;
    if(son[u]) dfs2(son[u],tf);
    for(int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v,v);
    }
}

int sum[N << 2], tag[N << 2];

void pushup(int rt)
{
    sum[rt] = sum[ls] + sum[rs];
}

void pushdown(int l,int r,int rt)
{
    if(tag[rt] != -1)
    {
        int mid = (l + r) >> 1;
        sum[ls] = tag[rt] * (mid - l + 1);
        tag[ls] = tag[rt];
        sum[rs] = tag[rt] * (r - mid);
        tag[rs] = tag[rt];
        tag[rt] = -1;
    }
}

void update(int L,int R,int v,int l,int r,int rt)
{
    if(l > R || r < L) return;
    if(L <= l && r <= R)
    {
        sum[rt] = v * (r - l + 1);
        tag[rt] = v;
        return;
    }
    pushdown(l,r,rt);
    int mid = (l + r) >> 1;
    update(L,R,v,l,mid,ls);
    update(L,R,v,mid + 1,r,rs);
    pushup(rt);
}

void upd1(int x)
{
    while(top[x] != 1)
    {
        update(id[top[x]], id[x], 1, 1, n ,1);
        x = fa[top[x]];
    }
    update(id[top[x]], id[x], 1, 1, n, 1);
}

void upd2(int x)
{
    update(id[x], id[x] + siz[x] - 1, 0, 1, n, 1);
}

int main()
{
    n = read();
    for(int i = 1; i < n; i++)
    {
        int u = read() + 1;
        G[u].push_back(i + 1);
    }
    dfs1(1,0);
    dfs2(1,1);
    memset(tag,-1,sizeof(tag));
    m = read();
    while(m--)
    {
        char op[10];
        scanf("%s",op);
        int x = read() + 1, ans = sum[1];
        if(op[0] == 'i')
        {
            upd1(x);
            printf("%d\n",sum[1] - ans);
        }
        else
        {
            upd2(x);
            printf("%d\n",ans - sum[1]);
        }
    }
    return 0;
}
// A.S.

NOI2014 动物园

根据 $kmp$ 求出的 $nxt$ 数组进行计算。

但是为了避免在 $aaa...a$ 时复杂度退化为 $O(n^2)$ ，可以像求 $nxt$ 一样用指针记录一下，如果在 $i-1$ 时合法，那么在 $i$ 时也合法。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long

using namespace std;

const int N = 1e6 + 5;
const int p = 1e9 + 7;
char s[N];
int nxt[N],num[N];

signed main()
{
    int T;
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%s",s + 1);
        int n = strlen(s + 1);
        num[0] = 0, num[1] = 1;
        memset(nxt,0,sizeof(nxt));
        for(int i = 2, j = 0; i <= n; i++)
        {
            while(j && s[i] != s[j + 1]) j = nxt[j];
            if(s[i] == s[j + 1]) j++;
            nxt[i] = j;
            num[i] = num[j] + 1;
        }
        int ans = 1;
        for(int i = 1, j = 0; i <= n; i++)
        {
            while(j && s[i] != s[j + 1]) j = nxt[j];
            if(s[i] == s[j + 1]) j++;
            while(j && j * 2 > i) j = nxt[j];
            ans = ans * (num[j] + 1) % p;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
// A.S.

BJOI2012 最多的方案

首先有个性质：任意自然数都能被不同的斐波那契数之和表示

（其实有没有都一样）

根据 $f_i=f_{i-1}+f_{i-1}$

任意一项都只能分解为前两项之和。

所以我们可以先把 $n$ 分解为几个最大的斐波那契数的和，然后将这些数分解，求方案数。

$n=\sum_{i=1}^{cnt}f_{pos_i}$ $pos_i$ 递增

设 $g_{i,0/1}$ 表示前 $i$ 个数分解后恰好组成 $\sum_{j=1}^if_{pos_j}$ 的方案数，其中第二维 $0/1$ 表示第 $i$ 个数是否被分解。

初值 $g_{1,0} = \dfrac{pos_1-1}{2},g_{1,1} = 1$

转移方程，因为每次分解都会产生两个数，所以要除以二

$g_{1,0}=g_{i-1,0}\times \dfrac{pos_i-pos_{i-1}}{2}+g_{i-1,1}\times \dfrac{pos_i-pos_{i-1}-1}{2}$

$g_{i,1}=g_{i-1,0}+g_{i-1,1}$

Code

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 110;
ll n, f[N];
int m, g[N][2], pos[N], cnt;

int main()
{
    scanf("%lld", &n);
    f[1] = 1, f[2] = 2;
    for(m = 3; f[m - 1] <= n; m++)
        f[m] = f[m - 1] + f[m - 2];
    m--;
    for(int i = m; i >= 1; i--)
        if(n >= f[i])
        {
            pos[++cnt] = i;
            n -= f[i];
        }
    sort(pos + 1, pos + 1 + cnt);
    g[1][0] = (pos[1] - 1) >> 1, g[1][1] = 1;
    for(int i = 2; i <= cnt; i++)
    {
        g[i][0] = g[i - 1][0] * (pos[i] - pos[i - 1] >> 1) + g[i - 1][1] * (pos[i] - pos[i - 1] - 1 >> 1);
        g[i][1] = g[i - 1][0] + g[i - 1][1];
    }
    printf("%d\n", g[cnt][0] + g[cnt][1]);
    return 0;
}
// A.S.

SCOI2010 连续攻击游戏

用并查集维护一下，从小数向大数连边

答案为最大的连通块的点的个数减 $1$

AHOI2005 约数研究

$[1,n]$ 中有约数 $i$ 的个数是 $\dfrac{n}{i}$

所以答案为 $\sum_{i=1}^n\dfrac{n}{i}$

然后对于中间连续相等的直接统计一下个数，跳过去就行了。

Code

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, ans = 0;
    scanf("%d", &n);
    for(int i = 1, j; i <= n; i = j + 1)
    {
        j = n / (n / i);
        ans += (n / i) * (j - i + 1);
    }
    printf("%d\n", ans);
    return 0;
}
// A.S.