Luogu1309 瑞士联邦轮(分治,归并排序)葡京娱乐软件下载

Description

Luogu1309 瑞士联邦轮(分治,归并排序)

在一部分一对一游戏的较量(如下棋、乒乓球和羽毛球的单打)中,大家平常会遭受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)视为等同的情事。

Description

在双人对决的比赛性比赛,如斯诺克、羽球、国际象棋中,最常见的比赛制度是淘汰赛和循环赛。前者的特色是竞技场数少,每场都浮动刺激,但偶然性较高。后者的风味是相比较公平,偶然性较低,但竞赛进度往往十二分冗长。

主旨中介绍的瑞士联邦轮比赛制度,因最早选择于1895年在瑞士联邦办起的国际象棋比赛而得名。它能够作为是淘汰赛与循环赛的投降,既保险了竞赛的祥和,又能使比赛日程不至于过长。
2*N 名编号为 1~2N
的运动员共进行LX570轮竞赛。每轮竞技起头前,以及具有比赛结束后,都会根据总分从高到低对选手举办三次排名。选手的总分为率先轮开头前的开头分数加樱笋时在场过的持有比赛的得分和。总分一样的,约定编号较小的运动员排名靠前。

每轮竞技的对立安顿与该轮竞技初始前的排名有关:第① 名和第① 名、第 3
名和第 4名、……、第②K – 1 名和第 2K名、…… 、第叁N – 1
名和第1N名,各进行一场交锋。每场比赛胜者得1 分,负者得 0
分。也正是说除了第一轮以外,别的轮竞赛的配置均不可能事先显明,而是要在于选手在前头交锋中的表现。

现给定每种选手的上马分数及其实力值,试总计在大切诺基 轮比赛过后,排行第 Q
的健儿编号是稍微。我们假设选手的实力值两两不一致,且每场比赛前实力值较高的总能赢球。

N私家参预一场那样的玩乐的竞赛,赛程规定专断五个人里面都要拓展一场较量:那样一起有场交锋。竞技一度开始展览了一局地,大家想清楚在无比情形下,比赛截至后最多会时有发生多少剪刀石头布动静。即给出已经发出的比赛结果,而你能够任意安顿剩下的竞技的结果,以获取尽量多的剪刀石头布情况。

Input

输入的第3行是四个正整数N、奥迪Q7 、Q,每四个数里面用八个空格隔离,表示有
2*N 名运动员、Odyssey 轮比赛,以及我们关切的排名 Q。

第②行是2N 个非负整数s1, s2, …, s2N,每三个数里面用二个空格隔开分离,其中si 表示编号为i 的健儿的起来分数。 第贰行是2N 个正整数w1 , w2 , …,
w2N,每七个数里面用3个空格隔开,在那之中 wi 表示编号为i 的运动员的实力值。

Input

Output

输出唯有一行,包罗一个平头,即Odyssey 轮比赛甘休后,排行第 Q 的选手的号码。

输入文件的第③行是贰个平头N,表示加入竞技的总人口。

Sample Input

2 4 2
7 6 6 7
10 5 20 15

其后是多少个NN列的数字矩阵:一共N行,每行N列,数字间用空格隔开。

Sample Output

1

在第(i+1)行的第j列的数字倘诺是1,则代表i在曾经产生的竞赛中赢了j;该数字要是0,则象征在曾经发出的较量中i败于j;该数字是2,表示ij里头的比赛尚未发生。数字矩阵对角线上的数字,即第(i+1)行第i列的数字都是0,它们可是是占位符号,没有别的意义。

Http

Luogu:https://www.luogu.org/problem/show?pid=1309

输入文件保险合法,不会时有发生争持,当i≠j时,第(i+1)行第j列和第(j+1)行第i列的多少个数字照旧都以2,要么二个是03个是1。

Source

分治,归并排序

Output

不留余地思路

刚看那道难题一定想到的是每一轮都全体以分数为率先要害字、编号为第③要害字排序一遍,但诸如此类自然会晚点,所以大家另寻办法。

因为每二次比赛前胜者的分数都只+1,所以假诺大家在每一轮过后把胜者和败者分别放入多个数组,我们会发觉,它们各自都是一动不动的。

之所以为了选拔好那几个天性,大家选取归并排序,这样就不会爆时间了。

输出文件的第1行是三个平头,表示在您安顿的比赛结果中,出现了多少剪刀石头布情况。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

class PEOPLE//定义人的结构体
{
public:
    int point,w,num;
};

bool operator < (PEOPLE a,PEOPLE b)//重载小于运算符,因为要使用STL中的sort
{
    if (a.point==b.point)
        return a.num<b.num;
    else
        return a.point>b.point;
}

const int maxN=1000001;
const int inf=2147483647;

int n,R,Q;
PEOPLE A[maxN*2];//存放所有人
PEOPLE K1[maxN*2];//每轮后临时存放胜者
PEOPLE K2[maxN*2];//临时存放败者

int main()
{
    cin>>n>>R>>Q;
    for (int i=1;i<=n*2;i++)
        cin>>A[i].point;
    for (int i=1;i<=n*2;i++)
        cin>>A[i].w;
    for (int i=1;i<=n*2;i++)
        A[i].num=i;
    sort(&A[1],&A[2*n+1]);//第一轮前用一边快排
    for (int i=1;i<=R;i++)
    {
        for (int j=1;j<=2*n;j=j+2)
        {
            if (A[j].w>A[j+1].w)
            {
                K1[j/2+1]=A[j];//分别放入两个数组
                K2[j/2+1]=A[j+1];
                K1[j/2+1].point++;
            }
            else
            {
                K1[j/2+1]=A[j+1];
                K2[j/2+1]=A[j];
                K1[j/2+1].point++;
            }
        }
        int j1=1,j2=1;
        for (int j=1;j<=2*n;j++)//归并排序
            if ((j2>n)|| ((j1<=n)&&((K1[j1].point>K2[j2].point)||((K1[j1].point==K2[j2].point)&&(K1[j1].num<K2[j2].num))) )     )
            {
                A[j]=K1[j1];
                j1++;
            }
            else
            {
                A[j]=K2[j2];
                j2++;
            }
    }
    cout<<A[Q].num<<endl;
    return 0;
}

输出文件的第一行开端有一个和输入文件中格式相同的NN列的数字矩阵。第(i+1)行第j个数字描述了ij以内的比赛结果,1意味i赢了j,0表示i负于j,与输入矩阵分歧的是,在这一个矩阵中从未代表比赛尚未开始展览的数字2;对角线上的数字都以0。输出矩阵要保障合法,不可能发生争持。

 

题解:http://blog.csdn.net/pouy94/article/details/5972444

PS:那题太牛叉了值得一做……

 

代码(896MS):

葡京娱乐软件下载 1葡京娱乐软件下载 2

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <queue>
  6 using namespace std;
  7 
  8 const int MAXN = 110;
  9 const int MAXV = MAXN * MAXN;
 10 const int MAXE = MAXN * MAXV;
 11 const int INF = 0x7f7f7f7f;
 12 
 13 struct ZWK_FLOW {
 14     int head[MAXV], dis[MAXV];
 15     int to[MAXE], next[MAXE], flow[MAXE], cost[MAXE];
 16     int n, ecnt, st, ed;
 17 
 18     void init() {
 19         memset(head, 0, sizeof(head));
 20         ecnt = 2;
 21     }
 22 
 23     void add_edge(int u, int v, int c, int w) {
 24         to[ecnt] = v; flow[ecnt] = c; cost[ecnt] = w; next[ecnt] = head[u]; head[u] = ecnt++;
 25         to[ecnt] = u; flow[ecnt] = 0; cost[ecnt] = -w; next[ecnt] = head[v]; head[v] = ecnt++;
 26         //printf("%d %d %d %d\n", u, v, c, w);
 27     }
 28 
 29     void spfa() {
 30         for(int i = 1; i <= n; ++i) dis[i] = INF;
 31         priority_queue<pair<int, int> > que;
 32         dis[st] = 0; que.push(make_pair(0, st));
 33         while(!que.empty()) {
 34             int u = que.top().second, d = -que.top().first; que.pop();
 35             if(d != dis[u]) continue;
 36             for(int p = head[u]; p; p = next[p]) {
 37                 int &v = to[p];
 38                 if(flow[p] && dis[v] > d + cost[p]) {
 39                     dis[v] = d + cost[p];
 40                     que.push(make_pair(-dis[v], v));
 41                 }
 42             }
 43         }
 44         int t = dis[ed];
 45         for(int i = 1; i <= n; ++i) dis[i] = t - dis[i];
 46     }
 47 
 48     int minCost, maxFlow;
 49     bool vis[MAXV];
 50 
 51     int add_flow(int u, int aug) {
 52         if(u == ed) {
 53             maxFlow += aug;
 54             minCost += dis[st] * aug;
 55             return aug;
 56         }
 57         vis[u] = true;
 58         int now = aug;
 59         for(int p = head[u]; p; p = next[p]) {
 60             int &v = to[p];
 61             if(flow[p] && !vis[v] && dis[u] == dis[v] + cost[p]) {
 62                 int t = add_flow(v, min(now, flow[p]));
 63                 flow[p] -= t;
 64                 flow[p ^ 1] += t;
 65                 now -= t;
 66                 if(!now) break;
 67             }
 68         }
 69         return aug - now;
 70     }
 71 
 72     bool modify_label() {
 73         int d = INF;
 74         for(int u = 1; u <= n; ++u) if(vis[u]) {
 75             for(int p = head[u]; p; p = next[p]) {
 76                 int &v = to[p];
 77                 if(flow[p] && !vis[v]) d = min(d, dis[v] + cost[p] - dis[u]);
 78             }
 79         }
 80         if(d == INF) return false;
 81         for(int i = 1; i <= n; ++i) if(vis[i]) dis[i] += d;
 82         return true;
 83     }
 84 
 85     int min_cost_flow(int ss, int tt, int nn) {
 86         st = ss, ed = tt, n = nn;
 87         minCost = maxFlow = 0;
 88         spfa();
 89         while(true) {
 90             while(true) {
 91                 for(int i = 1; i <= n; ++i) vis[i] = false;
 92                 if(!add_flow(st, INF)) break;
 93             }
 94             if(!modify_label()) break;
 95         }
 96         return minCost;
 97     }
 98 } G;
 99 
100 int n, m;
101 int mat[MAXN][MAXN], ans[MAXN][MAXN];
102 
103 inline int encode(int i, int j) {
104     if(i > j) swap(i, j);
105     return i * n + j;
106 }
107 
108 int main() {
109     scanf("%d", &n);
110     for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) scanf("%d", &mat[i][j]);
111     m = n * n;
112     int ss = n + m + 1, tt = ss + 1;
113     G.init();
114     int sum = n * (n - 1) * (n - 2) / 6;
115     for(int i = 1; i <= n; ++i) {
116         for(int j = 1, tmp = 1; j < n; ++j, tmp += 2) G.add_edge(ss, i, 1, tmp);
117         for(int j = 1; j <= n; ++j) if(mat[i][j] != 0)
118             ans[i][j] = G.ecnt, G.add_edge(i, encode(i, j), 1, 0);
119     }
120     for(int i = 1; i <= m; ++i) G.add_edge(i + n, tt, 1, 0);
121     int x = G.min_cost_flow(ss, tt, tt);
122     printf("%d\n", sum - (x - n * (n - 1) / 2) / 2);
123     for(int i = 1; i <= n; ++i) {
124         for(int j = 1; j <= n; ++j) {
125             if(j != 1) printf(" ");
126             if(mat[i][j] != 2) printf("%d", mat[i][j]);
127             else {
128                 if(G.flow[ans[i][j]] == 0) printf("1");
129                 else printf("0");
130             }
131         }
132         puts("");
133     }
134 }

View Code