5.30模拟赛-白红宇

5.30模拟赛

阅读量：5357 次

发布时间：2019-06-15

本文共 5560 字，大约阅读时间需要 18 分钟。

　　5.30了我...我不知道我究竟该干什么。考试一塌糊涂我只是不想思考么我想并不是我只是缺乏一些品质罢了吧，只会刷题算什么我要做考试的王者。

今天的失败是下次我的蜕变！我瞧不起那些弱的人。

我的妈妈和爸爸以及姐姐对我很好我有什么理由再去胆怯。

我的爷爷和奶奶都等着我去上一个好大学，我有什么理由丧失斗志。

我的自己还有很多能力，我有什么理由不去奋斗。

今天是数论专题尽管是这样我也是近乎倒数，我这是怎么回事明明有能力却发现不出题目的性质，原因？用心啊。

首先N==1 时我们很显然的发现了答案应该是5吧。。这个样例使我爆零了，我算服了。

以后注意想不出来样例就一直想想不出正解很正常。样例是我和石神探讨下的得出的结论是这样的图：

观察中间的两条边发现我们看成重叠的但是却是有两条这样的边。

首先把中间的边删掉然后这样的生成树有8种。然后对半删也就是中间仍有连线这样方案数是16种 4*4 然后删掉中间的一条边

知道要说什么了吧下次我们删掉中间的另外一条边 16 刚好答案为40.

实话这道题没有样例解释且题目描述不清晰生成树不同在此题的定义是指什么我怎么知道？所以我爆零了感觉很不错！不是我不会是这道题出的不好。

我不怪我自己。现在分析一下这道题怎么写 30分好像是可以爆搜的但是及其难写 50分矩阵树定理回去我补一下这个知识点。

100分是找到规律我是这样找规律的利用样例的方法寻找到规律：

1 把中间形成的环这个环全部删掉那么有4n种方案。

2 对于所有的五边形显然我都是要删其中的一条边的那么此时就是5^n 然后显然的发现必然还会存在一个环那么对于再删一条边即可。

对于一个五边形我们让其再删一条边，那么就是5^(n-1)* 最后一个删去两条边一条是中间环上的显然！一条是自己边上的显然！

那么方案数是4n 总答案是4n*5^(n-1) 值得一提的是这个和n==2时不冲突。再值得一提的是这个和1是冲突的想一下5^(n-1)显然有可能出现1中情况所以容斥一下就是-4n

答案如旧。

//#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      #include
                       
                        #include
                        
                         #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 10000000000#define mod 2007#define ll long longusing namespace std;char buf[1<<15],*fs,*ft;inline char getc(){ return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}inline int read(){ int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f;}inline void put(int x){ x<0?putchar('-'),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar('\n');return;}const int MAXN=1010;int n,T;ll ans;//4n*5^(n-1)inline void fast_pow(ll b,ll p){ ans=1; while(p) { if(p&1)ans=(ans*b)%mod; p=p>>1; b=(b*b)%mod; } return;}int main(){ //freopen("1.in","r",stdin); T=read(); while(T--) { n=read(); fast_pow(5,n-1); put((4*((n*ans)%mod))%mod); } return 0;}

View Code

仔细观察这题是个dp 发现还比较好写60分观察一下就有了我不知怎么了搞了1h多。

//#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      #include
                       
                        #include
                        
                         #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 10000000000#define mod 998244353using namespace std;char buf[1<<15],*fs,*ft;inline char getc(){ return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}inline int read(){ int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f;}inline void put(int x){ x<0?putchar('-'),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar('\n');return;}const int MAXN=1010;int n,m,k;int f[MAXN][MAXN];//如题 想让我求出一个倒三角的方案数 且多加了一条线。//讨论 如果 y=x-b 显然是没有卵用的 只有y=x+b才会有点用//y=x-(n-m); y=x-n+m m-n<0 显然b<0显然 这条线都没用//y=x+(n-m) 上面还有一条线我的妈呀。。int main(){ //freopen("1.in","r",stdin); freopen("path.in","r",stdin); freopen("path.out","w",stdout); n=read();m=read(); f[0][0]=1;k=n-m; for(int i=0;i<=n;++i) for(int j=max(0,i-k);j<=i&&j<=m;++j) { if(i-1>=0)f[i][j]=(f[i][j]+f[i-1][j])%mod; if(j-1>=0)f[i][j]=(f[i][j]+f[i][j-1])%mod; } /*for(int i=0;i<=n;++i) { for(int j=0;j<=i&&j<=m;++j) { cout<
                         
                          <<' '; } cout<

100分的话是一个组合数问题现在还不太会以后补坑。

dp 写的话只有60分，眼界放宽点就是一个组合数了，额不会。C(n+m,m)表示从0,0走到n,m的方案数还有一些其他的东西。。

看不懂QAQ。。。

这道题就比较有意思了我就讨厌这种数数题了，我不会数数。正解是发现这是一个标准的左偏树小根堆。

可以证明的是的确是这样的，不必要去刻意的放上某个数字因为每一个数字都有自己要放的范围，这形成了一个递归的子问题，或者说形成了dp的子状态。

设 f[i] 表示i个数字可以以小根堆左偏树的形式放的方案数，显然的是 f[i]=C(i-1,l)*f[l]*f[r]; l是当前左子树大小随着i确定而确定。

还是很显然的就是我们选出一些数字去填左边乘上左右两边的方案数即可。很经典的题目。

这里求子树大小我采用O(n)2次幂直接慢慢求，至于组合数lucas定理即可。

//#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      #include
                       
                        #include
                        
                         #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 10000000000#define mod 998244353#define ll long longusing namespace std;char buf[1<<15],*fs,*ft;inline char getc(){ return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}inline int read(){ int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f;}inline void put(int x){ x<0?putchar('-'),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar('\n');return;}const int MAXN=1000010;int n,p,s,l,r,res,last,cnt;ll f[MAXN],fac[MAXN];//f[i]表示i个数字所满足小根堆性质的方案数//一个看起来非常显然的转移f[i]=f[l]*f[r]*C(i-1,l);ll inv[MAXN],sz[MAXN];//inverse 相反的 element 要素inline int fast_pow(ll b,int k){ ll tmp=1; while(k) { if(k&1)tmp=tmp*b%p; k=k>>1; b=b*b%p; } return tmp;}inline ll lucas(int a,int b){ if(b>a)return 0; if(a
                         
                          =0;--i)inv[i]=inv[i+1]*(i+1)%p; //for(int i=1;i<=s;++i)cout<
                          
                           <<' '; for(int i=2;i<=n;++i) { --res; sz[i]=(res
                           
                            >1,last=last<<1,res=last; } //for(int i=2;i<=n;++i)put(sz[i]); for(int i=2;i<=n;++i)f[i]=(lucas(i-1,sz[i])*f[sz[i]])%p*f[i-1-sz[i]]%p; //for(int i=1;i<=n;++i)cout<
                            
                             <<' '; put(f[n]); return 0;}

View Code

心态崩了！

转载于:https://www.cnblogs.com/chdy/p/10957109.html

你可能感兴趣的文章