• The Castle

题意: 一个城堡的房间构成了m*n的矩阵, 其中有的房间是隔着墙的有的则没有. 首先要求城堡可以由墙分成多少个联通块. 如果可以推倒其中一面墙, 问推倒哪面墙可以使得新的联通块的最大的空间的值最大.

分析: 经典'floodfill'问题, 也就是用dfs求联通块. 注意在寻找推倒的墙面的位置时, 题目要求是: 尽量靠近WEST, 否则尽量靠近SOUTH, 同时, N的优先级要高于E, 所以枚举的时候要注意顺序.

/*
ID: geek7774
LANG: C++
TASK: castle
*/

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 55;

int g[N][N];
bool isWall[N][N][5];
int cnt[N*N];
int t;

void floodfill(int x, int y){
    if(g[x][y] != -1) return;

    g[x][y] = t;
    cnt[t]++;

    if(!isWall[x][y][1]){
        floodfill(x, y-1);
    }

    if(!isWall[x][y][2]){
        floodfill(x-1, y);
    }

    if(!isWall[x][y][3]){
        floodfill(x, y+1);
    }

    if(!isWall[x][y][4]){
        floodfill(x+1, y);
    }
}

int main(){
    freopen("castle.in", "r", stdin);
    freopen("castle.out", "w", stdout);
    int m, n;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i){
        for(int j = 1; j <= n; ++j){
            int k;
            scanf("%d", &k);
            for(int p = 0; p < 4; ++p){
                if(k & (1<<p)){
                    isWall[i][j][p+1] = true;
                }
            }
            g[i][j] = -1;
        }
    }

    t = 0;
    for(int i = 1; i <= m; ++i){
        for(int j = 1; j <= n; ++j){
            if(g[i][j] == -1){
                floodfill(i, j);
                ++t;
            }
        }
    }

    int maxE = 0;
    for(int i = 0; i < t; ++i){
        if(cnt[i] > maxE){
            maxE = cnt[i];
        }
    }
    printf("%d\n%d\n", t, maxE);

    int maxS = 0, maxi, maxj;
    char dir;
    for(int j = 1; j <= n; ++j){
        for(int i = m; i >= 1; --i){
            if(i > 1 && g[i][j] != g[i-1][j]){
                int x = cnt[g[i][j]] + cnt[g[i-1][j]];
                if(x > maxS){
                    maxS = x;
                    maxi = i, maxj = j;
                    dir = 'N';
                }
            }

            if(j < n && g[i][j] != g[i][j+1]){
                int x = cnt[g[i][j+1]] + cnt[g[i][j]];
                if(x > maxS){
                    maxS = x;
                    maxi = i, maxj = j;
                    dir = 'E';
                }
            }
        }
    }

    printf("%d\n%d %d %c\n", maxS, maxi, maxj, dir);
    return 0;
}


  • Ordered Fractions

题意: 要求构造介于0/1与1/1之间的所有分数, 满足分数的分母不超过N

分析: 这道题目先构造出所有的分数,然后排序输出. 但是这题很巧妙, 有一个super解法, 也就是递归构造, 至于为什么会这样, 应该是数学的一种美吧.

/*
ID: geek7774
LANG: C++
TASK: frac1
*/

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n;

void solve(int x1, int y1, int x2, int y2){
    int x = x1 + x2, y = y1 + y2;
    if(y > n){
        return ;
    }
    solve(x1, y1, x, y);
    printf("%d/%d\n", x, y);
    solve(x, y, x2, y2);
}

int main(){
    freopen("frac1.in", "r", stdin);
    freopen("frac1.out", "w", stdout);
    scanf("%d", &n);
    printf("0/1\n");
    solve(0, 1, 1, 1);
    printf("1/1\n");
    return 0;
}


  • Sorting A Three-Valued Sequence

题意:类似于荷兰三色旗, 给出一些数字, 他们是1,2,3到一种, 现在要求用最小的置换次数, 让这些数字集合按照1,2,3的顺序排列好

分析:既然要求最小的置换次数, 那么1在2的位置上,2在1的位置上这种情况显然可以直接交换, 1在3,3在1, 2在3,3在2上面也是, 而且这样做肯定是最节省交换次数的, 然后剩下的情况只能是:1在2上, 2在3, 3在1的位置上这种情况

#include<cstdio>
#include<cstring>
using namespace std;
#define minab(a, b) ((a) < (b) ? (a) : (b))
const int N = 1001;
int a[N];

int main(){
    freopen("sort3.in", "r", stdin);
    freopen("sort3.out", "w", stdout);
    int n;
    scanf("%d", &n);
    int x = 0, y = 0, z = 0;
    int xy = 0, xz = 0, yx = 0, yz = 0, zx = 0, zy = 0;
    for(int i = 0; i < n; ++i){
        scanf("%d", &a[i]);
        if(a[i] == 1){
            ++x;
        }
        if(a[i] == 2){
            ++y;
        }
        if(a[i] == 3){
            ++z;
        }
    }

    for(int i = 0; i < x; ++i){
        if(a[i] == 2){
            ++xy;
        }
        if(a[i] == 3){
            ++xz;
        }
    }
    for(int i = x; i < x+y; ++i){
        if(a[i] == 1){
            ++yx;
        }
        if(a[i] == 3){
            ++yz;
        }
    }
    for(int i = x+y; i < n; ++i){
        if(a[i] == 1){
            ++zx;
        }
        if(a[i] == 2){
            ++zy;
        }
    }
    int ans = minab(xy, yx);
    ans += minab(xz, zx) + minab(yz, zy);
    ans += (xy + yx - 2*minab(xy, yx)) << 1;
    printf("%d\n", ans);
    return 0;
}


  • Healthy Holsteins

题意: 每头cow都需要一定的营养, 有v种营养, 每种营养必须到达vi的量。 现有n种能量源, 每种能量源可以提供v种营养, 现在需要求出最少需要几种能量源, 达到营养目标, 成为一头healthy cow.

分析: 考虑到数据范围, 可以用dfs搜索来搜索整个解空间。 当然在搜索到过程种要尽量剪枝

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N = 16;
typedef struct{
    int v[N<<1];
}contain;
contain types[N];

int need[N<<1];
int ans = 0, v, n;
//vector<int > root, *p;
int root[N];

void solve(int *b, int *c, int k, int num){
    if(num > ans) return ;

    bool flag = false;
    for(int i = 0; i < v; ++i){
        if(b[i] < need[i]){
            flag = true;
            break;
        }
    }
    if(!flag){
        if(num < ans){
            ans = num;
            for(int i = 0; i < num; ++i){
                root[i] = c[i];
            }
        }
        return ;
    }

    if(k == n) return;

    for(int i = 0; i < v; ++i){
        b[i] += types[k].v[i];
    }
    c[num] = k + 1;
    solve(b, c, k+1, num+1);

    for(int i = 0; i < v; ++i){
        b[i] -= types[k].v[i];
    }
    solve(b, c, k+1, num);
}

int main(){
    freopen("holstein.in", "r", stdin);
    freopen("holstein.out", "w", stdout);
    scanf("%d", &v);
    for(int i = 0; i < v; ++i){
        scanf("%d", &need[i]);
    }
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < v; ++j){
            scanf("%d", &types[i].v[j]);
        }
    }

    int b[N<<1], c[N<<1];
    memset(b, 0, sizeof(b));
    ans = 1e9;
    solve(b, c, 0, 0);
    printf("%d", ans);
    for(int i = 0; i < ans; ++i){
        printf(" %d", root[i]);
    }
    printf("\n");
    return 0;
}


  • Hamming codes

题意:给出N, B, D, 给出hamming code的定义: binary distance,也就是a,b分别写成二进制之后,每一位上如果数字不同也就是一个0,一个1算一个distance。 需要求出N个数, 每个数表示成B位二进制数之后, 两两之间的hamming code >= D

分析: 这里有一个很trick的想法: 0肯定可以作为N个数的第一个, 因为假设最小的数为k, 而不是0, 那么用k去xor这N个数,得到的新的序列依然是满足条件的(两个数xor同一个数, hamming code并不会改变), 而k xor k = 0, 所以0肯定是第一个数。 确定第一个数, 就可以进行枚举判断, 直到找到N个数为止

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

int N, B, D;
vector<int > ans;

bool check(int a, int b){
    int bit = a ^ b;
    int cnt = 0;
    for(int i = 0; i < B; ++i){
        if((1<<i) & bit){
            ++cnt;
            if(cnt >= D) return true;
        }
    }
    return false;
}

bool solve(int cnt, int k){
    for(int i = 0; i < cnt; ++i){
        if(!check(k, ans[i])) return false;
    }
    return true;
}

int main(){
    freopen("hamming.in", "r", stdin);
    freopen("hamming.out", "w", stdout);
    scanf("%d%d%d", &N, &B, &D);
    ans.clear();
    ans.push_back(0);

    int cnt = 1, cur = 1;
    while(cnt < N){
        if(solve(cnt, cur)){
            ans.push_back(cur);
            ++cnt;
        }
        ++cur;
    }

    for(int i = 0; i < ans.size(); ++i){
        if(i > 0 && i%10 == 0) printf("\n");
        else{
            if(i != 0){
                printf(" ");
            }
        }
        printf("%d", ans[i]);
    }
    printf("\n");
    return 0;
}


  • Preface Numbering

题意: 这道题目是关于罗马编码的问题, 给出一些罗马编码的规则, 需要求出1~N的罗马数字表示里面各种罗马字母出现的次数。

分析: 刚开始觉得这道题目相当繁琐, 后来慢慢分析之后发现可以递归解决。 十位百位千位的情况与个位等同。 只要将个位的数字表达描述好, 就可以用来模拟高位的情况。

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

char *roman[] = {
"", "I", "II", "III", "IV", "V",
"VI", "VII", "VIII", "IX", "X"
};

char* solve(int n, char *val){
    static char ans[10];
    char *p = ans;
    for(char *i = roman[n]; *i; ++p, ++i){
        if(*i == 'I'){
            *p = val[0];
        }
        else if(*i == 'V'){
            *p = val[1];
        }
        else if(*i == 'X'){
            *p = val[2];
        }
    }
    *p = '\0';
    return ans;
}

char* evlos(int n){
    char buffer[31];
    strcpy(buffer, "");
    strcat(buffer, solve(n/1000, "M"));
    strcat(buffer, solve(n/100%10, "CDM"));
    strcat(buffer, solve(n/10%10, "XLC"));
    strcat(buffer, solve(n%10, "IVX"));
//    printf("%s\n", buffer);
    return buffer;
}

int main(){
    freopen("preface.in", "r", stdin);
    freopen("preface.out", "w", stdout);
    int cnt[128];
    for(char *s = "IVXLCDM"; *s; ++s){
        cnt[*s] = 0;
    }

    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        for(char *r = evlos(i); *r; ++r){
            ++cnt[*r];
        }
    }

    for(char *s = "IVXLCDM"; *s; ++s){
        if(cnt[*s]){
            printf("%c %d\n", *s, cnt[*s]);
        }
    }
    return 0;
}


  • Subset Sums

题意: 给出1~N这N个数, 要求把他们分成两份, 两份的sum要相等。

分析: 经典dp问题, 属于背包的范畴。 问题转化为: 从1-N中选k个数, 要求这k个数的和为s. s为1~N和值的一半。 算出的结果发现重复算了两次, 所以要除以2.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 40;
int dp[N];

int main(){
    freopen("subset.in", "r", stdin);
    freopen("subset.out", "w", stdout);
    int n;
    scanf("%d", &n);
    int s = (n)*(n+1)/2;
    if(s & 1){
        printf("\0");
    }
    else{
        s >>= 1;
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for(int i = 1; i <= n; ++i){
            for(int j = s; j >= i; --j){
                dp[j] = dp[j] + dp[j-i];
            }
        }
        printf("%d\n", dp[s]>>1);
    }
    return 0;
}


  • Runaround Numbers

题意: 求满足s条件的数, s条件:一个数字从第一个数字开始, 按本位的数字往下循环访问, 要求能回到首位数字, 而且回到首位数字的时候, 所有的数字刚好被访问一次。 比如147, 刚开始1表示访问1之后的第一个数字4, 之后访问4之后的第4个数字, 到达7, 之后访问7之后的第7个数字,到达1, 至此回到第一个数字, 并且所有第数字被访问了一次, 所以147是满足条件第数。

分析:当第二次访问某个数字当时候, 说明肯定进入了某个循环节, 如果此时并非所有数字都访问过, 那么之后再也不可能被访问到。 同时有可能在数字的后面进入循环节, 再也回不到首位数字。 所以可以通过访问的数字次数进行控制。

#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
char buf[10086];
bool vis[10];
bool digit[128];

bool solve(int n){
    sprintf(buf, "%d", n);
    memset(digit, false, sizeof(digit));
    for(char *p = buf; *p; ++p){
        if(*p == '0') return false;
        if(digit[*p] == true){
            return false;
        }
        digit[*p] = true;
    }
    memset(vis, false, sizeof(vis));
    int cnt = 1, len = strlen(buf), p = 0;
    vis[0] = true;
    if(len == 1) return true;

    while(true){
        p = (p + buf[p] - '0')%len;
        if(vis[p] == true){
            return false;
        }
        vis[p] = true, ++cnt;
        if(cnt == len){
            p = (p + buf[p] - '0')%len;
            if(p == 0){
                return true;
            }
            return false;
        }
    }
}

int main(){
    freopen("runround.in", "r", stdin);
    freopen("runround.out", "w", stdout);
    int n;
    scanf("%d", &n);
    while(++n){
        if(solve(n)){
            printf("%d\n", n);
            break;
        }
    }
    return 0;
}


  • Party Lamps

题意:给出四种操作还有一些lamps, 现在需要执行c次操作, 要求所有的lamp的状态满足给定的条件。

分析: 这种类型的题目, 都要注意:几种操作先后顺序是无关的 & 一种操作执行多次是没有意义的, 等效于执行一次或者没有执行。 那么这样就可以枚举操作了, 因为要满足操作c次, 如果枚举的操作为k次, 只要c-k是偶数就ok了

#include<cstdio>
#include<cstring>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
const int N = 101;
bool isLight[N];
int on[N], off[N];
int n, c, on_cnt, off_cnt;
vector<string > sb;
bool cmp(string a, string b){
    return a < b;
}

void solve(){
    bool suc = false;
    sb.clear();
    //int types = (c <= 16 ? c : 16);
    for(int i = 0; i < 16; ++i){
        int s = i, bit1 = 0;
        while(s){
            s -= s & (-s);
            ++bit1;
        }
        if(bit1 > c) continue;
        if((c-bit1) & 1) continue;
        for(int i = 0; i < n; ++i){
            isLight[i] = 1;
        }
        if(i & (1<<0)){
            for(int j = 0; j < n; ++j){
                isLight[j] ^= 1;
            }
        }
        if(i & (1<<1)){
            for(int j = 0; j < n; j += 2){
                isLight[j] ^= 1;
            }
        }
        if(i & (1<<2)){
            for(int j = 1; j < n; j += 2){
                isLight[j] ^= 1;
            }
        }
        if(i & (1<<3)){
            for(int j = 0; j < n; j += 3){
                isLight[j] ^= 1;
            }
        }
        bool flag = true;
        for(int j = 0; j < on_cnt; ++j){
            if(!isLight[on[j]]){
                flag = false;
                break;
            }
        }
        for(int j = 0; j < off_cnt; ++j){
            if(isLight[off[j]]){
                flag = false;
                break;
            }
        }
        if(flag){
            suc = true;
            string tmp = "";
            for(int j = 0; j < n; ++j){
                tmp += isLight[j] + '0';
            }
            //tmp += '\0';
            sb.push_back(tmp);
        }
    }
    if(!suc){
        printf("IMPOSSIBLE\n");
        return ;
    }

    sort(sb.begin(), sb.end(), cmp);
    for(int i = 0; i < sb.size(); ++i){
        printf("%s\n", sb[i].c_str());
    }
}

int main(){
    freopen("lamps.in", "r", stdin);
    freopen("lamps.out", "w", stdout);
    scanf("%d%d", &n, &c);
    on_cnt = 0, off_cnt = 0;
    int val;
    while(~scanf("%d", &val)){
        if(val == -1) break;
        on[on_cnt++] = val - 1;
    }
    while(~scanf("%d", &val)){
        if(val == -1) break;
        off[off_cnt++] = val - 1;
    }
    solve();
    return 0;
}


  • Longest Prefix

题意: 给出一些单词, 然后给出一个字符串序列, 求这个序列的最长的能够由给出的单词拼接的前缀

分析: 经典dp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
const int N = 200010;

int dp[N];
vector<string > dict;

void solve(string s){
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i = 0; i < s.size(); ++i){
        for(int j = 0; j < dict.size(); ++j){
            if(dict[j].size() > i+1) continue;
            string tmp = s.substr(i - dict[j].size() + 1, dict[j].size());
            if(tmp == dict[j] && dp[i - dict[j].size() + 1]){
                dp[i+1] = 1;
                break;
            }
        }
    }

    for(int i = s.size(); i >= 0; --i){
        if(dp[i]){
            printf("%d\n", i);
            break;
        }
    }
}

int main(){
    freopen("prefix.in", "r", stdin);
    freopen("prefix.out", "w", stdout);
    dict.clear();
    string dc, s, slice;
    while(cin >> dc){
        if(dc == ".") break;
        dict.push_back(dc);
    }

    s = "";
    while(getline(cin, slice)){
        s += slice;
    }
    solve(s);
    return 0;
}


  • Cow Pedigrees

题意: 有一颗二叉树, 该树节点的度只有0或者2两种, 要求用n个节点可以组成多少种树高为k的二叉树

分析: 经典dp。 首先明确一点: 该树的节点个数只能为奇数个(用度很好证明) 对于节点个数为n, 且高度为k的二叉树来说, 可以分解成三种情况:

  • 左子树的高度为k-1, 右子树的高度也为k-1
  • 左子树的高度为k-1, 右子树的高度不超过k-2
  • 右子树的高度为k-1, 左子树的高度不超过k-2

这样就可以找到dp中的子问题, 开两个数组:dp[i][j] 表示高度为i, 节点数为j的二叉树的个数, tree[i][j]表示高度不超过i节点数为j的二叉树个数, 节点数为注意dp的初始化, 以及在dp过程中可以利用树的对称性等。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
int dp[N][N<<1], tree[N][N<<1];
int n, k;
const int MOD = 9901;

void solve(){
    memset(dp, 0, sizeof(dp));
    memset(tree, 0, sizeof(tree));
    dp[1][1] = 1;
    for(int i = 2; i <= k; ++i){
        for(int j = 1; j <= n; j += 2){
        //    dp[i][j] = 0;
            for(int t = 1; t <= j-1-t; t += 2){
                int c = 2;
                if(t == j-1-t){
                    c = 1;
                }
                dp[i][j] += c*dp[i-1][t]*tree[i-2][j-t-1];
                dp[i][j] += c*tree[i-2][t]*dp[i-1][j-t-1];
                dp[i][j] += c*dp[i-1][t]*dp[i-1][j-t-1];
                dp[i][j] %= MOD;
            }
        }
        for(int t = 0; t <= n; ++t){
            tree[i-1][t] += tree[i-2][t] + dp[i-1][t];
            tree[i-1][t] %= MOD;
        }
    }
}

int main(){
    freopen("nocows.in", "r", stdin);
    freopen("nocows.out", "w", stdout);
    scanf("%d%d", &n, &k);
    solve();
    printf("%d\n", dp[k][n]);
    return 0;
}


  • Zero Sum

题意: 1~N N个数, 在这些数字之间填上+, - 或者空格形成一个运算表达式, 要求这个表达式的结果为0

分析: 典型的dfs搜索题。 这种题目就是要正确表达一层一层之间的联系。 在我的代码中, 我带入了初始的符号 +, 相当于在1之前加了一个+号, 这样就能统一计算, 而不用分类讨论。

#include<cstdio>
#include<cstring>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int n;
vector<string > good;
char ans[25];

bool cmp(string a, string b){
    return a < b;
}

void solve(int sum, int k, int cnt, int op){//当前和为sum, 当前计算到1~N中的k,  cnt是记录结果的游标,当前保存的符号为op,  -1表示+,-2表示-
    int s = 0, i;
    bool flag = false;
    for(i = k; i <= n; ++i){
        s = s*10 + i;
        if(flag){
            ans[cnt++] = -3;//blank
        }
        ans[cnt++] = i;
        flag = true;
       // printf("s  = %d\n", s);

        if(i < n){
            if(op == -1){//+
                ans[cnt] = -1;
                solve(sum+s, i+1, cnt+1, -1);
                ans[cnt] = -2;
                solve(sum+s, i+1, cnt+1, -2);
            }
            else{//-
                ans[cnt] = -1;
                solve(sum-s, i+1, cnt+1, -1);
                ans[cnt] = -2;
                solve(sum-s, i+1, cnt+1, -2);
            }
        }

        else{
            int tmp;
            if(op == -1){
                tmp = sum + s;
            }
            else if(op == -2){
                tmp = sum - s;
            }
            if(tmp == 0){
                string res = "";
                for(int j = 0; j < cnt; ++j){
                    if(ans[j] > 0) res += ans[j] + '0';
                    if(ans[j] == -1) res += "+";
                    if(ans[j] == -2) res += "-";
                    if(ans[j] == -3) res += " ";
                }
                good.push_back(res);
            }
            return ;
        }
    }
}

int main(){
    freopen("zerosum.in", "r", stdin);
    freopen("zerosum.out", "w", stdout);
    scanf("%d", &n);
    good.clear();
    solve(0, 1, 0, -1);
    sort(good.begin(), good.end(), cmp);
    for(int i = 0; i < good.size(); ++i){
        printf("%s\n", good[i].c_str());
    }
    return 0;
}


  • Money Systems

题意: 有n中面值的钱币, 给出一个v, 求有多少种方法可以用这n种钱币凑出v

分析: 经典dp, 背包问题。 因为每种钱币可以任取, 所以这是完全背包问题。 所以递推顺序为正向以及设定好初始值就ok了

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 10010;
int n, vm, v[26];
typedef long long LL;
LL dp[N];

void solve(){
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i = 0; i < n; ++i){
        for(int j = v[i]; j <= vm; ++j){
            dp[j] = dp[j] + dp[j-v[i]];
        }
    }
    printf("%lld\n", dp[vm]);
}

int main(){
    freopen("money.in", "r", stdin);
    freopen("money.out", "w", stdout);
    scanf("%d%d", &n, &vm);
    for(int i = 0; i < n; ++i){
        scanf("%d", &v[i]);
    }
    solve();
    return 0;
}


  • Controlling Companies

题意: 公司之间是有控制关系的, 而且控制关系可以传递, 求哪些公司可以控制其他的公司

分析: 多层传递的时候, 只要某一层的公司已经被根节点控制了, 就无所谓控制额是多少了, 因为已经能控制了, 之后的传递关系需要知道的之后的控制额的大小, 而跟本层的控制额没关系。 考虑到数据范围很小, 可以直接暴力dfs搜索

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 101;
int a[N][N];
int control[N];
bool vis[N];

void solve(int cur){
    vis[cur] = true;
    for(int i = 1; i < N; ++i){
        control[i] += a[cur][i];
        if(!vis[i] && control[i] > 50){
            solve(i);
        }
    }
}

int main(){
    freopen("concom.in", "r", stdin);
    freopen("concom.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[x][y] = z;
    }

    for(int i = 1; i < N; ++i){
        memset(vis, false, sizeof(vis));
        memset(control, 0, sizeof(control));
        solve(i);
        for(int j = 1; j < N; ++j){
            if(j != i && control[j] > 50){
                printf("%d %d\n", i, j);
            }
        }
    }
    return 0;
}


  • The Tamworth Two

题意:有个农夫,要找他的牛。 他们在一个10*10的castle中按着某种规则不停的走, 直到他们相遇。 这个规则很简单, 能往前走继续往前走, 不能的话就顺时针转向再走。

分析: 单纯的模拟题。 情况无非就是'101041010*4'种。

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 101;

int fx[4] = {-1, 0, 1, 0};
int fy[4] = {0, 1, 0, -1};
char s[N][N];
bool vis[N][N][4][4];

int next(int p, int d){
    int px = p/10, py = p%10;
    int newx = px + fx[d], newy = py + fy[d];
    if(newx < 0 || newx >= 10 || newy < 0 || newy >= 10 || s[newx][newy] == '*')
        return -1;
    return 10*newx + newy;
}

int solve(int x1, int x2){
    memset(vis, false, sizeof(vis));
    int d1 = 0, d2 = 0;
    int cnt = 0;
    while(1){
        if(vis[x1][x2][d1][d2]) return 0;
        if(x1 == x2) return cnt;
        vis[x1][x2][d1][d2] = true;
        int n1 = next(x1, d1);
        if(n1 == -1){
            d1 = (d1 + 1)%4;
        }
        else{
            x1 = n1;
        }
        int n2 = next(x2, d2);
        if(n2 == -1){
            d2 = (d2 + 1)%4;
        }
        else{
            x2 = n2;
        }
        ++cnt;
    }
}

int main(){
    freopen("ttwo.in", "r", stdin);
    freopen("ttwo.out", "w", stdout);
    int x1, x2;
    for(int i = 0; i < 10; ++i){
        scanf("%s", s[i]);
        for(int j = 0; j < 10; ++j){
            if(s[i][j] == 'C'){
                x1 = i*10 + j;
            }
            if(s[i][j] == 'F'){
                x2 = i*10 + j;
            }
        }
    }

    int ans = solve(x1, x2);
    printf("%d\n", ans);
    return 0;
}


  • Overfencing

题意: fences形成一个mazes, 有两个入口, 不同的maze之间可能连通也可能被阻断 mazes有两个入口, 每个入口可以到达每一个maze, 现在需要求最大的maze距离入口的distance

分析: 毫无疑问用bfs解决最短路, 该题的关键在于格式化输入数据。 写的有将近1h..呵呵哒

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 210;
char s[N][N];
bool vis[N][N];
int dist[N][N], dist2[N][N];
struct node{
    int x, y;
    int cnt;
};
queue<node > q;
int m, n;

void solve(int sx, int sy, int dist[][N]){
    memset(dist, -1, sizeof(dist));
    memset(vis, false, sizeof(vis));
    while(!q.empty()) q.pop();
    node tmp;
    tmp.x = sx, tmp.y = sy, tmp.cnt = 1;
    dist[sx][sy] = 1, vis[sx][sy] = true;
    q.push(tmp);
    int cnt = 0;
    while(!q.empty()){
        node p = q.front();
//        printf("%d %d %d\n", p.x, p.y, p.cnt);
        q.pop();
        int tx = p.x, ty = p.y;
        if(tx >= 3){
            if(s[tx-1][ty] == ' ' && !vis[tx-2][ty]){
                vis[tx-2][ty] = true;
                tmp.x = tx-2, tmp.y = ty, tmp.cnt = p.cnt + 1;
                q.push(tmp);
                dist[tx-2][ty] = tmp.cnt;
            }
        }

        if(tx <= (m<<1)-3){
            if(s[tx+1][ty] == ' ' && !vis[tx+2][ty]){
                vis[tx+2][ty] = true;
                tmp.x = tx+2, tmp.y = ty, tmp.cnt = p.cnt + 1;
                q.push(tmp);
                dist[tx+2][ty] = tmp.cnt;
            }
        }

        if(ty >= 3){
            if(s[tx][ty-1] == ' ' && !vis[tx][ty-2]){
                vis[tx][ty-2] = true;
                tmp.x = tx, tmp.y = ty-2, tmp.cnt = p.cnt + 1;
                q.push(tmp);
                dist[tx][ty-2] = tmp.cnt;
            }
        }

        if(ty <= (n<<1)-3){
            if(s[tx][ty+1] == ' ' && !vis[tx][ty+2]){
                vis[tx][ty+2] = true;
                tmp.x = tx, tmp.y = ty+2, tmp.cnt = p.cnt + 1;
                q.push(tmp);
                dist[tx][ty+2] = tmp.cnt;
            }
        }
    }
}

int main(){
    freopen("maze1.in", "r", stdin);
    freopen("maze1.out", "w", stdout);
    scanf("%d%d", &n, &m);
    getchar();
    for(int i = 0; i < (m<<1|1); ++i){
        gets(s[i]);
    //    puts(s[i]);
    }

    int cnt = 0, x[2], y[2];
    for(int i = 1; i < (n<<1|1); i += 2){
        if(cnt == 2) break;
        if(s[0][i] == ' '){
            x[cnt] = 1, y[cnt] = i;
            ++cnt;
        }
    }
    for(int i = 1; i < (n<<1|1); i += 2){
        if(cnt == 2) break;
        if(s[m<<1][i] == ' '){
            x[cnt] = (m<<1) - 1, y[cnt] = i;
            ++cnt;
        }
    }

    for(int i = 1; i < (m<<1|1); i += 2){
        if(cnt == 2) break;
        if(s[i][0] == ' '){
            x[cnt] = i, y[cnt] = 1;
            ++cnt;
        }
    }
    for(int i = 1; i < (m<<1|1); i += 2){
        if(cnt == 2) break;
        if(s[i][n<<1] == ' '){
            x[cnt] = i, y[cnt] = (n<<1) - 1;
            ++cnt;
        }
    }

    solve(x[0], y[0], dist);
    solve(x[1], y[1], dist2);
    int ans = -1;
    for(int i = 1; i < (m<<1|1); i += 2){
        for(int j = 1; j < (n<<1|1); j += 2){
            int res = dist[i][j];
            if(res > dist2[i][j]){
                res = dist2[i][j];
            }
            if(res > ans){
                ans = res;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}


  • Cow Tours

题意: 一群cows都有自己的一个坐标, 然后这些cows可以分成几个连通块。 现在可以在其中的两个连通块之间加上一条边。 求如何加边可以使得加完边之后的大的连通块的半径最小。 这里的半径可以定义为一个连通块里面最远的两个点之间的距离。

分析: 首先明确对于合并之后的连通块的半径, 它的可能来源:(假设为a,b连通块)

  • a的半径
  • b的半径
  • distance(u,v) + longest(u) + longest(v) (其中u,v是分别属于a,b的点) 显然是选取这三者里面的最大值作为新的连通块的半径, 所以要枚举u,v, 来判断半径的最小值。

  • 所以首先将所有点分块(简单dfs进入不同的vector)

  • 根据得到的不同连通块用o(n3)的floyd求所有点对之间的SSSP,
  • 然后遍历一遍可以求得某个点x在某块里面距离它最远的点离他 的距离
  • 然后再枚举不同的连通块,求它的半径, 并且选取最小值

由于刚开始理解错题意, 以为只有两个连通块, wa了好长时间...WTF!!!

#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 151;
const int INF = 0x3f3f3f3f;
double dist[N][N];
bool vis[N];
char s[N][N];
int x[N], y[N];
int n;
double longest[N];
vector<vector<int > > g;
vector<double > farest;

void solve1(int k, vector<int > &g){
    vis[k] = true;
    g.push_back(k);
    for(int i = 0; i < n; ++i){
        if(s[k][i] == '1' && !vis[i]){
            solve1(i, g);
        }
    }
}

double CalDist(int i, int j){
    return sqrt((x[j]-x[i])*(x[j]-x[i]) + (y[j]-y[i])*(y[j]-y[i]));
}

int main(){
    freopen("cowtour.in", "r", stdin);
    freopen("cowtour.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%d%d", &x[i], &y[i]);
    }
    for(int i = 0; i < n; ++i){
        scanf("%s", s[i]);
    }
    memset(vis, false, sizeof(vis));

    for(int i = 0; i < n; ++i){
        vector<int > q;
        if(!vis[i]){
            solve1(i, q);
            g.push_back(q);
        }
    }

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            dist[i][j] = INF;
        }
    }
    memset(longest, 0, sizeof(longest));
    for(int x = 0; x < g.size(); ++x){
        vector<int > point = g[x];
        for(int i = 0; i < point.size(); ++i){
            dist[point[i]][point[i]] = 0;
            for(int j = 0; j < point.size(); ++j){
                if(s[point[i]][point[j]] == '1'){
                    dist[point[i]][point[j]] = CalDist(point[i], point[j]);
                }
            }
       }

        for(int k = 0; k < point.size(); ++k){
            for(int i = 0; i < point.size(); ++i){
                for(int j = 0; j < point.size(); ++j){
                    if(i != j && dist[point[i]][point[k]] + dist[point[k]][point[j]] < dist[point[i]][point[j]]){
                        dist[point[i]][point[j]] = dist[point[i]][point[k]] + dist[point[k]][point[j]];
                    }
                }
            }
        }

        double ans1 = 0;
        for(int i = 0; i < point.size(); ++i){
            for(int j = 0; j < point.size(); ++j){
                if(dist[point[i]][point[j]] > ans1){
                    ans1 = dist[point[i]][point[j]];
                }
                if(dist[point[i]][point[j]] > longest[point[i]]){
                    longest[point[i]] = dist[point[i]][point[j]];
                }
            }
        }
        farest.push_back(ans1);
    }

    /*
    for(int i = 0; i < farest.size(); ++i){
        printf("%lf ", farest[i]);
    }
    for(int i = 0; i < n; ++i){
        printf("%lf ", longest[i]);
    }*/

    double ans = 1e9;
    for(int i = 0; i < g.size(); ++i){
        for(int j = i+1; j < g.size(); ++j){
            vector<int > u = g[i], v = g[j];
            double ans1 = 1e9;
            for(int l = 0; l < u.size(); ++l){
                for(int k = 0; k < v.size(); ++k){
                    double tmp = CalDist(u[l], v[k]) + longest[u[l]] + longest[v[k]];
                    if(tmp < farest[i]) tmp = farest[i];
                    if(tmp < farest[j]) tmp = farest[j];
                    if(tmp < ans1){
                        ans1 = tmp;
                    }
                }
            }
            if(ans1 < ans){
                ans = ans1;
            }

        }
    }
    printf("%.6lf\n", ans);
    return 0;
}


  • Bessie Come Home

题意: 给出一些road的连接, 现在要从Z出发, 寻找最短路

分析: 考虑到点的范围在'a-z' 'A-Z'之间, 直接ASCII表走起。。 然后dijkstra寻路ok, 注意dijkstra的结束条件~

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 128;
const int INF = 1e9;
int a[N][N];
int dist[N];
bool vis[N];

void solve(int src){
    dist[src] = 0;
    while(1){
        int min = INF, minj = -1;
        for(int i = 0; i < N; ++i){
            if(!vis[i] && dist[i] < min){
                min = dist[i];
                minj = i;
            }
        }
        if(min >= INF){
            break;
        }
        vis[minj] = true;
        bool flag = false;
        for(int i = 0; i < N; ++i){
            if(dist[minj] + a[minj][i] < dist[i]){
                dist[i] = dist[minj] + a[minj][i];
                flag = true;
            }
        }
    }
}

int main(){
    freopen("comehome.in", "r", stdin);
    freopen("comehome.out", "w", stdout);
    int n;
    scanf("%d", &n);
    getchar();
    for(int i = 0; i < N; ++i){
        dist[i] = INF;
    }
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            a[i][j] = INF;
        }
    }
    for(int i = 0; i < n; ++i){
        char x, y;
        int d;
        scanf("%c %c %d", &x, &y, &d);
        if(d < a[x][y]){
            a[x][y] = d, a[y][x] = d;
        }
        getchar();
    }

    memset(vis, false, sizeof(vis));
    solve('Z');
    int ans = INF, pos;
    for(int i = 0; i < N; ++i){
        if(i >= 'A' && i < 'Z' && dist[i] != INF){
            if(ans > dist[i]){
                ans = dist[i];
                pos = i;
            }
        }
    }
    printf("%c %d\n", pos, ans);
    return 0;
}


  • Fractions to Decimals

题意: 给出n, k, 求出n/k的小数形式, 要么是有限小数, 要么是无限循环小数

分析: 模拟除法过程, 记录出现的余数, 要么除尽, 要么寻找余数的循环节。 注意每76个字符输出一行, 所以每输出一个字符都要记录当前输出字符个数

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int v[N], p[N];

int main(){
    freopen("fracdec.in", "r", stdin);
    freopen("fracdec.out", "w", stdout);
    int n, k;
    scanf("%d%d", &n, &k);
    int d = n%k, cnt = 0;
    memset(v, -1, sizeof(v));
    printf("%d.", n/k);
    int x = n/k;
    int ccc = 0;
    if(x == 0){
        ccc = 1;
    }
    while(x){
        ++ccc, x /= 10;
    }
    ++ccc;
    //printf("%d  ", ccc);
    while(1){
        if(d == 0){
            if(cnt == 0){
                printf("0");
            }
            for(int i = 0; i < cnt; ++i){
                if(ccc%76 == 0){
                    printf("\n");
                }
                ++ccc;
                printf("%d", p[i]);
            }
            break;
        }
        if(v[d] != -1){
            int pos = v[d];
            for(int i = 0; i < pos; ++i){
                if(ccc%76 == 0){
                    printf("\n");
                }
                ++ccc;
                printf("%d", p[i]);
            }
            if(ccc%76 == 0){
                puts("");
            }
            ++ccc;
            printf("(");
            for(int i = pos; i < cnt; ++i){
                if(ccc%76 == 0) printf("\n");
                ++ccc;
                printf("%d", p[i]);
            }
            if(ccc%76 == 0){
                puts("");
            }
            ++ccc;
            printf(")");
            break;
        }
        v[d] = cnt;
        p[cnt++] = (d*10)/k;
        d = (d*10)%k;
    }
    printf("\n");
    return 0;
}


第二章完结, 整体来说, 第二章属于算法基础题, 没有什么高级算法, 但是考察编程基本功。 有些题目看起来实现简单,然而容易出错, 而且如何将问题用代码精准的高效的描述出来是一个重点

相似文章


最近发表的文章

全部文章

评论区

comments powered by Disqus 回到顶部