1. noip模拟测验（一）-A.POB

图的面数包括无限面，也即图与整个平面不会被完全分割开。

想想有哪些图论算法可以求解，发现生成树似乎很合理。

保证两条边可以在非端点处相交，更加证实了我们的想法，再造几个小样例自己试试于是大胆得出结论，答案就是边权总和减去最大生成树（也就得到了删边的最小值）、

只要想到了最大生成树就非常简单了，也非常容易想到，建议作为生成树模板

2. noip模拟测验（一）-凯旋而归

题意：对于一个序列a,f(a)等于将序列断为两部分，两部分的异或值的和的最大值（也可以只有一部分即整个a）。给定序列，求出其每个前缀b的f(b)

暴力做法很显然，统计前缀异或和，枚举两端点l,r。则前缀1~r的答案为s[l]+s[l]^s[r]，统计每个前缀最大值输出即可，复杂度O(n^2)

在上述做法上扩展，考虑0/1对每个s[r]的每一位的贡献。设s[r]=k，则若k的一位为1，可发现s[l]是0/1是无所谓的。因为1^1+1和1^0+0答案都为1。因此O(n)枚举s[r]，之后只贪心的考虑s[r]为0的每一位即可。当然，将s[r]为1的每一位忽略即可。

之后我们设g[x]为能异或上x的最小i值，对于s[r]为0的每一位，我们肯定要尽量让其为1，这样0^1+1=2，也即贡献了两个“1”。所以从高到低考虑，tmp表示当前可以异或上的值（能让s[r]增大的量为2*tmp，因为1个”1”可以贡献两个”1”），当s[r]的一位j为0的时候，我们考虑能不能让g[tmp+(1<<j)]<=r（因为l肯定在r的前面，这也是为什么g统计最小值的原因）如果能就让tmp+=(1<<j)即可，重复此过程。

代码虽然很简单，但我认为这题是有难度的

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,M=(1<<22);
int n,s[N],g[M],tmp;
int main(){
    memset(g,0x3f,sizeof(g)); 
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&tmp);
        s[i]=s[i-1]^tmp;
        g[s[i]]=min(g[s[i]],i);//初始化
    }
    for(int i=M-1;i>=0;i--)
        for(int j=0;j<22;j++) g[i]=min(g[i],g[i|(1<<j)]);
        //如果i|(1<<j)可以，那么i也一定可以（多余的位不用考虑，如果多余的位s[r]为1无所谓，如果为0的话之后自然有更优的情况来更新tmp）
    for(int i=1;i<=n;i++){
        tmp=0;
        for(int j=21;j>=0;j--)
            if(!(s[i]>>j&1)&&g[tmp+(1<<j)]<=i) tmp+=(1<<j);
        printf("%d\n",s[i]+(tmp<<1)); 
    }
    return 0;
}

3. 2021-10-12-1班NOIP模拟测验（三）-battle

第二部分的30分还没调出来呢，别说满分了

4. noip模拟测验（三）-走向巅峰

这是一道看似不可做的题目事实上对我而言没题解就是不可做

思维过程：考虑直接观察题解

自己的注释：

要点：

1. 分类讨论直径奇偶性，注意若直径为奇则叶子只分为两类（两个根的子树）

2. 对于如何求出根（直径中点或者直径中边的两个端点）：先找出一条直径的两个叶子，使用vector存储两个叶子到目前的根（一般以1作为根）的路径，之后翻转再拼接，得出一整条直径，然后取出中点即可。算是一个小trick

3. 对于一个点，如果染黑的概率为 $a/b$ 则期望步数为 $b/a$

4. 多预处理信息

5. 若求 $a!$ 的逆元，求出取模后的 $a!$ 之后再用快速幂得出逆元即可。阶乘取模不会对求逆元造成问题。

感觉对于式子虽然大概能理解，但是自己推是万万不能，感觉这题对我收获最大的是增加了码力（下面是根本没法看的代码）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10,mod=998244353;
int n,m,len,rt,rt1,lfcnt,fat[N];
int h[N],e[N],ne[N],idx,leaf1,leaf2;
int dep[N],id[N],team[N],d[N];
vector<int> R[2];
struct Nd{
    int x,lf;
}; 
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    d[a]++,d[b]++;
}
void get_dep(int u,int fa,int d,int _id){
    dep[u]=d;id[u]=_id;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa) continue;
        if(!_id&&u==rt||u==rt1) ++m;
        get_dep(j,u,d+1,(!_id?m:_id));
    }
}
Nd findmr(int u,int fa){
    Nd mx1={0,0},mx2={0,0};int CNT=0;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa) continue;
        fat[j]=u;
        Nd t=findmr(j,u);CNT++;
        if(t.x+1>mx1.x) mx2=mx1,mx1={t.x+1,t.lf};
        else if(t.x+1>mx2.x) mx2={t.x+1,t.lf};
    }
    if(mx1.x+mx2.x>len){
        len=mx1.x+mx2.x;
        if(mx1.x&&mx2.x) leaf1=mx1.lf,leaf2=mx2.lf;
        else leaf1=(!mx1.lf?u:mx1.lf),leaf2=(!mx2.lf?u:mx2.lf); 
    }
    if(!CNT) mx1={0,u};
    return mx1;
}
void get_rd(int u,int ed,int ID){
    R[ID].push_back(u);
    while(u!=ed){
        u=fat[u];
        if(ID||u!=ed) R[ID].push_back(u);
    }
}
ll qmi(ll a,ll p){
    ll res=1;
    while(p){
        if(p&1) res=(res*a)%mod;
        a=(a*a)%mod,p>>=1;
    }
    return res;
}
ll Inv(ll x){return qmi(x,mod-2);}
ll presum[N],d0,fact[N],infact[N];
ll getc(ll x,ll y){
    return fact[x]*infact[y]%mod*infact[x-y]%mod;
}
int main(){
    memset(h,-1,sizeof(h));
    scanf("%d",&n);int m1=0;
    for(int i=0;i<n-1;i++){
        int a,b;scanf("%d%d",&a,&b);
        add(a,b);add(b,a);
    }
    for(int i=1;i<=n;i++) 
        if(d[i]<=2) lfcnt++;
    findmr(1,-1); 
    if(len&1){
        get_rd(leaf1,1,0);get_rd(leaf2,1,1);
        reverse(R[1].begin(),R[1].end());
        for(int i=0;i<R[1].size();i++) R[0].push_back(R[1][i]);
        rt=R[0][len/2];rt1=R[0][len/2+1];
//      cout<<rt<<" "<<rt1<<endl; 
        get_dep(rt,rt1,0,1);get_dep(rt1,rt,0,2);
        for(int i=1;i<=n;i++){
//          cout<<dep[i]<<endl;
            if(dep[i]<len/2) m1++;
            else team[id[i]]++;
        }
    }
    else{
        get_rd(leaf1,1,0);get_rd(leaf2,1,1);
        reverse(R[1].begin(),R[1].end());

        for(int i=0;i<R[1].size();i++) R[0].push_back(R[1][i]);
        rt=R[0][len/2];
//      cout<<rt<<endl;
        get_dep(rt,-1,0,0);
        for(int i=1;i<=n;i++){
            if(dep[i]<len/2) m1++;
            else{
                team[id[i]]++;
//              cout<<i<<endl;
            }
        }
    }
//  cout<<lfcnt<<endl;
    for(int i=1;i<=m;i++) d0+=team[i];
    for(int i=d0;i;i--) presum[i]=(presum[i+1]+lfcnt*Inv(i))%mod;
    fact[0]=infact[0]=1;
    for(ll i=1;i<=N-10;i++){
        fact[i]=(fact[i-1]*i)%mod;
        infact[i]=(infact[i-1]*Inv(i))%mod;
    }
    ll ans=0;
    for(int T=1;T<=m;T++){
        ll sumcnt=team[T];
        for(int i=0;i<team[T];i++){
            ans=(ans+getc(sumcnt,i)*fact[d0-(sumcnt-i+1)]%mod*(d0-sumcnt)%mod*presum[sumcnt-i+1]%mod*fact[sumcnt-i]%mod*Inv(fact[d0])%mod)%mod;
        }
    }
    printf("%lld",ans);
    return 0;
}
/*
leafcnt=m
枚举的集合大小为d即为team[team_id] 
染黑一个点概率为n/m，期望步数为 m/n（即 1/(n/m)）

6
1 2
2 3
3 4
4 5
5 6 
*/