Codeforces Round #516 (Div. 2, by Moscow Team Olympiad)

题面:http://codeforces.com/contest/1064/problems

A. Make a triangle!

题意：给定三条边，问每条边需要共增加多少才能组成三角形。
解法：签到。
如果已经满足两边之和大于第三边输出0，否则最短的边增加需要增加的即可。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<int> a = vector<int>(3);
    for(int& idx: a)
        cin >> idx;
    sort(a.begin(), a.end());
    cout << max(0, 1 + a[2] - a[1] - a[0]) << endl;
    return 0;
}

B. Equations of Mathematical Magic

题意：有一个有趣的式子$a - ( a \oplus x ) - x = 0$，先给定$a$，要求你迅速的求出x。
解法：规律 & 思维
把式子进行变形变为$a - x = a \oplus x$ 从二进制的角度来分析要使式子成立，令$a_i$为$a$第$i$位，$x_i$为$x$第$i$位对于每一位 真值表如下
| $a_i$ | $x_i$ | $xor$ | $a_i - x_i$|
| ——— | ——— | ——— | ——— |
| 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | (-1) |
可以发现 对于$a_i$为0时，$x_i$必须为0，而$a_i$为1时，$x_i$为0或1都可以。
所以只要找出a中有多少个为1的位设为n位，答案为$2^n$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--)
    {
        int t; cin >> t;
        bitset<32> q = bitset<32>(t);
        cout << (1 << q.count()) << endl;
    }
    return 0;
}

C. Oh Those Palindromes

题意：重新排列所有的字符，要求回文子串最多
解法：样例是骗人的，排个序相同的字符连在一起就是最多的。

#include <bits/stdc++.h>
#define ll long long
const int maxn = 1e5 + 10;
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    cout << s << endl;
    return 0;
}

D. Labyrinth

题意：给定一个图，从起点出发可以向四个方向走。限制向左走和向右走的次数，不限制向上和向下走的次数。问最多能走到多少个点。
解法：01BFS
和普通的搜索不同的是，由于限制了向左走和向右走的次数，会导致单纯的bfs不能搜到所有的点。因为会存在某个点第二次访问到时会更优（左右用的次数更少）从而到达更多的点。
所以要优先考虑使用步数少的点。有两种方法实现。
第一是使用优先队列，每次在队首的都是步数少的。
第二是使用双向队列，将上下走的点放在头部，左右走的点放在尾部。

//优先队列
#include <bits/stdc++.h>
#define ll long long
const int maxn = 2e3 + 10;
using namespace std;
int n, m;
char g[maxn][maxn];
struct node{
    int x, y;
    int ri, le;
};
bool operator < (const node& a, const node& b)
{
    if(a.ri == b.ri)
        return a.le < b.le;
    else
        return a.ri < b.ri;
}
int vis[maxn][maxn];
int px[] = {0, 1, 0, -1};
int py[] = {1, 0, -1, 0};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    int r, c, x, y, cnt = 0;
    cin >> r >> c >> x >> y;
    for(int i = 1; i <= n; i++)
        cin >> (g[i] + 1);
    priority_queue<node> q;
    q.push(node{r, c, y, x});
    vis[r][c] = 1;
    while(q.size())
    {
        node now = q.top();
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            int dx = px[i] + now.x, dy = py[i] + now.y;
            if(i == 0 && now.ri < 1) continue;//向右走
            if(i == 2 && now.le < 1) continue;//向左走
            if(dx > 0 && dx <= n && dy > 0 && dy <= m)
                if(!vis[dx][dy] && g[dx][dy] == '.')
                {
                    vis[dx][dy] = 1;
                    if(i == 0)
                        q.push(node{dx, dy, now.ri - 1, now.le});
                    else if(i == 2)
                        q.push(node{dx, dy, now.ri, now.le - 1});
                    else
                        q.push(node{dx, dy, now.ri, now.le});
                }
        }
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(vis[i][j])cnt++;
    cout << cnt << endl;
    return 0;
}

//双向队列
#include <bits/stdc++.h>
#define ll long long
const int maxn = 2e3 + 10;
using namespace std;
int n, m;
char g[maxn][maxn];
struct node{
    int x, y;
    int ri, le;
};
int vis[maxn][maxn];
int px[] = {0, 1, 0, -1};
int py[] = {1, 0, -1, 0};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    int r, c, x, y, cnt = 0;
    cin >> r >> c >> x >> y;
    for(int i = 1; i <= n; i++)
        cin >> (g[i] + 1);
    deque<node> q;
    q.push_front(node{r, c, y, x});
    vis[r][c] = 1;
    while(q.size())
    {
        node now = q.front();
        q.pop_front();
        for(int i = 0; i < 4; i++)
        {
            int dx = px[i] + now.x, dy = py[i] + now.y;
            if(i == 0 && now.ri < 1) continue;//向右走
            if(i == 2 && now.le < 1) continue;//向左走
            if(dx > 0 && dx <= n && dy > 0 && dy <= m)
                if(!vis[dx][dy] && g[dx][dy] == '.')
                {
                    vis[dx][dy] = 1;
                    if(i == 0)
                        q.push_back(node{dx, dy, now.ri - 1, now.le});
                    else if(i == 2)
                        q.push_back(node{dx, dy, now.ri, now.le - 1});
                    else
                        q.push_front(node{dx, dy, now.ri, now.le});
                }
        }
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(vis[i][j])cnt++;
    cout << cnt << endl;
    return 0;

}

E. Dwarves, Hats and Extrasensory Abilities

题意：交互题。有$n$个点，每次你给定一个点，交互系统返回你这个点的颜色，最后需要你找到一条直线使得将所有的点按黑白分割为两个部分。
解法：使用二分的策略。
首先给定$(0,1)$如果黑色，则黑色边界为左半部分，白色为右半部分。否则正好反过来。
然后每次给定$(mid, 1)$如果与第一个颜色相同，则处理右半部分，否则处理左半部分。
由于$n$最大不超过30，所以二分可行。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    n--;
    int l = 0, r = 1e9;
    cout << "0 1" << endl;
    string s;
    cin >> s;
    bool mode = 0;
    if(s[0] == 'b')
        mode = 1;
    while(n--)
    {

        int mid = (l + r) / 2;
        cout << mid << " 1" << endl;
        cin >> s;
        if(s[0] == 'b')
        {
            if(mode)
                l = mid;
            else
                r = mid;
        }
        else
        {
            if(mode)
                r = mid;
            else
                l = mid;
        }
    }
    cout << l << " 0 "<< r << " 2" << endl;
return 0;
}