题面:http://codeforces.com/contest/1064/problems
A. Make a triangle!
题意：给定三条边，问每条边需要共增加多少才能组成三角形。
解法：签到。
如果已经满足两边之和大于第三边输出0，否则最短的边增加需要增加的即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
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$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using namespace std;
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
题意：重新排列所有的字符，要求回文子串最多
解法：样例是骗人的，排个序相同的字符连在一起就是最多的。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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不能搜到所有的点。因为会存在某个点第二次访问到时会更优（左右用的次数更少）从而到达更多的点。
所以要优先考虑使用步数少的点。有两种方法实现。
第一是使用优先队列，每次在队首的都是步数少的。
第二是使用双向队列，将上下走的点放在头部，左右走的点放在尾部。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61//优先队列
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;
}
1 | //双向队列 |
E. Dwarves, Hats and Extrasensory Abilities
题意：交互题。有$n$个点，每次你给定一个点，交互系统返回你这个点的颜色，最后需要你找到一条直线使得将所有的点按黑白分割为两个部分。
解法：使用二分的策略。
首先给定$(0,1)$如果黑色，则黑色边界为左半部分，白色为右半部分。否则正好反过来。
然后每次给定$(mid, 1)$如果与第一个颜色相同，则处理右半部分，否则处理左半部分。
由于$n$最大不超过30，所以二分可行。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
}