noip2021 训练5

发表于 更新于 分类于 阅读次数： 本文字数： 3.4k 阅读时长 ≈ 7 分钟

Link

SDOI2010 地精部落

法一：

首先有两个性质

  • 在一个波动序列中，若 ii 和 jj 不相邻，那么交换 i,ji,j 后依然是一个波动序列。
  • 把波动序列中的 aia_i 都改为 n+1−ain+1-a_i，还是一个波动序列，且山峰与山谷相反。

设 fi,jf_{i,j} 表示选 [1,i][1,i] 这些数，第一个为山峰且为 jj 的方案数（山谷与山峰的方案数是一样的）

转移 fi,j=fi,j−1+fi−1,i−j+1f_{i,j}=f_{i,j-1}+f_{i-1,i-j+1}

若 jj 与 j−1j-1 不相邻（jj 表示的是数而不是位置），交换后仍是合法的，所以是 fi,j−1f_{i,j-1}。

若 jj 与 j−1j-1 相邻，因为第一个数 jj 为山峰，所以 j−1j-1 必为山谷，此时确定了第一个为 jj，所以一共选了 i−1i-1 个数，根据性质二，j−1j-1 为山谷的方案数数与 (i−1)+1−(j−1)(i-1)+1-(j-1) 为山峰的方案数是相同的，所以是 fi−1,i−j+1f_{i-1,i-j+1}

最后答案为 ∑i=1nfn,i\sum_{i=1}^nf_{n,i}

转移时可以用滚动数组优化一下空间

法二：

设 fi,0/1f_{i,0/1} 分别表示长度为 ii 且第一位为山峰/山谷的方案数。

转移时可以按最大的数分成两半，然后将两边的方案数乘起来，再乘上一个组合数。

因为最大的数必定是山峰，与它相邻的必定是山谷，所以根据其位置 jj 的奇偶性，可以得到前面一段的第一位为山峰还是山谷，同理可得后面一段的。

然后就可以转移了。

其中组合数为在 i−1i-1 个数中选 jj 个放在前面，也就是 Ci−1jC_{i-1}^j。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstdio>
#define ll long long

using namespace std;

const int N = 4210;
int n, p;
int f[N][2], C[N][N];

int main()
{
    ios :: sync_with_stdio(false);
    cin >> n >> p;
    f[0][0] = f[0][1] = 1;
    f[1][0] = f[1][1] = 1;
    for(int i = 0; i <= n; i++)
    {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
    }
    for(int i = 2; i <= n; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(j & 1) f[i][1] = (f[i][1] + (ll)C[i - 1][j] * f[j][1] % p * f[i - 1 - j][0] % p) % p;
            else f[i][0] = (f[i][0] + (ll)C[i - 1][j] * f[j][0] % p * f[i - 1 - j][0] % p) % p;
        }
    }
    cout << (f[n][0] + f[n][1]) % p << endl;
    return 0;
}
// A.S.

HAOI2010 软件安装

首先不难想到缩点，因为环内的点必须全选才能产生贡献

由于一个软件最多依赖另外一个软件，所以得到了一棵树，然后就是树上背包板子了

要保证选了父亲才能选其儿子

我写的 O(n3)O(n^3) 的

不过这种题好像可以处理出 dfs 序，然后就可以 O(n2)O(n^2) dp 了？

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO
{
    template <typename T>
    inline 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;
        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 = 110;
const int M = 510;

int n, m, a[N], b[N], fa[N];
vector <int> g[N];
vector <int> G[N];
int dfn[N], low[N], tim;
bool vis[N];
int stk[N], top, cnt, id[N];
int val[N], deg[N], w[N], v[N];

void tarjan(int u)
{
    dfn[u] = low[u] = ++tim;
    stk[++top] = u;
    vis[u] = 1;
    for(auto v : g[u])
    {
        if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if(vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        int x; cnt++;
        do {
            x = stk[top--];
            w[cnt] += a[x];
            v[cnt] += b[x];
            id[x] = cnt;
            vis[x] = 0;
        } while(x != u);
    }
    return;
}

int f[N][M];

void dfs(int u)
{
    for(int i = w[u]; i <= m; i++)
        f[u][i] = v[u];
    for(auto v : G[u])
    {
        dfs(v);
        for(int i = m; i >= w[v]; i--)
            for(int j = 0; j <= i - w[u]; j++)
                f[u][i] = max(f[u][i], f[u][i - j] + f[v][j]);
    }
    return;
}

int main()
{
    read(n), read(m);
    for(int i = 1; i <= n; i++) read(a[i]);
    for(int i = 1; i <= n; i++) read(b[i]);
    for(int i = 1; i <= n; i++) read(fa[i]), g[fa[i]].pb(i);

    for(int i = 1; i <= n; i++)
        if(!dfn[i]) tarjan(i);

    for(int i = 1; i <= n; i++)
        for(auto j : g[i])
            if(id[i] != id[j])
                G[id[i]].pb(id[j]), deg[id[j]]++;

    for(int i = 1; i <= cnt; i++)
        if(!deg[i]) G[0].pb(i);

    dfs(0);
    write(f[0][m]), putchar('\n');

    return 0;
}
// A.S.

BJWC2012 冻结

分层图最短路板子

一定要注意边的数量，算不清就开大点！！！

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>

using namespace std;

namespace IO
{
    template <typename T>
    inline 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;
        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 = 2600;
const int M = 2e5;

int n, m, k;
struct edge
{
    int v, w, nxt;
} e[M];
int head[N], tot;

void link(int u, int v, int w)
{
    e[++tot] = (edge) {v, w, head[u]};
    head[u] = tot;
}

queue <int> que;
int dis[N];
bool vis[N];

void spfa()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    que.push(1), vis[1] = 1;
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        vis[u] = 0;
        for(int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].v;
            if(dis[v] > dis[u] + e[i].w)
            {
                dis[v] = dis[u] + e[i].w;
                if(!vis[v]) que.push(v), vis[v] = 1;
            }
        }
    }
    return;
}

int main()
{
    read(n), read(m), read(k);
    for(int i = 1, u, v, w; i <= m; i++)
    {
        read(u), read(v), read(w);
        for(int j = 0; j <= k + 1; j++)
        {
            int x = u + j * n, y = v + j * n;
            link(x, y, w), link(y, x, w);
            link(x, y + n, w >> 1), link(y, x + n, w >> 1);
        }
    }

    spfa();

    int ans = 1e9;
    for(int i = 1; i <= k + 1; i++)
        ans = min(ans, dis[i * n]);
    write(ans), putchar('\n');

    return 0;
}
// A.S.

SDOI2012 Longge 的问题

经典数学题

求 ∑i=1ngcd⁡(i,n)\sum_{i=1}^n\gcd(i,n)

考虑对于每个 gcd⁡\gcd 有几个 ii，统计贡献。

设 cnt(x)cnt(x) 表示 [1,n][1,n] 中与 nn 的最大公因数为 xx 的数的个数

cnt(x)=∑i=1n[gcd⁡(i,n)=1]=∑i=1⌊nx⌋[gcd⁡(i,⌊nx⌋)=1]cnt(x)=\sum_{i=1}^n[\gcd(i,n)=1]=\sum_{i=1}^{\left\lfloor \frac{n}{x}\right\rfloor}[\gcd(i,\left\lfloor \frac{n}{x}\right\rfloor)=1]

我们发现 cnt(x)=ϕ(⌊nx⌋)cnt(x)=\phi(\left\lfloor \frac{n}{x}\right\rfloor)

所以原式可以化简为

∑i=1n=∑d∣nd∑i=1n[gcd⁡(i,n)=d]=∑d∣nd×ϕ(⌊nd⌋)\sum_{i=1}^n=\sum_{d|n}d\sum_{i=1}^n[\gcd(i,n)=d]=\sum_{d|n}d\times\phi(\left\lfloor \frac{n}{d}\right\rfloor)

然后 O(n)O(\sqrt{n}) 枚举 dd，O(n)O(\sqrt{n}) 单点求 phi就可以了。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define int long long

using namespace std;

int phi(int x)
{
    int res = x;
    for(int i = 2; i * i <= x; i++)
    {
        if(x % i == 0)
        {
            res = res / i * (i - 1);
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1) res = res / x * (x - 1);
    return res;
}

signed main()
{
    int n, ans = 0;
    scanf("%lld", &n);
    for(int i = 1; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            ans += i * phi(n / i);
            if(n / i != i) ans += n / i * phi(i);
        }
    }
    printf("%lld\n", ans);
    return 0;
}
// A.S.

NOI2015 程序自动分析

并查集开两倍，分别表示是否相等

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=1e6+10;
struct node
{
	int x,y,e;
}a[N];
int num[N<<1],cnt;
int f[N];

int Find(int a)
{
	return f[a]==a?a:f[a]=Find(f[a]);
}

bool cmp(node A,node B)
{
	return A.e>B.e;
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n*2;i++) f[i]=i;
		cnt=-1;
		memset(num,0,sizeof(num));
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].e);
			num[++cnt]=a[i].x;
			num[++cnt]=a[i].y;
		}
		sort(num,num+cnt);
		int tot=unique(num+1,num+1+cnt)-num;
		for(int i=1;i<=n;i++)
		{
			a[i].x=lower_bound(num,num+tot,a[i].x)-num;
			a[i].y=lower_bound(num,num+tot,a[i].y)-num;
		}
		for(int i=1;i<=n;i++) f[i]=i;
		sort(a+1,a+1+n,cmp);
		int flag=0;
		for(int i=1;i<=n;i++)
		{
			int fx=Find(a[i].x),fy=Find(a[i].y);
			if(a[i].e==1) f[fx]=fy;
			else if(fx==fy) {flag=1;break;}
		}
		if(!flag) puts("YES");
		else puts("NO");
	}
	return 0;
}
// A.S.

JSOI2008 最小生成树计数

首先有一个性质：不同的最小生成树中权值相同的边的个数是相同的（比较显然？）

因为 具有相同权值的边不会超过10条，所以可以直接暴力。

先求出最小生成树中每个权值有几条边。

处理出权值相同的边，排序后存一下同一个权值的左右端点，对可以构成生成树的边进行乘法原理即可。

使用搜索，并随时判断是否出现了环。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>

using namespace std;

namespace IO
{
    template <typename T>
    inline 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;
        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 = 110;
const int M = 1010;
const int p = 31011;

int n, m, cnt;
struct edge
{
    int u, v, w;
    friend bool operator < (edge x, edge y)
    {
        return x.w < y.w;
    }
} e[M];

struct node
{
    int l, r, num;
} a[M];

int f[N];

void init()
{
    for(int i = 1; i <= n; i++) f[i] = i;
}

int Find(int a)
{
    return f[a] == a ? a : Find(f[a]);
}

int sum;
void dfs(int id, int now, int k)
{
    if(now == a[id].r + 1)
    {
        if(k == a[id].num) sum++;
        return;
    }
    int x = Find(e[now].u), y = Find(e[now].v);
    if(x != y)
    {
        f[x] = y;
        dfs(id, now + 1, k + 1);
        f[x] = x, f[y] = y;
    }
    dfs(id, now + 1, k);
}

int main()
{
    read(n), read(m);
    for(int i = 1; i <= m; i++)
        read(e[i].u), read(e[i].v), read(e[i].w);
    sort(e + 1, e + 1 + m);

    init();
    int tot = 0;
    for(int i = 1; i <= m; i++)
    {
        if(e[i].w != e[i - 1].w) cnt++, a[cnt - 1].r = i - 1, a[cnt].l = i;
        int x = Find(e[i].u), y = Find(e[i].v);
        if(x != y) f[x] = y, a[cnt].num++, tot++;
    }
    a[cnt].r = m;
    if(tot != n - 1)
    {
        puts("0");
        return 0;
    }

    init();
    int ans = 1;
    for(int i = 1; i <= cnt; i++)
    {
        sum = 0;
        dfs(i, a[i].l, 0);
        ans = ans * sum % p;
        for(int j = a[i].l; j <= a[i].r; j++)
        {
            int x = Find(e[j].u), y = Find(e[j].v);
            if(x != y) f[x] = y;
        }
    }
    write(ans), putchar('\n');
    return 0;
}
// A.S.

HEOI2014 南园满地堆轻絮

使得最大值最小，肯定要二分答案

考虑如何 chk，贪心的想，因为要使序列不下降，所以要尽量让前面的更小，所以就很好写了。

复杂度 O(nlog⁡n)O(n\log n)

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
#define int long long

using namespace std;

namespace IO
{
    template <typename T>
    inline 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;
        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 = 5e6 + 5;
int n, sa, sb, sc, sd, a[N], mod;
int b[N];

int F(int x)
{
    return (sa * x % mod * x % mod * x % mod + sb * x % mod * x % mod + sc * x % mod + sd) % mod;
}

bool chk(int x)
{
    memcpy(a, b, sizeof(b));
    a[1] -= x;
    for(int i = 2; i <= n; i++)
    {
        if(a[i - 1] <= a[i]) a[i] = max(a[i] - x, a[i - 1]);
        else if(a[i - 1] - a[i] > x) return false;
        else a[i] = a[i - 1];
    }
    return true;
}

signed main()
{
    read(n), read(sa), read(sb), read(sc), read(sd), read(a[1]), read(mod);
    for(int i = 2; i <= n; i++)
        a[i] = (F(a[i - 1]) + F(a[i - 2])) % mod;
    memcpy(b, a, sizeof(a));

    int l = 1, r = mod, 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.

HNOI2012 矿场搭建

首先，如果有割点，那么两边的点肯定要分开讨论，这里把两边的点定义为“组”。

下面进行分类讨论：

  1. 如果该组内没有割点，那么至少设置两个出口
  2. 如果有一个割点，那么只需要设置一个。因为如果不是割点坍塌，可以走出去
  3. 如果有两个割点，就不需要设置，因为不管哪个坍塌，都可以走出去

方案数直接乘法原理就行了。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

namespace IO
{
    template <typename T>
    inline bool 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;
        return x;
    }

    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 = 510;

int n, m, Case;
vector <int> g[N];
int dfn[N], low[N], tim, vis[N];
bool cut[N];

void tarjan(int u, int s)
{
    int ch = 0;
    dfn[u] = low[u] = ++tim;
    vis[u] = 1;
    for(auto v : g[u])
    {
        if(!dfn[v])
        {
            tarjan(v, s);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u] && u != s) cut[u] = 1;
            if(u == s) ch++;
        }
        else if(vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if(u == s && ch >= 2) cut[u] = 1;
    return;
}

ll ans, tot;
int id, num, cnt;

void dfs(int u)
{
    vis[u] = id;
    num++;
    for(auto v : g[u])
    {
        if(cut[v] && vis[v] != id)
            cnt++, vis[v] = id;
        if(!vis[v]) dfs(v);
    }
    return;
}

void Clear()
{
    tim = 0, id = 0;
    ans = 0, tot = 1;
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(vis, 0, sizeof(vis));
    memset(cut, 0, sizeof(cut));
    for(int i = 1; i <= n; i++) g[i].clear();
    n = 0;
}

int main()
{
    while(read(m))
    {
        Clear();

        for(int i = 1, u, v; i <= m; i++)
        {
            read(u), read(v);
            g[u].pb(v), g[v].pb(u);
            n = max(n, max(u, v));
        }
        
        for(int i = 1; i <= n; i++)
            if(!dfn[i]) tarjan(i, i);

        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; i++)
        {
            if(vis[i] || cut[i]) continue;
            id++, num = 0, cnt = 0;
            dfs(i);
            if(!cnt) ans += 2, tot *= (ll)num * (num - 1) / 2;
            else if(cnt == 1) ans++, tot *= (ll)num;
        }

        printf("Case %d: ", ++Case);
        write(ans), putchar(' ');
        write(tot), putchar('\n');
    }

    return 0;
}
// A.S.

Luogu P4198 楼房重建

见noip2021 线段树专项第一题

JOISC 2014 Day1 有趣的家庭菜园

树状数组+贪心

网上搜了一下，发现大部分题解是从小到大处理的，但是这样遇到相同的高度会很麻烦，所以这里从大到小进行计算。

对于第 ii 株植物，因为我们从大到小枚举，所以在 ii 前面的都是 >hi>h_i 的，我们需要将 ii 移动到最旁边，要么到左边，要么到右边。

发现可以用树状数组维护前缀和，能直接查询到左边需要交换几次，到右边的次数就是前面植物的个数减去到左边的次数。

对于高度相同的，要取出来后同统一查询答案，然后再统一插入树状数组，因为两边有高度相同也是合法的。

答案就是每株植物到两边的较小次数的和。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>

using namespace std;

namespace IO
{
    template <typename T>
    inline 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;
        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;
struct node
{
    int val, id;
    friend bool operator < (node x, node y)
    {
        return x.val > y.val;
    }
} a[N];
int c[N];

void add(int x, int y)
{
    for(; x <= n; x += x & -x)
        c[x] += y;
}

int qry(int x)
{
    int res = 0;
    for(; x; x -= x & -x)
        res += c[x];
    return res;
}

int main()
{
    read(n);
    for(int i = 1; i <= n; i++)
        read(a[i].val), a[i].id = i;
    sort(a + 1, a + 1 + n);

    long long ans = 0;
    for(int i = 1, pos = 1; i <= n; i++)
    {
        if(a[i].val != a[i - 1].val)
            for(; pos < i; pos++)
                add(a[pos].id, 1);
        int pre = qry(a[i].id);
        ans += min(pre, pos - 1 - pre);
    }
    write(ans), putchar('\n');

    return 0;
}
// A.S.

APIO2009 采油区域

神奇的 dp

dp 本身并不难，难在思路

因为要选 33 块，所以直接 dp 并不好做，考虑分别算出 33 块，将它们拼起来。

对于 n×mn\times m 的矩形，处理出四个数组，分别表示 (i,j)(i,j) 左上、右上、左下、右下的 k×kk\times k 的最大的矩形。

1
2
3
a | b
--|--
c | d

然后分六种情况讨论

  1. 上中下
  2. 左中右
  3. 左上+右上+下
  4. 左+右上+右下
  5. 左上+左下+右
  6. 上+左下+右下

代码看似很毒瘤，实际上都是重复的

还要说一下 luogu 的数据比较水，最好去 bzoj 上交

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long

using namespace std;

const int N = 1510;
int n, m, k, s[N][N];
int a[N][N], b[N][N], c[N][N], d[N][N];

/*
a | b
--|--
c | d
*/

int get_sum(int x, int y)
{
    return s[x][y] - s[x - k][y] - s[x][y - k] + s[x - k][y - k];
}

void calc()
{
    for(int i = k; i <= n; i++)
        for(int j = k; j <= m; j++)
            a[i][j] = max(get_sum(i, j), max(a[i - 1][j], a[i][j - 1]));
    for(int i = k; i <= n; i++)
        for(int j = m - k + 1; j >= 1; j--)
            b[i][j] = max(get_sum(i, j + k - 1), max(b[i - 1][j], b[i][j + 1]));
    for(int i = n - k + 1; i >= 1; i--)
        for(int j = k; j <= m; j++)
            c[i][j] = max(get_sum(i + k - 1, j), max(c[i + 1][j], c[i][j - 1]));
    for(int i = n - k + 1; i >= 1; i--)
        for(int j = m - k + 1; j >= 1; j--)
            d[i][j] = max(get_sum(i + k - 1, j + k - 1), max(d[i + 1][j], d[i][j + 1]));
}

int rd()
{
    int x = 0;
    char c = getchar();
    while(!isdigit(c)) c = getchar(), cout << c << endl;
    while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
    return x;
}

signed main()
{
    scanf("%lld%lld%lld", &n, &m, &k);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%lld", &s[i][j]), s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    calc();
    int ans = 0;
    for(int i = k; i <= n; i++)
        for(int j = k; j <= m; j++)
        {
            ans = max(ans, b[i - k][1] + get_sum(i, j) + d[i + 1][1]);
            ans = max(ans, c[1][j - k] + get_sum(i, j) + d[1][j + 1]);
        }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            ans = max(ans, a[i][j] + b[i][j + 1] + c[i + 1][m]);
            ans = max(ans, a[n][j] + b[i][j + 1] + d[i + 1][j + 1]);
            ans = max(ans, a[i][j] + c[i + 1][j] + b[n][j + 1]);
            ans = max(ans, a[i][m] + c[i + 1][j] + d[i + 1][j + 1]);
        }
    printf("%lld\n", ans);
    return 0;
}
// A.S.

JSOI2007 建筑抢修

反悔贪心

对 t2t2 按升序排序，对于第 ii 个，如果不能在 t2t2 内完成，那么前 ii 个就最多只能修 i−1i-1 个，贪心的取 t1t1 最小的就行了，只需要用堆维护一下。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>

using namespace std;

namespace IO
{
    template <typename T>
    inline 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;
        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 = 150005;
int n;
struct node
{
    int t1, t2;
    friend bool operator < (node x, node y)
    {
        return x.t2 < y.t2;
    }
} a[N];
priority_queue <int> que;
int T, ans;

int main()
{
    read(n);
    for(int i = 1; i <= n; i++)
        read(a[i].t1), read(a[i].t2);
    sort(a + 1, a + 1 + n);

    for(int i = 1; i <= n; i++)
    {
        if(T + a[i].t1 > a[i].t2)
        {
            if(a[i].t1 < que.top())
            {
                T -= que.top();
                que.pop();
                T += a[i].t1;
                que.push(a[i].t1);
            }
        }
        else
        {
            T += a[i].t1;
            que.push(a[i].t1);
            ans++;
        }
    }
    write(ans), putchar('\n');
    return 0;
}
// A.S.

JSOI2007 文本生成器

AC自动机上 dp

正难则反

用总数减去不合法的，dp 时只需要保证不经过单词的结尾。

设 fi,jf_{i,j} 表示长度为 ii，在AC自动机上走到了 jj 的方案数，转移的时候判一下是不是单词的结尾就行了。

最后答案 ans=26m−∑i=1totfm,ians=26^m-\sum_{i=1}^{tot}f_{m,i}

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

const int N=6010;
const int p=1e4+7;
char s[110];
int trie[N][30],tot,f[110][N];
bool val[N];

void ins(char s[])
{
	int len=strlen(s),c=0;
	for(int i=0;i<len;i++)
	{
		int n=s[i]-'A';
		if(!trie[c][n]) trie[c][n]=++tot;
		c=trie[c][n];
	}
	val[c]=true;
}

queue<int>que;
int fail[N];
void build()
{
	for(int i=0;i<26;i++)
		if(trie[0][i]) que.push(trie[0][i]);
	while(!que.empty())
	{
		int c=que.front();
		que.pop();
		for(int i=0;i<26;i++)
		{
			if(trie[c][i]) fail[trie[c][i]]=trie[fail[c]][i],val[trie[c][i]]|=val[fail[trie[c][i]]],que.push(trie[c][i]);
			else trie[c][i]=trie[fail[c]][i];
		}
	}
}

int qpow(int a,int b)
{
	int res=1;
	a%=p;
	while(b)
	{
		if(b&1) res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s);
		ins(s);
	}
	build();
	f[0][0]=1;
	for(int i=0;i<m;i++)
		for(int j=0;j<=tot;j++)
			for(int k=0;k<26;k++)
				if(!val[trie[j][k]])
					f[i+1][trie[j][k]]=(f[i+1][trie[j][k]]+f[i][j])%p;

	int ans=qpow(26,m);
	for(int i=0;i<=tot;i++)
		ans=(ans-f[m][i]+p)%p;
	printf("%d\n",ans);
	return 0;
}
// A.S.

HNOI2006 超级英雄

二分图最大匹配板子

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int N = 2010;
int n,m;
vector <int> G[N];
int tim, match[N],t[N],ans[N];

bool dfs(int u)
{
	for(int i = 0; i < G[u].size(); i++)
	{
		int v = G[u][i];
		if(t[v] == tim) continue;
		t[v] = tim;
		if(!match[v] || dfs(match[v]))
		{
			match[v] = u;
			ans[u] = v - m;
			return true;
		}
	}
	return false;
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		G[i].push_back(m + x);
		G[i].push_back(m + y);
	}
	int sum = 0;
	tim = 1;
	for(int i = 1; i <= m; i++, tim++)
		if(dfs(i)) sum++;
		else break;
	printf("%d\n", sum);
	for(int i = 1; i <= sum; i++)
		printf("%d\n",ans[i]);
	return 0;
}
// A.S.

ZJOI2006 物流运输

观察到 n≤100,m≤20n\le 100,m\le 20

这不随便写（？但其实还是挺难的

先考虑如何 dp

设 fif_i 表示到第 ii 天的最小花费

转移 fi=min{fj+gj+1,i×(i−j)+k}f_i=min\{f_{j}+g_{j+1,i}\times (i-j)+k\}

表示第 jj 天换路线，从 j+1j+1 到 ii 天不换路线，其中 gj+1,ig_{j+1,i} 就表示其最小花费，这个是可以 O(n3m)O(n^3m) 枚举两天并去掉不能走的点，然后 O(nlog⁡n)O(n\log n) 跑最短路预处理的（够暴力吧

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
#define ll long long

using namespace std;

namespace IO
{
    template <typename T>
    inline 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;
        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 = 110;
int t, n, k, m, d;
struct edge
{
    int v, w, nxt;
} e[N * N];
int head[N], tot;

void link(int u, int v, int w)
{
    e[++tot] = (edge) {v, w, head[u]};
    head[u] = tot;
}

queue <int> que;
int dis[N];
bool vis[N], flag[N], cl[N][N];

void spfa()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    que.push(1), vis[1] = 1;
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        vis[u] = 0;
        for(int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].v;
            if(flag[v]) continue;
            if(dis[v] > dis[u] + e[i].w)
            {
                dis[v] = dis[u] + e[i].w;
                if(!vis[v]) que.push(v), vis[v] = 1;
            }
        }
    }
    return;
}

ll g[N][N], f[N];

void dp()
{
    for(int i = 1; i <= t; i++)
    {
        f[i] = g[1][i] * i;
        for(int j = 1; j < i; j++)
            f[i] = min(f[i], f[j] + g[j + 1][i] * (i - j) + k);
    }
    return;
}

int main()
{
    read(t), read(n), read(k), read(m);
    for(int i = 1, u, v, w; i <= m; i++)
    {
        read(u), read(v), read(w);
        link(u, v, w), link(v, u, w);
    }
    read(d);
    for(int i = 1, p, a, b; i <= d; i++)
    {
        read(p), read(a), read(b);
        for(int j = a; j <= b; j++) cl[p][j] = 1;
    }

    for(int i = 1; i <= t; i++)
        for(int j = 1; j <= t; j++)
        {
            memset(flag, 0, sizeof(flag));
            for(int k = 1; k <= n; k++)
                for(int p = i; p <= j; p++)
                    if(cl[k][p]) flag[k] = 1;
            spfa();
            g[i][j] = dis[n];
        }

    dp();
    write(f[t]);

    return 0;
}
// A.S.