- 博客(103)
- 收藏
- 关注
RSS订阅
翻译 ACM比赛题解模板
Problem A题意：题解：C++版本一Problem B题意：题解：C++版本一Problem C题意：题解：C++版本一Problem D题意：题解：C++版本一Problem E题意：题解：C++版本一Problem F题意：题解：C++版本一Problem G题意：题解：C++版本一Problem H题意：题解：C++版本一...
2019-05-06 12:07:19
319
原创 Go语言学习笔记
Go学习笔记Go学习笔记Go学习笔记Go语言基础语法行分隔行一、变量1.1 变量的声明1.2 初始化变量1.4 多个变量同时赋值1.5 匿名变量(_)二、常量三、基本数据类型3.1 整型3.2 浮点型3.3 布尔型3.4 字符串3.4.1 字符串常见转义符3.4.2 反引号定义多行字符串3.5 字符四、数据类型的转换五 、指针5.1 认识指针地址和指针类型5.2 从指针获取指针指向的值5.3 使用指针修改值5.4 创建指针的另一种方法--new（）函数六、字符串应用6.1 计算机字符串长度 -- len(
2020-12-04 00:38:26
370
原创 书记图片js代码
<div class="head_img"><img width="160" height="160" alt="我的头像" src="http://m.5577.com/up/2019-2/15501113468430433.jpg" class="img_avatar"><div>
2019-08-14 23:54:22
179
原创 二分图匹配匈牙利算法
这篇文章讲无权二分图（unweighted bipartite graph）的最大匹配（maximum matching）和完美匹配（perfect matching），以及用于求解匹配的匈牙利算法（Hungarian Algorithm）；不讲带权二分图的最佳匹配。二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不...
2019-06-05 21:06:45
233
原创 拓扑排序例题
不懂的看这里拓扑排序以下是例题：拓扑排序·一简单拓扑判环#include<bits/stdc++.h>using namespace std;const int maxn = 1e5 + 7;vector<int> G[maxn];int inDeg[maxn];int n,m;queue<int>q;int sum;bool top(...
2019-06-05 01:40:07
1198
1
原创 拓扑排序
在一个有向图中，对所有的节点进行排序，要求没有一个节点指向它前面的节点。先统计所有节点的入度，对于入度为0的节点就可以分离出来，然后把这个节点指向的节点的入度减一。一直做改操作，直到所有的节点都被分离出来。如果最后不存在入度为0的节点，那就说明有环，不存在拓扑排序，也就是很多题目的无解的情况。下面是算法的演示过程。模板vector//重环无影响const int maxn = 1...
2019-06-05 01:25:06
297
1
原创 Codeforces Beta Round #42 (Div. 2)-C. Lucky Tickets（水，思维）
题意：找两张可以组成3的倍数的牌的方法数题解：全部对3取模，然后%3==0的两两配对，min（1,2)配对。#include<bits/stdc++.h>using namespace std;const int MAXN = 1.5e6+5;const int MAXM = 1.5e6+5;typedef long long ll;std::vector<int&...
2019-05-31 00:48:43
154
原创 B. Ternary Logic（三进制）
time limit per test 2 secondsmemory limit per test 256 megabytesinput standard inputoutput standard outputLittle Petya very much likes computers. Recently he has received a new “Ternatron IV” as a...
2019-05-31 00:35:18
421
原创 Codeforces Beta Round #69 (Div. 2 Only)
A - Panoramix’s Predictionb是否是大于a的第一个质数#include <iostream>#include <cstdio>using namespace std;bool judge(int x){ bool flag=true; for(int i=2;i*i<=x;i++) if(x%i==0...
2019-05-31 00:26:09
132
原创 Educational Codeforces Round 50 (Rated for Div. 2) B. Diagonal Walking v.2（思维）
题意：给你一个q代表q次询问，然后给出三个数n，m， k。（n，m）代表终点，k代表最多移动的步数。让你求出到达终点的过程中，走对角线的最大步数。思路：当m > k时输出-1（设m是较大的数），当m-n是奇数时有一步不能走对角线所以k–，当走对角线可以直接到达终点，如果剩余的步数是奇数则有两步不能走对角线所以k - 2。（画图观察规律）#include<bits/stdc++.h&...
2019-05-30 23:11:12
106
原创 D. Vasya and Arrays（贪心）
题意给你两个数组长度分别为n,m;有这么一种操作，用某个数组的某个子区间元素之和代替这个子区间，这样使得数组长度减少，两个数组都可以进行问你最后两个数组一摸一样的时候，最大数组长度是多少？如果无法使两个数组一摸一样输出-1分析先判断开始数组总和是否相等，不相等是不可能最后两个数组一摸一样的从头和尾两个位置判断是否相等，相等继续如果不相等统计两个数组区间的长度，在比较大小，进行到最后ps...
2019-05-30 21:27:01
352
原创 1037D - Valid BFS?（思维BFS）
有点意思题意：给了一颗n节点，n-1条边的树，进行BFS遍历，问遍历顺序是否可能是所给数组的顺序思路：先对构树的邻接表通过序列中的数的次序进行排序，再直接对树bfs，看其结果是否相同即可按照进队列的顺序排了一个序，这样就可以我们保证自己写的BFS序最可能是符合所给顺序的BFS序了。如果这样都不行，哪一定不行。感性理解感性理解。vector建图#include<bits/stdc++...
2019-05-30 18:23:31
297
原创 894C - Marco and GCD Sequence(构造gcd）
894C - Marco and GCD Sequence(构造gcd）
2019-05-30 17:29:51
391
原创 893C - Rumor（并查集）
有个散布谣言的人，要把一个谣言传给所有人，有的人是朋友，只要告诉其中一人，他的朋友就会知道，求最小花费。例如样例一，先告诉1（然后1会告诉4，4再告诉5），这样就只用再告诉2和3就行了，所以最小花费是2+5+3=10。#include<bits/stdc++.h>using namespace std;const int MAXN = 1.5e6+5;const int M...
2019-05-30 17:04:47
239
原创 Codeforces 892 B. Wrath （递推）（思维）
题意每个人都有一个长度为 li 的武器，相邻的两个人之间距离为 1 ，同一时间所有人使用武器攻击左边的人，问最后存活下来的人数。显然，最右侧的人一定是可以存活下来的。我们维护一个 cntcnt 代表右侧延伸到当前位置的武器长度，若 cnt>0说明当前位置在别人的攻击范围内，否则 ans+1 。更新 cnt为 max(cnt−1,ai)看对于 ii 来说是否可以攻击到更远的位置。时...
2019-05-30 13:33:03
253
原创 D. Maximum Distance(图论)最小生成树从（前向星写法待补）
题意：给一张图，定义一条路径的长度为这条路径上的边权最大的边的边权。定义两点间距离为这两点间路径的最小长度。给出k个特殊节点，求对于每个特殊节点，距离它最远的点到它的距离。思路：可以知道，这个距离一定出现在最小生成树上。所以先跑一遍kruskal，然后取第一个特殊节点dfs求出每个特殊节点到它的距离d[i]，所有节点的最远距离都是 max (d[i])。题解：我们可以发现答案一定是...
2019-05-30 11:35:29
285
原创 Codeforces Round #449 (Div. 2)
A - Scarborough Fair题意好理解.View Code//A. Scarborough Fair 字符更换#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>#include<iostream>using namespace...
2019-05-30 02:14:36
127
原创 (E2) Stars Drawing (Hard Edition)（dp，前缀和，覆盖）（搜索也可以）
题目大意，给你一个n×m大小的字符矩阵，仅由‘.’和‘’组成，提问这个图可否划分为一些由‘’组成的十字形状，这些十字之间可以有重叠，如果可以完全覆盖输出每个十字中心坐标与边长度，不可以输出-1。 这是一道很有意思的题，在这场比赛中上一道题是这一道题的简化版本，数据范围仅有100，所以我采用了O(n^3)的做法，即枚举每个 * ，然后向四周扩展，显然，在这道题中1000的数据范围中这种做法会...
2019-05-30 00:20:25
318
原创 CodeForces - 1082C Multi-Subject Competition (前缀和 + 思维)
题意：给定n名选手，每名选手都有唯一选择的科目si和对应的能力水平。选择时每个科目对应数量要么一致，要么不选题解：对于某一类的先排序，优先选择大的，sum[i] 表示每类选择i个，符合条件的 和 ，当然当某一类贡献为负时，就不选求sum[i] (0<=i<=m) 最大值即可#include<bits/stdc++.h>using namespace std;typ...
2019-05-29 22:52:28
222
原创 C. Colorful Bricks （组合数学/dp）
给你n个方格排成一行，有m种颜色，然后要把这n个方格分成k+1段，每段涂不同的颜色，问有多少种方法。排列组合问题，首先要在n-1个位置里面选出k个位置当作段与段的分割点，然后每段涂的时候有m*(m-1)^k种，二者相乘即使答案。要注意的是计算组合数的时候也要取mod，因为组合数的增加也是很快的。还有要上快速幂计算所以C(n-1,k)m(m-1)^k。注意取模。#include<cs...
2019-05-29 20:13:29
284
原创 CF 502 B-The Bits(找规律)
题意：两个二进制数字a,b，然后进行or运算，然后进行交换数字a，如果数字交换以后，得到的结果不相同，求数字交换以后的位置。思路：我们可以知道与运算有四种情况分别为： a=0，a=0，a=1，a=1 b=0，b=1，b=0，b=1 1 0 0 1两种情况：① 对于b二进制如果是1，a 的值对or运算以后的结果没有影响，所以...
2019-05-29 15:18:18
191
原创 1016B - Segment Occurrences(前缀和/substr预处理）
给两个字符串s，t，之后给出s的一个区间，问这个子串中存在多少个子串与t相同前缀和#include<bits/stdc++.h>using namespace std;const int MAXN = 1.5e7+5;const int MAXM = 1.5e7+5;int hay[MAXN],shay[MAXM];int main(){ int n , m ...
2019-05-29 14:03:17
157
原创 CodeForces - 1079B Personalized Cup 好题
题意：给一串字符串，让你分成x行w列（w<=20)，保证x行最小，不够，用*补,输出x w 和字符串。分析：我们首先确定行数，字符长度len，x=len/x（要向上取整），判断取*的个数，（y+len）%x==0，y=x-len%x，w=len/x，然后就是模拟分析了。然后就是分配*号，取模后 * 号的个数必然小于行数，可自行证明#include<cstdio>#in...
2019-05-29 13:29:43
265
原创 1034A - Enlarge GCD（div1）数论，线性筛的运用
题意：给出n个数字，求最少删除几个可以使剩下的数字的GCD大于n个数字的GCD。思路：求出最多的公共因子，去掉没有这个因子的数，剩下的数的GCD大于原来的GCD。题解：随便说说吧，要使GCD变大，那么尽可能使数中的互质数变少，那么问题解答变显而易见了，只要找到最多的公共因子，那么其他数没有就去掉，那么便是最大。线性筛的运用#include<bits/stdc++.h>usin...
2019-05-29 02:18:12
163
原创 1037A - Packets（二进制）
题意：给出一个数n，问最少多少个数可以组成从1到n的所有数。题解：显而易见，把问题转化成二进制问题就可以极大的解决这个问题，倍增思想，那么显然需要最多的数就是2^n-1， 问题变转换成求大于x且2^n-1需要最多的那个n即可#include<cstdio>#include<cmath>#include<iostream>using namespace ...
2019-05-28 18:02:17
224
原创 B. Reach Median（思维）
题意：给n个数字，对每个数字多次可以加1或者减1，求最少操作几次可以使得n个数字中位数是s，题目保证n为奇数。思路：将n个数字从小到大排序，如果当前中位数是s，则输出0如果当前的中位数小于s，则需要将当前位置和之后的位置小于s的数字全部变成s如果当前的中位数大于s，则需要将当前位置和之前的位置大于s的数字全部变成s#include<cstdio>#include<cs...
2019-05-27 06:38:47
216
原创 A. Benches（思维）
题意：题目大意：公园里有n个座位，一开始每个座位都有多少人（人数给出），公园里将进来m人，问这些人往座位上坐，那么座位上人数最多的那个能有多少人，最多人数最小化能有多少人？思路：最大的肯定好求，最小的要分两类讨论；我的做法是，把所有的人数都加起来，然后除以凳子数，相当于把人数平均分到每个凳子上，如果%n有剩下的就+1，就是所求；然后就是就会有一种情况，来m之前就有一个座位上比m平分后大，那么...
2019-05-27 06:34:12
261
原创 C. Equalize（思维）
题意：两个长度为n只含有0和1的字符串a，b，求最少花费多少可以将a字符串变成b字符串有两种操作：1.将当前位置的字符取反（即0变成1,1变成0），花费12.将位置i和位置j的字符交换，花费为abs(i-j).思路：我们可以发现，位置i不相同，且位置j也不相同（j>i），如果交换后都可以对应位置与b相同，那么这两个位置有两种选择自身取反，花费2，交换位置花费j-i；所以当i,j相...
2019-05-27 06:28:41
156
原创 B. Shashlik Cooking（思维）
题意：给你一个n代表有n个初始状态为正面的羊肉串，k代表你每次可以随机选择一个数值i，并把第 i-k 到第 i+k 个羊肉串翻过来。问你最少需要多少次可以把所有羊肉串全部翻过来。解题报告：经过观察发现，当k==0时，那就需要翻n次了，当n<=(2k)+1时，肯定翻中间那个翻一次就可以啦。其他的就是观察n%(2k+1)与k的关系来确定从哪里开始翻。大于k就表示开始总中间就可以，因为到最后必然...
2019-05-27 06:21:38
336
原创 Codeforces 1038C. Gambling(贪心)（简单博弈）
题意是两个人分别有n个数，他们每次可以加上自己的一个数或者删去对方的一个数(他们刚开始都为0，A先操作)，两个人都很聪明，都想让自己所得的数最大，最后求出A-B的最大值。思路就是贪心，对于自己的最大数和对方的最大数来做比较，当自己的最大数大于对方的最大数的时候要自己先加上这个值，否则就删去对方的最大值。#include <bits/stdc++.h>#define maxn 10...
2019-05-27 06:10:29
167
原创 codeforces #519B. Lost Array（数学思维）
【描述】Bajtek有一个数组x[0],x[1],…,x[k-1]但被搞丢了，但他知道另一个n+1长的数组a，有a[0]=0，对i=1,2,…,n。由此可以找到数组x[0],x[1],…,x[k-1]的一些可能情况，即满足这个关系的数组x[0],x[1],…,x[k-1]。问一共有多少种可能的数组x[0],x[1],…,x[k-1]的长度k，输出可能的数量以及所有可能的长度k。数据范围：1&l...
2019-05-27 06:06:13
209
原创 B. Labyrinth（BFS 记忆化搜索）（双端队列）
记忆化搜索。dp[0] 向左 dp[1] 向右 dp[2] 表示这个点能够满足条件#include<iostream>#include<queue>#include<string.h>using namespace std;char map[2005][2005];int step[4][2]={{1,0},{0,1},{-1,0},{0,-1}};...
2019-05-27 06:00:29
500
原创 1082B - Vova and Trophies（思维好题）
给你一个包含GS的字符串，只允许交换一次任意不同位置的字符，问最长的连续G串是多少分析很显然贪心找相邻的中间间隔一个S的两个连续G串#include<bits/stdc++.h>using namespace std;int main(){ int n; string s; //freopen("in.txt","r",stdin); while(ci...
2019-05-27 05:56:36
200
原创 Masha and two friends（容斥+矩阵面积并）（矩形切割）
题意：题目很长，但是其实题意非常简单，首先是给定一个n*m的方格，然后黑白相间，其中左下角是白色。然后有两个人爱涂色，然后A先涂色把他所选中的地方涂成白色，然后B把他选中的地方涂成黑色。然后问最后的情况白色格子有多少，黑色格子有多少？题解：前提工作：设置一个函数，只要知道左下角的位置是黑色还是白色，然后知道这个选中的方格的大小，然后就可以算出里面的黑格和白格算出来。然后进行容斥：定义...
2019-05-26 11:55:09
297
原创 1081B - Farewell Party（思维/细节）
题意概括：有 N 个人，每个人都佩戴一顶帽子（帽子种类有 1、2、3 … N )；接下来 N 个数表示所有人里面 与 第 i 个人佩戴了不同帽子的总数。解题思路:ai 代表与自己佩戴了不同帽子的个数，那么反过来意思就是说有 N - ai个人佩戴了与自己相同帽子。如果能满足 数量为 ai 的 个数 Si == N - ai， 则说明刚好有 N-ai 个人佩戴相同帽子。如果 Si >...
2019-05-25 16:30:16
345
原创 1051A - Vasya And Password(模拟/构造）
题目大意：给出n个字符串，字符串要满足有大写字母，小写字母，数字才能构成密码，要求以最小改动把字符串变为密码字符串vector写法#include<bits/stdc++.h>using namespace std;typedef long long ll;#define pb push_backconst int maxn = 1e6 + 7;int main(){...
2019-05-25 15:43:06
259
原创 1065B - Vasya and Isolated Vertices（图论/思维）（公式）
Description求一个N个点M条边的无向图，点度为 0 的点最多和最少的数量。N≤105,M≤N×(N−1)2Solution关于最少的数量，注意到一条边会增加两个点度，所以最多能带来 2M 个点度，最少的零点度点数就是 max(N−2M,0)。关于最多的数量，要知道 N 个点的完全图边数是 N×(N−1)2 。然后就可以二分上界是什么了。可以打表递推，也可以直接利用完全图的性质...
2019-05-25 15:04:08
262
原创 A. Oh Those Palindromes（思维结论题）
题意：给一个字符串，让你重新把字符串重新排，使他从左到右把他顺便分成子串，让他可以成回文的子串最多；思路：当然是按升序排最多回文结论题。考虑个连在一起，此时有 个回文子串。再在其中插入一个其它的字符，答案一定会变小。因为此时把原串拆成了两部分。那么sort一遍就好了#include<bits/stdc++.h>using namespace std;typedef ...
2019-05-25 00:27:05
214
原创 1085C - Connect Three(思维/贪心）
题目给了三个点的坐标，问三个格子可以互相到达最少需要多少格子。首先先将3个点的坐标排序。然后模拟，从A走到B,从C走到B,把经过的点放到set里边。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 3e6 + 7;//char str[maxn][maxn];...
2019-05-25 00:12:35
289
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人