A Tasks
实况
一开始非常居然想DP(反动思想),然后队友说拍个序就好了.
题解
从小到大排序,贪心选小的,直到不能选为止.
C Angel's Journey
实况
一开始输出6位小数,居然wa了,非要输出4位才行.
题解
如果终点在直线x=rx-r的左边,那就从底部一直走到(rx-r,ry).然后走直线直接去终点.
如果终点在直线x=rx-r的右边,那就从底部一直走到(rx+r,ry).然后走直线直接去终点.
如果终点在以上两个直线的中间,那就找到终点和圆的切线,从底部走到切点,然后走直线去终点.
距离是
D Miku and Generals
实况
我把给的点简化成了若干个pair,队友写了一个dp.
因为存pair的vector没有清空,re一发.
题解
先把数字/100,方便使用.
把互相关联的数字连接起来,然后涂色,每个联通块可以得到两个数字,
分别代表这个联通块的第一个点给A时,A获得的值和B获得的值.
如果有cnt个联通块,我们就有cnt对这样的数字(自由的数字就是{c[i], 0}).
然后dp
dp[i][j]表示只考虑前i对数字,是否可以形成差是j的分配方案
一开始dp[1...cnt][-1e6..1e6]都赋值成0;
dp[0][0]赋值成1,表示不考虑任何数字时,可以使差是0.
然后对于每一对数字for i = 0 to cnt
对于每一种差for j = -1e6 to 1e6
如果考虑前i对数字时,可以使差是j,即f[i][j] == 1
那么如果把这一对数字的前一个分配给A,差就会变成j+i.first-i.second,所以F[i+1][j+i.first-i.second]=1,
那么如果把这一对数字的前一个分配给B,差就会变成j-i.first+i.second,所以F[i+1][j-i.first+i.second]=1,
找到最小的差,较大的一个的数值是(所有数字的和-差)/2+差
E Tree
实况
蛐蛐树剖,我起了,一枪秒了
题解
树链剖分,用一颗线段树来存链上的数字.
线段树的每个节点是一个32的数组,数组的值val[rt][i]代表:
在这个节点代表的区间里,有多少个数字x符合x&(1<<i) != 0,
-
第一种操作,如果
t&(1<<i) != 0,那么被修改的区间的val[rt][i]修改为区间的大小,表示区间里的每一个数字这一位都是1;否则无视 -
第二种操作,如果
t&(1<<i) == 0,那么被修改的区间的val[rt][i]修改为0,表示区间里的每一个数字这一位都是0;否则无视
第三种操作,我们求一个数组tmp[1..32],其中tmp[i]为他给的区间的所有节点的val[rt][i]的和.
然后根据nim博弈,遍历每一位for i = 0 to 30,
int p = (t&(1<<i))?1:0
如果某一位tmp[i] + p不是偶数,那么输出YES.
否则输出NO.
J And And And
实况
只会求一条直链的,
然后就开始瞎想:启发式合并?树剖?点剖???
和AC的距离
完全忘了树上dp....
题解
以1为根
对于一条路径(u,v),如果他的异或和是0, 那么他的贡献应该是u那一端的节点数量*v那一端的节点数量.
先第一个dfs,算出每一个点的:
siz[u],代表u的子树大小;
sum[u],代表每一个点到根节点的路径和异或和.
如下
void dfs1(ll u)
{
siz[u] = 1;
for(auto i : g[u])
{
ll v = i.first;
ll w = i.second;
sum[v] = sum[u] ^ w;
dfs1(v);
siz[u] += siz[v];
}
}
第二个dfs,统计答案
可以知道如果两个节点u和v满足sum[u] == sum[v],那么他们之间的路径异或和是0;
那么他的贡献应该是u那一端的节点数量*v那一端的节点数量.
用一个map[x,y],y表示当前已经经过的节点里面,每一个符合sum[v]==x的节点v的另一端的节点数量的和.
所以每当遍历到一个结点map[sum[u]]就表示所有v那一端的节点数量的和.ans += map[sum[u]]*siz[u]
如下
void dfs2(int u)
{
ans = (ans + siz[u] * m[sum[u]] % mod) % mod;
for(auto i : g[u])
{
ll v = i.first;
ll w = i.second;
m[sum[u]] = (m[sum[u]] + n - siz[v] + mod) % mod;
dfs2(v);
m[sum[u]] = (m[sum[u]] - n + siz[v] + mod) % mod;
}
m[sum[u]] = (m[sum[u]] + siz[u]) % mod;
}
L Swap
实况
通过一种神秘力量(打表),发现了规律
题解
轮流执行操作一和操作二就可以产生所有结果,
然后看数量找规律
if n==1 : 1
else if n==2 : 2
else if n==3 : 6
else if (n-1)%4 == 0 : n*2
else if (n%2) != 0 : 12
else if n%4 == 0 : 4
else if n%2 == 0 : n
M Travel
实况
dijkstra,上来就wa一发,回头一看输入:额,c是干什么的
题解
就是dijkstra,要注意这里dis[x]要存两个数字,lv和剩余次数.
lv小的更优,如果lv相同,剩余次数多的更优.
每次找下一步要注意升级和减少剩余次数.