Little_sk

2022 CCPC 绵阳站 E题 （图上DP，根号分治）题意有一个由$n$城市组成的国家，城市之间由一条权值为$w$的边连接，共m条这样的边，并且保证整个国家是连通的。每个城市中有$a_i$ 个居民。 在接下来的q天，每天都会有一个城市遭受灾难$b_1,b_2,…,b_q$，你必须将该城市的所有人都转移到其它城市才能避免居民受到灾难，转移一个居民到相邻城市的代价为两个城市之间路径的权值w。 请问你最少需要多少代价才能让所有居民都安全度过q天的灾难。 思路我们不必管每个城市中有多少个人，我们只需要求出每个城市中转移一个人的最小代价，在最终计算总代价时再乘上人数即可。很容易想到一个暴力的DP解法如下： 令$f(i,j)$ 表示在第$j$号点，第$i$天后所有的操作中最小的代价。那么有$f(i,j) = MIN{(v,w) \in edge{b_i}}{w+f(i+1,v)}$ 。 我们发现每天只会更新一个dp值，于是我们可以直接省去f的第一维，然后倒序枚举天数 $i $ 从$q$到$1$ 。 总的时间复杂度为$O(\sum_{i=1}^q deg(b_i)$...

刚学python，还是免不了C++的代码风格。 Love Story12345678910111213def solve(): str = input() ans = 0 for i in range(10): if(str[i] != std[i]): ans +=1 print(ans)###########t = int(input())std = "codeforces"for i in range(t): solve() Blank Space1234567891011121314#pythont = int(input())for i in range(t): n = int(input()) a = map(int,input().split()) temp = 0 ans = -1 for j in a: if j == 0: temp+=1 else: temp =...

Dashboard - Codeforces Round 899 (Div. 2) - Codeforces C. Card Game题意有n张卡牌，每张卡牌上有一个整数（可能是负数），按顺序盖好， 你可以选择任意次如下操作，使得你最终的得分最多： 选择一个奇数 $i$ ,将第 $i$ 个数从牌堆中取出，然后获得这张牌上对应的分数 选择一个偶数 $i$ ,将第i个数从牌堆中丢弃，不获得对应分数 问进行若干次操作后（可以为0次） 最多可以获得多少分数。 思路由于牌上的数可以是负数，所以我们要尽量多的选择正数，然后尽量少地选择负数。 我们可以把连续的一段负数（或者连续的一段正数） 称为 负数串（正数串）对于任意一个长度大于等于2的负数串，我们可以通过不断舍弃偶数，使得最终这个串只剩下一个或零个负数对于任意一个长度大于等于2的正数串，我们可以通过不断选取奇数，来让这个串最终只剩一个或零个整数 这样化简到最后，一定会是 负正负正... 的串 因此我们只需要考虑负数在奇数，正数在偶数的情况：这时候我们就需要选择两种情况中的较优解：1. 选取负数，然后选取后面跟着的正数。...

Educational Codeforces Round 155 (Rated for Div. 2) D. Sum of XOR Functions题意给出一个数列： $a1,a_2,…,a_n$ ，求$\sum {l=1}^{n} \sum {r=l}^{n}f(l,r) \cdot (r - l + 1)$,其中 $f(l,r) = a_l \oplus a{l+1} \oplus … \oplus a_r$ 答案对$998244353$取模. （$n \le 3\cdot 10 ^ 5$） 思路我们如果暴力枚举，我们的复杂度就太高了（纯暴力$O(n^3)$ ,即使使用前缀来优化区间异或的操作，也需要 $O(n^2)$）。 因此我们需要考虑异或操作的特殊性。我们可以将a按每个二进制位差分，这样就得到了一个二维数组（设为v），数组的长度是数列中的数的个数，宽度是一个数的二进制位数。 例如样例 $1，3，2$ 对应的v数组为: V数组 1 3 2 $(a_i >> 1) \& 1$ 0 1 1 $(a_i >> 0)...

CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) （2023年9月18日晚） C. Colorful Table题意给出n个数$a1 ,a_2,…,a_n$ ，以及一个数k，所有数满足 $1\le a_i \le k$ ,数组b是一个nxn的二维数组，其中 $b{i,j} = min(a_i,a_j)$ ,对于每一个数 $1 \le x \le k$ ，求出面积最小的矩阵，使得矩阵中涵盖了b数组中的所有的$x$，输出矩阵的两边之和（例如矩阵为3x3就输出6（6=3+3），矩阵为2x5就输出7（7=2+5））。 思路例如a数组为（k = 4）： 1 2 3 4 1 那么b数组为： $b[i,j]$ $a_1 = 1$ $a_2 = 2$ $a_3 = 3$ $a_4 = 4$ $a_5 = 1$ $a_1 = 1$ 1 1 1 1 1 $a_2 = 2$ 1 2 2 2 1 $a_3 = 3$ 1 2 3 3 1 $a_4 = 4$ 1 2 3 4 1 $a_5 =...

The 2023 ICPC Asia Regionals Online Contest (1)，不要选时光机，用签到送的金币就可以练习 G Spanning Tree题意起初树只有n个节点，没有边，按照如下操作进行n-1次，对于第i次操作，选择$a_i,b_i$ ,从$a_i$ 所在的块中随机选出一个节点$u_i$，从$b_i$ 所在的块中随机选出一个节点$v_i$， 连接$u_i,v_i$保证最终会形成一个树，求构造出的这个树和给出的标准的树T能够完全相同的期望（对 998244353取模） 保证第$i$次操作前,$a_i,b_i$ 不在同一个块。 定义一个节点v所在的块即v能到达的所有节点的集合（包括v本身） 请注意，所求的期望可能是0。 思路可以得出，最终期望一定是0或者 $\frac{1}{s}$ ： 每次连接两个块时，最多只有一种连接方式能够使得所连边的情况和最终的树匹配。而本次操作会使得操作前的期望$s_{i-1}$ 再乘上 $\frac{1}{sz_a*sz_b}$ ($sz_a,sz_b$表示a和b当前所在块的节点数量)。 ...

数论博弈论：sg函数定义NIM博弈： 给定n堆物品，第$i$堆物品有$A_i$ 个，两名玩家轮流行动，每次任选一堆，取出任意多个物品，取走最后一件物品者胜利。 当且仅当 $A_1 xorA_2xor…xorA_n$时，NIM博弈先手必胜。 公平组合游戏ICG：（NIM就是经典的公平组合游戏） 1.由两名玩家交替行动2.在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关3.不能行动的玩家判负 有向图游戏： 给定一个有向无环图，途中有唯一的起点，在起点放一枚棋子。两名玩家交替把这个棋子沿边移动，无法移动者判负。 公平组合游戏都可以转化为有向图游戏。 SG函数： 在有向图游戏中，对于节点x，设从节点x出发分别到达了$y_1,y_2,…,y_k$ ，定义$sg(x)$: $sg(x) = mex({ sg(y_1),sg(y_2),…,sg(y_k)})$ 。（mex(s)表示不属于集合s的最小非负整数） 对于整个有向图G，$sg(G) = sg(s)$ 对于多个有向图游戏$G_1,G_2,…,G_m$的和G$SG(G) =...

Dashboard - Codeforces Round 897 (Div. 2) - Codeforces A - green_gold_dog, array and permutation题意有一个长度为n的数组a，请你找出一个长度为n的排列b。 根据数组a和b来构造出数组c。$c[i] = a[i] - b[i]$ ，尽可能地使c数组中的 互不相同的数的数量。 思路好妙的思路！ 让最小的$a[i]$ 减去n,次小的减去$n-1$ ,这样每个$c[i]$ 都不一样。 代码1234567891011121314151617181920212223242526272829303132333435#include<iostream>#include<set>#include<vector>#include<algorithm>using namespace std;const int N = 4e4 + 5;pair<int,int> a[N];pair<int,int> b[N];int...

牛客小白月赛76 https://ac.nowcoder.com/acm/contest/60393 F. Kevin的矩阵1.题意给出n个数字的数字序列组成一个矩阵，m表示矩阵初始的列数，这n个数从左至右从上至下排列在矩阵中。要求进行若干次操作，使得矩阵的某一列的值全部为k可以执行的操作有:1.将矩阵的列数加1或者减12.改变矩阵中某个数的值一共有t组数据，并且保证所有数据中的n的和小于2e5 2.思路不论数据怎样，每组样例中所进行的操作数都不多于2 次操作1.初始的列数m小于 ,那么可以花费至多 – m次 操作将列数变为 ，然后花费至多 + 1 次操作改变某一列上面的值来保证这一列的值全部为k。假设m为最糟糕的情况，即m = 1，那么总共最多需要 2 次操作。2.初始的列数m大于 那么直接将某一列中的所有不为k的数都变为k。最多花费 次操作表示即可符合要求，因为m 所以，所以总操作数永远小于 2 因此可以只对列数 [m – ,...

0. 杂类cin/cout提速使用ios::sync_with_stdio(false);加速输入输出速度 <<的优先级运算符<<和>> 的优先级比表达式中有的运算符要高，有时候要加上括号 1cout<<(a<b)<<endl; 字符函数库cctype判断一个字符ch是什么类型的： 1234isalpha(ch);//字母isdight(ch);//数字isspace(ch);//空白（不止是空格）ispunct(ch);//标点 比直接判断ASCII码更加容易使用（有的字符格式没有用ASCII码存就只能这么判断） 文件输入输出IO包含库文件fstream后可以进行文件的读写 创建ofstream对象和ifstream对象来分别对文件进行写和读用法和cout...