[CF1064X]Codeforces Round #516 (Div. 2, by Moscow Team Olympiad)

感觉这次题目算法性似乎很强,很多题目都是结论题,思维难度也不算太高,这里给出题人点个赞。(滑稽)

题目链接

https://codeforces.com/contest/1064

A. Make a triangle!

大意

给出长度分别为 \(a , b , c\) 的三根木棒,求出至少将木棒延长多长可以使这三根木棒拼成一个三角形。

题解

这里设 \(a \leq b \leq c\),毫无悬念,当 \(a+b>c\) 时,答案为 \(0\)。

否则,我们可以延长最短的那根木棒,使得 \(a+b>c\) 成立。这时的答案为 \(c-(a+b+1)\)。

#include <cstdio>
#include <algorithm>
using namespace std;
int a[3];
int main()
{
 scanf("%d%d%d",&a[0],&a[1],&a[2]);
 sort(a,a+3);
 if(a[0]+a[1]>a[2])printf("0\n");
 else printf("%d\n",a[2]-(a[0]+a[1])+1);
 return 0;
}

B. Equations of Mathematical Magic

大意

给出 \(a\),判断方程 \(a-(a \oplus x)-x=0\) 的解的个数。

题解

移项后可得 \(a \oplus x=a-x\),随便找几个规律就会知道, \(x\) 是方程的解当且仅当 \(x\) 的二进制表示中的 \(1\) 是 \(a\) 中 \(1\) 的子集。

举个栗子,当 \(a=13 ((1101)_2)\) 时,\(x=4 ((0100)_2)\) 就是方程的一个根。

根据子集的规律可知,假如 \(a\) 中有 \(x\) 位的值为 \(1\),答案就是 \(2^x\)。

#include <stdio.h>
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  int a;
  scanf("%d",&a);
  if(a==0)puts("1");
  else
  {
   int cnt=1;
   while(a!=0)
   {
    if(a%2)cnt*=2;
    a>>=1;
   }
   printf("%d\n",cnt);
  }
 }
 return 0;
}

C. Oh Those Palindromes

大意

给出一个字符串,通过重新排序,使得新字符串的回文子串数目最多。

题解

“abccba”和”aabbcc”哪个回文子串多?答案事实上是一样多的。(都是 \(9\) 个)

所以似乎可以猜一个结论:直接把字符串按字母顺序排列不就好了?(这个结论事实上是正确的)

#include <cstdio>
#include <algorithm>
using namespace std;
char s[100005];
int main()
{
 int n;
 scanf("%d",&n);
 scanf("%s",s);
 sort(s,s+n);
 printf("%s",s);
 return 0;
}

E. Dwarves, Hats and Extrasensory Abilities

大意

这是一道交互题。

你的程序将读入一个数字 \(n\),每次你输出一个位于第一象限内的点 \((x,y)\),交互器将会给出该点的颜色(”black”或”white”)。当你输出 \(n\) 个点后,你应该输出两个点 \((x1,y1),(x2,y2)\),这两个点连成的直线将把整个平面分成两侧,位于直线同一侧的点应该颜色相同,并且你输出的任何一个点都不应刚好在这条直线上。

题解

刚开始误解了题意,于是瞎搞了一个程序:

#include <stdio.h>
int a[35];
char s[35];
int main()
{
 int n;
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
 {
  printf("%d %d\n",0,(i-1)*2);
  fflush(stdout);
  scanf("%s",s);
  if(s[0]=='b')a[i]=1;
  else a[i]=0;
 }
 int y=2*n;
 for(int i=2;i<=n;i++)
  if(a[i]!=a[i-1])
  {
   y=(i-1)*2-1;
   break;
  }
 printf("%d %d %d %d",0,y,1,y);
 return 0;
}

题目中说到交互器具有“自适应性”,然而被误解成对于我们给出的输出,交互器一定会保证存在一种合法的分割方案,结果死的很惨。

那么我们就不能把所有点都放在一条直线上了?其实还是可以的。

事实上,我们可以采用二分的方法来放点。

首先在原点上放一个点,然后在数轴的中点放一个点(对于本题,这个点可以放在 \((5 * 10 ^ 8,0)\) 这个位置上),然后每次都在两端点颜色不相同的区间的中点上继续放点,直到点放完为止。最后的答案就位于相邻的黑点和白点之间。

听起来有些绕?放个图来加深一下理解:

这样放点就确保了黑点白点被隔开的情况不会发生了。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据