1004

2024-02-27 12:10:15

A.题目描述
决定在之后的天中用很多理综卷子来折纸飞机，以此来消磨高三时光。于是他收
集到了张相同的理综试卷。一张试卷折一架飞机。
为了不让自己某一天太过无聊，他要求自己每天至少要用一张试卷折飞机，同时为了
不让自己过度劳累，他决定这套试卷不需要全部折完。只会折一种纸飞机，但他想
知道，总共有多少种可能的消磨时光的方案。
当然知道答案，但是他希望你帮他验证一下，由于答案可能会很大，所以你只需要算
出答案对取模后的结果就行了。

解：
插板法或者打表可知
答案为C（n,m）
关键是怎么处理求组合数的问题
注意到p为质数并且模数已知
这不就是打表吗
对于子任务1 组合数递推
子任务2 和3 lucas C(n,m)=lucas(n/p,m/p)*C(n%p,m%p);
但是注意询问很多所以要进行打表

对于最后一个子任务

注意到 T只有30 并且 O(max(log2(n)*T,1e9)) 还是有一些余地
所以我们考虑在阶乘上入手问题的关键在于处理阶乘

然后我们发现问题的关键就是阶乘表太大打不出来

所以我们就可以分块打表
将1e9 分成块长为1000000 每次找出所在块号暴力求
这样刚好是极限然后就可以过...
code:
算了还是不放code 太长了

B
XXX解决了 SF之问后决定大宴宾客，于是他找到了一棵有 N个节点的果树，这棵果树
上总共有种不同的果实，树上每个节点都有一颗果实。
现在为了表明自己很文明，决定只在果树上选择一棵子树摘走，同时，他希望摘到
尽可能多的种类的果实，现在希望你能帮助他确定某些子树中总共有多少种不同的
果实。
总共会有M 次询问，为了方便，指定了根为 1号节点。

解：
子树上的问题首先想到DFS序列转化为线性问题
我考试的时候就是中了set的招时间复杂度上过的去但是常数太大又是捆绑测试导致...
细致细致观察到我们其实可以用容斥原理
关键是怎么容斥
一个节点只对父亲产生贡献
排除点的情况就是 lca 两个相同点
并且这两个相同颜色的点挨的最近。。。
最近亲戚关系 lca dfs序列
。。。
其实还可以用dfs序列 +莫队转化为线性
就跟HH的项链差不多了


//
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define maxnn 1000100
#define maxn 500100
int n,m,c;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
inline int R()
{
    char t=GC;
    int x=0;
    while(!isdigit(t)) t=GC;
    while(isdigit(t)) x=x*10+t-48,t=GC;
    return x;
}
int las[maxnn],en[maxnn],tot,id[maxnn],nex[maxnn];
int ddd[maxnn];
int tr[maxnn];
int size[maxn];
int dfn[maxn],cnt;
int f[maxn][20];
int dep[maxn];
int d[maxnn];
int C[500010];
int cou[500010];
void add(int a,int b) {
    en[++tot]=b;
    nex[tot]=las[a];
    las[a]=tot;
}
int go_up(int s,int k)
{
    int d=log2(n);
    for(int i=d;i>=0;i--)
    {
        if((1<<i)&k)
        {
            s=f[s][i];
        }
    }
    return s;
}
int lca(int a,int b)
{
    if(dep[a]<dep[b])
    {
        swap(a,b);
    }
    int d=dep[a]-dep[b];
    a=go_up(a,d);
    if(a==b) return b;
    int e=log2(n);
    for(int i=e;i>=0;i--)
    {
        if(f[a][i]!=f[b][i])
        {
            a=f[a][i];
            b=f[b][i];
        }
    }
    return f[a][0];
}
void dfs(int v,int fa) {
    dep[v]=dep[fa]+1;
    dfn[v]=++cnt;
    tr[cnt]=v;
    int r=log2(n);  
    f[v][0]=fa;
    for(int i=1;i<=r;i++)
    {
        f[v][i]=f[f[v][i-1]][i-1];
    }
    if(C[id[v]])
    {
        ddd[lca(tr[C[id[v]]],v)]++;
    }
    C[id[v]]=cnt;
    for(int i=las[v]; i; i=nex[i]) {
        int u=en[i];
        if(u!=fa) {
            dfs(u,v);

        }
    }
}
void dfs1(int v,int fa) {
    size[v]=1-ddd[v];
    for(int i=las[v]; i; i=nex[i]) {
        int u=en[i];
        if(u!=fa) {
            dfs1(u,v);
            size[v]+=size[u];
        }
    }
}
void FIE () {
    freopen("fruit4.in","r",stdin);
    freopen("tes.txt","w",stdout);
}   
int main() {
    //FIE();
    n=R();
    m=R();
    c=R();
    int x,y;
    for(int i=1; i<=n; i++) {
        id[i]=R();
    }
    for(int i=1; i<n; i++) {
        x=R();y=R();
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    dfs1(1,0);
    while(m--) {
        x=R();
        printf("%d\n",size[x]);
    }
}

C
心情大好的xxx 决定出去旅行，他决定在n 个城市中来选择旅行路线，这个城市由m
条双向道路连接，由于特殊的原因，对于双向道路，m->n 的长度为ai ，
n->m的长度为di ，居住的城市为 1号城市。
现在 xxx想要从 1号城市出发，经过一些城市，最后回到 1号城市，并且由于每条路上
的风景是一样的，因此要求每条边至多经过一次，然而发现旅行可能会耗费
过多时间，于是他决定在所有的可能路线中选择最短的那一条路线。
由于正忙于收拾书包，所以他拜托你帮他计算一下最短的可能路线的长度。
解：
注意到本题要求一号节点的最小环
最小环的必要条件是从一号点出发不重复经过与1号点相连的边回到一号点要限制与一号点相连的点被重复经过
删边限定每次只能走这条边暴力求最短路时间复杂度O(n^2 log2(n))

考虑一次枚举多对，将一号点拆成 2个，一个做入点，一个做出点，然后将所有和一号点相邻的点分成两个集合利用随机算法
其中一个集合连到出点，入点连到另一集合，那么跑一次入点到出点的最短路即可算出两个集合分别选一个点的所有环
然后有两种处理方式，可以直接随机划分点集，多随机几次就行了
或者按照二进制分组，依次枚举二进制位，将该位为的做一个集合，为的做另一个集合即可，复杂度 O(nlog2n)

不知道为什么我dij写挂了 spfa跑的飞快

co'de:


//
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define maxnn 400110
int n,m;
#define ll long long
int las[maxnn],en[maxnn],tot,id[maxnn],nex[maxnn],le[maxnn];
ll ans=1000000000000;
queue<int > Q;
int f[maxnn];
ll dis[maxnn];
int mark[maxnn],mask[maxnn];
vector<int> s;

void add(int a,int b,int c) {
    en[++tot]=b;
    nex[tot]=las[a];
    las[a]=tot;
    le[tot]=c;
}
void spfa() {
    for(int i=1; i<=n+1; i++) {
        dis[i]=100000000000;
        mark[i]=0;
    }
    Q.push(1);
    mark[1]=1;
    dis[1]=0;
    while(Q.size()) {
        int v=Q.front();
        mark[v]=0;
        Q.pop();
        for(int i=las[v]; i; i=nex[i]) {
            int u=en[i];
            if(mask[u]&&f[u]&&(v==1)) {
                if(dis[v]+le[i]<dis[u]) {
                    dis[u]=dis[v]+le[i];
                    if(!mark[u]) {
                        mark[u]=1;
                        Q.push(u);
                    }
                    continue;
                }

            } else {
                if(mask[u]&&(!f[u])&&(v==1))
                    continue;
            }
            if(mask[v]&&(u==1)&&(!f[v])) {
                if(dis[v]+le[i]<dis[n+1]) {
                    dis[n+1]=dis[v]+le[i];
                    if(!mark[n+1]) {
                        mark[n+1]=1;
                        Q.push(n+1);
                    }
                
                }   continue;
            }
            if((v!=1)||u!=1) {
                if(dis[v]+le[i]<dis[u]) {
                    dis[u]=dis[v]+le[i];
                    if(!mark[u]) {
                        mark[u]=1;
                        Q.push(u);
                    }
                }
            }
        }
    }
}

void FIE () {
    freopen("travel2.in","r",stdin);
    freopen("travel.out","w",stdout);
}
int main() {
    //FIE();
    int x,y,z1,z2;
    srand(time(0));
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++) {
        scanf("%d%d%d%d",&x,&y,&z1,&z2);
        add(x,y,z1);
        add(y,x,z2);
    }
    for(int i=las[1]; i; i=nex[i]) {
        int u=en[i];
        {
            s.push_back(u);
            mask[u]=1;
        }
    }
    int cnt=19;
    while(cnt--) {
        int d=s.size();
        for(int i=0; i<d; i++) {
            f[s[i]]=rand()%2;
        }
        spfa();
        ans=min(ans,dis[n+1]);
    }
    printf("%lld",ans);



}

码农公寓

相关文章