[ICPC2016Dalian Onsite]官方题解

[PDF版](http://pan.baidu.com/s/1bpkkoTD)
> 添加 `-D__STDC_FORMAT_MACROS`以支持`PRId64`

#Problem A Wrestling Match
##提交情况：170/434
##解题思路
本题做法比较随意，此处说两种：
1. 读入数据，建好图以后，以每一个点为开始遍历的起始节点，搜索整个图，在搜索的过程中判断是否出现冲突
2. 用并查集维护题目中所谓『好选手』以及『坏选手』的关系，在建立并查集的过程中，就可判断冲突

总的来说，第2种做法需要处理的特殊情况较少，并且计算量照第1种做法少，所以标程采用第2种做法。

##标准程序
```c++
#include <iostream>
#include <assert.h>
#define Max_N 1005
#define Max_M 10005
using namespace std;

int8_t gb_no[Max_N];
int32_t uset[Max_N];
int32_t urel[Max_N];
int8_t rmap[Max_N];

int32_t pair_rel[Max_M][2];

void init(int32_t n) {
    memset(gb_no, -1, sizeof(gb_no));
    memset(urel, 0, sizeof(urel));
    memset(rmap, 0, sizeof(rmap));
    for (int32_t i = 1; i <= n; i++) {
        uset[i] = i;
    }
    return ;
}

int32_t father(int32_t ind, int32_t &rel) {
    if (uset[ind] == ind) {
        rel = 0;
        return ind;
    }
    int relt, fa;
    fa = father(uset[ind], relt);
    urel[ind] = relt ^ urel[ind];
    uset[ind] = fa;
    rel = urel[ind];
    return fa;
}

bool insert(int32_t a, int32_t b) {
    int32_t fa, fb, rela, relb, rel;
    fa = father(a, rela);
    fb = father(b, relb);
    rel = rela ^ relb ^ 1;
    if (fa == fb && rel != 0) return false;
    if (fa != fb) {
        uset[fa] = fb;
        urel[fa] = rel;
    }
    return true;
}

bool set_father_no(int32_t a) {
    int32_t fa, rela;
    fa = father(a, rela);
    if (gb_no[fa] >= 0 && gb_no[a] >= 0) {
        return (gb_no[fa] ^ gb_no[a]) == rela;
    } else if (gb_no[fa] == -1) {
        gb_no[fa] = gb_no[a] ^ rela;
    }
    return true;
}

int main() {
    int32_t n, m, x, y, ai, bi, t = 0;
    bool flag;
    while (scanf("%d%d%d%d", &n, &m, &x, &y) != EOF) {
        init(n); flag = true;
        assert(n > 1 && n <= 1000);
        assert(m >= 1 && m <= 10000);
        assert(x + y <= n);
        for (int32_t i = 0; i < m; i++) {
            scanf("%d%d", &ai, &bi);
            assert(ai >= 1 && ai <= n);
            assert(bi >= 1 && bi <= n);
            assert(ai != bi);
            rmap[ai] = rmap[bi] = 1;
            flag = flag && insert(ai, bi);
        }
        for (int32_t i = 0; i < x; i++) {
            scanf("%d", &ai);
            assert(ai >= 1 && ai <= n);
            if (gb_no[ai] != -1 && gb_no[ai] != 1) flag = false;
            gb_no[ai] = 1;
            flag = flag && set_father_no(ai);
        }
        for (int32_t i = 0; i < y; i++) {
            scanf("%d", &ai);
            assert(ai >= 1 && ai <= n);
            if (gb_no[ai] != -1 && gb_no[ai] != 0) flag = false;
            gb_no[ai] = 0;
            flag = flag && set_father_no(ai);
        }
        for (int32_t i = 1; i <= n; i++) {
            flag = flag && (rmap[i] != 0 || gb_no[i] != -1);
        }
        printf("%s\n", flag ? "YES" : "NO");
    }
    return 0;
}
```

#Problem B Regular Number
##提交状况：20/104
##解题思路
经典的shift-and算法可以搞定问题，会了shift-and算法以后，就需要注意以下事项了：
1. 正则表达式的长度有1000，所以可以用一个Int64_t数字代表64位状态。
2. 做好映射表示，以免进行不必要的判断和计算，映射表示主要用来回答这个问题，正则表达式的第i个状态用状态数组的第几个数字的第几位表示。
具体的请看程序。
##标准程序

```c++
#include <iostream>
#include <stdint.h>
#include <inttypes.h>
#define MAX_N 1005
#define MAX_LEN 10000005
#define MAX_ARR_LEN ((MAX_N >> 6) + 5)
#define MASK 63
using namespace std;
#define MYPRID PRId64
typedef uint64_t myint;

myint num[10][MAX_ARR_LEN];
myint ret_n[MAX_ARR_LEN];
myint ind_x_arr[MAX_N];
myint ind_y_arr[MAX_N];
char str[MAX_LEN];

void init(myint n) {
    memset(num, 0, sizeof(num));
    memset(ret_n, 0, sizeof(ret_n));
    for (myint i = 0; i < n; i++) {
        ind_x_arr[i] = (i >> 6) + 1;
        ind_y_arr[i] = ((myint)1 << (i & MASK));
    }
}

inline void set_one(myint *arr, myint n) {
    arr[ind_x_arr[n]] |= ind_y_arr[n];
}

inline bool seek_one(myint *arr, myint n) {
    return arr[ind_x_arr[n]] & ind_y_arr[n];
}

inline void left_move_one(myint *arr, myint n) {
    for (myint i = n; i >= 1; i--) {
        arr[i] <<= 1;
        arr[i] |= (!!(arr[i - 1] & 0x8000000000000000LL));
    }
    set_one(arr, 0);
}

inline void and_opt(myint *arr1, myint *arr2, myint n) {
    for (myint i = 1; i<= n; i++) {
        arr1[i] &= arr2[i];
    }
}
int main() {
    myint n, ai, bi, len, l;
    char ch;
    scanf("%"MYPRID, &n);
    init(n);
    for (myint i = 0; i < n; i++) {
        scanf("%"MYPRID, &ai);
        for (myint j = 0; j < ai; j++) {
            scanf("%"MYPRID, &bi);
            set_one(num[bi], i);
        }
    }
    scanf("%s", str);
    len = strlen(str);
    l = (n >> 6) + (!!(n & MASK));
    for (myint i = 0; i < len; i++) {
        left_move_one(ret_n, l);
        and_opt(ret_n, num[str[i] - '0'], l);
        if (seek_one(ret_n, n - 1)) {
            ch = str[i + 1];
            str[i + 1] = '\0';
            printf("%s\n", str + i - n + 1);
            str[i + 1] = ch;
        }
    }
    return 0;
}
```

#Problem C Game of Taking Stones
##提交情况：13/93
##解题思路
题目是一个威佐夫博弈问题，可是数据范围太大原式在计算机种不是很容易解决问题，观察原威佐夫博弈的求解判别公式：
```math
A_{k}=\lfloor k\times \frac{1+\sqrt{5}}{2}\rfloor
```
```math
B_{k}=A_{k}+k
```
两堆石子数两满足上式，即是一个『先手必败态』。观察公式中$$A_{k}$$部分的表示，与菲波那切数列通项公式有些关系。而菲波那切数列第n项求解问题，使用『+/-』就可以搞定问题，所以标程的解决思路，是试图将上述公式转换成某种菲波那切数列问题的等价变换，这里只做提示，大家有兴趣可以自己进行详细推导，或找裁判讨论。
##标准程序

```c++
#include <iostream>
#include <time.h>
using namespace std;
class BigInt {
    private :
        int flag, len, val[5000];
    public :
        BigInt();
        BigInt(const int &n);
        BigInt operator + (const int &n) const;
        BigInt operator - (const int &n) const;
        BigInt& operator = (const int &n);
        BigInt& operator = (const char* n);
        BigInt operator + (const BigInt &b) const;
        BigInt operator - (const BigInt &b) const;
        
        bool operator < (const BigInt &b) const;
        bool operator < (const int &n) const;
        bool operator == (const BigInt &b) const;
        bool operator == (const int &n) const;
        bool operator <= (const BigInt &b) const;
        bool operator <= (const int &n) const;
        bool operator > (const BigInt &b) const;
        bool operator > (const int &n) const;
        bool operator != (const BigInt &b) const;
        bool operator != (const int &n) const;
        void Print();
        void Println();
        int getLen();
};
int BigInt::getLen() {
    return this->len;
}

void BigInt::Print() {
    flag?printf(""):printf("-");
    for (int i=this->len-1;i>=0;i--)
        printf("%d",this->val[i]);
}

void BigInt::Println() {
    this->Print();
    printf("\n");
}

BigInt::BigInt() {
    len=0;
    flag=true;
    val[len]=0;
    len++;
}

BigInt::BigInt(const int &n) {
    int temp(n);
    len=0;
    flag=(n>=0);
    temp=temp>=0?temp:-temp;
    while (temp!=0)
    {
        val[len]=temp%10;
        temp/=10;
        len++;
    }
}

BigInt BigInt::operator + (const BigInt &b) const {
    BigInt temp;
    BigInt temp1,temp2;
    temp1=*this;
    temp2=b;
    temp1.flag=temp2.flag=true;
    if (this->flag&&!b.flag) {
        temp=temp1-temp2;
        return temp;
    }

if (!this->flag&&b.flag) {
        temp=temp2-temp1;
        return temp;
    }
    temp.len=b.len>this->len?b.len:this->len;
    for (int i=0;i<temp.len;i++) {
        if (i<b.len)
            temp.val[i]=b.val[i];
        else
            temp.val[i]=0;
        if (i<this->len)
            temp.val[i]+=this->val[i];
    }
    for (int i=0;i<temp.len;i++)
        if (temp.val[i]>=10) {
            if (i==temp.len-1) {
                temp.val[i+1]=1;
                temp.val[i]-=10;
                temp.len++;
            }
            else {
                temp.val[i+1]++;
                temp.val[i]-=10;
            }
    }
    temp.flag=this->flag;
    return temp;
}
BigInt BigInt::operator + (const int &n) const {
    BigInt temp(n);
    return (temp+*this);
}
BigInt BigInt::operator - (const BigInt &b) const {
    BigInt temp;
    BigInt temp1,temp2;
    temp1=*this;
    temp2=b;
    temp1.flag=temp2.flag=true;
    if (this->flag&&!b.flag) {
        temp=temp1+temp2;
        return temp;
    }
    if (!this->flag&&b.flag) {
        temp=temp1+temp2;
        temp.flag=false;
        return temp;
    }
    if (!this->flag&&!b.flag) {
        temp1.flag=false;
        temp=temp1+temp2;
        return temp;
    }
    if (*this==b) {
        temp=0;
        return temp;
    }
    if (*this<b) {
        temp=(b-(*this));
        temp.flag=false;
        return temp;
    }
    temp=*this;
    for (int i=0;i<b.len;i++)
        temp.val[i]=temp.val[i]-b.val[i];
    for (int i=0;i<temp.len;i++) {
        if (temp.val[i]<0) {
            temp.val[i]+=10;
            temp.val[i+1]-=1;
        }
        else if (i>=b.len) break;
    }
    while (temp.val[temp.len-1]==0&&temp.len>1)
        temp.len--;
    temp.flag=true;
    return temp;
}

BigInt BigInt::operator - (const int &n) const {
    BigInt temp;
    temp=n;
    return (*this-temp);
}
bool BigInt::operator < (const BigInt &b) const {
    if (this->flag&&!b.flag) return false;
    if (!this->flag&&b.flag) return true;
    if (this->len<b.len) return true;
    if (this->len>b.len) return false;
    for (int i=this->len-1;i>=0;i--) {
        if (this->val[i]!=b.val[i]) {
            if (this->val[i]<b.val[i]) return this->flag;
            else return !this->flag;
        }
    }
    return false;
}

bool BigInt::operator < (const int &n) const {
    BigInt temp;
    temp=n;
    return (*this<temp);
}

bool BigInt::operator == (const BigInt &b) const {
    if (*this<b) return false;
    if (b<*this) return false;
    return true;
}

bool BigInt::operator == (const int &n) const {
    BigInt temp;
    temp=n;
    return (*this==temp);
}

bool BigInt::operator <= (const BigInt &b) const {
    if ((*this<b)||(*this==b)) return true;
    return false;
}

bool BigInt::operator <= (const int &n) const {
    BigInt temp;
    temp=n;
    return (*this<=temp);
}

bool BigInt::operator > (const BigInt &b) const {
    return (b<*this);
}

bool BigInt::operator > (const int &n) const {
    BigInt temp;
    temp=n;
    return (temp<*this);
}

BigInt& BigInt::operator = (const int &n) {
    int temp;
    temp=n;
    len=0;
    flag=(n>=0);
    temp=temp>=0?temp:-temp;
    while (temp!=0)
    {
        val[len]=temp%10;
        temp/=10;
        len++;
    }
    if (len==0){val[0]=0;len=1;}
    return *this;
}

BigInt& BigInt::operator = (const char* n) {
    int j=0;
    int len=strlen(n);
    for (int i=len-1;i>=0;i--)
    {
        this->val[j]=(n[i]-'0')%10;
        j++;
    }
    this->len=j;
    return *this;
}

bool BigInt::operator != (const BigInt &b) const {
    if (*this<b||b<*this) return true;
    return false;
}

bool BigInt::operator != (const int &n) const {
    BigInt temp;
    temp=n;
    if (*this!=temp) return true;
    return false;
}

BigInt a[500];
BigInt b[500];
int main()
{
    BigInt n,m;
    a[0]=a[2]=2;
    a[1]=a[3]=3;
    b[0]=b[1]=b[2]=b[3]=1;
    for (int i=4;i<=485;i++)
        a[i]=a[i-1]+a[i-2];
    for (int i=4;i<=485;i++)
        b[i]=b[i-1]+b[i-2];
    char s[100],w[100];
    BigInt temp, we, ha;
    while (scanf("%s%s",s,w)!=EOF)
    {
        n=s; m=w;
        if (n>m) {
            temp=m;
            m=n;
            n=temp;
        }
        we=0; ha=m;
        int j = -1;
        while (a[j+1] <= ha) {
            ++j;
            ha = ha - a[j];
            we = we + b[j];
        }
        while (j >= 3 && ha != 0) {
            if (a[j] <= ha) {
                ha = ha - a[j];
                we = we + b[j];
            }
            --j;
        }
        if (ha == 0 && n == (m - we))
            printf("0\n");
        else
            printf("1\n");
    }
    return 0;
}
```

#Problem D A Simple Math Problem
##提交情况：182/528
##解题思路
题目中给出$$x,y$$两数的和以及两个数的最小公倍数：
```math
X+Y=a
```
```math
LeastCommonMultiple(X,Y)=b
```
设$$X,Y$$的最大公约数为$$c$$，则可得如下式子：
```katex
\begin{array}{}
(1):\space X=z_{1}\times c \\
(2):\space Y=z_{2}\times c \\
(3):\space X+Y=(Z_{1}+Z_{2})\times c \\
(4):\space LeastCommonMultiple(X,Y)=z_{1}\times z_{2}\times c
\end{array}
```

-
因为$$\gcd(z_{1},z_{2})=1$$，所以$$\gcd((1),(2))=c$$，所以可得如下式子：
```katex
\begin{array}{}
z_{1}+z_{2}=\frac{(1)}{c} \\
z_{1}\times z_{2}=\frac{(2)}{c} \\
(z_{1}-z_{2})^{2}=(z_{1}+z_{2})^{2}-4\times z_{1}\times z_{2}
\end{array}
```
-
从而可得$$z_{1}-z_{2}$$的值，得解。

##标准程序
```c++
#include <iostream>
#include <assert.h>
#include <math.h>
#define NS_STR "No Solution"
using namespace std;
int32_t gcd(int32_t a, int32_t b) {
    if (!b) return a;
    return gcd(b, a % b);
}

int main() {
    int32_t a, b, c, d, e, f, g, x, y;
    while (scanf("%d%d", &a, &b) != EOF) {
        assert(a <= 2 * 10000 && a >= 1);
        assert(b <= 1000000000 && b >= 1);
        c = gcd(a, b);
        d = a / c;
        e = b / c;
        f = d * d - 4 * e;
        if (f < 0) {
            printf("%s\n", NS_STR);
            continue;
        }
        g = (int32_t)sqrt(f);
        if (g * g != f) {
            printf("%s\n", NS_STR);
            continue;
        }
        g = -g;
        x = (g + d) / 2 * c;
        y = a - x;
        assert(x > 0 && y > 0);
        printf("%d %d\n", x, y);
    }
    return 0;
}
```

#Problem E Aninteresting game
##提交情况：29/134
##解题思路
本题是一道计数问题。
1.第一个操作可以用前缀和的差来求解。添加完前$$x$$个数字，消耗$$\sum_{i=1}^{x}lowbit(i)$$点体力。通过枚举lowbit可以降低求和复杂度至$$logx$$
2.第二个操作求$$x$$被加入新集合的次数。我们先考虑添加$$k$$时，$$[k-lowbit(k)+1, k-1]$$和$$k$$会被加入新集合。除去$$k$$，剩余的是$$k$$的最低非零位变成了0，更低的位**不全为0**的所有数字。反过来，先找到$$x$$的最低非零位，将某个比该位高的位置由0变成1得到$$k$$。添加$$k$$时，$$x$$会被加入新集合。这样的$$k$$的个数是：$$x$$二进制表示中比$$x$$最低非零位高的0的个数。再加上$$x$$本身就得到结果。
##标准程序
```c++
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <stdint.h>
#include <inttypes.h>
#include <algorithm>
using namespace std;
typedef int64_t ll;

ll n, l, r, q, a;

ll Cal(ll x) {
    ll ans = 0;
    for(int k = 0; (1ll<<k) <= x; k++) {
    ans += ((x>>(k+1)) + !!((1ll<<k) & x)) * (1ll<<k);
    }
    return ans;
}

int main() {
    while(scanf("%" PRId64 "%" PRId64, &n, &q) != EOF) {
        while(q --) {
            scanf("%" PRId64, &a);
            if(a == 1) {
                scanf("%" PRId64 "%" PRId64, &l, &r);
                printf("%" PRId64 "\n", Cal(r) - Cal(l-1));
            }
            else {
                scanf("%" PRId64, &l);
                ll ans = 1ll;
                l += l & (-l);
                while (l <= n) {
                    ++ans;
                    l += l & (-l);
                }
                printf("%" PRId64"\n", ans);
            }
        }
    }
    return 0;
}
```

#Problem F Detachment
##提交情况：150/428
##解题思路
题意相当于给定一个自然数$$x$$，让你给出一种拆分方式$$x=a_{1}+a_{2}\ldots (a_{i}\neq a_{j})$$，使得每个小部分的乘积$$s=a_{1}\times a_{2}\times \ldots $$最大
对于使得$$s(s>4)$$最大的递增序列$$a_{1},a_{2}\ldots $$，有以下性质：
1）$$a{i+1}\leq 2$$
2）最多有一个$$i$$，满足$$a_{i+1}-a_{i}=2$$
3）$$1< a_{1}\leq 3$$
反证法证明上述结论，简证如下：
证明性质1。假设存在$$i$$，满足$$a_{i+1}-a_{i}> 2$$，用$$a_{i+1}-1$$和$$a_{i}+1$$会得到更大的乘积，矛盾。
性质2。假设存在$$i< j$$，满足$$a_{i+1}-a_{i}=2$$，$$a_{j+1}-a_{j}> 2$$，用$$a_{j+1}-1$$和$$a_{i}+1$$代替$$a_{j+1}$$和$$a_{i}$$，会得到更大的乘积，矛盾。
性质3。如果$$a_{1}=1$$，那么它加到$$a_{i}(i>1)$$上去会得到更大的乘积。矛盾！如果$$a_{1}=4$$，分两种情况考虑。
1）$$a_{2}=5=2+3,2\times 3\times 4>4\times 5$$，得到一个$$a_{1}=2$$的更优解。矛盾！2）$$a_{2}=6,4+6=2+3+5,2\times 3\times 5>4\times 6$$，得到一个$$a_{1}=2$$的更优解。矛盾！
综上，解的结构是以下两种中的一种。
```katex
\begin{array}{}
s=2\times 3\times \ldots \times (r-1)\times (r+1)\times \ldots \times n \\
s=3\times \ldots \times (r-1)\times (r+1)\times \ldots \times n
\end{array}
```
对于每一类最优解都是唯一确定$$r$$和$$n$$，所以找出一组猫足条件的$$r$$和$$n$$即可构造出最优解。
观察可知，与阶乘类似，所以可以用阶乘逼近答案。
首先，对于$$x$$，找出唯一确定的$$n$$和$$r^{\prime}$$，满足$$x=1+2+3+\ldots +n-r^{\prime}(0\leq r^{\prime}< n)$$。对$$r^{\prime}$$分类讨论。
```katex
\begin{array}{l}
1)r^{\prime}=0:x=2+3+\ldots +(n-1)+(n+1) \\
2)r^{\prime}=1:x=2+3+\ldots +n \\
3)r^{\prime}=2:x=3+4+\ldots +(n-1)+(n+1) \\
4)r^{\prime}\geq 3:x=2+3+\ldots +(r^{\prime}-2)+r^{\prime}+\ldots +n

\end{array}
```
-
$$x\leq 10^9 \Rightarrow n< 10^5$$。预处理阶乘后，每次求出符合条件的$$n$$和$$r^{\prime}$$，对每种情况分类构造即可。
##标准程序
```c++
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <math.h>
#include <assert.h>

typedef int64_t ll;
const ll MAX_T = 1000000;
const ll MOD = 1e9 + 7;

ll seri_times[MAX_T];

void init() {
    ll temp = 1;
    seri_times[0] = 1;
    for (ll i = 1; i < MAX_T; i++) {
        temp = (temp * i) % MOD;
        seri_times[i] = temp;
    }
    return ;
}

/*
p - x * v = r
x * v + r = 0 (mod p)
x * r1 + v1 = 0 (mod p)
v1 = -x * r1 (mod p)
*/

ll rev_num(ll k) {
    assert(k);
    if (k == 1) return 1;
    return ((-(MOD / k) * rev_num(MOD % k)) % MOD + MOD) % MOD;
}

int main() {
    ll tcase, n, x, r, ret;
    init();
    scanf("%" PRId64, &tcase);
    while (tcase--) {
        scanf("%" PRId64, &n);
        if (__builtin_expect(!!(n == 1), 0)) {
            printf("1\n");
            continue;
        }
        x = ((ll)sqrt(2 * n));
        while (x * (x + 1) >> 1 < n) ++x;
        r = (x * (x + 1) >> 1) - n;
        assert(r >= 0);
        switch (r) {
            case 0 :
                ret = seri_times[x + 1] * rev_num(x);
                break;
            case 1 :
                ret = seri_times[x];
                break;
            case 2 :
                ret = seri_times[x + 1] * rev_num(2 * x);
                break;
            default :
                ret = seri_times[x] * rev_num(r - 1);
                break;
        }
        ret %= MOD;
        printf("%" PRId64 "\n", ret);
    }
    return 0;
}
```

#Problem G Garden of Eden
##提交情况：72/221
##解题思路
树分治+枚举子集/DP
点的编号很小，所以可以用$$(1<< i)$$表示编号$$i$$的结点，问题转化为求权值**或和**为$$K=(1<< k)=1$$的有向路径条数。用树的点分治简化问题。问题转化为：给定一个集合，求该集合中**或和**为$$K$$的元素对，给出两种做法。
1）统计集合中元素值为$$x$$的个数$$num[x]$$，$$ans=\sum_{1\leq x\leq K}num[x]\times \sum_{y\space is\space subset \space of \space x}num[(x\oplus K)|y]$$
2)进行dp。$$dp[i][st]$$表示低$$i$$位是$$st$$低$$i$$位的倍集（x是st的倍集：x&st=st），高位和st相同的元素个数。
(1<<(i-1))&st==0:$$dp[i][st]=dp[i-1][st]+dp[i-1][st\oplus ((1<<(i-1))]$$
(1<<(i-1))&st==1:$$dp[i][st]=dp[i-1][st]$$
```katex
ans=\sum_{0\leq x\leq K}num[x]\times dp[k][x\oplus K]
```
第一种时间复杂度$$O(nlogn+n\times 3^{k})$$，第二种$$O(nlogn+n\times k\times 2^{k})$$
对$$k=1$$特殊情况考虑一下（包含起点和终点相同的路径，用上述方法会出现重复计数）。
##标准程序
```c++
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<assert.h>
#include<math.h>
#include<vector>
#define MP make_pair
#define PII pair<int,int>
#define X first
#define Y second
#define ll long long
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;

const int maxn = 50000+10;
const int INF = 0x3f3f3f3f;
const int maxk = 13;
const int maxm = (1<<10)+10;
vector<int> g[maxn];

int n, k, s[maxn], vis[maxn], num[maxn], dp[maxk][maxn], w[maxn];
ll ans;
void init(){
    mem(vis, 0); ans = 0;
}

PII Find(int u, int f, int sum){
    s[u] = 1;
    int lar = 0;
    PII tmp = MP(INF, 0);
    for(int i = 0; i < g[u].size(); i ++){
        int v = g[u][i];
        if(v == f || vis[v]) continue;
        PII x = Find(v, u, sum);
        s[u] += s[v];
        lar = max(lar, s[v]);
        tmp = min(tmp, x);
    }
    lar = max(lar, sum-s[u]);
    return min(tmp, MP(lar, u));
}

void dfs2(int u, int f, int x){
    num[x] ++;
    s[u]=1;
    for(int i = 0; i < g[u].size(); i ++){
        int v = g[u][i];
        if(v == f || vis[v]) continue;
        dfs2(v, u, x|(1<<w[v]));
        s[u]+=s[v];
    }
}

ll cal(int u, int x){
    ll ans = 0;
    for(int i = 0; i < (1<<k); i ++) num[i] = 0;
    dfs2(u, 0, x);
    
    for(int i = 0; i < (1<<k); i ++) dp[0][i] = num[i];
    for(int i = 1; i <= k; i ++){
        for(int j = 0; j < (1<<k); j ++){
            dp[i][j] = dp[i-1][j];
            if(!(j&(1<<(i-1)))) dp[i][j] += dp[i-1][j^(1<<(i-1))];
        }
    }
    for(int i = 0; i < (1<<k); i ++) ans += 1ll * num[i]*dp[k][i^((1<<k)-1)];
    return ans;
}

void dfs(int u, int f, int sum){
    u = Find(u, f, sum).Y;
    ans += cal(u, 1<<w[u]); vis[u] = 1;
    for(int i = 0; i < g[u].size(); i ++){
        int v = g[u][i];
        if(vis[v]) continue;
        ans -= cal(v, (1<<w[u])|(1<<w[v]));
    }
    for(int i = 0; i < g[u].size(); i ++){
        int v = g[u][i];
        if(!vis[v] && s[v] > 1) dfs(v, u, s[v]);
    }
}

int main()
{
    while(scanf("%d%d", &n, &k) != EOF){
        for(int i = 1; i <= n; i ++) scanf("%d", &w[i]), w[i] --, g[i].clear();
        for(int i = 1; i < n; i ++){
            int u, v; scanf("%d%d", &u, &v);
            g[u].push_back(v), g[v].push_back(u);
        }
        if(k == 1) { printf("%lld\n", 1ll*n*n); continue; }
        init();
        dfs(1, 0, n);
        printf("%lld\n", ans);
    }
    return 0;
}
```

#Problem H To begin or not to begin
##提交情况：216/298
##解题思路
直接推公式即可。
先手获胜概率为$$\frac{\lfloor \frac{n+2}{2}\rfloor }{n+1}$$，向下取整。
n为偶数时，大于$$\frac{1}{2}$$；n为奇数时，等于$$\frac{1}{2}$$。所以n为偶数时，先手获胜；n为奇数时先手后手获胜概率相同。
标准程序
```c++
#include <stdio.h>
#include <iostream>
#include <stdlib.h>

using namespace std;
int main(){
    for(int n; cin>>n; ){
        puts(n&1?"0":"1");
    }
    return 0;
}
```

#Problem I Convex
##提交情况：216/254
##解题思路
用公式$$\frac{1}{2}\times sin\theta \times a \times b$$求三角形面积再求和
##标准程序
```c++
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;

const double pi = acos(-1.0);

int n, d;
double sum;

int main(){
    while(scanf("%d %d", &n, &d) != EOF){
        sum = 0;
        for(int i = 0, ang; i < n; ++i){
            scanf("%d", &ang);
            sum += sin(1.0 * ang * pi / 180);
        }
        printf("%.3f\n", 0.5 * d * d * sum);
    }
    return 0;
}
```

#Problem J Find Small A
##提交情况：215/360
##解题思路
用位移操作，每次向右移动8位，统计小$$a$$的数量即可。
##标准程序
```c++
#include<iostream>
#define a1mask (97 << 0)
#define mask1 (0x000000ff)
using namespace std;

int cnt_a(uint32_t ind) {
    uint32_t ret = 0;
    while(ind) {
        ret += !!((ind & mask1) == a1mask);
        ind >>= 8;
    }
    return ret;
}

int main() {
    int32_t n, ai, sum = 0;
    scanf("%d", &n);
    for (int32_t i = 0; i < n; i++) {
        scanf("%d", &ai);
        sum += cnt_a(ai);
    }
    printf("%d\n", sum);
    return 0;
}
```

#Problem K Guess the number
##提交情况：20/73
##解题思路
题目需要回答两个问题：1、最优策略需要猜几次；2、有多少种最优策略。
1、由题意，易得动规方程：$$f(x)=min(max(y,1+f(x-y))|y\in [1,x])$$，此方程复杂度太高，可以作为找规律方法的基础。现在我们采用另一种方式来思考这个问题：
现在来反推最优策略，设函数$$y=f(x)$$是区间长度位$$x$$时最优策略的猜数次数，并且容易得知以下事实：
当$$x_{1}\leq x_{2}$$时有$$f(x_{1})\leq f(x_{2})$$
所以，$$y=f(x)\geq 1+f(x-y)$$，$$1+f(x-y)$$是$$f(x)$$的下限，现在讨论，$$f(x)$$到下限时的情况。
则$$f(x-f(x))=y_{1}=y-1$$，同时可得$$f(x+y+1)=y+1$$，则由公式可得如下$$f(x)$$到达下限时的$$x$$值
```katex
\begin{array}{}
f(1)=1,f(3)=2,f(6)3,f(10)=4 \\
f(15)=5,f(21)=6,f(28)=7,f(36)=8
\end{array}
```
则可知，$$f([2,3])=f(3)=2, f([4,6])=f(6)=3\ldots $$，由此我们得到了$$f(x)$$的值。
2、现在来讨论最优策略有多少种。由动规方程$$max(y,1+f(x-y))$$其中$$f(x-y)$$中$$y$$的上限为$$f(x)$$，$$f(x-y)$$的上限是$$f(x)-1$$，这两个上限大大缩小了动规方程中$$y$$的取值范围。具体的，请看标程。
##标准程序
```c++
#include <iostream>
#include <stdint.h>
#include <inttypes.h>
#include <algorithm>
#define Maxn 5000005
#define Mod_Num 100000073
using namespace std;
typedef int64_t inta;
const bool Output_flag = true;
inta many_Time[Maxn + 5];
inta many_Acti[Maxn + 5];
void init() {
    memset(many_Time, 0, sizeof(many_Time));
    memset(many_Acti, 0, sizeof(many_Acti));
}

int64_t max(inta a,inta b)
{
    if (a > b) return a;
    return b;
}
int main()
{
    init();
    inta *p = many_Time;
    inta *q = many_Acti;
    p[1] = 1; p[0] = 0;
    q[1] = 1; q[0] = 1;
    int32_t i, j, t, total_num, pre_total_num;
    i = 2; j = 2; pre_total_num = 1;
    while (j < Maxn) {
        t = i;
        total_num = pre_total_num + 1;
        total_num %= Mod_Num;
        pre_total_num = 0;
        while (j < Maxn && t--) {
            p[j] = i;
            q[j] = total_num;
            total_num = (total_num - q[j - i] + Mod_Num) % Mod_Num;
            pre_total_num += q[j];
            pre_total_num %= Mod_Num;
            j++;
        }
        i++;
    }
    int32_t a,b;
    while (scanf("%d%d",&a,&b)!=EOF)
        printf("%" PRId64 " %" PRId64 "\n",p[b-a+1],q[b-a+1]);
    return 0;
}
```

已有 7 条评论

慕若曦

November 9th, 2016 at 09:50 pm

你最近这个解题频率看起来很亢奋啊……在做什么准备嘛

回复
1. rin
  
  November 9th, 2016 at 11:37 pm
  
  准备在区域赛打铁:hj-huamoji60:
  
  回复
胡杨

December 14th, 2016 at 11:58 am

代码挺多的额

回复
慕若曦

December 25th, 2016 at 01:48 am

节日快乐哦Baby（这个是读卑鄙吧~）

回复
1. rin
  
  December 31st, 2016 at 01:58 pm
  
  新年快乐
  
  回复
Matriks

January 5th, 2017 at 01:00 pm

po主加油！
区域赛金牌！！

回复
1. rin
  
  January 5th, 2017 at 08:05 pm
  
  肝！
  
  回复

[ICPC2016Dalian Onsite]官方题解

已有 7 条评论

添加新评论

最近回复

分类

归档

Links

其它