Codeforces Round #495 (Div. 2) A,B,C

A题

1.新添加一间酒店，要求酒店离已有的最近的一间酒店的距离恰好等于d

2.最左和最右必定存在合适的两种情况

3.酒店之间的情况就要判断两间酒店间的距离：

小于2d，表示无法在这两间酒店中间找到合适情况
等于2d，表示这两间酒店的正中间可以满足条件，新建酒店
大于2d，表示这两间酒店之间存在两种满足条件的情况

 #include<bits/stdc++.h>

 /*

 -6 0 5 6 12 13 19

 2 6 10 13 16 21

 */

 using namespace std;

 #define int long long

 #define N 209

 map<int,int> mp;

 int arr[N];

 signed main(){

     int n,d;

     cin>>n>>d;

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

     {

         cin>>arr[i];

         mp[arr[i]]=;

     }

     if(n==){

         cout<<;

         return ;

     }

     sort(arr+,arr++n);

     int sum=;

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

         if(i==){

             if(!mp[arr[i]+d]&&(arr[i+]-(arr[i]+d))>=d){

             mp[arr[i]+d]=;

         //    cout<<arr[i]+d<<endl;

             sum++;

             }

             continue;

         }

         if(i==n){

             if(!mp[arr[i]-d]&&(arr[i]-d-arr[i-])>=d){

             mp[arr[i]-d]=;

         //    cout<<arr[i]-d<<endl;

             sum++;

             }

             continue;

         }

         if(!mp[arr[i]-d]&&(arr[i]-d-arr[i-])>=d){

             mp[arr[i]-d]=;

         //    cout<<arr[i]-d<<endl;

             sum++;

         }

         if(!mp[arr[i]+d]&&(arr[i+]-(arr[i]+d))>=d){

             mp[arr[i]+d]=;

         //    cout<<arr[i]+d<<endl;

             sum++;

         }

     }

     printf("%d\n",sum+);

     return ;

 }

 /*

 3 2

 4 4

 5 6

 6 9

 */

 */

B题

题意：有一排n个格子，每个格子里能放一种花，一共有两种花，一种用 0 代表，另一种用 1 代表，然后给你m各区间，每个区间的价值就是这个区间内的两种花的数量之积。问你应该怎么放花，使得这些区间的价值和最大。

思路：就是说让0 1 的个数在各个区间内都是接近的（和相等，越接近，积越大），也就是说0 1 分布均匀，那么，我们直接0 1 交替输出，就可以保证0 1 在各个区间都是最接近的。

AC代码：

#include<bits/stdc++.h>

using namespace std;

#define N 200505

struct str{

    int l,r;

    int cha;

}st[N];

int main(){

    int n,m;

    cin>>n>>m;

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

        cin>>st[i].l>>st[i].r;

    }

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

        if(i%)

            cout<<;

        else

            cout<<;

    }

    return ;

}

/*

2 1

3 2

4 4

5 6

6 9

101010

2+4+2

101010

1+4+2

*/

/**/

C题：

题意：给出一个长为n的数列（数字可以重复），表示在i号位置的数字为ai。.现在，在数列的最左和最右端有一个报数机器人，最左端的机器人向右移动，最右端的机器人向左移动，每移动到一个位置时，机器人就会将这个位置的数字报出来。现在，每个机器人都有一个编号，如果机器人报出来的数字和这个编号相同的话，机器人就会停止移动。

问，这两个机器人的编号有多少种情况，可以使这两个机器人不发生碰撞。
思路：跑后缀就行。用MAP标记超时了QAQ
AC代码：

 #include<map>

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define int long long

 #define N  250000

 int arr[N];

 int sum[N];

 int mp[N];

 int mmp[N];

 signed main(){

     int n;

     cin>>n;

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

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

     int add=;

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

         sum[i]=add;

         if(!mmp[arr[i]])

             add++;

         mmp[arr[i]]=;

     }

     int ans=;

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

         if(mp[arr[i]])

             continue;

         ans+=sum[i];

         mp[arr[i]]=;

     }

     cout<<ans;

     return ;

 }

巴特西

Codeforces Round #495 (Div. 2) A,B,C

最新文章

热门文章