2016.10.30 NOIP模拟赛 day2 AM 整理-白红宇

2016.10.30 NOIP模拟赛 day2 AM 整理

阅读量：4983 次

发布时间：2019-06-12

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

题目+数据：链接：密码：ho7o

总共得了：130分，

1：100分 2:30分（只会这30分的暴力） 3：0（毫无思路）

虽然不高，但是比较满意，因为把自己会的分数都拿到了。

T1：100分

1 /*  2 T1明显是个数论题。  3 正确的思路：把n!质因数分解，把所有质因数的指数都取到最大的偶数，它们的乘积便是最终的结果。  4 有一种很快的方法在Eular筛中可以n!的质因数分解。  5 if(!is_prim[i])  6 {  7     prim[++prim[0]]=i;  8     ll x=n;  9     while(x) 10     { 11         cs[prim[0]]+=x/prim[prim[0]]; 12         x/=prim[prim[0]]; 13     } 14 } 15 具体的可以用“抽数法（反正我这么叫它）”来证明。 16  17 */ 18 #define N 5000010 19 #include
     
       20 using namespace std; 21 #include
      
        22 #define Mod 100000007 23 typedef long long ll; 24 ll prim[N]={
   0}; 25 int cs[N]={
   0}; 26 bool is_prim[N]; 27 int n; 28 void eular() 29 { 30     for(ll i=2;i<=n;++i) 31     { 32         if(!is_prim[i]) 33         { 34             prim[++prim[0]]=i; 35             ll x=n; 36             while(x) 37             { 38                 cs[prim[0]]+=x/prim[prim[0]]; 39                 x/=prim[prim[0]]; 40         } 41     } 42     for(int j=1;j<=prim[0];++j) 43     { 44             if(i*prim[j]>n) break; 45             is_prim[i*prim[j]]=true; 46             if(i%prim[j]==0) break; 47     } 48     } 49 /*    for(int i=1;i<=prim[0];++i) 50       printf("%d\n",prim[i]);*/ 51 } 52 void fj() 53 { 54     for(ll i=2;i<=n;++i) 55     { 56         ll x=i; 57         while(x!=1) 58         { 59             for(int j=1;j<=prim[0];++j) 60             { 61                 if(x%prim[j]==0) 62                 { 63                     cs[j]++; 64                     x/=prim[j]; 65                     break; 66                 } 67             } 68         } 69     } 70 } 71 ll quick_mod(ll a,ll b)//a^b 72 { 73     ll ret=1; 74     while(b) 75     { 76         if(b&1) 77         { 78             ret=(ret*a)%Mod; 79         } 80         b>>=1; 81         a=(a*a)%Mod; 82     } 83     return ret; 84 } 85 int main() 86 { 87     freopen("hao.in","r",stdin); 88     freopen("hao.out","w",stdout); 89     scanf("%d",&n); 90     eular(); 91 //  fj();这是没用这个优化的部分，只能得50分。 92     ll ans=1; 93     for(int i=1;i<=prim[0];++i) 94     { 95         if(cs[i]%2==0) 96         { 97             ans=(ans*quick_mod(prim[i],cs[i]))%Mod; 98         } 99         else{100             ans=(ans*quick_mod(prim[i],cs[i]-1))%Mod;101         }102     }103     cout<
       
        <

T2：

/*这道题目内部的转化非常巧妙，

首先[l,r]->[0,r]-[0,l-1]

现在只讨论r

Σxi/m -r<=0 --> ∑(xi-r)/m<=0 ==>∑(xi-m)<=0：

题目==>询问有多少区间和小于等于0

做一个前缀和S，现有[a,b] 要满足 s[b]-s[a]<=0 ：

询问有多少对a,b使s[b]<=s[a] --> 求逆序对

注意这道题目的转换，十分的巧妙。

--------*****------

另外求逆序对有两种方法：归并排序或者树状数组，第二种请自行百度。

1 #include
     
        2 using namespace std;  3 #include
      
         4 #define N 500010  5 typedef long long ll;  6 ll a[N],sum[N],zc[N];  7 int n,r,l;  8 ll read()  9 { 10     ll ret=0,ff=1; 11     char s=getchar(); 12     while(s<'0'||s>'9') 13     { 14         if(s=='-') ff=-1; 15         s=getchar(); 16     } 17     while(s>='0'&&s<='9') 18     { 19         ret=ret*10+s-'0'; 20         s=getchar(); 21     } 22     return ret*ff; 23 } 24 void gb1(int l1,int r1,ll &ans) 25 { 26     if(l1==r1) return; 27     int mid=(l1+r1)>>1; 28     gb1(l1,mid,ans); 29     gb1(mid+1,r1,ans); 30     int s=l1,i=l1,j=mid+1; 31     while(i<=mid&&j<=r1) 32     { 33         if(sum[i]>=sum[j]) 34         { 35             zc[s]=sum[j]; 36             ans+=mid-i+1; 37             s++;j++; 38         } 39         else{ 40             zc[s]=sum[i]; 41             i++;s++; 42         } 43     } 44     while(i<=mid) 45     { 46         zc[s]=sum[i]; 47         i++;s++; 48     } 49     while(j<=r1) 50     { 51         zc[s]=sum[j]; 52         s++;j++; 53     } 54     for(int i=l1;i<=r1;++i) 55        sum[i]=zc[i]; 56 } 57 void gb2(int l1,int r1,ll &ans) 58 { 59     if(l1==r1) return ; 60     int mid=(l1+r1)>>1; 61     gb2(l1,mid,ans); 62     gb2(mid+1,r1,ans); 63     int i=l1,s=l1,j=mid+1; 64     while(i<=mid&&j<=r1) 65     { 66         if(sum[i]>sum[j]) 67         { 68             ans-=(mid-i+1); 69             zc[s]=sum[j]; 70             s++;j++; 71         } 72         else{ 73             zc[s]=sum[i]; 74             i++;s++; 75         } 76     } 77     while(i<=mid) 78     { 79         zc[s]=sum[i]; 80         i++;s++; 81     } 82     while(j<=r1) 83     { 84         zc[s]=sum[j]; 85         j++;s++; 86     } 87     for(int i=l1;i<=r1;++i) 88         sum[i]=zc[i]; 89 } 90 void gcd(ll a,ll b,ll &gc) 91 { 92     if(!b) 93     { 94         gc=a; 95         return; 96     } 97     gcd(b,a%b,gc); 98 } 99 int main()100 {101     freopen("jian.in","r",stdin);102     freopen("jian.out","w",stdout);103     scanf("%d%d%d",&n,&l,&r);104     for(int i=1;i<=n;++i)105       a[i]=read();106     ll ans=0;107     sum[0]=0;108     for(int i=1;i<=n;++i)109       sum[i]=a[i]-r;110     for(int i=1;i<=n;++i)111       sum[i]+=sum[i-1];112     gb1(0,n,ans);113     sum[0]=0;114     for(int i=1;i<=n;++i)115       sum[i]=a[i]-l;116     for(int i=1;i<=n;++i)117       sum[i]+=sum[i-1];118     gb2(0,n,ans);119     ll mu=(ll)(n+1)*n/2;/*一定要注意这个小细节，赋值时最大就是int，超过int，即使是给long long 赋值，也会炸数据类型*/120     ll gc;121     gcd(ans,mu,gc);122     ans/=gc;mu/=gc;123     if(mu==1) printf("1");124     else cout<
       
        <<"/"<

T3:

考试时蒙蔽到连10%的数据都不会处理了。╮(╯▽╰)╭

1 /* 2 这道题目直接用dfs可以，也可以如下的先用dp处理一部分点。 3 但是都要用到状态压缩。 4 其实，这一点我们是应该想到的，每个栅栏内放哪几个葱是很重要的而且n<=16，我们应该想到用状压的。  5 */ 6 #include
     
       7 #include
      
        8 #include
       
         9 #include
        
         10 11 using namespace std;12 13 int m,k,n,x[20],y[20],f[17][1<<16],cost[1<<16],s[20],ans;14 15 void dfs(int now,int cnt,int res)/*res当前所用的栅栏长度，now当前处理第几根葱，cnt已用栅栏的数目*/16 {17     if (now==n)18     {19         if (res
         
          =ans) return;/*最优性剪枝，当前所用栅栏的数目+几乎最少的长度>=ans就剪枝*/23     /*对于当前这个葱，只有放入之前的栅栏和新建一个栅栏两种方案*/24     for (int a=1;a<=cnt;a++)/*枚举已用的栅栏*/25     {26         int pres=s[a];/*取出这个栅栏的放的葱的情况*/27         s[a]|=(1<
          
           >b)&1)55 {56 if (x[b]
           
            mx) mx=x[b];58 if (y[b]
            
             my) my=y[b];/*计算这个栅栏的最小大小*/60 }61 f[1][a]=(mx-sx+1)*2+(my-sy+1)*2;62 }63 for (int a=2;a<=k;a++)/*枚举k个栅栏*/64 for (int b=0;b<(1<
             
              14会有超时*/73 {74 ans=4000;75 for (int a=1;a<(1<
              
               >b)&1)80 {81 if (x[b]
               
                mx) mx=x[b];83 if (y[b]
                
                 my) my=y[b];85 }86 cost[a]=(mx-sx+1)*2+(my-sy+1)*2;/*一个栅栏的情况*/87 }88 dfs(0,0,0);89 printf("%d\n",ans);90 }91 92 return 0;93 }

我的：

1 #define M 1010 2 #include
     
       3 using namespace std; 4 #include
      
        5 #define N 17 6 int n,m,k; 7 struct Pos{ 8     int x,y; 9 }pos[N];10 int val[1<
       
        =ans) return;43     for(int i=1;i<=cnt;++i)44     {45         int x=zha[i];46         zha[i]|=(1<