2018 China Collegiate Programming Contest Final (CCPC-Final 2018)

虚拟了这套比赛，感觉发挥的已经到极限了，没想到还只是个铜orz
B. Balance of the Force

题意：每个人要么分到A组，要么分到B组，分A组系统会得到Li的权值，分B组系统会得到Di的权值，其中有m对互斥关系，代表x和y不能分到同组，求系统最大权值减去最小权值的最小值

解法：我们可以枚举系统最小值的值，然后根据该最小值去分组产生最小的最大值，对答案去造成贡献，这里我们设$d[i]$为最小值为$i$时，最小的最大值为$d[i]$，对于第$i$个没有互斥关系的人（假设 L i < D i L_{i}Li​<Di​），假设我选了 L i L_{i} Li​，如果 j < = L i j<=L_{i} j<=Li​，那么 d [ j ] = m a x ( d [ j ] , L i ) d[j]=max(d[j], L_{i}) d[j]=max(d[j],Li​)，选了 D i D_{i} Di​，如果 L i < j < = D i L_{i}Li​<j<=Di​，那么 d [ j ] = m a x ( d [ j ] , D i ) d[j] = max(d[j], D_{i}) d[j]=max(d[j],Di​)，对于所有的大于 d i d_{i} di​的$j$，$d[j]=inf$，互斥关系可以建个图，如果不是二分图无解，如果是二分图这个图可以转化成两对权值：$(L1,D1)$，$(L2,D2)$，两对权值选一对对系统造成贡献，$dp$转移方法同上，但是这样转移复杂度不过关，因此我们可以用线段树维护$dp$，最后找一个最小的$d[i]-i$就是答案

#include
#define ll long long
#define ls o * 2
#define rs o * 2 + 1
#define mid (l + r) / 2
using namespace std;
const int maxn = 4e5 + 10;
ll mx[maxn * 4], X[maxn], x[maxn], y[maxn], inf = 1e18, val[3], ans;
int col[maxn], vis[maxn], cnt, Case;
struct node {ll L1, R1, L2, R2;
} cat[maxn];
vector<int> G[maxn];
int dfs(int u, int color) {col[u] = color;if (color & 1) {cat[cnt].L1 = min(cat[cnt].L1, x[u]);cat[cnt].R1 = max(cat[cnt].R1, x[u]);cat[cnt].L2 = min(cat[cnt].L2, y[u]);cat[cnt].R2 = max(cat[cnt].R2, y[u]);}else {cat[cnt].L1 = min(cat[cnt].L1, y[u]);cat[cnt].R1 = max(cat[cnt].R1, y[u]);cat[cnt].L2 = min(cat[cnt].L2, x[u]);cat[cnt].R2 = max(cat[cnt].R2, x[u]);}int okk = 1;for (auto v : G[u])if (!col[v])okk &= dfs(v, 3 - color);else if (col[v] == col[u])return 0;return okk;
}
void up(int o, int l, int r, int ql, int qr, ll v) {if (ql > qr)return;if (l >= ql && r <= qr) {mx[o] = max(mx[o], v);return;}if (ql <= mid)up(ls, l, mid, ql, qr, v);if (qr > mid)up(rs, mid + 1, r, ql, qr, v);
}
void query(int o, int l, int r, ll v) {v = max(v, mx[o]);if (l == r) {ans = min(ans, v - X[l]);return;}query(ls, l, mid, v);query(rs, mid + 1, r, v);
}
int solve() {int n, m, u, v, sz = 0;scanf("%d%d", &n, &m);for (int i = 1; i <= 8 * n; i++)mx[i] = 0;for (int i = 1; i <= n; i++) {col[i] = vis[i] = 0;G[i].clear();}for (int i = 1; i <= m; i++) {scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);vis[u] = vis[v]  = 1;}for (int i = 1; i <= n; i++) {scanf("%d%d", &x[i], &y[i]);X[++sz] = x[i], X[++sz] = y[i];}sort(X + 1, X + 1 + sz);sz = unique(X + 1, X + 1 + sz) - X - 1;for (int i = 1; i <= n; i++) {x[i] = lower_bound(X + 1, X + 1 + sz, x[i]) - X;y[i] = lower_bound(X + 1, X + 1 + sz, y[i]) - X;}printf("Case %d: ", ++Case);cnt = 0;for (int i = 1; i <= n; i++)if (vis[i] && !col[i]) {cnt++;cat[cnt].L1 = cat[cnt].L2 = inf;cat[cnt].R1 = cat[cnt].R2 = -inf;if (!dfs(i, 1))return puts("IMPOSSIBLE"), 0;if (cat[cnt].L1 > cat[cnt].L2) {swap(cat[cnt].L1, cat[cnt].L2);swap(cat[cnt].R1, cat[cnt].R2);}if (cat[cnt].R1 <= cat[cnt].R2) {up(1, 1, sz, 1, cat[cnt].L1, X[cat[cnt].R1]);up(1, 1, sz, cat[cnt].L1 + 1, cat[cnt].L2, X[cat[cnt].R2]);up(1, 1, sz, cat[cnt].L2 + 1, sz, inf);}else {up(1, 1, sz, 1, cat[cnt].L2, X[cat[cnt].R2]);up(1, 1, sz, cat[cnt].L2 + 1, sz, inf);}}for (int i = 1; i <= n; i++)if (!vis[i]) {if (x[i] > y[i])swap(x[i], y[i]);up(1, 1, sz, 1, x[i], X[x[i]]);up(1, 1, sz, x[i] + 1, y[i], X[y[i]]);up(1, 1, sz, y[i] + 1, sz, inf);}ans = inf;query(1, 1, sz, 0);printf("%lld\n", ans);}
int main() {int T;scanf("%d", &T);while (T--)solve();
}

I. Cockroaches

题意：二维平面有n个怪兽，你可以选择一个点，然后消除该行该列所有怪兽，问能消除最多的怪兽的数量mx，以及有多少个点能消除mx个怪兽

解法：我们用线段树维护每行的怪兽数量的最大值以及最大值数量，枚举每一列，从线段树中删除该列所有怪兽，那么能消除的怪兽就是该列怪兽数量+线段树中的最大值，这题就写完了

#include
#define ll long long
#define ls o * 2
#define rs o * 2 + 1
#define mid (l + r) / 2
using namespace std;
const int maxn = 2e5 + 10;
int X[maxn], x[maxn], y[maxn], n, r[maxn], Case = 0;
vector<int> xx[maxn];
struct seg {int mx, sum;seg operator+(const seg& t) {seg tmp = t;if (mx > tmp.mx)tmp.mx = mx, tmp.sum = sum;else if (mx == tmp.mx)tmp.sum += sum;return tmp;}
} cat[maxn * 4];
void up(int o, int l, int r, int k, int v) {if (l == r) {cat[o].mx += v;cat[o].sum = (cat[o].mx > 0) ? 1 : 0;return;}if (k <= mid)up(ls, l, mid, k, v);elseup(rs, mid + 1, r, k, v);cat[o] = cat[ls] + cat[rs];
}
ll solve() {int n, sz = 0;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d%d", &x[i], &y[i]);X[++sz] = x[i];X[++sz] = y[i];}sort(X + 1, X + 1 + sz);sz = unique(X + 1, X + 1 + sz) - X - 1;for (int i = 1; i <= sz * 4; i++)cat[i].mx = cat[i].sum = 0;for (int i = 1; i <= sz; i++)xx[i].clear(), r[i] = 0;for (int i = 1; i <= n; i++) {x[i] = lower_bound(X + 1, X + 1 + sz, x[i]) - X;y[i] = lower_bound(X + 1, X + 1 + sz, y[i]) - X;xx[x[i]].push_back(y[i]);r[x[i]]++;up(1, 1, sz, y[i], 1);}int mx = 0;ll ans = 0;for (int i = 1; i <= sz; i++) {for (auto v : xx[i])up(1, 1, sz, v, -1);if (cat[1].mx + r[i] > mx)mx = cat[1].mx + r[i], ans = cat[1].sum;else if (cat[1].mx + r[i] == mx)ans += cat[1].sum;for (auto v : xx[i])up(1, 1, sz, v, 1);}ll peach = 0;if (mx == 2)for (int i = 1; i <= sz; i++) {for (auto v : xx[i])up(1, 1, sz, v, -1);if (cat[1].mx == 1 && r[i] == 1)peach += cat[1].sum;for (auto v : xx[i])up(1, 1, sz, v, 1);}peach /= 2;if (mx == n)ans = peach + 1;printf("Case %d: %d %lld\n", ++Case, mx, ans - peach);
}
int main() {int T;scanf("%d", &T);while (T--)solve();
}

K .Mr. Panda and Kakin
学自：Link_Ray

#include
#define ll long long
#define ld long double
using namespace std;
const int maxn = 1e5 + 10;
int pri[maxn], vis[maxn], cnt;
ll mod;
void init(int n) {for (int i = 2; i <= n; i++) {if (!vis[i])pri[++cnt] = i;for (int j = 1; pri[j] * i <= n; j++) {vis[pri[j] * i] = 1;if (i % pri[j] == 0)break;}}
}
ll mul(ll &x, ll y) {x = (x * y - (ll)((ld)x * y / mod) * mod + mod) % mod;
}
ll ksm(ll x, ll y) {ll res = 1;while (y) {if (y & 1)mul(res, x);mul(x, x);y /= 2;}return res;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {if (!b) {x = 1, y = 0;return a;}ll gcd = exgcd(b, a % b, y, x);y -= a / b * x;return gcd;
}
int okk(int n) {for (int i = 1; pri[i] * pri[i] <= n; i++)if (n % pri[i] == 0)return 0;return 1;
}
int main() {init(1e5);int T, Case = 0;ll e = (1 << 30) + 3;scanf("%d", &T);while (T--) {ll n, c, p, q, x, y;scanf("%lld%lld", &n, &c);int m = sqrt(n) + 1;for (int i = m; ;i--)if (okk(i)) {p = i, q = n / i;break;}ll N = (p - 1) * (q - 1);exgcd(e, N, x, y);x = ((x % N) + N) % N;mod = n;printf("Case %d: %lld\n", ++Case, ksm(c, x));}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！