前行 - COCI 2016/2017 Round 3 | Lucky_Glass's Blog

以心为名，名为爱惜

0%

前行 - COCI 2016/2017 Round 3

发表于 更新于 分类于 Valine：

考试愉(bao)快(zha)

不得不说这场比赛前4道题不AC说不过去（啪啪打脸）

· A题：Imena

- 题意

一个句子由一个或多个单词构成，除了句子的最后一个单词，每个单词只包含大写和小写字母；最后一个单词的末尾是一个标点（只有 “.”,”,”,”!”,”?” 四种标点），除了这个符号之外只包含大小写字母。

我们称一个单词为“名字”当且仅当它的第一个字母为大写，除此之外的所有字符都是小写字母，（对于句子的最后一个单词忽略其末尾的句号）

给出 $N$ 个句子，对于每个句子求其中的单词有多少个是名字。

数据规模：$1\leq N\leq 5$，总字符数不超过 $1000$

[Input]
1
Spavas li Mirno del Potro juan Martine?

[Output]
4

[Explain]
只有 Spavas, Mirno, Protro, Martine?（这是句子的最后一个单词，忽略末尾的标点） 是名字。

- 解析

依次判断，若判断到一个单词的末尾是标点，则标记该句子结束，并忽略这个标点，判断该单词是否是名字。

- 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char str[1005];
bool symbl(char c){return c=='.'||c==','||c=='?'||c=='!';}
bool ABC(char c){return 'A'<=c && c<='Z';}
bool abc(char c){return 'a'<=c && c<='z';}
int main(){
	freopen("imena.in","r",stdin);
	freopen("imena.out","w",stdout);
	int n,ans=0;scanf("%d",&n);
	for(int i=0;i<n;){
		scanf("%s",str);
		int len=strlen(str);
		if(symbl(str[len-1])){
			bool fail=false;
			if(!ABC(str[0])) fail=true;
			for(int i=1;i<len-1 && !fail;i++)
				if(!abc(str[i]))
					fail=true;
			if(!fail) ans++;
			printf("%d\n",ans);
			ans=0;
			i++;
		}
		else{
			bool fail=false;
			if(!ABC(str[0])) fail=true;
			for(int i=1;i<len && !fail;i++)
				if(!abc(str[i]))
					fail=true;
			if(!fail) ans++;
		}
	}
	return 0;
}

· B题：Pohlepko

- 题意

给出一个 $N$ 行 $M$ 列的方格图，每个方格中有一个小写字母。

在方格图的第一行第一列有一个棋子，你需要将棋子向下或向左挪动（即挪到下一行或下一列），但不能越出方格图的边界，直到将棋子挪到第 $N$ 行第 $M$ 列。

将棋子经过的方格上的字母按顺序记录下来，可以得到一个字符串（包括棋子最初所在的第一行第一列）。求出所有可能得到的字符串中字典序最小的一个。

数据规模：$1\leq N,M\leq 2000$

[Input]
4 5
ponoc
ohoho
hlepo
mirko

[Output]
pohlepko

- 解析

因为比较两个字符串的字典序大小，只需要比较两个串从左到右第一个不同的字符，所以我们容易得到一个贪心的想法——对于向下挪动和向左挪动这两种方案（前提是能够向下、向左），如果下边的字符比左边的字符小，则向下；如果左边的字符更小，则向左……

但是，如果下边和左边的字符一样呢？

我们还不能马上判断出哪一种方案更好，所以我们同时考虑这两种方案——类似于 BFS ，把这两种方案都放入队列中。下一次就把这两种方案拓展出来的所有方案再找最小的字符，直到找到第 $N$ 行第 $M$ 列。

- 源代码

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
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int SIZ=2000;
struct PAIR{int x,y;PAIR(){}PAIR(int _x,int _y):x(_x),y(_y){}};
int rol,col,npus;
char maz[SIZ+3][SIZ+3];
bool vis[SIZ+3][SIZ+3];
PAIR pus[SIZ*SIZ+5];
int main(){
	freopen("pohlepko.in","r",stdin);
	freopen("pohlepko.out","w",stdout);
	queue<PAIR> que;
	scanf("%d%d",&rol,&col);
	for(int i=1;i<=rol;i++)
		scanf("%s",maz[i]+1);
	que.push(PAIR(1,1));
	printf("%c",maz[1][1]);
	if(rol==1 && col==1) return 0;
	while(!que.empty()){
		int chr=(1<<29);
		while(!que.empty()){
			PAIR pre=que.front();que.pop();
			if(pre.x!=rol && chr>(int)maz[pre.x+1][pre.y])
				npus=0,
				chr=(int)maz[pre.x+1][pre.y];
			if(pre.y!=col && chr>(int)maz[pre.x][pre.y+1])
				npus=0,
				chr=(int)maz[pre.x][pre.y+1];
			if(pre.x!=rol && chr==(int)maz[pre.x+1][pre.y] && !vis[pre.x+1][pre.y])
				pus[++npus]=PAIR(pre.x+1,pre.y),
				vis[pre.x+1][pre.y]=true;
			if(pre.y!=col && chr==(int)maz[pre.x][pre.y+1] && !vis[pre.x][pre.y+1])
				pus[++npus]=PAIR(pre.x,pre.y+1),
				vis[pre.x][pre.y+1]=true;
		}
		printf("%c",(char)chr);
		for(int i=1;i<=npus;i++)
			que.push(pus[i]);
		if(pus[1].x==rol && pus[1].y==col) break;
	}
	return 0;
}

· C题：Kronican

- 题意

有 $n$ 个装有水的杯子，每个杯子的容积无限大（=_=），你可以花费 $C(i,j)$ 的体力把第 $i$ 杯中的所有水倒入第 $j$ 杯。

经过若干次倒水，当不超过 $m$ 个杯子里有水时，求你花费的体力的最小值。

对于每组 $(i,j)$ ，给出 $C(i,j)$ ，保证当 $i=j$ 时，$C(i,j)=0$；注意不保证 $C(i,j)=C(j,i)$。

数据规模：$1\leq m\leq n\leq 20$，$0\leq C(i,j)\leq 10^5$

[Input]
5 2
0 5 4 3 2
7 0 4 4 4
3 3 0 1 2
4 3 1 0 5
4 5 5 5 0

[Output]
5

- 解析

这道题的数据规模真的特别有用（不知道为什么我考试的时候就没注意到），我们会发现 $2^{20}\approx 10^6$ ……好像开数组开得下？而且好像每个杯子只有“装有水”，“没有水”两种状态？

—— 状态压缩

定义 dp[S] ：S 是一个压缩的状态，如果 S 的第 $i$ 位是 $0$，说明第 $i$ 个杯子里没有水，否则说明第 $i$ 个杯子里有水。

贪心地想，我们一定不会把一个有水的杯子倒到一个没水的杯子里，只会把水倒到一个有水的杯子里。所以转移的时候，S 中 “1” 的个数一定会减少 1。

于是转移方程式是 $dp[S]=\min\{dp[S\text^u]+\min\{C(u,v)\} | u\in S,v\in S 且 u\not=v\}$ 。

初始状态 S 里全是 1，结束状态 S 中 1 的个数不超过 $m$。

- 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=20,INF=(1<<29);
int n,m;
int cst[N+5][N+5];
int dp[(1<<N)+5];
int BitCnt(int S){
	int ret=0;
	while(S) ret++,S-=S&-S;
	return ret;
}
int DP(int S){
	if(dp[S]!=-1) return dp[S];
	if(BitCnt(S)<=m) return dp[S]=0;
	dp[S]=INF;
	for(int i=0;i<n;i++)
		if(S&(1<<i)){
			int mincst=INF;
			for(int j=0;j<n;j++)
				if(j!=i && (S&(1<<j)))
					mincst=min(mincst,cst[i][j]);
			dp[S]=min(dp[S],DP(S^(1<<i))+mincst);
		}
	return dp[S];
}
int main(){
	freopen("kronican.in","r",stdin);
	freopen("kronican.out","w",stdout);
	memset(dp,-1,sizeof dp);
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			scanf("%d",&cst[i][j]);
	printf("%d\n",DP((1<<n)-1));
	return 0;
}

· D题：Kvalitetni

- 题意

这是题意最难理解的一道题了……

质量算数表达式由乘号，括号，数字和加号组成。

质量算数表达式由以下方式定义：
质量表达式由一个小于或等于 $Z_1$ 的正实数组成，这种表达式具有形式：$(X)$
例如，如果 $Z_1=5$，则 $(4)$ 是质量表达式。

如果 $A_1,A_2,…,A_k$ 是质量表达式，使得 $2≤k≤K$，且这些质量表达式的和不超过 $Z_k$，那么以下表达式也是质量表达式：

已知一个质量表达式，其中的数字用问号替换，共有 $K$ 个问号。
求这个表达式可能具有的最大值。

数据规模：$2\leq K\leq 50$，$1\leq Z_i\leq 50$，给出的表达式包含的字符个数不超过 $10^6$。

[Input]
3
2 5 3
(((?)+(?))*(?))

[Output]
6.000

- 解析

= 初步分析

不难想到可以递归处理表达式的值——Solve(lef,rig) 表示表达式中从 lef 到 rig 的表达式的值。

因为实数是连续的！如果我们求出一个表达式能够取到的最大值为 $X$，那这个表达式一定可以取到大于 $0$（不包含）小于等于 $X$（包含）的所有值，所以我们只需要求某一个表达式的最大值就可以了。

所以更改 Solve(lef,rig) 的定义为：表达式中从 lef 到 rig 的子表达式的最大值。

质量表达式分为 $3$ 类：

  1. $(A)$ ：则该表达式的最大值为 $Z_1$；
  2. $(A_1+A_2+…+A_k)$ ；
  3. $(A_1\times A_2\times…\times A_k)$ ；

对于第 $2,3$ 种情况我们需要递归求解。

= 递归求解情况 2

假设我们递归求出 $A_i$ 的最大值为 $B_i$，即 $0<A_i\leq B_i$；

如果 $B_1+B_2+…+B_k\leq Z_k$ ，那每个 $A_i$ 都取 $B_i$，就能得到最大值，为 $B_1+B_2+…+B_k$；

如果 $B_1+B_2+…+B_k>Z_k$，那将某些 $A_i$ 减小，一定可以使 $A_1+A_2+…+A_k\leq Z_k$ （毕竟 $A_i$ 是实数），此时最大值为 $Z_k$；

综上，表达式的最大值为 $\min\{Z_k,B_1+B_2+…+B_k\}$。

= 递归求解情况 3

先看这么一个问题：

已知 $x_1+x_2+x_3+…+x_n=X$，求 $x_1x_2x_3…x_n$ 的最大值；（$x_i$为实数）

则当 $x_1=x_2=x_3=…=x_n=\frac Xn$ 时，$x_1x_2x_3…x_n$ 取得最大值 $\left(\frac Xn\right)^n$。

再回来看情况3：

仍然假设我们递归求出 $A_i$ 的最大值为 $B_i$，即 $0<A_i\leq B_i$；

显然当 $A_1+A_2+…+A_k=\min\{Z_k,B_1+B_2+…+B_k\}$ 时，$A_1\times A_2\times…\times A_k$ 能够取得最大值，相当于我们已知 $A_1+A_2+…+A_k$ ，求 $A_1\times A_2\times …\times A_k$ 的最大值。

令 $M=\min\{Z_k,B_1+B_2+…+B_k\}$ 。则当 $A_1=A_2=…=A_k=\frac Mk$ 时，表达式能够取到最大值。但问题是 $B_i$ 可能小于 $\frac Mk$ ，即 $A_i$ 取不到 $\frac Mk$。那此时应该让 $A_i$ 尽可能接近 $\frac Mk$，即 $A_i$ 取 $B_i$。那么剩下的 $(k-1)$ 个 $A$ 的和就为 $M-B_i$，就应该让剩下的 $A$ 的值尽可能接近 $\frac {M-B_i}{k-1}$ ，一直重复这个操作，直到确定每个 $A_i$ 的取值。

- 源代码

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
/*Lucky_Glass*/
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=50,LEN=1e6;
int n,len;
int lim[N+5],cnc[LEN+5];
char str[LEN+5];
double Solve(int lef,int rig){
	if(lef+2==rig) return (double)lim[1];
	bool tag; //true: + ; false: *
	vector<double> vec;
	for(int i=lef+1;i<rig;i++){
		if(str[i]=='+') tag=true;
		if(str[i]=='*') tag=false;
		if(str[i]=='('){
			vec.push_back(Solve(i,cnc[i]));
			i=cnc[i];
		}
	}
	int siz=vec.size();
	double ret;
	if(tag){
		ret=0;
		for(int i=0;i<siz;i++) ret+=vec[i];
		ret=min(ret,(double)lim[vec.size()]);
	}
	else{
		ret=1;
		sort(vec.begin(),vec.end());
		double sum=lim[siz];
		for(int i=0;i<siz;i++){
			double wnt=sum/(siz-i);
			if(vec[i]>=wnt) sum-=wnt,ret*=wnt;
			else sum-=vec[i],ret*=vec[i];
		}
	}
	return ret;
}
int main(){
	freopen("kvalitetni.in","r",stdin);
	freopen("kvalitetni.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&lim[i]);
	scanf("%s",str+1);
	len=strlen(str+1);
	stack<int> stk;
	for(int i=1;i<=len;i++){
		if(str[i]=='(') stk.push(i);
		if(str[i]==')'){
			int pos=stk.top();stk.pop();
			cnc[pos]=i;
		}
	}
	printf("%.4f\n",Solve(1,len));
	return 0;
}

· E题：Zoltan

- 题意

你有一个包含 $n$ 个数的数列，并将用这个数列进行如下操作：

取出数列的第一个数并把它写在黑板上；取出数列的第 $2$ 个数，把它写在第一个数的左边或右边，于是黑板上出现了一个长度为 $2$ 的数列；取出数列的第 $3$ 个数，把它写在黑板上的长度为 $2$ 的数列的左边或右边，得到一个长度为 $3$ 的数列……取出数列的第 $i$ 个数，把它写在黑板上的长度为 $(i-1)$ 的数列的左边或右边，得到一个长度为 $i$ 的数列……直到把 $n$ 个数全部取完。

此时你会得到一个 $n$ 个数的数列。当存在某个数在数列 $A$ 中写在右边，在数列 $B$ 中写在左边，我们称两个数列 $A,B$ 不同（和数的值没有关系，比如初始的数列为 $[1,1]$ ，取出第一个 $1$ 写下来，然后把第二个 $1$ 写在第一个的左边或右边，都会得到 $[1,1]$ ，但是得到的这两个数列是不一样的）。

求最后得到的所有可能的 $n$ 个数的数列中最长上升子序列的长度 $m$（严格上升），并求出长度为 $m$ 的上升子序列在所有可能得到的数列中出现了多少次。

[Input]
3
1 2 1

[Output]
2 4

[Explain]
假设给原数组的数字编号 $[1_1,2,1_2]$ ，所有可能得到的数列有 $[1_1,2,1_2],[1_2,1_1,2],[2,1_1,1_2],[1_2,2,1_1]$ ，可以发现最长上升子序列是 $[1,2]$ ，长度为 $2$。
其中 $[1_1,2,1_2]$ 中存在 $1$ 个：$[1_1,2]$；$[1_2,1_1,2]$ 存在 $2$ 个：$[1_1,2],[1_2,2]$；$[2,1_1,1_2]$ 中没有；$[1_2,2,1_1]$ 中有 $1$ 个：$[1_2,2]$ 。则总共出现了 $4$ 个。

- 解析

= 求最长上升子序列的长度

（下面是一个gif动图，如果它没动，点它一下）

gif1

先从原数列中选取一些数字记作 ${A_1,A_2,A_3,…,A_t}$（按数字在原数列中的顺序排列），定义 $X=A_1$。

显然我们可以选择让 $A_i(i\not =1)$ 放在 $A_1$ 的左边或者右边，那么我们找出 $\{A_1,A_2,A_3,…,A_t\}$ 中以 $A_1$ 开头的最长下降和最长上升子序列。再将最长下降子序列的所有元素（除去 $A_1$ 本身）放在 $A_1$ 的左边，那么就可以构成最长的上升子序列。【上面的动图就是一个演示（Tab. 上图选出 {3,1} 意思是选出以“3”开头的最长下降子序列，写掉了，抱歉 TAT）】

贪心地想，如果我们确定了 $X$ ，那么要使上升子序列更长，我们选择的数应该是 $X$ 右边的所有数——因为如果不选完右边的所有数，则额外选择一个右边的数，上升子序列长度要么不变，要么加 $1$ 。

= 统计方案数

设选择的数中以 $X$ 开头的不同的最长上升子序列和最长下降子序列的数量分别为 $cnt_1,cnt_2$，则根据组合数学的乘法原理，即 选择的数中一个最长上升子序列和一个最长下降子序列 一起构成一个 答案中的最长上升子序列，共有 $cnt_1\times cnt_2$ 个。

怎么实现呢？线段树当然可以~

- 源代码

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N=2e5;
const ll MOD=1e9+7;
struct SEGTREE{
	struct NODE{int len;ll cnt;}nod[N*4+5];
	void Build(int u,int lef,int rig){
		nod[u].len=nod[u].cnt=0;
		if(lef==rig) return;
		int mid=(lef+rig)>>1;
		Build(u<<1,lef,mid);
		Build(u<<1|1,mid+1,rig);
	}
	void Update(int u){
		nod[u].len=max(nod[u<<1].len,nod[u<<1|1].len);
		nod[u].cnt=0;
		if(nod[u].len==nod[u<<1].len) nod[u].cnt+=nod[u<<1].cnt;
		if(nod[u].len==nod[u<<1|1].len) nod[u].cnt+=nod[u<<1|1].cnt;
		nod[u].cnt%=MOD;
	}
	pii Query(int u,int lef,int rig,int L,int R){
		if(L>R) return make_pair(0,0);
		if(L<=lef && rig<=R) return make_pair(nod[u].len,nod[u].cnt);
		if(R<lef || rig<L) return make_pair(0,0);
		int mid=(lef+rig)>>1;
		pii res1=Query(u<<1,lef,mid,L,R),
			res2=Query(u<<1|1,mid+1,rig,L,R);
		if(res1.first>res2.first) return res1;
		if(res1.first<res2.first) return res2;
		return make_pair(res1.first,(res1.second+res2.second)%MOD);
	}
	void Modify(int u,int lef,int rig,int pnt,int len,int cnt){
		if(pnt<lef || rig<pnt) return;
		if(lef==rig){
			if(len>nod[u].len)
				nod[u].cnt=0,
				nod[u].len=len;
			if(len==nod[u].len)
				nod[u].cnt=(cnt+nod[u].cnt)%MOD;
			return;
		}
		int mid=(lef+rig)>>1;
		Modify(u<<1,lef,mid,pnt,len,cnt);
		Modify(u<<1|1,mid+1,rig,pnt,len,cnt);
		Update(u);
	}
}tre1,tre2;
int n,ncpynum;
int num[N+5],cpynum[N+5];
ll QPow2(int ovr){
	ll ret=1,cur=2;
	while(ovr){
		if(ovr&1) ret=ret*cur%MOD;
		cur=cur*cur%MOD;
		ovr>>=1;
	}
	return ret;
}
int main(){
	freopen("zoltan.in","r",stdin);
	freopen("zoltan.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&num[i]),
		cpynum[i]=num[i];
	sort(cpynum+1,cpynum+1+n);
	ncpynum=unique(cpynum+1,cpynum+1+n)-cpynum-1;
	for(int i=1;i<=n;i++)
		num[i]=lower_bound(cpynum+1,cpynum+1+ncpynum,num[i])-cpynum;
	int maxlen=0;
	ll maxcnt=0;
	for(int i=n;i>=1;i--){
		pii res1=tre1.Query(1,1,ncpynum,num[i]+1,ncpynum),
			res2=tre2.Query(1,1,ncpynum,1,num[i]-1);
		int len1=res1.first+1,len2=res2.first+1;
		ll  cnt1=res1.second,cnt2=res2.second;
		if(!cnt1) cnt1=1;
		if(!cnt2) cnt2=1;
		int len=len1+len2-1;
		ll cnt=cnt1*cnt2%MOD*QPow2(n-len)%MOD;
		tre1.Modify(1,1,ncpynum,num[i],len1,cnt1);
		tre2.Modify(1,1,ncpynum,num[i],len2,cnt2);
		if(len>maxlen) maxlen=len,maxcnt=0;
		if(len==maxlen) maxcnt=(maxcnt+cnt)%MOD;
	}
	printf("%d %lld\n",maxlen,maxcnt);
	return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ，欢迎提问~