2024牛客暑期多校训练营2（部分题目题解）

2024牛客暑期多校训练营2（部分题目题解）

C.Red Walking on Grid

题意：给定只有红白的2*n个格子，只能走红色各自且只能上下左右走，问最多可以走多少红色格子。
题解：
左右走：

dp[0][i] = dp[0][i-1]+1；

上下走：

int k1 = dp[0][i];
int k2 = dp[1][i];
dp[0][i] = max(dp[0][i] ,k2 + 1);
dp[1][i] = max(dp[1][i] ,k1 + 1);

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int n;
    cin>>n;
    string s[2];
    cin>>s[0]>>s[1];
    s[0] = 'W'+s[0]+'W';
    s[1] = 'W'+s[1]+'W';
    vector< vector <int> > dp(2,vector<int>(n+1));
    for(int i=1;i<=n;i++)
    {
        if(s[0][i] == 'R')dp[0][i] = dp[0][i-1]+1;
        if(s[1][i] == 'R')dp[1][i] = dp[1][i-1]+1;
        if(s[1][i] == s[0][i] && s[0][i] == 'R')
        {
            int k1 = dp[0][i];
            int k2 = dp[1][i];
            dp[0][i] = max(dp[0][i] ,k2 + 1);
            dp[1][i] = max(dp[1][i] ,k1 + 1);
        }
    }
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        ans = max(ans,dp[0][i]-1);
        ans = max(ans,dp[1][i]-1);
    }
    cout<<ans<<endl;
    return 0;
}

E.GCD VS XOR

题意：给一个数x，找到一个数字num使得gcd(num,x)=num^x。
题解：x是偶数，输出
x是奇数，输出x-1。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		ll x;
		cin>>x;
		if(x>=2)
		{
			if(x%2==0)
			{
				int num=0;
				ll xx=x;
				ll number = 1;
				while(xx%2==0 && xx != 0)
				{
					num++;
					xx/=2;
					number*=2;
				}
				if(xx == 1)
				{
					cout<<-1<<endl;
				} 
				else cout<<x-number<<endl;
			}
			else{
				cout<<x-1<<endl;
			}
		}
		else 
		{
			cout<<-1<<endl;
		}
	}
	return 0;
}