从这里开始
- 题目列表
- 瞎扯
- Problem A Find a Number
- Problem B Berkomnadzor
- Problem C Cloud Computing
- Problem D Garbage Disposal
- Problem E Getting Deals Done
- Problem F Debate
- Problem G Monsters and Potions
- Problem H BerOS File Suggestion
- Problem I Privatization of Roads in Berland
- Problem J Streets and Avenues in Berhattan
- Problem K Video Posts
- Problem L Odd Federalization
- Problem M Algoland and Berland
瞎扯
又来打比赛了，发现自己菜得不行。
果然我是标准的普及组选手。（这个队名是啥意思？我也不知道，因为不知道取啥队名，就随机在键盘上敲Emmm）
这次队友很给力，把我不会的模拟和贪心全切掉了，并且每次翻译了正确的题意（我英语真垃圾）。（上次UESTC ACM Final的队友让我很绝望，既不会做题又给我翻译假题面）
然后我把剩下的送分题都切掉了。
于是被碾压了：
开始通读全题（提供pdf真良心，避免网卡耽误时间），我觉得很绝望，尤其是那个B，读得我很绝望，直接扔翻译里都弃了。
之后并不知道怎么做题，然后随机一道题，发现是水题是一道水题就直接切掉了。
之后就开始看榜，那个题通过的队多就做哪个。
佬表示这个不是正确的做法，正确的做法是每个人随机若干道题，先自己去做，不会的话然后扔给队友。
挂掉的话也可以扔队友。
但是我和我队友都挺菜的，这么搞可能完蛋了。
下来发现B，J都是送分题。
Problem A Find a Number
题目大意
问最小的满足各位数字之和为$s$并且能被$d$整除的正整数。
首先用bfs确定它的位数，每个状态记录通过尽量小的转移边转移的前驱。
然后做完了。
Code
/**
* Codeforces
* Problem#1070A
* Accepted
* Time: 108ms
* Memory: 24800k
* Author: yyf
*/
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
typedef bool boolean; const int N = , D = ;
#define pii pair<int, int>
#define fi first
#define sc second int d, s;
int f[N][D];
char lst[N][D];
int lstr[N][D];
boolean vis[N][D]; pii trans(int s, int r, int dig) {
return pii(s + dig, (r * + dig) % d);
} inline void init() {
scanf("%d%d", &d, &s);
} queue<pii> que;
boolean bfs() {
que.push(pii(, ));
memset(f, 0x3f, sizeof(f));
f[][] = , vis[][] = true;
while (!que.empty()) {
pii e = que.front();
que.pop(); for (int i = ; i <= ; i++) {
pii eu = trans(e.fi, e.sc, i);
if (eu.fi > s)
break;
if (vis[eu.fi][eu.sc])
continue;
vis[eu.fi][eu.sc] = true;
lst[eu.fi][eu.sc] = i + '';
lstr[eu.fi][eu.sc] = e.sc;
f[eu.fi][eu.sc] = f[e.fi][e.sc] + ;
que.push(eu);
}
}
return vis[s][];
} void print(int s, int r) {
if (!s && !r)
return ;
int nr = lstr[s][r];
print(s - lst[s][r] + '', nr);
putchar(lst[s][r]);
} inline void solve() {
if (bfs()) {
print(s, );
} else
puts("-1");
} int main() {
init();
solve();
return ;
}
Problem A
Problem B Berkomnadzor
题目大意
给定一个IPv4白名单和黑名单，要求用最少的IPv4码给出一个包含所有黑名单中的地址但不包含任何一个白名单里的地址。
先判掉无解的情况。
剩下直接分治。
Code
/**
* Codeforces
* Problem#1070B
* Accepted
* Time: 530ms
* Memory: 52800k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; #define ull unsigned long long
#define pii pair<int, int>
#define ll long long
#define ui unsigned
#define sc second
#define fi first const signed ll llf = (signed ll) (~0ull >> );
const signed int inf = (signed) (~0u >> ); template <typename T>
T __abs(T x) {
return (x < ) ? (-x) : (x);
} template <typename T>
void pfill(T* pst, const T* ped, T val) {
for ( ; pst != ped; *(pst++) = val);
} template <typename T>
void pcopy(T* pst, const T* ped, T* pv) {
for ( ; pst != ped; *(pst++) = *(pv++));
} #define digit(_x) ((_x) >= '0' && (_x) <= '9') template <typename T>
char* read(char* s, T& u) {
for ( ; *s && !digit(*s); s++);
if (!*s)
return NULL;
for (u = *s - ''; ++s, digit(*s); u = u * + *s - '');
return s;
} const int N = 2e5 + ; typedef class Segment {
public:
ui l, r;
ui sgn; Segment() { }
Segment(ui l, ui r, ui sgn):l(l), r(r), sgn(sgn) { } boolean operator < (Segment b) const {
if (l ^ b.l)
return l < b.l;
return r < b.r;
} boolean intersect(Segment b) {
return !(b.r < l || b.l > r);
}
}Segment; int n;
char buf[]; Segment read() {
ui l, r, x;
scanf("%s", buf);
ui sgn = (buf[] == '+');
char* str = buf + ;
str = read(str, l);
str = read(str, x), l = l << | x;
str = read(str, x), l = l << | x;
str = read(str, x), l = l << | x;
if (*str == '/') {
read(str, x);
x = - x;
l >>= x, l <<= x;
if (x == )
r = ~0u;
else
r = l | (( << x) - );
return Segment(l, r, sgn);
}
return Segment(l, l, sgn);
} int res = ;
vector<Segment> ss, rs; inline void init() {
scanf("%d", &n);
Segment s;
for (int i = ; i <= n; i++)
s = read(), ss.push_back(s);
} void dividing(vector<Segment> &ss, ui l, ui r, ui bit) {
if (ss.empty())
return;
boolean app1 = false, app0 = false;
for (ui i = ; i < ss.size(); i++)
app1 |= (ss[i].sgn == ), app0 |= (ss[i].sgn == ); if (!app1) {
rs.push_back(Segment(l, - bit, ));
return;
} if (!app0)
return; assert(l ^ r); ui mid = l + ((r - l) >> );
vector<Segment> ql, qr;
for (ui i = ; i < ss.size(); i++) {
if (ss[i].r <= mid)
ql.push_back(ss[i]);
else if (ss[i].l > mid)
qr.push_back(ss[i]);
else {
ql.push_back(Segment(ss[i].l, mid, ss[i].sgn));
qr.push_back(Segment(mid + , ss[i].r, ss[i].sgn));
}
}
ss.clear();
dividing(ql, l, mid, bit - );
dividing(qr, mid + , r, bit - );
} inline void solve() {
sort(ss.begin(), ss.end());
for (ui i = , j; i < ss.size(); i = j)
for (j = i + ; j < ss.size() && ss[j].intersect(ss[i]); j++)
if (ss[j].sgn ^ ss[i].sgn) {
puts("-1");
return;
}
dividing(ss, , ~0u, );
printf("%u\n", rs.size());
ui msk = ( << ) - ;
for (ui i = , x; i < rs.size(); i++) {
x = rs[i].l;
printf("%u.%u.%u.%u/%u\n", x >> , x >> & msk, x >> & msk, x & msk, rs[i].r);
}
} int main() {
init();
solve();
return ;
}
Problem B
Problem C Cloud Computing
题目大意
一个公司每天需要$K$个CPU内核，有$m$个供应商，在第$l_i$到第$r_i$天，以每个CPU内核$p_i$的价格提供$c_i$个，如果一天买不够，那么必须把能够提供的内核都购买。问最小的总花费。
随便拿个数据结构就过了。
Code
/**
* Codeforces
* Problem#1070C
* Accepted
* Time: 249ms
* Memory: 28000k
* Author: yyf
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
using namespace std;
typedef bool boolean; typedef class Opt {
public:
int i, p, c;
int sgn; Opt(int i, int p, int c, int sgn):i(i), p(p), c(c), sgn(sgn) { } boolean operator < (Opt b) const {
return i < b.i;
}
}Opt; const int bzmax = ; template <typename T>
class IndexedTree {
public:
int s;
T* ar; IndexedTree() { }
IndexedTree(int s):s(s) {
ar = new T[(s + )];
memset(ar, , sizeof(T) * (s + ));
} void add(int idx, T val) {
for ( ; idx <= s; idx += (idx & (-idx)))
ar[idx] += val;
} T query(int idx) {
T rt = ;
for ( ; idx; idx -= (idx & (-idx)))
rt += ar[idx];
return rt;
} int kth(int k) {
int rt = , cur = ;
for (int l = ( << (bzmax - )); l; l >>= )
if ((rt | l) <= s && (cur + ar[rt | l]) < k)
rt |= l, cur += ar[rt];
return rt + ;
}
}; #define ll long long const int V = 1e6 + ; int n, K, m;
IndexedTree<ll> itc;
IndexedTree<ll> its;
vector<Opt> vs; inline void init() {
scanf("%d%d%d", &n, &K, &m);
itc = IndexedTree<ll>(V);
its = IndexedTree<ll>(V);
for (int i = , l, r, c, p; i <= m; i++) {
scanf("%d%d%d%d", &l, &r, &c, &p);
vs.push_back(Opt(l, p, c, ));
vs.push_back(Opt(r + , p, c, -));
}
} ll res = ;
inline void solve() {
sort(vs.begin(), vs.end());
int pv = , s = (signed) vs.size();
for (int i = ; i <= n; i++) {
while (pv < s && vs[pv].i == i) {
itc.add(vs[pv].p, vs[pv].c * vs[pv].sgn);
its.add(vs[pv].p, vs[pv].c * 1ll * vs[pv].p * vs[pv].sgn);
pv++;
}
ll cnt = itc.query(V);
if (cnt < K) {
res += its.query(V);
} else {
int p = itc.kth(K);
cnt = itc.query(p);
res += its.query(p) - (cnt - K) * p;
}
}
cout << res << endl;
} int main() {
init();
solve();
return ;
}
Problem C
Problem D Garbage Disposal
题目大意
每天会产生若干垃圾，每天的垃圾只能当天或者后天处理，第$n + 1$天不能留下垃圾。每次处理垃圾至多能处理$k$个单位，问最少的总处理次数。
随便模拟一下就过了。
Code
//Author: dream_maker
#include<bits/stdc++.h>
using namespace std;
//----------------------------------------------
//typename
typedef long long ll;
//convenient for
#define fu(a, b, c) for (int a = b; a <= c; ++a)
#define fd(a, b, c) for (int a = b; a >= c; --a)
#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)
//inf of different typename
const int INF_of_int = 1e9;
const ll INF_of_ll = 1e18;
//fast read and write
template <typename T>
void Read(T &x) {
bool w = ;x = ;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') w = , c = getchar();
while (isdigit(c)) {
x = (x<<) + (x<<) + c -'';
c = getchar();
}
if (!w) x = -x;
}
template <typename T>
void Write(T x) {
if (x < ) {
putchar('-');
x = -x;
}
if (x > ) Write(x / );
putchar(x % + '');
}
//----------------------------------------------
const int N = 3e5 + ;
ll a[N], n, k, ans = ;
int main() {
Read(n), Read(k);
fu(i, , n) Read(a[i]);
fu(i, , n - ) {
if (!a[i]) continue;
ll num = a[i] / k;
if (a[i] % k) ++num;
a[i + ] = max(0ll, a[i + ] - (num * k - a[i]));
ans += num;
}
if (a[n]) {
ans += a[n] / k;
if (a[n] % k) ++ans;
}
Write(ans);
return ;
}
Problem D
Problem E Getting Deals Done
题目大意
有$n$个任务和参数$m$，每个任务有一个耗时$p_i$，以及时限$t$，要求出$d$使得按照下面方式完成的任务尽量多。
- 按顺序完成$p_i \leqslant d$的任务
- 每做$m$个任务需要休息与做这$m$个任务花费的时间相等的时间。
yangkai觉得这玩意儿可以三分，于是我们成功得到了-5.
发现有用的$d$一定时某个$p_i$，可以把$p_i$排序，按顺序插进树状数组。
每次可以二分一下求出能够完成的任务的数量。
时间复杂度$O(n\log^{2} n)$。
但是这个可以二分答案。
判断条件是是否能够把所有可做的任务做完。
答案只可能是它或者它加上1后的情况，
因为再大的时候不会花更少的时间去做数量相同的任务。
然后我的垃圾做法就被暴打了。
然后注意几个地方：
- $p$相同的任务要一起加入树状数组
- 树状数组求第$k$大特判$k = 0$。
继续口胡一个做法，考虑按顺序枚举序列，同时对所有 $d$ 维护当前花费的时间以及完成的任务数，超时的总是 $d$ 最大的几个，用一个变量维护当前最大的没有超时的 $d$，check 它是否超时可以再开 2 个 BIT。
Code
/**
* Codeforces
* Problem#1070E
* Accepted
* Time: 608ms
* Memory: 4700k
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean;
#define ll long long template <typename T>
class IndexedTree {
public:
int s;
T* ar; IndexedTree() { }
IndexedTree(int s):s(s) {
ar = new T[(s + )];
memset(ar, , sizeof(T) * (s + ));
} void add(int idx, T val) {
for ( ; idx <= s; idx += (idx & (-idx)))
ar[idx] += val;
} T query(int idx) {
T rt = ;
for ( ; idx; idx -= (idx & (-idx)))
rt += ar[idx];
return rt;
} int kth(int k) {
if (!k)
return ;
int rt = , cur = ;
for (int i = ( << ); i; i >>= )
if ((rt | i) <= s && ar[rt | i] + cur < k)
rt |= i, cur += ar[rt];
return rt + ;
} void clear() {
s = ;
delete[] ar;
}
}; const int N = 2e5 + ;
#define pii pair<int, int>
#define fi first
#define sc second int T;
int n, m;
ll t;
IndexedTree<int> itc;
IndexedTree<ll> its;
int ps[N];
pii ar[N]; inline void init() {
scanf("%d%d"Auto, &n, &m, &t);
itc = IndexedTree<int>(n);
its = IndexedTree<ll>(n);
for (int i = ; i <= n; i++)
scanf("%d", ps + i), ar[i] = pii(ps[i], i);
} int query(int i) {
int l = , r = i, mid, k, ti;
ll s = ;
while (l <= r) {
mid = (l + r) >> ;
k = itc.kth(mid);
s = its.query(k);
ti = (mid - ) / m * m;
k = itc.kth(ti);
s += its.query(k);
if (s > t)
r = mid - ;
else
l = mid + ;
}
return l - ;
} inline void solve() {
int ansc = , ansd = ;
sort(ar + , ar + n + );
int i = , c;
while (i <= n) {
int cur = ar[i].fi;
while (i <= n && ar[i].fi == cur) {
itc.add(ar[i].sc, );
its.add(ar[i].sc, ar[i].fi);
i++;
}
c = query(i - );
if (c > ansc)
ansc = c, ansd = ar[i - ].fi;
}
printf("%d %d\n", ansc, ansd);
} void clear() {
itc.clear();
its.clear();
} int main() {
scanf("%d", &T);
while (T--) {
init();
solve();
clear();
}
return ;
}
Problem E
Problem F Debate
题目大意
有$n$个观众，每个观众有一个观点是否支持$Alice$以及支持$Bob$，和一个影响度。
要求选出一些人使得至少有一半的人支持$Alice$和一半的人支持$Bob$，最大化他们的影响度之和。
两者都支持的一定全选。
然后支持一方的配对选。
剩下的再怎么选都不会改变还能选多少人，直接贪。
Code
//Author: dream_maker
#include<bits/stdc++.h>
using namespace std;
//----------------------------------------------
//typename
typedef long long ll;
//convenient for
#define fu(a, b, c) for (int a = b; a <= c; ++a)
#define fd(a, b, c) for (int a = b; a >= c; --a)
#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)
//inf of different typename
const int INF_of_int = 1e9;
const ll INF_of_ll = 1e18;
//fast read and write
template <typename T>
void Read(T &x) {
bool w = ;x = ;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') w = , c = getchar();
while (isdigit(c)) {
x = (x<<) + (x<<) + c -'';
c = getchar();
}
if (!w) x = -x;
}
template <typename T>
void Write(T x) {
if (x < ) {
putchar('-');
x = -x;
}
if (x > ) Write(x / );
putchar(x % + '');
}
//----------------------------------------------
deque<ll> p[];
ll n, w, ans = ;
char s[];
bool cmp(ll a, ll b) {
return a > b;
}
int main() {
Read(n);
fu(i, , n) {
scanf("%s", s);
Read(w);
if (s[] == '') {
if (s[] == '') p[].push_back(w);
else p[].push_back(w);
} else {
if (s[] == '') p[].push_back(w);
else p[].push_back(w);
}
}
fu(i, , ) sort(p[i].begin(), p[i].end(), cmp);
ll ans = , num = , cnt0 = , cnt1 = ;
fv(i, p[]) {
ans += p[][i];
num++;
cnt0++, cnt1++;
}
while (p[].size() && p[].size()) {
num += ;
cnt1++, cnt0++;
ans += p[].front() + p[].front();
p[].pop_front();
p[].pop_front();
}
int last = cnt1 * - num;
while (last--) {
if (!p[].size() && !p[].size() && !p[].size()) break;
if (p[].size()) {
bool can = ;
if (p[].size() && p[].front() > p[].front()) can = ;
if (p[].size() && p[].front() > p[].front()) can = ;
if (can) {
ans += p[].front();
p[].pop_front();
continue;
}
}
if (p[].size()) {
bool can = ;
if (p[].size() && p[].front() > p[].front()) can = ;
if (p[].size() && p[].front() > p[].front()) can = ;
if (can) {
ans += p[].front();
p[].pop_front();
continue;
}
}
if (p[].size()) {
bool can = ;
if (p[].size() && p[].front() > p[].front()) can = ;
if (p[].size() && p[].front() > p[].front()) can = ;
if (can) {
ans += p[].front();
p[].pop_front();
continue;
}
}
}
/*if (p[1].size()) {
while (cnt1 * 2 > num && cnt0 * 2 > num) {
if (!p[1].size() && !p[0].size()) break;
if (!p[1].size() || !p[0].size()) {
if (!p[1].size()) {
num++;
ans += p[0].front();
p[0].pop_front();
} else {
num++, cnt0++;
ans += p[1].front();
p[1].pop_front();
}
}
if (p[0].front() > p[1].front()) {
num++;
ans += p[0].front();
p[0].pop_front();
} else {
num++, cnt0++;
ans += p[1].front();
p[1].pop_front();
}
}
} else if (p[2].size()) {
while (cnt1 * 2 > num && cnt0 * 2 > num) {
if (!p[2].size() && !p[0].size()) break;
if (!p[2].size() || !p[0].size()) {
if (!p[2].size()) {
num++;
ans += p[0].front();
p[0].pop_front();
} else {
num++, cnt1++;
ans += p[2].front();
p[2].pop_front();
}
}
if (p[0].front() > p[2].front()) {
num++;
ans += p[0].front();
p[0].pop_front();
} else {
num++, cnt1++;
ans += p[2].front();
p[2].pop_front();
}
}
}
while (p[0].size() && cnt1 * 2 > num && cnt0 * 2 > num) {
num++;
ans += p[0].front();
p[0].pop_front();
}*/
Write(ans);
return ;
}
Problem F
Problem G Monsters and Potions
题目大意
（请耐心读原题）
暴力枚举拉力点，暴力枚举一下动的英雄。（能动就直接移动，不是爆搜）
很好奇为什么只有100多个队过。
Code
//Author: dream_maker
#include<bits/stdc++.h>
using namespace std;
//----------------------------------------------
//typename
typedef long long ll;
//convenient for
#define fu(a, b, c) for (int a = b; a <= c; ++a)
#define fd(a, b, c) for (int a = b; a >= c; --a)
#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)
//inf of different typename
const int INF_of_int = 1e9;
const ll INF_of_ll = 1e18;
//fast read and write
template <typename T>
void Read(T &x) {
bool w = ;x = ;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') w = , c = getchar();
while (isdigit(c)) {
x = (x<<) + (x<<) + c -'';
c = getchar();
}
if (!w) x = -x;
}
template <typename T>
void Write(T x) {
if (x < ) {
putchar('-');
x = -x;
}
if (x > ) Write(x / );
putchar(x % + '');
}
//----------------------------------------------
const int N = ;
ll n, m;
ll s[N], h[N], p[N];
ll now[N], tp[N], tot;
bool wk[N];
void init() {
fu(i, , n) now[i] = p[i];
memset(tp, , sizeof(tp));
memset(wk, , sizeof(wk));
tot = ;
}
bool check_walk(ll fro, ll to, ll vl) {
if (fro == to) return ;
if (fro > to) {
fd(i, fro, to) {
if (now[i] < && vl + now[i] < ) return ;
vl += now[i];
}
return ;
} else {
fu(i, fro, to) {
if (now[i] < && vl + now[i] < ) return ;
vl += now[i];
}
return ;
}
}
void get_clean(ll l, ll r) {
if (l >= r) {
fd(i, l, r) now[i] = ;
} else {
fu(i, l, r) now[i] = ;
}
}
struct Node {
int id, dis;
} w[N];
bool cmp(Node a, Node b) {
return a.dis < b.dis;
}
bool check(int pos) {
init();
fu(i, , m) {
w[i].id = i;
w[i].dis = labs(pos - s[i]);
}
sort(w + , w + m + , cmp);
fu(i, , m) {
if (check_walk(s[w[i].id], pos, h[w[i].id])) {
tp[++tot] = w[i].id;
get_clean(s[w[i].id], pos);
wk[w[i].id] = ;
}
}
fu(i, , m) {
if (!wk[w[i].id]) {
if (!check_walk(s[w[i].id], pos, h[w[i].id])) return ;
tp[++tot] = w[i].id;
wk[w[i].id] = ;
}
}
Write(pos); putchar('\n');
fu(i, , m) {
Write(tp[i]);
putchar(' ');
}
return ;
}
int main() {
Read(n), Read(m);
fu(i, , m) Read(s[i]), Read(h[i]);
fu(i, , n) Read(p[i]);
fu(i, , n)
if (check(i)) return ;
printf("-1");
return ;
}
Problem G
Problem H BerOS File Suggestion
题目大意
给定$n$个字符串，每次询问一个字符串，问有多少个字符串包含它作为子串，然后要求随便输出$n$个串中任意一个满足条件的串。
居然有人写AC自动机。牛逼。
我直接Hash。好像可以直接开一个string映射到xxx的map。
感觉我对STL一无所知。
Code
/**
* Codeforces
* Problem#1070E
* Accepted
* Time: 234ms
* Memory: 15900k
* Author: yyf
*/
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <map>
using namespace std;
typedef bool boolean;
#define ull unsigned long long ull base = ; const int N = 1e4 + ; int n, q;
char strs[N][];
map<ull, int> cnt;
map<ull, int> lst; inline void init() {
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%s", strs[i]);
char *s = strs[i];
for (int l = ; s[l]; l++) {
ull ha = ;
for (int r = l; s[r]; r++) {
ha = ha * base + s[r];
if (lst[ha] != i) {
lst[ha] = i;
cnt[ha]++;
// cerr << "added" << " " << ha << endl;
}
}
}
}
} char str[];
inline void solve() {
scanf("%d", &q);
while (q--) {
scanf("%s", str);
ull ha = ;
for (int i = ; str[i]; i++)
ha = ha * base + str[i];
int r1 = cnt[ha];
if (r1)
printf("%d %s\n", r1, strs[lst[ha]]);
else
puts("0 -");
}
} int main() {
init();
solve();
return ;
}
Problem H
Problem I Privatization of Roads in Berland
题目大意
给定一个$n$个点$m$条边的无向图，有足够多个公司，将每条边分配给一个公司，满足：
- 一个公司最多拥有两条边
- 每个顶点相邻的边至多被分给$K$个公司。
容易发现，如果一个公司拥有了两条边，那么它存在一个公共顶点会比较优。
考虑如果一个顶点的度数大于$K$，那么我们就要硬点它周边$2(d - k)$条边两两配对。
然后每条边建一个点做匹配就完了。
Code
/**
* Codeforces
* Problem#1070I
* Accepted
* Time: 31ms
* Memory: 200k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; #define ull unsigned long long
#define pii pair<int, int>
#define ll long long
#define ui unsigned
#define sc second
#define fi first const signed ll llf = (signed ll) (~0ull >> );
const signed int inf = (signed) (~0u >> ); template <typename T>
T __abs(T x) {
return (x < ) ? (-x) : (x);
} template <typename T>
void pfill(T* pst, const T* ped, T val) {
for ( ; pst != ped; *(pst++) = val);
} template <typename T>
void pcopy(T* pst, const T* ped, T* pv) {
for ( ; pst != ped; *(pst++) = *(pv++));
} typedef class Edge {
public:
int ed, nx, cap, f; Edge() { }
Edge(int ed, int nx, int cap, int f):ed(ed), nx(nx), cap(cap), f(f) { }
}Edge; typedef class MapManager {
public:
int *h;
vector<Edge> es; MapManager() { }
MapManager(int n) {
h = new int[(n + )];
pfill(h, h + n + , -);
} void addEdge(int u, int v, int cap, int f) {
es.push_back(Edge(v, h[u], cap, f));
h[u] = (signed) es.size() - ;
} void addArc(int u, int v, int cap) {
addEdge(u, v, cap, );
addEdge(v, u, cap, cap);
} Edge& operator [] (int p) {
return es[p];
} void clear() {
delete[] h;
es.clear();
}
}MapManager; const int N = ; int n, m, K;
int s = , t;
int mxcap;
int deg[N];
MapManager g; inline void init() {
scanf("%d%d%d", &n, &m, &K);
pfill(deg, deg + n + , );
g = MapManager(n + m + );
for (int i = , u, v; i <= m; i++) {
scanf("%d%d", &u, &v);
deg[u]++, deg[v]++;
g.addArc(, i, );
g.addArc(i, u + m, );
g.addArc(i, v + m, );
}
t = n + m + , mxcap = ;
for (int i = ; i <= n; i++)
if (deg[i] > K)
g.addArc(i + m, t, (deg[i] - K) << ), mxcap += deg[i] - K;
mxcap <<= ;
} int cur[N << ], _div[N << ]; int dfs(int p, int mf) {
if (p == t || !mf)
return mf;
int f, flow = ;
for (int& i = cur[p], e; ~i; i = g[i].nx) {
e = g[i].ed;
if (g[i].f < g[i].cap && _div[e] == _div[p] + && (f = dfs(e, min(mf, g[i].cap - g[i].f))) > ) {
g[i].f += f;
g[i ^ ].f -= f;
mf -= f;
flow += f;
if (!mf)
break;
}
}
return flow;
} queue<int> que;
boolean bfs() {
pfill(_div, _div + t + , -);
_div[s] = ;
que.push(s);
while (!que.empty()) {
int e = que.front();
que.pop();
for (int i = g.h[e], eu; ~i; i = g[i].nx) {
eu = g[i].ed;
if (g[i].cap == g[i].f)
continue;
if (~_div[eu])
continue;
_div[eu] = _div[e] + ;
que.push(eu);
}
}
return _div[t] != -;
} int dinic() {
int rt = ;
while (bfs()) {
pcopy(cur, cur + t + , g.h);
rt += dfs(s, inf);
}
return rt;
} int lab[N];
vector<int> mat[N]; inline void solve() {
int flow = dinic(), used = ; if (flow != mxcap) {
for (int i = ; i <= m; i++)
printf("0 ");
putchar('\n');
return;
} for (int i = ; i <= n; i++)
mat[i].clear(); for (int i = ; i <= m; i++)
for (int j = g.h[i]; ~j; j = g[j].nx)
if (g[j].cap == g[j].f && g[j].ed > m) {
mat[g[j].ed - m].push_back(i);
break;
} pfill(lab + , lab + m + , );
for (int i = , a, b; i <= n; i++)
while (!mat[i].empty()) {
a = mat[i].back();
mat[i].pop_back();
b = mat[i].back();
mat[i].pop_back(); lab[a] = lab[b] = ++used;
} for (int i = ; i <= m; i++) {
if (!lab[i])
lab[i] = ++used;
printf("%d ", lab[i]);
}
putchar('\n');
} inline void clear() {
g.clear();
} int T;
int main() {
scanf("%d", &T);
while (T--) {
init();
solve();
clear();
}
return ;
}
Problem I
Problem J Streets and Avenues in Berhattan
题目大意
给定一个长度为$K$的字母串，以及$n, m$，要求在$K$中选出不同位置的$n$个字符和$m$个字符，使得$n$个字符中和$m$字符中相同的对数尽量小。
容易发现算贡献的只有一种字符。
然后枚举它，随便dp一下就过了。
时间复杂度$O(n|\Sigma|^2)$
感觉用多项式除法可以去掉一个平方。
Code
/**
* Codeforces
* Problem#1070J
* Accepted
* Time: 46ms
* Memory: 1200k
* Author: yyf
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; template <typename T>
void pfill(T* pst, const T* ped, T val) {
for ( ; pst != ped; *(pst++) = val);
} const int N = 2e5 + , Alpha = ; int T;
int n, m, K;
int cnt[Alpha];
boolean f[N];
int g[N];
char str[N]; inline void init() {
scanf("%d%d%d", &n, &m, &K);
scanf("%s", str);
pfill(cnt, cnt + Alpha, );
for (char *p = str; *p; p++)
cnt[*p - 'A']++;
} inline void solve() {
int res = (signed) (~0u >> );
for (int i = , used, diff; i < Alpha && res; i++) {
pfill(f, f + K + , false);
f[] = true;
for (int c = , s = ; c < Alpha; c++)
if (cnt[c] && (c ^ i)) {
for (int j = s; ~j; j--)
f[j + cnt[c]] |= f[j];
s += cnt[c];
} for (int j = ; j <= K; j++)
g[j] = (f[j] ? j : K + );
for (int j = K - ; ~j; j--)
g[j] = min(g[j + ], g[j]); for (int c = ; c <= cnt[i] && c <= n && res; c++) {
used = g[n - c] + c;
if (K - used >= m) {
diff = K - cnt[i] - g[n - c];
if (diff >= m)
res = ;
else
res = min(res, (m - diff) * c);
}
}
}
printf("%d\n", res);
} int main() {
scanf("%d", &T);
while (T--) {
init();
solve();
}
return ;
}
Problem J
Problem K Video Posts
题目大意
（没听过）
（听说是普及题）
Code
//Author: dream_maker
#include<bits/stdc++.h>
using namespace std;
//----------------------------------------------
//typename
typedef long long ll;
//convenient for
#define fu(a, b, c) for (int a = b; a <= c; ++a)
#define fd(a, b, c) for (int a = b; a >= c; --a)
#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)
//inf of different typename
const int INF_of_int = 1e9;
const ll INF_of_ll = 1e18;
//fast read and write
template <typename T>
void Read(T &x) {
bool w = ;x = ;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') w = , c = getchar();
while (isdigit(c)) {
x = (x<<) + (x<<) + c -'';
c = getchar();
}
if (!w) x = -x;
}
template <typename T>
void Write(T x) {
if (x < ) {
putchar('-');
x = -x;
}
if (x > ) Write(x / );
putchar(x % + '');
}
//----------------------------------------------
const int N = 1e5 + ;
ll n, k, a[N], ans[N];
int main() {
Read(n), Read(k);
fu(i, , n) Read(a[i]), a[i] += a[i - ];
if (a[n] % k) {
printf("No");
return ;
}
ll len = a[n] / k, last = , tot = ;
fu(i, , n) {
if (a[i] - a[last] == len) {
ans[++tot] = i - last;
last = i;
} else if(a[i] - a[last] > len) {
printf("No");
return ;
}
}
printf("Yes\n");
fu(i, , k) {
Write(ans[i]);
putchar(' ');
}
return ;
}
Problem K
Problem L Odd Federalization
题目大意
要求把$n$个点$m$条边分成$r$个部分，使得每一部分每个点的度都是偶数（不看不在同一部分内的边），问最小的$r$和方案。
首先来猜想答案小于等于2.
然后把每个点在哪个集合看成未知数$x_i$。
用异或算一下每个点被割掉的边的奇偶性，然后就可以列方程了。
高斯消元 + bitset就可以过了。
证明可以见：http://codeforces.com/blog/entry/62570?#comment-465420 （orz Um_nik）
没怎么看懂。然后我来口胡两句。
如果上面的方程存在解，答案一定小于等于2.否则必然存在若干行在模2意义下的向量加得到零向量，并且对应常数项加起来同于1。
不妨设这些点是$1, 2, \dots, k$，对应的行向量是$\overrightarrow{x_{1}},\overrightarrow{x_2},\dots,\overrightarrow{x_k}$，这些行对应的常数项是$y_1, y_2, \dots, y_k$。
由列方程的方法可以知道$y_i \equiv deg_i \pmod{2}$
那么设$\sum_{i = 1}^{k} y_{i}\equiv \sum_{i = 1}^{k} deg_{i} = D \pmod{2}$，因为$\overrightarrow{x_{1}} + \overrightarrow{x_2} + \cdots + \overrightarrow{x_k} = \vec{0}$，所以当某个点的标号$a > k$时，那么$1$到$k$中的点与它相连的边的数量一定是偶数（不然这一维得到的和不是0），假设这一部分总边数是$E$，那么我们愉快地得到了$D\equiv D - E$。
我们考虑$D - E$有着什么美妙的意义。我们考虑$G' = (V' = \left \{1, 2, \cdots, k\right \}, E')$这个诱导子图。$D - E$把满足$x \in V', y\not \in V'$的边$(x, y)$的贡献除去，因此$D - E$等于这个诱导子图中所有点的度数之和。它不可能是奇数。所以$D \equiv 0\pmod{2}$。
Code
/**
* Codeforces
* Problem#1070L
* Accepted
* Time: 93ms
* Memory: 500k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; #define ull unsigned long long
#define pii pair<int, int>
#define ll long long
#define ui unsigned
#define sc second
#define fi first const signed ll llf = (signed ll) (~0ull >> );
const signed int inf = (signed) (~0u >> ); template <typename T>
T __abs(T x) {
return (x < ) ? (-x) : (x);
} template <typename T>
void pfill(T* pst, const T* ped, T val) {
for ( ; pst != ped; *(pst++) = val);
} template <typename T>
void pcopy(T* pst, const T* ped, T* pv) {
for ( ; pst != ped; *(pst++) = *(pv++));
} const int N = ; int n, m;
boolean deg[N];
bitset<N> eq[N]; void reverse(bitset<N> &bs, int bit) {
if (bs.test(bit))
bs.reset(bit);
else
bs.set(bit);
} inline void init() {
scanf("%d%d", &n, &m);
pfill(deg, deg + n, false);
for (int i = ; i < n; i++)
eq[i].reset();
for (int i = , u, v; i <= m; i++) {
scanf("%d%d", &u, &v);
u--, v--;
eq[u].set(v);
eq[v].set(u);
reverse(eq[u], u);
reverse(eq[v], v);
deg[u] = !deg[u], deg[v] = !deg[v];
}
} void guass() {
for (int i = ; i < n; i++) {
int p = -;
for (int j = i; j < n && p == -; j++)
if (eq[j].test(i))
p = j;
if (p == -)
continue;
swap(eq[p], eq[i]);
swap(deg[p], deg[i]);
for (int j = ; j < n; j++)
if ((j ^ i) && eq[j].test(i))
eq[j] ^= eq[i], deg[j] ^= deg[i];
}
} inline void solve() {
guass();
int r = ;
for (int i = ; i < n && r == ; i++)
if (deg[i])
r = ;
printf("%d\n", r);
for (int i = ; i < n; i++)
printf("%d ", deg[i] + );
puts("");
} int T;
int main() {
scanf("%d", &T);
while (T--) {
init();
solve();
}
return ;
}
Problem L
Problem M Algoland and Berland
题目大意
平面上有$n$个白点和$m$个黑点，满足任意三点不共线，要求给出一个生成树满足：
- 每条边是平面上的一条线段，边与边只在端点处相交
- 每条边恰好连接一个白点和一个黑点
- 第$i$个黑点的度数为$r_i$，保证$r_1 + r_2 + \cdots + r_m = n + m - 1$
神仙题。orz yjq_naiive & 他的数竞同学。
设$r = \max\left \{ r_1, r_2, \dots, r_{m}\right \}$
若$r = 1$，则$n + m = 2$，构造是显然的。
若$r > 1$，考虑选出$r$最大的点$P$。
考虑用一条经过$P$的直线将整个平面分成两个部分（先假设是可行的）。对于每部分我们都能够得到若干生成树，然后$P$向它们连边，这样就得到了解。
如何保证这个能够得到若干个生成树，它的一个必要条件是$|E| - |V| \leqslant -1$。
如何表示$|E| - |V|$？我们将每个点的赋一个权值$r_i - 1$（如果这个点是白点，那么它的$r_i$记为0），这样一部分内的点权和就是这一部分的$|E| - |V|$。（等价于把$|V|$的贡献摊在每个点上）
当知道一部分$|E| - |V|$后可以计算出$P$需要向它们连的边数：$x = |V| - |E|$。
我们知道$1\leqslant x \leqslant r - 1$，所以$1 - r \leqslant |V| - |E| \leqslant -1$
然后我们把$P$当成两个点分别加入两个部分，这两半部分分别是一个子问题，可以递归处理。
现在我们来证明一下必定存在这样一条直线满足条件。我们考虑随便找一条经过$P$的直线，记某一半的点权和为$s$，然后顺时针转动这条直线，每遇到一个点$s$至多会改变$r - 1$。如果存在一个不合法的时刻，那么必然满足$s < 1 - r$或者$s > -1$，考虑当直线旋转180度以后，这样$s' = r - s$，因为变化了至少$r$，所以必然存在某个时刻$1 - r \leqslant s \leqslant -1$。
于是这道题愉快地被通过啦。时间复杂度$O(n^2\log n)$
Code
/**
* Codeforces
* Problem#1070M
* Accepted
* Time: 624ms
* Memory: 106100k
*/
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
typedef bool boolean; template <typename T>
void pfill(T* pst, const T* ped, T val) {
for ( ; pst != ped; *(pst++) = val);
} const double pi = acos(-);
const double eps = ; typedef class Point {
public:
int x, y, deg, id; Point():x(), y(), deg(), id() { }
Point(Point p, int ndeg):x(p.x), y(p.y), deg(ndeg), id(p.id) { }
Point(int x, int y, int deg):x(x), y(y), deg(deg), id() { }
}Point; typedef class Event {
public:
int val, id;
boolean add;
double theta; Event() {}
Event(int val, int id, boolean add, double theta):val(val), id(id), add(add), theta(theta) { } boolean operator < (Event e) const {
return theta < e.theta;
}
}Event; const int N = 6e3 + ; int T;
int n, m;
int rs[N];
int tp = ;
boolean onleft[N];
Event events[N << ];
vector<Point> ps; inline void init() {
scanf("%d%d", &n, &m);
ps.clear();
ps = vector<Point>(n + m);
for (int i = ; i < m; i++)
scanf("%d", rs + i);
for (int i = ; i < n; i++)
scanf("%d%d", &ps[i].x, &ps[i].y), ps[i].deg = , ps[i].id = i + ;
for (int i = ; i < m; i++)
scanf("%d%d", &ps[i + n].x, &ps[i + n].y), ps[i + n].deg = rs[i], ps[i + n].id = i + ;
} void solve(vector<Point> &ps) {
int r = , mxid = -;
for (int i = ; i < (signed) ps.size(); i++)
if (ps[i].deg > r)
r = ps[i].deg, mxid = i;
if (r == ) {
int cnt = ;
for (int i = ; i < (signed) ps.size(); i++)
if (!ps[i].deg)
mxid = i, cnt++;
assert(cnt == || ps.size() == );
for (int i = ; i < (signed) ps.size(); i++)
if (i ^ mxid)
printf("%d %d\n", ps[i].id, ps[mxid].id);
return;
} int dx, dy;
double theta;
tp = ;
int sum = ;
for (int i = ; i < (signed) ps.size(); i++) {
if (i == mxid)
continue;
dx = ps[i].x - ps[mxid].x, dy = ps[i].y - ps[mxid].y;
theta = atan2(dy, dx);
if (theta > || fabs(theta) < eps) {
sum += ps[i].deg - , onleft[i] = true;
events[tp++] = Event( - ps[i].deg, i, false, theta);
} else
events[tp++] = Event(ps[i].deg - , i, true, theta + pi);
} sort(events, events + tp);
for (int i = ; i < tp && (sum < - r || sum > -); i++) {
sum += events[i].val;
onleft[events[i].id] = events[i].add;
} assert(sum >= - r && sum <= -); vector<Point> pl, pr;
for (int i = ; i < (signed) ps.size(); i++) {
if (i == mxid)
continue;
if (onleft[i])
pl.push_back(ps[i]);
else
pr.push_back(ps[i]);
}
pfill(onleft, onleft + ps.size(), false);
pl.push_back(Point(ps[mxid], -sum));
pr.push_back(Point(ps[mxid], r + sum));
ps.clear(); solve(pl);
solve(pr);
} inline void solve() {
puts("YES");
solve(ps);
} int main() {
scanf("%d", &T);
while (T--) {
init();
solve();
}
return ;
}
Problem M