Codeforces Round #227 (Div. 2)

A. George and Sleep

题意:给出一个现在的时间和一个经过的时间,问开始时间是多少。

分析:直接模拟。

Codeforces Round #227 (Div. 2)
/****************************************
* File Name: 227a.cpp
* Author: sky0917
* Created Time: 2014年01月30日 23:30:04
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

char s[10];
char t[10];
int main(){
    int nh, ns, th, ts;
    int ah, as;
    while (scanf("%d:%d %d:%d",&nh,&ns,&th,&ts)!=EOF){
        ah = nh - th; 
        as = ns - ts;   
        if (ns < ts){
            as += 60;
            ah--;   
        }   
        if (ah < 0){
            ah += 24;
        }
        printf("%02d:%02d\n",ah,as);    
    }
    return 0;
}
View Code

 

B. George and Round

题意:给出n个数字的序列, a1,?a2,?...,?an ,表示要出的题数和难度要求,再给出m个数字序列,b1,?b2,?...,?bm

        表示已经存在的题目的数目和难度,可以把现在出好的题目难度降低,问最少再出多少道可以满足要求。

分析:贪心,对于ai,尽量用最小的bj去满足它,如果不能满足,说明需要出一道题目。

Codeforces Round #227 (Div. 2)
/****************************************
* File Name: 227b.cpp
* Author: sky0917
* Created Time: 2014年01月30日 23:46:17
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 3003;

int n, m;
int a[maxn];
int b[maxn];
int v[maxn];
int main(){
    while (scanf("%d %d",&n,&m)!=EOF){
        for (int i=0; i<n; i++){
            scanf("%d",&a[i]);
        }
        for (int i=0; i<m; i++){
            scanf("%d",&b[i]);
        }
        int pa=n-1, pb=m-1; 
        int res = 0;
        for (int i=n-1; i>=0; i--){
            for (int j=0; j<m; j++){
                if (!v[j] && b[j] >= a[i]){
                    v[j] = 1;
                    res++;
                    break;
                }
            }
        }   
        printf("%d\n",n-res);
    }
    return 0;
}
View Code

 

D. George and Interesting Graph

题意:给出一个有n个点和m条边且无重边的有向图,每次操作可以删除一条边或者加上一条边,问最少多少次操作可以让图变成“有趣图”。

        “有趣图”要求:

         存在一个中心点u,满足图中任意一点v,存在 u->v 和 v->u,(包括u->u)

         除了上述的点u,其它所有的点的入度和出度都为2.

分析:枚举点u,首先计算出让中心点满足要求要增加的边数。

         对剩下的点拆点,变成v1,v2, v1作为左集合,v2作为右集合的点,

         由于要求剩下的点出度和入度都等于2,且由于和中心点之间有u->v和v->u,

         那么剩下的点只要满足拆点之后的图是完全匹配即可。

Codeforces Round #227 (Div. 2)
/****************************************
* File Name: 227d.cpp
* Author: sky0917
* Created Time: 2014年01月31日  0:25:49
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 505;
const int maxm = 2002;
const int INF = 0x1f1f1f1f;

struct node{
    int to, next;
}e[maxm];
int tot;
int head[maxn];
void add(int s, int t){
    e[tot].to = t;
    e[tot].next = head[s];
    head[s] = tot++;
}

int n, m;
int ind[maxn];
int oud[maxn];
int v[maxn];
int lik[maxn];
int g[maxn][maxn];
int sa;
int tn;

int find(int u){

    for (int i=head[u]; i!=-1; i=e[i].next){
        int k = e[i].to;
        if (!v[k] && k!=tn){
            v[k] = 1;
            if (lik[k] == 0 || find(lik[k])){
                lik[k] = u;
                return 1;
            }   
        }
    }
    return 0;
}
int cal(int u){
    tn = u;
    int sum = 0;
    int rs = sa - ind[u] - oud[u];
    
    sum += 2*n-oud[u] - ind[u];

    if (g[u][u])
        rs++;
    else
        sum--;

    int tmp = 0;
    memset(lik, 0, sizeof(lik));
    for (int i=1; i<=n; i++){
        if (i != u){
            memset(v, 0, sizeof(v));
            if (find(i)){
                tmp++;              
            }
        }   
    }   
    sum += (rs-tmp) + (n-1-tmp);
    return sum;
}
void solve(){
    int res = INF;
    for (int i=1; i<=n; i++){
        int tmp = cal(i);
        res = min(res, tmp);
    }
    printf("%d\n",res);
}
int main(){
    while (scanf("%d %d",&n,&m)!=EOF){
        int a, b;

        memset(head, -1, sizeof(head));
        tot = 0;
        sa = 0;
        for (int i=0; i<m; i++){
            scanf("%d %d",&a,&b);
            g[a][b] = 1;
            sa++;   
            oud[a]++;
            ind[b]++;
            add(a, b);
        }
        solve();
    }   
    return 0;
}
View Code

Codeforces Round #227 (Div. 2)

上一篇:微软StockTrader应用程序


下一篇:vs2005 QT4.7.1编译 详细