Individual Contest #1 and Private Training #1

第一次的增补赛，也是第一场个人排位赛，讲道理打的和屎一样，手速题卡了好久还WA了好多发，难题又切不出来，这种情况是最尴尬的吧！

Individual Contest #1：

Ploblem D:

题意：给你一个含有N个元素的数组和操作次数m，然后求出经过m次操作后，从区间X到Y的总和；操作如下：{1,6,9}==>{1,7,6,15,9}（多CASE）

题目链接：https://www.codechef.com/problems/CHSPARR

思路：

首先，最容易想到的是单纯的模拟每一次这样的操作然后用数组存起来，再去算区间X到Y的总和。可是，当N和m取最大的时候，数组元素数量会达到10^15，直接GG！所以得换个套路！

对于原始数组{1,6,9}，元素对应的下标各自为1,2,3。以1,6为例，{1,6}==>{1,7,6}==>{1,8,7,13,6}==>{1,9,8,15,7,20,13,19,6}，元素6的标和m的变化为：i（0），2*i-1（1），4*i-3（2），8*i-7（3）

把两者联系起来你可以发现经过m次变换后元素6的下标为：i*2^m-(2^m-1)==>(i-1)*2^m-1。

接着继续模拟：{1，6}==>{1，7（1+6），6}==>{1，8（1，1+6），7（1+6），13（1+6，6），6}，你会发现，如果把1和6中间的所有新增加的元素看成一个整体s，那个他每一次都会

向左向右复制一遍，再加上他本身，就是3*s，同时端点处的1和6也会每一次都增加一次，如果能将s和（1+6）联系起来，那么1和6之间的元素总和不就可以直接求了吗！到这里也可以看出

来是倍数关系。设数组k表示分别经过1-m次操作后对应的系数，则k[m]=k[m-1]*3+1。这样的话如果X和Y里面有包含一个或多个完整的中间元素块，就可以直接求出来了！

那多出来的那部分怎么办呢？你会发现对于元素a(i)和元素b(j)，元素a+b一定在（i+j）/2的位置。所以直接分治，每一次都缩小规模找到完整块++，代码如下：

#include <iostream>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <map>

#include <set>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <string>

#include <sstream>

#define lson l,m,rt*2

#define rson m+1,r,rt*2+1

#define mod 1000000007

using namespace std;

typedef long long LL;

using namespace std;

LL a[],k[],n,m,x,y;

void init()

{

    k[]=;

    for(int i=;i<=;i++)

    {

        k[i]=(k[i-]*+)%mod;

    }

}

LL f(LL num)

{

    if(num==)return ;

    int i,j,mm;

    LL res=,p=<<m,q,h,mid,l,r;

    q=num/p;

    for(i=;i<=q;i++)

    {

        res=(res+(a[i]+a[i+])*k[m]+a[i])%mod;

    }

    h=num%p;

    l=a[q+];

    r=a[q+];

    mm=m;

    while(h>&&mm>)

    {

        mm--;

        mid=<<mm;

        if(h>=mid)

        {

            res=(res+(*l+r)*k[mm]+l)%mod;

            h-=mid;

            l=l+r;

        }

        else

        {

            r=l+r;

        }

    }

    //if(h!=0)res+=r;

    return res%mod;

}

int main()

{

#ifdef Local

    freopen("data.txt","r",stdin);

#endif

    int i,j,T;

    LL ans;

    cin>>T;

    init();

    while(T--)

    {

        cin>>n>>m>>x>>y;

        for(i=;i<=n;i++)

        {

            scanf("%lld",&a[i]);

        }

        ans=f(y)-f(x-);

        if(ans<)ans+=mod;

        printf("%lld\n",ans);

    }

}

Ploblem H:

题意：给你一棵N节点的树和K种颜色的颜料，对这样的一棵树进行染色，使得任意两个相同颜色的联通节点之间所有节点颜色相同，求出所有的染色方法。

题目链接：https://www.codechef.com/problems/COLTREE

思路 I：

其实就是给你一棵树，让你切分成m棵子树，每棵子树的染色相同，有多少种染色方法。切成m棵子树，其实就是选择m-1条边去切断，所有就是C（n-1，m-1）,

然后对于m棵子树进行K种染色，其实就是A（K，m），所有方法数就是C（n-1，m-1）*A（K，m）。然后对于规模不大的大组合数取模，用杨辉三角把除变加进行

处理就可以了。

 #include <iostream>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <vector>

 #include <map>

 #include <set>

 #include <algorithm>

 #include <cmath>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <sstream>

 #define lson l,m,rt*2

 #define rson m+1,r,rt*2+1

 #define mod 1000000007

 using namespace std;

 typedef long long LL;

 LL C[][];

 LL A(int n,int m)

 {

     LL res=;

     for(int i=n;i>n-m;i--)

     {

         res=(res*i)%mod;

     }

     return res;

 }

 void init()

 {

     memset(C,,sizeof(C));

     for(int i=;i<=;i++)C[i][]=;

     for(int i=;i<=;i++)

     {

         for(int j=;j<=i;j++)

         {

             if(j==)C[i][j]=i;

             else if(i==j)C[i][j]=;

             else C[i][j]=(C[i-][j]+C[i-][j-])%mod;

         }

     }

 }

 int main()

 {

 #ifdef Local

     freopen("data.txt","r",stdin);

 #endif

      int n,m,u,v,T,i,j;

      LL ans;

      init();

      cin>>T;

      while(T--)

      {

          ans=;

          cin>>n>>m;

          for(i=;i<n-;i++)scanf("%d%d",&u,&v);

          for(i=;i<=min(n,m);i++)

          {

              ans=(ans+C[n-][i-]*A(m,i))%mod;

          }

          cout<<ans<<endl;

      }

 }

思路 II：树形DP（等我学会了再更...）

Private Training #1

Problem C （UVALive 6602 Counting Lattice Squares）

题意：给你一个（n+1）*（m+1）的点矩阵，然后让你在点阵里面找出，所有面积为奇数的正方形的个数？

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4613

思路：

首先，面积为奇数的正方形，可以直接由边长为奇数K得来，也可以由类似这样sqrt（K）的边得来。然后对于第二种情况的K，可以由a+b的和为奇数的情况得来，即

K=sqrt（a*a+b*b）&&（a+b）%2==1。接着你会发现，边长为sqrt（K）的正方形需要的空间是边长为（a+b）的正方形，所以边长为sqrt（K）的情况可以把它当做边长为

（a+b）的一类型，且该区域一共可以画2个不同的边长为sqrt（K）的正方形。然后对于一个（n+1）*（m+1）的点矩阵，一共可以切成（n-i+1）*（m-i+1）种边长为i的正方

形，但是对于边长i，它可以由不同的a+b组合而来，假设i=5,那么5=1+4=2+3，6=1+5=2+4=3+3，所以最后的公式就是（n-i+1）*（m-i+1）*（i/2*2(2种画法)+1(本身)）

 #include <iostream>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <vector>

 #include <map>

 #include <set>

 #include <algorithm>

 #include <cmath>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <sstream>

 #define lson l,m,rt*2

 #define rson m+1,r,rt*2+1

 #define mod 1000000007

 using namespace std;

 typedef long long LL;

 int main()

 {

 #ifdef Local

     freopen("data.txt","r",stdin);

 #endif

     int i,j;

     LL ans,s,n,m;

     while(~scanf("%lld %lld",&n,&m))

     {

         if(!n&&!m)break;

         ans=;

         for(i=;i<=min(n,m);i+=)

         {

             ans+=((n-i+)*(m-i+)*(i/*+));

         }

         cout<<ans<<endl;

     }

 }

Ploblem J:（UVALive 6609 Minimal Subarray Length）

题意：给你一个含有N个元素的数组和一个价值X，使得数组中连续一段数字和大于等于X的长度最小，如果找不到则输出-1

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4620

思路：

先用预处理出元素1-i（i<=n）的元素总和sum[i],再用RMQ预处理出dp[i][j]表示区间从i开始，长度为2^j的最大sum，然后再对于每一个i（1-n）二分（query（l,r）-sum[i-1]）

>=X，的最短长度，复杂度是n(logn)。

 #include <iostream>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <vector>

 #include <map>

 #include <set>

 #include <algorithm>

 #include <cmath>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <sstream>

 #define lson l,m,rt*2

 #define rson m+1,r,rt*2+1

 #define mod 1000000007

 using namespace std;

 typedef long long LL;

 const int INF=0x3f3f3f3f;

 LL dp[][],sum[];

 void RMQ(int n)

 {

     int i,j;

     for(i=;i<=n;i++)dp[i][]=sum[i];

     for(j=;(<<j)<=n;j++)

     {

         for(i=;(i+(<<j))<=n;i++)

         {

             dp[i][j]=max(dp[i][j-],dp[i+(<<(j-))][j-]);

         }

     }

 }

 LL query(int l,int r)

 {

     int p=;

     while(<<(p+)<=(r-l+))p++;

     return max(dp[l][p],dp[r-(<<p)+][p]);

 }

 int main()

 {

 #ifdef Local

     freopen("data.txt","r",stdin);

 #endif

     int i,j,T,n;

     LL k;

     cin>>T;

     while(T--)

     {

         memset(sum,,sizeof(sum));

         cin>>n>>k;

         for(i=;i<=n;i++)

         {

             scanf("%lld",&sum[i]);

             sum[i]+=sum[i-];

         }

         RMQ(n);

         int ans=INF;

         for(i=;i<=n;i++)

         {

             int l=i,r=n;

             while(l<=r)

             {

                 int m=(l+r)/;

                 if((query(i,m)-sum[i-])>=k)

                 {

                     r=m-;

                 }

                 else l=m+;

             }

             if(r<=n&&sum[r]-sum[i-]>=k)ans=min(ans,r-i+);

             if(l<=n&&sum[l]-sum[i-]>=k)ans=min(ans,l-i+);

         }

         if(ans==INF)cout<<-<<endl;

         else cout<<ans<<endl;

     }

     return ;

 }

To Be Continue!

巴特西

Individual Contest #1 and Private Training #1

最新文章

热门文章