https://codeforces.com/contest/1787
问 [1,2,3,…,n] 能否拆成k个非空序列(不一定连续), 且每个序列内的数字xor为x
如果可以给具体方案
n 2e5
x [1,1e9]
1s
256mb
想了很久线性基, 没啥办法, 感觉都是O(n^2)以上
然后 显然 如果 k为奇数那么 x = xor[1..n], 如果k为偶数, 0 = xor[1…n]
然后n%4==3 的时候 xor[1..n] = 0
然后n%4==0 的时候 xor[1..n] = n
然后n%4==1 的时候 xor[1..n] = 1
然后n%4==2 的时候 xor[1..n] = n+1
其中 n%4==1 很好做, 相邻取偶数和偶数+1 就能构成
n%4==0和n%4==2没有什么办法, 但是这个如果暴力出来,是可以打表的
但是n%4==3 就连打表都不行
https://atcoder.jp/contests/abc286/tasks
二维平面, 有N点的凸多边形C(逆时针给点),
以及两个点S和T(保证在多边形外部)
求从S到T不经过多边形内部的最短距离
n 1e5
所有坐标 [-1e9,1e9]
2s
1024mb
看错题了
如果是凸包, 那就还好, 按S排个角度, 每次找下一个点和S哪个夹角更小, 就完了
问题是这里可能是奇怪的形状
1 | xxxx |
一个事实是, 如果从当前点能不穿过其它点到S,那么就直接走, 但是又该如何判断 中间不被阻挡, 需要O(n)条边的判断?
那么其实 任意两点都满足这个性质, 如果直接能到就直接走
最短路? 还是 如何在非凸包 判断不被阻断, 不会了
https://codeforces.com/contest/1613
根1的n点树
给点上排列色ci = 1~n (每个颜色出现且仅出现一次)
p[i]=i的父节点
如果所有点满足c[i] != c[p[i]] -1, 则认为美丽
问有多少种美丽的染色方案mod 998244353
n 250000
4.5s
512mb
也就是 每个点的颜色不能正好比父节点小1
一般来说, 树的兄弟之间没有关系, 但是这里 如果一个非法的子树, 和兄弟的子树, 值进行穿插, 这有可能变得合法
例如
1 | root |
1 | root |
一个方向就是去考虑容斥, 把边作为属性, 拥有属性表示边连的两个点相邻
有指定属性连接在一起的点, 在子树之间 做穿插时就不能拆开了,
而注意到当子树穿插时, 只与有几个可穿插的有关
考虑f[u][c] = 节点u的子树中, 可连可不连的自由节点个数为c时的方案数
先不考虑根, v1 和 v2 之间的穿插
[c1 + c2] = sum f[u][c1] * f[u][c2] * binom(c1+c2,c1)
[c1 + c2]/(c1+c2)! = sum f[u][c1]/c1! * f[u][c2]/c2!
看起来就是ntt
最后考虑根u
f[u][c1+c2+...] = [c1+c2+...]*count(child), 直接放(某个子树的最大+1) 且指定边不可移动
f[u][c1+c2+...+1] = [c1+c2+...]*(c1+c2+...+1), 放任意地方(包括 最大+1), 但不指定边
f[u][c] = (count child)[c] + [c-1]*c
变形 f[u][c]/c! = (count child)[c]/c! + [c-1]/(c-1)!
那么就是 g[u] = (c+x) g(v0) g(v1) g(v2) ...
g(leaf) = x
ans = sum f[1][c]*c!
但是看起来暴力算感觉会tle
仔细一看表达式 原来是 f[1] = (c1+x)(c2+x) * x^叶子
https://codeforces.com/contest/1620
给你1~n排列数组a
问能否 给每个数乘上 1或-1,
然后对所有逆序点连边, 让所有点能二分图
n 1e6
2s
256mb
考虑一个点是负数, 那么它前面所有点和它相连, 所以前面点和它 都在二分图对面, 所以它们之间不能有边, 所以它们需要单调递增,
如果考虑n是正数, 同理 它右侧的点 需要单调递增
如果n是负数,那么它左侧的点要单调递增
问题是这样分割, 会产生n个分支?
dfs 来控制 ?
https://codeforces.com/contest/1622
n个学生,
m个题目
你知道每个学生 哪些题目对了哪些题目错了, 正确得分错误不得分
r[i] = 第i个学生的真实得分 = 正确题目得分之和
x[i] = 第i个学生的标准得分, 给定
问如何给题目 的分设置为 1~m 的排列
能让 sum |xi-ri| 最大, 求最大值
n 10
m 1e4
2s
256mb
这n很小, 就很想bitmask
但是 bitmask怎么用
想的是 分别计算 f(bitmask) = bitmask中的学生真实得分 >= 标准得分, 其它的学生 真实 < 标准
这样去掉了绝对值
然后如何算呢
这样得到 10个 不等式 和一个要求的最大值
正确错误的1/0串[i] * 题目分数设置 = r[i] >= x[i]
…
正确错误的1/0串[j] * 题目分数设置 = r[j] < x[j]
…
要求 max( 正确错误1/0加权和 * 题目分数设置)
有点像线性规划?
但一个是排列, 一个是又有大于等于, 又有小于等于, 并不知道怎么搞