15.10.04【贪心、排序扫描、dp+RKhash】

OI&ACM, OI训练
  1. 1.能量获取 (energy)
  2. 封印一击 (seal)
  3. 归途与征程 (journey)

100+50+40

1.能量获取 (energy)

【题目描述】 “封印大典启动，请出Nescafe魂珠！”随着圣主applepi一声令下，圣剑护法rainbow和魔杖护法freda将Nescafe魂珠放置于封印台上。 封印台是一个树形的结构，魂珠放置的位置就是根节点（编号为0）。还有n个其它节点（编号1-n）上放置着封印石，编号为i的封印石需要从魂珠上获取Ei的能量。能量只能沿着树边从魂珠传向封印石，每条边有一个能够传递的能量上限Wi，魂珠的能量是无穷大的。 作为封印开始前的准备工作，请你求出最多能满足多少颗封印石的能 量需求？ 注意：能量可以经过一个节点，不满足它的需求而传向下一个节点。每条边仅能传递一次能量。 【输入格式】 第一行一个整数n，表示除根节点之外其它节点的数量。 接下来n行，第i+1行有三个整数Fi、Ei、Wi，分别表示i号节点的父节点、i号节点上封印石的能量需求、连接节点i与Fi的边最多能传递多少能量。 【输出格式】 最多能满足多少颗封印石的能量需求。

想了好多，最大流、dp……，后来发现是贪心。。。 好像树形dp也可以

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
#include<algorithm>
#include<cstdio>
using namespace std;
int n,x,y,tot,fa[1001],e[1001];
struct node{int w,num;
}a[1001];
int mycomp(const node&a,const node&b)
{
	return a.w<b.w;
}
int main()
{
	freopen("energy.in","r",stdin);
	freopen("energy.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&fa[i],&x,&e[i]);
		a[i].w=x;a[i].num=i;
	}
	sort(a+1,a+n+1,mycomp);
	for(int i=1;i<=n;i++)
	{
		x=a[i].num;y=a[i].w;
		while(x&&e[x]>=y)  x=fa[x];
		if(x) continue;
		x=a[i].num;
		while(x) e[x]-=y,x=fa[x];
		tot++;
	}
	printf("%d",tot);
}

封印一击 (seal)

【题目描述】 “圣主applepi于公元2011年9月创造了Nescafe，它在散发了16次光辉之后与公元2011年11月12日被封印为一颗魂珠，贮藏于Nescafe神塔之中。公元2012年9月，圣主带领四大护法重启了Nescafe，如今已经是Nescafe之魂的第30次传播了。不久，它就要被第二次封印，而变成一座神杯……”applepi思索着Nescafe的历史，准备着第二次封印。 Nescafe由n种元素组成（编号为1-n），第i种元素有一个封印区间[ai,bi]。当封印力度E小于ai时，该元素将获得ai的封印能量；当封印力度E在ai到bi之间时，该元素将获得E的封印能量；而当封印力度E大于bi时，该元素将被破坏从而不能获得任何封印能量。现在圣主applepi想选择恰当的E，使得封印获得的总能量尽可能高。为了封印的最后一击尽量完美，就请你写个程序帮他计算一下吧！ 【输入格式】 第一行一个整数N。 接下来N行每行两个整数ai、bi，第i+1行表示第i种元素的封印区间。 【输出格式】 两个用空格隔开的整数，第一个数是能够获得最多总能量的封印力度E，第二个数是获得的总能量大小。当存在多个E能够获得最多总能量时，输出最小的E。

原来写的暴力50

题解： 很容易想到，最优解的E肯定是某个区间的端点（而且好像应该是右端点）。 所以我们把所有区间的左右端点取出，从小到大排序，扫描一遍。 维护一个变量sa，表示扫描到的值为p时，左端点大于p的所有区间的左端点之和；维护一个变量sp，表示扫描到的值为p时，p在左右端点之间的区间个数。那么此时可以封印一击得到的能量就是sa+sp*p。 扫描时遇到一个左端点，sa减去这个左端点，sp加一；遇到一个右端点，sp减一即可。

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
#include<algorithm>
#include<cstdio>
using namespace std;
int n,ansx;
long long ans,sa,sp;
struct node{int x,y;
}a[200002];
int mycomp(const node &a,const node &b)
{
	return a.x<b.x;
}
int main()
{
	freopen("seal.in","r",stdin);
	freopen("seal.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
	  	scanf("%d%d",&a[2*i-1].x,&a[2*i].x);
	  	sa+=a[2*i-1].x;a[2*i-1].y=0;a[2*i].y=1;
	}
	sort(a+1,a+2*n+1,mycomp);
	for(int i=1;i<=2*n;i++)
	{
		if(!a[i].y)	
		  sa-=a[i].x,sp++;

		long long b=sa+sp*a[i].x;
		if(b>ans) ans=b,ansx=a[i].x;
		else if(b==ans&&a[i].x<ansx) ansx=a[i].x;
		
		if(a[i].y)  sp--;
	}
	printf("%d %lld",ansx,ans);
}

归途与征程 (journey)

【题目描述】 给出一个长度为N的由小写字母‘a’-‘z’和‘ * ’组成的字符串A，一个长度为M的仅由小写字母‘a’-‘z’组成的字符串B。一个‘ * ’可以匹配任意多个字符（包括0个）。求在的所有循环同构串中，有多少个能够与A匹配。 循环同构串：就是把B的前k个字母(0<=k<M)移到结尾所得到的字符串。 例如abc的循环同构串有abc、bca和cab。 A与B匹配：若除了A中的‘ * ’号可以匹配B中的任意多个字符外，其余字符一一对应，则称A与B匹配。例如a*b*c与aadbc是匹配的，其中第一个 * 对应ad，第二个 * 对应空串。 【输入格式】 第一行为字符串A。 第二行为字符串B。 【输出格式】 输出在B的所有循环同构串中，有多少个能够与A匹配。

居然是dp，显然我并没有想到，爆搜了40

题解：

  • 算法一：类比最长公共子序列的DP方法 (O(NM^2) 80分) 首先枚举B的M个循环同构串。F[i,j]表示A串前i个字符和B串前j个字符能否匹配。 如果a[i]=b[j]，F[i,j]=F[i-1,j-1]； 如果a[i]=‘*’，F[i,j]=F[i-1,j] or F[i,j-1] or F[i-1,j-1]。 边界：F[0,0]=true，如果a[1]=‘*’，F[1,0]=true，其余为false。

  • 算法二：DP+RKhash (O(NM) 100分) 首先按‘*’把A串分成几段，从前往后第i段给一个hash值i，这样的hash值最多有(N+1)/2个。 F[i,j]表示在B串的第i个位置之后，第一次出现hash值为j的串的位置。 把B串前M-1个字符复制一份接在B串后面，枚举起始位置1-M，然后利用F[i,j]，依次向后找A串的那些段最早出现的位置，判断最后到达的位置和起始位置的差是否超过了M即可。但是要注意如果A串开头、结尾不是‘*’，要先把开头结尾处理掉。

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
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int d=29;
unsigned x,m[55],po;
long long y,inf=4294967295UL;
char A[210],B[200001];
int la,lb,n,pre,leng,len[55],tot,first,last,f[200001][55];
unsigned power(unsigned a,int b)
{
	unsigned re=1;
	for(;b;b>>=1,a=a*a)
		if(b&1) re=re*a;
	return re;
}
int main()
{
	freopen("journey.in","r",stdin);
	freopen("journey.out","w",stdout);
	scanf("%s%s",A+1,B+1);
	la=strlen(A+1);lb=strlen(B+1);
	for(int i=1;i<=lb;i++)  B[i+lb]=B[i];
	for(int i=1;i<=la;i++)
	if(A[i]=='*')
	{
		if(i-pre>1)
		{
			x=0;
			for(int j=pre+1;j<i;j++) 
			  x=x*d+(A[j]-'a'+1);
			m[++n]=x;len[n]=i-pre-1;
		}
		pre=i;
	}
	if(A[1]!='*') first=1;
	if(A[la]!='*')
	{
		x=0;last=1;
		for(int j=pre+1;j<=la;j++)  x=x*d+(A[j]-'a'+1);
		m[++n]=x;len[n]=la-pre;
	}
	for(int i=1;i<=n;i++)
	{
		leng=len[i];
		for(int j=lb*2-leng+1;j>=1;j--)
		{
			x=0;
			for(int t=j;t<=j+leng-1;t++)  x=x*d+B[t]-'a'+1;
			if(x==m[i]) f[j-1][i]=j;
			else f[j-1][i]=f[j][i];
		}
	}
	for(int start=1;start<=lb;start++)
	{
		int x=start-1;
		if(first&&f[x][1]!=start) continue;
		if(last&&f[start+lb-1-len[n]][n]!=start+lb-len[n]) continue;
		for(int i=1;i<=n;i++)
		{
		    if(f[x][i]==0) {x=0;break;}
			x=f[x][i]+len[i]-1;
		}
		if(x&&x+1<=lb+start) tot++;
	}
	printf("%d",tot);
}