Jason Fan.

CF-246E 题意简述 给定一片 nnn 个点的森林，每次询问一个节点的K-Son共有个多少不同的名字。一个节点的K-Son即为深度是该节点深度加 KKK 的节点。 n,q≤105n,q\le 10^5n,q≤105 题解 首先看一个弱化版的题目：CF208E Blood Cousins ，题意是 给你一片森林，每次询问一个点与多少个点拥有共同的 KKK 级祖先。 把所有根结点连向 0 ，可以 Dfs 出 dfn 序，要求的便是一个点向下 KKK 层 dfn 序在该点范围内的点有多少个，双关键字（先深度后dfn序）排序后，每次询问二分答案即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include <bits/stdc++.h>using namespace std;template<typename T>inline void red(T &x) { x=0;bool fg=0;c ...

fdbc2997623a61cf73a7235ddd759531c5c1d64aa56d5f2b54a26e0ff5aca4040b40a6a6c3c8b9692c5df60a1f0fe56700c5a70e69a7af3453907a08a2ba7f4e585a309c84c15e457d01a985a302cf76c506aaf7ba3414c4710cab6a17deee80639c700681091570a4aace3aa591df099cd920bc48c048a9729d9b6da9458cda77e2a070f8a36c87090029e286699cd143c6c0e8a698a4b7950f834a7655cb1cd96a136079a014d73a078dec0521b1611d22c47d4f0d5de3636f33f06ba691779b37b0b887486d253ef084fcb61358114223d278cb23b8100daab44a1362271d3a1ee43160fc31aaeb43e7b06197ce5680b33cddce566b5ad ...

只是测试，不要在意内容， 本视频是初一的时候闲的慌搞的。。。 var player = polyvObject('#plv_9cba273f4305d1fcc2a8c7cb7b3ee7ff_9').videoPlayer({ 'width':'100%', 'height':'300', 'vid' : '9cba273f4305d1fcc2a8c7cb7b3ee7ff_9' });

文章测试 H1 H2 H3 分割线 粗体 斜体 删除线 引用 图片 链接 link 有序列表 hello world nice to meet you 无序列表 第一项 第二项 第二.一项 第二.二项 第三项 代码块 123456789101112131415161718#include <bits/stdc++.h>std::vector< std::pair<int,int> > a;int rnd(int l,int r) { return rand()%(r-l+1)+l;}int main() { srand(clock()*1000); int n=rnd(5,10); printf("%d\n",n); for(int i=1;i<=n;i++) { printf("%d ",rnd(1,n)); }printf("\n"); for(int ...

CF-98E 题意 A 有 nnn 张牌， B 有 mmm 张牌，桌上还有一张反扣着的牌，牌的编号在 [1,n+m+1][1, n + m + 1][1,n+m+1] 之间且互不相同。 用这些牌进行博弈，每轮每人可以进行如下操作中的一个: 猜桌面上的反扣着的牌上的数字，猜对则获得胜利，猜错则对方胜利。 询问对方是否有某张牌，若拥有则对方需要出示这张牌，否则继续游戏。 若 A 和 B 都绝顶聪明，求 A 的胜率。 n,m≤1000n, m \le 1000n,m≤1000 题解 “首先我们清楚的知道双方的策略必然包含随机因素，因为这是一个非完全信息博弈，同时由于这是一个零和博弈，双方的策略都希望能够最小化对方获胜的概率。那么模型就很清楚了，混合策略纳什均衡。” ——搬自zxyoi dpn,mdp_{n,m}dpn,m​ 表先手 n 张牌，后手 m 张牌，先手胜的概率，我胜即你输，显然 dpn,m=1−dpm,ndp_{n,m}=1-dp_{m,n}dpn,m​=1−dpm,n​ 然后边界显然： dpn,0=1dp_{n,0}=1dpn,0​=1 先手知道桌上牌，必胜 dp0, ...

GYM-100553I in zh-CH 题意简述 原题说的是鬼话，这里是人话转述： 有 n+1n+1n+1 个点 x0,x1,…,xnx_0,x_1,\dots,x_nx0​,x1​,…,xn​ 其中 x0=0x_0=0x0​=0 ，xix_ixi​ 两两不同且 1≤xi≤n1\le x_i\le n1≤xi​≤n ，视第 iii 个区间为 (xi−1,xi)(x_{i-1},x_i)(xi−1​,xi​) ，定义 A,BA,BA,B 两区间不相交为 A∩B≠ϕ,A⊈B，B⊈AA\cap B \ne\phi,A\not\subseteq B，B\not\subseteq AA∩B=ϕ,A⊆B，B⊆A。要使没有区间相交，有一些 xix_ixi​ 要改变，求出不用改变的 xix_ixi​ 最多有几个。 1≤n≤2×1051\le n\le 2\times 10^51≤n≤2×105 题解 没有区间相交，就是说任意一对区间要么包含要么交集为空。 仔细想想，可以发现，若最终 nnn 个区间合法，对于 i<ji\lt ji<j ，第 jjj 个区间不能包含第 iii 个 ...

2018 ACM-ICPC World Finals H IN zh-CH 题意 有一个 w×hw\times hw×h 的框（ 1≤w,h≤1081\le w,h \le 10^81≤w,h≤108 ） ，有 nnn 条线段，每条线段两端点在框的不同边上，问每次砍直线，至少砍几刀把所有线砍断，并输出任意一种解。保证没有电线连接到门的四个角落。输入的所有位置都是两两不同的。 （蓝色为线，红色为刀切的直线） 左图一刀可切所有线，右图需两刀。 题解 首先，稍微观察一下就会发现：最多切两刀，如下图这样对角线的切法一定能断掉所有线（任意一条黑边到其他黑边的路都被断了） 那么我们只要判断能否用一刀切断所有线。 然后需要一点脑洞: 如图将一个框从左上角切开，再将其拉值，然后便得到了一些区间，考虑这和原图有怎样的对应关系：原图中直线 a 直线 b 有交点，等价于 右图中 a 区间包含 b 的一个端点。 那就好办了，先把原图“展开”，每条线对应到一个区间，我们切的一刀也是一条直线，那问题转化为找到一个区间 包含原本 nnn 个区间各自的一个端点。 这东西可以排序后用双指针解决。右指针+1，wh ...

某联考题，长门有希的序列(nagato) Update 2021-4-23: 发现原题，[THUSC2015]平方运算 跳过废话 题目背景都是废话 「他一见钟情的对象,并不是我。」 语调平稳得像是在念论文。 「他看到的我并不是我,而是资讯统合思念体。」 我静静聆听。长门又以同样的语调继续说明。 「只是他不晓得他看到的是什么。毕竟人类只是有机生命体,在意识层面上和资讯统合思念体是 天差地远。恐怕他看到的是那超越时空的智慧与日积月累的知识吧。尽管他透过终端机读取到的资讯 仅有九牛一毛,但那资讯带来的压力已足以令他为之倾倒。」 所以他才会会错意…吗?我看着长门参差不齐的刘海,叹了一口气。中河感受到的长门内在, 事实上只是资讯统合思念体的某一端。虽然我不是很清楚,但是长门的确实拥有人类无法比拟的庞大 历史、知识量等奇妙的力量。一不小心误闯进去的中河,为何会茫然自失一点也不足为奇了。 … 「我还是有点好奇,你到底是怎么消除他拥有的能力的呢? 」 尽管清楚那是人类所无法理解的知识,我仍然不自量力地提问。也许我也像中河那样抓狂了吧。 「那并不复杂,我可以告诉你,也许你可以理解。」 你是认真的?我有 ...

「牛客」神J上树 题意简述 给一棵 nnn 个点的树，每条边有边权 wiw_iwi​，定义 dis(u,v)dis(u,v)dis(u,v) 为 uuu 到 vvv 简单路的长度。神J可以在树上移动，且每次只能从一个节点 uuu 跳向其子孙节点 vvv ，且代价为 u×dis(u,v)u\times dis(u,v)u×dis(u,v) 。给出 mmm 个询问，问是否能从 sss 跳到 ttt ，若能，求最小代价。 n,m≤3×105,1≤wi≤107n,m\le 3\times 10^5,1\le w_i\le 10^7n,m≤3×105,1≤wi​≤107 题解 判断 sss 是不是 ttt 的祖先，用dfn序即可。 再观察以下，显然最小代价是要每一个点跳到第一个比它小的点，最后再一步跳到 ttt 。 我们不妨先考虑在序列上怎么做： 处理每个点后第一个比它小的点可以用单调栈扫一遍，然后这东西可以倍增，预处理出从某个点跳 2j2^j2j 到达点及这一段的代价。 在查答案时从 sss 开始跳，跳到不越过 ttt 的最后的 uuu ，再手动计算 uuu 到 ttt 的代价即可。 现在是 ...

「牛客」排列计数机 题意 定义一个长为 kkk 的序列 A1,A2,…,AkA_1,A_2,\dots,A_kA1​,A2​,…,Ak​ 的权值为：对于所有 1≤i≤k1\le i\le k1≤i≤k，max⁡(A1,A2,…,Ai)\max(A_1,A_2,\dots,A_i)max(A1​,A2​,…,Ai​) 有多少种不同的取值。 给出一个 111 到 nnn 的排列 B1,B2,…,BnB_1,B_2,\dots,B_nB1​,B2​,…,Bn​，求 BBB 的所有非空子序列的权值的 mmm 次方之和。 答案对 109+710^9+7109+7 取模。 数据范围: 1≤n≤105,1≤m≤20,1\le n \le 10^5 ,1\le m \le 20,1≤n≤105,1≤m≤20, 保证 BBB 是 111 到 nnn 的排列。 题解 这种序列上的问题多是DP。 暴力DP 首先先考虑一个比较暴力的DP fv,jf_{v,j}fv,j​ 表示最大值为 vvv ，序列的权值为 jjj 的方案数。按顺序枚举 iii ： fAi,j=∑k∈[1,Ai−1]fk,j−1,j∈[2 ...