Ptilopsis_w's little blog

owo Description 有两组玩家进行游戏，第一组玩家有 nnn 个人，第二组玩家有 mmm 个人，两组之间玩家两两会进行比赛，一共进行 n∗mn*mn∗m 场比赛。 第一组玩家能力值为 a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1​,a2​,⋯,an​, 第二组玩家能力值为 b1,b2,⋯ ,bmb_1,b_2,\cdots,b_mb1​,b2​,⋯,bm​ ，其中能力值为 111 到 222 之间的浮点数，两个能力值为 aaa 和 bbb 的玩家进行比赛的时候，能力值为 aaa 的玩家获胜概率为 a/(a+b)a/(a+b)a/(a+b)。 请求出所有比赛结束后，第一组每个玩家获胜场次的期望。 Input 第一行两个整数 n,mn, mn,m。 接下来一行包含 nnn 个实数 a1,a2,⋯ ,ana_1, a_2, \cdots, a_na1​,a2​,⋯,an​ 。 最后一行包含 mmm 个实数 b1,b2,⋯ ,bmb_1, b_2, \cdots, b_mb1​,b2​,⋯,bm​。 输入的实数小数位数不超过 888 位。 Output 输出 nn ...

正方形 Description 给定一个 n∗mn*mn∗m 的棋盘，其中有些格子是障碍，有 qqq 次询问，每次询问给出 x1,y1,x2,y2,wx1,y1,x2,y2,wx1,y1,x2,y2,w，问能否将以 (x1,y1)(x1,y1)(x1,y1) 为右下角的边长为 www 的正方形通过平移使得右下角移动到 x2,y1x2,y1x2,y1，期间不穿过障碍且不能超出棋盘。 Input 第一行三个整数 n,m,qn,m,qn,m,q。 接下来 nnn 行，每行一个长度为 mmm 的 010101 字符串，其中第 jjj 个字符表示 (i,j)(i,j)(i,j) 是否有障碍，111 表示障碍。 接下来 qqq 行，每行五个整数 x1,y1,x2,y2,wx_1,y_1,x_2,y_2,wx1​,y1​,x2​,y2​,w。 Output 输出 qqq 行 Yes 或 No。 Hint n,m≤103,q≤105n,m \le 10^3, q \le 10^5n,m≤103,q≤105 Solution 先 O(nm)O(nm)O(nm) 处理出以每个格子为右下角能放下的最大正方形 ...

选举 Description Alice 和 Bob 要竞选魔方市市长。 有 nnn 个选民，编号为 1∼n1 \sim n1∼n，它们中有的人支持 Alice ，有的人支持 Bob ，还有的人保持中立。 现在你需要把选民分成若干个区间，每个区间的长度在 [l,r][l,r][l,r] 中。如果一个区间中支持 Alice 的人比支持 Bob 的人多，那么 Alice 得一票，一个区间中支持 Bob 的人比支持 Alice 的人多，那么 Bob 得一票。 Alice 想要赢得选举，于是它请你合理地分区间，使得它获得的票数减去 Bob 获得的票数最大。 Input 第一行三个整数 nnn, lll, rrr，第二行 nnn 个整数，每个整数为 1,01,01,0 或 −1−1−1，第 iii 个数为 111 表示它支持 Alice ，为 −1−1−1 表示它支持 Bob ，为 000 表示它保持中立。 Output 行一个整数表示 Alice 获得的票数减去 Bob 获得的票数的最大值。如果没有合法的方案输出 Impossible。 Hint 1≤n≤106,1≤l≤r≤n1 \le n ...

Infinite Operation Description 给出 nnn 和一个长度为 nnn 的数列 a1…na_{1 \dots n}a1…n​。 有 qqq 次修改，每次给出两个数 ppp、vvv，表示将 apa_pap​ 修改为 vvv。修改会改变 aaa，对以后的答案产生影响。 在每一次修改后，求出下面问题的答案： 你可以操作这个序列任意多次。下面的 aaa 与 xxx 均为实数。 每次选择两个 [1,n][1,n][1,n] 内的正整数 iii、jjj 满足 ai≤aja_i \le a_jai​≤aj​。然后选择一个 0≤x≤aj−ai20 \le x \le \frac{a_j-a_i}{2}0≤x≤2aj​−ai​​。 使 ai=ai+x,aj=aj−xa_i=a_i+x, a_j=a_j-xai​=ai​+x,aj​=aj​−x，同时得到 xxx 的分数。 求若干次操作后，你能得到的得分的最大值，在模 998244353998244353998244353 意义下的值。可以证明这个最大值是存在的且为有理数。 问题中进行的操作不会真的改变 aaa 的值，这些操作 ...

Medals Description 你有 NNN 个朋友，他们会来你家玩，第 iii 个人 1∼Ai1 \sim A_i1∼Ai​ 天来玩，然后 Ai+1∼2AiA_i+1 \sim 2A_iAi​+1∼2Ai​ 天不来，然后 2Ai+1∼3Ai22A_i+1 \sim 3A_i22Ai​+1∼3Ai​2 又会来，以此类推。 每天你会选一个来玩的人，给他颁个奖，如果没人来玩，你就不颁奖。 你要给每个人都颁 KKK 个奖，问至少需要多少天。 Input NNN KKK A1,A2,⋯ ,AnA_1, A_2, \cdots, A_nA1​,A2​,⋯,An​ Output 答案 Hint N≤18,K≤105,Ai≤105N \le 18, K \le 10^5, A_i \le 10^5N≤18,K≤105,Ai​≤105 Solution 天数的上界是 2NK2NK2NK，然后可以二分，用网络流 check，然而跑不动。 我们可以拆点看成二分图匹配问题，然后利用霍尔定理判断，进行一个超集和的统计。 #include <algorithm>#include <cst ...

啊 Description 给定一个 n×mn \times mn×m 的 010101 矩阵，求包含 [l,r][l,r][l,r] 个 111 的子矩形个数。 Input 第一行读入两个正整数 n,mn,mn,m。 接下来 nnn 行，每行一个长度为 mmm 的 010101 串，表示给定的矩阵。 接下来一行，两个自然数 l,rl,rl,r。 Output 一行一个整数表示答案。 Hint n≤30,m≤5×104n\le 30, m \le 5 \times 10^4n≤30,m≤5×104。 Solution 裸题，枚举上下边界 up,downup,downup,down ，左右边界直接用双指针算，时间复杂度 O(n2m)O(n^2m)O(n2m)。 #include <cstdio>#include <cstring>#include <iostream>using namespace std; typedef long long ll;const int N = 35;const int M = 5e4+10; int n, m, L, ...

最短子列 Description 对于一个字符串 S=S1S2…SnS=S_1S_2\dots S_nS=S1​S2​…Sn​ ，定义它的一个子序列是任意满足 1≤i1<i2<⋯<ik≤n1 \le i_1 < i_2 < \dots < i_k \le n1≤i1​<i2​<⋯<ik​≤n 的字符串 Si1Si2…SikS_{i_1}S_{i_2} \dots S_{i_k}Si1​​Si2​​…Sik​​ 。字符串 SSS 的非子序列即不是 SSS 的子序列的字符串。 对于两个字符串 S,TS,TS,T ，我们定义它们的最短公共非子序列为一个最短的字符串，使得它既是 SSS 的非子序列，也是 TTT 的非子序列。 这里 S,YS,YS,Y 仅由 000 和 111 构成。现在请你求出字典序最小的最短公共非子序列。 Input 第一行两个正整数 n,mn, mn,m ，表示两个字符串 S,TS,TS,T 的长度。 第二行一个长度为 nnn 的、仅由 0,10,10,1 组成的字符串 SSS ，表示第一个字符串。 第三行一个长度为 ...

取石子 Description 有 nnn 堆石子，第 iii 堆石子有 xix_ixi​ 个。 Alice 和 Bob 轮流取石子， Alice 先手。每人每次从一堆石子中取 a∼ba\sim ba∼b 个。无法操作的人失败。 此外，当一个人取完一堆石子时他会立即获胜。求谁会获胜。有多组数据。 Input 第一行一个整数 ttt 表示数据组数。接下来每组数据两行：第一行三个整数 n,a,bn,a,bn,a,b ，第二行 nnn 个整数 x1,x2,...,xnx_1,x_2,...,x_nx1​,x2​,...,xn​ 。 Output 每组数据输出一行一个字符串表示答案。 solution 考虑 SG 定理，先只看一堆石子的情况，石子个数为 1∼a−11 \sim a-11∼a−1 时，那么先手无法操作，后手必胜，所以 SG 值为 000，对于 a∼ba \sim ba∼b 的情况，因为这是必胜态的终止局面，所以没有 SG 值，可以看作 −1-1−1 或者 +∞+ \infin+∞ (我也不确定是不是没有 SG 值，但是这么算就是对的，我也不太会博弈论（逃)。因为每次取的石子数的限 ...

序列收益 看数据范围和取数方式知肯定是一道区间DP。 设 f(l,r)f(l,r)f(l,r) 为从区间 [l,r][l,r][l,r] 中任意取数的最大价值。 若 [l+1,r−1][l+1,r-1][l+1,r−1] 内的数都被取完，则可以同时取 l,rl, rl,r 处的数。 判断 [l+1,r−1][l+1,r-1][l+1,r−1] 是否被取完只需判断满不满足 f(l,r)=∑i=lrbif(l,r)=\sum_{i=l}^r b_if(l,r)=∑i=lr​bi​。 零一种就是套路的转移: 枚举断点，将区间分成两部分，左右分别加起来就行。 #include <climits>#include <cstdio>#include <cstring>#include <iostream>using namespace std;struct Rhine_Lab { Rhine_Lab() { freopen("clash.in", "r", stdi ...

最美森林 随便挑一个节点当根，那么所有的叶子节点的状态是已经确定的，然后又能确定倒数第二层的状态，也就是说，如果有解的话解唯一，所以我们就把每个连通块 dfs 一遍，如果一条边下面连的子树有奇数个黑点，那么这条边就一定选，否则一定不选，最后判一下选出来的方案合不合法即可。 #include <algorithm>#include <iostream>#include <string>#include <vector>using namespace std;struct Rhine_Lab { Rhine_Lab() { freopen("painting.in", "r", stdin); freopen("painting.out", "w", stdout); }};Rhine_Lab Ptilopsis_w;const int N = 1e5+10;struct edg ...