CodeForces 1324 - Codeforces Round #627 (Div. 3)-有解無憂

第一次遇到這么水的div. 3，，，

本來想搶D一血的，結果失敗了，，然后干脆就$45\mathrm$AK了，，，

CodeForces比賽頁面傳送門

A - Yet Another Tetris Problem

洛谷題目頁面傳送門 & CodeForces題目頁面傳送門

給出$n$個數，第$i$個數為$a_i$，每次操作可以選擇一個$i\in[1,n]$并令$a_i=a_i+2$，或令$\forall i\in[1,n],a_i=a_i-1$，問能否經過若干次操作，將$a$陣列清零，本題多測，

結論顯然，能將$a$陣列清零當且僅當所有數奇偶性相同，

證明：若所有數奇偶性相同，顯然可以通過若干次第$1$種操作把它們變成兩兩相等，再通過若干次第$2$種操作把它們都變成$0$；若存在$2$個數$a_i,a_j$奇偶性不相同，則若對$a_i,a_j$做第$1$種操作，那么它們奇偶性不變，若做第$2$種操作，它們奇偶性互換，所以它們奇偶性永遠不可能相同，自然也無法都變成$0$，得證，

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
void mian(){
	int n;
	cin>>n;
	int x;
	cin>>x;
	x&=1;//a[1]的奇偶性
	n--;
	bool ok=true;
	while(n--){
		int y;
		cin>>y;
		ok&=x==(y&1);//奇偶性要全部相同
	}
	puts(ok?"YES":"NO");
}
int main(){
	int testnum;
	cin>>testnum;
	while(testnum--)mian();
	return 0;
}

B - Yet Another Palindrome Problem

洛谷題目頁面傳送門 & CodeForces題目頁面傳送門

給出$n$個數，第$i$個數為$a_i$，問是否存在長度至少為$3$的回文子序列，本題多測，

$n\in[3,5000],\sum n\leq5000$，

顯然，任何一個回文子序列的兩端相等，又因為要求長度至少為$3$，所以兩端的距離至少為$2$，于是存在$2$個距離至少為$2$且相等的數是存在長度至少為$3$的回文子序列的必要條件，若存在$2$個距離至少為$2$且相等的數，那么隨便選擇它們之間的任意一個數即可構成長度為$3$的回文子序列，于是存在$2$個距離至少為$2$且相等的數是存在長度至少為$3$的回文子序列的充分條件，綜上，存在$2$個距離至少為$2$且相等的數是存在長度至少為$3$的回文子序列的充要條件，

直接暴力列舉數對，時間復雜度$\mathrm O!\left(\sum n^2\right)$，

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
const int N=5000;
int n;
int a[N+1];
void mian(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)for(int j=i+2/*距離至少為2*/;j<=n;j++)if(a[i]==a[j])/*相等*/{puts("YES");return;}
	puts("NO");
}
int main(){
	int testnum;
	cin>>testnum;
	while(testnum--)mian();
	return 0;
}

C - Frog Jumps

洛谷題目頁面傳送門 & CodeForces題目頁面傳送門

有$n+2$個格子，編號$0\sim n+1$，$\forall i\in[1,n]$，格子$i$上有一個字母$a_i\in{\texttt L,\texttt R}$，分別表示在格子$i$上只能往左、右跳，青蛙一開始站在格子$0$，$a_0=\texttt R$，求一個最小的$d$，表示青蛙一次能跳$1\sim d$格且不能出格，使得青蛙能到達格子$n+1$，保證總有符合要求的$d$，本題多測，

首先，不難發現對于任意一個$d$，能到達的格子組成前綴，證明：反證法，若不組成前綴，即存在$i\in[1,n]$使得$i$不能到達且$i+1$能到達，此時必存在一個$x\in[0,i)$使得$a_x=\texttt R$且$x$能到達$[i+1,n+1]$中任意一個格子$y$，根據青蛙跳的規則，$[x+1,y]$內任意一個格子都能從$x$到達，又$x<i,y>i\Rightarrow i\in[x+1,y]$，與$i$不能到達矛盾，得證，

接下來，又~~雙叒叕~~不難發現往左跳的格子不起絲毫作用，即任意一個能到達的格子都可以只往右跳來到達，證明：數學歸納法，設對于某一個$d$，能到達的格子組成的前綴為$0,r$，

格子$0$顯然滿足可以只往右跳來到達；
$\forall x\in[1,r]$，假設$\forall i\in[0,x)$，格子$i$都滿足可以只往右跳來到達，對于$x$的某一種到達方式，設最后一步是由$y$跳過來的，分$2$種情況：
1. $y<x$，此時最后一步一定是往右跳，再加上$\forall i\in[0,x)$，格子$i$都滿足可以只往右跳來到達，可以得出格子$x$滿足可以只往右跳來到達；
2. $y>x$，此時在$y$的到達方式中，必有一步是從$z\in[1,x)$跳到$xx\in[x,n+1]$，根據青蛙跳的規則，$[z+1,xx]$內任意一個格子都能從$z$到達，又$x>z,x\leq xx\Rightarrow x\in[z+1,xx]$，所以$x$能被$z$往右跳到達，再加上$z\in[1,x)\subsetneq[0,x)$且$\forall i\in[0,x)$，格子$i$都滿足可以只往右跳來到達，可以得出格子$x$滿足可以只往右跳來到達，
綜上，若$\forall i\in[0,x)$，格子$i$都滿足可以只往右跳來到達，那么格子$x$滿足可以只往右跳來到達，

綜上，得證，

于是我們可以把所有$a_i=\texttt R$的$i$有序地抽出來組成序列$pos$，特殊地，$pos_{|pos|}=n+1$，顯然，$\forall i\in[1,|pos|),pos_i\to pos_{i+1}$，這種跳法最省$d$，要滿足每次跳，起點和終點的距離都在$d$以內，所以答案是$d=\max\limits_^{|pos|-1}{pos_{i+1}-pos_i}$，

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200000;
int n;
char a[N+5];
void mian(){
	cin>>a+1;
	n=strlen(a+1);
	vector<int> pos;
	pos.pb(0);
	for(int i=1;i<=n;i++)if(a[i]=='R')pos.pb(i);
	pos.pb(n+1);
	int ans=0;
	for(int i=0;i+1<pos.size();i++)ans=max(ans,pos[i+1]-pos[i]);//取最大距離 
	cout<<ans<<"\n";
}
int main(){
	int testnum;
	cin>>testnum;
	while(testnum--)mian();
	return 0;
}

D - Pair of Topics

洛谷題目頁面傳送門 & CodeForces題目頁面傳送門

給定$2$個長度為$n$的陣列$a,b$，求有多少個有序對$(i,j)$滿足$i<j$且$a_i+a_j>b_i+b_j$，

$n\in\left[2,2\times10^5\right],a_i,b_i\in\left[1,10^9\right]$，

$a_i+a_j>b_i+b_j\Leftrightarrow a_i-b_i>b_j-a_j$，這樣左邊僅關于$i$，右邊僅關于$j$，于是我們把$\forall i\in[1,n],a_i-b_i,b_i-a_i$這$2n$個數一起離散化咯，然后類似BIT求逆序對那樣建一個值域BIT，從后往前掃描，每掃到一個數$i$，給答案貢獻值域區間$(-\infty,a_i-b_i)$上的區間計數的結果，再將$b_i-a_i$插入BIT，時間復雜度$\mathrm O(n\log n)$，

答案會爆int，記得開long long，

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
#define int long long//答案爆int
#define pb push_back
int lowbit(int x){return x&-x;}
const int N=200000;
int n;
int a[N+1];
int b[N+1];
vector<int> nums;
void discrete(){//離散化 
	sort(nums.begin(),nums.end());
	nums.resize(unique(nums.begin(),nums.end())-nums.begin());
	for(int i=1;i<=n;i++)
		b[i]=lower_bound(nums.begin(),nums.end(),-a[i])-nums.begin()+1,
		a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1;
}
struct bitree{//BIT 
	int sum[2*N+1];
	void init(){memset(sum,0,sizeof(sum));}
	void add(int x){//添加x 
		while(x<=nums.size())sum[x]++,x+=lowbit(x);
	}
	int Sum(int x){//前綴計數 
		int res=0;
		while(x)res+=sum[x],x-=lowbit(x);
		return res;
	}
}bit;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%lld",a+i);
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		a[i]-=x;
		nums.pb(a[i]);//a[i]-b[i]
		nums.pb(-a[i]);//b[i]-a[i]
	}
	discrete();
	int ans=0;
	bit.init();
	for(int i=n;i;i--){
		ans+=bit.Sum(a[i]-1);//貢獻答案 
		bit.add(b[i]);//添加 
	}
	cout<<ans;
	return 0;
}

E - Sleeping Schedule

洛谷題目頁面傳送門 & CodeForces題目頁面傳送門

在Vova的世界里，一天$h\mathrm h$，Vova會睡$n$次覺，每次睡剛好$1$天，第$i$次會在第$i-1$次睡覺醒來后$(a_i-1)\mathrm h$或$a_i\mathrm h$后入睡，特殊地，第$0$次睡覺在第$0\mathrm h$醒來，設一次睡覺是在入睡當天的第$x\mathrm h$入睡，若$x\in[l,r]$，則稱此次睡覺是好的，問最多能有多少次好的睡覺，

$n\in[1,2000],h\in[3,2000],0\leq l\leq r<h,a_i\in[1,h)$，

可以說是基礎DP，

設$dp_{i,j}$表示考慮到第$i$次睡覺，第$i$次睡覺在當天第$j\mathrm h$醒來時最多的好的睡覺次數，邊界為$dp_{i,j}=\begin0&j=0\- \infty&j\neq0\end$（$j\neq0$時狀態不合法），目標為$\max\limits_^{dp_{n,i}}$，狀態轉移方程為$dp_{i,j}=\max!\left(dp_{i-1,(j-(a_i-1))\bmod h},dp_{i-1,(j-a_i)\bmod h}\right)+[j\in[l,r]]$（選擇在上一次睡覺醒來后$(a_i-1)\mathrm h$還是$a_i\mathrm h$后入睡），時間復雜度$\mathrm O(nh)$，

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=2000,H=2000;
int dp[N+1][H];
int n,h,l,r;
int a[N+1];
bool in(int x){return l<=x&&x<=r;}//[x in [l,r]]
int main(){
	cin>>n>>h>>l>>r;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<h;i++)dp[0][i]=-inf;//不合法狀態 
	for(int i=1;i<=n;i++)for(int j=0;j<h;j++)//DP 
		dp[i][j]=max(dp[i-1][(j-a[i]+1+h)%h],dp[i-1][(j-a[i]+h)%h])+in(j);//狀態轉移方程 
	cout<<*max_element(dp[n],dp[n]+h);//目標 
	return 0;
}

F - Maximum White Subtree

洛谷題目頁面傳送門 & CodeForces題目頁面傳送門

給定一棵樹$T=(V,E),|V|=n,|E|=n-1$，節點$i$有一個權值$a_i\in{0,1}$，分別表示是白點、黑點，$\forall i\in[1,n]$，找一個樹上連通子圖，設此圖內白、黑點各有$cnt1,cnt2$個，要求最大化$cnt1-cnt2$，輸出最大值，

$n\in\left[1,2\times10^5\right]$，

~~先吐槽一句：為什么我總共就打過$4$場div. 3，其中$3$場的F都是樹形DP???/yiw~~

非常顯然的樹形DP+二次掃描與換根，

首先，如果當前要求的這個點$x$是樹根的話，那一切都好辦了，設$dp_i$表示在以$x$為整棵樹的根的情況下，在以$i$為根的子樹內選連通子圖，必須包含$i$時$cnt1-cnt2$的最大值，目標是$dp_x$，狀態轉移方程是$dp_i=\sum\limits_{j\in son_i}\max(0,dp_j)+\begin-1&a_i=0\1&a_i=1\end$（累加以每個兒子為根的子樹能給$dp_i$帶來的貢獻的最大值，如果為負就不選），時間復雜度$\mathrm O(n)$，

然而題目要求對于所有點，不妨先令$1$為根求出所有點的DP值，再一遍二次掃描與換根求出所有點的答案，時間復雜度$\mathrm O(n)$，

總時間復雜度$\mathrm O(n)+\mathrm O(n)=\mathrm O(n)$，

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200000;
int n;
bool a[N+1];//點權
vector<int> nei[N+1];
int dp[N+1];
void dfs(int x=1,int fa=0){//求出以1為根時所有點的DP值 
	dp[x]=a[x]?1:-1;
	for(int i=0;i<nei[x].size();i++){
		int y=nei[x][i];
		if(y==fa)continue;
		dfs(y,x);
		dp[x]+=max(0,dp[y]);
	}
}
int ans[N+1];
void dfs0(int x=1,int fa=0){//二次掃描與換根 
	ans[x]=dp[x];//記錄答案 
	for(int i=0;i<nei[x].size();i++){
		int y=nei[x][i];
		if(y==fa)continue;
		dp[x]-=max(0,dp[y]);
		dp[y]+=max(0,dp[x]);
		dfs0(y,x);
		dp[y]-=max(0,dp[x]);
		dp[x]+=max(0,dp[y]);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		nei[x].pb(y);nei[y].pb(x);
	}
	dfs();
	dfs0();
	for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
	return 0;
}

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

標籤：C++

上一篇：結題報告--P5551洛谷--Chino的樹學

下一篇：回文數字的驗證