专栏文章

国庆day3考试总结--下午

CCrash_Man_CHN
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minojq5e
此快照首次捕获于
2025/12/02 05:47
3 个月前
此快照最后确认于
2025/12/02 05:47
3 个月前
查看原文

problem A

错误点

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

CPP
#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

错误点

CPP
for(int j=2;j<=n-1;j++)
{
	g[s[j]].push_back(s[j+1]);
	in[s[j+1]]++;
}
这个代码是正确的，但是我原来思路是一样的，但是我把所有的j都写成i了，其次还有没有清空，所以错了

正确思路

除了第一个人，其余全部按顺序建边，然后跑一遍拓扑，判断是否有环即可
CPP
if(cnt==n)cout<<"YES";
else cout<<"NO";

problem B正确代码

CPP
#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 正确代码

CPP
#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 正确代码

CPP
#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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...