前几天的由于都是在3号机房打的，电脑自动清空了，再加上只有Away一个人有号，程序没有留下来，日后补。今日多原题。

光线

原题链接

当时是趁着信息课赶紧赶来写题，当时看到这题几分钟切了 $ n=2 $ 的情况，距离正解就差一点点，这次长见识了，不仅物理可以用整体法，其他的也都可以用整体法。

代码和第一篇题解一样（抄的）。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod=1e9+7;

const int N=5e5+10;

long long qmi(long long a,long long b){
    long long res=1;
    a%=mod;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
int n;
int a,b;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    long long inv=qmi(100,mod-2);
    long long p=1,q=0;
    for(int i=1;i<=n;i++){
        cin>>a>>b;
        a=a*inv%mod,b=b*inv%mod;
        long long w=qmi(1-q*b%mod+mod,mod-2);
        q=(b+a*a%mod*q%mod*w)%mod;
        p=p*a%mod*w%mod;
    }
    cout<<p<<'\n';
}

后面的几道题由于去上课了就没时间写了。

世界冰球锦标赛

原题链接

中午吃完饭来到机房看到这题自然是一眼背包，但是看到这体积大小就知道不对，想了一会想到之前在杭州集训的时候就写过这种题，在Acwing上也刚看到过，是双向DFS（或者说是折半DFS），但是没有上手过，毕竟在杭州的时候人能保持清醒就不容易了。

#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;

const int N=50;

int a[N];
int n,m;
int suma[1<<21];
int sumb[1<<21];
int cnta,cntb;

void dfs(int l,int r,int sum,int b[],int &cnt){
    if(sum>m) return;
    if(l>r){
        b[++cnt]=sum;
        return;
    }
    dfs(l+1,r,sum+a[l],b,cnt);
    dfs(l+1,r,sum,b,cnt);
}
int ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int mid=n>>1;
    dfs(1,mid,0,suma,cnta);
    dfs(mid+1,n,0,sumb,cntb);
    sort(suma+1,suma+1+cnta);
    for(int i=1;i<=cntb;i++){
        ans+=upper_bound(suma+1,suma+1+cnta,m-sumb[i])-suma-1;
    }
    cout<<ans<<'\n';
}

猜谜游戏

原题链接

这一题刚开始看的时候想了好久，以为有数学方法但是没想出来，想到和两个点之间路径的最大值有关，但是由于没有见过这种题目，所以想不到，只能说这次又学了一手。

大概是重构树，求瓶颈。

#include <bits/stdc++.h>

using namespace std;

const int N=4e5+10;

int n,q,m;

int a[N];
int fa[N],f[N];

int e[N],ne[N],h[N],idx;

int top[N],siz[N],son[N],dep[N],cnt;

int read(){
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=getchar();
    return x;
}

void add(int x,int y){
    e[++idx]=y;
    ne[idx]=h[x];
    h[x]=idx;
}

int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}

void dfs1(int x){
    siz[x]=1;
    son[x]=-1;
    for(int i=h[x];i;i=ne[i]){
        int ver=e[i];
        if(ver!=fa[x]){
            fa[ver]=x;
            dep[ver]=dep[x]+1;
            dfs1(ver);
            siz[x]+=siz[ver];
            if(siz[son[x]]<siz[ver]) son[x]=ver;
        }
    }
}

void dfs2(int x,int t){
    top[x]=t;
    if(son[x]==-1) return;
    dfs2(son[x],t);
    for(int i=h[x];i;i=ne[i]){
        int ver=e[i];
        if(ver!=fa[x]&&ver!=son[x]) dfs2(ver,ver);
    }
}

int lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]){
            y=fa[top[y]];
        }
        else{
            x=fa[top[x]];
        }
    }
    return dep[x]<dep[y]?x:y;
}

int main(){
    n=read();
    m=read();
    q=read();
    cnt=n;
    int n1=n<<1;
    for(int i=1;i<=n1;i++){
        f[i]=i;
    }
    for(int i=m;i>=1;i--){
        for(int j=i+i;j<=n;j+=i){
            int u=find(i),v=find(j);
            if(u!=v){
                a[f[u]=f[v]=++cnt]=m-i+1;
                add(u,cnt);
                add(cnt,u);
                add(v,cnt);
                add(cnt,v);
            }
        }
    }
    dfs1(cnt);
    dfs2(cnt,cnt);
    // for(int i=n+1;i<=cnt;i++){
    //     cout<<a[i]<<' ';
    // }
    // cout<<'\n';
    for(int i=1;i<=q;i++){
        int x,y;
        x=read(),y=read();
        // cout<<x<<y<<'\n';
        cout<<a[lca(x,y)]<<'\n';
    }
}

逆序对

还没来得及补。