您的位置: 首页 > IT文章 > Codeforces Round #228 (Div. 2)

Codeforces Round #228 (Div. 2)

分类: IT文章 • 2025-01-30 16:20:31

题意：有 n 个数，每次找一对 i ， j 满足a[i] > a[j],然后 a[i] = a[i] - a[j],问最后剩下的数的和最小是多少。

分析：每次找最小的数，看看哪些数比它大，然后减去，直到所有数相等。

/****************************************
* File Name: 228d2a.cpp
* Author: sky0917
* Created Time: 2014年02月 5日 13:32:03
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 102;

int a[maxn];
int main(){
    int n;
    while (scanf("%d",&n)!=EOF){
        for (int i=0; i<n; i++)
            scanf("%d",&a[i]);
        while (1){
            int d = a[0];
            for (int i=1; i<n; i++){
                if (a[i] < d)
                    d = a[i];   
            }
            int f = 1;
            for (int i=0; i<n; i++){
                if (a[i] > d){
                    a[i] -= d;
                    f = 0;
                }
            }
            if (f) break;
        }
        int sum = 0;
        for (int i=0; i<n; i++)
            sum += a[i];
        printf("%d
",sum);
    }   
    return 0;
}

View Code

B. Fox and Cross

题意：有个grid，里面有 "#" 和 “." ，问是否可以找到一些十字，如下：

###

把grid 中的 # 全部覆盖，并且不能相交。

分析：从上往下，从左往右，遍历方格，第一次遇到的"#" 一定是十字的最上方那个部分，看看是不是合法的十字，然后把这个十字全部标记掉。

最后看看grid 中是否有没有标记的 #。

/****************************************
* File Name: 228d2b.cpp
* Author: sky0917
* Created Time: 2014年02月 5日 13:42:30
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 102;

char s[maxn];
int  g[maxn][maxn]; 
int main(){
    int n;
    while (scanf("%d",&n)!=EOF){
        for (int i=0; i<n; i++){
            scanf("%s",s);
            for (int j=0; s[j]; j++){
                g[i][j] = (s[j]=='#'?1:0);
            }
        }
            
        int f = 1;
        for (int i=0; i<n-2 && f; i++){
            for (int j=1; j<n-1 && f; j++){
                if (g[i][j]){
                    int sum = g[i+1][j] + g[i+2][j] + g[i+1][j-1] + g[i+1][j+1];
                    if (sum == 4){
                        g[i][j] = g[i+1][j] = g[i+2][j] = g[i+1][j-1] = g[i+1][j+1] = 0;
                    }       
                    else f = 0;
                }
            }
        }
        for (int i=0; i<n && f; i++){
            for (int j=0; j<n && f; j++){
                if (g[i][j]) f = 0;
            }       
        }   
        printf("%s
",f?"YES":"NO");
    }   
    return 0;
}

View Code

C. Fox and Box Accumulation

题意：有 n 个盒子，每个盒子有一个属性，si, 表示这个盒子上方能连续放的盒子的数目，每个盒子形状相同，如果一些盒子能摞在一起就称为一堆，

问怎样摞，最后的堆数最少。

分析：二分 + 贪心。

先对盒子按si 大小排序，大的尽量放下面，二分枚举最后的堆数 k;

把盒子从大到小依次放在第 1。。。k 堆，构成最底层，然后在从大到小放好第二层，看看最后能否把盒子放完。

/****************************************
* File Name: 228a.cpp
* Author: sky0917
* Created Time: 2014年02月 3日 23:28:25
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 105;
const int INF = 0x1f1f1f1f;

int n, m;
int a[maxn];
int b[maxn];
int h[maxn];
bool ok(int x){
    sort(a, a+n);
    memset(h, INF, sizeof(h));      
    for (int i=n-1; i>=0; i--){
        int u = i % x;
        if (h[u] == 0)
            return false;   
        h[u] = min(h[u]-1, a[i]);
    }
    return true;
}
void solve(){
    int l = 1, r = n, mid;
    int res;
    while (l <= r){
        mid = (l+r)>>1;
        if (ok(mid)){
            r = mid-1;
            res = mid;
        }
        else{
            l = mid+1;
        }
    }
    printf("%d
",res);
}
int main(){
    while (scanf("%d",&n)!=EOF){
        for (int i=0; i<n; i++){
            scanf("%d",&a[i]);
        }
        solve();
    }
    return 0;
}

View Code

D. Fox and Minimal path

题意：给出一个 k 表示最短路的个数。要求构造出一个节点不大于1000的无向图，使得其最短路的个数为 k ，无向图的边长为1.

分析：可以把 k 看成二进制数，如 k = 100100. 那么 k = 2^5 + 2^2;

2 ^ m 个最短路可以这样构造：取两个节点作为第一层，再取两个节点作为第二层，第一层的每个点和第二层的每个点连一条边，

一直构造出 m 层，那么从第一层到第 m 层的最短路的个数就是 2^m 个。

最后只要把最短路数的个数加起来得到 k 即可。注意点数不够，要重复利用 2 ^ m 中部分点。

这里的程序用四进制。

/****************************************
 * File Name: 228b.cpp
 * Author: sky0917
 * Created Time: 2014年02月 4日 12:28:25
 ****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1001;

int K;
int d[maxn];
int g[maxn][maxn];
int tp;
inline void mark(int x, int y){
    g[x][y] = g[y][x] = 1;
}
void solve(){
    memset(g, 0, sizeof(g));
    tp = 0;
    while (K){
        d[tp++] = K % 4;
        K /= 4;
    }   
    int n = 2;
    for (int i=0; i<tp; i++){
        if (d[i]){
            n += d[i] + i * 4 + (tp-i-1);
        }
    }
    printf("%d
",n);
    int cnt = 2;
    int st;
    for (int i=0; i<tp; i++){
        if (d[i] != 0){
            if (i != tp-1){
                if (tp != 1){   
                    mark(0, cnt);
                    cnt++;
                    for (int j=1; j<tp-i-1; j++){
                        mark(cnt-1, cnt);
                        cnt++;
                    }
                }       
            }   
            if (i == 0){
                st = cnt-1;
                if (tp == 1)
                    st = 0;
                for (int j=0; j<d[i]; j++)
                    mark(st, cnt+j);
                st = cnt;
                cnt += d[i];
                for (int j=st; j<st+d[i]; j++)
                    mark(j, 1); 
                continue;
            }
            st = cnt-1;
            if (i == tp-1)
                st = 0;
            if (d[i] == 1){
                mark(st, cnt);
            }
            else if (d[i] == 2){
                mark(st, cnt);
                mark(st, cnt+1);
            }   
            else if (d[i] == 3){
                mark(st, cnt);
                mark(st, cnt+1);
                mark(st, cnt+2);
            }
            st = cnt;
            cnt += d[i];
            for (int j=st; j<cnt; j++){
                for (int k=0; k<4; k++){
                    mark(j, cnt+k);
                }
            }
            st = cnt;
            cnt += 4;
            for (int j=1; j<i; j++){
                for (int l=0; l<4; l++){
                    for (int k=st; k<st+4; k++){
                        mark(k, cnt+l);
                    }       
                }   
                st = cnt;
                cnt += 4;
            }
            for (int j=st; j<st+4; j++){
                mark(j, 1);
            }
        }
    }
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            if (g[i][j])putchar('Y');
            else putchar('N');
        }
        puts("");
    }
}
int main(){
    while (scanf("%d",&K)!=EOF){
        solve();    
    }   
    return 0;
}

View Code

E. Fox and Card Game

题意：给出 n 堆纸牌，每堆纸牌中每张卡片都有一个数值。

有两个人依次取纸牌，第一个人只能取任意一堆最上方的纸牌，第二个人只能去任意一堆最下方的纸牌，问采取最优策略的情况下，

第一个人拿到的纸牌数值和和的二个人的最大是多少。

分析：对于纸牌数为偶数的牌堆，两个人最后一定是各取一半，因为如果某一堆超过一半对第一个人有利，那么第二个人完全可以采取策略让他

无法使那堆超过一半，第二个人也一样。

对于纸牌数为奇数的堆数要放在一起考虑，第一个人可以利用先手的优势保证一定取到中间的纸牌，第二个人可以控制不让他拿到中间纸牌下方的

牌，但是第一个人拿了某堆中间的牌之后，剩下的牌堆对第二人来说就是先手的形式，他可以取到中间值最大的那堆牌的中间值。最后两个人交替

取完第一大的中间牌，第二大的，...。中间牌上面的牌都是第一个人拿的，下面的都是第二个人拿的最后。

/****************************************
* File Name: 228c.cpp
* Author: sky0917
* Created Time: 2014年02月 3日 23:37:46
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 105;

int a[maxn];
int b[maxn];
int main(){
    int n;
    while (scanf("%d",&n)!=EOF){
        int l = 0, r = 0;
        int tp = 0;
        for (int i=0; i<n; i++){
            int m;
            scanf("%d",&m);
            for (int j=0; j<m; j++)
                scanf("%d", &a[j]);
            if (m & 1){
                b[tp++] = a[m>>1];
            }
            for (int j=0; j<m/2; j++){
                l += a[j];
                r += a[m-j-1];
            }
        }
        sort(b, b+tp);
        for (int i=tp-1; i>=0; i-=2){
            l += b[i];
            if (i >= 0)
                r += b[i-1];
        }
        printf("%d %d
",l, r);
    }   
    return 0;
}

View Code

Codeforces Round #228 (Div. 2)

相关推荐