SDUT-2017年冬休み合宿段階テスト試合3(チーム編成)--解題報告

試合ID:2015
注:本題解参照コードはC++コードです.C使用者の場合、認識していないヘッダファイルが発生した場合、cで始まる場合は、冒頭のcを削除し、末尾に.hを追加することで、Cのヘッダファイルに変換できます.例えば、cstdioはCでstdio.hで、その他は自分で検索してください.また、sort（ ）、stack（ ）など、知らない書き方があれば、ご自分で実現してください.
A - SDUT 2413 n a^o7 !
問題にサインする.文字列を逆順に繰り返し、対応するルールに従って出力すればよい.
参照コード:

#include 
#include 
using namespace std;

int main(int argc, char const *argv[]) {
    int t;
    char str[101];
    scanf("%d%*c", &t);
    for(int l=1; l<=t; ++l) {
        gets(str);
        printf("Case %d: ", l);
        for(int i=strlen(str)-1; i>=0; --i) {
            if(str[i] == '!') putchar('i');
            else if(str[i] == 'u') putchar('n');
            else if(str[i] == 'n') putchar('u');
            else if(str[i] == 'a') putchar('e');
            else if(str[i] == 'e') putchar('a');
            else if(str[i] == 'p') putchar('d');
            else if(str[i] == '7') putchar('l');
            else if(str[i] == '^') putchar('v');
            else if(str[i] == 'w') putchar('m');
            else if(str[i] == '5') putchar('s');
            else putchar(str[i]);
        }
        putchar('
');
    }

    return 0;
}

B-SDUT 2777 Pちゃんの話-不思議な両替
典型的な完全なリュックサックは案数の問題を満たして、私達は3種類の物品があると見なすことができて、重量はそれぞれ1、2、3で、リュックサックの容量はお金の数Nで、リュックサックの案数を満たしてこの問題の答えです.
具体的なアルゴリズムはこのブログを学ぶことをお勧めします:“01リュックサック”と“完全リュックサック”がリュックサックをいっぱい入れる方案の総数の分析と実現.
参照コード:

#include 
using namespace std;

const int MAXC = 32767;
const int MAXN = 3;

int main(int argc, char const *argv[]) {
    int n, w[MAXN+1] = {0, 1, 2, 3,}, dp[MAXC+1] = {0};
    dp[0] = 1;
    for(int i=1; i<=MAXN; ++i) {
        for(int j=w[i]; j<=MAXC; ++j) {
            dp[j] += dp[j-w[i]];
        }
    }
    while(~ scanf("%d", &n)) {
        printf("%d
", dp[n]);
    }

    return 0;
}

C-SDUT 1576マジック47
直接lからrまで遍歴し,残数が47であるか否かを判断し,負数型取りの場合に注意する.
参照コード:

#include 
#include 
#include 
using namespace std;

int main(int argc, char const *argv[]) {
    int n, l, r;
    scanf("%d", &n);
    while(n--){
        scanf("%d %d", &l, &r);
        if(l > r) swap(l, r);
        bool has = false;
        for(int i=l; i<=r; ++i) {
            if(abs(i%100) == 47) {
                printf("%d
", i);
                has = true;
            }
        }
        if(!has) printf("NONE
");
    }

    return 0;
}

D-SDUT 1025ボードの問題
DFSを利用して,遡及タグ行列が使用されたかどうか,kまでの数で答えを記録することができる.
参照コード:

#include 
#include 
using namespace std;

int n, k, ans;
char graph[8][9];
bool vis_r[8], vis_c[8];

void DFS(int r, int num) {
    if(num == k) { //     k，       
        ans++;
        return;
    }
    for(int i=r; i//            
        for(int j=0; j//    
            if(graph[i][j]=='#' && !vis_r[i] && !vis_c[j]) { //     
                vis_r[i] = vis_c[j] = true; //         
                DFS(i, num+1);
                vis_r[i] = vis_c[j] = false; //       
            }
        }
    }
}

int main(int argc, char const *argv[]) {
    while(scanf("%d %d", &n, &k), ~n|~k) {
        memset(vis_r, false, sizeof(vis_r));
        memset(vis_c, false, sizeof(vis_c));
        for(int i=0; iscanf("%s", graph[i]);
        }
        ans = 0;
        DFS(0, 0);
        printf("%d
", ans);
    }

    return 0;
}

E - SDUT 3253 Game!
簡単なゲームでは、後手は先手の鏡像について石を取るだけでいい.
先手が取った後に奇数個残っていれば、後手は対称位置の1つの石を取り、そうでなければ後手は対称位置の2つの石を取り、いつも先手を必ず負けさせることができる.
n<=2先手が一度に取れるときだけ先手が勝つ.
参照コード:

#include 
using namespace std;

int main(int argc, char const *argv[]) {
    int t;
    long long n;
    scanf("%d", &t);
    while(t--){
        scanf("%lld", &n);
        if(n > 2) printf("blankcqk
");
        else printf("zbybr
");
    }

    return 0;
}

F-SDUT 2930人が生きているシリーズの会議
マルチソース最短問題.島ごとのアルファベット番号を数字にマッピングすれば、通常の最短ルートと同じように処理できます.重辺がある可能性があることに注意してください.
参照コード:

#include 
#include 
using namespace std;

const int MAX = 52;
const int INF = 0x3f3f3f3f;

int dis[MAX][MAX];

int GetIdx(char ch) {
    if(ch>='A' && ch<='Z') return ch-'A';
    else return ch-'a'+26;
}

void Floyd() {
    for(int k=0; kfor(int i=0; ifor(int j=0; jif(dis[i][k]+dis[k][j] < dis[i][j])
                    dis[i][j] = dis[i][k]+dis[k][j];
            }
        }
    }
}

int main(int argc, char const *argv[]) {
    int n, d;
    char s1[2], s2[2];
    for(int i=0; i//    
        for(int j=0; j0;
    }
    scanf("%d", &n);
    for(int i=0; iscanf("%s %s %d", s1, s2, &d);
        if(d < dis[GetIdx(s1[0])][GetIdx(s2[0])]) //  ：     
            dis[GetIdx(s1[0])][GetIdx(s2[0])] = dis[GetIdx(s2[0])][GetIdx(s1[0])] = d;
    }
    Floyd();
    int min_dis = INF, idx = -1;
    for(int i=0; i'Z'); ++i) { //   A-Y   Z          
        if(dis[i][GetIdx('Z')] < min_dis) {
            min_dis = dis[i][GetIdx('Z')];
            idx = i;
        }
    }
    printf("%c %d
", idx+'A', min_dis);

    return 0;
}

G-SDUT 2778小明の費用予算
このブログを参考にしてください.
H - SDUT 2162 The Android University ACM Team Selection Contest
やや複雑なシミュレーション問題は、問題の意味に応じてシミュレーションすればいい.
参照コード:

#include 
#include 
using namespace std;

struct info {
    char name[31];
    int A;
    int T;
    int P;
    int idx;
} a[10000], b[10000];

int cmp1(info a, info b) {
    if(a.T != b.T) return a.T > b.T;
    else return a.P < b.P;
}

int cmp2(info a, info b) {
    return a.idx < b.idx;
}

int main(int argc, char const *argv[]) {
    int c, n, m;
    scanf("%d", &c);
    for(int i=1; i<=c; ++i) {
        if(i > 1) printf("
");
        printf("Case %d:
", i);
        int cnt = 0;
        scanf("%d %d", &n, &m);
        for(int j=0; jscanf("%s %d %d %d", a[j].name, &a[j].A, &a[j].T, &a[j].P);
            a[j].idx = j;
            if(a[j].T) cnt++;
        }
        if(cnt < m) {
            for(int j=0; jprintf("%s
", a[j].name);
            }
        }
        else {
            sort(a, a+n, cmp1);
            bool has_all_girl = false, found = false;
            for(int j=0; jif(a[j].A) has_all_girl = true;
            }
            if(!has_all_girl) {
                for(int j=m; jif(a[j].A) {
                        a[m] = a[j];
                        found = true;
                        break;
                    }
                }
            }
            if(found) {
                sort(a, a+m+1, cmp2);
                for(int j=0; j1; ++j) {
                    printf("%s
", a[j].name);
                }
            }
            else {
                sort(a, a+m, cmp2);
                for(int j=0; jprintf("%s
", a[j].name);
                }
            }
        }
    }

    return 0;
}