星球大战

2019-11-11 19:53 来源:未知

P2419 [USACO08JAN]牛大赛Cow Contest,p2419usaco08jan

P1197 [JSOI2008]星球大战,p1197jsoi2010

题目背景

[Usaco2008 Jan]

标题陈述

比较久在此以前,在多少个遥远的星系,二个孔雀蓝的王国靠着它的特等武器统治者整个星系。某一天,凭着贰个临时的空子,风姿罗曼蒂克支反抗军摧毁了王国的最好军器,并占领了星系中差相当少具备的星麻木不仁。那些星球通过特殊的以太隧道相互直接或直接地连接。

但好景非常长,不慢帝国又再一次造出了她的特等军械。依附这一流武器的技能,帝国最早有安顿地摧毁反抗军占有的星球。由于星球的随处被损毁,多少个星球之间的广播发表通道也初步不可相信起来。将来,反抗军首领交给你叁个职分:给出原来多个星球之间的以太隧道连通景况甚至帝国打击的繁星顺序,以专心致志快的进程求出每三次打击之后反抗军并吞的星星的连通快的个数。(若是五个星球能够通过现成的以太通道直接或间接地连通,则那多少个星球在同贰个连通块中卡塔尔国。

难点陈述

N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.

Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

FJ的N(1 <= N <= 100)头红牛们近些日子到庭了场程序设计比赛:)。在赛管上,白牛们按1..N逐个编号。每头白牛的编制程序工夫不尽相似,並且未有哪三头红牛的程度相持不下,也便是说,水牛们的编制程序技能有显著的排名。 整个竞技被分成了多数轮,每风流洒脱轮是互相钦定编号的水牛的对决。借使编号为A的白牛的编制程序手艺强于编号为B的水牛(1 <= A <= N; 1 <= B <= N; A != B) ,那么他们的对决中,编号为A的白牛总是能胜出。 FJ想掌握水牛们编制程序技巧的实际排名,于是她找来了水牛们有着 M(1 <= M <= 4,500)轮比赛的结果,希望您能依据那么些音信,推断出尽恐怕多的红牛的编制程序才干排行。比赛结果保险不会自相恨恶。

输入输出格式

输入格式:

输入文件首先行富含多少个整数,N (1 <= N <= 2M) 和M (1 <= M <= 200,000),分别代表星球的多寡和以太隧道的多寡。星球用0~N-1的平头编号。

接下去的M行,每行饱含七个整数X, Y,此中(0<=X<>Y<N卡塔 尔(英语:State of Qatar),表示星球X和星球Y之间有以太隧道。注意有所的以太隧道都以双向的。

接下去风流倜傥行是三个卡尺头K,表示帝国陈设打击的星辰个数。

接下去的K行每行多个卡尺头X,知足0<=X<N,表示帝国安顿打击的星球编号。帝国总是按输入的依次依次摧毁星球的。

出口格式:

输出文件的率先行是早先时星球的对接块个数。

接下去的K行,每行一个寸头,表示通过该次打击后现成星球的交接块个数。

输入输出格式

输入格式:

第1行: 2个用空格隔绝的整数:N 和 M

第2..M+1行: 每行为2个用空格隔开分离的板寸A、B,描述了在座某后生可畏轮较量的奶牛的号子,以致结果(编号为A,即为每行的首先个数的水牛为 胜者卡塔尔

出口格式:

第1行: 输出1个整数,表示排行能够明确的红牛的数码

输入输出样例

输入样例#1:

8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7

输出样例#1:

1
1
1
2
3
3

输入输出样例

输入样例#1:

5 5
4 3
4 2
3 2
1 2
2 5

输出样例#1:

2

说明

[JSOI2008]

 

并查集的倒序使用,

风姿洒脱起首假如全数的星星全体灭绝

然后离线管理

 

 

图片 1 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 void read(int & n) 7 { 8 char c='+';int x=0; 9 while(c<'0'||c>'9') 10 c=getchar(); 11 while(c>='0'&&c<='9') 12 { 13 x=x*10+(c-48); 14 c=getchar(); 15 } 16 n=x; 17 } 18 const int MAXN=400001; 19 struct node 20 { 21 int u,v,nxt; 22 }edge[MAXN]; 23 int head[MAXN]; 24 int num=1; 25 int fa[MAXN]; 26 int n,m,t; 27 void add_edge(int x,int y) 28 { 29 edge[num].u=x; 30 edge[num].v=y; 31 edge[num].nxt=head[x]; 32 head[x]=num++; 33 } 34 int vis[MAXN]; 35 int des[MAXN]; 36 int ans[MAXN]; 37 int find(int x) 38 { 39 if(fa[x]==x) 40 return fa[x]; 41 else 42 return fa[x]=find(fa[x]); 43 } 44 void unionn(int x,int y) 45 { 46 int fx=find(x); 47 int fy=find(y); 48 fa[fx]=fy; 49 } 50 int create(int p) 51 { 52 vis[p]=0; 53 int x=0; 54 for(int i=head[p];i!=-1;i=edge[i].nxt) 55 { 56 if(vis[edge[i].v]==0&&find(edge[i].u)!=find(edge[i].v)) 57 { 58 unionn(edge[i].u,edge[i].v); 59 x++; 60 } 61 } 62 return x; 63 64 } 65 int vis2[MAXN]; 66 int calc() 67 { 68 memset(vis2,0,sizeof(vis2)); 69 int tot=0; 70 for(int i=0;i<n;i++) 71 { 72 if(vis[i]==0&&find(i)==i) 73 { 74 //vis2[fa[i]]=1; 75 tot++; 76 } 77 } 78 return tot; 79 } 80 int main() 81 { 82 freopen("bzoj_1015.in","r",stdin); 83 freopen("bzoj_1015.out","w",stdout); 84 read(n);read(m); 85 for(int i=0;i<n;i++) 86 head[i]=-1,fa[i]=i; 87 for(int i=0;i<m;i++) 88 { 89 int x,y; 90 read(x);read(y); 91 add_edge(x,y);add_edge(y,x); 92 } 93 read(t); 94 for(int i=0;i<t;i++) 95 { 96 read(des[i]); 97 vis[des[i]]=1; 98 } 99 for(int i=0;i<n;i++) 100 { 101 for(int j=head[i];j!=-1;j=edge[j].nxt) 102 if(vis[edge[j].u]==0&&vis[edge[j].v]==0) 103 unionn(edge[j].u,edge[j].v); 104 } 105 ans[t]=calc(); 106 for(int i=t-1;i>=0;i--) 107 { 108 int num=create(des[i]); 109 ans[i]=calc(); 110 } 111 for(int i=0;i<=t;i++) 112 { 113 printf("%dn",ans[i]); 114 } 115 return 0; 116 } TLE代码

 

 

 

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 using namespace std;
  6 void read(int & n)
  7 {
  8     char c='+';int x=0;
  9     while(c<'0'||c>'9')
 10     c=getchar();
 11     while(c>='0'&&c<='9')
 12     {
 13         x=x*10+(c-48);
 14         c=getchar();
 15     }
 16     n=x;
 17 }
 18 const int MAXN=400001;
 19 struct node
 20 {
 21     int u,v,nxt;
 22 }edge[MAXN];
 23 int head[MAXN];
 24 int num=1;
 25 int fa[MAXN];
 26 int n,m,t;
 27 void add_edge(int x,int y)
 28 {
 29     edge[num].u=x;
 30     edge[num].v=y;
 31     edge[num].nxt=head[x];
 32     head[x]=num++;
 33 }
 34 int vis[MAXN];
 35 int des[MAXN];
 36 int ans[MAXN];
 37 int find(int x)
 38 {
 39     if(fa[x]==x)
 40     return fa[x];
 41     else
 42     return fa[x]=find(fa[x]);
 43 }
 44 void unionn(int x,int y)
 45 {
 46     int fx=find(x);
 47     int fy=find(y);
 48     fa[fx]=fy;
 49 }
 50 int create(int p)
 51 {
 52     vis[p]=0;
 53     int x=0;
 54     for(int i=head[p];i!=-1;i=edge[i].nxt)
 55     {
 56         if(vis[edge[i].v]==0&&find(edge[i].u)!=find(edge[i].v))
 57         {
 58             unionn(edge[i].u,edge[i].v);
 59             x++;
 60         }
 61     }
 62     return x;
 63     
 64 }
 65 int vis2[MAXN];
 66 int calc()
 67 {
 68     memset(vis2,0,sizeof(vis2));
 69     int tot=0;
 70     for(int i=0;i<n;i++)
 71     {
 72         if(vis[i]==0&&find(i)==i)
 73         {
 74             //vis2[fa[i]]=1;
 75             tot++;
 76         }
 77     }
 78     return tot;
 79 }
 80 int main()
 81 {
 82     freopen("bzoj_1015.in","r",stdin);
 83     freopen("bzoj_1015.out","w",stdout);
 84     read(n);read(m);
 85     for(int i=0;i<n;i++)
 86         head[i]=-1,fa[i]=i;
 87     for(int i=0;i<m;i++)
 88     {
 89         int x,y;
 90         read(x);read(y);
 91         add_edge(x,y);add_edge(y,x);
 92     }
 93     read(t);
 94     for(int i=0;i<t;i++)
 95     {
 96         read(des[i]);
 97         vis[des[i]]=1;
 98     }
 99     for(int i=0;i<n;i++)
100     {
101         for(int j=head[i];j!=-1;j=edge[j].nxt)
102         if(vis[edge[j].u]==0&&vis[edge[j].v]==0)
103                 unionn(edge[j].u,edge[j].v);
104     }
105     ans[t]=calc();
106     for(int i=t-1;i>=0;i--)
107     {
108         int num=create(des[i]);
109         ans[i]=ans[i+1]-num+1;
110     }
111     for(int i=0;i<=t;i++)
112     {
113         printf("%dn",ans[i]);
114     }
115     return 0;
116 }

 

[JSOI2008]星球战争,p1197jsoi二零一零标题陈诉相当久早先,在三个漫长的星系,一个乌黑的王国靠着它的最好军器统治者整个星系。某一天,凭...

说明

输出表明:

编号为2的水牛输给了号码为1、3、4的红牛,也正是说她的水准比那3头奶

牛都差。而编号为5的奶牛又输在了她的手头,相当于说,她的品位比编号为5的

白牛强一些。于是,编号为2的水牛的排名自然为第4,编号为5的白牛的档次必

然最差。其余3头水牛的排行仍力不胜任鲜明。

 

一同头和气YY了20分,也是比较纯洁。。。

图片 2 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 void read(int & n) 8 { 9 char c='+';int x=0; 10 while(c<'0'||c>'9') 11 c=getchar(); 12 while(c>='0'&&c<='9') 13 { 14 x=x*10+(c-48); 15 c=getchar(); 16 } 17 n=x; 18 } 19 const int MAXN=4501; 20 struct node 21 { 22 int u,v,nxt; 23 }edge[MAXN]; 24 int head[MAXN]; 25 int num=1; 26 int n,m; 27 void add_edge(int x,int y) 28 { 29 edge[num].u=x; 30 edge[num].v=y; 31 edge[num].nxt=head[x]; 32 head[x]=num++; 33 } 34 int vis[MAXN]; 35 void dfs(int p) 36 { 37 vis[p]++; 38 for(int i=head[p];i!=-1;i=edge[i].nxt) 39 if(edge[i].v!=0) 40 dfs(edge[i].v); 41 } 42 int main() 43 { 44 read(n);read(m); 45 for(int i=1;i<=n;i++) 46 head[i]=-1; 47 for(int i=1;i<=m;i++) 48 { 49 int x,y; 50 read(x);read(y); 51 add_edge(x,y); 52 } 53 for(int i=1;i<=m;i++) 54 dfs(edge[i].v); 55 sort(vis+1,vis+n+1); 56 int ans=0; 57 for(int i=n;i>=1;i--) 58 { 59 //if((vis[i]-vis[i-1])==1) 60 //ans++; 61 if(vis[i]==i) 62 ans++; 63 } 64 cout<<ans; 65 return 0; 66 } YY

 

floyd跑一边

具有的点都访问过的话就可以规定

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 void read(int & n)
 8 {
 9     char c='+';int x=0;
10     while(c<'0'||c>'9')
11     c=getchar();
12     while(c>='0'&&c<='9')
13     {
14         x=x*10+(c-48);
15         c=getchar();
16     }
17     n=x;
18 }
19 const int MAXN=401;
20 const int maxn=0x7fffff;
21 struct node
22 {
23     int u,v,nxt;
24 }edge[MAXN];
25 int head[MAXN];
26 int num=1;
27 int n,m;
28 int map[MAXN][MAXN];
29 int ans[MAXN];
30 int main()
31 {
32     read(n);read(m);
33     for(int i=1;i<=n;i++)
34         for(int j=1;j<=n;j++)
35             map[i][j]=maxn;
36     for(int i=1;i<=m;i++)
37     {
38         int x,y;
39         read(x);read(y);
40         map[x][y]=1;
41     }
42     for(int k=1;k<=n;k++)
43         for(int i=1;i<=n;i++)
44             for(int j=1;j<=n;j++)
45                 if(map[i][k]!=maxn&&map[k][j]!=maxn)
46                     map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
47     
48     for(int i=1;i<=n;i++)
49         for(int j=1;j<=n;j++)
50             if(map[i][j]!=maxn)
51             {
52                 ans[i]++;
53                 ans[j]++;
54             }
55     int out=0;
56     for(int i=1;i<=n;i++)
57     {
58         if(ans[i]==n-1)
59         out++;
60     }
61     cout<<out;
62     return 0;
63 }

 

[USACO08JAN]牛大赛Cow Contest,p2419usaco08jan 主题材料背景 [Usaco2008 Jan] 标题描述 N (1 N 100) cows, conveniently numbered 1..N, are participating in a programming...

TAG标签:
版权声明:本文由990888藏宝阁发布于关于计算机,转载请注明出处:星球大战