题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2222
AC自动机,直接套模版水过,模版地址:AC自动机简单模版
1 |
|
题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2222
AC自动机,直接套模版水过,模版地址:AC自动机简单模版
1 | #include<stdio.h> |
题目大意是有n家银行,每家银行可抢mi的金钱,被抓的分险是pi,当你的分险和大于p时就会被抓,求你在不被抓的前提下怎样才能抢到最多的钱,这题,就是01背包的小数形式,我们可以用pi表示抢到i金币时的最大逃脱率
1 | #include<iostream> |
从题意中可得出两个递推关系:
要求Sn,显然这题是矩阵快速幂的问题,所以我们首先要将两个递推公式合并成一个只含有Sn递推的公式
显然,第二个式子含有平方项,所以,首先我们要将第一式平方并带入Sn中
这样就可以运用矩阵快速幂求Sn了
1 | /** |
原题地址:http://acm.hdu.edu.cn/showproblem.php?pid=4161
题目大意就是给出一段序列,然后生成一段新的序列,使新序列的第i个元素是原序列第i+1个元素与第i个元素差的绝对值(最后一个是第一个与最后一个差的绝对值),问如此经过多少步,可以得到一个元素全部一样的序列,当然,当要的步骤大于1000时我们认为不可能得到这样的序列,输出not attained
解决办法很简单,就是枚举循环操作,对于每次生成的序列进行判断是否满足,详细看代码
1 | #include<iostream> |
原题地址:http://acm.hdu.edu.cn/showproblem.php?pid=4162
题目大意就是定义出方向如原题描述,单由于起点和旋转的不确定性,对于同一幅图有多种描述方法,为了统一,定义一种新的描述
第一步转换很简单,和上一题类似,详细看hdu4161 Iterated Difference 解题报告,但对于第二步,如果直接枚举每种情况,绝对超时。多亏ACM群的taozifish帮忙,原来是要用后缀数组做,不会,搜模板:串的最小表示模板,然后水过。以后有时间就把这个空缺补上,详细看代码
1 | #include<iostream> |
原题地址:http://acm.hdu.edu.cn/showproblem.php?pid=4163
这题就是一个排序题,比较纠结。题目大意就是就是给出n个数,每个数对应着唯一的编号,就是他所处的序号,然后求出前k1小的元素对应的位置,升序输出,如果有相同的元素,选择和最小的,求出前k2大的元素对应的位置,升序输出,如果有相同的元素,选择和最大的。实际上就是一个稳定排序问题,可以用STL里的stable_sort,后续我会发一些关于STL模板库常用算法。详情看代码
1 | #include<iostream> |
原题地址:http://acm.hdu.edu.cn/showproblem.php?pid=4161
题目大意是什么意思,还不是很明白,好像是每次从一个瓶子里取药,可以取全部,也可以取一半,如果取到的药是完整的,就把它分成两半,吃掉其中的一半,另一半重新放入瓶中,如果取到半粒药,则直接吃掉,现在有n粒药,要2n天内吃完,问有多少种吃药方法
不知道题目是不是理解对的,看了很久无想法,然后,laputa大神发消息过来说他A了,虽然他也没看懂题,Orz,原来这题是一个裸的卡特兰数(也译为卡塔兰数),关于该数不做过多介绍,详细可以看维基百科,还说自己是搞数学的,给了这么多的测试数据都没看出猫腻,唉!然后向他要了模板,直接套用,AC了,不愧是大神!Orz!
1 | #include<iostream> |
看到这题就觉得是矩阵快速幂,但是g(n)里面还有g(n)不好处理。其实应该想到,既然有取余,就一定有循环节。再做的时候想到会有循环节了,但想到是对1e9+7取余,则循环节最大就可能是10^18,再加上爆了10^7范围内的数据没发现循环节,就没想了。看来有时候不是题目做不出来,而是没有往下面想的勇气
既然对1e9+7取余有循环节,假设是k1,则我们就有g(n)%1000000007=g(n%k1)%1000000007,则就要求g(g(g(n)))就相当于求g(g(g(n))%k1),而求g(g(n))%k1,同理,可爆出g(n)对k1取余的循环节k2,则题目就暂时变成了求g(g(g(n%k2))%k1),然后就可以用矩阵快速幂求解(程序爆出k1=222222224,k2=183120)
1 | #include<iostream> |
简单KMP,下面是官方题解
这道题问的就是将1个串如何变为stringA+stringB的形式,使得stringA是stringB经过映射得到相同的串。映射那步其实没有什么价值,假设str为原串s经过映射后得到的串,我们可以以str为模式串,以s为原串做一次扩展KMP,得到extend数组,extend[i]表示原串以第i开始与模式串的前缀的最长匹配。经过O(n)的枚举,我们可以得到,若extend[i]+i=len且i>=extend[i]时,表示stringB即为该点之前的串,stringA即为该点之前的str串,最后输出即可。
我的代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))
char s[30];
char q[30];
char inter[100010];
char cry[50010];
int p[100010];
int cnt[100010];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int i,j;
scanf("%s%s",s,inter);
for(i=0;s[i];i++)
{
q[s[i]-'a']=i+'a';
}
zero(cry);
int len=strlen(inter);
if(len==1)
{
printf("%c%c\n",inter[0],q[inter[0]-'a']);
continue;
}
for(i=(len-1)/2+1;inter[i];i++)
cry[i-1-(len-1)/2]=s[inter[i]-'a'];
p[0]=-1;
j=-1;
for(i=1;inter[i];i++)
{
while(j>=0&&inter[j+1]!=inter[i])
j=p[j];
if(inter[j+1]==inter[i])
j++;
p[i]=j;
}
j=-1;
int t;
t=strlen(cry);
//cout<<cry<<endl;
for(i=0;cry[i];i++)
{
while(j>=0&&inter[j+1]!=cry[i])
j=p[j];
if(inter[j+1]==cry[i])
{
j++;
}
cnt[i]=j;
if(j==t)
j=p[j];
}
for(i=0;i<len-cnt[t-1]-1;i++)
printf("%c",inter[i]);
for(i=0;i<len-cnt[t-1]-1;i++)
printf("%c",q[inter[i]-'a']);
printf("\n");
}
return 0;
}
下面是官方的解题报告
题意:
给定一个$2n$的矩形,求把这个矩形分割为$k$部分的方法,且对称的切割方法视为不同,输出时模上$100000007$。
($1 \leq n \leq 1000,1 \leq k \leq 2n$)
解法:
看到这个题目,很容易想到DP。
状态表示
$f_{i0j}$ :前$i$行已经出现了$j$部分且第$i$行的两个格子属于同一部分的方法数
$f_{i1j}$ :前$i$行已经出现了$j$部分且第$i$行的两个格子属于不同部分的方法数
初始条件
$f_{101} = f_{112} = 1$
状态转移,下面使用$I$表示$i+1$,$J$表示$j+1$,$jj$表示$j+2$
$f_{I0j}=f_{I0j}+f_{i0j}+2f_{i1j}$
$f_{I0J}=f_{I0J}+f_{i0j}+f_{i1j}$
$f_{I1j}=f_{I1j}+f_{i1j}$
$f_{I1J}=f_{I1J}+2f_{i0j}+2f_{i1j}$
$f_{I1jj}=f_{I1jj}+f_{i0j}+f_{i1j}$
共12种不同的状态转移(见下图)
我的代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))
int dp[2][1005][2010];
const int mod = 100000007;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,k,i,j;
scanf("%d%d",&n,&k);
zero(dp);
for(i=1;i<=n;i++)
dp[0][i][1]=1,dp[1][i][1]=0;
dp[1][1][2]=1;
for(i=2;i<=n;i++)
{
for(j=2;j<=2*i&&j<=k;j++)
{
dp[0][i][j]=( dp[0][i-1][j-1] + dp[0][i-1][j] + dp[1][i-1][j-1] + dp[1][i-1][j]*2 ) % mod;
dp[1][i][j]=( dp[0][i-1][j-1]*2 +dp[0][i-1][j-2]+ dp[1][i-1][j-1]*2 + dp[1][i-1][j] + dp[1][i-1][j-2]) % mod;
}
}
printf("%d\n",(dp[0][n][k]+dp[1][n][k])%mod);
}
return 0;
}
tag:
缺失模块。
1、请确保node版本大于6.2
2、在博客根目录(注意不是yilia根目录)执行以下命令:
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置:
jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true