2015 ICPC North American Qualifier Contest，原题链接

A – All about that base

题意

给你一个算式，问你这个算式中的数字在（1-36进制中）哪些进制下是合法的，输出所有合法的进制（10-35进制用a-z表示，36进制用0表示），否则输出invalid。只有满足所有数字的表示合法以及算式运算也合法才算合法。注意1进制此题规定只含有一个数字1，转换成十进制就是看有几个1（如1111表示十进制的4）。

分析

首先，数据的处理，可以按行读入然后按空格用字符串表示出每个数字和操作符。其次是进制转换，写个函数，转换成十进制来计算，进制转换过程中还要判断一下每位数字是否超过当前的进制。最后在十进制下判断算式是否正确。另外，本题要用longlong，1进制需要特殊处理，除法需要保证整除才算合法。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
typedef pair<LL, LL> PII;

LL change(int base, string s, int &flag) {//进制转换+判断每位数字合法性
    LL num, ans = 0;
    LL now = 1;
    for (int i = s.size() - 1; i >= 0; i--) {
        int num;
        if (s[i] >= 'a' && s[i] <= 'z')
            num = s[i] - 'a' + 10;
        else
            num = s[i] - '0';
        if (num >= base) {
            flag = 1;
            break;
        }
        ans += num * now;
        now *= base;
    }
    return ans;
}

int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    getchar();
    while (t--) {
        string s;
        getline(cin, s);
        string a, b, c, op, now;
        int cnt = 0;//记录当前是第几个空格
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                cnt++;
                if (cnt == 1)
                    a = now;
                else if (cnt == 3)
                    b = now;
                else if (cnt == 2)
                    op = now;
                now.clear();
            } else {
                now += s[i];
            }
        }
        c = now;
        LL x, y, z;
        int f = 0, flag = 0;
        //特殊判断1进制是否合法
        for (int i = 0; i < a.size(); i++) {
            if (a[i] != '1') {
                flag = 1;
                break;
            }
        }
        for (int i = 0; i < b.size(); i++) {
            if (b[i] != '1') {
                flag = 1;
                break;
            }
        }
        for (int i = 0; i < c.size(); i++) {
            if (c[i] != '1') {
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            if (op[0] == '-' && a.size() - b.size() == c.size())
                printf("1"), f = 1;
            else if (op[0] == '+' && a.size() + b.size() == c.size())
                printf("1"), f = 1;
            else if (op[0] == '*' && a.size() * b.size() == c.size())
                printf("1"), f = 1;
            else if (op[0] == '/' && a.size() % b.size() == 0 &&
                     a.size() / b.size() == c.size())//除法要整除
                printf("1"), f = 1;
        }
        //判断2-36进制是否合法
        for (int i = 2; i <= 36; i++) {
            flag = 0;
            x = change(i, a, flag);
            y = change(i, b, flag);
            z = change(i, c, flag);
            if (flag == 1) continue;
            char ans;
            if (i == 36)
                ans = '0';
            else if (i >= 10)
                ans = 'a' + i - 10;
            else
                ans = '0' + i;
            if (op[0] == '+' && x + y == z)
                printf("%c", ans), f = 1;
            else if (op[0] == '-' && x - y == z)
                printf("%c", ans), f = 1;
            else if (op[0] == '*' && x * y == z)
                printf("%c", ans), f = 1;
            else if (op[0] == '/' && x % y == 0 && x / y == z)
                printf("%c", ans), f = 1;
        }
        if (f == 0)
            puts("invalid");
        else
            puts("");
        // puts("_____________");
        // cout << a << ' ' << b << ' ' << c <<endl;
    }
    return 0;
}

B – Bobby’s Bet（概率）

题意

两人打赌，对于一个S面的骰子，若投Y次出现至少X次大于面值等于R则赢W元，否则输1元，问你期望的回报是否大于1元。

分析

就是一道期望题，求出全部的期望即可，首先算出单次赢的概率是$(s – r + 1) / s$,输的概率是$(r-1)/s$可能的情况有赢x次，x+1次一直到y次，对于赢x次的概率即 $C_y^x* (win)^x*(lose)^{y-x}$,其中win表示单次赢的概率，lose表示单次输的概率，求出所有的概率相加即最终赢的概率，乘w就是期望和1比较大小即可。可以发现的是无论输赢的概率分母都是s，且每次求概率时win和lose的幂之和为y，那么对于每次概率如果不约分那么分母都是 $s^y$，所以只要计算出分子即可。组合数用递推预处理，幂运算写个快速幂即可，记得longlong。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
typedef pair<LL, LL> PII;
int c[111][111];

void init() {
    c[0][0] = 1;
    for (int i = 1; i < 20; i++) {
        c[i][0] = 1;
        for (int j = 1; j < 20; j++) {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
    }
}
LL qmi(LL a, LL b) {
    LL ans = 1;
    while (b) {
        if (b & 1) {
            ans *= a;
        }
        a *= a;
        b /= 2;
    }
    return ans;
}
int main(int argc, char const *argv[]) {
    int t;
    init();
    cin >> t;
    while (t--) {
        LL r, s, x, y, w;
        cin >> r >> s >> x >> y >> w;
        LL win = s - r + 1, lose = r - 1;
        LL mu = pow(s, y);
        LL ans = 0;
        for (LL i = x; i <= y; i++) {
            ans += 1.0 * qmi(win, i) * qmi(lose, y - i) * c[y][i] * 1.0;
        }
        ans = ans * w;
        if (ans <= mu)
            puts("no");
        else
            puts("yes");
    }
    return 0;
}

D – Circuit Counting（思维+DFS）

题意

给你n个向量，任选几个组成一个集合使得集合内向量和为0，求集合个数。

分析

由于n<=40，第一反应想到dfs爆搜，但是 $2^{40}$ 还是太大了，可以进行两次dfs，运用到一点记忆化的思想，先对前n/2个向量dfs枚举出所有可能，$dp[i][j]$ 记录集合的向量和为 $（i，j）$ 的集合数。再对后n/2个向量进行dfs，若集合的向量和为 $(x,y)$ ，则答案加上 $dp[-x][-y]$ ,由于负数不能作为下标，所以下标全部加上一个基数，保证全部为正数。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e3+10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int n, m;
PII vec[maxn];
LL dp[maxn][maxn];
LL ans;
void dfs(int now, int x, int y) {
    if (now == m + 1) {
        dp[x + 500][y + 500]++;
        return;
    }
    dfs(now + 1, x, y);
    dfs(now + 1, x + vec[now].first, y + vec[now].second);
}
void dfs1(int now, int x, int y) {
    if (now == n + 1) {
        ans += (LL)dp[500 - x][500 - y];
        return;
    }
    dfs1(now + 1, x, y);
    dfs1(now + 1, x + vec[now].first, y + vec[now].second);
}

int main(int argc, char const *argv[]) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> vec[i].first >> vec[i].second;
    }
    m = n / 2;
    dfs(1, 0, 0);
    dfs1(m + 1, 0, 0);
    cout << ans - 1 << endl;
    return 0;
}

F – Quick Brown Fox（桶排）

题意

给你一串字符串，忽略大小写，问你a-z中有几个没出现过，若都出现过则输出“pangram”。

分析

写个桶排判断一下大小写，记录每个字符串出现的次数，遍历输出一遍即可。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
string co = "Simon says ";
int tong[200];
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    getchar();
    while(t--) {
        memset(tong,0, sizeof tong);
        string s;
        getline(cin, s);
        for(int i = 0; i < s.size(); i++) {
            if(s[i]>='a' && s[i] <= 'z') {
                tong[s[i]]++;
            }else if(s[i]>='A' && s[i] <= 'Z') {
                tong[s[i] + 32]++;
            }
        }
        vector<char> ans;
        for(int i = 'a'; i <= 'z'; i++){
            if(tong[i] == 0) {
                ans.push_back((char)i);
            }
        }
        if (ans.size() == 0) puts("pangram");
        else{
            cout << "missing ";
            for (int i = 0; i < ans.size(); i++) cout << ans[i];
            puts("");
        }
    }
    return 0;
}

H – Secret Message(签到)

题意

给你一串字符串，将其按从上到下，从左到右的顺序填入到一个M * M的矩阵中，M * M为大于等于字符串长度的最小值，多余的格子用“ * ”填满，然后将矩阵顺时针旋转90度，再按照从上到下从左到右的顺序输出字符串，忽略“ * ”。

分析

没啥好分析的，做就完事了。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
char ans[1000][1000];
char chu[1000][1000];
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while(t--) {
        string s;
        cin >> s;
        int m = 1;
        while(m*m < s.size())m++;
        int now = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < m; j++) {
                if(now < s.size()){
                    chu[i][j] = s[now++];
                }
                else chu[i][j] = '*';
            }
        }
        now = 0;
        for(int i = m-1; i >= 0; i--) {
            for(int j = 0; j < m; j++) {
                ans[j][now] = chu[i][j];
            }
            now++;
        }
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < m; j++) {
                if(ans[i][j] != '*')
                printf("%c",ans[i][j]);
            }
        }
        puts("");
    }
    return 0;
}

I – Simon Says(签到)

题意

给你n个字符串，若某个字符串的最前面两个单词为“Simon says”则输出剩下的字符串，否则跳过。

分析

注意判断时必须判断“Simon says”后面还带个空格，若出现“Simon saysxxx”这样的不能输出。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
string co = "Simon says ";
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    getchar();
    while(t--) {
        string s;

        getline(cin, s);
        int f = 0;
        for(int i = 0; i < 11; i++) {
            if(s[i] != co[i]) {
                f = 1;
                break;
            }
        }
        if(!f) {
            for(int i = 11; i < s.size(); i++) cout << s[i];
            puts("");
        }
    }
    return 0;
}

J – Torn To Pieces(简单图论)

题意

告诉你每个站点和哪些站点相连，告诉你起点和终点，问你是否可以从起点走到终点，输出路径。

分析

比赛时读错题了，以为可能有多条路径，求最短路，就写了个Dijkstra记录路径，实际上直接bfs一遍就行了。另外站点是用字符串形式给出的，用unordered_map存一下下标就行了。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int cnt;
int t, st, ed;
unordered_map<string,int> id;
unordered_map<int,string> fan;
int get_id(string s) {
    if(id.count(s) == 0) {
        id[s] = ++cnt;
        fan[cnt] = s;
    }
    return id[s];
}
int mp[111][111], dis[111], path[111];
bool vis[111];
void dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    dis[st] = 0;
    path[st] = -1;
    priority_queue<PII> q;
    q.push({0,st});
    while(q.size()) {
        int now = q.top().second;
        q.pop();
        if(vis[now]) continue;
        vis[now] = 1;
        for(int i = 1; i <= cnt; i++) {
            if(mp[now][i] == 1 && dis[i] > dis[now] + 1) {
                dis[i] = dis[now] + 1;
                path[i] = now;
                q.push({-dis[i],i});
            } 
        }
    }
}
int main(int argc, char const *argv[]) {
    cin >> t;
    string s;
    getchar();
    while(t--) {
        getline(cin, s);
        string now;
        int kong = 0;
        int x;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == ' ') {
                kong++;
                if(kong == 1) {
                    x = get_id(now);
                }
                else {
                    mp[x][get_id(now)] = 1;
                    mp[get_id(now)][x] = 1;
                }
                now.clear();
            }
            else now += s[i];
        }
        mp[x][get_id(now)] = 1;
        mp[get_id(now)][x] = 1;
    }
    getline(cin, s);
    string now;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == ' ') {
            st = get_id(now);
            now.clear();
        } else
            now += s[i];
    }
    ed = get_id(now);
    dijkstra();
    if(dis[ed] == 0x3f3f3f3f) puts("no route found");
    else {
        vector<string> ans;
        int now = ed;
        while(now != -1) {
            ans.push_back(fan[now]);
            now = path[now];
        }
        for(int i = ans.size() - 1; i>=0; i--) cout << ans[i] << ' ';
    }
    return 0;
}