Little_sk

注意事项请注意！： 题解仅代表个人看法，不代表最优解 每道题都会附上ac代码，但是仅作参考，要看懂后再了解代码。补题不要直接抄代码！禁止自欺欺人！ 只提供题解，不提供题目信息 ac代码为C++版本，如果遇到不懂的语法请自行百度 ac代码中的循环经常用到了for(int i = 1;i<=n;i++) ，这种在for的括号中int i的操作只有大于等于C++11标准才可以使用，编译错误时请检查自己编译使用的标准。 A.数位分解对于一个数x， 使用 x % 10 (% 是取余数) ，就可以得到他的最后一位 使用 x /= 10 (除以十并取整数)，就可以舍掉他的最后一位 使用while(x) 来进行循环 1234567891011#include<iostream>using namespace std;int main(){ int x; cin>>x; while(x){ cout<< x % 10 <<" "; x = x / 10; } return...

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) ,我们发现当b_i 的度较大时，复杂度会退化到O(qn)...

刚学python，还是免不了C++的代码风格。 [Love Story](https://codeforces.com/contest/1829/problem/A)12345678910111213def 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 Space](https://codeforces.com/contest/1829/problem/B)1234567891011121314#pythont = int(input())for i in range(t): n = int(input()) a = map(int,input().split()) temp...

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

[Educational Codeforces Round 155 (Rated for Div. 2)](https://codeforces.com/contest/1879) D. Sum of XOR Functions题意给出一个数列： a_1,a_2,...,a_n ，求undefinedsum _{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 undefineda_i...

[CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)](https://codeforces.com/contest/1870) （2023年9月18日晚） C. Colorful Table题意给出n个数a_1 ,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 =...

[The 2023 ICPC Asia Regionals Online Contest (1)](https://pintia.cn/market/item/1703381331863785472)，不要选时光机，用签到送的金币就可以练习 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或者 undefinedfrac{1}{s}：...

数论博弈论：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的和GSG(G) =...

[Dashboard - Codeforces Round 897 (Div. 2) - Codeforces](https://codeforces.com/contest/1867) 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>...

牛客小白月赛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 – ,...