COCI 2017/2018 部分题目题解

修改

2026年9月3日 · 阅读需 10 分钟

laieahoy

管理员

A. Lozinke

一个字符串能够对答案产生贡献，当且仅当它是除自己外某一个字符串的子串，于是我们可以依次判断加入答案，但这样显然会超时。

于是我们反过来想，不用某字符串匹配子串，而是用子串找字符串。具体来说，预处理出所有可能出现的子串的出现次数，那么一个字符串对答案的贡献就是与其相等的非自己的子串的个数，直接加到答案中即可。

还需注意一个小细节，因为一个字符串的某一个的子串只会匹配一次，所以需要判断某一子串是否已经在这个字符串中出现过，如果没有，就计入这种子串的出现次数。

预处理的实现用 Hash 即可。

点击展开代码

代码：

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

const int N=20005;
int n,ans;
string s[N];
unordered_map<string,int> mp1;
unordered_map<string,bool> mp2;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        mp2.clear();
        int len=s[i].size();
        for(int j=0;j<len;j++){
            for(int k=1;j+k-1<len;k++){
                string t=s[i].substr(j,k);
                if(!mp2[t]){
                    mp1[t]++;
                    mp2[t]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        ans+=mp1[s[i]]-1;
    }
    cout<<ans<<"\n";

    return 0;
}

B. Mate

非常直观的思路，设 $dp[i][x][y][len]$ 表示处理到第 $i$ 位时，将第 $i$ 位的字符放入取出的字符串中，取出的字符串末尾为 $x$ 和 $y$ （就是 $s[i]$ ），取出的字符串长度为 $len$ 时的方案数，转移很简单，就不写了。

于是我们会发现，记录的状态的第一维和第二维功能是重叠的，我们可以删去一个，删哪个呢，注意到，若保留第一维，虽然确实可以使无效的转移（即转移的状态不可达）减少，但我们更新时需要遍历所有的比 $i$ 小的位置，这样一来，复杂度就到了 $O(26\cdot n^3)$ ，会超时；再看保留第二维的情况，虽然有的状态不可达，但不可达的状态转移到下一状态时给的贡献是 $0$ ，所以首先对正确性没有影响，而且可以使复杂度到 $O(26\cdot 26 \cdot n^2)$ ，时间开销大大减少，所以我们会保留第二维。

但是即使这样仍然会超时，我们还要想办法优化，先将状态转移写出来：

dp[x][y][len]=\sum_{0\le k<25}dp[k][x][len-1](len\ge 3)

对于 $len=2$ 的情况，直接枚举所有小于 $i$ 的 $j$ ，然后使 $dp[s[j]-'a'][s[i]-'a']$ 自加 $1$ 。

现在导致超时的问题会是什么呢，有可能是我们之前提到过的计算了大量不可达状态导致的，但因为没有记录当前取出的倒数第二个字符来自哪个位置，这个优化暂时不能做。

那么还有没有可能导致超时的地方呢，我们发现除了遍历倒数第二个字符的 $26$ 外，还有一个 $26$ 是遍历倒数第三个字符的过程中产生的，这一维是否可以优化呢，注意到，其实倒数第三个字符是什么是不会对当前转移造成影响的，所以我们完全可以不遍历它，而是重新记录一个数组 $ways[len][x]$ 表示以 $x$ 结尾，长度为 $len$ 的取出字符串可能的方案数，为了在计算到每一位时能够快速计算它，可以再记录一个数组 $totalw[len]$ 表示长为 $len$ 的取出字符串的总方案数，那么转移方程就很好写了：

dp[x][y][len]=dp[x][y][len]+ways[len-1][x]\\ ways[len][s[i]-'a']=ways[len][s[i]-'a']+totalw[len-1](len\ge 2)\\ ways[1][s[i]-'a']=ways[1][s[i]-'a']+1\\ total[len]=total[len]+ways[len][s[i]-'a'](len\ge 2)\\ total[1]=total[1]+1\\

然后这道题就写完了，还有一个小细节，就是遍历 $len$ 时要从大到小遍历，以免后续需要用到的值被提前覆盖。

点击展开代码

代码：

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

const int M=2005,N=27,mod=1e9+7;
string s;
int q;
int dp[M][N][N],ways[M][N],totalw[M];

void addmod(int &x,int y)
{
    x+=y;
    if(x>mod) x-=mod;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>s;
    for(int i=0;i<s.size();i++){
        for(int len=i+1;len>=2;len--){
            for(int k=0;k<26;k++){
                addmod(dp[len][k][s[i]-'a'],ways[len-1][k]);
            }
            addmod(ways[len][s[i]-'a'],totalw[len-1]);
            addmod(totalw[len],totalw[len-1]);
        }
        addmod(ways[1][s[i]-'a'],1);
        addmod(totalw[1],1);
    }
    cin>>q;
    while(q--){
        int d;
        string s;
        cin>>d>>s;
        cout<<dp[d][s[0]-'a'][s[1]-'a']<<"\n";
    }

    return 0;
}

C. Deda

非常明显的线段树二分，将题意理解后就没什么思维难度了，主要是实现。

点击展开代码

代码：

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

const int N=2e5+5,inf=1e9;
int n,q;
struct SegTree{
    int val[N<<2];

    SegTree() {for(int i=0;i<N<<2;i++) val[i]=inf;}

    inline void pushup(int p){
        val[p]=min(val[p<<1],val[p<<1|1]);
    }

    inline void change(int p,int l,int r,int x,int y){
        if(l==r){
            val[p]=y;
            return;
        }
        int mid=l+r>>1;
        if(mid>=x) change(p<<1,l,mid,x,y);
        else change(p<<1|1,mid+1,r,x,y);
        pushup(p);
    }

    inline int query(int p,int l,int r,int L,int R){
        if(l>=L&&r<=R) return val[p];
        int mid=l+r>>1,res=inf;
        if(mid>=L) res=min(res,query(p<<1,l,mid,L,R));
        if(mid<R) res=min(res,query(p<<1|1,mid+1,r,L,R));
        return res;
    }

    inline int Query(int l,int r,int y){
        if(l==r){
            if(query(1,1,n,l,l)<=y) return l;
            return -1;
        }
        int mid=l+r>>1;
        if(query(1,1,n,l,mid)<=y) return Query(l,mid,y);
        else if(query(1,1,n,mid+1,r)<=y) return Query(mid+1,r,y);
        else return -1;
    }

}sg;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    while(q--){
        char op;
        cin>>op;
        if(op=='M'){
            int x,a;
            cin>>x>>a;
            sg.change(1,1,n,a,x);
        }else{
            int y,b;
            cin>>y>>b;
            cout<<sg.Query(b,n,y)<<'\n';
        }
    }

    return 0;
}

D. Portal

这道题中，人在某个各自时有两种移动方式：

普通移动：走到上下左右相邻的非墙格子，代价为 $1$ 。
传送：从当前位置向两个方向开枪，建立两个传送门；选择其中一个作为起点门，走到它旁边，再传送到另一个门，代价为： $走到起点传送门的距离 + 1$

要实现高效的最短路转移，必须在 $O(1)$ 的时间内知道：从当前格子 $(i,j)$ 向四个方向射击，对应的传送门分别建在哪个格子，以及自己走过去要花多少步。

用 $b[i][j][k]$ 表示：从格子 $(i,j)$ 出发，沿方向 k 走到“紧邻着墙的那个空地”所需的步数（即射击产生的传送门落脚点）。其中 $k$ 分别对应： $0$ : 右, $1$ : 下, $2$ : 左, $3$ : 上，再对每种方向扫一遍就可以预处理出某一格子能得到的传送门位置是哪些。

于是，剩下的问题就是求最短路了，我们只要用一下求最短路的变体，便能求出答案，代码中用的是 SPFA 求最短路。

点击展开代码

代码：

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

const int N=505,inf=0x3f3f3f3f;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int n,m,sx,sy,tx,ty;
int vis[N][N],dis[N][N],b[N][N][4];
char ch[N][N];
struct node{int x,y;};

void bfs()
{
	memset(dis,0x3f,sizeof dis),dis[sx][sy]=0;
	queue<node> q;q.push({sx,sy}),vis[sx][sy]=1;
	while(!q.empty()){
		node f=q.front();q.pop(),vis[f.x][f.y]=0;
		for(int i=0;i<4;i++){
			int nx=f.x+dx[i],ny=f.y+dy[i];
			if(ch[nx][ny]!='#'&&dis[f.x][f.y]+1<dis[nx][ny]){
				dis[nx][ny]=dis[f.x][f.y]+1;
				if(!vis[nx][ny]) q.push({nx,ny}),vis[nx][ny]=1;
			}
		}
		for(int i=0;i<4;i++){
			int d=b[f.x][f.y][i],mi=inf,nx=f.x+dx[i]*d,ny=f.y+dy[i]*d;
			for(int j=0;j<4;j++)
				if(i!=j) mi=min(mi,b[f.x][f.y][j]);
			mi+=dis[f.x][f.y]+1;
			if(dis[nx][ny]>mi){
				dis[nx][ny]=mi;
				if(!vis[nx][ny]) vis[nx][ny]=1,q.push({nx,ny});
			}
		}
	}
}

int main()
{
    cin>>n>>m;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
    {
        cin>>ch[i][j];
        if(ch[i][j]=='C') sx=i,sy=j;
        if(ch[i][j]=='F') tx=i,ty=j;
    }
	for(int i=1;i<=n;i++){
        for(int j=m;j;j--)
        if(ch[i][j]=='#') b[i][j][0]=-1;
        else b[i][j][0]=b[i][j+1][0]+1;
    }
	for(int j=1;j<=m;j++){
        for(int i=n;i;i--)
        if(ch[i][j]=='#') b[i][j][1]=-1;
        else b[i][j][1]=b[i+1][j][1]+1;
    }
	for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
        if(ch[i][j]=='#') b[i][j][2]=-1;
        else b[i][j][2]=b[i][j-1][2]+1;
    }
	for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++)
        if(ch[i][j]=='#') b[i][j][3]=-1;
        else b[i][j][3]=b[i-1][j][3]+1;
    }
	bfs();
	if(dis[tx][ty]==inf) puts("nemoguce");
	else cout<<dis[tx][ty]<<"\n";

    return 0;
}

A. Lozinke​

B. Mate​

C. Deda​

D. Portal​

A. Lozinke

B. Mate

C. Deda

D. Portal