2020-team1-051

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team1 返回]

== 概述 ==

solved: 6/12  dirt: 40%

rank: 7

[[Image(Rank.png,800px)]]


== 总结 ==

Sakuya:赛场5h就只是在想L，赛后调了一万年，如果不是oscar造的数据我根本调不出来，人没了的经典表现。

Grammy: J写丑了，卡了好久后自己造了个数据把自己卡掉了。感觉自己的写法很不优美，但是当时没想到别的写法就上了。感觉要是能过了这个L这场就还可以。

== 题解 ==

A: 背包

B: 分块，维护每块排序后的数组和后缀和，修改暴力O(B)，查询先把零散块取出来形成假块，然后二分答案后在每个块内再二分O(B+(n/B)log(n)log(w))，取B=nlogn左右

C: 

D: 

E: 

F: 拆位，每一位考虑，然后dsu

G: 

H: 先手必胜当且仅当初始点是一个一定在最大匹配内的点，dinic

I: 

J: 状压dp

K: gcd(a,b)=a xor b 的必要条件是 a=kc,b=(k+1)c 或相反。打表发现对于固定的a，不同的b至多只有71种，暴力维护每个集合的答案，合并用启发式

L: 枚举最小值所在的位置，然后解出要下降的（k+1）的数量

[/wiki/2020-team1 返回]

概述

solved: 6/12 dirt: 40%

rank: 7

总结

Sakuya:赛场5h就只是在想L，赛后调了一万年，如果不是oscar造的数据我根本调不出来，人没了的经典表现。

Grammy: J写丑了，卡了好久后自己造了个数据把自己卡掉了。感觉自己的写法很不优美，但是当时没想到别的写法就上了。感觉要是能过了这个L这场就还可以。

题解

A: 背包

B: 分块，维护每块排序后的数组和后缀和，修改暴力O(B)，查询先把零散块取出来形成假块，然后二分答案后在每个块内再二分O(B+(n/B)log(n)log(w))，取B=nlogn左右

C:

D:

E:

F: 拆位，每一位考虑，然后dsu

G:

H: 先手必胜当且仅当初始点是一个一定在最大匹配内的点，dinic

I:

J: 状压dp

K: gcd(a,b)=a xor b 的必要条件是 a=kc,b=(k+1)c 或相反。打表发现对于固定的a，不同的b至多只有71种，暴力维护每个集合的答案，合并用启发式

L: 枚举最小值所在的位置，然后解出要下降的（k+1）的数量

附加文件