2 Devil Zoey

尚未进行身份认证

暂无相关简介

等级
TA的排名 14w+

HDU4576 Robot(概率dp)

HDU4576 Robot题意1到n形成一个环,机器人从一号点出发,给定每次走的长度,方向随机,问最后在某个区域内的概率是多少。思路入门级概率dp把if(dp[id][i])这段去掉就超时了,还是得剪枝一下代码#include<bits/stdc++.h>using namespace std;const int maxn=210;double dp[2][...

2019-11-04 20:51:21

2019牛客暑期多校训练营(第六场)

D Move题意要把n个物品放到k个盒子里,每个物品都有一个体积,每次找与这个盒子最接近的体积放进去,直到放不下,然后去放下一个盒子直到放完,求盒子最小的体积.思路显然这个题每个不能二分体积,然后暴力找体积范围为[ceil(sum/k),ceil(sum/k)+maxV],sum是所有物品的总体积,maxV是最大的体积,对于每个体积在按题意模拟即可.代码#include<...

2019-11-04 18:21:36

HDU4585 Shaolin

HDU4585 Shaolin题意少林寺以武僧闻名,每年都有很多年轻人去少林寺出家。少林大师对一个年轻人的评价主要是看他对佛经的理解能力,但也要考虑他的打斗技巧。当一个年轻人通过了所有的测试并被宣布为少林新和尚时,将会有一场战斗,作为欢迎派对的一部分。每个和尚都有一个唯一的身份证和一个唯一的战斗等级,都是整数。新和尚必须与战斗等级最接近他的老和尚战斗。如果有两个老和尚满足这一条件,新和尚将采...

2019-11-04 18:14:51

2014-2015 ACM-ICPC, Asia Xian Regional Contest F Color

2014-2015 ACM-ICPC, Asia Xian Regional Contest F Color题意n个格子排成一行,有m种颜色,问用恰好k种颜色进行染色,使得相邻格子颜色不同的方案数。思路组合计数+容斥(奇加偶减)公式为∑i=1k(−1)k−i∗C(k,i)∗(i)∗(i−1)n−1\sum_{i=1}^k(-1)^{k-i}*C(k,i)*(i)*(i-1)^{n-...

2019-10-07 21:05:42

P2468 [SDOI2010]粟粟的书架

P2468 [SDOI2010]粟粟的书架题意给一个n*m的矩阵,每个位置里有一本书,每本书有一个高度,在给定的矩阵中找最少要几本书才能使高度大于等于h思路分情况讨论,首先对于R,C<=200: sum[i][j][k]表示对于子矩阵1-i ,1-j的子矩阵中有多少大于等于k值的和,cal[i][j][k]表示对于子矩阵1-i ,1-j的子矩阵中有多少大于等于k值的个数,然后...

2019-10-07 11:14:29

HDU6278(2018湘潭邀请赛C题Just h-index)

HDU6278题意在一个区间内找一个最大的h使得大于等于h的个数也得大于等于h思路建立一颗主席树,然后二分找最大的h(kuangbin模板属实好用)代码#include<bits/stdc++.h>using namespace std;const int maxn=1e5+10;int maxx=0,tot=0,root=0;int a[maxn],t[m...

2019-10-07 10:56:57

POJ2912(种类并查集)

POJ2912题意n个人玩石头剪刀布的游戏,其中有一个人是裁判,要求将这些人分成三组,这三组可以为空,然后如果裁判为1个输出裁判为第几个人,在多少行就判断出来,如果裁判可能有多个,就输出"Can not determine",没有就输出"Impossible".思路种类并查集(雾),我之前都做的是扩展域并查集,然而我是看完题解才懂的,并查集貌似是满足以下图片的关系,图片参考的博客...

2019-10-03 17:47:16

POJ1733Parity game

POJ1733Parity game题意区间长度为n,给定m个关系,然后三个输入l,r,s(字符) ,如果s="even"表示(l,r) 有偶数个1,如果s="odd"表示(l,r) 有奇数个1,求k使得1-k个条件都能满足要求,而k+1个条件不能满足.思路边带权并查集,记录与父亲节点之间有偶数个1还是奇数个1,当权值为1时时偶数个1,当权值为0时为偶数个1.代码#includ...

2019-10-02 20:26:45

P1525 关押罪犯

P1525 关押罪犯题意略(中文)思路扩展域并查集(当然二分图也可以做),开二倍数组,(1,n)记录关在同一个监狱里,(n+1,2*n)记录与自己不同监狱的,因为还有怨气值,所以怨气值要从大到小排序,保证怨气值大的不在一块,这样就能使怨气值最大的最小,然后依次判断就行了.代码#include<bits/stdc++.h>using namespace std;c...

2019-10-02 20:01:39

P1196 [NOI2002]银河英雄传说

P1196 [NOI2002]银河英雄传说题意略(中文)思路边带权并查集,用front[i]记录i到根节点之间有多少艘战舰,num[i]表示第i列有多少艘战舰.代码#include<bits/stdc++.h>using namespace std;const int maxn=3e4+10;int num[maxn],front[maxn],fa[maxn]...

2019-10-02 19:57:40

P2024 [NOI2001]食物链

P2024 [NOI2001]食物链题意略(中文)思路一道典型的扩展域并查集,我们开三倍数组,(1,n)记录同类域,(n+1,2n)记录捕食域,(2n+1,3*n)记录天敌域,分析各个域的关系,当x,y为同类时x的捕食域肯定不能是y,y的捕食域肯定不能是x,当x,y为捕食关系时(x吃y),此时x和y不能在同类域中,y的捕食域不能是x.代码#include<bits/std...

2019-10-02 19:52:47

P1197 [JSOI2008]星球大战

P1197 [JSOI2008]星球大战题意略(中文)思路一道思维并查集题,正着摧毁貌似不是很行,那就倒着修建,预处理按修建的顺序排序然后用并查集记录连通块个数就行了.代码#include<bits/stdc++.h>using namespace std;const int maxn=4e5+10;struct node{ int x,y,id; ...

2019-10-02 19:43:07

P1955 [NOI2015]程序自动分析

P1955 [NOI2015]程序自动分析题意略(中文)思路并查集加离散化就OK了代码#include<bits/stdc++.h>using namespace std;const int maxn=1e6+10;int fa[maxn];struct node{ int a,b,op; bool operator <(const n...

2019-10-02 19:36:44

2019CCPC秦皇岛题解

HDU6734签到题HDU6740题意a×循环节已经开始出现的部分长度−b×循环节长度a\times循环节已经开始出现的部分长度-b\times循环节长度a×循环节已经开始出现的部分长度−b×循环节长度思路将小数 点后的字符串倒过来求一次next,然后循环节出现的部分长度为i,循环节长度为i-next[i].代码#include<bits/stdc++.h>u...

2019-09-29 13:30:47

状态压缩(TSP问题)

POJ5067题意​ 有一个n*m的矩阵上存在一些石头,接下来要从起点出发把这些石头拿上并回到起点,问最小需要多少步。思路​ 用sum表示除了(1,1)这个点外其他有石头的点的个数,用x数组和y数组表示这些点的坐标的位置,在这里我用二进制下的每个位置表示点的位置,将最后的位置来表示起点,0 - n-1分别表示其他点的位置,然后开始暴力枚举二进制下的每个数字,注意初始化dp[0] [n]=0...

2019-09-24 10:38:21

HDU2825

HDU2825题意求长度为n且至少包含k个给定子串的种类数.思路AC自动机+状压dp.对end[]节点标记数组进行改动,用二进制下第几位表示即为包含第几个给定子串.dp转移方程为dp[i+1][nex][k|end[nex]]=(dp[i+1][nex][k|end[nex]]+dp[i][j][k])%mod第一维表示长度,第二维表示到达哪个节点第三维表示用了哪几个给定子串....

2019-09-24 10:36:28

HDU2243

HDU2243题意求长度为m且包含1-n个子串的种类数.思路首先计算26+262+....+26m26+26^2+....+26^m26+262+....+26m,构造矩阵为[sum(m+1)1]=[sum(m)(初始sum(1)=26)1]∗[260261]\left[ \begin{matrix} sum(m+1) & 1 \end{matrix} \...

2019-09-23 15:31:41

poj2778(ac自动机+矩阵快速幂)

HDU2778题意求长度为m且不包含n个子串的种类数.思路参考自这个博客.ac自动机+矩阵快速幂.这儿有个结论.给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值把给定的图转为邻接矩阵,即A(i,j)=1当且仅当存在一条边i->j。令C=A*A,那么C(i,j)=ΣA(i,k)*A(k,j),实际上就等于从点i到点j恰好经过2条边的路径...

2019-09-22 13:29:31

HDU2896 HDU3065(AC自动机)

HDU2896题意求目标串中出现了几个给定的子串.思路ac自动机模板题().代码#include<bits/stdc++.h>using namespace std;struct Trie{ int next[105010][130],fail[105010],end[105010]; int root,L; int newnode()...

2019-09-20 21:14:20

HDU2222

HDU2222题意求目标串中出现了几个模式串.思路ac自动机模板题.代码#include<bits/stdc++.h>using namespace std;struct Trie{ int next[500010][26],fail[500010],end[500010]; int root,L; int newnode(){ ...

2019-09-19 21:37:16

查看更多

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