2024牛客暑期多校训练营2题解自用
C
题目大意
在2*n的格子中，只能上下左右走到红格子上，求出能走的最长的路径。
答案
方法1：搜索
对于每一列上的一个起点及其之后的一列能走的位置，仅有4种情况
-
斜着走最赚
-
上下最多一个，那就往前走
-
没法往前走，只能走上下
-
都没法走
于是不断往前搜索。
注意，每一列的上下都需要作为起点尝试一次，可以记录走的最远的格子，然后搜索结束后直接跳过去。
代码：
#include<bits/stdc++.h>
using namespace std;
int b[2][1000005]={0};
int ans = 0;
int max_x = 0;//走的最远端
void solve(int x,int y,int t)
{
if(b[!x][y] == 0 && b[x][y+1] == 0)
{
max_x = y;
ans = max(ans,t);
}
else if( b[!x][y] & b[!x][y+1] )
{
solve(!x,y+1,t+2);
}
else if(b[x][y+1])
{
solve(x,y+1,t+1);
}
else
{
max_x = y;
ans = max(ans,t+1);
}
return;
}
int main()
{
int n = 0;
cin>>n;
string s1;
string s2;
cin>>s1>>s2;
for(int i = 0;i<n;i++)
{
if(s1[i] == 'R') b[0][i] = 1;
else b[0][i] = 0;
if(s2[i] == 'R') b[1][i] = 1;
else b[1][i] = 0;
}
for(int i = 0;i<n;i++)
{
if(b[0][i] == 1)
{
solve(0,i,0);
}
if(b[1][i] == 1)
{
solve(1,i,0);
}
if(b[0][i] == 1||b[1][i] == 1)
{
i = max_x;
}
}
cout<<ans;
return 0;
}
方法2：dp
代码：
#include<bits/stdc++.h>
using namespace std;
int dp[2];
string s[2];
int ans = -1;
int main()
{
int n = 0;
cin>>n>>s[0]>>s[1];
for(int i = 0;i<n;i++)
{
if(s[0][i] == 'R') dp[0]++;
else dp[0] = 0;
if(s[1][i] == 'R') dp[1]++;
else dp[1] = 0;
if(s[0][i] == 'R'&&s[1][i] == 'R')
{
int t0 = dp[0];
int t1 = dp[1];
dp[0] = max(dp[0],t1+1);
dp[1] = max(dp[1],t0+1);
}
ans =max(ans, max(dp[0],dp[1]));
}
cout<<max(0,ans-1);
return 0;
}
E
题目大意
给定x，求一个小于x的y使得gcd(x,y)=x⊕y。
可以从二进制的角度分析因子，每除以一个因子2，二进制的尾0就掉一个
例：对于11010100来说，最大可以除以4，那么，如果异或只异或一位，即与11010000异或时，刚好就是尾1处不一样,即gcd与异或值相等
于是，有y = x - lowbit(x) 使得 gcd(x,y)=x⊕y
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t = 0;
cin>>t;
long long x;
while(t-->0)
{
cin>>x;
x-=(x&-x);
if(x<=0) cout<<-1<<endl;
else cout<<x<<endl;
}
return 0;
}
