比赛网址：http://codeforces.com/contest/1285

A

题面：

输入一个长度为n的字符串（仅有L和R组成），代表机器人在x坐标轴上的移动指令，该机器人可能忘掉了部分指令，问你机器人最后能落在多少不同的位置？

solution：

记录L和R的个数，答案即为L+R+1（其实也可以直接输出n+1）

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int n,cnt1 = 0,cnt2 = 0;
    cin>>n;
    string s;
    cin>>s;
    for(int i=0;i<n;i++)
    {
        if(s[i] == 'L')
            cnt1++;
        else
            cnt2++;
    }
    cout<<cnt1+cnt2+1<<endl;
    return 0;
}

B

题面：

给出一个长度为n的数组，代表n块面包的美味值，A要买完所有的面包，B可以买任意连续子序列的面包，但是不能全部都买，问你是否能使B的美味值大于等于A？

solution：

很明显，我们要找到[1,n-1]和[2,n]的最大连续子序列和然后和[1,n]的和比较即可

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
ll a[maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,flag = 0;
        ll sum = 0;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum += a[i];
        }
        ll sum1 = 0,sum2 = 0,maxx = -1e9;
        for(int i=1;i<n;i++){
            sum1 += a[i];
            if(a[i] > sum1)
                sum1 = a[i];
            maxx = max(maxx , sum1);
        }
        for(int i=2;i<=n;i++){
            sum2 += a[i];
            if(a[i] > sum2)
                sum2 = a[i];
            maxx = max(maxx , sum2);
        }
        if(maxx >= sum)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

C

题面：

输入n，输出a b，满足a和b的最小公倍数 = n，而且最小化max(a,b)

solution：

从sqrt(n)遍历，找到__gcd(a,b) == 1 的即为答案，如果gcd不等于1，那么最小公倍数肯定也不等于n

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n;
    int flag = 0;
    cin>>n;
    ll sq =sqrt(n);
    for(ll i=sq; ;i--)
    {
        if(n%i == 0){
            ll x = i;
            ll y = n/i;
            if(__gcd(x,y) == 1){
                flag = 1;
                cout<<x<<" "<<y<<endl;
                break ;
            }
        }
        if(flag)
            break ;
    }
    return 0;
}

D

题面：

给出一个大小为n的数组a1~an，请找到最佳的x，满足max(ai^x)最小（1<=i<=n)，输出最小的max(ai^x)

solution：

这题没做出来，知道是二进制贪心，但是写不出来，不知道怎么处理01同时存在同一位上的情况，看了题解明白了，如果某一个位置上全部都是0或者全部都是1，那这一位肯定都是0，如果0和1同时存在，我们取min(这一位是0，这一位是1) + (1<<i)

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
int a[maxn];
int dfs(int i,vector<int> &v){
    vector<int> v0,v1;
    if(i < 0)
        return 0;
    for(int j=0;j<v.size();j++){
        if((v[j]>>i)&1)
            v1.push_back(v[j]);
        else
            v0.push_back(v[j]);
    }
    if(v0.size() == 0)
        return dfs(i - 1,v1);
    if(v1.size() == 0)
        return dfs(i - 1,v0);
    return min(dfs(i-1 , v0) , dfs(i-1 ,v1))+(1<<i);
}
vector<int> v;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        v.push_back(a[i]);
    }
    cout<<dfs(30 , v);
    return 0;
}