CF Round #600 (Div 2) 解题报告（A~E）
A:Single Push
采用差分的思想，让\(b-a=c\)，然后观察\(c\)序列是不是一个满足要求的序列
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int T, n;
int a[maxn], b[maxn];
int c[maxn];
int main()
{
cin >> T;
while(T--)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) c[i] = 0;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
int flag = 1;
for(int i = 1; i <= n; i++)
{
c[i] = b[i] - a[i];
if(c[i] < 0)
{
puts("NO"); flag = 0;
break;
}
}
if(!flag) continue; for(int i = 1; i <= n; i++)
{
if(c[i] == 0) continue;
for(int j = i; j <= n; j++)
{
if(c[i] == c[j])
{
i = j;
continue;
}
else
{
if(c[j] != 0)
{
flag = 0;
break;
}
if(c[j] == 0)
{
for(int k = j; k <= n; k++)
{
if(c[k] != 0)
{
flag = 0;
i = k;
j = k;
break;
}
}
}
}
if(!flag) break;
}
if(!flag) break;
}
if(flag) puts("YES");
else puts("NO");
}
return 0;
}这份代码真是又丑又长...
看了一下CF上学了一下这个写法。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn], n, T, cnt;
bool flag;
int main()
{
scanf("%d", &T);
while(T--)
{
scanf("%d", &n); cnt = 0; flag = 1;
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = 1, x; i <= n; i++)
{
scanf("%d", &x); a[i] = x - a[i];
if(a[i] < 0) flag = 0;
if(a[i] != a[i-1]) cnt++;
}
if(cnt > 2 || (cnt == 2 && a[n] != 0)) flag = 0;
if(flag) puts("YES");
else puts("NO");
}
return 0;
}相比我写的简洁明了了很多。
B:Silly Mistake
暴力模拟就行
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn], n;
int vis[1000000+10];
int cnt, c[maxn];
int isv[1000000+10];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
if(n % 2 == 1)
{
puts("-1");
return 0;
} int tot = 0, num = 0;
vector<int> d;
for(int i = 1, x; i <= n; i++)
{
x = a[i];
if(x > 0)
{
if(vis[x] == 0 && isv[x] == 0)
{
vis[x] = 1; isv[x] = 1;
d.push_back(x); num++;
} else {
puts("-1");
return 0;
}
} else if(x < 0)
{
if(vis[abs(x)] == 1)
{
vis[abs(x)] = 0;
tot += 2;
num -= 1;
}
else if(vis[abs(x)] == 0)
{
puts("-1");
return 0;
}
} if(num == 0)
{
c[++cnt] = tot;
tot = 0;
while(d.size())
{
int xx = d.back();
isv[xx] = 0;
d.pop_back();
}
}
}
if(num != 0)
{
puts("-1");
return 0;
} cout << cnt << endl;
for(int i = 1; i <= cnt; i++)
printf("%d ", c[i]);
puts(""); return 0;
}
C:Sweet Eating
排序+贪心+前缀和
假如说现在考虑一共吃\(i\)颗糖，那么首先肯定的一点是，每天吃\(m\)颗糖，我要尽可能的打满这\(m\)，很显然的贪心。
对于吃\(k\)颗糖，如果不考虑天数要乘上一个数，那么其实就是前缀和。
对于开启了新的一天，实际上是要把糖度高的放到第一天，然后把前面吃\(i-m\)颗糖的糖度加上。
-
这么说可能不太好理解，结合样例来看。
- 目前糖度是\(2,3,4,4\)，\(m=2\)。
- 吃\(1/2\)颗糖结果显然是在第一天都吃完，答案为\(2,5\)。
- 吃\(3\)颗糖的情况就需要我们开启新的一天，那么就是将\(3,4\)放到第一天，\(2\)放到第二天。
- 也就是说\(2\)被翻倍了。\(ans(3)=sum(3)+ans(1)\)
- 吃\(4\)颗糖的情况，那其实就是要把\(2,3\)放到第二天，\(4,4\)放到第一天。\(ans(4)=sum(4)+ans(2)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int a[maxn], n, m;
ll c[maxn];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
sort(a+1, a+1+n);
ll sum = 0;
for(int i = 1; i <= n; i++)
{
sum += a[i]; c[i] = sum;
if(i >= m) c[i] += c[i-m];
}
for(int i = 1; i <= n; i++)
printf("%lld ", c[i]); puts("");
return 0;
}
D: Harmonious Graph
并查集
考虑所有连通块，记录每个连通块中最大的数字。
然后枚举\(i\)，当\(i\)所在的连通块内最大的数字大于\(i\)时，判断\(i\)和\(i+1\)是否在一个连通块中，如果是，则跳过，否则连接\(i\)和\(i+1\)并让\(ans++\)。
#include<bits/stdc++.h>
using namespace std; const int maxn = 2e5 + 10;
int n, m; int fa[maxn], mx[maxn];
int get_fa(int x)
{
if(x == fa[x]) return x;
return fa[x] = get_fa(fa[x]);
} bool merge_dis(int x, int y)
{
x = get_fa(x), y = get_fa(y);
if(x == y) return false;
fa[y] = x;
mx[x] = max(mx[x], mx[y]);
return true;
} int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) fa[i] = mx[i] = i;
for(int i = 1, x, y; i <= m; i++)
{
cin >> x >> y;
merge_dis(x, y);
}
int ans = 0;
for(int i = 1; i <= n; i++)
{
if(mx[get_fa(i)] > i)
{
if(merge_dis(i, i + 1)) ans++;
}
}
cout << ans << endl;
return 0;
}
E：Antenna Coverage
考虑\(f(i)\)表示覆盖\(i\)~\(m\)的最小花费。初态\(f(m+1)=0\)，最后答案为\(f(1)\)。
倒序枚举。
当前枚举到点\(i\)，如果\(i\)已经被覆盖了，那么有\(f(i)=f(i+1)\)。
如果\(i\)没有被覆盖，枚举\(n\)个天线，考虑左端点大于\(i\)的那个天线。
设\(dis=x-s-i\)，即覆盖到区间左端点到\(i\)的距离。
因为同时左右扩展，所以也向右边延伸到了\(dis\)。
那么有\(f(i)=min\{dis+f(x+s+dis)\}\)。
#include<bits/stdc++.h>
using namespace std; const int maxn = 80 + 10;
const int maxm = 1e5 + 10;
int n, m, f[maxm]; struct Node{
int l, r;
bool operator < (Node a){
if(a.l == l) return r < a.r;
return l < a.l;
}
}h[maxn]; int main()
{
scanf("%d%d", &n, &m);
memset(f, 0x3f, sizeof f);
for(int i = 1, p, s; i <= n; i++)
{
scanf("%d%d", &p, &s);
h[i] = {max(p-s, 1), min(p+s, m)};
} sort(h+1, h+1+n); //for(int i=1; i<=n;i++) cout << h[i].l << " " << h[i].r << endl; f[m+1] = 0;
for(int i = m; i > h[n].r; i--)
f[i] = m - i + 1;
for(int i = 1; i <= n; i++)
for(int j = h[i].l; j <= h[i].r; j++)
f[j] = 0; for(int i = m; i >= 1; i--)
{
if(!f[i]) f[i] = f[i+1];
else
{
for(int j = 1; j <= n; j++)
{
if(h[j].l > i)
{
int d = h[j].l - i;
int num = min(h[j].r+d, m);
f[i] = min(f[i], d + f[num+1]);
}
}
}
} cout << f[1] << endl;
return 0;
}