【ZROI】ZROI 2019普及组Day3-题解

Problem A

题目链接

点我康题目

(ps.所有题目链接均需要开启ZROI普及组5联测权限)

---

分析

一道送分题目。

我们共有$3$种不同的走法，分别是不坐缆车，从$a$处上车$b$处下车，从$b$处上车$a$处下车。

这三种走法需要走路的长度分别为$|y - x|$ , $|x - a| + |y - b|$ , $|x - b| + |y - a|$。

因此，我们只需要分别算出$3$种走法的长度，然后取$min$即可

---

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline

using namespace std;

int x , y , a , b;

int main(){
    cin >> x >> y >> a >> b;
    cout << min(min(abs(y - x) , abs(x - a) + abs(b - y)) , abs(x - b) + abs(a - y));
    return 0;
}

---

Problem B

题目链接

点我康题目

---

分析

一道典型的搜索题。

首先，我们很容易想到可以直接枚举这个数中的每一位取与不取以及他们的顺序，但这样做最坏的时间复杂度高达$O(13!)$，而且很不好写。

因此，我们可以转换一下思路：直接枚举从$0$到根号下$n * 10$是否可行。

这样做虽然看起来时间复杂度很大，但我们所要做的工作就只是判断这个数可不可行，也就减少了多余的计算。

并且我们从小到大枚举，输出的顺序也就正好满足了题目要求。

但要注意，枚举的范围是从$0$到根号下$n 10$，因为当原数中的每一位调换顺序后可能会比原数要大，但显然小于要$n 10$.

---

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 14

using namespace std;

int t[N] , s[N];

bool check(ll n){	
	memset(t , 0 , sizeof(t));	
	do{
		t[n % 10] ++;	
		n /= 10;
	}while(n);
	for(int i = 0; i <= 9; i ++){
		if(t[i] > s[i]){
			return false;
		}
	}
	return true;
}

int main(){
	ll n;
	while(scanf("%lld" , &n)){
		if(n == 0){
			break;
		}
		memset(s , 0 , sizeof(s));
		ll num = n;
		while(num){
			s[num % 10] ++;	
			num /= 10;
		}
		for(ll i = 0; i <= sqrt(n * 10); i ++){
			if(check(i) && check(i * i)){
				printf("%lld * %lld = %lld\n" , i , i , i * i);
			}
		}
	}
	return 0;
}

---

Problem C

题目链接

点我康题目

---

分析

一道背包问题的改版。

认真读题，不难注意到题目中写着每种酒有且只有一瓶。而且题目要求价值最大化。因此，这是一道$01$背包问题

又因为题目让我们输出最大方案数，因此，我们需要使用$01$背包计数

状态转移方程为:$fj += f{j - d_i}$

---

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 2001

using namespace std;

int t , n , m;
int f[N] , d[51];
ll num = 0;

void Clear(){
    memset(f , 0 , sizeof(f));
    memset(d , 0 , sizeof(d));
    f[0] = 1;
    num = 0;
}

int main(){
    cin >> t;
    while(t --){
        Clear();
        cin >> n >> m;
        for(int i = 1; i <= n; i ++){
            cin >> d[i];
            num += d[i];
        }
        ll ans = 0;
        sort(d + 1 , d + 1 + n);
        num -= d[n];
        for(int i = n; i >= 2; i --){
            num -= d[i - 1];
            for(int j = m; j >= d[i]; j --){
                f[j] += f[j - d[i]];
            }
            for(int j = m - num; d[i - 1] > m - num - j && j > 0; j --){
                ans += f[j];
            }
        }
        cout << ans + 1 << "\n";
    }
    return 0;
}

---

Problem D

题目链接

点我康题目

---

分析

一道数据结构题

题目中给出的删除操作并不好实现，因此，我们考虑使用星球大战的套路，把删除改为重建。

这样的话，题目就转变为了将多个连通块合成一个连通块。

我们将询问排序，然后按照时间顺序处理询问。

实现时，用并查集维护连通性即可。

---

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 1501

using namespace std;

struct Node{
    int from;
    int to;
    int dis;
    bool operator < (const Node &b) const{
        return dis > b.dis;
    }
}node[N * N];

struct Ask{
    int w , id;
    bool operator < (const Ask &b) const{
        return w > b.w;
    }
}ask[100007];

const int dx[] = {0 , 1 , 0 , -1};
const int dy[] = {1 , 0 , -1 , 0};

int t , n , m , k;
int map[N][N] , pre[N * N] , size[N * N] , ans[N * N];

int find(int root){
    if(pre[root] == root){
        return root;
    }
    else{
        return pre[root] = find(pre[root]);
    }
}

I int id(int x, int y) {
    return (x - 1) * m + y;
}

void Solve(){
    int node_num = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            cin >> map[i][j];
            node[++ node_num] = Node{i , j , map[i][j]};
        }
    }
    for(int i = 1; i <= node_num; i ++){
        pre[i] = i;
        size[i] = 1;
    }
    cin >> k;
    for(int i = 1; i <= k; i ++){
        cin >> ask[i].w;
        ask[i].id = i;
    }
    sort(ask + 1 , ask + 1 + k);
    sort(node + 1 , node + 1 + n * m);
    
    int tot = 0 , prt = 1;
    int x , y , tx , ty , u , v;

    for(int i = 1; i <= k; i ++){
        while(prt <= n * m && node[prt].dis > ask[i].w){
            tot ++;
            x = node[prt].from;
            y = node[prt].to;
            for(int j = 0; j <= 3; j ++){
                tx = x + dx[j];
                ty = y + dy[j];
                if(tx >= 1 && ty >= 1 && tx <= n && ty <= m && map[tx][ty] > ask[i].w){
                    u = find(id(x , y));
                    v = find(id(tx , ty));
                
                    if(u == v){
                        continue;
                    }
                    if(size[u] < size[v]){
                        pre[u] = v;
                    }
                    else if(size[u] > size[v]){
                        pre[v] = u;
                    }
                    else{
                        pre[u] = v;
                        size[v] ++;
                    }
                    tot --;
                }
            }
            prt ++;
        }
        ans[ask[i].id] = tot;
    }
    for(int i = 1; i <= k; i ++){
        cout << ans[i] << " ";
    }
    puts("");
}

int main(){
    ios :: sync_with_stdio(false);
    cin >> t;
    for(int i = 1; i <= t; i ++){
        Solve();
    }
    return 0;
}

---

THE END