Codechef May Challenge 2015

随便瞎写，其实没做出多少题：

Chef and Cake

题目大概是用输入的数生成一个数组并且生成出q个【X，Y】的询问，

数组长度N<=1000000,q<=10^7;

开始用线段树，RMQ，分块能切过去，但是线段树RE，RMQ re ,分块最多40分。

但是一直忽视了区间询问的[X Y] K<=Y-X+1<=2K; K是给定的数。

然后是利用一些思想。

比如我们每次求出DP【X】 ----------> 表示 I in【X，X+K-1] 范围 min(A[i]);A[i] 生成的数组。

询问X，Y的区间最小值 =Mi年(dp[x],dp[y-k+1]);

求出每个dp；

这里利用单调队列，熟悉的应该比较简单。

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cmath>
  4 #include<string.h>
  5 #include<string>
  6 #include<iostream>
  7 #include<vector>
  8 #include<map>
  9 #include<deque>
 10 #include<vector>
 11 
 12 #define inf 0x3f3f3f
 13 #define N 10000105
 14 #define mod 1000000007
 15 
 16 using namespace std;
 17 typedef long long ll;
 18 int a,b,c,d,e,f,g,r,s,t,m,n,k,q;
 19 int L1,La,Lc,Lm,D1,Da,Dc,Dm;
 20 
 21 ll A[N];
 22 int L[N],R[N];
 23 
 24 void work()//生成数据部分
 25 {
 26   ll tmp=t;
 27   for (int x=2;x<=n;x++)
 28   {
 29     tmp=tmp*t%s;
 30     if (tmp<=r) A[x]=(A[x-1]*A[x-1]%m*a+A[x-1]*b%m+c)%m;
 31         else    A[x]=(A[x-1]*A[x-1]%m*d+A[x-1]*e%m+f)%m;
 32   }
 33 
 34   for (int i=1;i<=q;i++)
 35   {
 36   /*  L1=(ll) ((ll)La*L1+Lc)%Lm;
 37       D1=(ll) ((ll)Da*D1+Dc)%Dm;
 38       生成数据有问题，注意La为int La*L1溢出
 39     */
 40    L1=(ll) ((ll)La*L1+Lc)%Lm;
 41    D1=(ll) ((ll)Da*D1+Dc)%Dm;
 42    L[i]=L1+1;
 43    R[i]=min(L[i]+k-1+D1,n);
 44    }
 45 }
 46 
 47 int minarr[N];
 48 int ff[N];
 49 
 50 void work2()
 51 {
 52   int i,j,h,t;
 53   h=0,t=0;//维护一个长度为k的单调递增队列
 54   
 55   for (i=1;i<=k;i++)
 56   {
 57     while (h<t&&A[i]<=A[ff[t-1]]) t--;
 58     ff[t++]=i;
 59   }
 60   j=1;
 61   for (;i<=n;i++,j++)
 62   {
 63     minarr[j]=A[ff[h]];
 64     while (h<t&&ff[h]<=i-k) h++;
 65     while (h<t&&A[i]<=A[ff[t-1]]) t--;
 66     ff[t++]=i;
 67   }
 68   minarr[j]=A[ff[h]];
 69 }
 70 
 71 void debug()//debug部分
 72 {
 73   for (int i=1;i<=n;i++)
 74   cout<<A[i]<<" ";
 75   cout<<endl;
 76   for (int i=1;i<=n-k+1;i++)
 77   cout<<minarr[i]<<" ";
 78   cout<<endl;
 79 }
 80 
 81 
 82 int main()
 83 {
 84   while (scanf("%d%d%d",&n,&k,&q)!=EOF){
 85   scanf("%d%d%d%d%d%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f,&r,&s,&t,&m,&A[1]);
 86   scanf("%d%d%d%d%d%d%d%d",&L1,&La,&Lc,&Lm,&D1,&Da,&Dc,&Dm);
 87   work();
 88   work2();
 89 //  debug();
 90 
 91   ll ans1,ans2;
 92   ans1=0;
 93   ans2=1;
 94   
 95   for (int i=1;i<=q;i++)
 96   {
 97     int tmp=min(minarr[L[i]],minarr[R[i]-k+1]);
 98     ans1+=tmp;
 99     ans2=ans2*tmp%mod;
100     }
101     printf("%lld %lld
",ans1,ans2);
102   }
103   return 0;
104 }

Devu and binary String

也是很有意思的题目：

大意是：给一个01串，我们可以对每个0 1 翻转，使0->1,1->0.

然后问：用最少的翻转次数，是字符串里面没有连续k字符是一样的。

长标题：开始贪心思路是每连续k个一样就把最后一个翻转，但是会有问题。

当我们可能反转最后一个使的接下来K-1个和翻转的一个有成为一样的，显然这样并不是最优的

我们可以把前K个中倒数第二个翻转，结果就更优，基于这种贪心思路，这题可以这么做。

然后注意一下K=1的特判。