CGR 1 补题记

好久没打 CF 了，最近试着 vp 了几场去年的 Global Round，把题解写在这里。

题目链接

https://codeforces.com/contest/1119

A. Parity

从低次向高次暴力计算。

时间复杂度 \(O(k)\)。

#include <iostream>
using namespace std;
int a[100005];
int main()
{
 int b,k;
 cin>>b>>k;
 for(int i=1;i<=k;i++)
  cin>>a[i];
 int ans=a[k]%2,num=1;
 for(int i=k-1;i;i--)
 {
  num=num*b%2;
  ans=(ans+num*a[i])%2;
 }
 if(ans==1)cout<<"odd"<<endl;
 else cout<<"even"<<endl;
 return 0;
}

B. Tape

和最小生成树的思想很像。

刚开始我们只用一条胶带，覆盖了所有点。

现在我们可以选择撤掉两点间的胶带，每执行一次操作，用的胶带数增加一条。

贪心从大到小撤胶带即可。

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005],d[100005];
bool cmp(int x,int y)
{
 return x>y;
}
int main()
{
 ios::sync_with_stdio(false);
 int n,m,k,ans;
 cin>>n>>m>>k;
 for(int i=1;i<=n;i++)
  cin>>a[i];
 ans=a[n]-a[1]+1;
 for(int i=2;i<=n;i++)
  d[i-1]=a[i]-a[i-1]-1;
 sort(d+1,d+n,cmp);
 for(int i=1;i<k;i++)
  ans-=d[i];
 cout<<ans<<endl;
 return 0;
}

C. Meaningless Operations

设 \(k\) 为满足 \(a \leq 2^k-1\) 的最小整数。我们分两种情况讨论。

• \(a \lt 2^k-1\)

构造 \(b=2^k-a\)，此时 \(a \oplus b=2^k-1\)，\(a \& b=0\)，从而取得最大答案 \(2^k-1\)。

• \(a=2^k-1\)

这时候没法做到 \(a\&b=0\) 了。

注意到这时候一定满足 \(a\oplus b+b=2^k-1\)，从而问题变成了求 \(\gcd(a-b,b)\) 的最大值。

事实上这个问题等价于 \(\gcd(a,b)\)。

故 \(b\) 就等于 \(a\) 的最大真因子。

#include <cmath>
#include <iostream>
using namespace std;
int f(int x)
{
 int ans=0;
 while(x)
 {
  x>>=1;
  ans++;
 }
 return ans;
}
int main()
{
 int t;
 cin>>t;
 while(t--)
 {
  int x;
  cin>>x;
  if(x&(x+1))cout<<(1<<f(x))-1<<endl;
  else
  {
   bool flag=true;
   for(int i=2;i*i<=x;i++)
    if(x%i==0)
    {
     cout<<x/i<<endl;
     flag=false;
     break;
    }
   if(flag)cout<<1<<endl;
  }
 }
 return 0;
}

E. Magic Stones

神仙结论题。

首先如果 \(c_1 \neq t_1\) 或者 \(c_n \neq t_n\) 那显然不行。

排除了这种情况后，我们来看看一次操作会造成怎样的变化。

设 \(a_i=c_{i+1}-c_i\)。

原来的 \(a_i\) 是这样的：\(a_i=c_{i+1}-c_i\)，\(a_{i-1}=c_i-c_{i-1}\)。

现在我们将 \(c_i\) 变成 \(c_{i+1}+c_{i-1}-c_i\)，这时候的 \(a_i\) 变成了：\(a_i=(c_{i+1}+c_{i-1}-c_i)-c_{i-1}=c_{i+1}-c_i\)，\(a_{i+1}=c_{i+1}-(c_{i+1}+c_{i-1}-c_i)=c_i-c_{i-1}\)。

我们发现两个 \(a_i\) 互换了。

于是问题就变成了：给两个差分数组，每次操作可以将其中一个数组的相邻两个元素互换，问能不能让两个数组相等。

这个就很简单了。

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005],b[100005],c[100005],d[100005];
int main()
{
 int n;
 cin>>n;
 for(int i=1;i<=n;i++)
  cin>>a[i];
 for(int i=1;i<=n;i++)
  cin>>b[i];
 if(a[1]!=b[1]||a[n]!=b[n])
 {
  cout<<"No"<<endl;
  return 0;
 }
 for(int i=1;i<n;i++)
 {
  c[i]=a[i+1]-a[i];
  d[i]=b[i+1]-b[i];
 }
 sort(c+1,c+n);
 sort(d+1,d+n);
 for(int i=1;i<n;i++)
  if(c[i]!=d[i])
  {
   cout<<"No"<<endl;
   return 0;
  }
 cout<<"Yes"<<endl;
 return 0;
}