1004

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);



}
上一篇:PTA 乙级——1004成绩排名 C++实现


下一篇:1004 Counting Leaves (30分)