Codeforces ラウンド #279 (ディビジョン 2)_html/css_WEB-ITnose

そうですね、2 番目の問題はもちろん解けますが、配列が小さいサイズに設定されているため、本当に困っています。 。 。 。

最初の質問:

アイデア: 3 つの配列を開いて一緒に保存し、最後に最小値を取得します。これが一致するペアです。

タイトル:

A. チームオリンピアード

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

ベルランドの首都の学校 №0 には、n 人の子供たちが勉強しています。この学校の子供たちは全員、才能に恵まれています。プログラミングが得意な子供もいれば、数学が得意な子供も、体育が得意な子供もいます。したがって、各子供について、値 ti:

ti?=?1 (i 番目の子供がプログラミングが得意な場合)、

ti?=?2、i 番目の子供が数学が得意な場合、

がわかります。 ti?=?3、i 番目の子供が体育が得意な場合

各子供はたまたまこれら 3 つの科目のうちの 1 つが得意です。

チーム科学十種競技オリンピックでは、3 人の生徒のチームが必要です。学校の教師は次のように決定しました。チームは、異なる科目が得意な 3 人の子供で構成されます。つまり、各チームには数学者、プログラマー、スポーツマンが 1 人ずつ含まれていなければなりません。もちろん、各子供が所属できるチームは 1 つだけです。は、学校がオリンピックで発表できるチームの最大数ですか? そのためにはどのようにチームを編成すればよいですか?

入力

最初の行には整数 n (1?≤?n?≤?5000) が含まれています。 ) ? 学校の子供の数。n 個の整数 t1,?t2,?...,?tn(1?≤?ti?≤?3) は、i 番目の生徒のスキルを表します。 child.

出力

最初の行では、チームの最大数を整数で出力します。

次に、各行に 3 つの数値を含む w 行を出力します。各トリプルは、チームを構成する子のインデックスを表します。両方のチームと、トリプレットの番号を任意の順序で出力できます。子には、入力に出現する順序で 1 から n の番号が付けられます。複数のチームがある場合、各子は 1 つだけ参加する必要があります。解決策がある場合は、そのいずれかを出力します。

コンパイルできるチームがない場合は、値 w が 0 に等しい行だけを出力します。

サンプル テスト

入力

71 3 1 3 2 1 2

出力

23 5 26 7 4

入力

42 1 1 2

出力

コード:

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

2 番目の質問:

は、全員の前任者と後任者を与え、最終的な順序を尋ねます。 。

最後から 2 番目の 2 番目のものは、与えられたデータに基づいて推定できますが、それが偶数であることが判明した場合は、まったく推定できません。実際には、最初の 2 つ

すべてのシーケンスに基づいて推定できます。 , 最初のもの 1,3,5,7,2*n+1 に基づいて推定できるため、2 に基づいて 2,4,6,8,2*n を推定できます。 。 。隣接リストに直接保存するだけです

質問:

B. キュー

テストごとの時間制限

2 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

昼休み中、バーランド州立大学の学生全員がフードコートに並んでいたが、フードコートも昼休みであることが判明し、一時的に営業を停止しました

スタンディング。サービスが提供されない列に並ぶのはとても退屈なので、生徒はそれぞれ、自分のすぐ前に並んでいる学生と、自分のすぐ後ろに並んでいる学生の学生証の番号を書き留めました。学生の前後に誰も立っていない場合 (つまり、最初または最後の学生である場合)、代わりに番号 0 を書き留めます (バーランド州立大学では、学生 ID は 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*/