D原题链接: codeforces 难度1400

D. jzo 的增高计划 题意:

给定s,求一个s的最长子序列t,满足t的字典序大于s.(即s与t第一个不相同字符的位置i,满足,输出t的长度.

如何找到最长的t呢?

1.t是s的子序列.
2.第一个不同字符的位置满足

我们可以直接枚举s中所有的右括号,当,.那么要构造出这样的t,首先必须满足,因为 是 的子序列.由于题目已经给出s是完美序列,那么就,也就是说只要,就必然可以组成一个完美序列.

#include <bits/stdc++.h>
using namespace std;

int main(){
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        string s;
        cin >> n >> s;
        vector<int> nx(n + 1, n + 1);
        vector<int> suf(n + 1, 0);
        for(int i = n - 1; i >= 0; i--){
            if(s[i] == '(') nx[i] = i;
            else nx[i] = nx[i + 1];
            if(s[i] == '(') suf[i] += 1;
            suf[i] += suf[i + 1];
        }

        int ans = -1;
        for(int i = 0; i < n; i++){
            if(s[i] == ')' and nx[i] <= n){
                int ig = nx[i] - i;
                if(suf[nx[i] + 1] >= ig){
                    ans = max(ans, n - 2 * ig);
                }
            }
        }

        cout << ans << '\n';
    }
}        

copy from cf

事实上本题还有一个结论,就是我们只会浪费s字符串中的一个和.所以事实上答案只有-1或者n-2.

int ans=0;
for(int i=1;i<n;i++)
    {
        if(s[i]==')')
        {
            /*
            这里b数组表示i之后下一个(的位置,c数组是将s中(看成1
            )看成-1的前缀和数组,a数组是i-n有多少个),当你把)换成(时,
            被替换的)原先匹配的(就需要一个新的)去匹配,我选择了bi
            那个位置的(来替换这个),那么就需要bi之后至少要有2个),
            这个意思也就是ci+2.
            */
            if(b[i]!=-1&&a[b[i]]>=max(0,c[i]+2))
            {
                ans = 1;
                break;
            }
            now=0;
        }
    }
    if(ans)
        cout<<n-2<<endl;
    else cout<<-1<<endl;

E原题链接 洛谷绿板

E. 迷宫的试炼 题意:

给定一张无向图,求从1号点到i号点最短路有多少条.

注意到边权都可以看成1,那么当bfs第一次走到i点时就是最短的距离d,那么就可以记表示到i点的最短路有多少条,.

const int mod = 100003;
int h[N],ne[2*M],e[2*M],idx;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void solution::solve()
{
    memset(h,-1,sizeof h);
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;cin>>a>>b;
        if(a==b)continue;
        add(a,b),add(b,a);
        // 建图
    }

    vector<int>dis(n+1,INF);

    auto dijkstra=[&](int st)
    {
        queue<int>q;
        vector<bool>vis(n+1,0);
        q.push(st);
        dis[st]=0;
        while(q.size())
        {
            int p = q.front();
            q.pop();

            if(vis[p])continue;
            vis[p]=1;
            for(int i=h[p];~i;i=ne[i]) //遍历边
            {
                int v=e[i];
                if(dis[v]>dis[p]+1)
                {
                    dis[v]=dis[p]+1;
                    q.push(v);
                }
            }
            
        }
    };
    dijkstra(1);
    vector<int>f(n+1,-1);
	// 其实可以直接在dijksra中dp,这里写了个dfs写麻烦了
    function<int(int)>dfs=[&](int u)
    {
        if(f[u]!=-1)return f[u];
        f[u]=0;
        for(int i=h[u];~i;i=ne[i])
        {
            int v=e[i];
            if(dis[v]==dis[u]-1)
                f[u] = (f[u] + dfs(v))%mod;
        }
        return f[u];
    };
    f[1]=1;
    for(int i=1;i<=n;i++)
        if(dis[i]==INF)
            f[i]=0;
    for(int i=1;i<=n;i++)
        cout<<dfs(i)<<endl;
}

由于题解代码写得较早,事实上是不需要dfs去dp的,可以在bfs中dp,可以去看第一名的代码.