第 45 屆國際大學生程式設計競賽（ICPC）亞洲網上區域賽模擬賽 部分題解

這次比賽好多原題呀…

A、Easy Equation

前綴和差分，

首先一看資料范圍是1e6就不可能 O ( n 2 ) O(n^2) O(n2)做，只能 O ( n ) O(n) O(n)，

之前做過一道簡化版的題，是求 x + y = z x+y=z x+y=z的方案數，用的是前綴和，這里是三個，所以把那個方法拓展一下即可，

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

using namespace std;

const int N = 1e8 + 7, M = 5000007, INF = 0x3f3f3f3f;

long long a, b, c, d;
long long f[N];
long long g[N];

int main()
{

    scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
    for(int i = 0; i <= a; ++ i){
        f[i] ++ ;
        f[i + b + 1] -- ;
    }
    for(int i = 0; i <= a + b; ++ i)
        f[i] += f[i - 1];
    for(int i = 0; i <= a + b; ++ i){
        g[i] += f[i];
        g[i + c + 1] -= f[i] ;
    }
    for(int i = 0 ;i <= a + b + c; ++ i)
        g[i] += g[i - 1];
    long long ans = 0;
    for(int i = 0; i <= d; ++ i)
        ans += g[i];
    printf("%lld\n", ans);
    return 0;
}

B、XTL’s Chessboard

SB題，直接輸出2就行了，因為所有的點沿著45度角射出反彈最后都會回到起點，x-1和y-1互質的時候一定會經過角，就會直接反彈原路回傳，所以只有起點和終點經過奇數次，答案就是2，

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

using namespace std;

const int N = 500007, M = 5000007, INF = 0x3f3f3f3f;

int n, m, t;
int a[N], b[N];
bool vis[N];
int ans;

int main()
{
    int x, y;
    while(scanf("%d%d%d%d", &n, &m, &x, &y) != EOF && n + m){
        printf("2\n");
    }
    return 0;
}

D、Pokemon Ultra Sun

概率DP板子題…

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;

signed main() {
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		int h1, h2, w;
		double p;
		cin >> h1 >> h2 >> w >> p;
		int n = (h1 + w - 1) / w, m = (h2 + w - 1) / w;
		vector<vector<double>>f(n + 2, vector<double>(m + 2));
		f[1][1] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				f[i + 1][j] += f[i][j] * (1 - p);
				f[i][j + 1] += f[i][j] * p;
			}
		}
		double ans = 0;
		for (int i = 1; i <= m; i++) ans += f[n + 1][i] * (n + i - 1);
		for (int i = 1; i <= n; i++) ans += f[i][m + 1] * (m + i - 1);
		cout << fixed << setprecision(6) << ans << '\n';
	}
	return 0;
}

E、Eat Walnuts

其實就是一道區間DP的板子題，之前有一道最優矩陣鏈乘的題，幾乎一摸一樣，只不過計算方法改了一點，

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

using namespace std;
typedef long long ll;
const int N = 2007, M = 5000007, INF = 0x3f3f3f3f;

int n, m;
int f[N][N];
int a[N];

int main()
{
    while(scanf("%d", &n) != EOF && n){
        memset(f, 0x3f, sizeof f);
        for(int i = 1; i <= n; ++ i){
            scanf("%d", &a[i]);
            f[i][i] = 0;
            f[i][i + 1] = 0;
        }

        for(int len = 2; len <= n; ++ len){
            for(int i = 1; i <= n - len + 1; ++ i){
                int j = i + len - 1;
                for(int k = i + 1; k < j; ++ k)
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j] + (a[i] + a[k] + a[j]) * (a[i] + a[k] + a[j]));
            }
        }
        printf("%d\n", f[1][n]);
    }
    return 0;
}

F、wrestling on road

比賽的時候時間比較短因為這道題沒人過，我都沒看這道題

結果又是原題，還是我兩周前剛做過的題，正解是LCA，我之前是用樹鏈剖分過的，

還沒A，晚上回來補一下

啊，是我看錯了，好像不能用樹鏈剖分，因為這不是樹…那沒事了

應該用tarjan縮點，或者LCA亂搞

//假的樹鏈剖分代碼，過不去，我題看錯了，等我有空了就補
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>

using namespace std;
typedef long long ll;
const int N = 500007, M = 5000007, INF = 0x3f3f3f3f;
const double eps = 1e-6;

int n, m;
int root, mod;
int head[N], ver[M], nex[M], tot;
int a[N], a_after[N];
struct Tree
{
    int l, r;
    int lz;
    int maxv;
}tr[N * 4];
int son[N];
int id[N], fa[N], cnt, deep[N], sizes[N];
int top[N];

void add(int x, int y)
{
    ver[tot] = y;
    nex[tot] = head[x];
    head[x] = tot ++ ;
}

inline void pushup(int p){
    tr[p].maxv = max(tr[p << 1].maxv, tr[p << 1 | 1].maxv);
}

inline void pushdown(int p)
{
    auto &root = tr[p], &left = tr[p << 1], &right = tr[p << 1 | 1];
    if(root.lz == 0)return ;
    left.lz += root.lz;
    right.lz += root.lz;
    left.maxv += root.lz;
    right.maxv += root.lz;
    root.lz = 0;
}

void build(int p, int l, int r)
{
    tr[p] = {l, r, 0, 0};
    if(l == r){
        tr[p].maxv = a_after[l];
        return ;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
}

int query(int p, int l, int r)
{
    if(tr[p].l >= l && tr[p].r <= r){
        return tr[p].maxv;
    }
    pushdown(p);
    int mid = tr[p].l +tr[p].r >> 1;
    int res = 0;
    if(l <= mid)res = max(res, query(p << 1, l, r));
    if(r > mid)res = max(res, query(p << 1 | 1, l, r));
    return res;
}

void modify(int p, int l, int r, int k)
{
    if(tr[p].l >= l && tr[p].r <= r){
        tr[p].lz += k;
        tr[p].maxv += k;
        return ;
    }
    int mid = tr[p].l + tr[p].r >> 1;
    pushdown(p);
    if(l <= mid)modify(p << 1, l, r, k);
    if(r > mid)modify(p << 1 | 1, l, r, k);
    pushup(p);
    return ;
}

void dfs_son(int x, int father, int deeps)
{
    deep[x] = deeps;
    fa[x] = father;
    sizes[x] = 1;
    int max_son = -1;
    for(int i = head[x]; ~i; i = nex[i]){
        int y = ver[i];
        if(y == father)continue;
        dfs_son(y, x, deeps + 1);
        sizes[x] += sizes[y];
        if(sizes[y] > max_son)son[x] = y, max_son = sizes[y];
    }
}

void dfs_build(int x, int topfa)
{
    id[x] = ++ cnt;
    a_after[cnt] = a[x];
    top[x] = topfa;
    if(!son[x])return ;
    dfs_build(son[x], topfa);
    for(int i = head[x]; ~i; i = nex[i]){
        int y = ver[i];
        if(y == fa[x] || y == son[x])continue;
        dfs_build(y, y);//每個節點都有從他自己開始的一個輕鏈
    }
}

void update_range(int x, int y, int k)
{
    while(top[x] != top[y]){
        if(deep[top[x]] < deep[top[y]])swap(x, y);
        modify(1, id[top[x]], id[x], k);
        x = fa[top[x]];
    }
    if(deep[x] > deep[y])
        swap(x, y);
        modify(1, id[x], id[y], k);
}

bool solve(int a1, int a2, int b1, int b2){
    update_range(a1, a2, 1);
    update_range(b1, b2, 1);
    if(tr[1].maxv == 2){
        return false;
    }
    update_range(a1, a2, -1);
    update_range(b1, b2, -1);
    return true;
}
int t;
int main()
{
    scanf("%d", &t);
    while(t -- ){
        memset(tr, 0, sizeof tr);
        memset(head, -1, sizeof head);
        tot = 0;
        scanf("%d%d", &n, &m);
        root = 1;
        for(int i = 1; i <= n - 1; ++ i){
            int x, y;
            scanf("%d%d", &x, &y);
            add(x, y);add(y, x);
        }
        dfs_son(root, 0, 1);
        dfs_build(root, root);
        build(1, 1, n);
        //1~n, 1 ~ n - 1//2~n, 2~n - 1
        bool flag = 0;
        if(solve(1, n, 2, n - 1))
            puts("Banana and kazuya won't be angry!"), flag = 1;
        if(!flag && solve(1, n - 1, 2, n))
            puts("Banana and kazuya won't be angry!"), flag = 1;
        if(!flag)puts("Van is in a dilemma!");
    }
    return 0;
}

H、Nuclear launch detected

DP

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, h, l, r, a[N];
int dp[N][205];
int f(int x) { x = (x%h+h)%h; return x>=l&&x<=r; }
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> h >> l >> r;
	for(int i=1; i<=n; i++)
	{
		cin >> a[i];
		a[i] = (a[i] + a[i-1])%h;
		for(int j=0; j<=min(i-1, h-1); j++)
		{
			dp[i][j] = max(dp[i][j], dp[i-1][j] + f(a[i]-j));
			dp[i][(j+1)%h] = max(dp[i][(j+1)%h], dp[i-1][j] + f(a[i]-j-1));
		}
	}
	int ans = 0;
	for(int i=0; i<h; i++) ans = max(ans, dp[n][i]);
	cout << ans << '\n';
	return 0;
}