Codeforces Round #279 (Div. 2)_html/css_WEB-ITnose

哎，自己好水啊，明明第二题可以出的，哎，因为数组开小了，wa了，真蛋疼啊。。。。

第一题：

思路：开三个数组保存一起，然后最后取最小值，那个这就是匹配的对数。

题目：

立即学习“前端免费学习笔记（深入）”；

A. Team Olympiad

time limit per test

memory limit per test

input

output

The School №0 of the capital of Berland has n children studying in it. All the children in this school are gifted: some of them are good at programming, some are good at maths, others are good at PE (Physical Education). Hence, for each child we know value ti:

Each child happens to be good at exactly one of these three subjects.

The Team Scientific Decathlon Olympias requires teams of three students. The school teachers decided that the teams will be composed of three children that are good at different subjects. That is, each team must have one mathematician, one programmer and one sportsman. Of course, each child can be a member of no more than one team.

What is the maximum number of teams that the school will be able to present at the Olympiad? How should the teams be formed for that?

Input

The first line contains integer n (1?≤?n?≤?5000) ? the number of children in the school. The second line contains n integers t1,?t2,?...,?tn(1?≤?ti?≤?3), where ti describes the skill of the i-th child.

Output

In the first line output integer w ? the largest possible number of teams.

Then print w lines, containing three numbers in each line. Each triple represents the indexes of the children forming the team. You can print both the teams, and the numbers in the triplets in any order. The children are numbered from 1 to n in the order of their appearance in the input. Each child must participate in no more than one team. If there are several solutions, print any of them.

If no teams can be compiled, print the only line with value w equal to 0.

Sample test(s)

input

71 3 1 3 2 1 2

output

23 5 26 7 4

input

42 1 1 2

output

立即学习“前端免费学习笔记（深入）”；

立即学习“前端免费学习笔记（深入）”；

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<map>#include<vector>#include<cmath>#include<string>#include<queue>#define eps 1e-9#define ll long long#define INF 0x3f3f3f3fusing namespace std;priority_queue<int,vector<int>,greater<int> >Q;const int maxn=5000+10;int n;int t1[maxn],t2[maxn],t3[maxn];int main(){    int x1,x2,x3,x,ans;    while(~scanf("%d",&n))    {        x1=x2=x3=0;        for(int i=1;i<=n;i++)        {            scanf("%d",&x);            if(x==1)                t1[++x1]=i;            else if(x==2)                t2[++x2]=i;            else                t3[++x3]=i;        }        ans=min(x1,x2);        ans=min(ans,x3);        if(ans==0)           printf("%d\n",0);        else        {            x=0;            printf("%d\n",ans);            for(int i=1;i<=ans;i++)                {                    ++x;                    printf("%d %d %d\n",t1[x],t2[x],t3[x]);                }        }    }    return 0;}

立即学习“前端免费学习笔记（深入）”；

就是给出每个人的前驱后后继，然后问最后的顺序是什么。。

根据给的数据可以推出第二个和倒数第二个，但是发现为偶数的时候根本就推不出来，其实完全可以根据前两个推出

div+css3阶梯分页样式

div+css3阶梯分页样式

84

查看详情

所有的序列，因为根据第一个可以推出1,3,5,7,2*n+1，根据2可以推出2,4,6,8,2*n。。。直接用邻接表存储起来就好了

题目：

立即学习“前端免费学习笔记（深入）”；

B. Queue

time limit per test

memory limit per test

input

output

During the lunch break all n Berland State University students lined up in the food court. However, it turned out that the food court, too, has a lunch break and it temporarily stopped working.

Standing in a queue that isn't being served is so boring! So, each of the students wrote down the number of the student ID of the student that stands in line directly in front of him, and the student that stands in line directly behind him. If no one stands before or after a student (that is, he is the first one or the last one), then he writes down number 0 instead (in Berland State University student IDs are numerated from 1).

After that, all the students went about their business. When they returned, they found out that restoring the queue is not such an easy task.

Help the students to restore the state of the queue by the numbers of the student ID's of their neighbors in the queue.

Input

The first line contains integer n (2?≤?n?≤?2·105) ? the number of students in the queue.

Then n lines follow, i-th line contains the pair of integers ai,?bi (0?≤?ai,?bi?≤?106), where ai is the ID number of a person in front of a student and bi is the ID number of a person behind a student. The lines are given in the arbitrary order. Value 0 is given instead of a neighbor's ID number if the neighbor doesn't exist.

The ID numbers of all students are distinct. It is guaranteed that the records correspond too the queue where all the students stand in some order.

Output

Print a sequence of n integers x1,?x2,?...,?xn ? the sequence of ID numbers of all the students in the order they go in the queue from the first student to the last one.

Sample test(s)

input

492 310 731 07 141

output

92 7 31 141 

Note

The picture illustrates the queue for the first sample.

立即学习“前端免费学习笔记（深入）”；

立即学习“前端免费学习笔记（深入）”；

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<map>#include<vector>#include<cmath>#include<string>#include<queue>#define eps 1e-9#define ll long long#define INF 0x3f3f3f3fusing namespace std;priority_queue<int,vector<int>,greater<int> >Q;const int maxn=2000000+10;struct Edge{    int to,next;}edge[maxn<<2];int ans[maxn],head[maxn],cnt;bool vis[maxn];void add_edge(int x,int y){    edge[++cnt].to=y;    edge[cnt].next=head[x];    head[x]=cnt;}int num1[1000005],num2[1000005];int main(){    int u,v,n,x,xx;    while(~scanf("%d",&n))    {        memset(head,-1,sizeof(head));        memset(vis,false,sizeof(vis));        memset(num1,0,sizeof(num1));        memset(num2,0,sizeof(num2));        cnt=0;        for(int i=1;i<=n;i++)        {            scanf("%d %d",&u,&v);            if(u==0)  ans[2]=v;            num1[u]--;            num2[v]--;            if(u==0||v==0)  continue;            add_edge(u,v);        }        for(int i=0;i<1000005;i++)        {            if(num1[i]==-1&&num2[i]==0)            {                ans[1]=i;                break;            }        }        x=1;        xx=head[ans[1]];        while(x<n)        {            v=edge[xx].to;            x+=2;            ans[x]=v;            xx=head[v];        }        x=2;        xx=head[ans[2]];         while(x<n)        {            v=edge[xx].to;            x+=2;            ans[x]=v;            xx=head[v];        }        for(int i=1;i<n;i++)            printf("%d ",ans[i]);        printf("%d\n",ans[n]);    }    return 0;}/*50 21 32 53 45 0*/

立即学习“前端免费学习笔记（深入）”；