zcmimi's blog

arrow_back构造共5篇文章

avatar
zc
2020-10-17 11:25:38

查看原题

点击跳转

x构造一个矩阵满足a(i,j+1)=2a(i,j),a(i+1,j)=3a(i,j)

对于这个矩阵,我们不能选相邻的数,也就是说答案为不选相邻的数的方案数

这个矩阵长\log_2 n(不超过17),宽\log_3 n(不超过12),因此可以用状压dp解决

我们只需要对不是2,3倍数的数都构造一个矩阵就可以覆盖所有的数,容易发现每个矩阵互不相同,所以根据乘法原理把答案相乘即可

avatar
zc
2020-04-27 12:37:00
查看原题

点击跳转

很妙的构造题

首先,可以发现异或和明显不大于总和

第二,如果异或和与总和的奇偶不同,那么无解(二进制下最低位不同,没法用进位来填充)

剩下的就都可以构造了

u=v的时候,输出u就可以了,当u=0的时候记得特判

x=\frac{u+v}2

那么\left\{x,x,u\right\}就一定可以满足

如果x \And u=0的时候\left\{x,u\right\}等价于\left\{x+u\right\}

那么\left\{x,x+u\right\}可以满足

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

有趣的题

我们可以发现只有一组相邻两数只能求差的绝对值,其他数都可以取绝对值求和

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

  1. 如果个数中没有奇数,那么答案就是所有数字的gcd,然后构造答案就是输出\frac {gcd}2个回文串

  2. 如果个数中只有一个奇数,那么答案也是所有数字的gcd,然后构造答案就是输出gcd个回文串,个数为奇数的颜色放在回文串的中间

  3. 如果个数中有两个或以上的奇数,那么答案就是0,因为两个奇数就已经构造不出有优美cut的环来了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

我们先把所有边的方向掉转为从上到下

那么所有下端必须是n

有一种简单粗暴无脑但是好用的构造方案,就是构造一条链,并且n在长链的一端

问题变成了给你一个数组的前缀\max数组,反着构造原数组

1/1
Search
search