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

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

思路

  若是用高速排序的话只好过二分之一的数量,此题的正解是快排加归并。首先神速排序作为起先状态,然后模拟选出每场比赛的优胜者和退步者,优胜者每人加上一分后排名不变。所以再用归并排序合并八个有序数组。(PS:此归并非二分归并,能够参见一下以此题,{http://codevs.cn/problem/3296/},用指针实现即可)时间复杂度O(RN)。

  PS:作者竟然让如此1个普及组的水题坑了一天,代码已经上涨到200多行,后来竟是是急速排序时的一部分操作没有考虑和变量的题材。

图片 1图片 2

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

 

题目:在局地一对一游戏的比赛(如下棋、乒球和羽球的单打)中,大家常常会遇见A胜过B,B胜过C而C又胜过A的妙趣横生地方,无妨形象的名为剪刀石头布景况。有的时候,无聊的稠人广众会津津乐道于总结有个别许那样的剪子石头布情状时有爆发,即有多少对严节安慕希组(A,
B,
C),满意个中的一位在比赛前赢了另一位,另一位赢了第多人而第⑥人又胜过了第③私家。注意那里严节的情趣是说伊利组瓜月素的相继并不首要,将(A,
B, C)、(A, C, B)、(B, A, C)、(B, C, A)、(C, A, B)和(C, B,
A)视为等同的场馆。
       
N个体加入一场那样的游艺的较量,比赛日程规定私行几人之间都要进行一场比赛:那样一起有场较量。竞赛已经进展了一有些,我们想知道在极其情状下,比赛结束后最多会发出多少剪刀石头布情形。即给出已经发生的比赛结果,而你能够Infiniti制计划剩下的比赛的结果,以赢得尽量多的剪子石头布意况。

说明

【样例解释】
图片 3
【数据范围】 
对于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。 

输入输出格式

输入格式:

输入文件名为swiss.in 。 
  输入的第二行是多少个正整数N、LX570 、Q,每多个数里面用3个空格隔开分离,表示有
2*N 名选手、奥迪Q7 轮竞技,以及大家关注的排行 Q。 
  第3行是2*N 个非负整数s1, s2, …,
s2N,每八个数里面用3个空格隔离,在那之中 si 表示编号为i 的健儿的开首分数。
第二行是2*N 个正整数w1 , w2 , …, w2N,每五个数里面用二个空格隔离,在那之中wi 表示编号为i 的健儿的实力值。

出口格式:

  输出文件名为swiss.out。 
  输出惟有一行,包括二个平头,即昂Cora 轮竞赛甘休后,排行第 Q
的健儿的号码。

输入输出样例

输入样例#1:

2 4 2 
7 6 6 7 
10 5 20 15 

输出样例#1:

1

难题背景

  在双人对决的竞赛性比赛,如斯诺克、羽球、国际象棋中,最广大的比赛制度是淘汰赛和循环赛。前者的特色是竞赛场数少,每场都浮动刺激,但偶然性较高。后者的风味是相比较公平,偶然性较低,但竞赛过程往往特别冗长。本题中牵线的瑞士联邦轮比赛制度,因最早选用于1895年在瑞士联邦开设的国际象棋比赛而得名。它能够看成是淘汰赛与循环赛的妥胁,既保险了竞赛的平稳,又能使赛程不至于过长。

难题叙述

  2*N 名编号为 1~2N 的运动员共举行奥迪Q7轮竞赛。每轮竞技伊始前,以及独具竞赛甘休后,都会根据总分从高到低对选手举行贰遍排名。选手的总分为率先轮初始前的初步分数加季春在场过的持有比赛的得分和。总分一样的,约定编号较小的运动员排名靠前。 
  每轮交锋的对阵安顿与该轮比赛初步前的排行有关:第② 名和第叁 名、第 3
名和第 4名、……、第③K – 1 名和第 2K名、……  、第③N – 1
名和第③N名,各实行一场比赛。每场比赛胜者得1 分,负者得 0
分。也正是说除了首轮以外,其它轮交锋的安插均不能够事先鲜明,而是要在于选手在事先交锋中的表现。 
  现给定种种选手的起始分数及其实力值,试总结在Lacrosse 轮比赛过后,排名第 Q
的健儿编号是有个别。大家只要选手的实力值两两分歧,且每场竞赛中实力值较高的总能获胜。

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