526互联

AtCoder Beginner Contest 299(E,F)

发布时间 2023-05-27 16:42:28作者: righting

AtCoder Beginner Contest 299(E,F)

E （最短路）

E

题目大意为有\(n\)个点和\(m\)条边，我们我个这些点匹配颜色（有两种颜色），但是要满足下面的条件

必须由一个点的颜色是\(1\)

然后给出\(k\)点限制

对于\(p_i\)这一个点，离他最近的一个颜色为\(1\)的点的最近距离为\(d_i\)

既然知道某个点距离\(1\)的最短路为\(d\)，那么从这个点出发最小距离小于\(d\)的点，都一定不能是\(1\),我们可以预先处理出那些点一定是不能是\(1\)的，然后再从这个点出发找，找到一个距离为\(d\)且可以为\(1\)的点，否则找不到，则输出\(-1\)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=3e5+10;
const int mod=998244353;
int n,m;
vector<int>g[maxn];
vector<int>color,forbid;
int k;
vector<pair<int,int>>op;
void bfs1(int s,int d)
{
    vector<int>dis(n+1,inf);
    vector<bool>vis(n+1,false);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    dis[s]=0;
    q.push({dis[s],s});
    while (!q.empty())
    {
        auto [dd,u]=q.top();
        q.pop();
        if(dd>d) break;
        if(vis[u]) continue;
        vis[u]=true;
        if(dd<d)
        {
            forbid[u]=1;
        }
        for (auto v:g[u])
        {
            if(dis[v]>dis[u]+1)
            {
                dis[v]=dis[u]+1;
                q.push({dis[v],v});
            }
        }
    }
    return ;
}
bool bfs2(int s,int d)
{
    vector<int>dis(n+1,inf);
    vector<bool>vis(n+1,false);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    dis[s]=0;
    q.push({dis[s],s});
    while (!q.empty())
    {
        auto [dd,u]=q.top();
        q.pop();
        if(dd>d) break;
        if(dd==d&&!forbid[u])
        {
            color[u]=1;
            return true;
        }
        if(vis[u]) continue;
        vis[u]=true;
        for (auto v:g[u])
        {
            if(dis[v]>dis[u]+1)
            {
                dis[v]=dis[u]+1;
                q.push({dis[v],v});
            }
        }
    }
    return false;
}
signed main ()
{
    cin>>n>>m;
    color.resize(n+1,0);
    forbid.resize(n+1,0);
    for (int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin>>k;
    for (int i=1;i<=k;i++)
    {
        int s,d;
        cin>>s>>d;
        op.push_back({s,d});
        bfs1(s,d);
    }
    bool yes=true;
    for (auto [s,d]:op)
    {
        if(bfs2(s,d))
        {
            continue;
        }
        else 
        {
            yes=false;
            break;
        }
    }
    if(yes)
    {
        cout<<"Yes\n";
        if(k==0) color[1]=1;
        for (int i=1;i<=n;i++)
        {
            cout<<color[i];
        }
        cout<<"\n";
    }
    else 
    {
        cout<<"No\n";
    }
    system ("pause");
    return 0;
}

F（dp,子串）

F

这个题的大意就是给出一个字符串，找到一个非空字符串\(t\),可以得到一个\(s\)为\(tt\),且\(s\)为题目给出的字符串的子串

子串：原来的字符串删除若干个字符

这就代表着\(tt\)里面的字符的顺序只要是符合要求的即可

然后我们可以看到这个\(t\),不断地制造\(t\)

对于一个满足要求的\(tt\),我们需要从原来的字符串里面去找，不如把找\(tt\)转换成在原来的字符串里面找到一前一后一样的子串

对于此时的字符\(now\),此时的位置为\(r\)我们要找到一个\(l\)（这个位置的字符同样是\(now\),是第一个出现该字符的位置，这样就把以\(r\)可以作为\(tt\)的结尾的所有情况都包括了）

我们可以得到一个初状态\(dp[l] [r] =1\),代表着第一个字符串以\(st\)结尾，第二个字符串以\(r\)结尾，前面的都是满足的（初状态只有这一个字符，所以不需要考虑，直接\(dp[l] [r] =1\)

然后我们需要继续深入，往后找后面可以存在的字符,但是后面的前面一个不能超过\(r\)（不然这两个字符串的顺序不是一前一后了，而是相交了），后面不能超过\(n\),

假设\(i,j\)是此时的两个字符串的结尾位置，我们的下一个就在他们位置的后面

假设存在这样一个字符\(k\),\(i\)后面的位置\(nl\)存在，在\(j\)的后面的位置\(nr\)存在

那我们可以得到状态转移方程如下

\[dp[nl][nr]=dp[nl][nr]+dp[i][j] \]

我们取得的答案就是每一个不同结尾，对于此时的位置，只要是结尾的下一个\(now\)字符是\(r\),(这一次刚好是以\(r\)作为界限，\(r\)是第二个的开头，其他的情况，在其他的时候也已经加上了）可以加上这个答案

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=100+10;
const int mod=998244353;
int n;
string s;
void add(int &x,int c)
{
    x+=c;
    if(x>=mod)
    {
        x-=mod;
    }
    return ;
}
signed main ()
{
    cin>>s;
    n=s.size();
    s=" "+s;
    vector<int>pos(26,-1);
    vector<vector<int>>nxt(n+1);
    for (int i=n;i>=1;i--)
    {
        int now=s[i]-'a';  
        nxt[i]=pos;
        pos[now]=i;
    }
    int ans=0;
    for (int st=2;st<=n;st++)
    {
        int now=s[st]-'a';
        vector<vector<int>>dp(n+1,vector<int>(n+1,0));
        int l=pos[now],r=st;
        dp[l][r]=1;
        for (int i=l;i<r;i++)
        {
            for (int j=r;j<=n;j++)
            {
                for (int k=0;k<26;k++)
                {
                    int nl=nxt[i][k];
                    int nr=nxt[j][k];
                    if(nl==-1||nr==-1||nl>=r) continue;
                   add(dp[nl][nr],dp[i][j]);
                }
            }
        }
        for (int i=l;i<r;i++)
        {
            for (int j=r;j<=n;j++)
            {
                if(nxt[i][now]==r)//如果nxt[i][now]小于r的话，前面可能已经加过一次了，大于更是不可能，我们加的只是此时刚好以r作为界限的情况
                {
                    add(ans,dp[i][j]);
                }
            }
        }
    }
    cout<<ans<<"\n";
    system ("pause");
    return 0;
}