2 Helium_wild

尚未进行身份认证

暂无相关简介

等级
TA的排名 2w+

HDU3091 (2n个分成n对使得结果最小 n小于等于10 状压dp 根据题目特性减少状态)

题目转自#include<bits/stdc++.h>typedef long long ll;using namespace std;const int N=21;struct node{int x,y;double d;}p[N],st;double dis[N][N],dp[1<<N];inline double get_dis(node A,no...

2020-02-24 09:22:02

HDU4628 Pieces(n小于等于16的串 最少分成几个回文子序列)

题目思路: 先求出所有的回文串。if(!(i&该回文串)) dp[i|回文串]=min(dp[i|回文串],dp[i]+1).#include<bits/stdc++.h>using namespace std;const int N=17;char s[N];int n;int st[1<<N],tmp[N],dp[1<<N];in...

2020-02-23 15:02:20

HDU1074 Doing Homework(写作业的顺序改变使失分最少 基础状压dp+记录路径)

题目#include<bits/stdc++.h>#define low(x) ((x)&(-x))using namespace std;const int N=16,INF=0x3f3f3f3f;char s[N][105];int d[N],c[N],sum[1<<N];int bin[1<<N],dp[1<<N],now...

2020-02-23 12:11:25

HDU4049 Tourism Planning(状压dp 一个状态的所有子集)

题目题意: 有n人,m个景点,每个景点有一个花费,每个人对每个景点有一个喜爱值,若去某个景点则每个人的bonus为对该景点的喜爱值减去该景点的花费,若两个人同时到某个景点则总bonus加上一个额外值,两两到同一点的额外值通过一个n*n的矩阵表示,每个人可以在中途离开,一旦离开不得再回来,现在旅行路线已经确定,求怎样计划每个人的去留使得总的bonus最大,输出最大bonus,若最大bonus小于等...

2020-02-23 11:08:00

HDU1358 Period(字符串s的每个前缀是否为周期串 若是输出最大周期)

题目设前缀长度为len,若len%(len-该前缀子串的最长公共前后缀)==0.则证明该前缀是周期串,最大的周期为 len/(len-该前缀子串的最长公共前后缀)。 kmp中 nex数组可用来解决这个问题。证明的话 首先证明 若可以整除,则一定为周期串。再证明 若不可以整除要想为周期串的话,那么最长公共前后缀一定比nex[len]大,反之证明不整除一定不为周期串。最大周期是 len/(...

2020-02-11 20:57:55

HDU1711 Number Sequence(kmp板子 输出t串在s串出现的第一个位置)

题目#include<bits/stdc++.h>using namespace std;const int N=1e6+5,M=1e4+5;int s1[N],s2[N],nex[N],n,m;void get_nex(){ int i=0,k=-1;nex[0]=-1; while(i<m){ if(k==-1||s2[i]==s2...

2020-02-11 20:11:50

cf1263E(可修改判断括号是否为合法序列以及最大嵌套深度 线段树维护最大/小前缀和)

题目题意给你一段序列,其中L代表左移,R代表右移,小写字母代表在当前位置放置对应字母,),(代表在当前位置放置左右括号,当括号可以匹配时输出括号的最大层数,否则输出-1题解题解: sum==0&&mi[1]=0 为合法括号序列,mx[1]为括号嵌套最大深度。线段树维护最大前缀和 最小前缀和 详情见代码中update函数。#include<bits/stdc++.h&...

2020-01-28 12:09:35

cf1168A. Increasing by Modulo(每次选择若干数进行(ai+1)%m,问使数组非递增的最小操作次数 二分+贪心 哭)

题目啊啊啊啊啊啊啊啊啊啊啊啊啊学习链接:https://www.cnblogs.com/Carered/p/10937082.html题意: 给一个数组,数组中元素范围为0~n,每次你可以选择若干元素进行(ai+1)%m的操作,问使数组呈非递增的最小操作次数。思路:因为每次都可以选若干个元素,用贪心思想,假设要操作x次,第一个元素加上x若能超过m,则对m取模最小值为0,令其等于0就好了,...

2020-01-20 22:44:38

cf1168B. Good Triple(挺好的一道题!!思维灵活的不像尺取sl=smid=sr)

题目按正常的尺取就不会做。哭了。对于右端点取r找到一个l。 符合要求以r为右端点的点对有l个。对于右端点r+1。l 应该从之前的l+1开始遍历。假如以r为右端点的时候没有s[l]==s[r]==s[(l+r)/2]的点对,那么符合要求以r为右端点的点对个数为之前的p。这是最靠右的p.代码很好懂。#include<bits/stdc++.h>using namespace ...

2020-01-20 20:52:56

cf1172B. Nauuo and Circle(全排列在圆上画边不相交的生成树 的种数)

题目#include<bits/stdc++.h>using namespace std;const int N=2e5+5,mod=998244353;typedef long long ll;int deg[N];int main(){ int n;scanf("%d",&n); ll ans=1; for(int i=1,x,y;i...

2020-01-20 18:19:40

cf1175D. Array Splitting(将数组分成k部分 所有数的值*他所在的第几个部分 和最大 拆式子)

题目我就是个弱智。哭了。唉。怎么就是想不到拆开式子呢? 拆开之后很简单。sum=s[r1]*1+(s[r2]-s[r1])*2+(s[r3]-s[r2])*3+....+(s[rk-1]-s[rk-2])*(k-1)+(s[n]-s[rk-1])*k;把括号打开sum=k*s[n]-s[r1]-s[r2]-...s[rk-1];为了使sum尽可能大就选前k-1个前缀和即可 那么就对前...

2020-01-20 17:36:15

cf1176D. Recover it!(给个2n序列打乱顺序找到长为n的原序列)

题目答案难道不是唯一的吗? 我觉着是唯一的代码第20行: 先从大到小,合数不能由合数变成,假如可以变成的话这个合数就不会剩余,遍历到比他大的那个可变成他的合数的时候–vis[它]了。代码第21行: 经过上一行的处理,剩下的数都是质数了。#include<bits/stdc++.h>#define m(a,b) memset(a,b,sizeof a)using nam...

2020-01-20 15:27:39

cf1176E. Cover it!(将连通图选出不超过一半的点 使剩点与已选某或多个相邻 生成树奇偶层)

题目题意: 给你一张n个点m条边的连通图,无自环和重边。输出k和k个点的编号。 k<=[n/2]。使得没被选的点一定会和这k个点里至少一个有边相连。思路: 直接将图生成一棵树,第一种涂色方法是将奇数层全涂色,若这种方法涂色节点数大于⌊n/2⌋,那么将偶数层全涂色肯定可行。#include<bits/stdc++.h>#define m(a,b) memset(a,b,s...

2020-01-20 13:08:23

cf1189A. Keanu Reeves(一个01串最少分割成多少串 使得每个串01数量不同)

题目题意: 一个01串最少分割成多少串 使得每个串01数量不同。思路: 要么不分割,要么分割成两个串。。#include<bits/stdc++.h>using namespace std;const int N=100+5;char s[N];int main(){ int n;scanf("%d%s",&n,s+1); int num0=...

2020-01-19 21:39:01

cf1202B. You Are Given a Decimal String...(求出所有的x-y型 对于s串需要添加多少字符可被该计算器打印 巧妙地最短路暴力)

题目#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=10+5,M=2e6+5,INF=2e7;int dis[N][N];char s[M];int len;inline ll cal(int x,int y){ for(int i=0;i<10;++...

2020-01-19 16:55:52

cf1204C. Anna, Svyatoslav and Maps(给一段邻间皆连边的路径,可删多少点使得最短路径不变)

题目题意: 给一段abcdefab…路径,保证相邻的两个点一定有直接边相连。问你可以最多删掉多少点,使得 给定路径也可以作为 要想经过删后的所有点的最短路径。思路: abcde 假如dis(a,b)+dis(b,c)=dis(a,c)。d这个点一定要删掉。因为此时ac之间经过d也是最短的。假如dis(a,c)+dis(c,d)>dis(a,d). c这个点一定要删掉。。显而易见。哦对刚...

2020-01-19 16:01:08

cf1196D2. RGB Substring (至少修改多少字符才有一个长为k的RGB循环串 简单地推但我不会)

题目题意: 给你一个长度为n的只有R G B的字符串和k。问最少修改多少次,可以得到一个长度为k的RGB循环串。RGB循环串是RGBRGBRGB任意摘取的子串。思路:dp[i][0]分别表示从1-i为RGBRGBRGBR。。。这样的循环。dp[i][1]分别表示从1-i为GBRGBRGBRG。。。这样的循环。dp[i][0]分别表示从1-i为BRGBRGBRGB。。。这样的循环。那么...

2020-01-18 22:20:59

codeforces1184C2. Heidi and the Turing Test (Medium) (坐标系旋转+固定长宽的矩阵最多覆盖多少点)

题目题意: 给n个点和半径r,请问半径为r的图形最多覆盖多少点。这里是指欧几里得距离。#include<bits/stdc++.h>using namespace std;const int N=6e5+5;struct node{int x,y1,y2,o;}a[N];inline int cmp(node A,node B){return (A.x==B.x)?(A...

2020-01-18 17:01:47

HDU5091 Beam Cannon(给定长宽的矩阵最多覆盖几个点 模板)

题目题意:有N个点,有一个W*H的矩形,这个矩形和x,y轴平行,问你怎么放置这个矩形,能让矩形里的点最多。思路: 把每个原点(x,y)对应再来个映点(x+w,y),这样就有2N个点。这N个原点每次在区间【y,y+h】加1,而N个映点在区间【y,y+h】减1。就保证当前线段树里的所有的点都是横坐标位于最早的那个x往右w之内,代表这个矩阵的左下角的纵坐标是[y,y+h]此时可另当前点合法。解释不清...

2020-01-18 15:57:54

poj3678 Katu Puzzle(2-sat 裸题 tarjan判断是否可行)

题目题意: 给你n个数和m组关系。 u v d XOR 意思是u^v=d。问是否可行。主要就是 u uu必须选u的时候应该 add(uu,u).#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=1e4+5,M=3e6+5;str...

2019-11-12 14:05:24

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。