X Round 4 补题记

目录显示

过去就像攥在手中的一把干沙，自以为攥得很紧，其实早就从指缝中流光了。记忆是一条早已干涸的河流，只在毫无生气的河床中剩下零落的砾石。
——刘慈欣 《三体》

A. 模拟赛

可以用 std::set 维护每天需要准备的模拟赛集合。

代码简单就不贴了。

B. 歌唱比赛

显然 Z 只能出现在字符串最后几位（因为是自低位到高位比较，因此一旦平局局面打破就不可能再出现平局）。

利用这一性质可以先判断出无解的情况。

合法解的构造方法就简单得多了：对于 X 的位，令小 X 在这一位上的数字比小 Y 大即可，反之同理。

C. 题

推式子题。

首先根据平方差公式进行因式分解，

$$(y+x)(y-x)=ax+b$$

这时不妨令 $t=y-x$，

$$t \times (t+2x)=ax+b$$

把所有含 $x$ 的项合并到一块，

$$2tx-ax=b-t^2$$

解得，

$$x=\frac{b-t^2}{2t-a}$$

枚举 $t$ 的值即可。

特别地，当 $a^2=4b$ 时，此时 $x^2+ax+b$ 为一完全平方式，该方程有无数组解。

时间复杂度？令 $u=b-t^2$，$v=2t-a$。容易发现 $u$ 单调递减，$v$ 单调递增。当 $u<0$ 且 $v>0$ 时我们可以终止枚举。

故 $t \leq \min \{\sqrt{b},\frac{a}{2}\}$。

#include <cmath>
#include <iostream>
using namespace std;
int main()
{
 long long a,b,ans=0;
 cin>>a>>b;
 if(a*a==4*b)
 {
  cout<<"inf"<<endl;
  return 0;
 }
 long long tmp=sqrt(b);
 if(tmp*tmp==b)ans++;
 for(long long i=1;;i++)
 {
  long long x=b-i*i,y=2*i-a;
  if(((x>0&&y>0)||(x<0&&y<0))&&x%y==0)ans++;
  if(x<0&&y>0)break;
 }
 cout<<ans<<endl;
 return 0;
}

D. 复读

先不加证明地给出一个事实：每个周期的相对位移是一定的。

因此只需确定第一个周期结束时的点，我们就可以求出所有周期结束时的点。这个第一步可以枚举实现。

一个周期走过的所有染色点会形成一棵树。我们需要构造一种序列，使得每个周期的指令完整覆盖所有树，也就是这若干棵树（形态上的）并。

设合并后的树的大小为 $size$，相对位移为 $x$，则指令的长度为：$2 \times (size-1)-x$（除了起点到终点的这些边只会走一次以外，其他所有边都会走两次）。

枚举的时间复杂度为 $O(n)$，构造合并树的时间复杂度也为 $O(n)$，故总时间复杂度为 $O(n^2)$。

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min;
int ans=1e8;
struct tree
{
 struct node
 {
  int son[2];
 }tr[100005];
 int cnt,rt;
 void clear()
 {
  memset(tr,0,sizeof(tr));
  cnt=1,rt=1;
 }
}p,q;
char s[2005];
int path[2005],dfn;
void build(int& u)
{
 if(!u)u=++p.cnt;
 int x=s[dfn++];
 if(x&1)build(p.tr[u].son[0]);
 if(x&2)build(p.tr[u].son[1]);
}
void merge(int& x,int y,int z)
{
 if(!x)x=++q.cnt;
 if(y==z)return;
 if(p.tr[y].son[0])merge(q.tr[x].son[0],p.tr[y].son[0],z);
 if(p.tr[y].son[1])merge(q.tr[x].son[1],p.tr[y].son[1],z);
}
void dfs(int u,int d)
{
 if(!u)return;
 if(u!=1)
 {
  q.clear();
  int x=1;
  while(x)
  {
   int r=x;
   for(int i=0;i<d;i++)
    x=p.tr[x].son[path[i]];
   merge(q.rt,r,x);
  }
  ans=min(ans,(q.cnt-1)*2-d);
 }
 path[d]=0;
 dfs(p.tr[u].son[0],d+1);
 path[d]=1;
 dfs(p.tr[u].son[1],d+1);
}
int main()
{
 scanf("%s",s);
 int len=strlen(s);
 for(int i=0;i<len;i++)
  s[i]-='0';
 p.clear(),q.clear();
 build(p.rt);
 dfs(p.rt,0);
 printf("%d\n",ans);
 return 0;
}

G. （附加题）尺规作图

在线上赛中见到这样的提答题算是一大创新。

Task 1

由图可看出是求已知线段的中点。

作图步骤如下：

以点 $A$ 为圆心，$AB$ 长为半径作圆 $C_1$；
以点 $B$ 为圆心，$AB$ 长为半径作圆。圆 $C_1,C_2$ 会产生两个交点，分别记为 $D,E$。
连接 $DE$，与 $AB$ 的交点即为所求线段 $AB$ 的中点。

Task 2

由图可看出是过直线外一点，作已知直线的垂线。