noip冲刺赛第2遍试验

  调换机可以起到增加局域网的意义,沟通机的种种接口直接与贰个单台主机或另一个以太网交流机相连,它一般都干活在全双工情势。沟通机的接口处有存储器,能在出口端口繁忙时把到来的帧举办缓存,在路经空闲时转载出来。同时它是一种即插即用设备,其里面维护着多少个帧沟通表,这一个帧互换表通过自学习算法自动地逐步建立起来。

1.公约数 (gcd.cpp\c\pas)

交流机帧沟通表自学习树立进度:

【难题讲述】
给定八个正整数,在[1,n]的限定内,求出有稍许个无序数对(a,b)满意gcd(a,b)=a xor b。

  5588葡京线路 1

【输入格式】 输入共一行,1个正整数n。

  刚起初时,互换机里面的交流表为空。即使此时PC6给PC13殡葬2个帧,该帧从接口1进入沟通机,交换机收到该帧后,先物色沟通表,若是找到相应的接口对应项目就径直转接该帧,没有查到应从哪个接口转载这些帧就展开如下的进度。接着,交流机把那几个帧的源地址PC6的MAC地址和接口1写入沟通表中,并向除接口1以外的具备接口广播这几个帧。PC5和PC14接受那些帧后,由于目标地址不对,于是放任这一个帧,PC13的位置和MAC帧中的目的地址一样,PC13收下这些帧,此时沟通机把PC13的MAC地址和接口2写入交换表。有时互换机的接口会变换主机,或然主机会转换网卡(网络适配器),那就要求改变交流机互换表中的项目,为此,在交流表中的各个种类都留存一定的实惠时间,过期的档次会被机关删除。

【输出格式】 输出共一行,3个正整数表示答案。

 

【输入输出样例】 gcd.in  3

沟通机和路由器的界别:

gcd.out 1

  1.集线器、沟通机都是做端口增添的,就是扩展局域网(日常都以以太网)的接入点,约等于能让局域网可以连进入越多的电脑。路由器是用来做网间连接,也等于用来延续区其他网络。

分解:唯有(2,3)满意须要

  2.互换机是采取物理地址只怕说MAC地址来规定转载数量的目的地址。而路由器则是行使差别网络的IP地址来规定数据转发的地方。IP地址是在软件中贯彻的,描述的是设备所在的互连网,有时这一个第2层的地点也称之为协议地址或许互联网地址。MAC地址平日是硬件自带的,由网卡生产商来分配的,而且已经固化到了网卡中去,一般的话是不行变更的。而IP地址则一般由互连网管理员或系统自动分配。

【数据范围】 对于3/10的数据满足n<=1000 对于3/5的数量满意n<=10^5
对此百分之百的数目满意n<=10^7

  3.交流机工作在链路层,路由器工作在互连网层。

拿到题就打了二十七分版本,没推出去公式。

 

60分版本:

设a^b=c,所以可得a^c=b;

–>gcd(a,a^c)=c;

然后通过枚举a,c落成代码

复杂度O(nlog(n^2))

100分版本:

在伍拾陆分版本上,加上以下公式:

先是,a=b肯定无解,不妨设a>b:

1:gcd(a,b)是a,b的因数,a-b中也有gcd(a,b)这么些因子—>a-b>=gcd(a,b);

2:分明,a^b>=a-b,因为异或区其他地点为1,而减法会牵扯借位;

据此取得gcd(a,b)<=a-b<=a^b;

因为gcd(a,b)=a^b

所以a^b=a-b=gcd(a,b)=c;

b=a-c;

之所以只需判断a^c是还是不是等于a-c即可

枚举c,a=i*c

复杂度O(nlog(n))

#include<cstdio>
int main()
{
    int n,ans=0;
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; ++i)
        for(int j = n/i ; j >= 2 ; --j)
        {
            int a=j*i;
            if((i^a)==(a-i))++ans;
        }
    printf("%d",ans);
    return 0;
}

 

2.通讯 (message.cpp\c\pas)

【难题讲述】“这一切都以命局石之门的 接纳。” 试图研制时间机器的自发性 SE汉兰达N
截获了中二地理学家伦太郎发往过去的一条
短信,并通过得知了伦太郎制作出了对讲机微波炉(仮)。
为了精通时间机器的技巧,SE索罗德N 总部必须尽快将以此消息通过不法秘密广播发表互联网,传达到独具分部。 SE牧马人N 共有 N 个机构(总部编号为 0),通信互联网有 M
条单向通信线路,每条 线路有多少个定位的报纸发布费用 Ci。
为了保密,音讯的传递只好依据一定的格局开展:从壹个已知新闻的部门向
另二个与它有路经的机关传递(恐怕存在多条通讯线路)。大家定义总花费为所有机构传递消息的费用和。
幸运的是,借使七个部门得以向来或直接地相互传递新闻(即能依据上述办法
将音信由 X 传递到 Y,同时能由 Y 传递到
X),大家就足以忽略它们之间的费用。
由于资本难点(预算都花在粒子对撞机上了),SEOdysseyN 总部的工程师希望知道,
达到目的的纤维开销是不怎么。

【输入格式】多组数据,文件以 2 个 0 结尾。 每组数据第2行,2个整数
N,表示有 N 个包含总部的部门(从 0 初始编号)。 然后是多少个整数 M,表示有
M 条单向通信线路。 接下来 M 行,每行多个整数,Xi,Yi,Ci,表示第 i 条线路从
Xi 连向 Yi,开支 为 Ci。

【输出格式】 每组数据一行,一个平头表示达到目标的蝇头开支。

【数据范围】对于 百分之十的多少, 有限支撑 M=N-1 对于另 三成的多寡,N ≤ 20 ,M ≤
20 对于 百分之百的数量,N ≤ 肆仟0 , M ≤ 10^5 ,Ci ≤ 10^5 ,数据组数 ≤ 5
数据保障一定可以将音讯传递到具有部门。

Tarjan_mod或者Kosaraju_mod都能过,裸的强连通分量。

1:Kosaraju

#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxm 100010
#define maxn 50010
#define inf 1<<29
int belong[maxn],head[maxn],head2[maxn],vis[maxn],dfn[maxn],dis[maxn];
int ecnt,cnt,sum,n,m,ans;
using namespace std;
struct edge{
    int u,v,next,w;
}E[maxm],Ee[maxm];
void addedge(int u,int v,int w)
{
    E[++ecnt].u=u;
    E[ecnt].v=v;
    E[ecnt].w=w;
    E[ecnt].next=head[u];
    head[u]=ecnt;
    Ee[ecnt].u=v;
    Ee[ecnt].v=u;
    Ee[ecnt].w=w;
    Ee[ecnt].next=head2[v];
    head2[v]=ecnt;
}
void dfs(int x)
{
    for(int i = head[x] ; i ; i = E[i].next)
    {
        int v=E[i].v;
        if(!vis[v])
        {
            vis[v]=1;
            dfs(v);
        }
    }
    dfn[++cnt]=x;
    return ;
}
void search(int x)
{
    for(int i = head2[x] ; i ; i = Ee[i].next)
    {
        int v=Ee[i].v;
        if(!belong[v])
        {
            belong[v]=sum;
            search(v);
        }
    }
    return ;
}
void kasa()
{
    cnt=0;
    for(int i = 1 ; i <= n ; ++i)
        if(!vis[i])
        {    
            vis[i]=1;
            dfs(i);
        }
    for(int i = cnt ; i >= 1 ; --i)
    {
        int x=dfn[i];
        if(!belong[x])
        {
            belong[x]=++sum;
            search(x);
        }
    }
}
void init()
{
    ecnt=cnt=sum=ans=0;
    memset(vis,0,sizeof(vis));
    memset(dfn,0,sizeof(dfn));
    memset(belong,0,sizeof(belong));
    memset(head,0,sizeof(head));
    memset(head2,0,sizeof(head2));
    for(int i = 1 ; i <= maxn ;  ++i)dis[i]=inf;
}
int main()
{
    int a,b,w;
    while(scanf("%d%d",&n,&m)&&n&&m)
    {
        init();
        for(int i = 1 ; i <= m ; ++i)
        {
            scanf("%d%d%d",&a,&b,&w);
            addedge(a+1,b+1,w);
        }
        kasa();
        for(int i = 1 ; i <= m ; ++i)
        {
            for(int j = head[i] ; j ; j = E[j].next)
            {
                int u=E[j].u;
                int v=E[j].v;
                int w=E[j].w;
                if(belong[u]!=belong[v])dis[belong[v]]=min(dis[belong[v]],w);
            }
        }
        for(int i = 1 ; i <= sum ; ++i)
            {
                if(dis[i]==inf)dis[i]=0;
                ans+=dis[i];
            }
        printf("%d\n",ans);
    }
    return 0;
}

2、Tarjan

#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 100010
#define maxm 50010
#define inf 1<<29
using namespace std;
int instack[maxm],stack[maxm],belong[maxm],dfn[maxm],low[maxm],head[maxm],dis[maxm];
int ecnt,cnt,ans,ord,top;
struct edge{
    int u,v,next,w;
}E[maxn];
void addedge(int u,int v,int w)
{
    E[++ecnt].u=u;
    E[ecnt].v=v;
    E[ecnt].w=w;
    E[ecnt].next=head[u];
    head[u]=ecnt;
}
void Tarjan(int x)
{
    dfn[x]=low[x]=++ord;
    stack[++top]=x;
    instack[x]=1;
    for(int i = head[x] ; i ; i = E[i].next)
    {
        int v=E[i].v;
        if(!dfn[v])Tarjan(v);
        if(instack[v])low[x]=min(low[v],low[x]);
    }
    if(dfn[x]==low[x])
    {
        ++cnt;
        int v;
        do{
            v=stack[top--];
            instack[v]=0;
            belong[v]=cnt;
        }while(x!=v);
    }
}
void init()
{
    top=ecnt=cnt=ans=ord=0;
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(E,0,sizeof(E));
    memset(belong,0,sizeof(belong));
    memset(head,0,sizeof(head));
    memset(instack,0,sizeof(instack));
    memset(stack,0,sizeof(stack));
    for(int i = 1 ; i <= maxm ; ++i)dis[i]=inf;
}
int main()
{
    int n,m,a,b,w;
    while(scanf("%d%d",&n,&m)&&n&&m)
    {
        init();
        for(int i = 1 ; i <= m ; ++i)
        {
            scanf("%d%d%d",&a,&b,&w);
            addedge(a+1,b+1,w);
        }    
        for(int i = 1 ; i <= n ; ++i)
            if(!dfn[i])Tarjan(i);
        for(int i = 1 ; i <= n ; ++i)
            for(int j = head[i] ; j ; j = E[j].next)
                {
                    int v=E[j].v;
                    int w=E[j].w;
                    if(belong[i]!=belong[v])dis[belong[v]]=min(dis[belong[v]],w);
                }
        for(int i = 1 ; i <= cnt ; ++i)
        {
            if(dis[i]==inf)dis[i]=0;
            ans+=dis[i];
        }
        printf("%d\n",ans);
    }
    return 0;
}

3.label (label.cpp/c/pas)

【难题讲述】
Samjia和Peter不一致,他欣赏玩树。所以Peter送给她一颗大小为n的树,节
点编号从1到n。
Samjia要给树上的每一个节点赋壹个[1,m]时期的权值,并使得有边直接相
连的多个节点的权值之差的断然值 ≥ k。请您告知Samjia有微微种区其他赋值
方案,只用求出答案对10 9+7(一千000007)取模得到的结果。

【输入格式】 输入文件名为 label.in。 输入数据的首先行包含二个整数
T,代表测试数据组数。 接下来是 T 组数据. 每组数据的第②行包括多少个整数
n、m 和 k。 接下来 n − 1 行,每行包罗多个整数 u 和 v, 代表节点 u 和 v
之间有 一条树边。

【输出格式】 输出文件名为 label.out。
对于每组数据,输出一行,包罗二个平头,代表所求的答案。

树形DP(mmp…)

 

评释写在代码里

#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define maxn 105
#define maxm 10005
#define mod 1000000007
using namespace std;
int f[maxn][maxm];
int T,n,m,k,lim,ecnt;
int head[maxn];
struct edge{
    int u,v,next;
}E[maxn<<1];
void addedge(int u,int v)//邻接表
{
    E[++ecnt].u=u;
    E[ecnt].v=v;
    E[ecnt].next=head[u];
    head[u]=ecnt;
}
ll getsum(int x,int from)
{
    ll ret(0);
    for(int i = from;i <= lim ; ++i)ret=(ret+f[x][i]%mod)%mod;遍历dp左端情况
    for(int i = m ; i >= m-lim+1 ; --i)//遍历dp右端情况
    {
        if(i<=lim||i<from)break;//防止i左移超出dp右端范围
        ret=(ret+f[x][m-i+1]%mod)%mod;//加上右端对应的dp左端值
    }
    int l=max(from,lim+1),r=m-lim;//max是为了处理from大于lim+1的情况
    int flg=r-l+1;
    if(flg>0)ret=(ret+1ll*flg*f[x][lim]%mod)%mod;//中间所有值相同,存在lim里即可
    return ret;
}
void dfs(int u,int fa)
{
    for(int i = 1 ; i <= lim ; ++i)f[u][i]=1;
    for(int i = head[u] ; i ; i = E[i].next)
    {
        int v= E[i].v;
        if(v==fa)continue;
        dfs(v,u);//建树
        ll sum=getsum(v,k+1);//对于父亲节点选1的情况进行初始化,通过右移过程中减去右端的值,增加左端的值实现动态变化。
        for(int j = 1 ; j <= lim ; ++j)
        {
            if(j-k>=1)sum=(sum+f[v][j-k]%mod)%mod;//加上新加入的左端值
            f[u][j]=1ll*sum*f[u][j]%mod;//乘法原理
            if(j+k<=m)//右端不出界
            {
                int bb=j+k;
                if(m-bb+1<=lim)bb=m-bb+1;//右端对应到lim左边,把右端对应到左端对称位置。
                else if(bb>=lim)bb=lim;右端对应到lim右边,把右端转移至lim位置
                sum=(sum-f[v][bb]+mod)%mod;//减去右边进入k范围内的值
            }
        }
    }
}
int ksm(int x,int y)
{
    int a=x%mod;
    int ret(1);
    while(y)
    {
        if(y&1)ret=1ll*ret*a%mod;
        y>>=1;
        a=1ll*a*a%mod;
    }
    return ret;
}
int main()
{
    int a,b;
    scanf("%d",&T);
    while(T--)
    {
        ecnt=0;
        memset(head,0,sizeof(head));
        scanf("%d%d%d",&n,&m,&k);
        for(int i = 1 ; i < n ; ++i)
        {
            scanf("%d%d",&a,&b);
            addedge(a,b);
            addedge(b,a);
        }
        if(!k)//如果K为0,计算m^n即可
        {
            printf("%d\n",ksm(m,n));
            continue;
        }
        lim=min(10000,m);//推导在下面
        dfs(1,0);
        printf("%I64d\n",getsum(1,1));
    }
    return 0;
}

lim的推导:

依傍样例

Dp[3][1]=dp[3][2]=……=dp[3][5588葡京线路,10]=1

Dp[2][1]=dp[2][10]=8

Dp[2][2]=dp[2][3]=……=dp[2][9]=7

Dp[1][1]=dp[1][10]=57

Dp[1][2]=dp[1][9]=50

Dp[1][3]=dp[1][4]=……=dp[1][8]=51

同2个点的 dp 值是对称的。 中间有一段的值是一致的。

树的最大深度n-1=99

因为k<=100所以某一端不相同的值最多有9900个,简记成10000。

一体化思路就是把f[v][i]中的左端实化,右端虚化,在做右端时经过左端对应地方来更新,然后把高中级相同部分一并处理。