XXY 的 NOIP 模拟赛 2

题目		过路费				走楼梯升级版	蜂巢
						stair	beehive
英文题目与子目录名		fee
单个测试点时间限制		1秒				1秒	1秒
内存限制		128M				128M	128M
测试点数目		10				10	10
每个测试点分值		10				10	10
比较方式		全文比较（过滤行末空格及文末回车）
题目类型		传统				传统	传统

过路费

Description

这是xxy的地盘，你在任何一条道路行走都需要交过路费。

这里有n个城市和m条双向道路，每条道路连接两个城市。你从某个城市出发到达某个城市。xxy已经在每一条双向道路上设置一个过路费L。 可能有多条道路连接相同的两个城市，但是不存在一条道路连接一个城市和这个城市本身。

xxy竟然在每个城市上面也设置了一个过路费C。从一个城市到另外一个城市的费用，是经过的所有道路的过路费之和，加上经过的所有的城市（包括起点和终点）的过路费的最大值。 Xxy希望你写一个程序，接受k个问题，每次计算从s到t的最小花费。如果s到t不连通，输出-1

Input

第一行包含3个整数n，m，k

接下来n行，每行一个整数表示ci

接下来m行，每行3个整数a，b，L，表示连接a与b的双向道路的过路费为L

接下来k行，每行2个整数s，t

Output

对于每个询问，输出一行表示答案

Example

Input

5 7 2

2

5

3

3

4

1 2 3

1 3 2

2 5 3

5 3 1

5 4 1

2 4 3

3 4 4

1 4

2 3

Output

8

9

对于30%的数据 n<=20,m<=50,k<=30

对于50%的数据 n<=110,m<=1000,k<=100

对于100%的数据 N<=250,m<=10000,k,c,L<=10000

 改编自：

 

佛洛依德、、、

将点权进行排序，然后跑Floyd，我们在依次跑Floyd的时候保证k=n是的k的点权最大，也就是说这里我们在更新i到j这条路径的时候依次是使的中间节点的点权最大，这样保证中间节点的点权最大的话，我们就不用费力的去找他一条路径上的最大点权了。

 

#include
      
       #include
       
        #include
        
         #include
         
          #define N 300#define maxn 9999999using namespace std;int n,m,x,y,z,k,dy[N],dis[N][N],f[N][N];struct A{    int id,c;}a[N];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}int cmp(A a,A b){    return a.c
          
           =maxn) printf("-1\n");        else printf("%d\n",dis[x][y]);    }    return 0; }
          
         
        
       
      

 

走楼梯升级版

Description

在你成功地解决了上一道走楼梯后，xxy 不禁有些气恼，于是她又在楼梯上跳来跳去，想要你求出她跳的方案数。.. 

xxy 站在一个 tot 阶楼梯下面，他每次可以往上跳1—n步，往下跳1——m步（由于地心引力跳得比较远），而且在往下跳的时候只能踩在往上跳时踩过的格子。 

现在 xxy 在楼梯上乱跳，想问她跳到楼梯顶上最后又跳回楼梯下面的方案数 mod 233333333。

注意：xxy 只能一直向上跳，跳到楼梯最上面，然后再往下跳，跳回楼梯最底下。

Inpu 

一行3个整数 tot，n，m

Output 

方案数 % 233333333 

Example

Input

2

5 2 4

5 2 3

Output

52

42

Hint

10%的数据，1<=tot，n<=5,m=1

另外10%的数据，1<=tot,n,m<=5

另外20%的数据，1<=tot<=10000,1<=n,m<=5

另外20%的数据，1<=tot<=10000,1<=n,m<=10

另外20%的数据，1<=tot<=400000,1<=n,m<=5

对于100%的数据，1<=tot<=400000,1<=n,m<=10

 

 跟走楼梯的思路一样。

走一遍楼梯，上去以后再下来可以看为从一层到最上面一层走两遍。

我们单纯的来看走一遍楼梯的情况，我们上去可以走1~n步，下来的时候可以选择走1~m步。

那么我们上去的时候的状态转移方程是不是可以看为f[i]=f[i-1]+f[i-2]+fi-3]+……+f[i-n],下来的时候就可以看做fi]=f[i-1]+f[i-2]+fi-3]+……+f[i-m].

这个是只考虑走一遍的情况。我们现在的走楼梯是要上去以后再下来。

我们现在考虑爬上去以后再下来，那么我们就可以推出状态转移方程dp[i]=dp[i-1]*f[1]+dp[i-2]*f[2]+dp[i-3]*f[3]+……+dp[i-m]*f[m].

这个时候有人一定要问了，dp是什么？？f[]又是什么？？

dp是我们爬到当前阶层时的方案数。我们先只考虑第二遍往下跳的时候，我们的方案数，上面我们说过了，这个时候的方案数是fi]=f[i-1]+f[i-2]+fi-3]+……+f[i-m]。由于我们每次下楼的时候必须走上楼时走过的楼梯，也就是说我们要在跳下来的台阶数要被跳上过一次，例如我们现在要向下跳j步，这个时候我们跳上去的方案数就变成了f[j]=f[j-1]+f[j-2]+……+f[j-n]，这就相当于我们要跳j层台阶，一共可以走1~n步，有几种方案数。

我们在利用乘法原理+加法原理，就好了。

（加法原理，我们当前点可以有好几种走法，首先它可以从i-1跳到i,可以从i-2跳到i,也可以从i-3跳到i、、、、、这几种走法的和为总方案数。对于每一种走法，我们又要分两步，在进行乘法原理。

   乘法原理，我们要跳到当前点分两步，一步向上跳，另一步是向下跳，这两步的方案数的乘积就是总共的方案数。）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define N 410000#define mod 233333333using namespace std;long long t,tot,n,m,dp[N],f[N];long long read(){ long long x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;}int main(){ freopen("stair.in","r",stdin); freopen("stair.out","w",stdout); t=read(); while(t--) { memset(f,0,sizeof(f)); memset(dp,0,sizeof(dp)); tot=read(),n=read(),m=read(); f[0]=1; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(i-j>=0) f[i]+=f[i-j]; else break; dp[0]=1; for(int i=1;i<=tot;i++) for(int j=1;j<=m;j++) if(i-j>=0) dp[i]=(dp[i]+dp[i-j]*f[j])%mod; else break; printf("%I64d\n",dp[tot]); } return 0;}
           
          
         
        
       
      

 

蜂巢

Description

求上图两点间的最短距离

Input

输入包含多组测试数据

每组数据包含一行，每行包含两个整数a，b

Output

对于每组测试数据，输出一行，

每行三个整数 a，b，dis，表示a与b之间的最短距离为dis

Example

Input

2 35

26 14

3 7

Output

3

3

2

Hint

对于10%的数据，1<=a,b<=10,数据组数<=10

对于30%的数据，1<=a,b<=100,数据组数<=1000

对于50%的数据，1<=a,b<=1000,数据组数<=160000

对于70%的数据，1<=a,b<=10000,数据组数<=500000

对于100%的数据，1<=a，b<=100000,数据组数<=500000

 

弃疗

#include
      
       #include
       
        #include
        
         using namespace std;int dx[6]={
     0,-1,-1,0,1,1};int dy[6]={-1,-1,0,1,1,0};int s[6]={
     2,1,2,2,2,2};int x[10001],y[10001];int main(){    y[2]=-1;    x[3]=-1; y[3]=-1;    x[4]=-1;    y[5]=1;    x[6]=1; y[6]=1;    int nowd=0,nows=1,nowx=1,nowy=1;    for(int now=7;now<=10000;now++)    {        if(nows>s[nowd]) nows=1,nowd++;        if(nowd>=6)         {            nowd=0;            for(int i=0;i<6;i++) s[i]++;        }        nowx+=dx[nowd];        nowy+=dy[nowd];        x[now]=nowx;        y[now]=nowy;        nows++;    }    int a,b,aa,bb;    while(scanf("%d%d",&aa,&bb)!=EOF)    {        a=aa; b=bb;        if(!a) return 0;        if(x[a]>x[b]) swap(a,b);        if(x[a]!=x[b] && y[a]