专栏文章

10.6考试总结

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

文章操作

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

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

题目总结

T1

错误原因：

dp用的一维，想得太简单了

正确思路

用dp[i][j]记录每个从上个点走到i这里，j字母出现了多少次。跑拓扑时同时记录，最后求最大值。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
int n,m,in[N],cnt,vis[N],dp[500000][30];
vector<int> g[N];
queue<int> q;
void topu(){
	for(int i=1;i<=n;i++){
		if(in[i]==0){
			q.push(i);
		}
	}	
	while(!q.empty()){
		int x=q.front();
		q.pop();
		cnt++;
		for(auto y : g[x]){
			for(int j=1;j<=26;j++){
				if(vis[y]==j) dp[y][j]=max(dp[y][j],dp[x][j]+1);
				else dp[y][j]=max(dp[y][j],dp[x][j]);
			}
			in[y]--;
			if(in[y]==0) q.push(y);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		char c; cin>>c;
		vis[i]=c-'a'+1;
		dp[i][vis[i]]++;
	}
	for(int i=1;i<=m;i++){
		int x,y; cin>>x>>y;
		g[x].push_back(y);
		in[y]++;
	}
	topu();
	if(cnt<n) cout<<-1;
	else{
		int ans=-1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=26;j++)
				ans=max(dp[i][j],ans);
		cout<<ans;
	}
	return 0;
}

T2

正确思路

这题看懂就很水，我们不看每组第一个，然后让后面的前后建边，然后跑拓扑判环，没环yes有环no

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
int n,k,in[N],cnt;
vector<int> g[N],x[N];
void topu(){
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(in[i]==0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		cnt++;
		for(int i=0;i<g[x].size();i++){
			int nx=g[x][i];
			in[nx]--;
			if(in[nx]==0) q.push(nx);
		}
	}
}
void solve(){
	cin>>n>>k;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=n;j++){
			int s; cin>>s;
			x[i].push_back(s);
			if(j>2){
				g[x[i][j-2]].push_back(x[i][j-1]);
				in[x[i][j-1]]++;
//				cout<<x[i][j-2]<<' '<<x[i][j-1]<<endl;
			}
		}
//		for(auto c : x[i]){
//			cout<<c<<' ';
//		}
	}
	topu();
	if(cnt==n) cout<<"YES\n";
	else cout<<"NO\n";
	for(int i=1;i<=n;i++) g[i].clear();
	for(int i=1;i<=k;i++) x[i].clear();
	for(int i=1;i<=n;i++) in[i]=0;
	cnt=0;
	return ;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

T3

错误原因

没认真写最后来不及了，第二题磕了一小时

正确思路

反向建图，然后跑一遍拓扑不加第一个点，然后再跑一遍就剩下之和1关联的了，最后反向输出。
也能用dfs，更简单，先建图，然后跑一个从1开始的dfs，最后反向输出。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
int vis[N],n;
vector<int> g[N];
void dfs(int x){
	vis[x]=1;
	for(int i=0;i<g[x].size();i++){
		int nx=g[x][i];
		if(!vis[nx]) dfs(nx);
	}
	if(x!=1) cout<<x<<' ';
	return ;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int c; cin>>c;
		for(int j=1;j<=c;j++){
			int x; cin>>x;
			g[i].push_back(x);
		}
	}
	dfs(1);
	return 0;
}

T4

错误原因

同上

正确思路

纯板子，因为要看哪些点在环上，所以统计出过队的，剩下的就是不能进队，也就是有环的，全程只改一个n-cnt，真不知道考试时脑子咋了。

AC Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
int n,m,in[N],cnt,vis[N];
vector<int> g[N];
void topu(){
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(in[i]==0){
			q.push(i);
			vis[i]=1;
		}
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		cnt++;
		for(int i=0;i<g[x].size();i++){
			int nx=g[x][i];
			in[nx]--;
			if(in[nx]==0) q.push(nx);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y; cin>>x>>y;
		g[y].push_back(x);
		in[x]++;
	}
	topu();
	cout<<n-cnt;
	return 0;
}

总结

这次事件没把握好，下次要注意。

评论

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

正在加载评论...