2019华工校赛 - B, F, H, K题题解
本场比赛四道中等题，其中三道题数据范围故意放水降低难度。
然后。。没放水那题。。好像。。没人过啊。。？
B - 修仙时在做什么？有没有空？可以来炼丹吗？
M姓出题人：这么老的idea怎么还没人做XD
考虑到本题的idea非常古老，所以在预估难度时设为中等题，然而现场没人过。题意本质上就是给出一个含$2^{18}$个结点的无向连通图，再指定其中$n$个点，求这$n$个指定点的两两之间的最短路的最小值。
接下来的讨论假定$n$个指定点的编号两两不同（如果出现相同编号的话答案就是$0$）。我们不妨考虑二进制分组。枚举二进制位$0 \sim 17$，对每个枚举出的二进制位$2^k$，我们将这$n$个点按照编号对应的二进制位$2^k$为$0$还是$1$分成两组，从一组往另一组跑多起点最短路，然后取个最小值就没了，总复杂度$O(18n \log n)$。
为什么这样做是正确的呢？考虑答案一定是某个编号为$u$的结点到某个编号为$v$的结点的最短路，而$u \neq v$，则他们一定在某个二进制位上是不相同的。当我们按照前述操作枚举到这个不相同的二进制位时，$u$和$v$一定会分到不同组中，因此跑完多起点最短路后一定会计算出全局最小值，于是这题就做完了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5;
const int maxm = 18;
const int maxV = 1<<maxm;
const int INF = 0x3f3f3f3f;
const int P = 19260817;
int cost[maxV][maxm];
int start[maxn], mark[maxV], ans = INF, cc = INF, n;
inline LL PowMod(LL a, LL b) { LL r=1; while(b) { if(b&1) r=r*a%P; a=a*a%P, b>>=1; } return r; }
void init()
{
for (int s = 0; s < maxV; ++s) {
for(int i = 0; i < maxm; ++i)
{
cost[s][i] = PowMod( max(s,s^(1<<i))%P, 1<<i ) % P + 1;
}
}
}
struct node
{
int u,dis;
node(int _u=0, int _dis = 0): u(_u), dis(_dis){}
bool operator <(const node& nn) const
{
return dis > nn.dis;
}
};
priority_queue<node>que;
int dis[maxV];
void solve(int mask)
{
while(!que.empty()) que.pop();
for (int i = 0; i < maxV; ++i) dis[i] = INF;
for (int i = 0; i < n; ++i)
if(start[i] >> mask & 1)
{
dis[start[i]] = 0;
que.push(node(start[i], 0));
}
while(!que.empty())
{
node tmp = que.top(); que.pop();
int u = tmp.u, d = tmp.dis;
if(d >= ans) return;
if(d != dis[u]) continue;
if(d && mark[u])
{
ans = d;
return;
}
for(int i = 0; i < maxm; ++i)
if(dis[u^(1<<i)] > d + cost[u][i])
{
dis[u^(1<<i)] = d + cost[u][i];
que.push(node(u^(1<<i), dis[u^(1<<i)]));
}
}
}
int main()
{
init();
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
scanf("%d", &start[i]);
if(mark[start[i]]==1) exit( puts("0")*0 );
mark[start[i]] = 1;
}
for (int i = 0; i < maxm; ++i) solve(i);
printf("%d\n",ans);
return 0;
}
F - 翻牌游戏
这是一道打表找规律概率DP题。其实这题的数据范围可以出很大，但在某C姓出题人的极力阻止下改成了现在这个范围，也就是说允许直接交概率DP （说到底还是因为CC handsome!）。
设$f[i][k]$表示当前有$i$对对子完全没有翻开过、$k$个对子已经翻开过恰好一张时，在最佳策略下翻完所有牌所需操作数的期望值。那么我们对每个状态有以下两种操作：
- 选两张都没有翻过的牌翻开；
- 选一张翻过的牌和一张没翻过的牌翻开。
仔细讨论每种操作下的转移即可，时间复杂度$O(n^2)$，然后你就会发现$ANS = 2n-1$。此外你还会发现，第二个操作只有在恰好剩两张牌翻过两张牌没翻过时才会进行。
其实这题可以出更难，因为通过打表可以发现$f[n][m] = 2n-1+\frac{3}{2}m+\frac{m}{2(2n+m)}$。。。不过为了提升参赛体验，就不出这么自闭了。
// CC!
#include<bits/stdc++.h>
using namespace std;
typedef double DB;
const int maxn = 5000;
DB f[maxn+5][maxn+5];
bool vi[maxn+5][maxn+5];
DB dfs(int n, int m) {
if(vi[n][m]) return f[n][m];
vi[n][m] = 1;
if(n==0 && m==0) return f[n][m] = 0;
f[n][m] = 1e9;
int hd = n*2+m;
// nn策略
if(hd>=2) {
DB tmp = 0;
if(n>=1) tmp += DB(n*2.0) / (hd*(hd-1.0)) * (dfs(n-1,m)+1); // 2张未知且相同
if(n>=2) tmp += (2.0*n*(2.0*n-2.0)) / DB(hd*(hd-1.0)) * (dfs(n-2,m+2)+1); // 2张未知但不同
if(m>=2) tmp += DB(m*(m-1.0)) / DB(hd*(hd-1.0)) * (dfs(n,m-2)+3); // 2张已知
if(n>=1 && m>=1) tmp += DB(4.0*n*m) / DB(hd*(hd-1.0)) * (dfs(n-1,m)+2); // 1张已知1张未知
f[n][m] = min(f[n][m], tmp);
}
// nm策略
if(m>0) {
DB tmp = 0;
tmp += 1.0 / DB(hd) * (dfs(n,m-1)+1); // 2张已知且相同
if(m>=2) tmp += (m-1.0) / DB(hd) * (dfs(n,m-1)+2); // 2张已知但不同
if(n>=1) tmp += (2.0*n) / DB(hd) * (dfs(n-1,m+1)+1); // 1张未知1张已知
f[n][m] = min(f[n][m], tmp);
}
return f[n][m];
}
int main() {
int _; scanf("%d", &_);
while(_--) {
int n; scanf("%d", &n);
printf("%.2f\n", dfs(n,0) );
}
return 0;
}
H - Parco_Love_GCD
这题原本的时间限制要更小，主要是为了卡掉RMQ的做法。但考虑到大家的参赛体验，就还是给多了时间让RMQ过了（现在来看或许不应该放水）。
两种做法。第一种做法是RMQ进行$O(n \log n \log 10^9)$的预处理搞出区间GCD值，然后每次就可以$O(\ log 10^9)$回答任意区间的GCD值。之后为了计算所有区间的GCD值之和，我们考虑$O(n)$枚举区间左端点，然后每次右端点从左往右二分+RMQ找到第一个会让区间GCD变化的位置，并累加答案。注意到右端点从左往右扫的过程中，GCD至多只会变化$O(\log 10^9)$次，所以这样做总复杂度就变成了$O(n \log n \log^2 10^9)$。
第二种做法是CDQ分治，也就是原本的正解。我们用函数$Solve(l,r)$来计算$[l,r]$的所有子区间的GCD之和。在每一层$Solve(l,r)$中，令$mid = \lfloor \frac{l+r}{2} \rfloor$，然后让左端点从$mid$往$l$扫，记录算出的GCD值及对应出现次数并扔到一个map里，同理让右端点从$mid+1$往$r$扫，将计算出的GCD值出现次数信息扔到另一个map里。现在我们有了两个map，他们的大小均不超过$O(\log 10^9)$，于是就可以$O(\log^2 10^9)$枚举两个map里的东西，同时$O(\log 10^9)$算一下GCD统计答案。
算一下第二种做法的复杂度。端点左右扫加上GCD以及map的复杂度后，所需的总复杂度为$O(n \log n \log 10^9)$。枚举map里的东西时，因为$Solve(1,n)$所涉及到的所有区间个数是$O(n)$级别的，所以这部分总复杂度为$O(n \log^3 10^9)$。综上CDQ分治的复杂度为$O(n (\log n \log 10^9 + \log ^3 10^9))$。
这里只贴CDQ分治的代码：
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define PER(i,a,b) for(int i=a; i>=b; --i)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long LL;
typedef double DB;
const int maxn = 5e5;
const int maxV = 1e9;
const int P = 1e9+7;
LL Gcd(LL a, LL b) { return b ? Gcd(b,a%b) : a; }
map<int,int> s1, s2;
int n, ai[maxn+5];
LL ans = 0;
inline void Add(LL &a, LL b) { a+=b; if(a>=P) a-=P; }
void Solve(int l, int r) {
if(l==r) { Add(ans, ai[l]); return; }
int mid = (l+r)>>1;
s1.clear();
s2.clear();
int now = 0;
for(int i = mid; i >= l; --i) {
now = Gcd(now, ai[i]);
++s1[now];
}
now = 0;
for(int i = mid+1; i <= r; ++i) {
now = Gcd(now, ai[i]);
++s2[now];
}
for(auto pp : s1) {
for(auto qq : s2) {
Add(ans, Gcd(pp.fi, qq.fi) * pp.se % P * qq.se % P);
}
}
Solve(l, mid);
Solve(mid+1, r);
}
int main() {
scanf("%d", &n);
assert(1<=n && n<=maxn);
REP(i,1,n) scanf("%d", ai+i);
Solve(1,n);
printf("%lld\n", ans);
return 0;
}
K - Parco_Love_String
本题时间限制及数据范围继续放水，出题人现在就是很后悔_(:3」∠)_
第一种做法是Hash后STL乱搞，没什么好说的，唯一要注意的是现场专门卡掉了map，需要unordered_map或者pb_ds才能通过，但牛客上是没有卡map的。
第二种做法是SAM（后缀自动机）乱搞。问题的核心就是给出$A, B$两个串，如何快速$B$的每个子串在$A$中的出现次数之和。我们考虑对$A$建SAM，通过经典的Fail树结点基数排序后就可以算出SAM中每个结点对应的那个（那些）串在整个$A$串中的出现次数（代码中记为occ）。此外，对于每个SAM上每个结点的$len$成员（在标程代码中是val），预处理出它在SAM中对应的那个长度为$len$的串的所有子串在整个$A$串的出现次数之和（代码中记为sum）。然后拿$B$串在SAM上跑一遍顺便计个数就可以算出答案了，具体计数方法参考代码。总时间复杂度$O(n^2)$，比Hash不知道高到哪里去。
现场还有人用KMP也过了，大家可以自行思考，这里只贴SAM代码。
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define PER(i,a,b) for(int i=a; i>=b; --i)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long LL;
typedef double DB;
const int maxn = 1000, c_size = 26;
struct State {
int val;
LL sum, occ;
int par, go[c_size];
void init() { val = 0, sum = 0, occ = 0, par = -1, mem(go,-1); }
}que[maxn*2+5];
int root, last;
int tot;
void Extend(int w) {
int p = last, np = tot++;
que[np].init();
que[np].val = que[p].val+1;
que[np].occ = 1;
while(p!=-1 && que[p].go[w]==-1)
que[p].go[w] = np, p = que[p].par;
if(p == -1) que[np].par = root;
else {
int q = que[p].go[w];
if(que[p].val+1 == que[q].val) que[np].par = q;
else {
int nq = tot++;
que[nq] = que[q];
que[nq].val = que[p].val+1;
que[nq].occ = 0;
que[np].par = que[q].par = nq;
while(p!=-1 && que[p].go[w]==q)
que[p].go[w] = nq, p = que[p].par;
}
}
last = np;
}
char str[maxn+5];
LL f[maxn+5];
int cont[maxn+5], S[maxn*2+5];
int main() {
scanf("%s", str+1);
int n = strlen(str+1);
for(int kk = 1; kk < n; ++kk) {
root = last = 0;
tot = 1, que[0].init();
for(int i = 1; i <= kk; ++i) Extend(str[i]-'a');
for(int i=0; i<=kk; ++i) cont[i] = 0;
for(int i=0; i<tot; ++i) ++cont[que[i].val];
for(int i=1; i<=kk; ++i) cont[i] += cont[i-1];
for(int i=tot-1; i>=1; --i) S[--cont[que[i].val]] = i;
for(int i = tot-1; i >= 1; --i) {
int x = S[i];
que[que[x].par].occ += que[x].occ;
}
for(int i = 1; i < tot; ++i) {
int x = S[i];
que[x].sum = que[que[x].par].sum;
que[x].sum += LL(que[x].val-que[que[x].par].val) * que[x].occ;
}
int p = root;
int now = 0;
f[kk] = 0;
for(int i = kk+1; i <= n; ++i) {
int w = str[i]-'a';
if(que[p].go[w] != -1) {
p = que[p].go[w];
++now;
}
else {
while(p!=-1 && que[p].go[w]==-1) p = que[p].par;
if(p == -1) p = root, now = 0;
else {
now = que[p].val+1;
p = que[p].go[w];
}
}
if(now>0) {
f[kk] += que[que[p].par].sum;
f[kk] += LL(now - que[que[p].par].val) * que[p].occ;
}
}
}
int _; scanf("%d", &_);
while(_--) {
int kk; scanf("%d", &kk);
printf("%lld\n", f[kk]);
}
return 0;
}