当先锋百科网

首页 1 2 3 4 5 6 7

A. Yet Another Tetris Problem

题意: 给定一个数组,每次可以给其中一个元素+2 ,问可否经过若干次操作使所有元素的值一样

分析: 找到最大的元素,判断与其它元素的差值是否是二的整倍数即可

代码:

#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t,n,a[101];
    cin>>t;
    while(t--)
    {
    	cin>>n; int m=0,flag=0;
    	for(int i=0;i<n;i++) cin>>a[i],m=max(m,a[i]);
    	for(int i=0;i<n;i++)
    		if((m-a[i])%2) {flag=1;break;}
		if(flag) cout<<"NO\n";
		else cout<<"YES\n";
	}
}

B. Yet Another Palindrome Problem

题意: 给定一个字符串,问是否存在长度为3的回文子序列

分析: 暴力枚举回文子序列两端,若存在 s [ l ] = = s [ r ]   a n d   r − l > 1 s[l]==s[r]~and~r-l>1 s[l]==s[r] and rl>1 即表示有解

代码:

#include<bits/stdc++.h>
using namespace std;

const int N = 5e3+10;
int a[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t,n;
	cin>>t;
	while(t--)
	{
		cin>>n; int flag=0;
		for(int i=0;i<n;i++) cin>>a[i];
		for(int i=0;i<n&&!flag;i++)
		   for(int j=i+2;j<n;j++)
		       if(a[i]==a[j])
		       {
		          flag=1;break;
			   }
		if(flag) cout<<"YES\n";
		else cout<<"NO\n"; 
	}
}

C. Frog Jumps

题意: 起点为 0 ,终点为 n+1 ,在区间 [1,n] 上每个点都有字母 ‘L’ 或 ‘R’ ,代表往左或者往右,当你跳到 [1,n] 上的点时,下一次起跳的方向需要对应点上的字母,每次跳跃的范围在 [1,k] ,现在要你使得从起点能跳到终点的情况下 k 的值尽量小,求这个最小值

分析: 最小的值肯定是 [0,n+1] 上连续的 ‘L’ 的最大值,不然是无法跳过这段距离的

代码:

#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;cin>>t;
	while(t--)
	{
		cin>>s; int n=s.length(),last=-1,ans=0;
		for(int i=0;i<n;i++)
		    if(s[i]=='R')
		    {
		    	ans=max(ans,i-last);
		    	last=i;
			}
		ans=max(ans,n-last);
		cout<<ans<<'\n';
	}
}

D. Pair of Topics

题意: 给定长度为 n 的两个数组 a 和 b,求有多少对 ( i , j ) (i,j) (i,j) i < j i<j i<j满足 a i + a j > b i + b j a_i+a_j>b_i+b_j ai+aj>bi+bj

分析: 移下项就变成了 a i − b i > − ( a j − b j ) a_i-b_i>-(a_j-b_j) aibi>(ajbj) ,那么令 c i = a i − b i c_i=a_i-b_i ci=aibi ,即找到所有的 ( i , j )   i < j (i,j)~i<j (i,j) i<j 满足 c i > − c j c_i>-c_j ci>cj ,给数组 c 排个序,对于每个 c i c_i ci ,二分找到满足条件的位置就可以了

代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 2E5+10;
int s[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
    int n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>s[i];
	for(int i=0,x;i<n;i++) cin>>x,s[i]-=x;
	sort(s,s+n);
	long long ans=0;
	for(int i=0;i<n;i++)
	{
		int xb=upper_bound(s,s+n,-s[i])-s; //找到第一个大于等于 -s[i] 的位置
		xb=max(i+1,xb); //满足 i<j 的条件
		ans+=(long long)n-xb;
	}
	cout<<ans;
} 

E. Sleeping Schedule

题意: 给出长度为 n 的睡觉数组 a, a i a_i ai 表示第 i 次睡觉的时长,Vova 从 0 时开始睡觉(按照数组a顺序,醒了又继续睡),若他某次醒来的时刻在模 h 意义下处于区间 [l,r] 内,那么这一次的睡眠是 good 的,Vova 可以控制每次睡觉的时间减小 1 小时,问 n 次睡眠中至多有几次是 good 的

分析: 因为每次睡觉至多减小一小时,所以可以给数组 a 做前缀和 sum,这样若前 i 次睡眠一共减小 j 次,那第 i 次睡眠后醒来的时刻就是 s u m [ i ] − j sum[i]-j sum[i]j ,设 dp[i][j] 表示前 i 次睡眠,减少操作为 j 次的情况下 good 最多的次数,则转移方程不难想

//a[i]是前缀和
for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
        {
            // 1.前i组睡眠j+1次操作,使得第i次睡眠醒来处于good区间
        	if((a[i]-j-1)%h>=l&&(a[i]-j-1)%h<=r)
                dp[i][j+1]=max(dp[i][j+1],dp[i-1][j]+1);
            // 2.前i组睡眠j次操作,使得第i次睡眠醒来处于good区间
        	if((a[i]-j)%h>=l&&(a[i]-j)%h<=r)
        	    dp[i][j]=max(dp[i][j],dp[i-1][j]+1);
        	// 3.前i组睡眠j次操作,第i次睡眠醒来不处于good区间
        	dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i-1][j-1]));
        	// 4.前i组睡眠j+1次操作,第i次睡眠醒来不处于good区间
        	dp[i][j+1]=max(dp[i][j+1],dp[i-1][j]);
		}
//写法不唯一,符合逻辑就可以了

代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 2000+5;
int a[N],dp[N][N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n,h,l,r; cin>>n>>h>>l>>r;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=2;i<=n;i++) a[i]+=a[i-1];
    
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++)
        {
        	if((a[i]-j-1)%h>=l&&(a[i]-j-1)%h<=r)
                dp[i][j+1]=max(dp[i][j+1],dp[i-1][j]+1);
        	if((a[i]-j)%h>=l&&(a[i]-j)%h<=r)
        	    dp[i][j]=max(dp[i][j],dp[i-1][j]+1);
        	dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i-1][j-1]));
        	dp[i][j+1]=max(dp[i][j+1],dp[i-1][j]);
		}
    
    int ans=0;
    for(int i=0;i<=n;i++) ans=max(ans,dp[n][i]);
    cout<<ans; 
} 

F. Maximum White Subtree

题意: 给定一棵树,每棵树属性或白或黑,设一个节点 u 所在连通块的权值为 c n t w − c n t b cnt_w-cnt_b cntwcntb , 即连通块内白点减去黑点的数量,现在你可以干预这个连通块(即本来 u 的连通块就是整棵树,你可以截断使得最后的连通块只要包含节点 u 就可以了),求每个节点的最大权值

分析: 图是一棵树,由题意,对于树上的节点,对其权值产生影响的除了它本身,就是子孙节点和祖先节点,那么可以两次dfs,第一次dfs1求出 子孙节点的影响,第二次dfs2再在dfs1的基础上求出并累加祖先节点的影响;

设 dp[u] 表示节点 u 的最大权值

//子孙节点的影响
void dfs1(int u,int pre)
{
	if(a[u]) dp[u]++; //初始化权值,节点属性为白+1,黑-1
	else dp[u]--;
	for(auto v:e[u])
	{
		if(v==pre) continue;
		dfs1(v,u);
		if(dp[v]>0) dp[u]+=dp[v]; 
		//对于节点 u ,它只累加子节点中权值大于零的,这样才会使得 u 的权值尽量大
	}
}

//祖先节点影响
void dfs2(int u,int pre)
{
	for(auto v:e[u])
	{
		if(v==pre) continue;
		if(dp[v]>=0&&dp[u]>dp[v]) dp[v]=dp[u];  
		//如果子节点v的权值大于等于零,则证明dfs1中u的权值肯定已经包括了v,此时若u的权值大于v,则更新v
		else if(dp[v]<0&&dp[u]>0) dp[v]+=dp[u]; 
		//否则若v的权值小于零,则dfs1中u的权值不包括v,若u的权值大于零,则v累加u的权值(为了使v的权值尽量大)
		dfs2(v,u);
	}
}

代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 2E5+10;
int a[N],n,dp[N];
vector<int>e[N];

void dfs1(int u,int pre)
{
	if(a[u]) dp[u]++;
	else dp[u]--;
	for(auto v:e[u])
	{
		if(v==pre) continue;
		dfs1(v,u);
		if(dp[v]>0) dp[u]+=dp[v];
	}
}

void dfs2(int u,int pre)
{
	for(auto v:e[u])
	{
		if(v==pre) continue;
		if(dp[v]>=0&&dp[u]>dp[v]) dp[v]=dp[u];
		else if(dp[v]<0&&dp[u]>0) dp[v]+=dp[u]; 
		dfs2(v,u);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<n;i++)
	{
		int u,v; cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,0);
	int ans=0;
	for(int i=1;i<=n;i++) cout<<dp[i]<<' ';
}