杭电杯第七场

个人题解，欢迎指正

P1003

思路：

​ 由于是一颗无根树，我们直接枚举脖子节点，然后从脖子节点的儿子节点中选出四个符合条件的子树作为头，左右手和躯干（包括两个脚）。现在的问题是如何确定手和和躯干，直接枚举的话复杂度为$n^2$及以上，加上枚举脖子……

​ 突然冒出来的思路：我们把每个儿子节点的儿子，每个儿子到脖子节点看做一个手，总数记为$x$，那么手的总数为$C^2_x$，因为可能会选重复，所以我们记录手选在同一个子树的情况，让$sson=\sum C_{son[j]}^2$，$j$为脖子的儿子，$son[j]$为$j$的儿子数量,此时我们枚举躯干$j$,手的情况数就是$C_{x-(son[j]-1)}^2-sson+C_{son[j-1]}^2$，脚的情况为$C_{son[j-1]}^2$，头的情况数为$son[i]-1$($i$为脖子节点),乘上就可以了

​ 最后记得结果可能为负数，取正一下

​ 因为各种小错误WA了几发

Code：

#include<bits/stdc++.h>
#define ll long long
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0, z = 1;char c = getchar();while (!isdigit(c)) {if (c == '-')z = -1;c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return z * x;}
inline void writ(ll x){if(x<0) {putchar('-');x=(~x)+1;}if(x>9)writ(x/10);putchar(x-x/10*10+48);}
const int N=5e5+5;
const ll mod=998244353;

ll C2(ll x){
    return x*(x-1)/2%mod;
}
int n;

void Qingtuan(){
    n=read();
    vector<vector<int>>f(n+1);
    vector<ll>son(n+1);
    ll x,y;
    for (int i = 1; i < n; i++)
    {
        x=read();y=read();son[x]++;son[y]++;
        f[x].push_back(y);f[y].push_back(x);
    }
    ll res=0;
    ll sson;
    for (int i = 1; i <= n; i++)
    {
        if(son[i]<4)continue;
        x=0;y=0;sson=0;
        for(auto j:f[i]){
            if(son[j]>1){
                x+=son[j]-1;
                sson=(sson+C2(son[j]-1))%mod;
            }
        }
        
        for(auto j:f[i]){
            if(son[j]>2){
                res=(res+(C2(x-(son[j]-1))-sson+C2(son[j]-1))*(son[i]-3)%mod*C2(son[j]-1)%mod)%mod;
            }
        }
    }
    writ((res+mod)%mod);ptn;

}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);
    int T=read();while (T--)
    Qingtuan();
    return 0;
}

P1004

思路：

最多：黑白相间的挨着放，用纯白的把黑的隔开

最少：黑的放一块，旁边加两个黑白相间的，最后把黑白的抱对

Code：

#include<bits/stdc++.h>
#define ll long long
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0;scanf("%lld",&x);return x;}
inline void writ(ll x){printf("%lld",x);}

int a[4];


void Qingtuan(){
    int mi,mx;
    for (int i = 0; i < 4; i++)
    {
        a[i]=read();
    }
    mx=a[0]+a[1]+a[2]+min(a[0]+1,a[3]);
    if(a[3]){
        if(a[1])
            a[1]--;
        if(a[2])
            a[2]--;
        a[3]=1;
    }
    mi=a[3]+a[0]+max(a[1],a[2]);
    writ(mi);putchar(' ');writ(mx);ptn;
}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T=read();while (T--)
    Qingtuan();
    return 0;
}

P1008

思路：

我也不知道我是啥思路0.0，感觉像写了一发过了

观察几种情况：有等腰三角形且第三条边不为$1$的时候先手必胜，最终情况为三条边：$1,1,1$

emm就猜了一个最终每堆为$1$的$Nim$博弈，然后就过了 0.0 等题解看看详细怎么推吧

Code:

#include<bits/stdc++.h>
#define ll long long
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0;scanf("%lld",&x);return x;}
inline void writ(ll x){printf("%lld",x);}

void Qingtuan(){
    ll res=0;
    for (int i = 0; i < 3; i++)
    {
        res^=read()-1;
    }
    if(res)puts("Win");
    else puts("Lose");

}

int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T=read();while (T--)
    Qingtuan();
    return 0;
}