题解 - Vijos

2

芙兰朵露•斯卡雷特 LV 8 @ 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

aph。 (chenqianrong) LV 10 @ 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

Mark__Zuckerburg LV 8 @ 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

我不是 (邸亦奥他爸爸) LV 8 @ 2017-08-11 11:23:58

求一个最长的拓扑序
#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

diamond_duke LV 8 @ 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

ljt12138 LV 10 @ 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

nzhtl1477 LV 10 @ 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

ydfq LV 10 @ 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

freefood LV 10 @ 2014-10-02 14:41:47

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

0

L.G.S LV 9 @ 2014-02-17 21:02:22

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

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

跪烂神犇……

0

wuyifan LV 8 @ 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

juan1973 LV 10 @ 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道通过！

题解

12 条题解

AC的贪心

车站分级

信息

状态

开发

支持

题解

12 条题解

AC的贪心

车站分级

信息

状态

开发

支持

还没有账户？

登录