2016.10.30 NOIP模拟赛 day2 AM 整理

题目+数据：链接：http://pan.baidu.com/s/1gfBg4h1 密码：ho7o

总共得了：130分，

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

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

T1：100分

 /*
 T1明显是个数论题。
 正确的思路：把n!质因数分解，把所有质因数的指数都取到最大的偶数，它们的乘积便是最终的结果。
 有一种很快的方法在Eular筛中可以n!的质因数分解。
 if(!is_prim[i])
 {
     prim[++prim[0]]=i;
     ll x=n;
     while(x)
     {
         cs[prim[0]]+=x/prim[prim[0]];
         x/=prim[prim[0]];
     }
 }
 具体的可以用“抽数法（反正我这么叫它）”来证明。

 */
 #define N 5000010
 #include<iostream>
 using namespace std;
 #include<cstdio>
 #define Mod 100000007
 typedef long long ll;
 ll prim[N]={};
 int cs[N]={};
 bool is_prim[N];
 int n;
 void eular()
 {
     for(ll i=;i<=n;++i)
     {
         if(!is_prim[i])
         {
             prim[++prim[]]=i;
             ll x=n;
             while(x)
             {
                 cs[prim[]]+=x/prim[prim[]];
                 x/=prim[prim[]];
         }
     }
     for(int j=;j<=prim[];++j)
     {
             if(i*prim[j]>n) break;
             is_prim[i*prim[j]]=true;
             if(i%prim[j]==) break;
     }
     }
 /*    for(int i=1;i<=prim[0];++i)
       printf("%d\n",prim[i]);*/
 }
 void fj()
 {
     for(ll i=;i<=n;++i)
     {
         ll x=i;
         while(x!=)
         {
             for(int j=;j<=prim[];++j)
             {
                 if(x%prim[j]==)
                 {
                     cs[j]++;
                     x/=prim[j];
                     break;
                 }
             }
         }
     }
 }
 ll quick_mod(ll a,ll b)//a^b
 {
     ll ret=;
     while(b)
     {
         if(b&)
         {
             ret=(ret*a)%Mod;
         }
         b>>=;
         a=(a*a)%Mod;
     }
     return ret;
 }
 int main()
 {
     freopen("hao.in","r",stdin);
     freopen("hao.out","w",stdout);
     scanf("%d",&n);
     eular();
 //  fj();这是没用这个优化的部分，只能得50分。
     ll ans=;
     for(int i=;i<=prim[];++i)
     {
         if(cs[i]%==)
         {
             ans=(ans*quick_mod(prim[i],cs[i]))%Mod;
         }
         else{
             ans=(ans*quick_mod(prim[i],cs[i]-))%Mod;
         }
     }
     cout<<ans%Mod<<endl;
     fclose(stdin);
     fclose(stdout);
     return ;
 }

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] --> 求逆序对
注意这道题目的转换，十分的巧妙。
--------*****------
另外求逆序对有两种方法：归并排序或者树状数组，第二种请自行百度。
*/

 #include<iostream>
 using namespace std;
 #include<cstdio>
 #define N 500010
 typedef long long ll;
 ll a[N],sum[N],zc[N];
 int n,r,l;
 ll read()
 {
     ll ret=,ff=;
     char s=getchar();
     while(s<''||s>'')
     {
         if(s=='-') ff=-;
         s=getchar();
     }
     while(s>=''&&s<='')
     {
         ret=ret*+s-'';
         s=getchar();
     }
     return ret*ff;
 }
 void gb1(int l1,int r1,ll &ans)
 {
     if(l1==r1) return;
     int mid=(l1+r1)>>;
     gb1(l1,mid,ans);
     gb1(mid+,r1,ans);
     int s=l1,i=l1,j=mid+;
     while(i<=mid&&j<=r1)
     {
         if(sum[i]>=sum[j])
         {
             zc[s]=sum[j];
             ans+=mid-i+;
             s++;j++;
         }
         else{
             zc[s]=sum[i];
             i++;s++;
         }
     }
     while(i<=mid)
     {
         zc[s]=sum[i];
         i++;s++;
     }
     while(j<=r1)
     {
         zc[s]=sum[j];
         s++;j++;
     }
     for(int i=l1;i<=r1;++i)
        sum[i]=zc[i];
 }
 void gb2(int l1,int r1,ll &ans)
 {
     if(l1==r1) return ;
     int mid=(l1+r1)>>;
     gb2(l1,mid,ans);
     gb2(mid+,r1,ans);
     int i=l1,s=l1,j=mid+;
     while(i<=mid&&j<=r1)
     {
         if(sum[i]>sum[j])
         {
             ans-=(mid-i+);
             zc[s]=sum[j];
             s++;j++;
         }
         else{
             zc[s]=sum[i];
             i++;s++;
         }
     }
     while(i<=mid)
     {
         zc[s]=sum[i];
         i++;s++;
     }
     while(j<=r1)
     {
         zc[s]=sum[j];
         j++;s++;
     }
     for(int i=l1;i<=r1;++i)
         sum[i]=zc[i];
 }
 void gcd(ll a,ll b,ll &gc)
 {
     if(!b)
     {
         gc=a;
         return;
     }
     gcd(b,a%b,gc);
 }
 int main()
 {
     freopen("jian.in","r",stdin);
     freopen("jian.out","w",stdout);
     scanf("%d%d%d",&n,&l,&r);
     for(int i=;i<=n;++i)
       a[i]=read();
     ll ans=;
     sum[]=;
     for(int i=;i<=n;++i)
       sum[i]=a[i]-r;
     for(int i=;i<=n;++i)
       sum[i]+=sum[i-];
     gb1(,n,ans);
     sum[]=;
     for(int i=;i<=n;++i)
       sum[i]=a[i]-l;
     for(int i=;i<=n;++i)
       sum[i]+=sum[i-];
     gb2(,n,ans);
     ll mu=(ll)(n+)*n/;/*一定要注意这个小细节，赋值时最大就是int，超过int，即使是给long long 赋值，也会炸数据类型*/
     ll gc;
     gcd(ans,mu,gc);
     ans/=gc;mu/=gc;
     if(mu==) printf("");
     else cout<<ans<<"/"<<mu;
     fclose(stdin);
     fclose(stdout);
     return ;
 }

T3:

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

 /*
 这道题目直接用dfs可以，也可以如下的先用dp处理一部分点。
 但是都要用到状态压缩。
 其实，这一点我们是应该想到的，每个栅栏内放哪几个葱是很重要的而且n<=16，我们应该想到用状压的。
 */
 #include<cstdio>
 #include<cstdlib>
 #include<cstring>
 #include<algorithm>

 using namespace std;

 int m,k,n,x[],y[],f[][<<],cost[<<],s[],ans;

 void dfs(int now,int cnt,int res)/*res当前所用的栅栏长度，now当前处理第几根葱，cnt已用栅栏的数目*/
 {
     if (now==n)
     {
         if (res<ans) ans=res;
         return;
     }
     if (res+(k-cnt)*>=ans) return;/*最优性剪枝，当前所用栅栏的数目+几乎最少的长度>=ans就剪枝*/
     /*对于当前这个葱，只有放入之前的栅栏和新建一个栅栏两种方案*/
     for (int a=;a<=cnt;a++)/*枚举已用的栅栏*/
     {
         int pres=s[a];/*取出这个栅栏的放的葱的情况*/
         s[a]|=(<<now);/*把这个葱放进去，再进行下一步搜索*/
         dfs(now+,cnt,res-cost[pres]+cost[s[a]]);
         s[a]^=(<<now);/*把这个葱取出来，回溯*/
     }
     if (cnt<k)
     {
         cnt++;/*新建一个栅栏，把葱放进去*/
         s[cnt]=(<<now);
         dfs(now+,cnt,res+);
     }
 }

 int main()
 {
     freopen("dan.in","r",stdin);
     freopen("dan.out","w",stdout);

     scanf("%d%d%d",&m,&k,&n);
     for (int a=;a<n;a++)
         scanf("%d%d",&x[a],&y[a]);
     if (n<=)
     {
         memset(f,0x3f,sizeof(f));
         for (int a=;a<(<<n);a++)/*状态压缩，把葱在一个栅栏中的所有情况都枚举了出来*/
         {
             int sx=,mx=-,sy=,my=-;
             for (int b=;b<n;b++)
                 if ((a>>b)&)
                 {
                     if (x[b]<sx) sx=x[b];
                     if (x[b]>mx) mx=x[b];
                     if (y[b]<sy) sy=y[b];
                     if (y[b]>my) my=y[b];/*计算这个栅栏的最小大小*/
                 }
             f[][a]=(mx-sx+)*+(my-sy+)*;
         }
         for (int a=;a<=k;a++)/*枚举k个栅栏*/
             for (int b=;b<(<<n);b++)/*枚举b个葱组成集合的1<<n中放置方法*/
                 for (int c=b-;c;c=(c-)&b)/*这是一种状态压缩枚举b集合中的所有子集的方法，c=b-1,就可以表示所有的元素都在集合中，每次-1，可以枚举出1<<b的所有情况*/
                     f[a][b]=min(f[a][b],f[a-][c]+f[][b^c]);/*枚举出任意子集c,b^c是c在b中的补集，c与b按位如果都有1或0，则他们的子集中都没有。*/
         int ans=f[][(<<n)-];/*这是一个栅栏n个葱都放入的结果*/
         for (int a=;a<=k;a++)
             ans=min(ans,f[a][(<<n)-]);
         printf("%d\n",ans);
     }
     else/*如果不这样特判的话，n>14会有超时*/
     {
         ans=;
         for (int a=;a<(<<n);a++)
         {
             int sx=,mx=-,sy=,my=-;
             for (int b=;b<n;b++)
                 if ((a>>b)&)
                 {
                     if (x[b]<sx) sx=x[b];
                     if (x[b]>mx) mx=x[b];
                     if (y[b]<sy) sy=y[b];
                     if (y[b]>my) my=y[b];
                 }
             cost[a]=(mx-sx+)*+(my-sy+)*;/*一个栅栏的情况*/
         }
         dfs(,,);
         printf("%d\n",ans);
     }

     return ;
 }

我的：

 #define M 1010
 #include<iostream>
 using namespace std;
 #include<cstdio>
 #define N 17
 int n,m,k;
 struct Pos{
     int x,y;
 }pos[N];
 int val[<<N],ans,zha[N+];
 void input()
 {
     scanf("%d%d%d",&m,&k,&n);
     for(int i=;i<n;++i)
         scanf("%d%d",&pos[i].x,&pos[i].y);
 }
 void pre_chuli()
 {
     for(int i=;i<(<<n);++i)
     {
         int dx=-,dy=-,xx=,xy=;
         for(int j=;j<n;++j)
         {
             if((<<j)&i)
             {
                 dx=max(dx,pos[j].x);
                 dy=max(dy,pos[j].y);
                 xy=min(xy,pos[j].y);
                 xx=min(xx,pos[j].x);
             }
         }
         val[i]=(dy-xy+)*+(dx-xx+)*;
     }
 }
 void dfs(int now,int cnt,int cos)
 {
     if(now==n)
     {
         ans=min(cos,ans);
         return;
      }
     if(cos+(k-cnt)*>=ans) return;
     for(int i=;i<=cnt;++i)
     {
         int x=zha[i];
         zha[i]|=(<<now);
         dfs(now+,cnt,cos-val[x]+val[zha[i]]);
         zha[i]^=(<<now);
     }
     if(cnt<k)
     {
         zha[cnt+]=(<<now);
         dfs(now+,cnt+,cos+);
         zha[cnt+]=;
     }
 }
 int main()
 {
     freopen("dan.in","r",stdin);
     freopen("dan.out","w",stdout);
     input();
     pre_chuli();
     ans=;
     dfs(,,);
     printf("%d\n",ans);
     fclose(stdin);
     fclose(stdout);
     return ;
 }