前行 - COCI 2016/2017 Round 3

考试愉(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) 表示表达式中从 lefrig 的表达式的值。

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

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

质量表达式分为 $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 ,欢迎提问~

0%