Codeforces Round #495 (Div. 2) ABC 题解

A.Sonya and Hotels

1. description：给你位于无限长的横坐标的n个城市，和每个城市的坐标Xi。要求再建一个城市，该城市需要满足距离所有的城市的最短距离为d。
2. link：http://codeforces.com/contest/1004/problem/A
3. 思路：以n=5，d=2为例：
   
4. AC code:

#include<iostream>
using namespace std;
typedef long long ll;
ll a[103],ans=0;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int x;ll d;cin>>x>>d;
    for(int i=1;i<=x;i++)cin>>a[i];
    for(int i=2;i<=x;i++)
        if((a[i]-a[i-1])>2*d)ans+=2;
        else if((a[i]-a[i-1])==2*d)ans++;
    cout<<ans+2<<endl;
}

B. Sonya and Exhibition

1. description：给你n（标记为1~n）个地点，和m个观察者以及每个观察者观察的花朵的位置（从Li到Ri，x=Ri-Li+1个位置），在x个位置中问如何放置0和1能够使0的个数乘以1的个数的乘积最大（或者1的个数乘以0的个数的乘积最大）。
2. link：http://codeforces.com/contest/1004/problem/B
3. 思路：由数学公式可推出，任何x=Ri-Li+1个数，当x为偶数时(x/2)(x/2)最大；当x为奇数时，（x/2+1）(x/2)最大。由此可知，只需满足0和1交替放置就可使得任意区间范围内的0和1的个数满足上述要求。
4. AC code：

#include<iostream>
using namespace std;
int main(){
    int n,m;cin>>n>>m;
    while(m--){ int a,b;cin>>a>>b;}
    for(int i=1;i<=n;i++)if(i%2)cout<<1;else cout<<0;
}

C. Sonya and Robots

1. descriprion:给你n个位置以及每个位置上的所有数字的值。已知有两个机器人，首先分别给他们两个一个值，第一个机器人从左边出发，第二个机器人从右边出发，两个机器人同时出发相向而行，每个机器人在第一次遇到与给它的值相等的值的位置上停下。问有多少对这样的数字满足两个机器人不会相遇。
2. link:http://codeforces.com/contest/1004/problem/C
3. 思路：n个数每个数与其他数进行匹配，找到不同的数对的个数。起初我用的pair存储数对，set进行去重。哈哈，肯定超时。
   下面是思路：
   
4. AC code:

#include<iostream>
#include<set>
using namespace std;
const int N=1e5+6;
typedef long long ll;
ll a[N],ans;set<int>s;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        a[x]=s.size();
        s.insert(x);
    }
    for(int i=1;i<=n;i++)ans+=a[i];
    cout<<ans<<endl;
}