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

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

作图步骤如下:

  1. 以点 \(A\) 为圆心,\(AB\) 长为半径作圆 \(C_1\);
  2. 以点 \(B\) 为圆心,\(AB\) 长为半径作圆。圆 \(C_1,C_2\) 会产生两个交点,分别记为 \(D,E\)。
  3. 连接 \(DE\),与 \(AB\) 的交点即为所求线段 \(AB\) 的中点。

Task 2

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

《X Round 4 补题记》上有1条评论

发表回复

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

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