2017 ACM/ICPC 沈阳赛区 网络赛

OI&ACM, ACM训练
  1. 1 【HDU 6194】string string string
  2. 2 【HUD 6195】cable cable cable
  3. 3 【HUD 6196】happy happy happy
  4. 4 【HUD 6197】array array array
  5. 5 【HUD 6198】number number number
  6. 6 【HUD 6199】gems gems gems
  7. 7 【HUD 6200】mustedge mustedge mustedge
  8. 8 【HUD 6201】transaction transaction transaction
  9. 9 【HUD 6202】cube cube cube
  10. 10 【HUD 6203】ping ping ping
  11. 11 【HUD 6204】triangulation triangulation triangulation
  12. 12 【HUD 6205】card card card

1 【HDU 6194】string string string

给一个字符串s，求正好出现k次的子串有多少个。

后缀自动机

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
#include <cstring>
#include <cstdio>
const int N=1e5+5;
char s[N];
int T,n,m,ans,last,cnt,son[N<<1][26],fa[N<<1],len[N<<1],sum[N<<1],c[N<<1],d[N<<1];
inline void Add(int x)
{
	int c=s[x]-'a',p=last,np=++cnt;
	sum[np]=1;
	len[last=np]=x;
	for(;p&&!son[p][c];p=fa[p]) son[p][c]=np;
	if(!p) fa[np]=1;
	else
	{
		int q=son[p][c];
		if(len[q]==len[p]+1) fa[np]=q;
		else
		{
			int nq=++cnt;
			len[nq]=len[p]+1;
			memcpy(son[nq],son[q],sizeof son[q]);
			fa[nq]=fa[q];
			fa[np]=fa[q]=nq;
			for(;son[p][c]==q;p=fa[p]) son[p][c]=nq;
		}
	}
}
inline void Solve()
{
	for(int i=1;i<=cnt;i++) c[len[i]]++;
	for(int i=1;i<=n;i++) c[i]+=c[i-1];
	for(int i=cnt;i;i--) d[c[len[i]]--]=i;
	for(int i=cnt;i;i--) sum[fa[d[i]]] += sum[d[i]];
	sum[1] = 0;
}

void Dfs(int x) {
	if (sum[x]==m) ans++;
	if (x!=1&&sum[x]<m) return;
	for (int i=0;i<26;i++)
		if(son[x][i]) Dfs(son[x][i]);
}
int main()
{
	for(scanf("%d",&T);T;T--)
	{
		scanf("%d%s",&m,s+1);
		n=strlen(s+1);
		last=cnt=1;
		ans=0;
		memset(c,0,sizeof(c));
		memset(son,0,sizeof(son));
		memset(fa,0,sizeof(fa));
		memset(sum,0,sizeof(sum));
		for(int i=1;i<=n;i++) Add(i);
		Solve();
		Dfs(1);
		printf("%d\n",ans);
	}
}

2 【HUD 6195】cable cable cable

有K个信号源，M个显示屏(K≤M)，一个信号源每次只能在一个显示器上显示。问至少需要多少线缆连接才能让任意K个显示屏都能同时显示全部K个信号源。

\(ans = K + (M-K)\times K(M-K+1)\times K\)

对于前K个显示器，分别连接前K个信号源；对于后(M-K)个显示器，连接全部K个信号源

3 【HUD 6196】happy happy happy

Bob和一个小朋友玩游戏，有n个数字。一个人可以拿最左边或最右边的数字，然后得到和数字相同的分数，最后得分多者胜。小朋友会选大的，如果左右一样大选左边。求Bob输掉比赛时的最小得分差距，或输出Bob一定会赢。

题解

4 【HUD 6197】array array array

问能否在数组A中选择K个元素删掉，使得剩余的数组非增或非减。

求是否满足 Max(最长不下降子序列,最长不上升子序列)+K>=N

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
#include <algorithm>
#include <cstdio>
const int N=1e5+5;
int T,n,m,K,ans1,ans2,a[N],max[N];
inline int Query(int x)
{
	int mx=0;
	for(;x;x-=x&(-x)) mx=std::max(mx,max[x]);
	return mx;
}
inline void Change(int x,int v)
{
	for(;x<=m;x+=x&(-x)) max[x]=std::max(max[x],v);
}
inline int Calc()
{
	int ans=0;
	for(int i=0;i<=m;i++) max[i]=0;
	for(int i=1,x;i<=n;i++)
	{
		ans=std::max(ans,x=Query(a[i])+1);
		Change(a[i],x);
	}
	return ans;
}
int main()
{
	for(scanf("%d",&T);T;T--)
	{
		scanf("%d%d",&n,&K);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]),m=std::max(m,a[i]);
		ans1=Calc();
		std::reverse(a+1,a+n+1);
		ans2=Calc();
		printf(std::max(ans1,ans2)+K>=n?"A is a magic array.\n":"A is not a magic array.\n");
	}
}

5 【HUD 6198】number number number

对于每个k，求最小的不能用k个斐波那契数表示的数字。答案mod 998244353

ans = Fib(2n+3)-1

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
#include <cstdio>
const int mod=998244353;
int n;
struct Matrix{
	int m[5][5],W,H;
};
Matrix operator * (const Matrix a,const Matrix b)
{
	Matrix c;
	c.H=a.H;c.W=b.W;
	for(int i=1;i<=c.H;i++)
		for(int j=1;j<=c.W;j++)
		{
			c.m[i][j]=0;
			for(int k=1;k<=a.W;k++)
	    		c.m[i][j]=(c.m[i][j]+1LL*a.m[i][k]*b.m[k][j]%mod)%mod;
		}
	return c;
}
Matrix power(Matrix x,int y)
{
	Matrix re;
	re.H=re.W=2;re.m[1][1]=re.m[2][2]=1;re.m[1][2]=re.m[2][1]=0;
	for(;y;y>>=1,x=x*x)
		if(y&1) re=re*x;
	return re;
}
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		Matrix A,B;
		A.H=2;A.W=1;A.m[1][1]=1;A.m[2][1]=0;
		B.H=B.W=2;B.m[1][1]=B.m[1][2]=B.m[2][1]=1;B.m[2][2]=0;
		Matrix ans=A*power(B,2*n+2);
		printf("%d\n",ans.m[1][1]-1);
	}
}

6 【HUD 6199】gems gems gems

n个宝石，价值为vi，Alice和Bob从左往右拿，轮流进行。第一次Alice可以拿1或2个宝石；设上一次拿了k个，则另一个人拿k或k+1个；直到取不到k或k+1个宝石为止。假设足够聪明，求最终两人宝石总价值的差。

题解

7 【HUD 6200】mustedge mustedge mustedge

无向连通图，最初无重边无自环。两种操作：1.从u到v加一条无向边；2.计算从u到v的所有路径边集的交集大小。

题解

8 【HUD 6201】transaction transaction transaction

n个城市，书的价格为ai；n-1条边，车票价格为vi。选择城市买书，到另一个城市卖书，求最大收益。

树形DP

\(ans(S,T) = a[T] - a[S] - dis(S,T) = (a[T] - dis(T,lca)) - (a[S] + dis(S,lca))\)

\(fmax[x] = \max\{ a[y] - dis(y,x) \}\)
\(fmin[x] = \min\{ a[y] + dis(y,x) \}\)

\(ans = \max\{ fmax[x] - fmin[x] , fmax[x] - a[x] , a[x] - fmin[x] \}\)

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 <iostream>
#include <cstdio>
const int inf=1e9+7,N=1e5+5;
int T,n,ans,a[N],fmax[N],fmin[N];
int ecnt,head[N],to[N<<1],cost[N<<1],next[N<<1];
inline void Addedge(int x,int y,int z)
{
	to[++ecnt]=y;cost[ecnt]=z;next[ecnt]=head[x];head[x]=ecnt;
}
void Dfs(int x,int f)
{
	fmax[x]=-inf;
	fmin[x]=inf;
	for(int e=head[x];e;e=next[e])
	{
		int y=to[e],z=cost[e];
		if(y==f) continue;
		Dfs(y,x);
		fmax[x]=std::max(fmax[x],std::max(fmax[y]-z,a[y]-z));
		fmin[x]=std::min(fmin[x],std::min(fmin[y]+z,a[y]+z));
	}
	ans=std::max(std::max(ans,fmax[x]-fmin[x]),std::max(fmax[x]-a[x],a[x]-fmin[x]));
}
int main()
{
	for(scanf("%d",&T);T;T--)
	{
		scanf("%d",&n);
		ecnt=ans=0;
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]),head[i]=0;
		for(int i=1,x,y,z;i<n;i++)
		{
			scanf("%d%d%d",&x,&y,&z);
			Addedge(x,y,z);
			Addedge(y,x,z);
		}
		Dfs(1,0);
		printf("%d\n",ans);
	}
}

9 【HUD 6202】cube cube cube

八轴八面魔方，长这样： 平面展开图： 转法： 解释：bilibili av8452301
问是否能三步恢复魔方

打表or暴力
题解

10 【HUD 6203】ping ping ping

n+1个服务器(0到n)通过n条网线连接，一些服务器坏掉了。记录一些ping不成功的服务器对，求服务器最少坏了多少个。

题解

11 【HUD 6204】triangulation triangulation triangulation

正n边形，画n-3条不相交的对角线，把n边形分成n-2个三角形。要求使面积最大的三角形只有一个的方法数，输出(ans%x)*(ans%y)。

12 【HUD 6205】card card card

n堆卡片排成一行，每堆ai张卡片。可以多次把第一堆放到最后。从头开始把每一堆卡片翻过来，再在所有翻过来的卡片中翻回去bi(penalty value)张，直到无法翻回去足够张为止。求开始时要移动多少堆，使曾经被翻过的卡片数量最多。保证\(\sum ai = \sum bi\)。(要用快读)

可证得一定能全部翻过。

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
#include <cstdio>
const int N=2e6+5;
int n,ans,a[N],b[N],c[N];
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++) a[i+n]=a[i]=read();
		for(int i=1;i<=n;i++) b[i+n]=b[i]=read();
		for(int i=1;i<=(n<<1);i++)
		{
			b[i]=a[i]-b[i];
			c[i]=c[i-1]+b[i];
			a[i]=a[i-1]+a[i];
		}
		for(int i=1,j=1;i<=n;i++)
		{
			while(b[i]<0) i++;
			while(j<=(n<<1)&&c[j]-c[i-1]>=0)
			{
				if(j-i==n-1) ans=i;
				j++;
			}
		}
		printf("%d\n",ans-1);
	}
}
后缀自动机 LIS 斐波那契 树形DP