【bzoj 2597】[Wc二〇〇五]剪刀石头布(图论–网络流 最小费用最大流)

题目:在某个一对一游戏的较量(如下棋、乒乓球和羽球的单打)中,大家平日会碰着A胜过B,B胜过C而C又胜过A的诙谐场所,无妨形象的叫做剪刀石头布情形。有的时候,无聊的人们会津津乐道于计算有稍许那样的剪刀石头布境况时有产生,即有多少对冬天安慕希组(A,
B,
C),满意个中的一个人在比赛中赢了另1人,另一个人赢了第④人而第八位又胜过了第一个体。注意那里冬季的意思是说伊利组3月素的次第并不重庆大学,将(A,
B, C)、(A, C, B)、(B, A, C)、(B, C, A)、(C, A, B)和(C, B,
A)视为等同的景观。
       
N村办到场一场那样的娱乐的比赛,比赛日程规定私自多个人中间都要拓展一场比赛:那样一起有场竞赛。比赛一度拓展了一部分,我们想领悟在无比气象下,竞技停止后最多会产生稍微剪刀石头布景况。即给出已经产生的比赛结果,而你能够肆意布置剩下的较量的结果,以取得尽量多的剪刀石头布景况。

noip二〇一三普及组第叁题。

解法:那题的图转化很妙。O.O
是个好题,留那唯一的二个坑先……

题材背景

  在双人对决的比赛性比赛,如台球、羽球、国际象棋中,最常见的比赛制度是淘汰赛和循环赛。前者的风味是竞比赛场馆数少,每场都浮动刺激,但偶然性较高。后者的表征是比较公平,偶然性较低,但竞赛进度往往11分冗长。本题中介绍的瑞士联邦轮赛制,因最早采取于1895年在瑞士联邦设置的国际象棋竞技而得名。它能够用作是淘汰赛与循环赛的投降,既有限援救了比赛的安居,又能使比赛日程不至于过长。

标题叙述

  2*N 名编号为 1~2N 的选手共开展汉兰达轮比赛。每轮比赛初叶前,以及拥有竞赛结束后,都会安份守己总分从高到低对运动员举办1回排名。选手的总分为首轮开端前的伊始分数加晚春到位过的具备竞技的得分和。总分一样的,约定编号较小的选手排行靠前。 
  每轮交锋的周旋安顿与该轮比赛开首前的排行有关:第叁 名和第1 名、第 3
名和第 4名、……、第壹K – 1 名和第 2K名、……  、第③N – 1
名和第②N名,各实行一场较量。每场竞赛胜者得1 分,负者得 0
分。也便是说除了首轮以外,别的轮交锋的安插均无法事先明显,而是要取决于选手在后边交锋中的表现。 
  现给定每一个选手的伊始分数及其实力值,试计算在Koleos 轮竞技过后,排行第 Q
的健儿编号是不怎么。大家只要选手的实力值两两差异,且每场竞赛中实力值较高的总能获胜。

输入输出格式

输入格式:

输入文件名为swiss.in 。 
  输入的首先行是多少个正整数N、Odyssey 、Q,每五个数里面用一个空格隔开分离,表示有
2*N 名选手、R 轮竞技,以及大家关切的排行 Q。 
  第③行是2*N 个非负整数s1, s2, …,
s2N,每八个数里面用一个空格隔断,个中 si 表示编号为i 的运动员的早先分数。
第一行是2*N 个正整数w1 , w2 , …, w2N,每八个数里面用3个空格隔绝,在那之中wi 表示编号为i 的运动员的实力值。

出口格式:

  输出文件名为swiss.out。 
  输出唯有一行,包涵3个平头,即途达 轮竞技截止后,排名第 Q
的运动员的数码。

输入输出样例

输入样例#1:

2 4 2 
7 6 6 7 
10 5 20 15 

输出样例#1:

1

说明

【样例解释】
图片 1
【数据范围】 
对于30% 的数据,1 ≤ N ≤ 100; 
对于50% 的数据,1 ≤ N ≤ 10,000 ;

 对于100%的数据,1 ≤ N ≤ 100,000,1 ≤ R ≤ 50,1 ≤ Q ≤ 2N,0 ≤ s1, s2, …,
s2N≤10^8,1 ≤w1, w2 , …, w2N≤ 10^8。 

思路

  假诺用高速排序的话只好过百分之五十的数目,此题的正解是快排加归并。首先火速排序作为起首状态,然后模拟选出每场竞技的优胜者和战败者,优胜者每人加上一分后排行不变。所以再用归并排序合并五个有序数组。(PS:此归并非二分归并,能够参见一下那么些题,{http://codevs.cn/problem/3296/},用指针实现即可)时间复杂度O(RN)。

  PS:作者居然让如此贰个普及组的水题坑了一天,代码已经上升到200多行,后来竟是是神速排序时的一片段操作没有设想和变量的难点。

图片 2图片 3

type ss=record
    fen,shi,hao:int64;
    end;

type arr=array[0..200000] of ss;

var a,b,c:arr;
    n,r,q:int64;
    ii:longint;

procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2].fen;
         y:=a[(l+r) div 2].hao;
         repeat
           while (a[i].fen>x) or ((x=a[i].fen) and (y>a[i].hao))do
            inc(i);
           while (x>a[j].fen) or ((x=a[j].fen) and (y<a[j].hao)) do
            dec(j);
           if not(i>j) then
             begin
                a[0]:=a[i];
                a[i]:=a[j];
                a[j]:=a[0];
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;
//有处理操作的快速排序

procedure guibing;
var i,j,k:int64;x:longint;
begin
    fillchar(a,sizeof(a),0);
    i:=1;
    j:=1;
    k:=1;
    while (i<>n+1)and(j<>n+1) do
        begin
            if b[i].fen>c[j].fen then
                begin
                    a[k]:=b[i];
                    inc(i);
                    inc(k);
                end;
            if c[j].fen>b[i].fen then
                begin
                    a[k]:=c[j];
                    inc(j);
                    inc(k);
                end;
            if c[j].fen=b[i].fen then
                if c[j].hao<b[i].hao then
                    begin
                        a[k]:=c[j];
                        inc(j);
                        inc(k);
                    end
                else
                    begin
                        a[k]:=b[i];
                        inc(i);
                        inc(k);
                    end;
        end;
    for x:=i to n do
            begin
                a[k]:=b[x];
                inc(k);
            end;
    for x:=j to n do
            begin
                a[k]:=c[x];
                inc(k);
            end;
end;
//归并排序

procedure init;
var i:longint;
begin
    readln(n,r,q);
    for i:=1 to 2*n do a[i].hao:=i;
    for i:=1 to 2*n do read(a[i].fen);
    for i:=1 to 2*n do read(a[i].shi);
end;

procedure main;
var sum1,sum2:int64;i,j:longint;
begin
    fillchar(b,sizeof(b),0);
    fillchar(c,sizeof(c),0);
    i:=1;
    sum1:=0;
    sum2:=0;
    while i<=2*n do
        begin
            j:=i+1;
            if a[i].shi<a[j].shi then
                begin
                    inc(sum1);
                    inc(sum2);
                    b[sum1]:=a[j];
                    c[sum2]:=a[i];
                    inc(b[sum1].fen);
                end
            else
                begin
                    inc(sum1);
                    inc(sum2);
                    b[sum1]:=a[i];
                    c[sum2]:=a[j];
                    inc(b[sum1].fen);
                end;
            inc(i,2);
        end;
    guibing;
end;
//模拟比赛过程

procedure printf;
var i:longint;
begin
    writeln(a[q].hao);
end;

begin
    init;
    sort(1,2*n);
    for ii:=1 to r do main;
    printf;
end.

View Code