2017信息ACM英雄定级赛（同步赛） 题解

A:寻找爱吃饭的你。
水题，按照题意，用map映射一下，然后遍历找最大值即可。

#include <bits/stdc++.h>
using namespace std;
map <string, long long> mp;
int main(){
    //freopen("3.in", "r", stdin);
    //freopen("3.out", "w", stdout);
    int n;
    while(scanf("%d", &n) != EOF)
    {
        mp.clear();
        string a;
        long long x;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < 14; j++){
                cin >> a >> x;
                mp[a] += x;
            }
        }
        string ans;
        long long total = 0;
        for(map<string, long long> ::iterator it = mp.begin(); it != mp.end(); it++){
            if(it->second > total){
                total = it->second;
                ans = it->first;
            }
            else if(it->second == total && it->first < ans){
                ans = it->first;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

B,数学涛之神奇卡片 非常容易推出公式:m^n - (m-1)^n。然后快速幂A掉。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int mod=1e9+7;
LL qpow(LL x,LL y)
{
    LL ans=1;
    while(y){
        if(y%2) ans=ans*x%mod;
        x=x*x%mod;
        y/=2; } return ans; } int main() { //    freopen("4.in", "r", stdin);
//    freopen("4.out", "w", stdout);
    LL n,m;
    while(scanf("%lld%lld",&n,&m) != EOF){
        printf("%lld\n",(qpow(m,n)-qpow(m-1,n)+mod)%mod);
    }
    return 0;
}

C,数字拼接，贪心，直接按照a+b

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        vector<string> v;
        while(n--)
        {
            string s;
            cin >> s;
            v.push_back(s);
        }
        sort(v.begin(), v.end(), [](string & x, string & y)
        {
            return x + y < y + x;
        });
        for(auto i : v) printf("%s", i.c_str());
        printf("\n");
    }
}

D,版本号控制
排序。。。。

#include<bits/stdc++.h>
using namespace std;
char s[(int)1e7];
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        set<vector<int> >st;
        while(n--)
        {
            scanf("%s",s);
            vector<int> v;
            istringstream ss(s);
            int x;
            while(ss >> x)
            {
                char c;
                ss >> c;
                v.push_back(x);
            }
            st.insert(v);
        }
        for(auto &i : st)
        {
            for(int j = 0; j < i.size(); j++)
            {
                printf("%d", i[j]);
                if(j == i.size() - 1) printf("\n");
                else printf(".");
            }
        }
    }
    return 0;
}

E,判断回文串。。。卡了内存，不能开数组，还卡了普通单Hash,要双Hash。。。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long uLL;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
void Update1(pair<uLL, uLL> &p, int x, pair<uLL, uLL> &val)
{
    p.first += x * val.first;
    p.first %= MOD1;
    p.second += x * val.second;
    p.second %= MOD2;
    val.first *= 131;
    val.first %= MOD1;
    val.second *= 131;
    val.second %= MOD2;
}
void Update2(pair<uLL, uLL> &p, int x)
{
    p.first *= 131;
    p.first += x;
    p.first %= MOD1;
    p.second *= 131;
    p.second += x;
    p.second %= MOD2;
}
int main()
{
    //freopen("2.in","r",stdin);
   //freopen("2.out","w",stdout);
    int n;
    while(~scanf("%d", &n))
    {
        char buf[100];
        gets(buf);
        int m = n / 2;
        if(n & 1)
        {
            pair<uLL, uLL> h1 = make_pair(0, 0), val = make_pair(1LL, 1LL), h2;
            for(int i = 1; i <= m; i++)
            {
                int c = getchar();
                Update1(h1, c, val);
            }
            n = getchar();
            Update1(h1, n, val);
            h2 = make_pair(n,n);
            for(int i = 1; i <= m; i++)
            {
                int c = getchar();
                Update2(h2, c);
            }
            if(h1 == h2) puts("YES");
            else puts("NO");
        }
        else
        {
            pair<uLL, uLL> h1 = make_pair(0, 0), val = make_pair(1LL, 1LL), h2 = make_pair(0, 0);
            for(int i = 1; i <= m; i++)
            {
                int c = getchar();
                Update1(h1, c, val);
            }
            for(int i = 1; i <= m; i++)
            {
                int c = getchar();
                Update2(h2, c);
            }
            if(h1 == h2) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}

F, ZXY的神奇扑克牌，良心题，读懂题意后发现就是一个裸带权LCS。所以O(n*n)的DP就可以了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int add(char a, char b){
    if(a == 'R' && b == 'R') return 50;
    if(a == 'R'){
        if(b == 'A') return 20;
        if(b == 'K') return 15;
        if(b == 'Q') return 15;
        if(b == 'J') return 15;
        if(b == 'T') return 10;
        return b - '0';
    }
    if(b == 'R'){
        if(a == 'A') return 20;
        if(a == 'K') return 15;
        if(a == 'Q') return 15;
        if(a == 'J') return 15;
        if(a == 'T') return 10;
        return a - '0';
    }
    if(a == 'A') return 20;
    if(a == 'K') return 15;
    if(a == 'Q') return 15;
    if(a == 'J') return 15;
    if(a == 'T') return 10;
    return a - '0';
}
char a[maxn][3], b[maxn][3];
int n, dp[maxn][maxn];
int main(){
    while(scanf("%d", &n) != EOF)
    {
        if(n == 0) break;
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++) scanf("%s", a[i]);
        for(int i = 1; i <= n; i++) scanf("%s", b[i]);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                if(a[i][0] == b[j][0] || a[i][0] == 'R' || b[j][0] == 'R'){
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + add(a[i][0], b[j][0]));
                }
            }
        }
        printf("%d\n", dp[n][n]*2);
    }
    return 0;
}

G, ZXY的不重叠区间问题 ，先按右端点排序，右端点相同的情况下按照左端点排序，然后对于没条线段的右端点，设dp[i]代表<=i点的最大权值和，我们去找<=这条线段的左端点的dp的最大值加上当前线段的权值更新当前的右端点的dp值，但是端点的数据太大，所以我们先要把端点离散化，之后就可以了吗？我们发现直接暴力是O(n*m)的，显然过不了。注意到我们去找<=这条线段的左端点的dp的最大值 这句话，我们可以随便用一种数据结构来维护这个东西，这题就做完了。当然不离散化，直接用unorder_map和动态开点线段树也是可以过的。

代码1：普通离散化

//

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5;
long long mp[maxn];
vector <int> v;
int getid(int x){
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
struct node{
    int l, r, v;
    node(){}
    node(int l, int r, int v) : l(l), r(r), v(v) {}
    bool operator <(const node &rhs) const{
        if(r == rhs.r) return l < rhs.l;
        return r < rhs.r;
    }
}a[maxn];
namespace bit{
    int mx;
    inline int lowbit(int x){return x&-x;}
    inline void update(int pos, long long x){for(int i = pos; i <= mx; i+=lowbit(i)) mp[i] = max(mp[i], x);}
    inline long long query(int x){long long res = 0; for(int i = x; i; i-=lowbit(i)) res = max(res, mp[i]); return res;}
} using namespace bit;
int n;
int main(){
    while(scanf("%d", &n) != EOF)
    {
        mx = 0;
        v.clear();
        memset(mp, 0, sizeof(mp));
        for(int i = 1; i <= n; i++){
            scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].v);
            //mx = max(mx, a[i].r);
            v.push_back(a[i].l);
            v.push_back(a[i].r);
        }
        sort(a + 1, a + n + 1);
        sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end());
        mx = (int)v.size();
        for(int i = 1; i <= n; i++){
            long long dp = query(getid(a[i].l));
            update(getid(a[i].r), dp + a[i].v);
        }
        printf("%lld\n", query(mx));
    }
    return 0;
}

代码2 : unorder_map

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5;
unordered_map<int, LL> c;
struct Line
{
    int l, r, v;
} line[maxn];
int maxm;
int lowbit(int x)
{
    return x & -x;
}
void Modify(int pos, LL x)
{
    for (int i = pos; i <= maxm; i += lowbit(i))
        c[i] = max(c[i], x);
}
LL GetMax(int pos)
{
    LL ret = 0;
    for (int i = pos; i > 0; i -= lowbit(i))
        ret = max(ret, c[i]);
    return ret;
}
struct FastIO
{
    static const int S = 1310720;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar()
    {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) exit(0);
        return buf[pos ++];
    }
    inline int xuint()
    {
        int c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x;
    }
    inline void wchar(int x)
    {
        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos ++] = x;
    }
    inline void wint(LL x)
    {
        if (x < 0) wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n ++] = '0' + x % 10, x /= 10;
        while (n--) wchar(s[n]);
    }
    inline void wstring(const char *s)
    {
        while (*s) wchar(*s++);
    }
    ~FastIO()
    {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;
int main()
{
    int n;
    while (true)
    {
        n = io.xuint();
        maxm = 0;
        c.clear();
        for (int i = 1; i <= n; i++)
        {
            line[i].l = io.xuint();
            line[i].r = io.xuint();
            line[i].v = io.xuint();
            maxm = max(maxm, line[i].r);
        }
        sort(line + 1, line + 1 + n, [](Line & x, Line & y)
        {
            if (x.r == y.r)
                return x.l < y.l;
            else return x.r < y.r;
        });
        for (int i = 1; i <= n; i++)
        {
            LL dp = GetMax(line[i].l);
            Modify(line[i].r, dp + line[i].v);
        }
        io.wint(GetMax(maxm));
        io.wchar('\n');
    }
    return 0;
}

代码3：动态开点线段树

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long LL;
struct Line
{
    int l, r, v;
} line[maxn];
const int maxm = 4e6;
int lson[maxm], rson[maxm];
LL mx[maxm];
int clk;
void init()
{
    lson[0] = rson[0] = mx[0] = 0;
    clk = 0;
}
int newnode()
{
    clk++;
    lson[clk] = rson[clk] = mx[clk] = 0;
    return clk;
}
void Modify(int &id, int L, int R, int pos, LL val)
{
    if(id == 0) id = newnode();
    if(L == R) mx[id] = max(mx[id], val);
    else
    {
        int mid = L + R >> 1;
        if(pos <= mid) Modify(lson[id], L, mid, pos, val);
        else Modify(rson[id], mid + 1, R, pos, val);
        mx[id] = max(mx[lson[id]], mx[rson[id]]);
    }
}
LL GetMax(int id, int L, int R, int l, int r)
{
    if(id == 0) return 0;
    if(l <= L && R <= r) return mx[id];
    else
    {
        LL ret = 0;
        int mid = L + R >> 1;
        if(l <= mid) ret = max(ret, GetMax(lson[id], L, mid, l, r));
        if(mid < r) ret = max(ret, GetMax(rson[id], mid + 1, R, l, r));
        return ret;
    }
}
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int st = INT_MAX, en = -INT_MAX;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d %d %d", &line[i].l, &line[i].r, &line[i].v);
            st = min(st, line[i].l);
            en = max(en, line[i].r);
        }
        sort(line + 1, line + 1 + n, [](Line & x, Line & y)
        {
            if(x.r == y.r)
                return x.l < y.l;
            else return x.r < y.r;
        });
        init();
        int rt = 0;
        for(int i = 1; i <= n; i++)
        {
            LL dp = GetMax(rt, st, en, st, line[i].l);
            Modify(rt, st, en, line[i].r, dp + line[i].v);
        }
        printf("%lld\n", mx[rt]);
    }
    return 0;
}

H: FM的孤独旅程
DP。dp[i][j]代表在i点当前经过了j个点的最小花费。我写标算的时候写了DFS，但是被hack机出了几组数据卡成了狗。
先上一下我的DFS代码

//这题会TLE。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005;
int dp[maxn][maxn], pre[maxn][maxn];//dp[i][j]代表在i点当前经过了j个点的最小花费
int n, m, T;
vector <int> E[maxn];
vector <int> val[maxn];
vector <int> ans;
void dfs(int x, int num, int cost, int fa)
{
    if(dp[x][num] <= cost) return;
    dp[x][num] = cost;
    pre[x][num] = fa;
    for(int i = 0; i < (int)E[x].size(); i++)
    {
        if(cost + val[x][i] <= T)
        {
            dfs(E[x][i], num+1, cost+val[x][i], x);
        }
    }
}
void print_path(int x, int y)
{
    ans.push_back(x);
    if(pre[x][y] == -1)
    {
        cout << ans.size() << endl;
        for(int i = (int)(ans.size() - 1); i >= 0; i--) cout << ans[i] << " ";
        cout << endl;
        return ;
    }
    else
    {
        print_path(pre[x][y], y-1);
    }
}
int main()
{
    //freopen("5.in","r",stdin);
   // freopen("5.out","w",stdout);
    while(scanf("%d%d%d", &n, &m, &T) != EOF)
    {
        memset(pre, -1, sizeof(pre));
        for(int i = 0; i < maxn; i++)
        {
            for(int j = 0; j < maxn; j++)
            {
                dp[i][j] = 1e9+7;
            }
        }
        ans.clear();
        for(int i = 0; i < maxn; i++) E[i].clear(), val[i].clear();
        for(int i = 1; i <= m; i++)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            E[a].push_back(b);
            val[a].push_back(c);
        }
        dfs(1, 1, 0, -1);
        for(int i = n; i >= 2; i--)
        {
            if(dp[n][i] <= T)
            {
                printf("%d\n", dp[n][i]);
                print_path(n, i);
                break;
            }
        }
    }
    return 0;
}

当把DFS改成SPFA后，发现世界突然变快了100倍

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 5;
struct EDGE
{
    int to, next, len;
    EDGE(int to = 0, int next = 0, int len = 0): to(to), next(next), len(len) {}
} edge[maxn];
int head[maxn], edgecnt;
int dis[maxn][maxn];
int pre[maxn][maxn];
bool vis[maxn][maxn];
void init()
{
    memset(head, -1, sizeof(head));
    edgecnt = 0;
    memset(dis, 0x7F, sizeof(dis));
    memset(vis, 0, sizeof(vis));
}
void add(int s, int t, int l)
{
    edge[edgecnt] = EDGE(t, head[s], l);
    head[s] = edgecnt++;
}
int main()
{
    int n, m, t;
    while(~scanf("%d %d %d", &n, &m, &t))
    {
        init();
        while(m--)
        {
            int u, v, l;
            scanf("%d %d %d", &u, &v, &l);
            add(u, v, l);
        }
        dis[1][1] = 0;
        queue<pair<int, int> >q;
        q.push(make_pair(1, 1));
        while(!q.empty())
        {
            int u = q.front().first;
            int p = q.front().second;
            q.pop();
            vis[u][p] = 0;
            for(int i = head[u]; ~i; i = edge[i].next)
            {
                int v = edge[i].to;
                int tt = dis[u][p] + edge[i].len;
                if(dis[v][p + 1] > tt)
                {
                    dis[v][p + 1] = tt;
                    pre[v][p + 1] = u;
                    if(!vis[v][p + 1])
                    {
                        vis[v][p + 1] = 1;
                        q.push(make_pair(v, p + 1));
                    }
                }
            }
        }
        int ans;
        for(int i = n; i >= 1; i--)
            if(dis[n][i] <= t)
            {
                ans = i;
                break;
            }
        printf("%d\n%d\n", dis[n][ans], ans);
        stack<int>s;
        while(n != 1)
        {
            s.push(n);
            n = pre[n][ans];
            ans--;
        }
        s.push(1);
        while(!s.empty())
        {
            printf("%d ", s.top());
            s.pop();
        }
    }
    return 0;
}

I，不会做QAQ，题解找上决。。。。