The 13th Chinese Northeast Collegiate Programming Contest 部分题解及AC代码

题解及AC代码"/>

The 13th Chinese Northeast Collegiate Programming Contest 部分题解及AC代码

The 13th Chinese Northeast Collegiate Programming Contest

B - Balanced Diet

题意：商店有m种糖果，有n个糖果在商店，每个糖果都有价值a[i], 为了平衡饮食，定义S/C，S为糖果的价值之和，C为数量最多的那种糖果的数量，要使得S/C最大，附加条件是每种糖果要么不去，要么至少取l[i]个，l[i]为0可以取任意个。

题解：显然对于一个C,每种糖果都取最大的C个，没有C个的全取计科，由小到大枚举C,将前每种糖果按由大到小排序，优先取大的，然后保存一个前缀和f(i)，用于存取C为i的糖果价值之和

#include <bits/stdc++.h>
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)
#define pb push_back
#define mp make_pairusing namespace std;
typedef long long ll;
const int maxn = 1e6 + 6;
const int maxm = 1e6 + 6;
const int INF = 0x3f3f3f3f;
vector<int> swt[maxm];
struct node{int id, v;bool operator<(const node A){return v < A.v;}
} l[maxn];
ll pre[maxn];
bool cmp(int a, int b){return a > b;
}
int n, m;ll mx(ll a, ll b){return a > b ? a : b;}ll gcd(ll a, ll b){while (b){ll  t = a % b;a = b;b = t;}return a;
}
int main()
{int T;cin>> T;while (T--){scanf("%d%d", &n, &m);FOR(i, 0, n) pre[i] = 0;FOR(i, 0, m) swt[i].clear();FOR(i, 0, m) l[i].v = 0;FOR(i, 1, m){scanf("%d", &l[i].v);l[i].id = i;}// sort(l + 1, l + m, cmp);FOR(i, 1, n){int a, b;scanf("%d%d", &a, &b);swt[b].pb(a);}FOR(i, 1, m) sort(swt[i].begin(), swt[i].end(), cmp);//FOR(i, 1, m) FOR(j, 1, swt[i].size())swt[i][j] += swt[i][j-1];int len = 0;FOR(i, 1, m){//int p = l[i].id;len = max(len,(int)(swt[i].size()));ll s = 0;FOR(j, 0, (int)swt[i].size()-1){if (l[i].v > j + 1) s += swt[i][j];else if (l[i].v == j + 1) pre[j] += s + swt[i][j];else pre[j] += swt[i][j];}}FOR(i, 1, len -1){pre[i] += pre[i - 1];}ll fz = pre[0], fm = 1;FOR(i, 1, len - 1){ll z = pre[i], mm = i + 1;if (fz * mm < z * fm) {fz = z;fm = mm;}}ll g = gcd(fz, fm);printf("%lld/%lld\n", fz / g, fm / g);}return 0;
}

C - Line-line Intersection

 题意：给出n条直线，问交点个数

题解：握手定理：若所有直线都不平行由n*(n-1)/2，若有m条直线平行或重合就减去m*(m-1)/2，若有k条直线重合就加上k*(k-1)/2

化简成标准式ax + by + c = 0 并按abc的优先顺序将系数换成大于0的系数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;
typedef pair<pair<ll,ll>,ll>Pi;
const int maxn=100010;
ll cnt,ans,n;
int main()
{int T;scanf("%d", &T);while(T--){scanf("%lld", &n);ans = n* (n - 1) / 2;map<P,ll>mp1;map<Pi,ll>mp2;for(int i=1;i<=n;i++){ll x1,x2,y1,y2;scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);ll a=x1-x2,b=y1-y2,c=x1*y2-x2*y1;if (a == 0 && b == 0 && c < 0) c*= -1;else if (a == 0 && b < 0) b*=-1, c*=-1;else if (a < 0) a *= -1, b *= -1, c*=-1;ll g=__gcd(abs(a),abs(b));a/=g;b/=g;c/=g;mp1[{a,b}]++;mp2[{{a,b},c}]++;ans+=mp2[{{a,b},c}]-mp1[{a,b}];}printf("%lld\n", ans);}return 0;
}

E - Minimum Spanning Tree

题意：给出一个树，然后边变点，点变树，边权为原来两条边的边权之和，求最小生成树

题解：由题意知，若想边权最小，就将边权最小的边与其他每条边相连

#include <bits/stdc++.h>
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)
#define pb push_back
#define mp make_pairusing namespace std;
typedef long long ll;
int n;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
vector <int> edge[maxn];
int main()
{int T;cin >> T;while (T--){scanf("%d", &n);FOR(i, 1, n ) edge[i].clear();FOR(i, 1, n-1){int u, v, x;scanf("%d%d%d", &u, &v, &x);edge[u].pb(x);edge[v].pb(x);}ll res = 0;FOR(i, 1, n){if (edge[i].size() <= 1) continue;ll ans = 0, minh = INF;FOR(j, 0, edge[i].size() - 1){ans += edge[i][j];minh = min(minh, (ll)edge[i][j]);}res += ans - minh + minh * (edge[i].size() - 1);}printf("%lld\n", res);}return 0;
}

G - Radar Scanner

 题意：平面上由n个窗口，需要将所有的窗口覆盖同一个点，问最小移动距离，每个窗口只能水平或者竖直移动

题解：求水平方向和竖直方向的中位数

#include <bits/stdc++.h>
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)
#define pb push_back
#define mp make_pairusing namespace std;
typedef long long ll;
const int maxn = 1e5 +2;struct Scanner{int a, b, c, d;
}sc[maxn];
int n, R, C;
int r[maxn * 2], c[maxn * 2];
int main() {int T;cin >> T;while (T--){scanf("%d", &n);FOR(i, 1, 2 * n) r[i] = c[i] = 0;FOR(i, 1, n){scanf("%d%d%d%d", &sc[i].a, &sc[i].b, &sc[i].c, &sc[i].d);r[i] = sc[i].a;r[i + n] = sc[i].c;c[i] = sc[i].b;c[i + n] = sc[i].d;}sort(r + 1, r + 2 * n + 1);sort(c + 1, c + 2 * n + 1);R = (r[n] + r[n + 1]) / 2;C = (c[n] + c[n + 1]) / 2;ll ans = 0;FOR(i, 1, n) {ans += (abs(sc[i].a - R) + abs(sc[i].c - R) - abs(sc[i].a - sc[i].c)) / 2;ans += (abs(sc[i].b - C) + abs(sc[i].d - C) - abs(sc[i].b - sc[i].d)) / 2;}printf("%lld\n", ans);}return 0;
}

H - Skyscraper

 题意：n 座摩天楼从左往右排成一排，第 i 座摩天楼的预计层数为ai。
            m 次操作：
            1. 将 a 的某个区间 [l; r] 的所有数都加上 k。
            2. 给定 [l; r]，问假如仅对 [l; r] 的摩天楼从零开始施工，最少需要几个阶段。每个阶段可以选择一个区间，将该区间内所有摩天楼往上修建一层

题解：

考虑静态的情况，令 a0 = 0; bi = ai - ai-1。
若 bi > 0，则至少需要多花 bi 个阶段才能完工。
若 bi ≤ 0，则 i - 1 的施工可以连带着把 i 给修好。
令 ci = bi[bi > 0]，对于区间 [l; r]，最少阶段数为
al + cl+1 + cl+2 + · · · + cr。
即 (b1 + b2 + · · · + bl) + (cl+1 + cl+2 + · · · + cr)
 

考虑区间加操作，对 b 和 c 的影响为 l 和 r + 1 两处单点修
改。
树状数组维护 b 和 c 的前缀和。
时间复杂度 O((n + m) log n)
 

#include <bits/stdc++.h>
#define FOR(i, s, t) for(int i=(s);i<=(t);i++)
using namespace std;const int maxn = 1e5 + 5;
typedef long long ll;
ll trb[maxn + 10], trc[maxn + 10];
ll a[maxn + 10], b[maxn], c[maxn + 10];int lowbit(int x){return x & (-x);
}void add(int x, ll val, ll *arr){for (int i = x; i <= maxn; i+= lowbit(i)){arr[i] += val;}
}ll query(int x, ll arr[]){ll res = 0;for (int i = x; i > 0; i-=lowbit(i)){res += arr[i];}return res;
}int n, m;int main()
{int T;cin >> T;while (T--){scanf("%d%d", &n, &m);FOR(i, 1, n){scanf("%d", &a[i]);b[i] = a[i] - a[i - 1];c[i] = b[i] > 0 ? b[i] : 0;}FOR(i, 0, n + 1) trb[i] = trc[i] = 0;FOR(i, 1, n){add(i, b[i], trb);add(i, c[i], trc);}while (m--){int op;scanf("%d", &op);if (op == 2){int l, r;scanf("%d%d", &l, &r);printf("%lld\n", query(l, trb) + query(r, trc) - query(l, trc));}else {int l , r;ll k, addcl, addcr;scanf("%d%d%lld", &l, &r, &k);if(b[l] < 0){addcl = b[l] + k;addcl = max(0ll, addcl);}else addcl = k;if (b[r + 1] > 0){addcr = min(b[r + 1], k);}else addcr = 0;b[l] += k;b[r+1] -= k;add(l, k, trb);add(r + 1, -k, trb);add(l, addcl, trc);add(r + 1, -addcr, trc);}}}return 0;
}

J - Time Limit

 题意：给一串数a1,a2,a3,...,an，要求x,使得满足一下三个条件

1.x>= 3*a1

2.x>=ai+1

3.x是偶数

题解：x=max{3*a1, ai+1},若x是奇数再加1

#include <bits/stdc++.h>
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)using namespace std;
int n;
int a[20];
int main()
{int T;cin >> T;while (T--){scanf("%d", &n);FOR(i, 1, n){scanf("%d", &a[i]);}int ans = a[1] * 3;FOR(i, 2, n){ans = max(ans, a[i] + 1);}if (ans & 1) ans++;cout << ans << endl;}return 0;
}