COCI 2016/2017 部分题目题解

修改

2026年9月5日 · 阅读需 8 分钟

laieahoy

管理员

A. Tavan

把每个 # 看成一个位置，每个位置有 $k$ 个候选字母。先分别将候选字母排序，这样每个位置的选择顺序就是字典序。

所有可能的单词实际上可以看成一个 $k$ 进制数：前面的 # 优先级更高。对于第 $i$ 个 #，后面还有 $m-i-1$ 个位置，因此当前选择固定后，后面共有 $k^(m-i-1)$ 种组合。

所以从前往后确定每一位：

用 $x$ 除以后面组合的数量，得到当前位应该选择第几个候选字母；
再减去前面完整跳过的组合数量，更新 $x$ ；
最后一个位置直接使用剩余的编号。

确定所有 # 的选择后，再从头扫描原字符串，把每个 # 替换成对应候选串中的字母即可。

需要注意的是，本题使用快速幂计算时可能溢出 $long long$ ，所以要加上特判。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;

const int N=505;
int n,m,k,cnt;
int a[N];
ll x;
string s,t[N];
int chs[N];

ll qpow(ll a,ll b)
{
    ll res=1;
    while(b){
        if(res>(x/a)) return x+1;
        if(b&1) res*=a;
        a*=a;
        b>>=1;
    }
    return res;
}

int main()
{
    cin>>n>>m>>k>>x;
    cin>>s;
    for(int i=0;i<m;i++){
        cin>>t[i];
        sort(t[i].begin(),t[i].end());
    }
    for(int i=0;i<m-1;i++){
        ll c=qpow(k,m-i-1);
        ll w=x/c+1;
        a[i]=w;
        x-=(a[i]-1)*c;
    }
    a[m-1]=x;
    for(int i=0;i<n;i++){
        if(s[i]!='#') cout<<s[i];
        else cout<<t[cnt][a[cnt]-1],cnt++;
    }

    return 0;
}

B. Nizin

回文串需要使串两边的元素依次相等，所以很容易想到一个贪心策略：

每次比较两端：

左端小：左端必须合并；
右端小：右端必须合并；
两端相等：可以安全固定并向内移动。

然后考虑这个做法的正确性，因为不等时执行的合并是任何可行方案都必须执行的；相等时跳过的操作不会影响最优性。因此，每一步贪心操作都不会排除任何最优方案。不断重复上述过程，直到所有元素处理完，得到的合并次数就是最少合并次数。

所以该算法正确。

最后需要注意的是写法不要太混乱。

点击展开代码

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;

const int N=1e6+5;
int n,pos;
ll a[N],ans,s[N],a1[N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],a1[i]=a[i];
	int i=1,j=n;
	while(i<j){
		while(a[i]>a[j]&&i<j){
			j--;
			a[j]+=a[j+1];
			ans++;
		}
		while(a[i]<a[j]&&i<j){
			i++;
			a[i]+=a[i-1];
			ans++;
		}
		if(a[i]==a[j]) i++,j--;
	}
    cout<<ans<<"\n";
    return 0;
}

C. Kroničan

根据数据范围想到状压 dp，试了一下发现没问题，设 $f_s$ 表示到达 $s$ 状态（ $s$ 表示哪些杯子有水）最少的代价，则转移方程为：

f_{s xor (1<<i-1) or (1<<j-1)}=min(f_{s xor (1<<i-1) or (1<<j-1)},f_s+c_{i,j})

点击展开代码

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;

const int N=21,M=(1<<20)+6;
int n,k;
ll c[N][N],f[M],ans=1e9;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>c[i][j];
        }
    }
    memset(f,0x3f,sizeof f);
    f[(1<<n)-1]=0;
    for(int s=(1<<n)-1;s>=0;s--){
        for(int i=1;i<=n;i++){
            if((s>>i-1)&1){
                for(int j=1;j<=n;j++){
                    f[(s^(1<<i-1))|(1<<j-1)]=min(f[(s^(1<<i-1))|(1<<j-1)],f[s]+c[i][j]);
                }
            }
        }
    }
    for(int s=0;s<1<<n;s++){
        int cnt=__builtin_popcount(s);
        if(cnt==k) ans=min(ans,f[s]);
    }
    cout<<ans<<"\n";

    return 0;
}

D. Rima

思路

设两个字符串的最长公共后缀长度为 $LCS(A,B)$ 。根据题意，两个不同的字符串押韵，当且仅当满足以下两种情况之一：

长度相同，只有第一个字符不同；
长度相差 $1$ ，且较短字符串是较长字符串的后缀。

由于题目保证所有字符串互不相同，因此不需要考虑两个字符串完全相等的情况。

建立 Trie

后缀不方便直接处理，可以将每个字符串翻转。翻转后：

原字符串的后缀变成了前缀；
长度相同且只有开头字符不同，变成 Trie 中位于同一节点下的不同子树；
长度相差 1 且短串是长串后缀，变成一个 Trie 节点是另一个节点的父节点。

因此，可以将所有翻转后的字符串插入 Trie 中。

关键性质

考虑一个合法的押韵字符串序列。其长度不会一直递增或递减，而是呈现“长 - 短 - 长”的结构：最长的字符串只能出现在序列两端附近。

以 Trie 中的节点 $u$ 为中心时，序列最多由以下部分组成：

$u$ 的字符串本身；
$u$ 的所有直接儿子中对应的字符串。它们都与 $u$ 押韵，并且任意两个这样的字符串也互相押韵；
至多选取两个不同子树中的序列，分别接在两侧。

设 $u$ 的直接儿子中，有字符串结束的节点数量为 $num$ ，并设所有儿子状态值中最大的两个为 $m1$ 和 $m2$ ，则经过 $u$ 的最长序列长度为：

m1+m2+cntu+max⁡(num−2,0) m1+m2+cntu+max(num−2,0)

其中 $cnt_u$ 表示字符串是否在节点 $u$ 结束。题目保证字符串互不相同，所以 $cnt_u$ 实际上只有 $0$ 或 $1$ 。

之所以最多使用两个子树，是因为一个序列经过中心节点后只能向左、向右各延伸一次；如果使用三个及以上子树，就无法排列成合法的“儿子 - 父亲 - 儿子”结构。状态定义

定义 $f[u]$ 表示：

在以节点 $u$ 对应的字符串作为序列结尾时，能够得到的最长序列长度。

如果 $u$ 本身没有字符串结束，则它不能作为序列结尾；否则可以从某个儿子的最优序列接过来，并把直接儿子中的字符串接在后面：

f_u=m1+max⁡(1,num) f_u=m1+max(1,num)

其中 $1$ 表示节点 $u$ 自身对应的字符串。

对 Trie 进行后序 DFS，先计算所有子节点，再计算当前节点，同时用全局变量维护经过每个节点的最长序列即可。

正确性说明

对于任意中心节点 $u$ ：

所有直接儿子对应的字符串都与 u 押韵；
任意两个直接儿子对应的字符串长度相同，且只在首字符处不同，因此它们也互相押韵；
每个子树内部能够接入的部分，其最优长度由 f 表示；
序列在中心节点两侧最多各连接一个子树，因此只需选择 f 最大的两个不同子树。

所以，经过 $u$ 的最优答案正是状态转移式计算出的值。枚举所有 Trie 节点后，取最大值，就得到了全局最长的合法押韵序列。

复杂度

设所有字符串长度之和为 $S$ 。

建 Trie： $O(S)$ ；
DFS 遍历：每个节点检查 $26$ 条边，复杂度为 $O(26S)$ ，即 $O(S)$ ；
空间复杂度： $O(S)$ 。

点击展开代码

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

const int N=3e6+5,M=26;
int n,cnt,ans;
int f[N];
string s[N];
struct Node{
	int tr[M],cnt;
}a[N];

void add(string s)
{
	int now=0;
	for(int i=s.size()-1;i>=0;i--){
		if(!a[now].tr[s[i]-'a']) a[now].tr[s[i]-'a']=++cnt;
		now=a[now].tr[s[i]-'a'];
	}
	a[now].cnt++;
}

void dfs(int u)
{
	int num=0,m1=0,m2=0;
	for(int i=0;i<26;i++){
		int v=a[u].tr[i];
		if(!v) continue;
		dfs(v);
		if(a[v].cnt) num++;
		if(f[v]>m1) m2=m1,m1=f[v];
		else if(f[v]>m2) m2=f[v];
	}
	if(a[u].cnt) f[u]=m1+max(1,num);
	ans=max(ans,m1+m2+a[u].cnt+max(num-2,0));
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		add(s[i]);
	}
	dfs(0);
	cout<<ans<<"\n";

	return 0;
}

A. Tavan​

B. Nizin​

C. Kroničan​

D. Rima​

思路​

建立 Trie​

关键性质​

正确性说明​

复杂度​

A. Tavan

B. Nizin

C. Kroničan

D. Rima

思路

建立 Trie

关键性质

正确性说明

复杂度