1003-Wavy Tree

来源: 杭电杯超级联赛10 算法: 模拟, 贪心题目链接: https://acm.dingbacode.com/contest/problem?cid=1053&pid=1003 补完: Yes

题目链接

题意简述

一个数列被称为”波浪“，表示这个数列中的所有\(i（1<i<n）\)，满足\(a_{i-1}<a_i\&\&a_i>a{i+1}\)或者\(a_{i-1}>a_i\&\&a_i<a{i+1}\)。

让一个数字+1或者-1消耗一个代价。

给你一个数列，问你把它变成波浪数列的最小代价。

题目分析

这样的波浪数列即要求每个数字要么是”峰“，要么是”谷“，不能是”山坡上“的数字。

那么波浪数列可以分为两种：第一个数字是”峰“；或者第一个数字是”谷“。

首先思考贪心的策略：

一个数字\(a_i\)是峰的话，\(a_{i+1}\)就是谷。如果\(a_{i+1}\)本身就满足比\(a_i\)小的性质，我们就不用动它。如果不满足，我们让它消耗最少的代价变得满足条件：把\(a_{i-1}\)变成\(a_i-1\)。

反之亦然。

显然对每个相邻数字的操作来看，这样是最节省费用的策略。

那么这样简单粗暴的贪心策略是否会有后效性导致局部最优的决策得不到全局的最优解呢？

~~交一发问评测机呗。~~

错误的，没到最后时候不要浪费罚时啊！

我们来简单整个比较极端的样例测试一下。

这个策略让人担心的点是：符合要求就不调整的话，会不会把整个数列波动的中线带到很高或者很低的地方，从而使得后面的序列浪费很多代价呢？

那我们假设，一个数列长成这个鬼样：

把第一个点当作谷，前四个点都不需要操作。这会让后面的序列都被迫提高，而导致费用过高吗？

显然是不会的。

在这里第五个点不需要操作。或者假设它需要操作的话——比如它比第四个点更高，我们只把它调到比第四个点小1的位置。那第六个点要调到高于它，也就是和第四个点平齐的位置。那第七个点又不需要操作了。

而这里的不用操作的第五个或者第七个后面的点，显然不关心前面其他的点到底再什么鬼地方——策略中，\(i\)只需要和\(i-1\)比大小。

并且如果想把高于点团的这部分拉下来，反而浪费了调整它们需要的代价。

那再考虑一下如果在底下的点需要上调的情况：比如在这里第四个点很小。

那么让它比第三个点大的代价是和前一个点的差值+1。和让前面的点来迁就它的代价没有区别。并且由于第四个点是”峰“，我们还希望第五个点比它小。如果让前面的第三个点下降来迁就第四个点，让第五个点小于第四个点的可能性就更小，或者说本来第五个点就比较大的话，让第五个点小于第四个点的代价就更大。

且如果这个差值代价极大，大到比其他的费用和还大得多。那么让点1作为峰，点4作为谷的时候，就会因为不用修改点4剩下更多的费用，这个方案的结果就会替代前面的运算。

那么这个方案就是可以尝试的。

~~如果WA了再想别的吧磨叽20分钟就是一个罚时了。~~

关于代码，因为比较的时候只要拿\(a_i\)和前一个数修改后的结果比较，如果用一个变量比如\(now\)来记录这个比较值，就能在读入\(a_i\)的时候直接跑答案，用两个变量分别记录两种方案的结果，最后比较即可。

~~但我懒。~~要区分谁是谁的\(3*n\)复杂度不如复制粘贴的\(n+n+n\)复杂度。

核心代码be like：

剩下的复制粘贴吧！

完整代码

#include<iostream>
using namespace std;
int a[1000010];
int main(){
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		int now=a[0];
		long long ans=0; 
		for(int i=1;i<n;i++){
			if(i%2==0){//大 
              //核心在这↓
				if(a[i]>now){
					now=a[i];
				}
				else{
					now+=1;
					ans+=now-a[i];
				}
			}
			else{//小 
				if(a[i]<now){//换个符号 
					now=a[i];
				}
				else{
					now-=1;//加减改一下 
					ans+=a[i]-now;//前后翻一下 
				}
			}
		}
		long long anss=ans;//记录上一个答案 
		now=a[0];
		ans=0; //两个变量初始化 
		
		for(int i=1;i<n;i++){
			if(i%2!=0){//整段for复制过来只改了这行 
				if(a[i]>now){
					now=a[i];
				}
				else{
					now+=1;
					ans+=now-a[i];
				}
			}
			else{
				if(a[i]<now){
					now=a[i];
				}
				else{
					now-=1;
					ans+=a[i]-now;
				}
			}
		}
		anss=min(anss,ans);
		cout<<anss<<'\n';
	}
	return 0; 
}

1007-Even Tree Split

来源: 杭电杯超级联赛10 算法: DFS, 图论题目链接: https://acm.dingbacode.com/contest/problem?cid=1053&pid=1007 补完: Yes 完成时间: August 18, 2022

题解

给含\(n\)个节点的无向树, 可任意删除边形成不同的分量集.

问删除后各个分量都含偶数个点的划分方案数量.

若有子树含偶数个点, 那么此子树就可以被分离出来.

整个树上有\(num\)个可分离的位置, 组合就有答案\(2^{num}\)种方案, 排除不删除的方案就有\(ans=2^{num}-1\).

DFS过程中会对根结点也判断一次可否分离故\(num\)需要再减\(1\)

注意多组数据时需要严格初始化.

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll P = 998244353;
const int MAXN = 200005;

vector<int> e[MAXN];
int cnt[MAXN];
int num;

ll Mul(ll a, ll b){
    return (a * b) % P;
}
ll Pow(ll a, ll n){
    ll ans = 1;
    while (n) {
        if (n & 1) ans = Mul(a, ans);
        a = Mul(a,a);
        n >>= 1;
    }
    return ans;
}

void dfs(int u,int f){
    cnt[u] = 0;
    for (auto v: e[u]) {
        if (v==f)continue;
        dfs(v,u);
        cnt[u] += cnt[v] + 1;
    }
    if (cnt[u]%2) {
        num++;
    }
}

void solve() {
    int n;
    cin>>n;
    num = 0;
    for (int i = 1; i <= n; i++) {
        e[i].clear();
    }
    for (int i = 1; i < n; i++) {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    cout<<Pow(2,num-1)-1<<"\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

Shelter

2022杭电杯超级联赛10

1003-Wavy Tree

题意简述

题目分析

完整代码

1007-Even Tree Split

题解

代码