× Codeforces Round 975 (Div. 2)(A~F)
A(见F)
代码
// Problem: F. Max Plus Min Plus Size
// Contest: Codeforces - Codeforces Round 975 (Div. 2)
// URL: https://codeforces.com/contest/2019/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
#define int long long
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
struct DSU {std::vector<int> f, siz , cnt0 , cnt1 , tag , val;int cnt = 0;int tot = 0;DSU() {}DSU(int n) {init(n);}void init(int n) {f.resize(n);cnt0.resize(n);cnt1.resize(n);tag.resize(n);val.resize(n);std::iota(f.begin(), f.end(), 0);siz.assign(n, 1);}int find(int x) {while (x != f[x]) {x = f[x] = f[f[x]];}return x;}bool same(int x, int y) {return find(x) == find(y);}bool merge(int x, int y) {x = find(x);y = find(y);if (x == y) {return false;}if(siz[x] & 1){swap(cnt0[y] , cnt1[y]);}siz[x] += siz[y];cnt0[x] |= cnt0[y];cnt1[x] |= cnt1[y];cnt -= tag[y];cnt -= tag[x];if(cnt0[x] || cnt1[x]){if(siz[x] & 1){tag[x] = cnt1[x];}else{tag[x] = 1;}}cnt += tag[x];tot -= val[x];tot -= val[y];val[x] = (siz[x] + 1) / 2;tot += val[x];f[y] = x;return true;}int size(int x) {return siz[find(x)];}
};
void solve()
{int n;cin >> n;int a[n + 1];set<int>st;for(int i = 1 ; i <= n ; i ++){cin >> a[i];st.insert(a[i]);} map<int,int>mp;map<int,int>pm;int id = 0;for(auto it : st){mp[it] = ++id;pm[id] = it;}vector<int>e[id + 1];//若一个并查集的大小为奇数,且奇数上有r,那么就能取到//若一个并查集的大小为偶数,那么无论如何都能取到r//我们需要知道这个并查集是否含有r,且奇数位上是否含有rDSU dsu(n + 1);int b[n + 1];for(int i = 1 ; i <= n ; i ++){b[i] = mp[a[i]];}for(int i = 1 ; i <= n ; i ++){if(b[i] == id){dsu.val[i] = 1;dsu.cnt1[i] = 1;dsu.tag[i] = 1;dsu.tot++;dsu.cnt++;}e[b[i]].pb(i);}int ans = 0;for(int l = id; l >= 1 ; l --){for(auto it : e[l]){if(l != id){dsu.val[it] = 1;dsu.tot++; } }for(auto it : e[l]){if(it > 1){if(b[it - 1] >= l){dsu.merge(it - 1 , it);}}if(it + 1 <= n){if(b[it + 1] >= l){dsu.merge(it , it + 1);}}}ans = max(ans , dsu.tot + pm[id] - (dsu.cnt == 0));//cout << dsu.cnt << " " << ans << endl;}cout << ans << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}
B
思路
由于数轴上任意两点都能构成区间,因此对于某个数而言,其被包含的区间数量为左侧点的个数*右侧点的个数,特别的,端点处需要额外加上左侧端点个数(代表了左侧端点连到该端点上的区间)。
代码
// Problem: B. All Pairs Segments
// Contest: Codeforces - Codeforces Round 975 (Div. 2)
// URL: https://codeforces.com/contest/2019/problem/B
// Memory Limit: 256 MB
// Time Limit: 1500 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
#define int long long
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
void solve()
{int n , q;cin >> n >> q;map<int,int>mp;int a[n];for(int i = 0 ; i < n ; i ++){cin >> a[i];}for(int i = 0 ; i < n - 1; i ++){//处理端点int l = a[i] , r = a[i + 1];if(i == 0)mp[i + (i + 1) * (n - i - 1)]++;mp[(i + 1) * (n - i - 1)] += r - l - 1;mp[i + 1 + (i + 2) * (n - i - 2)]++;}for(int i = 0 ; i < q; i ++){int x;cin >> x;cout << mp[x] << " ";}cout << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}
C
思路
考虑到当k足够大,且初始牌都为0时,你能构成任意数量的牌堆。那么当初始牌不为0时,能够构成的牌堆情况是什么样的?假设这些牌中数量最大的为 x x x,那么你至少需要构造出 x x x堆牌。由于购买牌是不限制的,因此构造完这 x x x堆牌之后,若 k k k还有剩余,一定能构造出任意数量的牌堆。因此,能构造出的牌堆数量为 [ x , i n f ] [x,inf] [x,inf].
接下来从大到小枚举牌堆中牌的数量,看能否用 k k k构造出来。
代码
// Problem: A. Cards Partition
// Contest: Codeforces - Codeforces Round 975 (Div. 1)
// URL: https://codeforces.com/contest/2018/problem/A
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
#define int long long
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
void solve()
{int n , k;cin >> n >> k;int a[n + 1];int sum = 0 , mx = 0;for(int i = 1 ; i <= n ; i ++){cin >> a[i];mx = max(mx , a[i]);sum += a[i];}for(int i = n ; i >= 1; i --){int ok = 0;int need = mx * i;if(sum + k < need){continue;}else if(sum > need){int t = (sum - 1 + i) / i * i;if(sum + k < t){continue;}else{ok = 1;}}else{ok = 1;}if(ok){cout << i << endl;return;}}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}
D
思路
注意到,若整个数组大小为 n n n,那么左右两端的数若都小于 n n n,那么就一定没法符合题意。反之,无论选哪个点为起始点,这个点都一定满足题意。
形式化来讲,我们用双指针 l , r l , r l,r代表了当前的左右两个端点,若 a [ l ] ≥ r − l + 1 a[l] \geq r - l + 1 a[l]≥r−l+1 , 那么对于该点而言,起始点处于 [ l − a [ l ] + 1 , l + a [ l ] − 1 ] [l - a[l] + 1,l + a[l] - 1] [l−a[l]+1,l+a[l]−1]范围内的点都是满足题意的,反之就一定没法满足题意。同理对 r r r也是一样。对于已经判过的点,我们从数组中将其删除。直到不满足题意或者全部判完。
代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
void solve()
{int n;cin >> n;int a[n + 1];int mi = n;int r = n , l = 1;for(int i = 1 ; i <= n ; i ++){cin >> a[i];} int rr = n;int ll = 1;while(l <= r){rr = min(rr , a[l] + l - 1);ll = max(ll , l - a[l] + 1);ll = max(ll , r - a[r] + 1);rr = min(rr , r + a[r] - 1);if(a[l] >= r - l + 1 && a[r] >= r - l + 1){l++;r--;}else if(a[l] >= r - l + 1){l++;}else if(a[r] >= r - l + 1){r--;}else{cout << 0 << endl;return;}//cout << ll << " " << rr << endl;}//cout << rr << " " << ll << endl;int ans = rr - ll + 1;cout << max(0 , ans) << endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}
E
思路
假设最终所有叶子的深度全部为 x x x,那么初始树中所有深度大于 x x x的结点全部需要被删除,所有深度小于 x x x的叶子结点需要删除(由于此步骤可能会导致出现新的叶子,所以需要实时判断)。
可以发现:所有深度大于 x x x的结点可以用前缀和来快速求得,所有深度小于 x x x的叶子结点在 x x x递增的过程中是不断递增的。因此我们从小到大的枚举 x x x,记录每个叶子结点的深度,当深度为 x x x的答案已经被算过后,就将所有深度为 x x x的叶子结点向上删除,直到没有出现叶子,记录被删除的叶子的数量。
代码
// Problem: C. Tree Pruning
// Contest: Codeforces - Codeforces Round 975 (Div. 1)
// URL: https://codeforces.com/contest/2018/problem/C
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
struct HLD {//轻重链剖分int n;std::vector<int> siz, top, dep, parent, in, out, seq , now;//子树大小 所在重链的顶部节点 深度 父亲 子树DFS序的起点 子树DFS序的终点std::vector<std::vector<int>> adj;int cur = 1;HLD() {}HLD(int n) {init(n);}void init(int n) {this->n = n;siz.resize(n);top.resize(n);dep.resize(n);parent.resize(n);in.resize(n);out.resize(n);now.resize(n);seq.resize(n);cur = 0;adj.assign(n, {});}void addEdge(int u, int v) {adj[u].push_back(v);adj[v].push_back(u);}void work(int root = 1) {top[root] = root;dep[root] = 0;parent[root] = -1;dfs1(root);dfs2(root);}void dfs1(int u) {if (parent[u] != -1) {adj[u].erase(std::find(adj[u].begin(), adj[u].end(), parent[u]));}siz[u] = 1;for (auto &v : adj[u]) {parent[v] = u;dep[v] = dep[u] + 1;dfs1(v);siz[u] += siz[v];if (siz[v] > siz[adj[u][0]]) {std::swap(v, adj[u][0]);}}}void dfs2(int u) {in[u] = ++cur;seq[in[u]] = u;for (auto v : adj[u]) {top[v] = v == adj[u][0] ? top[u] : v;dfs2(v);}out[u] = cur;}int lca(int u, int v) {while (top[u] != top[v]) {if (dep[top[u]] > dep[top[v]]) {u = parent[top[u]];} else {v = parent[top[v]];}}return dep[u] < dep[v] ? u : v;}int dist(int u, int v) {return dep[u] + dep[v] - 2 * dep[lca(u, v)];}int jump(int u, int k) {if (dep[u] < k) {return -1;}int d = dep[u] - k;while (dep[top[u]] > d) {u = parent[top[u]];}return seq[in[u] - dep[u] + d];}bool isAncester(int u, int v) {//是否为祖先return in[u] <= in[v] && in[v] < out[u];}int rootedParent(int u, int v) {std::swap(u, v);if (u == v) {return u;}if (!isAncester(u, v)) {return parent[u];}auto it = std::upper_bound(adj[u].begin(), adj[u].end(), v, [&](int x, int y) {return in[x] < in[y];}) - 1;return *it;}int rootedSize(int u, int v) {if (u == v) {return n;}if (!isAncester(v, u)) {return siz[v];}return n - siz[rootedParent(u, v)];}int rootedLca(int a, int b, int c) {return lca(a, b) ^ lca(b, c) ^ lca(c, a);}
};
void solve()
{int n;cin >> n;HLD hld(n + 5);for(int i = 1 ; i < n ; i ++){int u , v;cin >> u >> v;hld.addEdge(u , v);}hld.work();vector<int>cnt(n + 5 , 0);vector<int>e[n + 5];for(int i = 1 ; i <= n ; i ++){if(hld.adj[i].empty()){e[hld.dep[i]].pb(i);}cnt[hld.dep[i]]++;}vector<int>pos(n + 5 , 0);//是否已经被删除for(int i = 1 ; i <= n ; i ++){cnt[i] += cnt[i - 1];hld.now[i] = hld.siz[i];}int ans = inf;int tmp = 0;pos[1] = 1;for(int i = 1 ; i <= n ; i ++){int tot = tmp + cnt[n] - cnt[i];ans = min(ans , tot);for(auto it : e[i]){int x = it;int cnt = 0;while(x != 1 && hld.now[x] == 1){tmp++;int pr = x;x = hld.parent[x];hld.now[x] -= hld.siz[pr];}} }cout << ans << endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}
F
思路
假设某次选择的最大值为 x x x,且整个数组中有 a y > x a_{y}>x ay>x,那么我们若选择 a y a_{y} ay为最大值,两者的数量差距最大为 1 1 1,因此对于答案而言,最大值越大越好。
例如: 2 3 1 1 1 这个样例而言,你可以选择[2 , 1 , 1]变为红色, 也可以选择[3,1]变为红色。当最大值增大后,其选择的数量最多减一。
假设最小值为 l l l , 最大值为 r r r 。选择方案为若干段连续区间 ,其每一段连续区间的所有数都在 [ l , r ] [l,r] [l,r]之间。每个连续区间的最大方案为 ( x + 1 ) / 2 ( x 为区间大小 ) (x + 1) / 2(x为区间大小) (x+1)/2(x为区间大小)。需要注意:要保证能取到最大值 r r r,若所有区间在选择最大方案时都没法取到 r r r,那么就需要将答案-1.因此,我们用并查集来维护区间以及区间合并,记录这个区间的最大取值,以及这个区间的奇数位置能否取到 r r r,这个区间的偶数位置能否取到 r r r。
然后我们从大到小的枚举 l l l,对于那些值等于 l l l的数,我们尝试将其跟左右两边的数进行合并,然后再求答案。
代码
// Problem: F. Max Plus Min Plus Size
// Contest: Codeforces - Codeforces Round 975 (Div. 2)
// URL: https://codeforces.com/contest/2019/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
#define int long long
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
struct DSU {std::vector<int> f, siz , cnt0 , cnt1 , tag , val;int cnt = 0;int tot = 0;DSU() {}DSU(int n) {init(n);}void init(int n) {f.resize(n);cnt0.resize(n);cnt1.resize(n);tag.resize(n);val.resize(n);std::iota(f.begin(), f.end(), 0);siz.assign(n, 1);}int find(int x) {while (x != f[x]) {x = f[x] = f[f[x]];}return x;}bool same(int x, int y) {return find(x) == find(y);}bool merge(int x, int y) {x = find(x);y = find(y);if (x == y) {return false;}if(siz[x] & 1){swap(cnt0[y] , cnt1[y]);}siz[x] += siz[y];cnt0[x] |= cnt0[y];cnt1[x] |= cnt1[y];cnt -= tag[y];cnt -= tag[x];if(cnt0[x] || cnt1[x]){if(siz[x] & 1){tag[x] = cnt1[x];}else{tag[x] = 1;}}cnt += tag[x];tot -= val[x];tot -= val[y];val[x] = (siz[x] + 1) / 2;tot += val[x];f[y] = x;return true;}int size(int x) {return siz[find(x)];}
};
void solve()
{int n;cin >> n;int a[n + 1];set<int>st;for(int i = 1 ; i <= n ; i ++){cin >> a[i];st.insert(a[i]);} map<int,int>mp;map<int,int>pm;int id = 0;for(auto it : st){mp[it] = ++id;pm[id] = it;}vector<int>e[id + 1];//若一个并查集的大小为奇数,且奇数上有r,那么就能取到//若一个并查集的大小为偶数,那么无论如何都能取到r//我们需要知道这个并查集是否含有r,且奇数位上是否含有rDSU dsu(n + 1);int b[n + 1];for(int i = 1 ; i <= n ; i ++){b[i] = mp[a[i]];}for(int i = 1 ; i <= n ; i ++){if(b[i] == id){dsu.cnt1[i] = 1;dsu.tag[i] = 1;dsu.cnt++;}e[b[i]].pb(i);}int ans = 0;for(int l = id; l >= 1 ; l --){for(auto it : e[l]){dsu.val[it] = 1;dsu.tot++; }for(auto it : e[l]){if(it > 1){if(b[it - 1] >= l){dsu.merge(it - 1 , it);}}if(it + 1 <= n){if(b[it + 1] >= l){dsu.merge(it , it + 1);}}}ans = max(ans , dsu.tot + pm[id] + pm[l] - (dsu.cnt == 0));}cout << ans << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}