过去就像攥在手中的一把干沙,自以为攥得很紧,其实早就从指缝中流光了。记忆是一条早已干涸的河流,只在毫无生气的河床中剩下零落的砾石。
——刘慈欣 《三体》
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
由图可看出是过直线外一点,作已知直线的垂线。
喜欢前言