Preface
好难啊这场广州站，不愧是5题金4题铜的超恶劣站，中档题普遍难度较高
但我感觉主要原因还是题目出的太偏向于DP了，AI是本质差不多的树上换根DP，M又是个数位DP，导致像我这种不擅长DP的人直接中期坐牢
但好在祁神大力切出了medium~hard的K题，然后最后一小时我把一直在想的A题丢给徐神后转战I题发现是个傻逼题，过掉后6题收场
最后半小时徐神上去极限写完了A，过了样例后WA了也没时间调了，而且最后坐在下面的时候和祁神又发现了J题的很多性质，但都没时间写了
A. Alice and Her Lost Cat
首先发现\(t_i\)的作用可以最后考虑，因此不妨先考虑树上问题
手玩一下会发现一个叶子节点可以通过直接调监控确定，或者选择通过调查其祖先来确定，而一个子树中最多只能有一个点是通过调查祖先来确定
不妨设\(f_{u,i,0/1}\)表示在点\(u\)的子树内，能确定\(i\)个叶子节点，其中是否存在某个叶子节点是需要让其祖先来确定它
转移的话就是个类似于树上背包的合并，对于不在\(u\)这个点调监控的情况
第三维为\(0\)的状态只能由子树中第三维为\(0\)的状态转移来，而第三维为\(1\)的状态可以由子树中至多一个第三维为\(1\)的状态（其它的都是从\(0\)）转移来
而如果要在第三维调监控，那么它的子树的第三维可以在\(0/1\)间选择一个较小的转移，最后再加上\(a_u\)的代价
最后\(ans=\min_\limits{1\le i\le n} (\min(f_{1,i,0},f_{1,i,1})+t_{sz_1-i})\)，总复杂度就是树上背包的\(O(n^2)\)
#include<cstdio>
#include<iostream>
#include<vector>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=2005,INF=5e17;
int T,n,a[N],t[N],x,y,f[N][N][2],g[N][N],sz[N]; vector <int> v[N];
inline void DP(CI now=1,CI fa=0)
{
if (v[now].size()==1&&fa)
{
sz[now]=1; f[now][0][0]=f[now][1][1]=0;
f[now][1][0]=a[now]; return;
}
static int tmp[N][2],_tmp[N]; RI i,j;
sz[now]=0; f[now][0][0]=g[now][0]=0;
for (auto to:v[now]) if (to!=fa)
{
for (DP(to,now),i=0;i<=sz[now]+sz[to];++i)
tmp[i][0]=tmp[i][1]=_tmp[i]=INF;
for (i=0;i<=sz[now];++i) for (j=0;j<=sz[to];++j)
{
tmp[i+j][0]=min(tmp[i+j][0],f[now][i][0]+f[to][j][0]);
tmp[i+j][1]=min(tmp[i+j][1],min(f[now][i][1]+f[to][j][0],f[now][i][0]+f[to][j][1]));
_tmp[i+j]=min(_tmp[i+j],g[now][i]+min(f[to][j][0],f[to][j][1]));
}
for (sz[now]+=sz[to],i=0;i<=sz[now];++i)
f[now][i][0]=tmp[i][0],f[now][i][1]=tmp[i][1],g[now][i]=_tmp[i];
}
for (i=0;i<=sz[now];++i) f[now][i][0]=min(f[now][i][0],g[now][i]+a[now]);
}
signed main()
{
//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
for (scanf("%lld",&T);T;--T)
{
RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);
for (i=1;i<=n;++i) scanf("%lld",&t[i]),v[i].clear();
for (i=1;i<n;++i) scanf("%lld%lld",&x,&y),v[x].push_back(y),v[y].push_back(x);
if (n==1) { puts("0"); continue; }
int ans=INF; for (DP(),i=1;i<=sz[1];++i)
ans=min(ans,min(f[1][i][0],f[1][i][1])+t[sz[1]-i]);
printf("%lld\n",ans);
}
return 0;
}
B. Ayano and sequences
题目都没看，不可做之数据结构
C. Customs Controls 2
图论构造题，我扔给徐神一个假算法后徐神能还给我一个真算法，真是tql
考虑设\(d_i\)表示\(1\to i\)路径上所有点的点权和，则对于某个点\(v\)，它的所有入点\(u_i\)的\(d_{u_i}\)应该都相等，我们可以用并查集维护这些等价关系
然后类似于Tarjan求强连通分量后缩点的过程，我们把\(d_i\)相同的点都缩成一类，不难发现此时得到的还是个DAG
在这个DAG上跑出缩点后每个点从\(1\)出发的最长路\(dis_i\)后，不难发现对于原图中的一个点\(v\)的点权就是\(dis_{\operatorname{getfa(v)}}-dis_{\operatorname{getfa(u)}}\)，其中\(u\to v\)为原图中的一条边
本来徐神认为对于一次缩点后的图如果还存在某个点具有超过\(1\)个入点的情况的话就要再次缩点，但我当时觉得这个迭代缩点过程不好写（虽然徐神说很好写）就怂恿他直接交一发
后面也不知道是缩一遍就行了还是数据水了总之就过了，有点难绷
#include <bits/stdc++.h>
constexpr int $n = 200000 + 5;
int t, n, m, dis[$n], indu[$n], qu[$n], ans[$n], fa[$n], ars[$n], ql, qr;
std::vector<int> out[$n], ous[$n];
inline int father(int p) {
if(fa[p] == p) return p;
return fa[p] = father(fa[p]);
}
inline int unn(int a, int b) {
a = father(a), b = father(b);
if(a != b) fa[b] = a; return a;
}
int main() {
// freopen("1.in", "r", stdin);
std::ios::sync_with_stdio(false);
std::cin >> t;
while(t--) {
std::cin >> n >> m;
for(int i = 1; i <= n; ++i)
ans[i] = indu[i] = ars[i] = dis[i] = 0, fa[i] = i,
out[i].clear(), ous[i].clear();
for(int i = 1, f, t; i <= m; ++i) {
std::cin >> f >> t;
out[f].push_back(t);// back[t].push_back(f);
if(ars[t]) ars[t] = unn(ars[t], f); else ars[t] = f;
}
for(int i = 1; i <= n; ++i) for(auto out: out[i]) {
int fr = father(i), to = father(out);
if(fr == to) goto __No__;
ous[fr].push_back(to);
indu[to] += 1;
}
ql = 0, qr = 0;
dis[qu[ql] = father(1)] = 0;
while(ql <= qr) {
int now = qu[ql++];
for(auto out: ous[now]) {
dis[out] = std::max(dis[out], dis[now] + 1);
if(--indu[out] == 0) qu[++qr] = out;
}
}
for(int i = 1; i <= n; ++i) if(indu[i]) goto __No__;
// std::cerr << "QWQ\n";
for(int i = 1; i <= n; ++i) for(auto out: out[i]) {
int f = father(i);
int t = father(out);
ans[out] = dis[t] - dis[f];
}
ans[1] = 1;
// for(int i = 1; i <= n; ++i) if(ans[i] <= 0) goto __No__;
std::cout << "Yes\n";
for(int i = 1; i <= n; ++i) std::cout << ans[i] << char(i == n ? 10 : 32);
continue;
__No__: std::cout << "No\n";
}
return 0;
}
D. Digits
题目都没看过
E. Elevator
签到题，将电梯按\(x_i\)从小到大排序后枚举要变成第一名的\(i\)，发现要把所有\(x_j\)小于\(x_i\)的电梯都变成\(x_i\)才行
同时由于同时到达看序号的原因还有特别维护下这部分，可以用树状数组实现，代码是祁神写的
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5;
int n, m, A[N], id[N];
int ans[N];
int cnt[N];
int lb(int x){return x&(-x);}
void upd(int pos){
for (int i=pos; i<=n; i+=lb(i)){
++cnt[i];
}
}
int qry(int pos){
int res=0;
for (int i=pos; i>0; i-=lb(i)) res+=cnt[i];
return res;
}
bool cmp(int a, int b){
return A[a]!=A[b] ? A[a]<A[b] : a<b;
}
signed main(){
scanf("%lld%lld", &n, &m);
for (int i=1; i<=n; ++i){
scanf("%lld", &A[i]);
id[i]=i;
}
sort(id+1, id+n+1, cmp);
memset(ans, -1, (n+1)*sizeof(int));
ans[id[1]]=0;
upd(id[1]);
int sum=0;
for (int i=2; i<=n; ++i){
if (A[id[i]]>A[id[i-1]]){
sum += (A[id[i]]-A[id[i-1]])*(i-1);
}
ans[id[i]]=sum+qry(id[i]);
upd(id[i]);
if (ans[id[i]]>m-2){ans[id[i]]=-1; break;}
}
for (int i=1; i<=n; ++i) printf("%lld\n", ans[i]);
return 0;
}
F. Equations
神仙题，做不了一点
G. Game
ORZ徐神总能在开场的时候一眼找到本场最难的题并开始看题
H. GameX
签到题，不难发现Alice的策略就是每次把最小的没出现的奇数扔进集合里，Bob的就是扔偶数
模拟下这个过程后看看最后得到的\(\operatorname{MEX}\)的奇偶性即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=2e6+5;
int t,n,k,a[N],vis[N];
int main()
{
//freopen("H.in","r",stdin); freopen("H.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; scanf("%d%d",&n,&k); int ca=k,cb=k;
for (i=1;i<=n;++i) scanf("%d",&a[i]),vis[a[i]]=1;
int mex=0,flag=0; while (!flag)
{
while (vis[mex]) ++mex;
if (mex&1)
{
if (ca) --ca,vis[mex]=1; else flag=-1;
} else
{
if (cb) --cb,vis[mex]=1; else flag=1;
}
}
puts(flag>0?"Alice":"Bob");
for (i=0;i<=mex;++i) vis[i]=0;
for (i=1;i<=n;++i) vis[a[i]]=0;
}
return 0;
}
I. Infection
刚开始以为是个换根DP，后面发现TMD又是树上背包
首先发现最后的感染部分一定是一个连通块，且这个概率等于连通块中所有点的\(p_i\)的乘积，乘上所有和连通块相邻的外部点的\(1-p_i\)
同时还要在连通块内找一个点\(s\)作为感染初始点，要把之前的概率中的\(p_s\)除掉后替换成\(\frac{a_s}{\sum a_s}\)
乍一看很复杂其实仔细一想很简单，我们不妨直接钦定以\(1\)为根，设\(f_{u,i,0/1}\)表示在点\(u\)的子树中，选了\(i\)个点（若\(i>0\)则\(u\)本身一定要选，否则不连通），是否已经确定了感染初始点的概率
初值的话就是\(f_{u,1,1}=\frac{a_u}{\sum a_i},f_{u,1,0}=p_u,f_{u,0,0}=(1-p_u)\)，而转移的话可以说和A题的一模一样，对于第三维的限制考虑清楚转移即可
最后在求得每个点的\(f_u\)后，考虑在这个点处断开统计对答案的贡献，则\(f_{u,i,1}\times (1-p_{fa_u})\to ans_i\)
总复杂度\(O(n^2)\)
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=2005,mod=1e9+7;
int n,x,y,a[N],p[N],sz[N],sum,f[N][N][2],ans[N]; vector <int> v[N];
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void DP(CI now=1,CI fa=0)
{
f[now][1][1]=1LL*a[now]*quick_pow(sum)%mod;
f[now][0][0]=(1-p[now]+mod)%mod; f[now][1][0]=p[now];
static int tmp[N][2]; RI i,j; sz[now]=1;
for (auto to:v[now]) if (to!=fa)
{
for (DP(to,now),i=1;i<=sz[now]+sz[to];++i) tmp[i][0]=tmp[i][1]=0;
for (i=1;i<=sz[now];++i) for (j=0;j<=sz[to];++j)
{
inc(tmp[i+j][0],1LL*f[now][i][0]*f[to][j][0]%mod);
inc(tmp[i+j][1],1LL*f[now][i][1]*f[to][j][0]%mod);
inc(tmp[i+j][1],1LL*f[now][i][0]*f[to][j][1]%mod);
}
for (sz[now]+=sz[to],i=1;i<=sz[now];++i)
f[now][i][0]=tmp[i][0],f[now][i][1]=tmp[i][1];
}
for (i=1;i<=sz[now];++i) inc(ans[i],1LL*f[now][i][1]*(1-p[fa]+mod)%mod);
}
int main()
{
//freopen("I.in","r",stdin); freopen("I.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<n;++i)
scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
for (i=1;i<=n;++i) scanf("%d%d%d",&a[i],&x,&y),sum+=a[i],p[i]=1LL*x*quick_pow(y)%mod;
for (DP(),i=1;i<=n;++i) printf("%d\n",ans[i]);
return 0;
}
J. Math Exam
最后快结束的时候在下面和祁神玩这个题已经发现就是个坐标系走路的题了，但不知道为什么算出来和样例对不上，先坑了以后再补吧
K. Middle Point Graph
这题由于我一点没参与就直接扔官方题解中的讨论了，只能说祁神太猛了这种东西都能讨论清楚
然后祁神上去咔咔把板子一抄就直接秒了此题，ORZ
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
const int N = 2e5+5;
int t, n, m;
vector<int> G[N];
vector<int> G2[N];
vector<int> key[N];
int p[N], deg[N];
int cycle4(){
int ans=0;
vector<int> kth(n+1);
vector<int> rk(n+1);
vector<int> cnt(n+1);
for (int i=0; i<n+1; ++i) kth[i]=i;
sort(kth.begin(), kth.end(), [&](int x, int y){return deg[x] < deg[y];});
for (int i=1; i<n+1; ++i) rk[kth[i]]=i;
for (int u=1; u<n+1; ++u)
for (int v : G[u])
if (rk[v] > rk[u]) key[u].push_back(v);
for (int u=1; u<n+1; ++u){
for (int v : G[u])
for (int w : key[v])
if (rk[w] > rk[u]) ans += cnt[w]++;
for (int v : G[u])
for (int w : key[v])
if (rk[w] > rk[u]) --cnt[w];
}
return ans;
}
int cycle3(){
int ans=0;
for (int u=1; u<=n; ++u){
for (int v : G[u]){
if (deg[u]<deg[v] || (deg[u]==deg[v] && u<v))
G2[u].push_back(v);
}
}
for (int x=1; x<n+1; ++x){
for (int y : G2[x]) p[y]=x;
for (int y : G2[x]) for (int z:G2[y]) if (p[z]==x) ++ans;
}
return ans;
}
signed main(){
scanf("%lld", &t);
while (t--){
scanf("%lld%lld", &n, &m);
memset(deg, 0, (n+1)*sizeof(int));
memset(p, 0, (n+1)*sizeof(int));
for (int i=1; i<=n; ++i){
G[i].clear(); G2[i].clear();
key[i].clear();
}
for (int i=1; i<=m; ++i){
int a, b;
scanf("%lld%lld", &a, &b);
G[a].push_back(b); G[b].push_back(a);
++deg[a], ++deg[b];
}
int ans = m*(n+m-3)%MOD;
for (int i=1; i<=n; ++i){
if (deg[i]<2) continue;
ans = (ans+(deg[i]-1)*deg[i]/2)%MOD;
}
int c3=cycle3(), c4=cycle4();
// printf("3:%lld 4:%lld\n", c3, c4);
ans = (ans + c3*3)%MOD;
ans = (ans + c4)%MOD;
printf("%lld\n", ans);
}
return 0;
}
L. Station of Fate
签到题，开场的时候我通过对样例找规律发现答案就是\(n!\times C_{n-1}^{m-1}\)，交上去发现确实是对的
证明的话就是先把\(n\)个人定序然后依次插入队列中，由于这里要求每个序列不能为空所以用一下插板法就可以得到方案数了
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=998244353;
int t,n,m,fact[N],ifac[N];
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
//freopen("L.in","r",stdin); freopen("L.out","w",stdout);
for (scanf("%d",&t),init(100000);t;--t)
scanf("%d%d",&n,&m),printf("%d\n",1LL*fact[n]*C(n-1,m-1)%mod);
return 0;
}
M. XOR Sum
数位DP战俘闪总出列，这题比赛的时候看榜被过穿了，但我们队就愣是不会
后面一看题解妈的直接给我气吐血，可以说基本已经做出来了，就是没有大胆一点直接把和直接存到状态里
考虑从高位到低位分别处理，由于每一位的贡献之和这一位上\(1\)的个数有关
设当前处理的是第\(k\)位，当这一位上有\(x\)个\(1\)时，对序列的价值的贡献就是\(x\times (k-x)\times 2^k\)
而这里又有个每个数\(\le m\)的限制，因此很容易想到数位DP
每一位可以取\(1\)的数的数量和是否卡上界有关，因此我们可以把卡上界的数的个数也存到状态里
此时我们的状态就很容易设出了，设\(DP(now,lim,sum)\)表示从高到低处理到第\(now\)位，之前卡上界的数的个数为\(lim\)，产生的贡献为\(sum\)的方案数
转移的话就根据\(now\)这一位上\(m\)是\(0/1\)讨论下即可，方案数的话就是组合数
但直接这么写其实是会T飞的，原因自然是第三维的可能取值有太多了
但神奇的是我们可以通过一个简单的剪枝来大幅优化复杂度，假设在做到某个状态时，若之后的每一位都选择让贡献最大的方式还是无法使得总贡献达到\(n\)就直接退出
乍一看这个剪枝的作用微乎其微，但实际上可以证明它的复杂度上界是对的，具体看这里
代码就很好写了
#include<cstdio>
#include<iostream>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=21,mod=1e9+7;
int n,m,k,C[N][N]; unordered_map <int,int> f[N<<1][N];
inline void init(CI n)
{
RI i,j; for (C[0][0]=i=1;i<=n;++i)
for (C[i][0]=j=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
inline int DP(CI now,CI lim,CI sum)
{
if (sum>n) return 0; if (now<0) return sum==n;
if (sum+(k>>1LL)*(k+1>>1LL)*((1LL<<now+1)-1)<n) return 0;
if (f[now][lim].count(sum)) return f[now][lim][sum];
RI i,j; int ret=0; if ((m>>now)&1)
{
for (i=0;i<=lim;++i) for (j=0;j<=k-lim;++j)
(ret+=C[lim][i]*C[k-lim][j]%mod*DP(now-1,i,sum+(i+j)*(k-i-j)*(1LL<<now))%mod)%=mod;
} else
{
for (j=0;j<=k-lim;++j)
(ret+=C[lim][0]*C[k-lim][j]%mod*DP(now-1,lim,sum+j*(k-j)*(1LL<<now))%mod)%=mod;
}
return f[now][lim][sum]=ret;
}
signed main()
{
//freopen("M.in","r",stdin); freopen("M.out","w",stdout);
scanf("%lld%lld%lld",&n,&m,&k); init(k);
return printf("%lld",DP(39,k,0)),0;
}
Postscript
今晚还有CF，我直接搞新的小号开始摆烂了，不然这一天天的强度拉满真有点吃不消的说
标签：Onsite,include,const,Contest,int,Guangzhou,define,now,mod From： https://www.cnblogs.com/cjjsb/p/17738236.html