国庆day3考试总结--下午

· · 个人记录

problem A

错误点

考场写出了拓扑写法，但是错了却A了8个点(真水)，正确写法应该是在求拓扑序的同时枚举26个字母，每个都要判断，然后用dp转移转移方程两个

if(b[tmp]==j)f[tmp][j]=max(f[tmp][j],f[k][j]+1);
else f[tmp][j]=max(f[tmp][j],f[k][j]);

这里的f就是dp

problem A 正确代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,in[N],ans[N],tong[N],cnt;
string s;
vector<int> g[N];
void topu_sort()
{
queue<int> q;
for(int i=1;i<=n;i++)
{
if(in[i]==0)q.push(i);
}
int cnt=0;
while(!q.empty())
{
int cur=q.front();
q.pop();
for(int i=0;i<g[cur].size();i++)
{
int nxt=g[cur][i];
in[nxt]--;
if(in[nxt]==0)
{
ans[nxt]=max(ans[nxt],ans[cur]+1);
q.push(nxt);
}
}
}
int maxn=-1e18;
for(int i=1;i<=n;i++)maxn=max(maxn,ans[i]);
if(maxn<=1)cout<<-1;
else cout<<maxn;
return ;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
g[x].push_back(y);
in[y]++;
}
topu_sort();
return 0;
}

problem B

错误点

for(int j=2;j<=n-1;j++)
{
g[s[j]].push_back(s[j+1]);
in[s[j+1]]++;
}

这个代码是正确的，但是我原来思路是一样的，但是我把所有的j都写成i了，其次还有没有清空，所以错了

正确思路

除了第一个人，其余全部按顺序建边，然后跑一遍拓扑，判断是否有环即可

if(cnt==n)cout<<"YES";
else cout<<"NO";

problem B正确代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,in[N],s[N],k;
vector<int> g[N];
stack<int> st;
int mp[N];
void topu_sort()
{
int cnt=0;
queue<int> q;
for(int i=1;i<=n;i++)
{
if(in[i]==0)q.push(i);
}
while(!q.empty())
{
int cur=q.front();
q.pop();
cnt++;
for(int i=0;i<g[cur].size();i++)
{
int nxt=g[cur][i];
in[nxt]--;
if(in[nxt]==0)q.push(nxt);
}
}
if(cnt==n)cout<<"YES\n";
else cout<<"NO\n"; 
return ;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--)
{
cin>>n>>k;
for(int i=1;i<=n;i++)in[i]=0,g[i].clear();
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
cin>>s[j];
} 
for(int j=2;j<=n-1;j++)
{
g[s[j]].push_back(s[j+1]);
in[s[j+1]]++;
}
}
topu_sort();
}
return 0;
}

problem C

错误点

写的暴力bfs，所以是思路错误(37pts)

正确思路

首先反向建图，然后直接跑拓扑,最后反向输出即可AC

problem C 正确代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int in[N],n,m,flag,a[N],nn;
vector<int>g[N];
priority_queue<int>q; 
void topo()
{
for (int i=1;i<=n;i++)
{
if(in[i]==0)q.push(i);
}
while(!q.empty())
{
int u=q.top();
q.pop();
if(flag)a[++nn]=u;
if(u==1)flag=1;
for (int i=0;i<g[u].size();i++)
{
int nxt=g[u][i];
in[nxt]--;
if(in[nxt]==0)q.push(nxt);
}
}
}
signed main()
{
cin>>n;
for (int i=1,x;i<=n;i++)
{
cin>>x;
for (int j=1,u;j<=x;j++)
{
cin>>u;
in[u]++;
g[i].push_back(u);
}
}
topo();
for(int i=nn;i>=1;i--)cout<<a[i]<<' ';
return 0;
}

problem D

错误点

由于存边存反导致入度存错导致cnt答案求错，所以我把这3个点一改就AC了666

problem D 正确代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,du[N],ans[N],tong[N];
string s;
vector<int> g[N];
void topu_sort()
{
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(du[i]==0)q.push(i);
    }
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(auto y:g[t])
        {
            du[y]--;
            if(du[y]==0)q.push(y);
        }
    }
    return ;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        du[u]++;
        g[v].push_back(u); 
    }
    topu_sort();
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(du[i]!=0)ans++;
    }
    cout<<ans;
    return 0;
}

END