USACO Section 2.2

USACO Section 2.2
Preface Numbering

/*
    ID: beihai2013
    TASK: preface
    LANG: C++
*/
/*每次取最大的合法数的组合删去,类似于二进制表示*/
#include bits/stdc++.h
using namespace std;
#define LL long long
const int MAXN = 3500 + 5;
const int MAXM = 7 + 3;
int v0[MAXM] = {1, 5, 10, 50, 100, 500, 1000};
int v[MAXM * 2];
int vis[MAXN];
LL cnt[MAXN][MAXM];
char str[] = "IVXLCDM";
void init()
{
    for(int i = 1 ; i  MAXN ; i++) {
        for(int j = 0 ; j  7 ; j++) cnt[i][j] = 0;
        int temp = i;
        for(int j = 6 ; j = 0 ; j--) {
            while(temp = v0[j]) {
                temp -= v0[j];
                cnt[i][j]++;
            }
            for(int k = j - 1 ; k = max(j - 2, 0) ; k--) {
                if(k % 2) continue;
                int ok = 0;
                while(temp = v0[j] - v0[k]) {
                    temp -= v0[j] - v0[k];
                    cnt[i][j]++;
                    cnt[i][k]++;
                    ok = 1;
                }
                if(ok) break;
            }
        }
    }
//    for(int i = 1 ; i = 5 ; i++) {
//        printf("i = %d, ", i);
//        for(int j = 0 ; j  7 ; j++) printf("%I64d ", cnt[i][j]);
//        puts("");
//    }
    for(int i = 1 ; i  MAXN ; i++) {
        for(int j = 0 ; j  7 ; j++) cnt[i][j] += cnt[i - 1][j];
    }
}
int main()
{
    freopen("preface.in", "r", stdin);
    freopen("preface.out", "w", stdout);
    init();
    int n;
    while(scanf("%d", n) != EOF) {
        for(int i = 0 ; i  MAXM ; i++) {
            if(cnt[n][i]) {
                printf("%c %lld\n", str[i], cnt[n][i]);
            }
        }
    }
    return 0;
}

Subset Sums

/*
    ID: beihai2013
    TASK: subset
    LANG: C++
*/
/*
    首先判断有没有解,即所有数和的一半是否为整数
    其次记忆化搜索
*/
#include bits/stdc++.h
using namespace std;
#define LL long long
const int MAXN = 40;
int vis[MAXN];
LL dp[(MAXN + 1) * MAXN / 2 + 1][MAXN];
LL dfs(int rest, int mark)
{
    if(rest == 0) return 1;
    else if(rest  0) return 0;
    else if(dp[rest][mark]) return dp[rest][mark];
    else if((mark + 1) * mark / 2  rest) return 0;
    else {
        dp[rest][mark] = 0;
        for(int i = mark ; i = 1 ; i--) dp[rest][mark] += dfs(rest - i, i - 1);
//        if(dp[rest][mark] != 0) printf("dp[%d][%d] = %lld\n", rest, mark, dp[rest][mark]);
        return dp[rest][mark];
    }
}
int main()
{
    freopen("subset.in", "r", stdin);
    freopen("subset.out", "w", stdout);
    int n;
    while(scanf("%d", n) != EOF) {
        int temp = (n + 1) * n / 2;
        if(temp % 2 == 0) printf("%lld\n", dfs(temp / 2, n) / 2);
        else printf("0\n");
    }
    return 0;
}

Runaround Numbers

/*
    ID: beihai2013
    TASK: runround
    LANG: C++
*/
/*
    竟然是暴力……刚开始以为数据很少能不能预处理出所有合法数然后二分
    跑了小数据发现合法数特别多,所以试了一发暴力
    偷看了一组数据枪毙两分钟
*/
#include bits/stdc++.h
using namespace std;
bool check(unsigned int u)
{
//    int debug = u == 147 ? 1 : 0;
    if(u  10) return true;
    int a[10], cnt = 0;
    while(u) {
        a[cnt++] = u % 10;
        if(u % 10 == 0) return false;
        u /= 10;
    }
    for(int i = 0 ; i  cnt / 2 ; i++)
        swap(a[i], a[cnt - 1 - i]);
//    if(debug)
//    for(int i = 0 ; i  cnt ; i++) printf("%d ", a[i]);
    int vis[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
    int now = 0, num = 1;
    vis[a[now]] = 1;
//    printf("cnt = %d\n", cnt);
    while(num  cnt) {
        now = (now + a[now]) % cnt;
//        printf("now = %d, cnt = %d\n", now, num);

        if(vis[a[now]] == 1) {
//            if(debug) printf("num = %d, now = %d, a = %d\n", num, now, a[now]);
            break;
        }
        else vis[a[now]] = 1;
        num++;
    }
    if(num  cnt || (now + a[now]) % cnt != 0) return false;
    else return true;
}
int main()
{
    freopen("runround.in", "r", stdin);
    freopen("runround.out", "w", stdout);
    unsigned int n = 1;
    while(cin  n) {
        for(unsigned int u = n + 1; u = 999999999; u++) {
            if(check(u)) {
                cout  u  endl;
                break;
            }
        }
        n++;
    }
    return 0;
}

Party Lamps

/*
    ID: beihai2013
    TASK: lamps
    LANG: C++
*/
/*
    一个操作使用两次相当于没有使用,总共四种操作
    因此,用二进制枚举使用了哪些操作,得到对应的01串为可能合法的答案集合

    此时,就要判断已经用了当前次数后,是否能毫无改变的达到最终状态
    通常会想到周期为2的判断,但是也可能几个二进制枚举的组合使得一个01串不发生改变,预处理出来
    此处写残,就是没把一个操作都没取的组合特判掉

    最后答案用string输出方便排序,此处有坑就是会出现重复的string需要稍加判断
*/
#include bits/stdc++.h
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define pb push_back
typedef pairint,int pii;
pii cal(int u)
{
    if(u == 0) return mp(0, 1);
    else if(u == 1) return mp(0, 2);
    else if(u == 2) return mp(1, 2);
    else return mp(0, 3);
}
const int MAXN = 100 + 5;
const int MAXM = 4 + 2;
bool stor[1  MAXM][MAXN];
int v[MAXN];
int mul[MAXN], mulcnt;
string out[1  MAXM];
int outcnt;
bool check2(int c, int cnt)
{
    int temp = c - cnt;
//    printf("temp = %d\n", temp);
    for(int i = 0 ; i  mulcnt ; i++) if(temp % mul[i] == 0) return true;
    return false;
}
int main()
{
    freopen("lamps.in", "r", stdin);
    freopen("lamps.out", "w", stdout);
    int n, c;
    while(scanf("%d%d", n, c) != EOF) {
        for(int i = 0 ; i  n ; i++) v[i] = 0;
        int u;
        while(scanf("%d", u) != EOF  u != -1) v[u - 1] = 1;
        while(scanf("%d", u) != EOF  u != -1) v[u - 1] = -1;
        mulcnt = 0;
        mul[mulcnt++] = 2;
        outcnt = 0;
        for(int i = 0 ; i  (1  4) ; i++) {
//            printf("i = %d\n", i);
            for(int j = 0 ; j  n ; j++) stor[i][j] = 1;
            for(int j = 0 ; j  4 ; j++) {
                if((1  j)  i) {
                    pii p = cal(j);
                    while(p.fi  n) {
                        stor[i][p.fi] = (stor[i][p.fi] == 0 ? 1 : 0);
                        p.fi += p.se;
                    }
                }
            }
            int cnt = 0;
            int ok = 1;
            for(int j = 0 ; j  n ; j++) if(stor[i][j] == 0) {ok = 0; break;}
            if(ok  i) {
                for(int j = 0 ; j  4 ; j++) if((1  j)  i) cnt++;
                mul[mulcnt++] = cnt;
            }
        }
//        puts("first");
        int flag = 1;
        for(int i = 0 ; i  (1  4) ; i++) {
//            printf("i = %d\n", i);
            int ok = 1;
            for(int j = 0 ; j  n ; j++) {
                if(v[j] == 1  stor[i][j] == 0) ok = 0;
                else if(v[j] == -1  stor[i][j] == 1) ok = 0;
                if(ok == 0) break;
            }
            if(ok == 0) continue;
            int cnt = 0;
            for(int j = 0 ; j  4 ; j++) if((1  j)  i) cnt++;
//            puts("second");
            if(cnt  c) continue;
            else if(!check2(c, cnt)) continue;
//            puts("third");
            out[outcnt] = "";
            for(int j = 0 ; j  n ; j++) out[outcnt] += stor[i][j] + '0';
            outcnt++;
            flag = 0;
        }
        sort(out, out + outcnt);
        for(int i = 0 ; i  outcnt ; i++) {
            if(i == 0 || out[i] != out[i - 1]) cout  out[i]  endl;
        }
        if(flag) puts("IMPOSSIBLE");
    }
    return 0;
}
/*
24
41
2 11 5 15 -1
-1
*/
最新回复(0)
/jishuBl3Exa78tsWRdGdr_2FVHagM5SDjC_2BkNqhge_2BwDoTaDXw_3D4858379
8 简首页