ddcc2020-qual题解

Source

DISCO Presents Discovery Channel Code Contest 2020 Qual

ddcc2020-qual

E Majority of Balls

题意:客观存在一个长度为2n的由1、-1组成的序列,允许询问不超过210次一个长度为n子序列和的正负性,以猜出序列具体元素,$n=奇数 \le 99$

请先思考后再展开

设$f(i)=(\sum_{j=i}^{i+n-1} a_j)>0$,一定$\exists i,f(i)\ne f(i+1)$,发现能得知$a_i,a_{i+n},另外\sum_{j=i+1}^{i+n-1} a_i=0$,于是可以通过2n-2次询问得出整个序列,问题在于怎么找到这个i。首先$f(1) \ne f(n+1)$,二分答案,l=1,r=n,若$f(mid)=f(l),l=mid;否则r=mid-1$

总询问次数=$1+\lceil log_2(n) \rceil +2n-2$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
char str[N];
bool ask(int l1,int r1,int pos=0,int l2=1,int r2=0){
printf("? ");fo(i,l1,r1)write1(i);fo(i,l2,r2)write1(i);if(pos)write1(pos);
puts("");fflush(stdout);scanf("%s",str);if(str[0]=='-') assert(0);return str[0]=='R';
}
char a[N];
void main()
{
int n=qread();
int fl=1,fr=n,left=ask(1,n);
while(fl+1<fr)
{
int mid=(fl+fr)/2;
if(ask(mid,mid+n-1)==left) fl=mid; else fr=mid-1;
}
int pos=fl;if(fl<fr and ask(fl,fl+n-1)==ask(fl+1,fl+n)) pos++;a[pos]=left,a[pos+n]=left^1;
fo(i,1,pos-1) a[i]=ask(pos+1,pos+n-1,i);fo(i,pos+n+1,n+n) a[i]=ask(pos+1,pos+n-1,i);
fo(i,pos+1,pos+n-1) a[i]=ask(1,pos-1,i,pos+n+1,n+n);
printf("! ");fo(i,1,n+n) putchar(a[i]?'R':'B');puts("");fflush(stdout);
}

F DISCOSMOS

题意:有一个$H*W$的表格,在时刻0的时候往上面每个格放一个机器人,要求在任意T的倍数时刻,每个格上都有机器人

有三类机器人:A类不动,R类向右,D类向下,且坐标为$(x \bmod n,y \bmod m)$

想这题的时候不知不觉就理解成每个格子上有方向了……感觉这是我经常出的问题

请先思考后再展开

首先每个点连向向下T和向右T,则$列环长lcm(H,T),即列环数=H/环长=gcd(H,T)$,行同理,于是等价于存在$gcd(H,T)*gcd(W,T)个独立的表格,每个表格的T=1且大小为h=H/gcd(H,T),w=W/gcd(W,T)$

于是我们只需要考虑T=1且大小为$h*w$,然后我们考虑机器人的组成分类讨论,只有A类显然可行,恰有A类和(R、D中一种)则是$2^h+2^w-1$

如果恰有R和D类,「请看题解第一张图」,意思就是因为每个格子的左侧和上侧的机器人必须是相同的才不会立刻撞车,于是把这两个格合并,最后会形成若干个组,每个组内放的种类必须相同,显然$环长=lcm(h,w),故组数G=h*w/环长=gcd(h,w)$,方案数就是$2^G-全是R-全是D$,目前的答案是$2^h+2^w+2^G-3$,事实上这就是答案,下面我们将证明不存在三种同时有的情况

「请看题解第二张图」,假如存在一个组只有A类,显然覆盖了所有列和行于是无法放其他两类;因此一定存在一个组是都有的,以另一种是R为例,于是一定$\exists (i,j)=R,(i-1,j+1)=A$,于是我们发现$(i,j+1)必须=R$,进而发现$(i-1,j+2)必须=A$,于是所有列都有A,不可能放D了

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/cc527447.html
转载请注明出处,谢谢!