A. Three Piles of Candies
http://codeforces.com/contest/1196/problem/A
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
ll a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);
printf("%lld\n", (a + b + c) / 2);
}
} B. Odd Sum Segments
http://codeforces.com/contest/1196/problem/B
将n个数分为k块，每块是奇数个，可以分的话输出每个区间的右端点
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[200005];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int cnt = 0;
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if (a[i] & 1)
{
a[i] = 1;
cnt++;
}
else
a[i] = 0;
}
if (cnt < k)
{
printf("NO\n");
continue;
}
int he = cnt - k;
if (he & 1)
{
printf("NO\n");
continue;
}
vector<int>v;
for (int i = 1; i <= n; i++)
{
if (a[i] == 1)
{
if (he >= 0)
he--;
else
v.push_back(i - 1);
}
}
v.push_back(n);
int len = v.size();
printf("YES\n");
for (int i = 0; i < len; i++)
printf("%d%c", v[i], i == len - 1 ? '\n' : ' ');
}
} C. Robot Breakout
http://codeforces.com/contest/1196/problem/C
有n个机器人，他们有些不能向某个方向移动，问能否交于一点，可以输出一个交点。
遍历每个机器人来维护四个顶点。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int xs[200005], ys[200005];
int a1[200005], b1[200005], c1[200005], d1[200005];
int main()
{
int T, n;
int x, y;
int a, b, c, d;
scanf("%d", &T);
while (T--)
{
int xl = -100000, xr = 100000, yd = -100000, yu = 100000;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d%d%d%d%d%d", &xs[i], &ys[i], &a1[i], &b1[i], &c1[i], &d1[i]);
for (int i = 1; i <= n; ++i)
{
x = xs[i], y = ys[i], a = a1[i], b = b1[i], c = c1[i], d = d1[i];
if (a == 0 && c == 0)
{
if (xl > x || xr < x)
{
printf("0\n");
goto qwe;
}
else xl = xr = x;
}
else if (a == 0 && c == 1)
{
if (xr < x)
{
printf("0\n");
goto qwe;
}
else
xl = max(xl, x);
}
else if (a == 1 && c == 0)
{
if (xl > x)
{
printf("0\n");
goto qwe;
}
else
xr = min(xr, x);
}
if (b == 0 && d == 0)
{
if (yu<y || yd>y)
{
printf("0\n");
goto qwe;
}
else
yu = yd = y;
}
else if (b == 0 && d == 1)
{
if (yd > y)
{
printf("0\n");
goto qwe;
}
else
yu = min(yu, y);
}
else if (b == 1 && d == 0)
{
if (yu < y)
{
printf("0\n");
goto qwe;
}
else
yd = max(yd, y);
}
}
printf("1 %d %d\n", xl, yu);
qwe:;
}
} D1. RGB Substring (easy version)
D2. RGB Substring (hard version)
http://codeforces.com/contest/1196/problem/D2
要使长度为 n 的只包含 R G B 的序列中，出现长度为k的 RGBRGBRGB……的子串（连续）的最小代价，其中改变一个字母的代价为1.
首先预处理当起点为R G B 是各个点的维护代价
然后求一个前缀
然后遍历整个序列，求一下以当前为起点，所需要的代价是多少。
#include <bits/stdc++.h>
using namespace std;
char s[200005];
int a[3][200005];
int sum[3][200005];
char type[3] = { 'R','G','B' };
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n, k;
scanf("%d%d", &n, &k);
scanf("%s", s + 1);
int len = strlen(s + 1);
for (int i = 0; i < 3; i++)
{
for (int j = 1; j < len + 1; j++)
{
if (s[j] == type[(i + j) % 3])
a[i][j] = 0;
else
a[i][j] = 1;
sum[i][j] = sum[i][j - 1] + a[i][j];
}
}
int minn = 200005;
for (int i = 0; i < 3; i++)
{
for (int j = 1; j < len + 1; j++)
{
if (j + k - 1 >= len + 1)
continue;
minn = min(minn, sum[i][j + k - 1] - sum[i][j - 1]);
}
}
printf("%d\n", minn);
}
} E. Connected Component on a Chessboard
http://codeforces.com/contest/1196/problem/E
有一个棋盘，长度1e9*1e9，(1,1)方格是白色，然后黑白相间，问你能否找到一个联通块使得出现过b次黑色，w次白色。
只有当两个方块中间存在一条公共边时，我们认为他联通。
1、首先，假设a个白色，最多只能3*a+1个黑色，所以我们可以判掉不合法情况
2、然后我们先取一个数量大的颜色，然后将所有数量少的颜色相邻取第一个取的颜色后。
3、此时颜色少的个数为0，颜色多的取在我们已经练成的线的颜色少方格的上下一个单位。
4、具体实现看代码
#include <bits/stdc++.h>
using namespace std;
void print(int x, int y)
{
printf("%d %d\n", x, y);
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int b, w;
scanf("%d%d", &b, &w);
if (b < w)
{
if (w > 3 * b + 1)
{
printf("NO\n");
continue;
}
printf("YES\n");
int sx = 2, sy = 4;//白
int x = 2, y = 4;
print(x, y);
w--;
while (b != 0)
{
y++;
print(x, y);
y++;
print(x, y);
b--;
w--;
}
for (int i = sy + 1; i <= y; i += 2)
{
if (w)
{
print(x - 1, i);
w--;
}
else
break;
if (w)
{
print(x + 1, i);
w--;
}
else
break;
}
}
else if (b > w)
{
if (b > 3 * w + 1)
{
printf("NO\n");
continue;
}
printf("YES\n");
int sx = 2, sy = 3;//黑
b--;
int x = 2, y = 3;
print(x, y);
while (w != 0)
{
y++;
print(x, y);
y++;
print(x, y);
b--;
w--;
}
for (int i = sy + 1; i <= y; i += 2)
{
if (b)
{
print(x - 1, i);
b--;
}
else
break;
if (b)
{
print(x + 1, i);
b--;
}
else
break;
}
}
else
{
int x = 3, y = 3;
printf("YES\n");
while (b)
{
y++;
print(x, y);
y++;
print(x, y);
b--;
}
}
}
} F. K-th Path
http://codeforces.com/contest/1196/problem/F
没有起点终点，要求第k短路
由于K小于400，最多取400条边，800个点，先离散化一下，然后跑Floyd。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
int u;
int v;
ll w;
}in[400000];
ll dis[1000][1000];
void flody(int n)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
if (dis[j][k] > dis[j][i] + dis[i][k])
dis[j][k] = dis[j][i] + dis[i][k];
}
#define Pair pair<int,int>
int main()
{
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= 1001; i++)
for (int j = 1; j <= 1001; j++)
if (i == j)
dis[i][j] = 0;
else
dis[i][j] = 1e18 + 7;
for (int i = 1; i <= m; i++)
scanf("%d%d%lld", &in[i].u, &in[i].v, &in[i].w);
sort(in + 1, in + m + 1, [](node q, node w) {
return q.w < w.w;
});
//离散化
vector<int>dot;
for (int i = 1; i <= min(m, k); i++)
{
dot.push_back(in[i].u);
dot.push_back(in[i].v);
}
sort(dot.begin(), dot.end());
dot.erase(unique(dot.begin(), dot.end()), dot.end());
int len = dot.size();
//加边
for (int i = 1; i <= min(m, k); i++)
{
in[i].u = lower_bound(dot.begin(), dot.end(), in[i].u) - dot.begin() + 1;
in[i].v = lower_bound(dot.begin(), dot.end(), in[i].v) - dot.begin() + 1;
dis[in[i].u][in[i].v] = in[i].w;
dis[in[i].v][in[i].u] = in[i].w;
}
flody(len);
vector<ll>v;
for (int i = 1; i <= len; i++)
{
for (int j = i + 1; j <= len; j++)
v.push_back(dis[i][j]);
}
sort(v.begin(), v.end());
printf("%lld\n", v[k - 1]);
}
京公网安备 11010502036488号