4 张松超

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 6k+

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

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

牛客网 ~ 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

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

UVA ~ 673 ~ Parentheses Balance (栈,括号配对)

题意给定一串由()和[]组成的字符串。如果我们规定以下的字符串是合法的字符串:(1) 空串是合法的字符串(2) 如果A、B都是合法的,那么AB也是合法的字符串。(3) 如果A是合法的,那么(A)和[A]都是合法的字符串。也就是说,所有左右括号必须配对,且不能“切开括号”(如“[(])”或“([)]”)是不匹配的。思路直接拿栈模拟就OK,左括号入栈,右括号判断与栈顶是否匹配,匹配完最...

2019-01-06 16:51:08

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

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

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

洛谷 ~ 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

洛谷 ~ P1083 ~ 借教室 (差分数组 + 二分)

思路很容易想到暴力的写法,对于一个订单来说,直接从第一天到最后一天都减去d[i]即可,每个订单复杂度为O(n),总的复杂度为O(n*m)明显超时。可以发现如果前x个订单不符合要求,那么往后一定不符合,这个性质使得我们可以使用二分来求答案。我们每次二分一个答案,对于当前答案x,我们需要判断前x个订单是否可以符合要求。如果每一个订单都去暴力去减的话,那么依旧会超时。对于区间减法的操作很容易想...

2018-12-21 21:35:03

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

洛谷 ~ 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

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

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

洛谷 ~ 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])−>2)(k:1−&...

2018-12-14 13:34:06

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

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

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

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

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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得