CodeForces精选笔记

方杰123 · 2023-03-08 15:55:54 · 个人记录

\color{purple}\text{Deletion of Repeats}

\color{red}\text{Rating:2100}

\color{green}\text{time:2023.3.8}

莫名出现的东西必有猫腻。

本题核心在于每个字符最多出现 10 次，所以找出所有相邻的重复部分（枚举开头相同的字串），用 \text{hash} 判断即可。

\color{purple}\text{Greedy Change}

\color{red}\text{Rating:2600}

\color{green}\text{time:2023.3.9}

有时侯越是深入，越难看清，不如置身世外，跟着感觉走。

我们记答案为 \text{S} 。（即要表示的金额）

其实我们都不难感觉到，大概要找一个接近一种货币 T 但稍微大一点的值作为 \text{S}，因为这样贪心的笨蛋用了这种货币 T 后就只能用更小的货币了，这样就容易造成劣解。但是究竟该怎么找，恐怕难以具象化为程序。

方法是设定一个最下界货币 j ，上文说了，“笨蛋只能用更小的货币了”，那么正解肯定不会去用很小的货币，设定一个下界 j ，当表示 T 时强制只能用 j 到 T 之间的货币。 然后对于这种方案润色一下（你暂时不需要明白怎么“润色”），再交给笨蛋做，比较一下答案对不对。

关键变成了枚举这个 S ，有一点显然， S<a[T+1] ，（否则笨蛋还会选 T 么？），不妨先设 S=a[T+1]-1 （T 枚举），枚举下界 j ，然后贪心一遍模拟聪明人，此时 S 可能仍有剩余，方法是简单粗暴地去掉这个剩余；此时又发现可能用的最小货币可能不是 j ，方法是 S+=a[j] 。

确定了合法的 S 后其他就是顺藤摸瓜：模拟笨蛋做一遍，与聪明人对比，如果更劣就更新答案。

嗯，然后就结束了。其实看到这里你肯定还是不明白，没关系，因为我也不明白。冗杂的证明看不来，尚且能根据人类的推理能力得出答案。

其实世界就是这样呢，有时候不需要知道为什么，也会勇敢地尝试。

\color{purple}\text{Galaxy Union}

\color{red}\text{Rating:2700}

\color{green}\text{time:2023.3.12}

简化题面：给定一个 n 点无向基环树，求每个点到其余点最短路之和。

先考虑普通的树怎么做：U285295 的 & 树 。 以一号点为根，怎么求出他到其他点的距离？也许可以树形 DP ，设置 dp[i] 表示从 i 点到其他点的距离， sze[i] 表示 i 点子树大小：

void work(int u,int fa){
    sze[u]=1;
    for(int i=head[u];i;i=last[i]){
        int v=to[i];if(v==fa || bk[v]==2)continue;//暂时忽略bk[v]==2
        work(v,u);
        sze[u]+=sze[v];
        dp[u]+=dp[v]+w[i]*sze[v];
    }
    return;
}

然后呢？然后是换根 DP，求出剩下点为根的答案：

void tree_dp(int u,int fa){
    ans[u]=dp[u];
    for(int i=head[u];i;i=last[i]){
        int v=to[i];if(v==fa || bk[v]==2)continue;//暂时忽略bk[v]==2
        int r1=dp[u],r2=sze[u],r3=dp[v],r4=sze[v];
        dp[u]-=dp[v]+sze[v]*w[i];sze[u]=n-sze[v];
        dp[v]+=dp[u]+sze[u]*w[i];sze[v]=n;
        tree_dp(v,u);
        dp[u]=r1,sze[u]=r2;
        dp[v]=r3,sze[v]=r4;//还原
    }
    return;
}

完成这些后即可通过弱化版的此题。 接下来考虑基环树上：

首先找环，这里不多说了。 然后对环上每个点向它的子树做一次树形 DP 。

接下来考虑以 1 为起点，那么它的最短路怎么走：发现最优秀走法是对于环上的 \text{4,3} 点及其子树走逆时针，对于 2 及其子树走顺时针。子树中的点已经树形 DP 计算过了，剩下的只要考虑环上的边的贡献即可。

显然有一个性质，对于点 i 出发 ,有半个环的最优走法是顺时针，剩下半个环是逆时针。我们考虑变换起点时维护环上的走顺时针的点的区间，然后即可计算出环上每个点的答案，最后在对环上每个点的子树内做一次换根DP 那么这题就结束了。

\color{purple}\text{Pairs}

\color{red}\text{Rating:2700}

\color{green}\text{time:2023.3.14}

简化题面：给定基环树（森林），每个点被染为白或黑色，求基环树的最大匹配，且此时黑色与白色的匹配数量最大。

还是先考虑树上怎么做，考虑树形 DP ，根据经验，我们可以把最大匹配的权值乘上 2e5 ，显然这样保证优先最多匹配。设置 f[i][0] 表示 i 不被匹配时 i 及其子树最大匹配数， f[i][1] 表示 i 不论匹配与否时 i 及其子树最大匹配数。易得：

然后考虑基环树，显然我们可以删掉一条边变成一棵树，然后枚举这条边选不选，即可得到答案（其实我不是这么写的，但思路大致相同）。

最后提一些细节，如果出现基环树变树的情况，请一定要去重边；以及我 bk 的时候用 bk[u]=fa ，但是没想到根的 fa=0 ，白标记了。

\color{purple}\text{Help Shrek and Donkey}

\color{red}\text{Rating:2700}

\color{green}\text{time:2023.3.15}

且不说怎么推概率，欺骗策略真的很好玩。

这里主要写一下纳什均衡。

任何一位玩家在此策略组合下单方面改变自己的策略（其他玩家策略不变）都不会提高自身的收益。

例如这题，（图片来自题解） 显然，当我们确定先手 p 的概率询问时（ 1-p 的概率欺骗），后手可以选择相信或不相信，并可能因此改变我们的获胜概率，而此时最优方案就是达到纳什均衡。即后手相不相信，我们获胜的概率都是一样的。