B - Vika and the Bridge
题意：从桥的一边走到另一边，每次只能踩在相同颜色的木板上，并且有一次操作，可以修改期中一个模板的颜色。 问那种走法，跨过模板的最大值最小。
思路：首先可以统计出选择每种颜色的，跳过木板的的个数，如果不能修改颜色，那么答案一定是每个颜色所对应的最大值的最小值，因为现在可以修改，所以对于每种颜色来说，就不一定是最大值了。最大值/2，与次大值比较，k值很小，二维度vector存，sort排序，比较最大值/2和次大值即可
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define max(ver1,ver2) (ver1>ver2?ver1:ver2)
#define min(ver1,ver2) (ver1>ver2?ver2:ver1)
#define lowbit(ver) ver&(-ver)
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define ull unsigned long long
#define debug(ver) cout<<#ver<<" = "<<ver<<"\n"
#define debug2(ver,ver2) cout<<#ver<<" = "<<ver<< " " << #ver2 << " = " << ver2 <<"\n"
#define eps 1e-9
#define pb push_back
using namespace std;
const int N = 1e6 + 10, M = N * 4, mod = 1e9 + 7;
int n, m, k;
int a[N];
int c[N];
void solve()
{
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
a[0]=0;
for(int i=0;i<=k;i++) c[i]=0;
vector<int> ve[k+1]; //开里面不用初始化
for(int i=1;i<=n;i++) //统计对应颜色所跨越木板个数
{
ve[a[i]].push_back(i-c[a[i]]-1);
c[a[i]]=i;
}
int ans=n+1;
for(int i=1;i<=k;i++)
{
ve[i].push_back(n-c[i]); //对应颜色最后一块木板，到终点的距离。
sort(ve[i].begin(),ve[i].end() );
int x=ve[i][ve[i].size()-1]; //最大值
int y=ve[i][ve[i].size()-2]; //次大值
x=max(y,x/2);
ans=min(ans,x);
}
cout<<ans<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T=1;
// scanf("%lld",&T);
cin>>T;
while(T--)
{
solve();
}
return 0;
}
C Vika and Price Tags
题意：判断是都可以生成全零数组。
思路：先打单独判断一位数，打表找规律，发现 多次操作后一定会出现 0 x x 0 x x 0 ,所以只需要找到每个数第一次出现0的位置即可。的到数组c，如果c中数差值都是三的倍数，则能变成全零数组。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define max(ver1,ver2) (ver1>ver2?ver1:ver2)
#define min(ver1,ver2) (ver1>ver2?ver2:ver1)
#define lowbit(ver) ver&(-ver)
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define ull unsigned long long
#define debug(ver) cout<<#ver<<" = "<<ver<<"\n"
#define debug2(ver,ver2) cout<<#ver<<" = "<<ver<< " " << #ver2 << " = " << ver2 <<"\n"
#define eps 1e-9
#define pb push_back
using namespace std;
const int N = 1e6 + 10, M = N * 4, mod = 1e9 + 7;
int n, m, k;
int a[N];
int c[N];
int b[N];
int ck(int x,int y)//返回第一次出现零的位数
{
if(x==y) return 1; //相等下一位一定是0
if(x<y)
{
return ck(y,abs(x-y))+1; //下次 y 一定大于 x
}
else
{
if(x/y<=2) //
{
return ck(y,abs(x-y))+1;
}
else //这是一个规律，每次没经过三次，相当于 x值减去 两个 y
{
int w=x/y;
w=w/2;
return ck(x-w*(2*y),y)+3*w;
}
}
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
int tot=0;
for(int i=1;i<=n;i++)
{
if(a[i]==0&&b[i]==0) continue; //0 0 一直是零不考虑
else if(a[i]==0) c[tot++]=1; //特判
else if(b[i]==0) c[tot++]=2; //
else
c[tot++]=ck(a[i],b[i])+2; //加二表示前两位
}
int flag=1;
for(int i=1;i<tot;i++)
{
if(abs(c[i]-c[i-1])%3!=0) flag=0;
}
if(flag) cout<<"YES\n";
else cout<<"NO\n";
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T=1;
// scanf("%lld",&T);
cin>>T;
while(T--)
{
solve();
}
return 0;
}