CF 1088(A , B , C , D)——思路

时间:2021-12-19 00:23:02

http://codeforces.com/contest/1088

A:Ehab and another construction problem

  输出 2 和 n(偶数的话)或者 2 和 n-1(奇数的话)就行了。n==1的时候非法。

CF 1088(A , B , C , D)——思路CF 1088(A , B , C , D)——思路
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int x;
int main()
{
  scanf("%d",&x);
  if(x==1)puts("-1");
  else if(x&1)printf("%d %d\n",x-1,2);
  else printf("%d %d\n",x,2);
  return 0;
}
View Code

B:Ehab and subtraction

  排序之后走一遍就行了。

CF 1088(A , B , C , D)——思路CF 1088(A , B , C , D)——思路
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n,k,a[N];
int main()
{
  scanf("%d%d",&n,&k);
  for(int i=1;i<=n;i++)scanf("%d",&a[i]);
  sort(a+1,a+n+1); int p=1,tag=0;
  for(int i=1;i<=k;i++)
    {
      if(p>n){puts("0");continue;}
      printf("%d\n",a[p]-tag);tag=a[p];
      for(p++;a[p]==tag&&p<=n;p++);
    }
  return 0;
}
View Code

C:Ehab and a 2-operation task

  如果升序的话,比如要弄成 0 , 1 , 2 , 3 , ... n-1 , k(k>=n),假设正在做第 i 个位置,那么模数应该大于 i-1 ,如果之前都弄好了的话,这次取模就不会对之前造成影响了!

  所以一开始给每个位置加上足够大的数(让它的值 >= (i-1)*2+1),然后依次取模就行了。

CF 1088(A , B , C , D)——思路CF 1088(A , B , C , D)——思路
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2005;
int n,a[N],tag;
int main()
{
  scanf("%d",&n);
  for(int i=1;i<n;i++)
    scanf("%d",&a[i]),tag=max(tag,(i-1<<1)+1-a[i]);
  scanf("%d",&a[n]);tag=max(tag,n-1-a[n]);
  if(tag)printf("%d\n1 %d %d\n",n,n,tag);
  else printf("%d\n",n-1);
  for(int i=1;i<n;i++)
    {
      printf("2 %d %d\n",i,a[i]+tag-(i-1));
    }
  return 0;
}
View Code

D:Ehab and another another xor problem

  因为最高位对大小影响比较大,所以从高到低位做;这样能已经知道更高位的值,从而通过异或把更高位的影响消掉。

  然后就不太会了。想着在每一位上判断 0 , 0 和 1 , 1 ,但无法通过2次来确定相等的话是同为0还是同为1。

  看了题解。原来是一开始先判一个 0 , 0 来了解哪个比较大;然后可以每一位判断 0 , 1 和 1 , 0 ,这样可以知道相等的话是同为0还是同为1,但无法知道不相等的话哪个是0哪个是1;这时只要利用一开始判断出来的那个“哪个比较大”就能知道这一位上哪个是0哪个是1了!而且在判这一位的 0 , 1 和 1 , 0 时已经可以知道去掉这一位之后哪个比较大,就可以做下去了!

CF 1088(A , B , C , D)——思路CF 1088(A , B , C , D)——思路
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=35;
int bin[N],a,b;
int main()
{
  bin[0]=1;for(int i=1;i<30;i++)bin[i]=bin[i-1]<<1;
  printf("? 0 0\n");fflush(stdout);
  int d; scanf("%d",&d);
  for(int t=29,x,y;t>=0;t--)
    {
      printf("? %d %d\n",a|bin[t],b);fflush(stdout);
      scanf("%d",&x);
      printf("? %d %d\n",a,b|bin[t]);fflush(stdout);
      scanf("%d",&y);
      if(x==y)
    {
      if(d==1)a|=bin[t]; else b|=bin[t];
      d=x;
    }
      else if(y==1)a|=bin[t],b|=bin[t];
    }
  printf("! %d %d\n",a,b);
  return 0;
}
View Code