比賽 ID: 2015
注：本題解參考代碼均為 C++ 代碼，如果你是 C 使用者，出現不認識的頭檔案時，若是
c
開頭的，一般可以通過去掉開頭的
c
然後在末尾添加
.h
來轉換成 C 的頭檔案，如
cstdio
在 C 中為
stdio.h
，其他的請自行搜尋。另外，如果出現不認識的寫法，如
sort（排序）
、
stack（棧）
等，請自行實作。
A - SDUT 2413 n a^o7 !
簽到題。逆序周遊一遍字元串，根據對應規則輸出即可。
參考代碼：
#include <cstdio>
#include <cstring>
using namespace std;
int main(int argc, char const *argv[]) {
int t;
char str[];
scanf("%d%*c", &t);
for(int l=; l<=t; ++l) {
gets(str);
printf("Case %d: ", l);
for(int i=strlen(str)-; i>=; --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('\n');
}
return ;
}
B - SDUT 2777 小P的故事——神奇的換零錢
典型的完全背包裝滿方案數的題，我們可以看做有 3 種物品，重量分别為 1, 2, 3，背包容量為錢數 N，裝滿背包的方案數就是此題的答案。
具體算法推薦學習這篇部落格：背包問題——“01背包”及“完全背包”裝滿背包的方案總數分析及實作。
參考代碼：
#include <cstdio>
using namespace std;
const int MAXC = ;
const int MAXN = ;
int main(int argc, char const *argv[]) {
int n, w[MAXN+] = {, , , ,}, dp[MAXC+] = {};
dp[] = ;
for(int i=; i<=MAXN; ++i) {
for(int j=w[i]; j<=MAXC; ++j) {
dp[j] += dp[j-w[i]];
}
}
while(~ scanf("%d", &n)) {
printf("%d\n", dp[n]);
}
return ;
}
C - SDUT 1576 魔幻數字47
直接從 l 周遊 到 r，判斷餘數是否為 47 即可，注意負數取模的情況。
參考代碼：
#include <cstdio>
#include <cstdlib>
#include <algorithm>
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%) == ) {
printf("%d\n", i);
has = true;
}
}
if(!has) printf("NONE\n");
}
return ;
}
D - SDUT 1025 棋盤問題
可以 DFS 一下，并利用回溯标記行列有沒有用過，數量到 k 時記錄答案。
參考代碼：
#include <cstdio>
#include <cstring>
using namespace std;
int n, k, ans;
char graph[][];
bool vis_r[], vis_c[];
void DFS(int r, int num) {
if(num == k) { // 數量到 k，記錄答案并傳回
ans++;
return;
}
for(int i=r; i<n; ++i) { // 從目前行開始向下枚舉行
for(int j=; j<n; ++j) { // 枚舉列
if(graph[i][j]=='#' && !vis_r[i] && !vis_c[j]) { // 符合條件
vis_r[i] = vis_c[j] = true; // 标記此行列已用過
DFS(i, num+);
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=; i<n; ++i) {
scanf("%s", graph[i]);
}
ans = ;
DFS(, );
printf("%d\n", ans);
}
return ;
}
E - SDUT 3253 Game!
簡單博弈，後手隻需要跟着先手鏡像取石子即可。
如果先手取完後剩餘奇數個，則後手取對稱位置的 1 個石子，否則後手取對稱位置的 2 個石子，總能使先手必輸。
隻有當 n <= 2 先手可以一次取完時，先手才必勝。
參考代碼：
#include <cstdio>
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 > ) printf("blankcqk\n");
else printf("zbybr\n");
}
return ;
}
F - SDUT 2930 人活着系列之開會
多源最短路問題。把每個島的字母編号映射成數字就可以和普通最短路一樣處理了，注意可能有重邊。
參考代碼：
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX = ;
const int INF = ;
int dis[MAX][MAX];
int GetIdx(char ch) {
if(ch>='A' && ch<='Z') return ch-'A';
else return ch-'a'+;
}
void Floyd() {
for(int k=; k<MAX; ++k) {
for(int i=; i<MAX; ++i) {
for(int j=; j<MAX; ++j) {
if(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[], s2[];
for(int i=; i<MAX; ++i) { // 初始化
for(int j=; j<MAX; ++j) {
dis[i][j] = INF;
}
dis[i][i] = ;
}
scanf("%d", &n);
for(int i=; i<n; ++i) {
scanf("%s %s %d", s1, s2, &d);
if(d < dis[GetIdx(s1[])][GetIdx(s2[])]) // 坑：可能有重邊
dis[GetIdx(s1[])][GetIdx(s2[])] = dis[GetIdx(s2[])][GetIdx(s1[])] = d;
}
Floyd();
int min_dis = INF, idx = -;
for(int i=; i<GetIdx('Z'); ++i) { // 找 A-Y 到 Z 的最短路中的最小值
if(dis[i][GetIdx('Z')] < min_dis) {
min_dis = dis[i][GetIdx('Z')];
idx = i;
}
}
printf("%c %d\n", idx+'A', min_dis);
return ;
}
G - SDUT 2778 小明的花費預算
請參考這篇部落格。
H - SDUT 2162 The Android University ACM Team Selection Contest
稍複雜的模拟題，按題意模拟即可。
參考代碼：
#include <cstdio>
#include <algorithm>
using namespace std;
struct info {
char name[];
int A;
int T;
int P;
int idx;
} a[], b[];
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=; i<=c; ++i) {
if(i > ) printf("\n");
printf("Case %d:\n", i);
int cnt = ;
scanf("%d %d", &n, &m);
for(int j=; j<n; ++j) {
scanf("%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=; j<n; ++j) {
printf("%s\n", a[j].name);
}
}
else {
sort(a, a+n, cmp1);
bool has_all_girl = false, found = false;
for(int j=; j<m; ++j) {
if(a[j].A) has_all_girl = true;
}
if(!has_all_girl) {
for(int j=m; j<cnt; ++j) {
if(a[j].A) {
a[m] = a[j];
found = true;
break;
}
}
}
if(found) {
sort(a, a+m+, cmp2);
for(int j=; j<m+; ++j) {
printf("%s\n", a[j].name);
}
}
else {
sort(a, a+m, cmp2);
for(int j=; j<m; ++j) {
printf("%s\n", a[j].name);
}
}
}
}
return ;
}
![CF1394C 計算幾何[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)