Codeforces Round #575 (Div. 3)
这个div3打的太差了，心态都崩了。
B. Odd Sum Segments
B 题我就想了很久，这个题目我是找的奇数的个数，因为奇数想分成x个奇数，那么这个x肯定是一个奇数，
偶数同理，如果一个偶数想分成y个奇数，那么这个y肯定是一个偶数。
所以数奇数的个数，如果奇数有x个，x是偶数，那么k一定是一个偶数，如果x是一个奇数，那么k肯定是一个奇数。
输出也比较简单，因为奇数要分成奇数个，所以可以前面每组都是含有一个奇数，最后肯定会有奇数个奇数的。
偶数同理。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 2e5 + ;
vector<int>e;
int main()
{
int q;
scanf("%d", &q);
while(q--)
{
int n, k;
scanf("%d%d", &n, &k);
e.clear();
for(int i=;i<=n;i++)
{
ll x;
scanf("%lld", &x);
if(x&) e.push_back(i);
}
int len = e.size();
if (k > len) printf("NO\n");
else if (((len & ) && (k & )) || ((len % == ) && (k % == ))) {
printf("YES\n");
for (int i = ; i < k - ; i++) printf("%d ", e[i]);
printf("%d\n", n);
}
else printf("NO\n");
}
}
B
C. Robot Breakout
这个C题当时没有写出来，因为我感觉要分很多种情况来讨论，实际上并不需要。
这个题目我只要给x y 的上下界限制范围就可以了，根据每一个位置出现0的情况来缩小xy的范围。
虽然这个题目比赛的时候没有写出来，不过还是很有收获的，因为我自己对于这种题目本身就不是很擅长。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 2e5 + ;
vector<int>e;
bool judge(char ch,char c)
{
if (ch == 'R'&&c == 'G') return ;
if (ch == 'G'&&c == 'B') return ;
if (ch == 'B'&&c == 'R') return ;
return ;
}
char s[maxn];
int main()
{
int q;
scanf("%d", &q);
while(q--)
{
int n;
scanf("%d", &n);
int l=-1e5, r=1e5, d=-1e5, u=1e5;
for(int i=;i<=n;i++)
{
int a, b;
scanf("%d %d", &a, &b);
for(int j=;j<=;j++)
{
int x;
scanf("%d", &x);
if (j == && x == ) l = max(l, a);
if (j == && x == ) u = min(u, b);
if (j == && x == ) r = min(r, a);
if (j == && x == ) d = max(d, b);
//printf("l=%d r=%d u=%d d=%d\n", l, r, u, d);
}
}
if (l > r || u < d) printf("0\n");
else printf("1 %d %d\n", l, u);
}
return ;
}
C
D1. RGB Substring (easy version)
这个D1 我觉得还比较难吧，自己也没有写出来，看了别人的代码，
这个题目要找这种序列，那么就可以先用一个数组存下来前面的组成完整的RGBRGBR.....的个数。
这个我觉得有一点点dp的思想，再加上前缀和，然后就可以求出来。
最后我们要求的是有m个的最小花费，这个的话就是枚举，枚举长度为m，求最小花费。
这种题目我很少做，这次没做出来，以后希望不要忘记了。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 2e5 + ;
int sum[maxn][];
char s[maxn];
int main()
{
int q;
scanf("%d", &q);
while(q--)
{
int n, m;
cin >> n >> m;
int ans = inf;
memset(sum, , sizeof(sum));
scanf("%s", s+);
for (int i = ; i <= n; i++) {
if (i % == ) {
if (s[i] == 'R') sum[i][]++;
if (s[i] == 'G') sum[i][]++;
if (s[i] == 'B') sum[i][]++;
}
if (i % == ) {
if (s[i] == 'R') sum[i][]++;
if (s[i] == 'G') sum[i][]++;
if (s[i] == 'B') sum[i][]++;
}
if (i % == ) {
if (s[i] == 'R') sum[i][]++;
if (s[i] == 'G') sum[i][]++;
if (s[i] == 'B') sum[i][]++;
}
}
for(int i=;i<=n;i++)
{
sum[i][] += sum[i - ][];
sum[i][] += sum[i - ][];
sum[i][] += sum[i - ][];
// printf("sum[%d][1]=%d\n", i, sum[i][1]);
// printf("sum[%d][2]=%d\n", i, sum[i][2]);
// printf("sum[%d][3]=%d\n", i, sum[i][3]);
}
for(int i=;i<=n;i++)
{
if(i<=m)
{
ans = min(ans, m - sum[i][]);
ans = min(ans, m - sum[i][]);
ans = min(ans, m - sum[i][]);
}
else
{
ans = min(ans, m - (sum[i][] - sum[i - m][]));
ans = min(ans, m - (sum[i][] - sum[i - m][]));
ans = min(ans, m - (sum[i][] - sum[i - m][]));
}
// printf("i=%d ans=%d\n", i, ans);
}
printf("%d\n", ans);
}
return ;
}
D1
D2和D1代码差不多，不过卡了memset，把memset换成for循环就可以了。
E. Connected Component on a Chessboard
是一个比较简单的构造题，我写搓了，但是很好写，就是一条横线就可以了。
这个是求第k短路，但是这个因为k很小，所以可以直接暴力，我用的floyed，
先把所有的点离散化了，然后再跑floyed，最后把结果存到数组里面，然后输出第k大就可以了。
这个求第k大有一个A* 算法，但是这个题目好像不可以用，因为时间复杂度太高了。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 2e5 + ;
struct node
{
int u, v;
ll w;
node(int u=,int v=,ll w=):u(u),v(v),w(w){}
}exa[maxn];
bool cmp(node a,node b)
{
return a.w < b.w;
}
int f[maxn];
int a[maxn];
ll w[][];
vector<ll>e;
int main()
{
int n, m, k, tot = ;
scanf("%d%d%d", &n, &m, &k);
for(int i=;i<=m;i++)
{
int u, v;
ll w;
scanf("%d%d%lld", &u, &v, &w);
exa[i] = node(u, v, w);
}
sort(exa + , exa + + m, cmp);
for(int i=;i<=min(k,m);i++)
{
a[tot++] = exa[i].u;
a[tot++] = exa[i].v;
}
sort(a, a + tot);
int len = unique(a , a + tot) - a;
int cnt = ;
for (int i = ; i <len; i++) {
f[a[i]] = ++cnt;
}
memset(w, inf64, sizeof(w));
for(int i=;i<=min(m,k);i++)
{
w[f[exa[i].u]][f[exa[i].v]] = exa[i].w;
w[f[exa[i].v]][f[exa[i].u]] = exa[i].w;
}
for (int i = ; i <= cnt; i++) w[i][i] = ;
for(int l=;l<=cnt;l++)
{
for(int i=;i<=cnt;i++)
{
for(int j=;j<=cnt;j++)
{
w[i][j] = min(w[i][j], w[i][l] + w[l][j]);
}
}
}
for(int i=;i<=cnt;i++)
{
for(int j=i+;j<=cnt;j++)
{
e.push_back(w[i][j]);
//printf("w[%d][%d]=%lld\n", i, j, w[i][j]);
}
}
sort(e.begin(), e.end());
// for(int i=0;i<e.size();i++)
// {
// printf("i=%d %lld\n", i, e[i]);
// }
printf("%lld\n", e[k - ]);
return ;
}
这一场打的很差，要加油啊。