- 博客(646)
- 收藏
- 关注
RSS订阅原创 Codeforces Round #532 (Div. 2) （A，B，C，D，E，F）
A. Roman and Browsern个数只有（1/-1），你可以选择一个位置b，然后把所有c位置的数删除，c=b+i*k ( i 可以为任意整数)，求的最大值思路直接暴力枚举b然后搞一遍就OK#include <bits/stdc++.h>using namespace std;const int MAXN = 1e5 + 5;int n, k, a[M...
2019-03-27 17:07:26
503
原创 Educational Codeforces Round 62 (Rated for Div. 2) (A,B,C,D,E)
A. Detective Book题意有一本侦探小说共n页，每一页都会有一个问题，第 i 页的答案在第 a[i] 页。有个人再看这本书，他读书有个习惯，必须把所有的问题都找到答案，问他几天能看完这本书？题解定义MAX为前缀的最大值，统计有几个位置MAX = a[i] 即可。#include<bits/stdc++.h>using namespace std;c...
2019-03-25 17:13:41
435
原创 牛客网 ~ 2018年湘潭大学程序设计竞赛G ~ 又见斐波那契 （矩阵快速幂）
题意思路显然就是矩阵快速幂，我们只需要构造6*6的矩阵使得F[i−1]+f[i−2]+i3+i2+i+1F[i-1] + f[i-2] + i^3 + i^2 + i + 1F[i−1]+f[i−2]+i3+i2+i+1 乘一次可以转移到F[i]+f[i−1]+(i+1)3+(i+1)2+(i+1)+1F[i] + f[i-1] + (i+1)^3 + (i+1)^2 + (i+1) + ...
2019-03-07 15:51:27
462
原创 UVA ~ 712 ~ S-Trees（二叉树，二进制枚举）
题意给出一棵满二叉树，每一层用一个xix_ixi的01变量来表示，xix_ixi取0往左走，取1往右走。每个叶子结点有一个值（0或1），然后有一些询问，求每个询问到达的叶子结点的值。多组测试数据，以n=0表示结束，每组先输入n表示有n层，然后输入从根到叶子每一层对应x几x_几x几那个变量，然后输入叶子结点对应的值。接下来输入Q次询问，每次询问输入一个长度为n的01串表示x1−&...
2019-01-06 21:33:31
496
原创 UVA ~ 673 ~ Parentheses Balance （栈，括号配对）
题意给定一串由()和[]组成的字符串。如果我们规定以下的字符串是合法的字符串：(1) 空串是合法的字符串(2) 如果A、B都是合法的，那么AB也是合法的字符串。(3) 如果A是合法的，那么(A)和[A]都是合法的字符串。也就是说，所有左右括号必须配对，且不能“切开括号”（如“[(])”或“([)]”）是不匹配的。思路直接拿栈模拟就OK，左括号入栈，右括号判断与栈顶是否匹配，匹配完最...
2019-01-06 16:51:08
452
原创 HDU ~ 6273 ~ Master of GCD （差分数组 + 快速幂）
题意T组测试数据，每组给出一个N和M，N表示有一个长度为N初始值全为1的序列，现在有M次操作，每次把[L,R]区间乘上x（x只可能是2或者3），问最终整个序列的最大公约数是多少？题目PDF地址思路答案就是：22出现最小次数∗33出现的最小次数2^{2出现最小次数}* 3^{3出现的最小次数}22出现最小次数∗33出现的最小次数。解释一下，第一个数被乘了2次2，4次3，第二个数被乘了3次...
2018-12-25 20:44:17
497
原创 POJ ~ 3263 ~ Tallest Cow（差分数组）
题意有N头牛，最高的是第i头，身高是H，现在有R组相对关系。每组相对关系有两个数A和B，表示A和B能相互看见，也就是他们中间的牛都比他俩低。输出所有牛的最大的可能身高。思路我们只要找到每个牛最大可能是第几高的就OK。A和B可以相互看见，其实就是[A+1,B-1]区间的牛都比他俩低，也就是我们把这个区间的值都 -1即可。很明显是在修改完之后在查询，直接用差分数组就OK。==坑点：==相...
2018-12-25 20:14:45
370
原创 GYM ~ 101775J ~ Straight Master（思维，差分数组）
题意T组测试数据，每次给你一个长度为N的序列，每次可以选择一个长度3,4,5的区间将这个区间内的数都减一，问能否经过若干次操作后使得数组全变为0？思路首先将数组进行差分获得差分数组diff（diff[i]=a[i]-a[i-1]）。diff[i]为+++就相当于以 i 为起点的区间有diff[i]个。diff[i]为−-−就相当于以 i 为终点的区间有diff[i]个。对于区间长度如何...
2018-12-25 19:41:21
323
原创 洛谷 ~ P3948 ~ 数据结构 （差分数组）
思路直接差分数组搞一搞就OK了。因为前面的查询和修改掺杂在一起的询问很少，所以对于那些询问我们暴力去查询就OK。在final询问之前求一个符合要求的前缀和就可以O(1)输出了。#include <bits/stdc++.h>using namespace std;const int MAXN = 8e4 + 5;typedef long long LL;int n, opt...
2018-12-24 14:52:29
362
原创 洛谷 ~ P1083 ~ 借教室 （差分数组 + 二分）
思路很容易想到暴力的写法，对于一个订单来说，直接从第一天到最后一天都减去d[i]即可，每个订单复杂度为O(n)，总的复杂度为O(n*m)明显超时。可以发现如果前x个订单不符合要求，那么往后一定不符合，这个性质使得我们可以使用二分来求答案。我们每次二分一个答案，对于当前答案x，我们需要判断前x个订单是否可以符合要求。如果每一个订单都去暴力去减的话，那么依旧会超时。对于区间减法的操作很容易想...
2018-12-21 21:35:03
352
原创 HDU ~ 1556 ~ Color the ball （差分数组）
思路差分数组模板题。学习链接#include <bits/stdc++.h>using namespace std;const int MAXN = 1e5 + 5;int n, a[MAXN];int main(){ while (~scanf("%d", &n) && n) { memset(a, 0, si...
2018-12-21 20:21:52
242
原创 洛谷 ~ P2458 [SDOI2006] ~ 保安站岗（树形DP，最小支配集变形）
注意他看守的是通道端点（即树中的点）思路看起来很像是最小点覆盖或最小支配集。但是最小点覆盖是去覆盖边的；最小支配集，一个点只可以被支配集中的一个点支配。而本题，需要支配点，但是一个点可以被多个点去支配，所以本题是最小支配集的一个变形。dp[u][0/1/2]dp[u][0/1/2]dp[u][0/1/2]表示以u为根的子树上的点全部被控制的答案。dp[u][0]dp[u][0]dp[u...
2018-12-21 19:18:23
359
原创 UVA ~ 1218 ~ Perfect Service （树形dp，最小支配集）
题意补充本题是多组输入输出，每组先输入N，然后输入N-1条边，然后在输入一个flag，flag=-1表示结束。dp[u][2]=min(dp[u][2],dp[u][1]−dp[v][2]+dp[v][0]);dp[u][2] = min(dp[u][2], dp[u][1] - dp[v][2] + dp[v][0]);dp[u][2]=min(dp[u][2],dp[u][1]−dp...
2018-12-18 19:09:33
255
原创 UVA ~ 1292 ~ Strategic game （树的最小点覆盖）
题意对于图G=(V,E)来说，最小点覆盖指的是从V中取尽量少的点组成一个集合，使得E中所有的边都与取出来的点相连。也就是说，设V‘是图G的一个顶点覆盖，则对于图中的任意一条边(u,v)，要么u属于集合V’，要么v属于集合V‘。在V‘中除去任何元素后V’不在是顶点覆盖。输入有多组数据，每组先输入N，表示N个结点（0~n-1），然后N行输入这个N个结点的信息，每行第一个数字表示第i个结点的编...
2018-12-14 15:29:24
256
原创 洛谷 ~ P2014 ~ 选课 （树形背包）
思路树形背包的模板题。加一个虚拟的0结点然后选m+1个科目就OK。sz[u]sz[u]sz[u]表示以uuu为根的这棵子树的节点数目dp[u][j]dp[u][j]dp[u][j]表示uuu以uuu为根节点的子树，选取jjj门课且必须选自己的最优解。dp[u][j]=max(dp[u][j−k]+dp[v][k])，(j:min(m,sz[u])−&gt;2)(k:1−&...
2018-12-14 13:34:06
533
原创 HDU ~ 4745 ~ Two Rabbits （区间DP，环形序列的最长回文子序列）
题意有两只兔子和一个N块石头组成的环，他们在这个环跳，A顺时针跳，B逆时针跳，有一个要求他们两个每时每刻必须站在相同质量的石头上，跳过的石头不能再跳，两个人的起点任意（可以相同），求两只兔子步数之和的最大值？思路问题就相当于：环形序列的最长回文子序列。环形序列，其实我们把原串往后复制一段就OK了。dp[i][j]dp[i][j]dp[i][j]表示[i,j][i,j][i,j]区间的最优...
2018-12-13 15:47:48
349
原创 HDU ~ 4632 ~ Palindrome subsequence（区间DP，容斥，回文子序列个数）
题意T组测试数据，每组给你一个序列，问这个序列有多少个回文子序列，mod104+7mod\quad 10^4+7mod104+7思路dp[i][j]dp[i][j]dp[i][j]表示[i,j][i,j][i,j]区间有多少个回文子序列①s[i]!=s[j]s[i]!=s[j]s[i]!=s[j]，通过容斥可得dp[i][j]=dp[i+1][j]+dp[i][j−1]−dp[i+1][...
2018-12-12 21:21:59
270
原创 POJ ~ 3280 ~ Cheapest Palindrome（区间DP，变为回文子序列最小代价）
题意给你长度为N一个字符串，和M个字符，对于每个字符有两种操作：增加或删除，各有一个权值，问将这个串变为一个回文串的最小花费是多少？思路dp[i][j]dp[i][j]dp[i][j]表示将[i,j][i,j][i,j]区间变为回文串的最小花费那么状态转移很容易想到:①如果s[i]==s[j]s[i]==s[j]s[i]==s[j]，那么dp[i][j]=dp[i+1][j−1]dp[...
2018-12-12 20:29:47
293
原创 Codeforces ~ 1083A ~ The Fair Nut and the Best Path（树形DP，树的直径）
题意先输入N表示一棵有N个结点的树，然后输入N个点的点权，然后输入M条边。要求一条链，使得链上的∑\sum∑点权和-∑\sum∑边权和最大，输出这个最大值。思路显然是树的直径？dp[u]表示当前到u的最长链，那么ans=max(dp[u]+dp[e.v]−e.w)ans = max(dp[u]+dp[e.v]-e.w)ans=max(dp[u]+dp[e.v]−e.w)，dp[u]=m...
2018-12-12 18:07:19
570
原创 HDU ~ 2476 ~ String painter（区间DP，好题）
题意现在有两个字符串A，B，现在有一种操作是可以将A的某一段全变为同一个字符，问将A变成B最少需要多少次操作？思路可以发现是区间DP，如果考虑直接将A变为B，A和B有的字符相同有的不同不太好DP。我们可以分两步来，先计算出来把一个空串刷成B的花费，然后在计算把A变为B的花费就比较好计算了首先看第一步：定义dp[i][j]dp[i][j]dp[i][j]为把[i,j][i,j][i,j...
2018-12-11 19:40:44
429
原创 HDU ~ 4283 ~ You Are the One （区间DP）
题意T组测试数据，每组输入N，表示有N个人要上台表演，然后输入这N个人的不开心度。如果第i个人第k个上台表演，那么他的不开心度就是d[i]*(k-1)。现在有一个狭窄的小黑屋，导演可以暂时让人先进入小黑屋中，然后让后面的人去舞台表演，因为小黑屋很狭窄所以最先进去的人最后才能出来，问怎么安排才能使所有人的不开心度最小，输出这个不开心度。思路dp[i][j]dp[i][j]dp[i][j]表示...
2018-12-10 21:51:34
243
原创 POJ ~ 1657 ~ Distance on Chessboard（思维 or 搜索）
思路x = 横坐标之差 y = 纵坐标之差王：其实就是max(x, y)，这个也是切比雪夫距离后：在横竖斜三条线上为1，否则为2车：在横竖两条线上为1，否则为2象：同在白格子或黑格子即可到达，在同一条斜线上为1，否则为2判断是否在一条斜线上其实也就是x是否等于y白色格子和黑色格子（横坐标+纵坐标）奇偶性一定不同，同颜色的格子x-y一定为偶数。//#include <bit...
2018-12-10 21:30:22
329
原创 ZOJ ~ 3469 ~ Food Delivery （区间DP）
题意一个人要送外卖，现在，在X轴上有N个人，先输入n，x，v，表示n个人，骑手一开始在x位置，他的速度是v，然后N行输入X[i]和B[i]表示这个人在x[i]位置，每分钟的等待都会增加b[i]的愤怒度，想要更多的回头客，所以骑手需要安排一个送外卖的方案使得所有人总的愤怒度最小，输出这个愤怒度。思路首先对于每个人我们肯定要按坐标位置排个序，我们把骑手也当做一个点放进去。dp[i][j][0...
2018-12-09 22:03:46
229
原创 POJ ~ 1651 ~ Multiplication Puzzle（区间DP）
题意多组测试数据，每组输入一个长度为n的数组，每次可以挑选一个值，然后获得该值乘以左右两边的分数，不可以挑选两端，求只剩下左右两端的最小分数。思路最优矩阵链乘的变形。dp[i][j]dp[i][j]dp[i][j]表示[i,j][i,j][i,j]区间的最小分数dp[i][j]=min(dp[i][k]+dp[k][j]+a[i]∗a[k]∗a[j])(i&amp;lt;k&amp;l...
2018-12-09 19:01:34
217
原创 ZOJ ~ 2433 ~ Highways（水）
题意T组测试数据，每组先输入n，表示n个城市之间有一条单向的高速路，然后输入n-1个数字，表示1到[2,n]的路程。现在要新建两条反向的高速路，使得新建的路程最短，并且保证可以从任意城市到达任意城市，且一个城市不能建两个高速站。输出新建的路程和S1，E1，S2，E2。每组数据后面输出一个换行。思路很容易想到就是两条路是（i，1)和(n，i-1），那么答案就是总路程+a[i]-a[i-1]...
2018-12-09 18:41:35
181
原创 Codeforces ~ 1088D ~ Ehab and another another xor problem （交互题，位运算）
题意现在有两个数字a，b（a,b&amp;lt;230a,b&amp;lt;2^{30}a,b&lt;230）每次可以给出两个数字c，d，询问a⊕c和b⊕d的关系。询问次数不能超过62次。询问结束后输出a，b的值。思路考虑a和b在二进制下的情况，从高位到低位依次求出a和b的每一位。对于当前位我们询问cura⊕(1&lt;&lt;i)，curb和cura，curb⊕(1&lt;&lt;i
2018-12-05 13:01:29
414
原创 Codeforces ~ 1088C ~ Ehab and a 2-operation task （思维，构造）
题意一个长度为n的序列，你有两种操作：①将前i个数字加上一个值，②将前i个数字取余一个值。让你通过不超过n+1次操作，将序列变为递增的。思路可以想到构造成0，1，2，3，4…n-1这种形式。这个n+1给的很玄。从后往前，通过n次加操作，把a[i]加到a[i]%n=i，最后所有数对n取余即可。#include&lt;bits/stdc++.h&gt;using namespace st...
2018-12-05 11:44:24
313
原创 Codeforces ~ 1088B ~ Ehab and subtraction （set，模拟）
题意给你一个长度为n序列，让你重复m次以下操作：选出序列中最小的正（&amp;gt;0）整数，输出这个数字，所有数字减去这个数，全为0就输出0。思路通过手推第一个样例发现每次减去的值是两个不同的数的差值，所以直接放入set，每次输出当前值减去上一个值即可。#include&amp;lt;bits/stdc++.h&amp;gt;using namespace std;int n, k;set&amp;lt;int...
2018-12-05 11:37:31
403
原创 Codeforces ~ 1088A ~ Ehab and another construction problem （暴力）
题意给你一个x，让你求得一组a和b，满足a∗b&gt;x,a/b&lt;x,a%b=0a*b&gt;x,a/b&lt;x,a\%b=0a∗b>x,a/b<x,a%b=0，输出一组合法的a和b，如果没有输出-1.思路n2n^2n2暴力，或者O(1)。输出n-n%2和2.#include<bits/stdc++.h>using nam...
2018-12-05 11:32:51
540
原创 Codeforces ~ 1082G ~ Petya and Graph （最大权闭合子图）
题意N个点M条边，每个点有一个点权，每条边有一个边权。要求选出一个子图，使得边权和-点权和最大。选这条边就必须选这条边的两个端点。思路其实就是边为正权值的点，点就是负权值的点，这样就是最大权闭合图的问题了。源点s为0，汇点t为n+m+1，边成为的点编号为[1,m]，原来的点编号为[m+1,m+n]。建图如下：①s向[1,m]建边，容量为该边的边权②[m+1,m+n]向汇点建边，容量...
2018-12-04 21:28:38
386
原创 Codeforces ~ 1082D ~ Maximum Diameter Graph （构造，树）
题意N个点，给定每个点的最大值，要求构造一棵树，使得直径最长。思路首先度数超过2的都是直径上的点，剩下的度为1的点往上面挂即可，注意先在第一个和最后一个挂上一个。什么时候是NO呢，除了根节点和叶子结点，每个点度数至少为2，叶子最少为1个。那么度数和最小为2*n-2。#include<bits/stdc++.h>using namespace std;const int...
2018-12-04 21:01:46
239
原创 Codeforces ~ 1082C ~ Multi-Subject Competition （vector，暴力）
题意n个人m个学科，然后n行每行输入s，r，表示这个人专攻方向为s，能力值为r。现在要选出一些人参加竞赛，任意选几个学科，但是要求每个学科选的人数必须相等，求所有人能力和的最大值。思路用vector存一下每个学科有哪些能力，从大到小排序，求个前缀和。ans[j]表示选j个人的时候的答案，遍历一下所有数据，维护一下即可。最终ans中最大值就是答案。#include&lt;bits/...
2018-12-04 20:52:35
211
原创 Codeforces ~ 1082B ~ Vova and Trophies （模拟）
题意给你一个只有‘G’和‘S’的字符串，可以交换两个字符的位置，问可以使得只有G的子段的最大长度是多少？思路模拟就行，但是情况比较麻烦。我们可以把每两个SS之间的G的长度存下来，并且统计一下非0段的个数。然后相邻两段相加，再加是否可替换，求一个MAX即可。#include <bits/stdc++.h>using namespace std;const int MAXN ...
2018-12-04 20:22:46
284
原创 Codeforces ~ 1082A ~ Vasya and Book （水）
题意T组测试数据，每次输入n，x，y，d表示这本书有n页，你要从x页翻到y页，你每次只可以往前或往后严格的翻d页，不会超过最后一页和第一页。输入最少需要翻多少次？翻不到输出-1.思路考虑三种情况即可。①直接翻到②翻到第一页然后翻到y③翻到最后一页然后翻到y#include<bits/stdc++.h>using namespace std;const int INF = ...
2018-12-04 20:10:35
281
原创 牛客练习赛32 ~ D ~ Where are you（kruskal + 边双联通）
题目链接思路kruskal过程，我们按边权排序，然后依次加入，同时用并查集维护连通性。本题难以处理的其实是边权相同的边，我们把这些边一起考虑。假设此时最小生成树的这个森林中，我们把在一棵树（一个集合）看作一个点，以这些边权相同的边（如果这条边不太同一棵树中）建立新图，可以证明桥边一定必选。#include &lt;bits/stdc++.h&gt;using namespace s...
2018-12-03 18:58:35
245
原创 HDU ~ 4612 ~ Warm up（边双联通缩点 + 树的直径）
题意N个点M条边的图，问如果加一条边， 最少可以剩下多少个桥？思路边双联通缩点以后形成一棵的树，所有树边均为桥。环上的边显然不是桥，所以我们使得最长的一条链称为环，也就是直径。那么答案就是：原来的桥数 - 直径坑点是：有重边！！！重边自然不算是桥了。#include <bits/stdc++.h>using namespace std;const int MAXN ...
2018-12-03 18:25:36
182
原创 POJ ~ 3013 ~ Big Christmas Tree （最短路径树，思维）
题意T组测试数据，每组先输入n，m表示有一个n个点m条边的无向图，然后输入n个点的点权，然后输入m条边（u，v，w），求一棵以1为根节点的数使得该树花费最小，输出最小花费，如果无法构建成一棵树输出“No Answer”。树的花费为：∑\sum∑（边权*子树的点权和）思路通过推样例可以发现每个点的点权需要乘以这个点到根结点的所有边的边权，所以可以得到∑\sum∑边权*子树的点权和 = ∑...
2018-11-20 18:41:48
247
原创 POJ ~ 3498 ~ March of the Penguins（最大流，结点容量）
题意T组测试数据，每组先输入N，d，表示有N块浮冰。然后输入N行表式N块浮冰的信息编号为0~(N-1)，(x[i]，y[i]，n[i]，m[i])表示第 i 块浮冰在(x[i]，y[i])位置，上面有n[i]只企鹅，m[i]表示这块浮冰最多允许跳跃m[i]只企鹅从这里离开。每块浮冰都可以承载无穷的企鹅，问哪几块浮冰可以使全部企鹅都可以到达，输出这几块浮冰的编号，否则输出-1.思路其实就是...
2018-11-20 18:00:08
665
原创 HDU ~ 2732 ~ Leapin' Lizards（最大流，结点容量）
题意T组测试数据，每组测试数据输入n，d，表示有两个n行的矩阵，保证列数相等但是没有输入是多少列。第一个矩阵，每个点有一根柱子，每个柱子的高度&lt;10。第二个矩阵，‘L’表示该点有一只蜥蜴，‘.’表示啥也没有。由于作用力与反作用力的原因，柱子上每当有一只蜥蜴跳过柱子高度就会减少1，柱子高度为0时不能再有蜥蜴跳过。蜥蜴跳跃距离为d，行数之差+列数之差距离不超过d即可进行跳跃。思路...
2018-11-20 14:21:30
212
原创 Codeforces ~ 1062C ~ Math（贪心，前缀和，快速幂）
题意给你一个长度为n的01串，q次询问，每次询问[l,r]区间可以获得的最大值为多少，取模1e9+7。假定答案为ans，ans初始为0。你每次选择01串中的某个元素将其吃掉，ans加上这个元素的值，并将其他元素都加上这个元素的值。比如第一个样例的第一次询问，串的变化过程如下：“1011”，“x122”，“x34x”，“x7xx”，“xxxx”,ans = 1+2+4+7思路容易发...
2018-11-19 20:06:45
844
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人