第二届CCPC女生赛简易题解

前言：2015/5/13用虚拟OJ的方式3人一台电脑打了CCPC女生赛，一共做出9题（共10题），因为自己太坑D

题错了9发，罚时爆炸，在现场就只能排第2，上交小姐姐太强啦，很稳。

接下来就把做出来的题，写个简易题解，题目在HDU上可以找到，题号对应为6023-6032。

A：模拟水题，不说了。

B：题意：有n个节点，我们可以选择在每个节点建或不建商店。对于第i个点，其坐标是a[i].x，建设商店的成

本为a[i].c。每个节点对答案的贡献是——dis（i点的坐标, i向左方向走最近节点的坐标）。让你安排一个方

案，使得”∑所有节点对答案的贡献”尽可能小

解法：简单DP。显然要按照坐标排序。用dp[i][j]表示我们考虑到第i个点，i向左走，距离i最近的有商店的点

是j对应的前缀最小成本。那么有转移dp[i][j] = dp[i - 1][j] + dis(i, j); 特别的，如果我们在第i个点建服务器，

那么有dp[i][i] = max(dp[i - 1][j], for all j); 然后维护全局最大值即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long LL;
LL dp[3005][3005];
pair<LL, LL> p[3005];
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        for(int i = 1; i <= n; i++)
            scanf("%lld %lld", &p[i].first, &p[i].second);
        sort(p + 1, p + 1 + n);
        memset(dp, 0x3F, sizeof(dp));
        dp[1][1] = p[1].second;
        for(int i = 1; i <= n; i++)
            for(int k = 1; k <= i; k++)
            {
                dp[i + 1][i + 1] = min(dp[i + 1][i + 1], dp[i][k] + p[i + 1].second);
                dp[i + 1][k] = min(dp[i + 1][k], dp[i][k] + p[i + 1].first - p[k].first);
            }
        LL ans = __LONG_LONG_MAX__;
        for(int i = 1; i <= n; i++)
            ans = min(ans, dp[n][i]);
        printf("%lld\n", ans);
    }
    return 0;
}

C：题意：n个数，恰好去掉一个后的最大gcd

解法：维护一个前缀GCD和后缀GCD，暴力枚举去掉的数是哪个，然后前缀后缀max一下就好了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int a[maxn],l[maxn],r[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        l[1]=a[1];
        for(int i=2;i<=n;i++) l[i]=__gcd(a[i],l[i-1]);
        r[n]=a[n];
        for(int i=n-1;i>=1;i--) r[i]=__gcd(a[i],r[i+1]);
        int ans = 1;
        for(int i=1;i<=n;i++)
        {
            int temp;
            if(i==1) temp = r[i+1];
            else if(i==n) temp= l[i-1];
            else temp = __gcd(l[i-1],r[i+1]);
            ans=max(ans,temp);
        }
        printf("%d\n",ans);
    }
    return 0;
}

D：题意：让你把一个图删成一棵树，使得1到每个点的最短路保持不变

解法：我们可以直接求出1到每个点的最短路，然后看看每个点的前驱边可能是有几条（显然对于每一条合法

前驱边，以任何一条作为前缀都是等价的）所有点可能的前驱边数量，乘起来就是最后的答案了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 60;
struct EDGE
{
    int to, next, len;
    EDGE(int to = 0, int next = 0, int len = 0): to(to), next(next), len(len) {}
} edge[maxn * maxn];
int head[maxn], edgecnt;
const int mod = 1e9 + 7;
void init()
{
    memset(head, -1, sizeof(head));
    edgecnt = 0;
}
void add(int s, int t, int l)
{
    edge[edgecnt] = EDGE(t, head[s], l);
    head[s] = edgecnt++;
}
int dis[maxn], cnt[maxn];
bool f[maxn];
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        init();
        for(int i = 1; i <= n; i++)
        {
            char s[maxn];
            scanf("%s", s + 1);
            for(int j = 1; j <= n; j++)
            {
              // if(i != j)
              // {
                    if(s[j] != '0') add(i, j, s[j] - 48);
              // }

            }
        }
        memset(dis, 0x3F, sizeof(dis));
        memset(cnt, 0, sizeof(cnt));
        memset(f, 0, sizeof(f));
        cnt[1] = 1;
        dis[1] = 0;
        queue<int>q;
        q.push(1);
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            f[u] = 0;
            for(int i = head[u]; ~i; i = edge[i].next)
            {
                int v = edge[i].to;
                int d = dis[u] + edge[i].len;
                if(d <= dis[v])
                {
                    if(d == dis[v])
                    {
                        cnt[v]++;
                    }
                    else
                    {
                        dis[v] = d;
                        cnt[v] = 1;
                        if(!f[v])
                        {
                            q.push(v);
                            f[v] = 1;
                        }
                    }
                }
            }
        }
        int ans = 1;
        for(int i = 2; i <= n; i++)
        {
            if(dis[i] == 0x3F3F3F3F)
                ans = 0;
            else
                ans = (long long)ans * cnt[i] % mod;
        }
        printf("%d\n", ans);
    }
}

E：签到题，不说了。

F：神题， HDU至今只有Claris大神A掉，好像是他出的题？

G：题意：有n个点，每个点要不不连前缀边要不连所有前缀边，判断是否可以n个数配成n/2对。

解法：贪心，显然我们从后向前看，任意时刻2的数量一定要比1的数量多。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
int n;
int f()
{
    int t=0;
    for(int i=n;i>=2;i--){
        if(a[i]==1) t++;
        else{
            if(t==0) return 0;
            t--;
        }
    }
    if(t%2) return 1;
    return 0;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=2;i<=n;i++) scanf("%d",&a[i]);
        if(!f()) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

H：题意：有一串珍珠，长度为n（1e18）每个珍珠要不染色成红色，要不染色成蓝色。要求任何连续素数

长度的珍珠，都必须是红色个数>=蓝色个数让你求出有多少种对这串珍珠的染色方案。

解法：我们用f[i]表示长度为i的珍珠串的合法染色方案数。显然，如果第i颗珍珠染色为红色，f[i-1]的都依然

合法、如果第i颗珍珠染色为蓝色，要求这连续三颗必须为红红蓝，于是收获f[i-3]的贡献。而只要2、3素数

满足要求，所有素数都会满足要求（因为它们可以拆成2与3）。所以得到递推式：f[i] = f[i - 1] + f[i - 3] 矩

阵快速幂即可求解。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int mod=1e9+7;
LL n;
struct matrix
{
    int A[3][3];
    void init()
    {
        memset(A,0,sizeof(A));
    }
    void gete()
    {
        memset(A,0,sizeof(A));
        A[0][0]=A[1][1]=A[2][2]=1;
    }
};
matrix cheng(matrix a,matrix b)
{
    matrix ans;
    ans.init();
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                ans.A[i][j]=(ans.A[i][j]+1ll*a.A[i][k]*b.A[k][j]%mod)%mod;
            }
        }
    }
    return ans;
}
matrix qpow(matrix x,LL y)
{
    matrix ans;
    ans.gete();
    while(y){
        if(y%2) ans=cheng(ans,x);
        x=cheng(x,x);
        y/=2;
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%lld",&n);
        matrix A;
        A.A[0][0]=1,A.A[0][1]=0,A.A[0][2]=1;
        A.A[1][0]=1,A.A[1][1]=0,A.A[1][2]=0;
        A.A[2][0]=0,A.A[2][1]=1,A.A[2][2]=0;
        A=qpow(A,n-2);
        int ans=0;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                ans=(ans+A.A[i][j])%mod;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

I：题意：一棵树，有n（1e5）个节点。同时存在m（1e5）个询问。每个询问给你2个集合。要你求出
for(第一个集合中的点x)
{
for(第一个集合中的点y)
{
max(dep[ lca(x,y) ]);
}
}

解法：显然，如果我们考虑了x，哪个点y，会可能产生尽可能大的dep[ lca(x,y) ]呢? 一定是与x时间戳（dfs

序）最接近的节点y。因为要知道一棵子树的dfs序必然是连续的一段。所以如果y是x或者是x的子孙，都一样

会收获对于x最好的y，产生的dep[ lca(x,y) ]就等于dep[x] 而如果y不是x的子孙，则还是基于dfs序定理，最接

近的一定可以获取到最大的dep[ lca(x,y) ]

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
struct EDGE
{
    int to, next;
    EDGE(int to = 0, int next = 0): to(to), next(next) {}
} edge[maxn * 2];
int head[maxn], edgecnt;
int dfscr[maxn * 3];
int Left[maxn], Right[maxn];
int dfsclk;
void init()
{
    memset(head, -1, sizeof(head));
    edgecnt = 0;
    dfsclk = 0;
}
void add(int s, int t)
{
    edge[edgecnt] = EDGE(t, head[s]);
    head[s] = edgecnt++;
}
void dfs(int u, int fa, int dep)
{
    Left[u] = ++dfsclk;
    dfscr[dfsclk] = dep;
    for(int i = head[u]; ~i; i = edge[i].next)
    {
        int v = edge[i].to;
        if(v == fa)
            continue;
        dfs(v, u, dep + 1);
        dfscr[++dfsclk] = dep;
    }
}
int mi[maxn * 3][19];
int que(int l, int r)
{
    int k = 0;
    while((1 << k + 1) <= r - l + 1)
        k++;
    return min(mi[l][k], mi[r - (1 << k) + 1][k]);
}
int main()
{
    int n, q;
    while(~scanf("%d %d", &n, &q))
    {
        init();
        for(int i = 1; i < n; i++)
        {
            int s, t;
            scanf("%d %d", &s, &t);
            add(s, t);
            add(t, s);
        }
        dfs(1, 0, 1);
        for(int i = 1; i <= dfsclk; i++)
            mi[i][0] = dfscr[i];
        for(int i = 1; (1 << i) <= dfsclk; i++)
            for(int j = 1; j + (1 << i) - 1 <= dfsclk; j++)
                mi[j][i] = min(mi[j][i - 1], mi[j + (1 << i - 1)][i - 1]);
        while(q--)
        {
            vector<int> x, y;
            int k;
            scanf("%d", &k);
            while(k--)
            {
                int t;
                scanf("%d", &t);
                x.push_back(Left[t]);
            }
            scanf("%d", &k);
            while(k--)
            {
                int t;
                scanf("%d", &t);
                y.push_back(Left[t]);
            }
            sort(x.begin(), x.end());
            int ans = 1;
            for(auto &i : y)
            {
                auto it = upper_bound(x.begin(), x.end(), i);
                if(it != x.end())
                {
                    ans = max(ans, que(i, *it));
                }
                if(it != x.begin())
                {
                    it--;
                    ans = max(ans, que(*it, i));
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

J：给你n（30）个串，每个串的长度也不超过30。 Alice和Bob博弈，Alice先手，初始是空串。每次要在串

前或串后任意加一个小写字符，使得原始串中，至少存在一个串包含该子串。不能操作就输了。双方博弈的

关键字是（胜败，自己分数尽可能高，对手分数尽可能低）让你输出Alice的最优结局。

解法：直接按照基本SG博弈的方法，从终止态退回初始态（空串）就好啦!但是要先预处理好所有合法串，再

按长度排序得到DP的顺序。队友开始没有预处理所有转移直接写了暴力转移，T成SB。预处理好之后，按照

博弈DAG做DP就可以了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 35;
int n;
char dict[maxn][maxn];
vector<int> vec[15000];
int val[15000];
unordered_map<string, int> GetID;
int cnt = 0;
struct status
{
    int win;
    int me, you;
    status(bool win = 0, int me = 0, int you = 0): win(win), me(me), you(you) {}
    bool cmp(const status &b)
    {
        if(win == b.win)
            if(me == b.me)
                return you < b.you;
            else
                return me > b.me;
        else
            return win > b.win;
    }
} dp[15000];
int GetVal(string &s)
{
    int ret = 0;
    int mx = 0;
    for(auto &i : s)
    {
        ret += i - 'a' + 1;
        mx = max(mx, i - 'a' + 1);
    }
    ret *= mx;
    const char *c = s.c_str();
    for(int i = 1; i <= n; i++)
        if(strstr(dict[i], c))
            ret++;
    return ret;
}

status dfs(int u)
{
    if(dp[u].win != -1)
        return dp[u];
    dp[u] = status(0, 0, 0);
    for(auto &v : vec[u])
    {
        status temp = dfs(v);
        temp.win ^= 1;
        swap(temp.me, temp.you);
        temp.me += val[v];
        if(temp.cmp(dp[u]))
            dp[u] = temp;
    }
    return dp[u];
}
void BuildGraph()
{
    cnt = 0;
    GetID.clear();
    GetID[""] = cnt++;
    for(int i = 1; i <= n; i++)
        for(int st = 0; dict[i][st]; st++)
            for(int en = st; dict[i][en]; en++)
            {
                string s(dict[i] + st, dict[i] + en + 1);
                if(!GetID.count(s))
                {
                    GetID[s] = cnt++;
                    val[cnt - 1] = GetVal(s);
                }
            }
    for(int i = 0; i < cnt; i++)
    {
        dp[i].win = -1;
        vec[i].clear();
    }
    for(auto &i : GetID)
    {
        const string &en = i.first;
        if(en.size() < 1)
            continue;
        string st = string(en.begin(), en.end() - 1);
        vec[GetID[st]].push_back(i.second);
        st = string(en.begin() + 1, en.end());
        vec[GetID[st]].push_back(i.second);
    }
}
int main()
{
    while(~scanf("%d", &n))
    {
        for(int i = 1; i <= n; i++)
            scanf("%s", dict[i]);
        BuildGraph();
        status ans = dfs(0);
        if(ans.win)
            puts("Alice");
        else
            puts("Bob");
        printf("%d %d\n", ans.me, ans.you);
    }
    return 0;
}

第二届CCPC女生赛 简易题解

第二届CCPC女生赛简易题解