AtCoder Beginner Contest 287(C,D,E,F)

C （图）

C

题目大意为\(n\)个点,\(m\)条边，问是否这个图是一条长度为\(n\)的链

这个就直接判断每个点的度，我们发现只存在两个点的度是\(1\)(链的两端)，其余都是\(2\)，我们还需要知道这\(n\)个点都是连通即可，不需要判断环（环的情况不可能其余点都是\(2\),至少是\(3\))

#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>
#include <numeric>
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=2e5+10;
const int mod=998244353;
vector<int>f,d;
int n,m;
int find(int x)
{
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
void merge(int x,int y)
{
    int tx=find(x),ty=find(y);
    if(tx==ty) return ;
    f[ty]=tx;
    return ;
}
signed main ()
{
    cin>>n>>m;
    f.resize(n+1);
    d.resize(n+1);
    iota(f.begin(),f.end(),0);
    for (int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        d[u]++;
        d[v]++;
        merge(u,v);
    }
    if(m!=n-1)
    {
        cout<<"No\n";
        system ("pause");
        return 0;
    }
    int cnt2=0,cnt1=0;
    cnt1=count(d.begin(),d.end(),1);
    cnt2=count(d.begin(),d.end(),2);
    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        if(i==f[i])
        {
            cnt++;
        }
    }
    if(cnt1==2&&cnt2==n-2&&cnt==1)
    {
        cout<<"Yes\n";
    }
    else 
    {
        cout<<"No\n";
    }
    system ("pause");
    return 0;
}

这次竟然\(C\)都没有过，可恶

D（思维）

D

题目大意就是给出一个\(s\)和\(t\)字符串，其中\(s\)的长度\(n\)一定大于\(t\)的长度\(m\),\(m+1\)个询问

对于\(i\)个询问，我们可以把\(s\)的前\(i\)个字符，如果还不够\(m\)个字符，就去取\(m-i\)个后缀，拼接得到一个新的字符串，问这个新的字符串是否和\(t\)是否匹配

对于匹配问题，两个字符串如果是已定字符，如果是一样就可能是可以匹配的，因为我们还会存在一种代表未知字符的\(?\),这个位置可以变成任意字符，所以对于两个已定的字符，如果不一样，那么就是一定不匹配，否则如果存在未知符号，我们可以变成和那个一样的

记录一下我的写法

那么对于两个一样的，我发现只要前面一段存在不匹配的情况后面，后面\(i\)变大，前面的那个不匹配的情况仍然还在，所以还是不匹配的情况，后面的那一段也是同样的

所以，我们提前求出最长的可匹配前缀长度和最长的可匹配后缀的长度

然后这两个长度都有着自己可以满足的\(i\)区间，求并集，即两个条件都满足，前面一段匹配，后面一段匹配，这个区间的\(i\)是\(Yes\),否则是\(No\)

#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=2e5+10;
const int mod=998244353;
string s,t;
int n,m;
signed main ()
{
    cin>>s>>t;
    n=s.size(),m=t.size();
    s=" "+s;
    t=" "+t;
    int pre=0,suf=0;
    for (int i=1;i<=m;i++)
    {
        if(s[i]==t[i])
        {
           pre++;
        }
        else if(s[i]=='?'||t[i]=='?')
        {
            pre++;
        }
        else break;
    }
    for (int i=n,j=m;i>=1&&j>=1;i--,j--)
    {
        if(s[i]==t[j])
        {
           suf++;
        }
        else if(s[i]=='?'||t[j]=='?')
        {
            suf++;
        }
        else 
        {
            break;
        }
    }
    int l=0,r=pre;
    int ll=m-suf,rr=m;
    int L=max(l,ll),R=min(r,rr);
    for (int i=0;i<=m;i++)
    {
        if(i>=L&&i<=R)
        {
            cout<<"Yes\n";
        }
        else 
        {
            cout<<"No\n";
        }
    }
    system ("pause");
    return 0;
}

E(字典树/思维)

E

这个题的大意是有\(n\)个字符串，还有一个\(LCP(s_i,s_j)\),代表着\(s_i\)和\(s_j\)的最长公共前缀长度

每次都会问\(s_i\)和其他的\(s_j\)的\(LCP\)中最大的是哪一个

即

这个题我写了两种不同的写法

第一种是字典树

这个应该很多人都看出来了，但是我对这个字典树还不是很熟练，就没有想到

我们就是把每一个字符都加到字典树里面去，然后去寻找\(s_i\)，但是我们判断的条件是字符数量大于\(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>
#include <numeric>
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=5e5+10;
const int mod=998244353;
string s[maxn];
struct Tire
{
    int val,son[27];
}tr[maxn];
int n;
int idx;
int f(char ch)
{
    int res=ch-'a';
    return res;
}
void init()
{
    for (int i=0;i<=idx;i++)
    {
        tr[i].val=0;
        for (int j=0;j<26;j++)
        {
            tr[i].son[j]=0;
        }
    }
    idx=0;
}
void insert(string s)
{
    int rt=0;
    for (int i=0;i<s.size();i++)
    {
        int now=f(s[i]);
        if(!tr[rt].son[now])
        {
            tr[rt].son[now]=++idx;
        }
        rt=tr[rt].son[now];
        tr[rt].val++;
    }
    return ;
}
int query(string s)
{
    int rt=0;
    for (int i=0;i<s.size();i++)
    {
        int now=f(s[i]);
        rt=tr[rt].son[now];
        if(tr[rt].val<=1)
        {
            return i;
        }
    }
    return s.size();
}
signed main ()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>s[i];
        insert(s[i]);
    }
    for (int i=1;i<=n;i++)
    {
        int ans=query(s[i]);
        cout<<ans<<"\n";
    }
    system ("pause");
    return 0;
}

另外一种写法真的很妙

学自这里

就是他先把字符串按照从到大小的顺序排序，然后我们可以知道两个相邻大小的字典序，他们才是可能最大的最长公共前缀长度（字典序相差越小，最长公共前缀长度越大）

所以我们这个还需要记录下字符串的位置

具体可看代码

#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>
#include <numeric>
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=5e5+10;
const int mod=998244353;
int n;
struct node
{
    int id;
    string s;
}a[maxn];
int ans[maxn];
bool cmp(node x,node y)
{
    return x.s<y.s;
}
int LCP(string s,string t)
{
    int i=0,j=0;
    int res=0;
    while (i<s.size()&&j<t.size())
    {
        if(s[i]==t[j])
        {
            i++;
            j++;
            res++;
        }
        else break;
    }
    return res;
}
signed main ()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i].s;
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    for (int i=1;i<n;i++)
    {
        int p=LCP(a[i].s,a[i+1].s);
        int x=a[i].id;
        int y=a[i+1].id;
        ans[x]=max(ans[x],p);
        ans[y]=max(ans[y],p);
    }
    for (int i=1;i<=n;i++)
    {
        cout<<ans[i]<<"\n";
    }
    system ("pause");
    return 0;
}

F(树形dp)

F

给出一棵树，我们可以选择任意个点，问连通分量为\(x\)时有多少种不同的选择

我树形\(dp\)不是很熟练，没有看出来（太弱了）

一开始是想把\(i\)个连通分量中选择一个点去拿走，然后就会变成\(i+1\)个连通分量，但是对于不同的位置，都是不同的情况，不太可行

上面是我们胡思乱想

下面才是正解

\(dp[u] [j] [0/1]\)代表着以\(u\)为根,连通分量为\(j\),且这一个点\(u\)的选择状态

上面我自己想到的是拆分，而这个是合并

把以\(u\)为根节点的树和以\(v\)为根节点的树合并，这两个点之间通过一条边相连，也就是父子关系，其中两个不同状态的合并，和\(u\)和\(v\)的选择优关

如果这两个点都选择了，那么得到的连通分量为\(i+j-1\)，两个人的连通分量和，但是\(u,v\)连接了两个不同的分量，要减一，其余的都是\(i+j\),\(u,v\)不能够连通，不用减一

然后我们每一次都会枚举不同的连连通分量个数，然后不断的更新

#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>
#include <numeric>
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=5e3+10;
const int mod=998244353;
int n;
int siz[maxn];
vector<int>g[maxn],dp[maxn][2];
void add(int &x,int c)
{
    x+=c;
    if(x>=mod)
    {
        x-=mod;
    }
    return ;
}
void dfs(int u,int fa)
{
    siz[u]=1;
    dp[u][0].resize(2);
    dp[u][0][0]=1;
    dp[u][0][1]=0;
    dp[u][1].resize(2);
    dp[u][1][0]=0;
    dp[u][1][1]=1;
    for (auto v:g[u])
    {
        if(v==fa) continue;
        dfs(v,u);
        vector<int>tmp[2];
        tmp[0].resize(siz[u]+siz[v]+1,0);
        tmp[1].resize(siz[u]+siz[v]+1,0);
        for (int i=0;i<=siz[u];i++)
        {
            for (int j=0;j<=siz[v];j++)
            {
                add(tmp[0][i+j],(dp[u][0][i]*dp[v][0][j])%mod);
                add(tmp[0][i+j],(dp[u][0][i]*dp[v][1][j])%mod);
                add(tmp[1][i+j],(dp[u][1][i]*dp[v][0][j])%mod);
                if(i+j>=1)
                {
                    add(tmp[1][i+j-1],(dp[u][1][i]*dp[v][1][j])%mod);
                }
            }
        }
        	siz[u]+=siz[v];
            dp[u][0]=tmp[0],dp[u][1]=tmp[1];
    }
    return ;
}
signed main ()
{
    cin>>n;
    for (int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    for (int i=1;i<=n;i++)
    {
        int ans=dp[1][0][i];
        add(ans,dp[1][1][i]);
        cout<<ans<<"\n";
    }
    system ("pause");
    return 0;
}

本栏目推荐文章
• AtCoder World Tour 2022 B The Greatest Two
• 2021-2022 ICPC Northwestern European Regional Programming Contest (NWERC 2021)
• AtCoder Beginner Contest 335 G Discrete Logarithm Problems
• 2023 United Kingdom and Ireland Programming Contest (UKIEPC 2023)
• 2022 Jiangsu Collegiate Programming Contest
• AtCoder Regular Contest 138
• 2020-2021 ACM-ICPC, Asia Seoul Regional Contest
• 2021 Jiangsu Collegiate Programming Contest
• AtCoder Beginner Contest 335 (Sponsored by Mynavi)
• 2023-2024 ACM-ICPC Latin American Regional Programming Contest

Beginner AtCoder Contest 287beginner atcoder contest 287 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 315 beginner atcoder contest 334