noip2021训练2(USACO)

2023-11-11 18:31:10

Link

[USACO10MAR] Great Cow Gathering G

换根 dp 板子

先用树形 dp 求出以 \(1\) 为根的最小不方便值，然后 bfs 向儿子换根

\(f_v=f_u + (siz_u - siz_v \times 2) \times w\)

这个手推一下就好了，大概就是把两边子树中的点经过 \((u,v)\) 这条边的代价算一下。

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

using namespace std;

const int N = 1e5 + 5;
int n, c[N];
struct edge
{
    int v, w, nxt;
}e[N << 1];
int head[N], tot;

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

ll f[N], siz[N], ans;

void dfs(int u, int fa)
{
    siz[u] = c[u];
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if(v == fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
        f[u] += f[v] + siz[v] * e[i].w;
    }
    return;
}

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

void bfs()
{
    ans = 1e18;
    que.push(1);
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        ans = min(ans, f[u]);
        for(int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].v;
            f[v] = f[u] + (siz[u] - siz[v] * 2) * e[i].w;
            siz[v] = siz[u];
            que.push(v);
        }
    }
    return;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    for(int i = 1, u, v, w; i < n; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w), add(v, u, w);
    }
    dfs(1, 0);
    bfs();
    printf("%lld\n", ans);
    return 0;
}

[USACO09FEB] Stock Market G

CSP-J2019 T3 原题

感觉思路还是比较难的，虽然代码难度极低

要求最终能获得的最大钱数，其实可以分别对每一天，求当天能获得的最大钱数。

对于每个物品在每天，有三种情况：

  1. 不买
  2. 今天买，明天卖
  3. 今天买，过几天卖

其实第三种可以通过第二种实现

今天买了，明天卖掉，然后明天再买，后天卖掉...

就相当于今天买了，过几天再卖。

所以就两种情况，然后就是一个完全背包了

设 \(f_i\) 表示手上有 \(i\) 元钱时最大收益，注意总钱数要每天更新。

Code
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 5;
int n, m, s, p[55][15];
int f[MAXN];

int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &p[i][j]);
    for(int j = 2; j <= m; j++)
    {
        int mx = 0;
        memset(f, 0, sizeof(f));
        for(int i = 1; i <= n; i++)
        {
            for(int k = p[i][j - 1]; k <= s; k++)
            {
                f[k] = max(f[k], f[k - p[i][j - 1]] + p[i][j] - p[i][j - 1]);
                mx = max(mx, f[k]);
            }
        }
        s += mx;
    }
    printf("%d\n", s);
    return 0;
}

USACO13MAR Necklace G

这里用的 AC自动机，也可以用 kmp，但如果有多个不能出现的子串就不行了。

正难则反，求出最多能保留多少，然后减一下就行了

先建出 AC自动机，在上面 dp

设 \(f_{i,j}\) 表示在第 \(i\) 个位置，在 AC自动机上走到了 \(j\) 时最多能保留多长

如果 \(j\) 不是子串的末尾，\(f_{i,j}=max(f_{i,j},f_{i-1,j})\)

令 \(k=trie_{j,a_i}\)，也就是在 AC自动机上从 \(j\) 向后沿着 \(a_i\) 走到哪个点。

如果 \(k\) 不是子串的末尾，\(f_{i,k}=max(f_{i,k},f_{i-1,j}+1)\)

Code
#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 5;
char a[N], b[N];
int n, m, nxt[N];
int trie[N][30], tot, ed;
int fail[N];
int f[N][1010];

void insert(char s[])
{
    int len = strlen(s + 1), x = 0;
    for(int i = 1; i <= len; i++)
    {
        int c = s[i] - 'a';
        if(!trie[x][c]) trie[x][c] = ++tot;
        x = trie[x][c];
    }
    ed = x;
    return;
}

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

int main()
{
    scanf("%s%s", a + 1, b + 1);
    n = strlen(a + 1), m = strlen(b + 1);
    insert(b), build();
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
        {
            if(j != ed) f[i][j] = max(f[i][j], f[i - 1][j]);
            int k = trie[j][a[i] - 'a'];
            if(k != ed) f[i][k] = max(f[i][k], f[i - 1][j] + 1);
        }
    int ans = 0;
    for(int i = 0; i <= m; i++)
        ans = max(ans, f[n][i]);
    printf("%d\n", n - ans);
    return 0;
}

USACO12DEC Running Away From the Barn G

神奇的树上差分

因为只求子树内的，所以第 \(i\) 个点的贡献只在这个点到根的链上

所以预处理每个点的深度，然后对每个点向上倍增找到最高的能产生贡献的点，链上都要 \(+1\)，做个差分即可。

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

using namespace std;

const int N = 2e5 + 5;
int n, m;
int f[N][25], dep[N];
int val[N];

int Find(int x)
{
    int d = dep[x];
    for(int i = 20; i >= 0; i--)
        if(d - dep[f[x][i]] <= m)
            x = f[x][i];
    return f[x][0];
}

signed main()
{
    scanf("%lld%lld", &n, &m);
    for(int i = 2; i <= n; i++)
    {
        int w;
        scanf("%lld%lld", &f[i][0], &w);
        dep[i] = dep[f[i][0]] + w;
        for(int j = 1; j <= 20; j++)
            f[i][j] = f[f[i][j - 1]][j - 1];
    }
    for(int i = n; i >= 1; i--)
    {
        int x = Find(i);
        val[x]--, val[i]++;
    }
    for(int i = n; i >= 1; i--)
        val[f[i][0]] += val[i];
    for(int i = 1; i <= n; i++)
        printf("%lld\n", val[i]);
    return 0;
}

USACO18FEB Snow Boots G

见 noip2021训练1 最后一题

USACO12FEB Nearby Cows G

非常的套路

分别求出每个点子树内的答案和子树外的答案，求和即可。

在求子树外的时候细节还是比较多

初始化数组不要 memset()，那样复杂度就变成 \(O(n^2)\) 了，需要用多少就初始化多少。

Code
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 1e5 + 5;
int n, m, c[N];
vector <int> G[N];
int f[N][25], g[N][25], pre[25], suf[N][25];

void dfs1(int u, int fa)
{
    for(int i = 0; i <= m; i++)
        f[u][i] = c[u];
    for(auto v : G[u])
    {
        if(v == fa) continue;
        dfs1(v, u);
        for(int i = 1; i <= m; i++)
            f[u][i] += f[v][i - 1];
    }
    return;
}

void dfs2(int u, int fa)
{
    vector <int> ch;
    for(auto v : G[u])
        if(v != fa) ch.pb(v);
    
    memset(pre, 0, sizeof(pre));
    for(int i = 0; i <= (int)ch.size(); i++)
        for(int j = 0; j <= m; j++)
            suf[i][j] = 0;

    for(int i = (int)ch.size() - 1; i >= 0; i--)
    {
        int v = ch[i];
        for(int j = 0; j <= m; j++)
            suf[i][j] = suf[i + 1][j] + f[v][j];
        for(int j = 1; j <= m; j++)
            g[v][j] = c[u];
    }

    for(int i = 0; i < (int)ch.size(); i++)
    {
        int v = ch[i];
        for(int j = 2; j <= m; j++)
            g[v][j] += pre[j - 2] + suf[i + 1][j - 2] + g[u][j - 1];
        for(int j = 0; j <= m; j++)
            pre[j] += f[v][j];
    }

    for(auto v : ch) dfs2(v, u);
    return;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1, u, v; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        G[u].pb(v), G[v].pb(u);
    }
    for(int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    dfs1(1, 0);
    dfs2(1, 0);
    for(int i = 1; i <= n; i++)
        printf("%d\n", f[i][m] + g[i][m]);
    return 0;
}

USACO05DEC Layout G

差分约束板子题

\(dis_x-dis_y\le w\qquad dis_x\le dis_y+w\qquad add(y,x,w)\)

\(dis_x-dis_y\ge w\qquad dis_y\le dis_x-w\qquad add(x,y,-w)\)

有负环无解，\(dis_n=inf\) 可以无穷远

（很久以前的代码了）

Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 1010
#define M 21010
#define INF 0x3f3f3f3f

using namespace std;

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

void add(int a,int b,int d)
{
	e[++tot]=(edge){b,d,head[a]};
	head[a]=tot;
}

int dis[N],vis[N],cnt[N];

void spfa(int S)
{
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	for(int i=0; i<=n; i++)
		dis[i]=(i==S)?0:INF;
	queue<int>que;
	vis[S]=1;
	que.push(S);
	while(!que.empty())
	{
		int u=que.front();
		que.pop();
		vis[u]=0;
		if((++cnt[u])>=n)
		{
			printf("-1\n");
			exit(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;
				}
			}
		}
	}
}

int main()
{
	scanf("%d%d%d",&n,&ml,&md);
	for(int i=1; i<=ml; i++)
	{
		int a,b,d;
		scanf("%d%d%d",&a,&b,&d);
		add(a,b,d);
	}
	for(int i=1; i<=md; i++)
	{
		int a,b,d;
		scanf("%d%d%d",&a,&b,&d);
		add(b,a,-d);
	}
	for(int i=1; i<=n; i++)
		add(0,i,0);
	spfa(0);
	spfa(1);
	if(dis[n]==INF) printf("-2\n");
	else printf("%d\n",dis[n]);
	return 0;
}

USACO08MAR Land Acquisition G

斜率优化板子题，暑假的时候学长讲过，但当时没写 qaq

我把 \(x,y\) 分别当作长和宽

首先可以将被包含的矩形去掉，然后剩下的矩形 \(x\) 递增，\(y\) 递减

设 \(f_i\) 表示前 \(i\) 个矩形的最小代价

\(f_i=min\{f_{j-1}+x_i\times y_j\}\ (1\le j \le i)\)

现在已经有了 \(O(n^2)\) 的暴力 dp，考虑优化

比较显然的斜率优化，先将式子变形一下

\(f_{j-1}=-x_i\times y_i+f_i\)

把 \(y_i\) 看作 \(x\)，\(f_{j-1}\) 看作 \(y\)，\(x_i\) 看作 \(k\)，\(f_i\) 看作 \(b\)

然后就得到了一次函数的基本形式 \(y=-k\times x + b\)

\(k\) 是已知的 \(x_i\) 并且递增，现在就是要最小化截距。

要维护一个下凸包，将已知斜率的一次函数与下凸包相切，就是最小的截距了。

维护下凸包可以用单调队列维护一个斜率递增的区间，当队首的斜率小于 \(x_i\) 时就已经没用了，因为后面的斜率递增，不可能再碰到队首了。

入队时只需要判断一下 队尾与队尾前一个点的斜率 和 \((y_i,f_{i-1})\) 与队尾的斜率 哪个大。

这个画图模拟一下就很好理解了，大概就是一个在一次象限的下凸包和斜率为负的一函数。

注意斜率是负的。

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

using namespace std;

const int N = 5e4 + 5;
int n;
struct node
{
    ll x, y;
    friend bool operator < (node a, node b)
    {
        return a.y == b.y ? a.x > b.x : a.y > b.y;
    }
}a[N];
int cnt, l, r, q[N];
db k[N];
ll f[N];

db slope(int i, int j)
{
    return (db)(f[j - 1] - f[i - 1]) / (db)(a[i].y - a[j].y);
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%lld%lld", &a[i].x, &a[i].y);
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++)
        if(a[cnt].x < a[i].x) a[++cnt] = a[i];

    l = 1, r = 0;
    for(int i = 1; i <= cnt; i++)
    {
        while(l < r && k[r - 1] >= slope(q[r], i)) r--;
        k[r] = slope(q[r], i), q[++r] = i;
        while(l < r && k[l] <= a[i].x) l++;
        f[i] = f[q[l] - 1] + a[i].x * a[q[l]].y;
    }

    printf("%lld\n", f[cnt]);
    return 0;
}

USACO17FEB Why Did the Cow Cross the Road III G

看到这题第一反应就是树状数组，然后试了试，过了样例，写完就过了（？

其实就是求每个数两次出现的位置间有多少个数出现了一次。

用树状数组维护前缀和，如果 \(a\) 是第一次出现，直接 \(+1\)，否则将答案加上两次出现位置中间的和。

其实就是中间出现了一次的数的个数。

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

using namespace std;

const int N = 1e5 + 5;
int n, a[N], pos[N];
ll c[N], ans;

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

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

int main()
{
    scanf("%d", &n);
    n <<= 1;
    for(int i = 1; i <= n; i++)
    {
        int a;
        scanf("%d", &a);
        if(!pos[a]) add(i, 1), pos[a] = i;
        else add(pos[a], -1), ans += qry(i) - qry(pos[a]);
    }
    printf("%lld\n", ans);
    return 0;
}

USACO13JAN Seating G

比较套路的线段树题

维护区间最长连续 \(1\) 的个数

分别维护最左边，最右边最长的长度，然后合并一下。

在查询时先找左边，再找中间（将两边合并起来），最后找右边。

Code
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;
int n, m, ans;

namespace seg
{
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)

    int mx[N << 2], lmx[N << 2], rmx[N << 2];
    int tag[N << 2], len[N << 2];

    void pushup(int rt)
    {
        lmx[rt] = lmx[ls];
        rmx[rt] = rmx[rs];

        if(lmx[rt] == len[ls]) lmx[rt] += lmx[rs];
        if(rmx[rt] == len[rs]) rmx[rt] += rmx[ls];

        mx[rt] = max(max(mx[ls], mx[rs]), rmx[ls] + lmx[rs]);
    }

    void build(int l, int r, int rt)
    {
        len[rt] = r - l + 1; 
        tag[rt] = -1;
        mx[rt] = lmx[rt] = rmx[rt] = len[rt];
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(l, mid, ls);
        build(mid + 1, r, rs);
    }

    void pushdown(int rt)
    {
        if(tag[rt] != -1)
        {
            mx[ls] = lmx[ls] = rmx[ls] = tag[rt] ? len[ls] : 0;
            mx[rs] = lmx[rs] = rmx[rs] = tag[rt] ? len[rs] : 0;
            tag[ls] = 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)
        {
            mx[rt] = lmx[rt] = rmx[rt] = v ? len[rt] : 0;
            tag[rt] = v;
            return;
        }
        pushdown(rt);
        int mid = (l + r) >> 1;
        update(L, R, v, l, mid, ls);
        update(L, R, v, mid + 1, r, rs);
        pushup(rt);
    }

    int query(int p, int l, int r, int rt)
    {
        if(l == r) return l;
        pushdown(rt);
        int mid = (l + r) >> 1;
        if(mx[ls] >= p) return query(p, l, mid, ls);
        if(rmx[ls] + lmx[rs] >= p) return mid - rmx[ls] + 1;
        return query(p, mid + 1, r, rs);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    seg :: build(1, n, 1);
    while(m--)
    {
        char op[5];
        scanf("%s", op);
        if(op[0] == 'A')
        {
            int p;
            scanf("%d", &p);
            if(seg :: mx[1] < p)
            {
                ans++;
                continue;
            }
            int l = seg :: query(p, 1, n, 1);
            seg :: update(l, l + p - 1, 0, 1, n, 1);
        }
        else
        {
            int a, b;
            scanf("%d%d", &a, &b);
            seg :: update(a, b, 1, 1, n, 1);
        }
    }
    printf("%d\n", ans);
    return 0;
}
上一篇：『学了就忘』Linux基础命令 — 27、搜索操作相关命令


下一篇：ls改进