10.6考试总结

· · 个人记录

题目总结

T1

错误原因：

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

正确思路

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

AC Code

#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

#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

#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

#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;
}

总结

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