Codeforces #611
前不知名算法竞赛选手被 div 3 血虐现场
div 3 其实有一个好,码量巨大小,但需要思考,适合康 复 训 练
round of greedy
A
倒计时,随便算个式子
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
int main()
{
int t; read(t);
while(t--)
{
int h, m; read(h, m);
int sum = (24 - h - 1) * 60 + (60 - m);
printf("%d\n", sum);
}
}
B
分果子,一种特殊的平均规则,也是随便推推
#include <iostream>
using namespace std;
int main()
{
int t; cin>>t;
while(t--)
{
int a, b; cin>>a>>b;
int res = a % b;
if(res < b / 2) cout<<a<<endl;
else cout<<a - res + b / 2<<endl;
}
return 0;
}
C
给1些链造环。突破口在于单个的点。
其实很久前应该做过类似的题,唉,老了。
提供1种比较容易实现的策略:把单个的点串起来,如果只有1个单的就串一个其他的后面,然后入/出度为零的点随意配对就好了。
#include <iostream>
using namespace std;
const long long maxn = 2e5 + 10;
long long f[maxn];
bool in[maxn], out[maxn];
long long in2[maxn], inc = 0, ou2[maxn], ouc = 0;
long long main()
{
long long n; cin>>n;
long long pre = 0, st = 0, cnt = 0;
for(long long i = 1; i <= n; ++i)
{
cin>>f[i];
if(f[i]) in[f[i]] = true, out[i] = true;
}
for(long long i = 1; i <= n; ++i) if(!in[i] && !out[i]) ++cnt;
if(cnt == 1)
{
for(long long i = 1; i <= n; ++i) if(!in[i] && !out[i]) pre = i;
for(long long i = 1; i <= n; ++i) if(!in[i] && i != pre)
{
f[pre] = i;
in[i] = true; out[pre] = true;
break;
}
}
else if(cnt > 1)
{
for(long long i = 1; i <= n; ++i) if(!in[i] && !out[i])
{
if(pre) in[f[i] = pre] = true, out[i] = true;
pre = i;
}
}
for(long long i = 1; i <= n; ++i)
{
if(!in[i]) in2[inc++] = i;
if(!out[i]) ou2[ouc++] = i;
}
for(long long i = 0; i < inc; ++i) f[ou2[i]] = in2[i];
for(long long i = 1; i <= n; ++i)
cout<<f[i]<<" ";
return 0;
}
D
安排一些人到一些位置,使得离最近的树的距离总和最小。人不能重叠。
很经典的多源bfs模型,可是俺不会了,可恶。
#include <iostream>
#include <map>
#include <vector>
#include <queue>
using namespace std;
queue<long long> q;
map<long long, long long> d;
vector<long long> v;
int main()
{
long long n, m; cin>>n>>m;
vector<long long> x(n);
for(long long i = 0; i < n; ++i)
{
cin>>x[i];
q.push(x[i]); d[x[i]] = 0;
}
long long ans = 0;
while(!q.empty())
{
if(v.size() == m) break;
long long k = q.front(); q.pop();
if(d[k]) ans += d[k], v.push_back(k);
if(!d.count(k - 1)) q.push(k - 1), d[k - 1] = d[k] + 1;
if(!d.count(k + 1)) q.push(k + 1), d[k + 1] = d[k] + 1;
}
cout<<ans<<endl;
for(auto iter : v) cout<<iter<<" ";
return 0;
}
E
每个人可以当相邻房子或者不动。求最少/多占据房子树。
这是两个独立问题。被坑了,往dp想了。可恶。
最小的话,注意每连续三个位置,只要有东西必然最后可以只占一个位置。贪心就好了。
最大的话,每个连续段的人数大于段的长度的话,就可以往左或者往右扩展各最大一格。然后处理以下边界情况,具体就是往左边扩展的那个格会不会被上次盖到。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 10;
int f[maxn][2], cnt[maxn];
int main()
{
int n; cin>>n;
for(int i = 0, j; i < n; ++i) cin>>j, ++cnt[j];
int _min = 0;
for(int i = 0; i <= n; ++i)
{
if(!cnt[i]) continue;
else _min += 1, i += 2;
}
int _max = 0, len = 0;
bool right = false;
for(int i = 0; i <= n; ++i)
{
if(!cnt[i]){++len; continue;}
int j = i, sum = 0;
for(; cnt[j]; ++j) sum += cnt[j];
_max += j - i;
if(sum > j - i && (!right || len > 1)) --sum, ++_max;
right = false;
if(sum > j - i) ++_max, right = true;
i = j;
len = 1;
}
cout<<_min<<" "<<_max<<endl;
return 0;
}
F
觉得是1道好题,不枉做这套题叻。
每个点的权是这个节点编号的2的幂。每个边的权是子树点权和。给每一条边的排名和对应他们的爸爸,求复原这棵树。
也事贪心,,,
诉诸这样一种策略:把相邻出现的两个点连起来,连不起来的话,就从大到小可以选的点里选一个。
这是正确的因为二的幂永远比比它小的二的幂的和要大。所以大的点不出现在这里的话也不能出现在其他地方。
#include <iostream>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
bool flag[maxn];
int main()
{
int n; cin>>n;
for(int i = 1; i < n; ++i) cin>>a[i];
cout<<a[1]<<endl;
int cur = n;
for(int i = 1; i < n; ++i)
{
flag[a[i]] = true;
while(flag[cur]) --cur;
if(i == n - 1 || flag[a[i + 1]])
{
cout<<a[i]<<" "<<cur<<endl;
flag[cur] = true;
}
else
{
cout<<a[i]<<" "<<a[i + 1]<<endl;
}
}
return 0;
}