- 博客(4512)
- 收藏
- 关注
RSS订阅转载 [杂题]:staGame（博弈论+Trie树+DFS）
题目描述$pure$和$dirty$决定玩$T$局游戏。对于每一局游戏，有$n$个字符串，并且每一局游戏由$K$轮组成。具体规则如下：在每一轮游戏中，最开始有一个空串，两者轮流向串的末尾添加一个字符，并且需要保证该串为$n$个字符串中任意一个串的前缀，不能操作的人输掉这一轮，并且在下一轮游戏中由该轮输掉的人先手。另外为了遵循女士优先的原则，在每一局游戏的第一轮均由$pure$先手。玩...
2019-09-28 18:15:00
508
转载 [杂题]:group（状压DP+轮廓线）
题目描述 $pure$在玩一个战略类游戏。现在有一个士兵方阵，每行有若干士兵，每个士兵属于某个兵种。行的顺序不可改变，且每一行中士兵的顺序也不可改变。但由于每一行都有$C$个位置（$C$不小于任一行的士兵数），她能够安排每行的士兵依次站在某几个位置上。 对于每一个士兵，令其前后左右相邻四个位置上有$v$个和他种类相同的士兵，则$pure$会获得$v$的布阵分数。现在$pure$想...
2019-09-28 17:41:00
526
转载 [CSP-S模拟测试]:w（树上DP）
题目背景$\frac{1}{4}$遇到了一道水题，完全不会做，于是去请教小$D$。小$D$看了${0.607}^2$眼就切掉了这题，嘲讽了$\frac{1}{4}$一番就离开了。于是，$\frac{1}{4}$只好来问你，这道题是这样的：题目描述有一棵$n$个节点的树，每条边长度为$1$，颜色为黑或白。可以执行若干次如下操作：选择一条简单路径，反转路径上所有边的颜色。对于...
2019-09-28 15:28:00
640
转载 [CSP-S模拟测试]:v（hash表+期望DP）
题目背景 $\frac{1}{4}$遇到了一道水题，完全不会做，于是去请教小$D$。小$D$看了$0.607$眼就切掉了这题，嘲讽了$\frac{1}{4}$一番就离开了。于是，$\frac{1}{4}$只好来问你，这道题是这样的：题目描述 有$n$个球排成一行，每个球的颜色为黑或白。 执行$k$次操作，第$i(1\leqslant i\leqslant k)$次操...
2019-09-28 14:22:00
251
转载 [CSP-S模拟测试]:u（差分）
题目背景 $\frac{1}{4}$遇到了一道水题，完全不会做，于是去请教小$D$。小$D$看了一眼就切掉了这题，嘲讽了$\frac{1}{4}$一番就离开了。于是，$\frac{1}{4}$只好来问你，这道题是这样的：题目描述 考虑一个$n\times n$的矩阵$A$，初始所有元素均为$0$。 执行$q$次如下形式的操作给定$4$个整数$r,c,l,s$，对于每...
2019-09-28 13:55:00
220
转载 [CSP-S模拟测试]:序列（主席树）
题目描述小$A$把自己之前得到的序列展示给了小$B$，不过这一次，他并不要求小$B$模仿他之前的行为。他给了小$B$一些询问，每个询问都是$l\ r\ x$的形式，要求小$B$数出在序列的第$l$个到第$r$个元素中有多少是不小于$x$的。小$B$很快就算出来了。小$A$很不甘心，于是要求动态修改这个序列......这样，他只要求每次修改后求出所有询问答案的和即可。然而小$B$还是很...
2019-09-28 11:33:00
105
转载 [CSP-S模拟测试]:涂色游戏（DP+组合数+矩阵快速幂）
题目描述小$A$和小$B$在做游戏。他们找到了一个$n$行$m$列呈网格状的画板。小$A$拿出了$p$支不同颜色的画笔，开始在上面涂色。看到小$A$涂好的画板，小$B$觉得颜色太单调了，于是把画板擦干净，希望涂上使它看起来不单调的颜色（当然，每个格子里只能涂一种颜色）。小$B$想知道一共有多少种不单调的涂色方案。我们定义一个涂色方案是不单调的，当且仅当任意相邻两列都出现了至少$q$种...
2019-09-28 10:57:00
745
转载 [CSP-S模拟测试]:平均数（二分答案+归并排序）
题目描述有一天，小$A$得到了一个长度为$n$的序列。他把这个序列的所有连续子序列都列了出来，并对每一个子序列都求了其平均值，然后他把这些平均值写在纸上，并对它们进行排序，最后他报出了第$k$小的平均值。你要做的就是模仿他的过程。输入格式第一行两个整数$n,k$，意义如题中所述。第二行$n$个正整数，即为小$A$得到的序列。输出格式一行一个实数，表示第$k$小...
2019-09-27 15:15:00
477
转载 [CSP-S模拟测试]:string（文艺平衡树）
题目传送门（内部题60）输入格式第一行三个数$n,m,k$。第二行一个长度为$n$的串。接下来$m$行每行两个数$L_i$和$R_i$。输出格式一个串，表示字典序第$k$小的合法的能被填出的串。样例样例输入：12 1 4ztrs?a?isred5 7样例输出：ztrsdadisred数据范围与提示对于$10\%$的数据，保证$n...
2019-09-27 14:13:00
126
转载 [CSP-S模拟测试]:randomwalking（DP）
题目传送门（内部题59）输入格式第一行一个数$n$表示点数。第二行$n$个数$A_i$。接下来$n−1$行，每行两个数$u,v$表示$u$和$v$有边直接相连。输出格式一个数表示最小花费的起点。样例样例输入：52 2 1 2 21 22 33 44 5样例输出：3数据范围与提示对于$10\%$的数据，保证$n\leqslant ...
2019-09-27 12:10:00
125
转载 局域网聊天传送文件的即时通讯软件，飞秋(FeiQ)
飞秋官网网址一、https://proxy.mijisou.com/?mortyhash=7cecff196d930ad19f7483f94ad1a81a7a1cd4747bd2c85d2602fb43e4483f63&mortyurl=http%3A%2F%2Fwww.feiq.cn网址二、http://www.feiq18.com/转载于:https://www.c...
2019-09-27 11:42:00
472
转载 [CSP-S模拟测试]:antipalindrome（数学）
题目传送门（内部题58）输入格式第一行一个数$T$表示数据组数。接下来每行两个数$n$和$m$。输出格式$T$行，每行一个答案，对${10}^9+7$取模。样例样例输入：25 66 5样例输出：19201620数据范围与提示对于$10\%$的数据，保证$n,m\leqslant 5$。对于$30\%$的数据，保证$n,m\leq...
2019-09-26 17:43:00
144
转载 [CSP-S模拟测试]:tree（DP）
题目传送门（内部题57）输入格式第一行包含一个数：$n$表示树的节点数。接下来$n-1$行，每行包含两个数：$u,v$表示无根树的一条边。输出格式输出$n$行，第$i$行包含一个浮点数，保留三位小数，表示第$i$号点第一次访问的期望时间。样例样例输入：31 22 3样例输出：1.0002.0005.000数据范围与提示样例解释：...
2019-09-26 17:13:00
123
转载 [CSP-S模拟测试]:reverse（模拟）
题目传送门（内部题56）输入格式第一行包含一个整数：$T$，表示数据组数。接下来$T$行，每行包含两个字符串：$a\ b$。输出格式对于每组数据，如果存在$c$，输出最长的情况下字典序最大的$c$，否则输出$-1$。样例样例输入：3AB BAABA BABAB ABAA样例输出：-1ABAB数据范围与提示样例解释：对于第一组...
2019-09-25 17:42:00
122
转载 [CSP-S模拟测试]:attack（支配树+LCA+bitset）
题目传送门（内部题55）输入格式第一行，包含两个整数：$n,m,q$，表示敌军城市数、路数和情报数。接下来$m$行，每行包含两个整数：$u,v$，表示从$u$到$v$包含一条单向道路。接下来$q$行，每行包含一些整数：$k\ u_1\ u_2...u_k$，表示敌军会向$u_1...u_k$这$k$个城市派遣大军。输出格式对于每个询问，输出一行包含一个整数表示必经...
2019-09-25 16:43:00
90
转载 [杂题]:C/c（二分答案）
题目传送门（内部题54）输入格式第一行一个整数表示$n$。第二行$n$个整数表示初始序列。（这行原题没有，是我加的）接下来$2n$行每行两个整数，分别表示$X_i,Y_i$。数据保证至少存在一种方案使得游戏在$2n$轮之内完成。输出格式一个整数表示小$A$最少需要进行的轮数。样例样例输入：31 0 21 20 20 00 10 21 2样例输出...
2019-09-24 18:18:00
136
转载 [杂题]:B/b（二分答案）
题目传送门（内部题53）输入格式第二行$2$个整数表示$n,m$。接下来$m$行每行两个整数，描述一个点对$(x_i,y_i)$。输出格式一个整数，表示最短距离。样例样例输入：6 21 52 6样例输出：1数据范围与提示样例解释：最优方案是在$2$号节点和$5$号节点之间建边。数据范围：对于前$30\%$的数据：$n...
2019-09-24 15:33:00
141
转载 二维莫队（离线）
什么是莫队算法莫队算法何谓二维莫队区别与一维莫队，无非就是放在了二维上而已。适用范围同一维莫队。二维莫队的思路依然是将问题离线，将整张图（设长为$n$宽为$m$），我们分别将长和宽分成根号块，然后将其编号，对于每一组询问，我们将其一个端点按块的大小排序，另一个端点直接按大小排序，可以类比一维莫队。时间复杂度分析时间复杂度分析是我自己$Y...
2019-09-24 11:56:00
242
转载 [CSP-S模拟测试]:联盟（搜索+树的直径）
题目描述$G$国周边的$n$个小国家构成一个联盟以抵御$G$国入侵，为互相支援，他们建立了$n−1$条双向通路，使得任意两个国家可以经过通路相互到达。当一个国家受到攻击时，所有其它国家都会沿着最短路径前往这个国家进行支援，经过每条通路所需的时间均为$1$。定义一个国家的危险程度为所有国家全部赶到需要的最短时间，联盟的危险程度为所有国家的危险程度的最大值。为了降低危险程度，联盟决定断开...
2019-09-24 11:32:00
182
转载 [CSP-S模拟测试]:蔬菜（二维莫队）
题目描述 小$C$在家中开垦了一块菜地，可以抽象成一个$r\times c$大小的矩形区域，菜地的每个位置都种着一种蔬菜。秋天到了，小$C$家的菜地丰收了。 小$C$拟定了$q$种采摘蔬菜的计划，计划采摘区域是菜地的一个子矩形，你需要帮助他计算每种计划的美味度，美味度等于每种蔬菜在采摘区域出现次数的平方和。输入格式第一行三个正整数$r,c,q$。接下来$r$行每行$c...
2019-09-24 11:10:00
437
转载 [CSP-S模拟测试]:施工（DP+单调栈+前缀和）
题目描述小$Y$家门前有一条街道，街道上顺序排列着$n$幢建筑，其中左起第$i$幢建筑的高度为$h_i$。小$Y$定义街道的不美观度为所有相邻建筑高度差的绝对值之和乘上常数$c$，为了改善街道环境，政府决定进行施工，施工队会选择一些建筑并提升它们的高度，如果一幢建筑最终高度增加了$t$，则需要花费$t_2$的人力。小$Y$非常好奇，施工完成后街道的不美观度与施工队花费的人力之和最小为...
2019-09-24 10:32:00
259
转载 [CSP-S模拟测试]:画作（BFS+数学）
题目描述小$G$的喜欢作画，尤其喜欢仅使用黑白两色作画.画作可以抽象成一个$r\times c$大小的$01$矩阵。现在小$G$构思好了了他的画作，准备动笔开始作画。初始时画布是全白的，他每一次下笔可以将一个四联通的部分涂成黑色或白色。你需要告诉他，在给出的构思下，他最少需要下笔多少次才能完成画作。输入格式第一行两个正整数$r,c$。接下来$r$行，每行$c$个字符，表示...
2019-09-24 07:30:00
195
转载 [CSP-S模拟测试]:折射（DP）
题目描述 小$Y$十分喜爱光学相关的问题，一天他正在研究折射。 他在平面上放置了$n$个折射装置，希望利用这些装置画出美丽的折线。 折线将从某个装置出发，并且在经过一处装置时可以转向，若经过的装置坐标依次为$(x_1,y_1),(x_2,y_2),...(x_k,y_k)$，则必须满足： $\bullet \forall j\in (1,k],y_j<y_{j−1}$ ...
2019-09-23 21:37:00
205
转载 [CSP-S模拟测试]:养花（分块）
题目描述小$C$在家种了$n$盆花，每盆花有一个艳丽度$a_i$。在接下来的$m$天中，每天早晨他会从一段编号连续的花中选择一盆摆放在客厅，并在晚上放回。同时每天有特定的光照强度$k_i$，如果这一天里摆放在客厅的花艳丽度为$x$，则他能获得的喜悦度为$x\mod k_i$。他希望知道，每一天他能获得的最大喜悦度是多少。输入格式数据第一行包含两个正整数$n,m$。接下来一...
2019-09-23 21:16:00
292
转载 [CSP-S模拟测试]:Walk（BFS+建边）
题目描述 在比特镇一共有$n$个街区，编号依次为$1$到$n$，它们之间通过若干条单向道路连接。 比特镇的交通系统极具特色，除了$m$条单向道路之外，每个街区还有一个编码${val}_i$，不同街区可能拥有相同的编码。如果${val}_i\ and\ {val}_j={val}_j$，即$val_i$在二进制下与${val}_j$做与运算等于${val}_j$，那么也会存在一条额...
2019-09-23 21:01:00
108
转载 [CSP-S模拟测试]:Tourist Attractions（简单图论+bitset）
题目描述在美丽的比特镇一共有$n$个景区，编号依次为$1$到$n$，它们之间通过若干条双向道路连接。$Byteasar$慕名来到了比特镇旅游，不过由于昂贵的门票费，他只能负担起$4$个景区的门票费。他可以在任意景区开始游览，然后结束在任意景区。$Byteasar$的旅游习惯比较特殊，一旦他路过了一个景区，他就一定会进去参观，并且他永远不会参观同一个景区两次。所以他想知道，有多少种可行...
2019-09-23 20:08:00
239
转载 [CSP-S模拟测试]:String Master（暴力）
题目描述所谓最长公共子串，比如串$A:"abcde"$，串$B:"jcdkl"$，则它们的最长公共子串为串$"cd"$，即长度最长的字符串，且在两个串中都作为连续子串出现过。给定两个长度都为RnR的字符串，对于字符串大师的你来说，求它们的最长公共子串再简单不过了。所以现在你有$k$次修改机会，每次你可以选择其中某个串的某个位置，将其修改成任意字符。你需要合理使用这$k$次修改机会，使...
2019-09-23 19:45:00
306
转载 [CSP-S模拟测试]:字符消除2（hash+KMP）
题目背景生牛哥终于打通了“字符消除”，可是他又被它的续集难倒了。题目传送门（内部题52）输入格式第一行$n$表示数据组书。接下来每行一个字符串。（只包含大写字母）输出格式每组数据输出一个$01$串。样例样例输入：3 YDYYDY JRYJREJRYJR YDYAKYDY样例输出：010010 01001101001 010000...
2019-09-23 16:55:00
203
转载 [CSP-S模拟测试]:Endless Fantasy（DFS）
题目描述中二少年$cenbo$幻想自己统治着$Euphoric\ Field$。由此他开始了$Endless\ Fantasy$。$Euphoric\ Field$有$n$座城市，$m$个民族。这些城市之间由$n-1$条道路连接形成了以城市$1$为根的有根树。每个城市都是某一民族的聚居地，$cenbo$知道第$i$个城市的民族是$A_i$，人数是$B_i$。为了维护稳定，$cenbo...
2019-09-23 07:36:00
111
转载 [CSP-S模拟测试]:Emotional Flutter（贪心）
题目传送门（内部题51）输入格式第一行一个整数$t$表示数据组数。每组数据的第一行有三个整数$s,k,n$。第二行有$n$个整数$A_1,A_2,...,A_n$，依次表示黑白条的长度。输出格式若能通过输出$"TAK"$，否则输出$"NIE"$。样例样例输入：22 8 72 5 6 3 2 1 22 8 41 6 7 4样例输出：TAKNI...
2019-09-23 07:13:00
158
转载 [CSP-S模拟测试]:Race（数学+Trie树）
题目描述一年一度的运动会开始了。有$N$个选手参赛，第$i$个选手有一个能力值（保证$A[i]$两两不同），比赛一共进行了天。在第$j$天（$0\leqslant j\leqslant 2^{m-1}$）的比赛中，第$i$个选手的得分为$A[i]\ xor\ j$，然后从大到小排名，排名为$x$（$x$从$0$开始）的同学会获得的积分，你需要求出每个同学最后总的积分和$q[i]$模$...
2019-09-22 12:16:00
201
转载 [CSP-S模拟测试]:Read（数学）
题目描述热爱看书的你有$N$本书，第$i$本书的种类为$A[i]$。你希望每天能够看一本书，但是不希望连续两天看种类相同的书。为了达成这个条件，你需要选择一些书不看，作为一个好学生，你希望不看的书尽可能少，求最少可以有多少书不看。输入格式为了避免输入文件过大，我们采取如下方式生成$A[i]$。第一行读入两个个整数$M$，$K$。接下来一行读入$M$个整数$count[i]...
2019-09-22 12:03:00
152
转载 [CSP-S模拟测试]:Set（随机化）
题目描述你手上有$N$个非负整数，你需要在这些数中找出一个非空子集，使得它的元素之和能被$N$整除。如果有多组合法方案，输出任意一组即可。注意：请使用高效的输入输出方式避免输入输出耗时过大。输入格式第一行一个整数$N$，代表数字个数。接下来一行$N$个数，代表你手上的数。输出格式如果无解，输出$-1$。否则，第一行输出一个整数$M$，代表你选择的数的个数。接下...
2019-09-22 11:44:00
155
转载 [CSP-S模拟测试]:weight（Kruskal+树链剖分）
题目描述给你一个$n$个点$m$条边的带边权的无向图（无重边，无自环），现在对于每条边，问你这条边的权值最大可以是多大，使得这条边在无向图的所有最小生成树中？（边权都是整数）。输入格式第一行包含三个整数$n,m,a$表示点数和边数及特殊性质标记（如果$a=0$表示没有特殊性质，如果殊性质）。接下来$m$行每行包含三个整数$u,v,w$表示有一条$u$和$v$之间的边，且边...
2019-09-22 11:25:00
110
转载 [CSP-S模拟测试]:beauty（搜索）
题目描述距离产生美。一棵包含$n$个点的树，有$2k$个不同的关键点，我们现在需要将这些点两两配对，对于一种形如：$$(u_1,v_1),(u_2,v_2),...,(u_k,v_k)$$的配对方案，我们定义其美丽值为：$$beauty=\sum \limits_{i=1}^k dist(u_i,v_i)$$（其中$dist(u,v)$表示点$u$到$v$的简单路径的边数）。现在，请...
2019-09-22 11:00:00
107
转载 [CSP-S模拟测试]:kill（二分答案+贪心）
题目传送门（内部题50）输入格式第一行包含四个整数$n,m,s$，表示人数、怪物数及任务交付点的位置。第二行包含$n$个整数$p_1,p_2,...,p_n$。第三行包含$n$个整数$q_1,q_2,...,q_n$。输出格式输出一行包含一个整数$ans$，表示答案。样例样例输入：2 4 52 106 1 4 8样例输出：5数据范围...
2019-09-21 18:16:00
167
转载 [CSP-S模拟测试]:F（DP+线段树）
题目传送门（内部题49）输入格式第一行四个整数$n,q,a,b$。接下来$n$行每行一个整数$p_i$。输出格式一行一个整数表示答案。样例样例输入：10 3 3 7428样例输出：4数据范围与提示对于$30\%$的数据：$n,q\leqslant 2,000$对于所有数据：$1\leqslant n,q\leqsla...
2019-09-21 17:43:00
110
转载 [CSP-S模拟测试]:E（贪心）
题目传送门（内部题48）输入格式第一行一个整数$n$。接下来$n$行每行两个整数$x_i,y_i$。输出格式一行一个整数表示答案。样例样例输入$1$：23 72 5样例输出$1$：2样例输入$2$：55 1511 1616 342 149 17样例输出$2$：96数据范围与提示样例$1$解释：第一组球中权值为...
2019-09-21 17:10:00
116
转载 2019.9沉淀反思
浏览数学大师陶哲轩的博客时，看到他引用的这么一段话Advice is what we ask for when we already know the answer but wish we didn’t.（当我们向他人询问建议时，我们其实已经知道了答案，只是不愿相信罢了）转载于:https://www.cnblogs.com/zhangjianghao/p/11556956....
2019-09-20 14:29:00
310
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人