Codeforces Round #193 (Div. 2) 部分题解

A:直接判断前三项是否相等

 int main()

 {

     //FIN;

     //CHEAT;

     int n;

     cin>>n;

     getchar();

     char a[];

     gets(a);

     int len = strlen(a);

     int cnt = ;

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

     {

         if(i % n ==  && i !=  )

         {

             if(a[i-] == a[i-] && a[i-] == a[i-])

                 cnt++;

         }

     }

     cout<<cnt<<endl;

     return ;

 }

求一遍前缀和O(n).... 用前缀和求一遍所有长度为k的区间和O(n)....

再从后往前找一遍这些区间的最大值O(n)...并记下从该点到最后的区间最大值...

然后就从前向后遍历一遍,每次找从i开始的区间和从点i+k之后的最大区间 ,求一次MAX即可 O(n)

总共还是O(n)...用线段树什么的就别逗了

 LL a[];

 LL sum[];

 LL sum1[];

 LL max2[];

 LL maxe[];

 int main()

 {

     //FIN;

     //CHEAT;

     int n,k;

     cin>>n>>k;

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

     {

         cin>>a[i];

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

     }

     int cnt = ;

     for(int i =  ; i <= n-k+ ; i++)

     {

         sum1[cnt++] = sum[i+k-] - sum[i-];

     }

     int back = cnt-;

     LL M = -INF;

     for(int i = cnt- ; i >=  ; i--)

     {

         if(sum1[i] >= M)

         {

             max2[i] = sum1[i];

             maxe[i] = i;

             M = sum1[i];

         }else

         {

             max2[i] = M;

             maxe[i] = maxe[i+];

         }

     }

     M = -INF;

     int s1=,s2=;

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

     {

         if(max2[i+k] + sum1[i] > M)

         {

             M = max2[i+k] + sum1[i];

             s1 = i;

             s2 = maxe[i+k];

         }

     }

     cout<<s1<<" "<<s2<<endl;

     return ;

 }

先贪心找 b最小a最大的这是有可能取的任务

再贪心找 a最大b最大的这是一定取的k个任务,并求出最小值

再贪心从剩下的点中找出b小于最小值的点 ,再贪心找取p-k个b最大a最小的点...

排三遍序就行了...挺麻烦而且我感觉数据弱了...

 struct point

 {

     int id ;

     int s,v;

 }x[MAXN],q[MAXN];

 int cmp(point a,point b)

 {

     if(a.v != b.v)

         return a.v < b.v;

     else return a.s > b.s;

 }

 int cmp1(point a,point b)

 {

     if(a.s != b.s)

         return a.s > b.s;

     else return a.v > b.v;

 }

 int cmp2(point a,point b)

 {

     if(a.v != b.v)

         return a.v > b.v;

     else return a.s < b.s;

 }

 int main()

 {

     //FIN;

     //CHEAT;

     int n,p,k;

     cin>>n>>p>>k;

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

     {

         cin>>x[i].s>>x[i].v;

         x[i].id = i;

     }

     sort(x,x+n,cmp);

     sort(x+(p-k),x+n,cmp1);

 //    for(int i = 0 ; i < n ; i++)

 //        cout<<x[i].s<<" "<<x[i].v<<"   "<<x[i].id+1<<endl;

 //    cout<<endl;

     int M = INF;

     for(int i = p-k ;i < p ; i++)

         M = min(M,x[i].v);

     int cnt =  ;

     for(int i =  ; i < p - k ; i++)

         q[cnt++] = x[i];

     for(int i = p- ; i < n ; i++)

         if(x[i].v < M )

             q[cnt++] = x[i];

     sort(q,q+cnt,cmp2);

     for(int i = p-k ; i < p ; i++)

         cout<<x[i].id+<<" ";

     for(int i =  ; i < p - k ; i++)

         cout<<q[i].id+<<" ";

     cout<<endl;

     return ;

 }

都是赛后做的...赛中做的话又要掉rating真是难过...今天多校也爆0...真是弱的不能多说...

巴特西

Codeforces Round #193 (Div. 2) 部分题解

最新文章

热门文章