- 博客(332)
- 收藏
- 关注
RSS订阅
原创 STL容器用法总结
vector 向量、pair、string 字符串、stack 栈、queue 队列、deque 双向队列、priority_queue 优先队列（堆）、set/multiset/unordered_set、map/multimap/unordered_map
2020-05-11 20:53:54
955
1
原创 2021 ICPC上海 I.Steadily Growing Steam（dp）
题目描述题目链接题目大意给定n张牌，每张牌有ti与一个si。你至多可选m张牌，将其ti翻倍。在翻倍结束后，从n张牌中找出若干数量的牌，将其分为两组，两组的ti之和相等。求出此时的最大的si之和。题目分析代码如下...
2021-12-06 14:01:59
1901
原创 2021 ICPC上海 K.Circle of Life（构造）
题目描述题目链接题目分析构造题难就难在能不能想到一种符合题目要求的构造方法，想到ac，想不到白给。构造题难就难在能不能想到一种符合题目要求的构造方法，想到ac，想不到白给。构造题难就难在能不能想到一种符合题目要求的构造方法，想到ac，想不到白给。本题的构造字符串为0110011001（01后面接10，10后面接01即可）本题的构造字符串为0110011001（01后面接10，10后面接01即可）本题的构造字符串为0110011001（01后面接10，10后面接01即可）这样字符串只要2秒即可恢复原
2021-12-06 13:19:11
1683
原创 2021 ICPC上海 H.Life is a Game（Kruskal重构树）
题目描述题目链接题目大意给你一个图，图上有点权和边权。以及q个查询：每个查询给你一个初始位置x和初始能量k。你每到一个新点上即可获得该点的能量（即点权），但是如果想通过一条边，你的能量总数需要大于边权。问：可以获取的最大能量数题目分析代码如下...
2021-12-04 17:39:52
1173
原创 2021 ICPC上海 G.Edge Groups（树形dp）
题目描述题目链接题目大意给出一个点数为n的树（n为奇数），将n-1条边两两分组。每组内需要满足：有两条边，且这两条边要有一个公共点。题目分析代码如下#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#include <set>#include <map>#include <
2021-12-03 20:56:06
895
原创 2021 ICPC沈阳 L.Perfect Matchings（树形dp+容斥原理）
题目描述题目链接题目大意给你一个2n个点的完全图，从这个图里面删除2n−1条边，这些边形成一颗树，问剩下的图里面点进行完美匹配有多少种方案？题目分析代码如下
2021-12-01 18:59:39
1767
1
原创 2021 ICPC沈阳 M.String Problem（思维）
题目描述题目链接题目大意给你一个字符串，求这个字符串的所有前缀字符串中的最大字典序子串。题目分析这个题的思路非常的简单。这个题的思路非常的简单。这个题的思路非常的简单。首先我们可以发现：对于一个字符串，其字典序最大的子串，这个子串的结尾一定是整个字符串的结尾。首先我们可以发现：对于一个字符串，其字典序最大的子串，这个子串的结尾一定是整个字符串的结尾。首先我们可以发现：对于一个字符串，其字典序最大的子串，这个子串的结尾一定是整个字符串的结尾。证明（反证法）：假设字符串范围是[1,n]，其字典序最
2021-11-30 20:45:18
1737
原创 2021 ICPC沈阳 H.Line Graph Matching（并查集+贪心）
题目描述题目链接题目大意懒得写翻译了。题目分析首先，本题要求的是图L(G)的最大独立边集。我们要再给它翻译回图G，L(G)的最大独立边集回到图G上，首先，本题要求的是图L(G)的最大独立边集。我们要再给它翻译回图G，L(G)的最大独立边集回到图G上，首先，本题要求的是图L(G)的最大独立边集。我们要再给它翻译回图G，L(G)的最大独立边集回到图G上，即为：求G上相连的边对的集合的最大值。（相连的边对意为两条边之间至少存在一个公共点的边对，例即为：求G上相连的边对的集合的最大值。（相连的边对意为两条
2021-11-30 16:12:10
1384
2
原创 P1058 [NOIP2008 普及组] 立体图（模拟）
题目描述题目链接题目分析这道题就是乍一看特别唬人，但其实并没有那么难（我一开始就被唬住了）。只要按照顺序从后往前，从左到右，从下到上的顺序依次放入每个立方体即可。本题的难点在于计算出放入的某个立方体对应的二维坐标。代码如下#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#include <set&
2021-11-30 09:21:08
1097
原创 2021 ICPC沈阳 J.Luggage Lock（bfs，模拟）
题目描述题目链接题目分析这是一道很明显的bfs+模拟的题（和八数码是一类题）这是一道很明显的bfs+模拟的题（和八数码是一类题）这是一道很明显的bfs+模拟的题（和八数码是一类题）因为起点和终点都不一样，还有1e5个测试样例。因此不能直接对每一组样例都做一遍bfs，肯定会超时。因为起点和终点都不一样，还有1e5个测试样例。因此不能直接对每一组样例都做一遍bfs，肯定会超时。因为起点和终点都不一样，还有1e5个测试样例。因此不能直接对每一组样例都做一遍bfs，肯定会超时。因此我们可以将所有测试样例的
2021-11-28 20:47:07
808
原创 2021 ICPC沈阳 B.Bitwise Exclusive-OR Sequence（位运算+图论）
题目描述题目链接题目大意有n个点和m个约束，每个约束包含三个数u，v，w，表示a[u]^a[v]=w.求满足m个约束 并且 和最小的序列的和。题目分析这很明显是一个图论问题，对于每个约束u−v−w，我们可以在u和v之间连一条权值为w的边。这很明显是一个图论问题，对于每个约束u-v-w，我们可以在u和v之间连一条权值为w的边。这很明显是一个图论问题，对于每个约束u−v−w，我们可以在u和v之间连一条权值为w的边。因为题目对于约束并没有太多的限制。因此这个图是可能存在环和不连通的。因为题目对于约束
2021-11-28 15:24:52
721
原创 #757 (Div. 2) D. Divan and Kostomuksha（约数+dp）
题目描述This is the hard version of the problem. The only difference is maximum value of ai.Once in Kostomuksha Divan found an array a consisting of positive integers. Now he wants to reorder the elements of a to maximize the value of the following function
2021-11-27 16:47:12
594
原创 #757 (Div. 2) C. Divan and bitwise operations（组合数字+位运算）
题目描述Once Divan analyzed a sequence a1,a2,…,an consisting of n non-negative integers as follows. He considered each non-empty subsequence of the sequence a, computed the bitwise XOR of its elements and added up all the XORs, obtaining the coziness of the
2021-11-27 12:42:09
395
原创 icpc区域赛（济南）总结
这场比赛就很离谱，一题能拿铜，两题能拿银，四题金。题目基本上没有区分度（除了签到都很难）。开局我们的分配是我读题，并记录每道题的算法类型；cdx找一道能做的先做着；lcy跟榜出签到。开局lcy成功的出了签到题（树上的概率dp），不过因为没看清题目的精度要求wa了一发（伏笔1），然后去想d。cdx想了一段时间的c题，发现一时半会做不出来，就来帮我们看了d，用三分套三分出了，不过因为用的cin输入被卡了一发（伏笔2）。当时根据榜单，出的最多的题目是C和J，J是一道线性代数题，我们三个人线性代数都忘干净了，谁都
2021-11-16 12:07:06
1133
原创 P3605 [USACO17JAN]Promotion Counting P（树状数组）
题目描述题目链接题目分析代码如下#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#include <set>#include <map>#include <queue>#include <vector>#include <algorithm>
2021-11-12 13:27:46
461
原创 P5584 【SWTR-01】Sunny‘s Crystals（贪心线段树）
题目描述题目链接题目分析代码如下#include <iostream>#include <cstdio>#include <cmath>#include <string>#include <cstring>#include <set>#include <map>#include <queue>#include <vector>#include <algorithm>
2021-11-12 10:07:21
416
原创 P3522 [POI2011]TEM-Temperature（单调队列）
题目描述某国进行了连续 n( 1≤n≤1,000,000）天的温度测量，测量存在误差，测量结果是第 ii 天温度在 [li,ri] 范围内。求最长的连续的一段，满足该段内可能温度不降。输入格式In the first line of the standard input there is one integer n n ( 1 \le n \le 1,000,000 1≤n≤1,000,000) that denotes the number of days for which Byteasa
2021-11-11 21:47:00
484
2
原创 P2859 [USACO06FEB]Stall Reservations S（区间问题，堆）
题目描述约翰的N(l<N< 50000)头奶牛实在是太难伺候了，她们甚至有自己独特的产奶时段.当 然对于某一头奶牛，她每天的产奶时段是固定的，为时间段A到B包括时间段A和时间段B.显然，约翰必须开发一个调控系统来决定每头奶牛应该被安排到哪个牛棚去挤 奶，因为奶牛们显然不希望在挤奶时被其它奶牛看见.约翰希望你帮他计算一下：如果要满足奶牛们的要求，并且每天每头奶牛都要被挤过奶，至少需要多少牛棚 •每头牛应该在哪个牛棚被挤奶。如果有多种答案，你只需任意一种即可。输入格式Line 1: A
2021-11-09 23:08:34
151
原创 P2061 [USACO07OPEN]City Horizon S（区间问题，线段树 / 堆）
题目描述Farmer John has taken his cows on a trip to the city! As the sun sets, the cows gaze at the city horizon and observe the beautiful silhouettes formed by the rectangular buildings.The entire horizon is represented by a number line with N (1 ≤ N ≤ 40,
2021-11-08 23:54:47
216
原创 AtCoder Beginner Contest 225 English D - Play Train（双链表）
题目描述题目链接题目大意有n个点，每个点的编号为i。有3种，一共m个操作：1）将y连到x的后面（保证x后面和y前面没有连点）2）将x-y的连接断开（保证一定存在x-y的连接）3）输出x所在的链（按顺序输出）题目分析设pre[x] //记录x的前驱节点，ne[x] //记录x的后继节点这样我们连接/断开边时都只需要操作pre[]和ne[]数组即可。输出x所在的链也只需要顺着链表往前和往后遍历即可。代码如下#include <iostream>#include <cs
2021-11-02 16:31:11
206
原创 #722 (Div. 1) B. Kavi on Pairing Duty（DP）
题目描述Kavi has 2n points lying on the OX axis, i-th of which is located at x=i.Kavi considers all ways to split these 2n points into n pairs. Among those, he is interested in good pairings, which are defined as follows:Consider n segments with ends at th
2021-10-26 23:24:53
399
原创 1310. 数三角形（组合数学）
题目描述给定一个 n×m 的网格，请计算三点都在格点上的三角形共有多少个。下图为 4×4 的网格上的一个三角形。注意：三角形的三点不能共线。输入格式输入一行，包含两个空格分隔的正整数 m 和 n。输出格式输出一个正整数，为所求三角形数量。数据范围1≤m,n≤1000输入样例2 2输出样例76题目分析我们直接算组成三角形的数量并不好算，因此我们可以反过来，先算出所有的选择，再减去其中不合法的方案即可。我们直接算组成三角形的数量并不好算，因此我们可以反过来，先
2021-10-16 18:18:44
607
原创 1309. 车的放置（组合数学）
题目描述有下面这样的一个网格棋盘，a,b,c,d 表示了对应边长度，也就是对应格子数。当 a=b=c=d=2 时，对应下面这样一个棋盘：要在这个棋盘上放 k 个相互不攻击的车，也就是这 k 个车没有两个车在同一行，也没有两个车在同一列，问有多少种方案。只需要输出答案 mod100003 后的结果。输入格式共一行，五个非负整数 a,b,c,d,k。输出格式包括一个正整数，为答案 mod100003 后的结果。数据范围0≤a,b,c,d,k≤1000，保证至少有一种可行方
2021-10-15 23:43:13
336
原创 最幸运的数字（同余方乘）
题目描述8 是中国的幸运数字，如果一个数字的每一位都由 8 构成则该数字被称作是幸运数字。现在给定一个正整数 L，请问至少多少个 8 连在一起组成的正整数（即最小幸运数字）是 L 的倍数。输入格式输入包含多组测试用例。每组测试用例占一行，包含一个整数 L。当输入用例 L=0 时，表示输入终止，该用例无需处理。输出格式每组测试用例输出结果占一行。结果为 Case i:+一个整数 N，N 代表满足条件的最小幸运数字的位数。如果满足条件的幸运数字不存在，则 N=0。数据范围1
2021-10-15 09:48:30
346
原创 樱花（约数之和）
题目描述给定一个整数 n，求有多少正整数数对 (x,y) 满足 1/x+1/y=1/n!。输入格式一个整数 n。输出格式一个整数，表示满足条件的数对数量。答案对 109+7 取模。数据范围1≤n≤106输入样例2输出样例3样例解释共有三个数对 (x,y) 满足条件，分别是 (3,6),(4,4),(6,3)。题目分析这道题看上去好像没有什么，代码如下#include <iostream>#include <cstdio>
2021-09-27 12:54:29
161
原创 质数距离（筛素数）
题目描述给定两个整数 L 和 U，你需要在闭区间 [L,U] 内找到距离最接近的两个相邻质数 C1 和 C2（即 C2−C1 是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。同时，你还需要找到距离最远的两个相邻质数 D1 和 D2（即 D1−D2 是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。输入格式每行输入两个整数 L 和 U，其中 L 和 U 的差值不会超过 106。输出格式对于每个 L 和 U，输出一个结果，结果占一行。结果包括距离最近的相邻质数对和距
2021-09-26 21:36:38
453
原创 2020 ICPC济南 J.Tree Constructer（构造）
题目描述题目链接题目大意有一颗含有n个点的树，每个点都有一个权值w[i]。如果u与v之间连有一条边，当且仅当w[u] or w[v]=260-1。给出这棵树的所有边，要求构造出每个点合法的权值。题目分析n的范围是100，因此暴力构造的话，260肯定是不够用的。我们可以用二分法给这颗树染色（其实就是给树的每一层染上一个不同的颜色）,这样就可以把所有点分为两组。这样我们就可以将其分开处理：取点数较少的那一组，将每个点加一个id值，然后除了最高位和第id位外，其余位全部取为1。另一组根据其临边来
2021-09-24 19:41:14
216
原创 9.21训练后的一些感想
今天我们打了一次模拟赛，2019icpc上海的题目。这次的情况也还是不太好，我和lcy两个人只出了2个题，离目标还是很远（如果要想在比赛中拿银，我和lcy至少要达到铜牌的水平才行）。不过一个好消息是这次的f题是一个铜牌的数据结构题（树链剖分），而我离做出这道题就只差了一个结论（如何用线段树维护序列n次方的和，其它所所有的部分我都是会的）。我认为，一道题目做不出来可以分为三种情况：1、这道题所需要的所有知识点我全部都会，但是因为对于知识点的应用组合不熟练，因此在做这道题时想不出来。我认为这种情况的表现就是
2021-09-21 23:43:41
90
原创 暑期训练总结
从暑假开始，我也cdx、lcy组队，准备一起努力训练，为了冲击icpc银牌而努力。最开始我们的训练还是很努力的，前期以做多校为主，此外还有补题和根据比赛刷相关的算法题。我们的策略是这样决定的：我和lcy先去做出那些相对比较简单的题目，cdx去看难一些的题目。他有了思路之后再给我们每人讲一个题，最后我们三人每人做一道难题，如果三个人都能把自己负责的题目做出来，那么至少就是一个银牌甚至是金牌；如果有两个人能做出自己负责的题目，那么就是银或者铜……不过这个策略在多校中并没有发挥出特别好的作用，大部分情况都是我们三
2021-09-20 11:13:48
101
原创 2021 icpc网络赛总结
今天我们打了icpc的网络赛，出了6个题，成绩还算可以，至少是达到了预期的目标。但是问题还是有不少的，如果配合好的话完全是有可能出七个题的（c题没出完全是因为时间不够了）。就直接说一下这次比赛出现的问题吧：一开始比赛我和队友在两个签到题上卡了半天，我做的I题，一道非常简单的签到题，但我硬是调了很长时间（我用字符串处理的输入，后来改成while(cin>>)输入过的，网上说这题的数据有脏空格，我？？？）。前面的签到题就耽误了不少的时间，也加了不少的罚时。解决完了签到题我们又遇到了第二个坎：读题。
2021-09-19 21:16:54
2428
原创 P2216 [HAOI2007] 理想的正方形（单调队列）
题目描述有一个a * b的整数组成的矩阵，现请你从中找出一个n * n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。输入格式第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。输出格式仅一个整数，为ab矩阵中所有“nn正方形区域中的最大整数和最小整数的差值”的最小值。样例输入 #1 复制5 4 21 2 5 60 17 16 016 17 2 12 10 2 11 2 2
2021-08-25 09:34:34
222
原创 2021牛客多校9 E.Eyjafjalla（dfs序+主席树）
题目描述There are n cities in the volcano country, numbered from 1 to n. The city 1 is the capital of the country, called Eyjafjalla. A large volcano is located in the capital, so the temperature there is quite high. The temperature of city i is denoted by t
2021-08-16 11:04:32
158
原创 2021牛客多校8 D.OR（位运算）
题目描述There are two sequences of length n−1, b=(b2,b3,……,bn), c=(c2,c3,……,cn). Here, each bi,ci is a non-negative integer.Now, the sequence a=(a1,a2,……,an)，considers beautiful if and only if forall i (2≤i≤n), bi = a[i-1] | a[i] , ci=a[i-1]+a[i] and each a
2021-08-09 22:13:52
130
原创 牛客多校2021 F.xay loves trees（树状数组+树上的滑动窗口）
题目描述You have two trees rooted at 1 that both have n nodes. You need to find the largest subset of {1,2,⋯,n} such that:On the first tree, the set is connected, and for any two points u, v in set, one of u or v is an ancestor of the other.On the second
2021-08-08 18:19:53
310
原创 #736 (Div. 2) C. Web of Lies（图论）
题目描述There are n nobles, numbered from 1 to n. Noble i has a power of i. There are also m “friendships”. A friendship between nobles a and b is always mutual.A noble is defined to be vulnerable if both of the following conditions are satisfied:the noble
2021-08-02 10:22:08
160
原创 Educational Codeforces Round 112 (Rated for Div. 2) B. Two Tables
题目描述You have an axis-aligned rectangle room with width W and height H, so the lower left corner is in point (0,0) and the upper right corner is in (W,H).There is a rectangular table standing in this room. The sides of the table are parallel to the walls
2021-07-31 11:09:27
121
原创 7.22训练日记
最近这两天做了一下今年的沈阳icpc的题目，难度还是比较大的，做起来很困难，一道题得弄很长时间。现在算是正式开始训练了，剩下的时间已经不多了，现在要开始努力训练了。最近又重新分了队，和cdx、lcy一队了，我还是负责数据结构和字符串这两部分，但是我这两部分的训练量明显还是不够多的（已经挺长一段时间没有做这方面的题了，现在做思维题做的比较多），最近正好趁着假期，赶紧多刷些题目。...
2021-07-22 21:15:40
99
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人