题解

12 条题解

  • 2
    @ 2016-07-15 12:48:32
    #include <bits/stdc++.h>
    using namespace std;
    bool a[1001],f[1001];
    int tp_r[1001],tp_b[1001],st[1001];
    bool fl[1001][1001];
    int n,m,q,ans,top;
    inline void init(){
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cin>>n>>m;
        for(register int i=1,q;i<=m;i++){
            memset(a,0,sizeof(a));
            cin>>q;
            for(register int j=1;j<=q;j++)
              cin>>tp_b[j],a[tp_b[j]]=1;
            for(register int j=tp_b[1];j<=tp_b[q];j++)
                if(!a[j])
                    for(register int k=1;k<=q;k++)
                        if(!fl[j][tp_b[k]])
                           fl[j][tp_b[k]]=1,tp_r[tp_b[k]]++;
        }
    }
    inline void getAns(){
        ans=0;
        while(true){
            top=0;
            for(int i=1;i<=n;i++)
                if(!tp_r[i]&&!f[i])
                    st[++top]=i,f[i]=1;
            if(top==0)break;
            for(int k=1;k<=top;k++){
                for(int i=1;i<=n;i++) 
                    if(fl[st[k]][i]) fl[st[k]][i]=0,tp_r[i]--;
            }
            ans++;
        }
        cout<<ans;
    }
    int main(int argc, char const *argv[]){
        // freopen("in.in","r",stdin);
        init();
        getAns();
        return 0;
    }
    
  • 1
    @ 2021-08-30 09:39:00
    #include <bits/stdc++.h>
    using namespace std;
    #define max(x,y) ((x)>(y)?(x):(y))
    #define rpt(n) for(register int ttxyc=0;ttxyc<(n);++ttxyc)
    
    inline int read()
    {
        register int x=0,t=0;
        register char c=getchar();
        for(;c<'0'||c>'9';t|=c=='-',c=getchar());
        for(; c>='0'&&c<='9'; x=(x<<3)+(x<<1)+(c^48),c=getchar());
        return t?-x:x;
    }
    
    int n,m,a[1000],f[1000][1000],s[1000];
    bool have[1000][1000];
    int main()
    {
        n=read();m=read();
        rpt(n)a[ttxyc]=1;
        rpt(m)
        {
            s[ttxyc]=read();
            for(register int i=0; i<s[ttxyc]; ++i)
                f[ttxyc][i]=read()-1,have[ttxyc][f[ttxyc][i]]=1;
        }
        for(;;)
        {
            bool cd=0;
            rpt(m)
            {
                int maxn=0;
                for(register int i=f[ttxyc][0];i<=f[ttxyc][s[ttxyc]-1];++i)
                    if(!have[ttxyc][i])
                        maxn=max(maxn,a[i]);
                ++maxn;
                for(register int i=0;i<s[ttxyc];++i)
                    if(a[f[ttxyc][i]]<maxn)
                        a[f[ttxyc][i]]=maxn,cd=1;
            }
            if(!cd)
                break;
        }
        int maxn=0;
        rpt(n)maxn=max(maxn,a[ttxyc]);
        cout<<maxn;
    }
    
  • 1
    @ 2017-10-31 17:22:44
    #include <cstdio>
    #include <cctype>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    using namespace std;
    struct EDGE
    {
        int to;
        int next;
    }e[3000001];
    #define MAX 1010
    int n,m,s,head[MAX],cnt,ans;
    int a[MAX],in[MAX],is[MAX],dep[MAX];
    bool vis[MAX][MAX];
    inline int read()
    {
        int res=0,k=1;
        char x=getchar();
        if(x=='-') k=-k;
        while(x>='0'&&x<='9'||x=='-')
        {
            res*=10;
            res+=(x-'0');
            x=getchar();
        }
        return res*k;
    }
    void add(int u,int v)
    {
        e[++cnt].to=v;
        e[cnt].next=head[u];
        head[u]=cnt;
    }
    void topsort()
    {
        queue<int> q;
        for(int i=1;i<=n;i++)
            if(!in[i])
            {
                q.push(i);
                dep[i]=1;           
            }
        while(q.size())
        {
            int tt=q.front(); q.pop();
            for(int i=head[tt];i;i=e[i].next)
            {
                int v=e[i].to;
                dep[v]=dep[tt]+1;
                ans=max(ans,dep[v]);
                in[v]--;
                if(!in[v]) q.push(v);
            }
        }
    }
    int main()
    {
        n=read(),m=read();
        for(int i=1;i<=m;i++)
        {
            memset(a,0,sizeof(a));
            memset(is,0,sizeof(is));
            s=read();
            for(int j=1;j<=s;j++)
            {
                a[j]=read();
                is[a[j]]=1;
            }
            for(int j=a[1]+1;j<=a[s];j++)
                if(!is[j])
                    for(int p=1;p<=s;p++)
                        if(!vis[j][a[p]])
                        {
                            in[a[p]]++;
                            add(j,a[p]);
                            vis[j][a[p]]=1;
                        }
    
        }
        topsort();
        printf("%d\n",ans);
        return 0;
    }
    

    topsort+bfs

  • 0

    求一个最长的拓扑序
    #include <iostream>
    #include <algorithm>
    #include <queue>
    #include <vector>
    #include <stack>
    #include <cstring>
    using namespace std;
    int n,m,station_number[1005],station_start[1005],station_end[1005],park_number[1005][1005],indegree[1005],f[1005],closest_station=1000,farthest_station;
    bool park_judge[1005][1005];
    vector<int> g[1005];
    stack<int> topology;
    int judge_level(int x,int y)
    {
    int s,t;
    if(station_start[x]>=station_end[y]||station_start[y]>=station_end[x])
    return 0;
    s=max(station_start[x],station_start[y]);
    t=min(station_end[y],station_end[x]);
    if(park_number[x][t]-park_number[x][s-1]>park_number[y][t]-park_number[y][s-1])
    return 2;
    else if(park_number[x][t]-park_number[x][s-1]<park_number[y][t]-park_number[y][s-1])
    return 1;
    else
    return 0;

    }
    int main()
    {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    cin>>station_number[i];
    cin>>station_start[i];
    park_judge[i][station_start[i]]=1;
    park_judge[0][station_start[i]]=1;
    closest_station=min(closest_station,station_start[i]);
    for(int j=2;j<station_number[i];j++)
    {
    int x;
    cin>>x;
    park_judge[i][x]=1;
    park_judge[0][x]=1;
    }
    cin>>station_end[i];
    park_judge[i][station_end[i]]=1;
    park_judge[0][station_end[i]]=1;
    farthest_station=max(farthest_station,station_end[i]);
    for(int j=station_start[i];j<=station_end[i];j++)
    park_number[i][j]=park_number[i][j-1]+park_judge[i][j];

    for(int j=1;j<i;j++)
    {
    int who;
    who=judge_level(i,j);
    if(who==1)
    {
    g[j].push_back(i);
    indegree[i]++;
    }

    else if(who==2)
    {
    g[i].push_back(j);
    indegree[j]++;
    }

    }
    }
    for(int i=1;i<=m;i++)
    {
    if(indegree[i]==0)
    {
    topology.push(i);
    f[i]=1;
    }
    }
    int ans=0;
    while(!topology.empty())
    {
    int p=topology.top();
    topology.pop();
    for(int i=0;i<g[p].size();i++)
    {
    f[g[p][i]]=max(f[g[p][i]],f[p]);
    if(--indegree[g[p][i]]==0)
    {
    f[g[p][i]]++;
    topology.push(g[p][i]);
    }
    }
    ans=max(ans,f[p]);
    }
    bool rest=0;
    for(int i=closest_station;i<=farthest_station;i++)
    if(park_judge[0][i]==0)
    {
    rest=1;
    break;
    }

    cout<<ans+rest<<endl;
    return 0;
    }

  • 0
    @ 2016-09-15 21:47:43

    裸的拓扑都能过,不可理喻2333
    评测结果
    编译成功

    foo.cpp: In function 'int main()':
    foo.cpp:45:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < adj[i].size(); j++)
    ^
    foo.cpp:60:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < adj[u].size(); i++)
    ^
    测试数据 #0: Accepted, time = 15 ms, mem = 1604 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1600 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1632 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 1632 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1620 KiB, score = 10
    测试数据 #5: Accepted, time = 62 ms, mem = 4280 KiB, score = 10
    测试数据 #6: Accepted, time = 296 ms, mem = 4244 KiB, score = 10
    测试数据 #7: Accepted, time = 125 ms, mem = 4164 KiB, score = 10
    测试数据 #8: Accepted, time = 125 ms, mem = 4036 KiB, score = 10
    测试数据 #9: Accepted, time = 140 ms, mem = 1600 KiB, score = 10
    Accepted, time = 778 ms, mem = 4280 KiB, score = 100

  • 0
    @ 2016-08-30 18:26:32

    pj居然会考差分约束。。不可理喻。。
    ```
    测试数据 #0: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 828 KiB, score = 10
    测试数据 #6: Accepted, time = 31 ms, mem = 824 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 824 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 824 KiB, score = 10
    测试数据 #9: Accepted, time = 31 ms, mem = 820 KiB, score = 10

    Accepted, time = 77 ms, mem = 828 KiB, score = 100

    用bitset优化一下,把预处理的复杂度降下来,后面就随你玩了。
    c++
    #include <bits/stdc++.h>
    using namespace std;

    inline int read()
    {
    int c, a = 0;
    do c = getchar(); while(!isdigit(c));
    while(isdigit(c)) {
    a = a*10+c-'0';
    c = getchar();
    }
    return a;
    }

    bitset<1001> dat[1001], tmp[1001];
    int n, m, t[1001];
    #define var register size_t
    inline int work()
    {
    var x, bg, ed;
    bitset<1001> tst, lr;
    for (var i = 1; i <= m; i++) {
    tst = 0;
    x = read();
    for (var j = 1; j <= x; j++) {
    t[j] = read();
    tst[t[j]] = 1;
    }
    lr = ((tmp[t[x]]^tmp[t[1]-1])^tst);
    for (var j = 1; j <= x; j++)
    dat[t[j]] |= lr;
    }
    int rd[1001], mk[1005], ans = 1, topr[1005], tp = 0;
    queue<int> stk;
    memset(rd, 0, sizeof rd);
    memset(mk, 0, sizeof mk);
    for (var i = 1; i <= n; i++)
    for (var j = 1; j <= n; j++)
    if (dat[i][j])
    rd[j]++;
    for (var i = 1; i <= n; i++)
    if (!rd[i]) {
    stk.push(i);
    mk[i] = 1;
    }
    while (!stk.empty()) {
    int t = stk.front();
    stk.pop();
    topr[++tp] = t;
    // cout << t << " ";
    for (var k = 1; k <= n; k++)
    if (dat[t][k] && !mk[k]) {
    rd[k]--;
    //cout <<k << " " <<rd[k] << endl;
    if (!rd[k]) {
    stk.push(k);
    mk[k] = 1;
    }
    }
    }
    int dis[1005];
    //cout << endl;
    memset(dis, 0, sizeof dis);
    for (var i = 1; i <= n; i++) {
    int to = topr[i];
    dis[to] = max(dis[to], 1);
    for (var j = 1; j <= n; j++)
    if (dat[j][to])
    dis[to] = max(dis[to], dis[j]+1);
    ans = max(ans, dis[to]);
    }
    return ans;
    }// O(n^2*|bitset|)

    int main()
    {
    tmp[0] = 0;
    for (int i = 1; i <= 1000; i++) {
    tmp[i] = tmp[i-1];
    tmp[i][i] = 1;
    // 类似前缀和,显然tmp[i]^tmp[j-1]会生成i..j全为1其他全为0的序列
    } // O(n)
    n = read(); m = read();
    cout << work() << endl;
    return 0;
    }
    ```
    本以为会卡常,没想到。。。目测我是历史最快了吧。。

  • 0
    @ 2014-10-29 20:21:06

    P1851车站分级
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1851 车站分级
    递交时间 2014-10-29 20:04:20
    代码语言 C++
    评测机 VijosEx
    消耗时间 1961 ms
    消耗内存 5208 KiB
    评测时间 2014-10-29 20:04:23

    评测结果

    编译成功

    foo.cpp: In function 'int dfs(int)':
    foo.cpp:33:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for( i = 0 ; i < table[a].next.size() ; i++ )
    ^

    测试数据 #0: Accepted, time = 15 ms, mem = 1284 KiB, score = 10

    测试数据 #1: Accepted, time = 15 ms, mem = 1292 KiB, score = 10

    测试数据 #2: Accepted, time = 15 ms, mem = 1652 KiB, score = 10

    测试数据 #3: Accepted, time = 15 ms, mem = 1652 KiB, score = 10

    测试数据 #4: Accepted, time = 15 ms, mem = 1656 KiB, score = 10

    测试数据 #5: Accepted, time = 202 ms, mem = 5208 KiB, score = 10

    测试数据 #6: Accepted, time = 873 ms, mem = 5192 KiB, score = 10

    测试数据 #7: Accepted, time = 312 ms, mem = 5208 KiB, score = 10

    测试数据 #8: Accepted, time = 265 ms, mem = 5208 KiB, score = 10

    测试数据 #9: Accepted, time = 234 ms, mem = 5196 KiB, score = 10

    Accepted, time = 1961 ms, mem = 5208 KiB, score = 100

    代码

    #include <iostream>
    #include <cmath>
    #include <stdio.h>
    #include <algorithm>
    #include <string.h>
    #include <vector>

    using namespace std;

    int n , m;
    int sta[1000 + 2];
    int station[1000 + 2];
    int num;
    int flag;
    int i , j , k;

    struct Node
    {
    vector < int > next;
    bool saved[1000 + 2];
    };

    Node table[1000 + 2];

    int dfs( int a )
    {
    if( sta[a] != -1 )
    return sta[a];
    if( !table[a].next.size() )
    return 0;
    int i , j;
    int maxd = -1;
    for( i = 0 ; i < table[a].next.size() ; i++ )
    {
    j = dfs( table[a].next[ i ] ) + 1;
    if( j > maxd )
    maxd = j;
    }
    sta[a] = maxd;
    return sta[a];
    }

    int main()
    {
    while( scanf( "%d %d" , &n , &m ) != EOF )
    {
    memset( table , 0 , sizeof( table ) );
    for( i = 1 ; i <= m ; i++ )
    table[i].next.reserve( 1000 );
    for( i = 1 ; i <= m ; i++ )
    {
    scanf( "%d" , &num );
    memset( station , 0 , sizeof( station ) );
    for( j = 1 ; j <= num ; j++ )
    {
    scanf( "%d" , &sta[j] );
    station[ sta[j] ] = 1;
    }
    for( j = sta[1] ; j <= sta[num] ; j++ )
    {
    flag = 0;
    if( !station[j] )
    for( k = 1 ; k <= num ; k++ )
    {
    if( !table[j].saved[ sta[k] ] )
    table[j].next.push_back( sta[k] );
    table[j].saved[ sta[k] ] = 1;
    }
    }
    }
    flag = 0;
    memset( sta , -1 , sizeof( sta ) );
    for( i = 1 ; i <= n ; i++ )
    flag = max( dfs( i ) , flag );
    flag++;
    printf( "%d\n" , flag );
    }
    return 0;
    }

    不用拓扑排序,带记忆化的dfs照样过

  • 0
    @ 2014-10-28 21:11:40

    NOIP2014赛前AC留念
    (首先想用最长路写,然后考虑到复杂度n³……SPFA也只能写到60分;堆优化的dijkstra写了将近100行竟然跪了。
    好吧还是要学会多用最基础的拓扑排序吧……毕竟PJ 的题没那么难)
    var level,s,n,m,i,j:longint;
    flag:boolean;
    use,choose:array[0..1001] of boolean;
    num,du:array[0..1001] of longint;
    map:array[0..1001,0..1001] of longint;
    f:array[0..1001,0..1001] of boolean;
    procedure build(k:longint);
    var i:longint;
    begin
    for i:=1 to s do
    begin
    if not f[k,num[i]] then begin
    inc(map[k,0]);
    map[k,map[k,0]]:=num[i];
    f[k,num[i]]:=true;
    inc(du[num[i]]);
    end;
    end;
    end;

    begin
    //assign(input,'t7.in');
    //assign(output,'t7.out');
    //reset(input);
    //rewrite(output);
    readln(n,m);
    for i:=1 to m do
    begin
    read(s);
    fillchar(use,sizeof(use),false);
    fillchar(num,sizeof(num),0);
    for j:=1 to s do
    begin
    read(num[j]);
    use[num[j]]:=true;
    end;
    for j:=num[1] to num[s] do
    if not use[j] then build(j);
    end;
    level:=0;
    fillchar(use,sizeof(use),false);
    flag:=true;
    while flag do begin
    inc(level);
    //flag:=false;
    fillchar(choose,sizeof(choose),false);
    for i:=1 to n do
    if (du[i]=0) and (not use[i]) and (not choose[i]) then
    begin
    for j:=1 to map[i,0] do
    begin
    dec(du[map[i,j]]);
    choose[map[i,j]]:=true;
    end;
    use[i]:=true;
    end;
    flag:=false;
    for i:=1 to n do
    if du[i]<>0 then flag:=true;
    end;
    writeln(level+1);
    //close(input);
    //close(output);
    end.

  • 0
    @ 2014-10-02 14:41:47

    P党:很简单的题,只是一直tle一个点,换成邻接表还是一样,于是用了inline……结果就过了……orz
    czl大神:“语言歧视题”

  • 0
    @ 2014-02-17 21:02:22

    只要你写得好,裸拓扑、裸FOLYED皆可以满!相信自己。
    另外,庆祝100道,和蒋世彪在同一学校。。

    • @ 2014-07-25 20:28:17

      跪烂神犇……

  • 0
    @ 2013-11-29 19:47:32

    AC的贪心

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #define MAXN 1001
    using namespace std;
    int b[MAXN],c[MAXN][MAXN],s[MAXN],d[MAXN];
    bool a[MAXN][MAXN];
    int main()
    {
    freopen("level.in","r",stdin);
    freopen("level.out","w",stdout);
    memset(a,false,sizeof(a));
    memset(b,-1,sizeof(b));
    int n,m,l,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
    scanf("%d",&s[i]);
    for(int j=1;j<=s[i];j++) scanf("%d",&c[i][j]);
    }
    for(int i=1;i<=m;i++){
    for(int j=c[i][1];j<=c[i][s[i]];j++) b[j]=0;
    }
    for(int i=1;i<=m;i++){
    l=1;
    for(int j=c[i][1];j<=c[i][s[i]];j++){
    if(j==c[i][l]) l++;
    else{
    for(int k=1;k<=s[i];k++){
    if(a[j][c[i][k]]==0){
    a[j][c[i][k]]=true;
    b[c[i][k]]++;
    }
    }
    }
    }
    }
    int temp=n;
    for(int i=1;i<=n;i++){
    if(b[i]==-1) temp--;
    }
    while(temp!=0)
    {
    ans++;
    int dl=0;
    for(int i=1;i<=n;i++){
    if(b[i]==0){
    dl++;
    d[dl]=i;
    }
    }
    temp-=dl;
    for(int i=1;i<=dl;i++){
    b[d[i]]=-1;
    for(int j=1;j<=n;j++){
    if(a[d[i]][j]==1) b[j]--;
    }
    }
    }
    printf("%d\n",ans);
    return 0;
    }

  • 0
    @ 2013-11-23 11:44:05

    var
    f:array[0..1000] of boolean;
    a,num:array[0..1000] of longint;
    map:array[0..1000,0..1000] of boolean;
    n,m,p,q,i,j,k,ans,cnt:longint;
    begin
    readln(n,m);
    for i:=1 to m do
    begin
    read(p);
    fillchar(f,sizeof(f),0);
    cnt:=0;
    for j:=1 to p do
    begin
    read(q);
    inc(cnt);
    a[cnt]:=q;
    f[q]:=true;
    end;
    for j:=a[1]+1 to a[cnt]-1 do
    if not(f[j]) then
    begin
    for k:=1 to cnt do
    if not(map[a[k],j]) then
    begin
    inc(num[j]);
    map[a[k],j]:=true;
    end;
    end;
    readln;
    end;
    ans:=0;
    fillchar(f,sizeof(f),false);
    while true do
    begin
    cnt:=0;
    for i:=1 to n do
    if (num[i]=0) and (not(f[i])) then
    begin
    f[i]:=true;
    inc(cnt);
    a[cnt]:=i;
    end;
    if cnt=0 then break;
    inc(ans);
    for i:=1 to cnt do
    for j:=1 to n do
    if map[a[i],j] then
    begin
    map[a[i],j]:=false;
    dec(num[j]);
    end;
    end;
    writeln(ans);
    end.

    我是oier蒋仕彪。
    这是NOIP2013,我当时也过了。
    虽然我是n^3,但表示数据比较水。。。
    建立拓扑排序,然后裸拓扑。
    此外,祝贺我第100道通过!

  • 1

信息

ID
1851
难度
7
分类
(无)
标签
递交数
1643
已通过
367
通过率
22%
被复制
13
上传者