第 45 屆國際大學生程式設計競賽（ICPC）亞洲網上區域賽模擬賽題解（除了C、G之后補）-有解無憂

這次比賽好多原題呀…（就是那種稍微拓展了一點的原題）

A、Easy Equation

在這里插入圖片描述
題目大意：求 x + y + z = k x+y+z=k x+y+z=k的方案數，輸入為四個數可取的范圍，

前綴和差分，

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

之前做過一道簡化版的題，是求 x + y = z x+y=z x+y=z的方案數，用的好像是什么前綴和映射思想，我忘了，是CF上面的一次比賽題，但是我找不到了…這里是三個，所以把那個方法拓展一下即可，

實際上用前綴和來解決思路特別簡單，大致是一個前綴和+遞推DP的思想，

因為有三個數相加的方案數

我們用 f[i] 表示i能夠被多少個前兩個范圍的數（x+y）加起來的方案數，我們直接回圈x，那么所有從 x 到 x+b的數都能被這個數遞推過去，方案數+1，我們可以直接用前綴和來維護一個區間+1的操作，這樣求得 f 陣列，然后我們用同樣的思路求g陣列，其中g[i]表示的是i能夠被多少個x+y+z的方案數，同樣的我們維護一個前綴和差分，再求一次前綴和就是所有能通過x+y+z得到這個數的方案數，我們直接列舉所有d的范圍，求和既是答案，

一個小插曲

#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 = 1; 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 = 1 ;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;
}

看了一位大佬的博客，說是因為測驗數弱，實際上應該加一些特判
博客鏈接：我是傳送門

先考慮在左上，右下，0個，再考慮正方形，是2*x-2，剩下都是2，

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll x,y,a,b;
    cin>>x>>y>>a>>b;
    if((a==x&&b==1)||(a==1&&b==y))
    {
        printf("0\n");
    }else if(a==1&&b==1&&x==y)
    {
        printf("1\n");
    }else{
        if(x==y)
        {
            printf("%lld\n",2*x-2);
        }else{
            printf("2\n");
        }
    }
    return 0;
}

D、Pokemon Ultra Sun

在這里插入圖片描述
題目大意：寶可夢們大戰，你和對手都有一個血量，每一輪都是你打對手，攻擊力為w，每次有p的概率對手掉血，1-p的概率你自己掉血，求比賽輪數的期望，

概率DP板子題…

我們用 f[i][j] 表示我方掉i血敵方掉j血的期望，
然后直接輸出即可，

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

using namespace std;

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

int n, m, t;
int hp1, hp2, w;
double f[N][N];
double p;

int main()
{
    scanf("%d", &t);
    while(t -- ){
        scanf("%d%d%d%lf", &hp1, &hp2, &w, &p);
        memset(f, 0, sizeof f);
        for(int i = 1; i <= hp1; ++ i){
            for(int j = 1; j <= hp2; ++ j){
                f[i][j] = f[max(0, i - w)][j] * (1 - p) + f[i][max(0, j - w)] * p + 1.0;
            }
        }
        printf("%.6f\n", f[hp1][hp2]);
    }
    return 0;
}

E、Eat Walnuts

在這里插入圖片描述
題目大意：一排的核桃，你每次可以從連續的三個中拿走中間的那一個，花費為a[i - 1] * a[i] * a[i + 1]，求拿的只剩下兩個核桃的最小花費，

其實就是一道區間DP的板子題，之前有一道最優矩陣鏈乘的題，幾乎一摸一樣，只不過計算方法改了一點，主要是這里需要至少三個核桃才能拿走一個，所以我們需要規定長度至少為3，然后初始化的時候應該初始化f[i][i] = 0; f[i][i + 1] = 0;，而最優矩陣鏈乘中兩個數表示兩個矩陣，所以初始條件和長度不一樣，區間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

在這里插入圖片描述
題目翻譯 ♂：

Banana先生和Kazuya先生是新日暮里的著名哲學家，新日暮里的國王范（Van）無法在沒有他們的情況下管理帝國，因此他將左右監護人的頭銜賦予他們，

由于政治上的差異，他們處于相反的立場，新日暮里每天都有早會，范需要設計兩條路線，以便香蕉先生和和也雅先生可以參加早會，使事情變得難以管理的是，如果一條道路（不包括兩個終點）既屬于香蕉先生的道路又屬于Kazuya的道路，那么它們將相互搏斗，

一般而言，新日暮里由n個城市和m條沒有自環的雙向道路組成，最多有一條道路連接任何兩個城市，Banana先生居住在1號城市，Kazuya先生居住在2號城市，n和n ? 1城市有兩個豪華轎車，他們應該參加早上的會議，更正式地：

如果道路在香蕉先生的路線上，那么它就不能可以在和Kazuya的路線上，反之亦然，（也就是他們的路線不能有交叉）

如果Banana先生應該在n城市使用豪華轎車，而Kazuya應該在n-1城市使用豪華轎車，（也就是🍌要到點n，Kazuya要到點n-1）

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

結果又是原題，還是我兩周前剛做過的題，正解是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<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>

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;
}

I 、Character Wheels

在這里插入圖片描述
題目大意：給你一個n*n的字串矩陣，其中n是偶數，我們從外向里編號為1~n，每次輸入P表示輸出這個矩陣，L、x、t表示第x圈向左（逆時針）轉t圈，R同理，

其實就是一個大模擬，會讓你轉然后輸出，我們可以標記一下當前一共需要轉多少次，最后輸出的時候直接判斷一下畫圖輸出即可，因為只有四種情況，畢竟正方形，轉四圈就會轉回來，然后一直是一個回圈節，所以我們只需要考慮%4，分別畫圖計算出轉0，1，2，3次的位置輸出即可，不用真的每次都把圖轉過來，這樣寫出來代碼比較簡單，（輸入字符還是cin好用，不用擔心什么奇怪的換行符，空格符，輸出的時候可以用printf快一點）

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

using namespace std;

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

int n, m;
int a[N];
char g[N][N], op;
int num;
int rota[N];//rota[i]表示第i圈要順時針轉多少圈

int get_num(int x, int y)//得到圈數，畫個圖就好
{
    int minv = min(x, y);//一側
    int maxv = n + 1 - max(x, y);//另一側
    return min(minv, maxv);//最小既是圈數
}

void print()
{
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= n; ++ j){
            num = get_num(i, j);
            int t = rota[num];
            if(t == 1)
                printf("%c", g[n + 1 - j][i]);//自己畫圖理解
            else if(t == 2)
                printf("%c", g[n + 1 - i][n + 1 - j]);
            else if(t == 3)
                printf("%c", g[j][n + 1 - i]);
            else printf("%c", g[i][j]);
        }
        puts("");
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= n; ++ j){
            cin >> g[i][j];
        }
    }
    scanf("%d", &m);
    while(m -- ){
        cin >> op;
        if(op == 'P'){
            print();
        }
        else if(op == 'L'){
            int x, t;
            scanf("%d%d", &x, &t);
            rota[x] -= t;
            while(rota[x] < 0)//順時針轉3圈等于逆時針轉1圈
                rota[x] += 4;
        }
        else {
            int x, t;
            scanf("%d%d", &x, &t);
            rota[x] += t;
            rota[x] %= 4;
        }
    }
    return 0;
}

J、K-th route

在這里插入圖片描述
~~圖我收了~~

待補，

先放一個大佬的代碼：

#include <bits/stdc++.h>
using namespace std;
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define ll long long
const int N=3e6;
ll f[N],a,b,c,d;
int main()
{
	ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--)
	{
		int x,y,k;
		cin>>x>>y>>k;
		if (k>(x+1)*(y+1)-1||x+y>k||(k-x-y)%2==1)
		{
			cout<<"NO"<<endl;
		} else
		{
			cout<<"YES"<<endl;
			int t=k-x-y;
			int f=t/(2*y);
			int x1=0,y1=0;;
			rep(i,1,f)
			{
				x1+=2;
				rep(j,1,y) cout<<"E";
				cout<<"S";
				rep(j,1,y) cout<<"W";
				cout<<"S";
			}
		    f=(t%(2*y))/2;
		    if (x1<x-1)
		    {
		    	rep(i,1,f) cout<<"E";
		    	cout<<"S";
		    	rep(i,1,f) cout<<"W";
		    	cout<<"S";
		    	x1+=2;
		    } else
		    {
		      rep(i,1,f)
			  {
				y1+=2;
				cout<<"SENE";
		      }
		    }
		    rep(i,x1,x-1) cout<<"S";
			rep(i,y1,y-1) cout<<"E";
			cout<<endl; 
		}
	}
	return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/200239.html

標籤：其他

上一篇：CSDN個人主頁下如何添加微信公眾號？

下一篇：二分查找演算法詳解

第 45 屆國際大學生程式設計競賽（ICPC）亞洲網上區域賽模擬賽 題解（除了C、G之后補）

目錄