2017 ACM/ICPC 沈阳赛区 网络赛

  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);
}
}