岳阳博物馆网站,网站一般字体,通用企业网站模板,最简单的网站模板下载前言 有人在过七夕#xff0c;我在打 cf #xff0c;还有某人独自一人在学校机房#xff0c;凌晨一点骑上共享单车回宿舍欣赏沿途的秋风扫落叶。 Standings#xff1a;2166 题目链接#xff1a;Dashboard - Codeforces Round 965 (Div. 2) - Codeforces
A. Find K Distin…前言 有人在过七夕我在打 cf 还有某人独自一人在学校机房凌晨一点骑上共享单车回宿舍欣赏沿途的秋风扫落叶。 Standings2166 题目链接Dashboard - Codeforces Round 965 (Div. 2) - Codeforces
A. Find K Distinct Points with Fixed Center 题意 给一个点x,y要求构造 k 个点使得这 k 个点的中心是x,y。 思路 分奇偶讨论两两对应即可。
#includecstdio
#includecstring
using namespace std;int T,x,y,k;int main()
{scanf(%d,T);while (T --){scanf(%d%d%d,x,y,k);if(k 1){printf(%d %d\n,x,y);for (int i 1;i k / 2; i) printf(%d %d\n%d %d\n,x i,y i,x - i,y - i);}else{for (int i 1;i k / 2; i) printf(%d %d\n%d %d\n,x i,y i,x - i,y - i);}}return 0;
}
B. Minimize Equal Sum Subarrays 题意 给你一个 1 ~ n 的排列 p 你需要构造出一个新的 1 ~ n 的排列 q 使得满足条件的 i , j对的数目最小 思路 只要使每一位的前缀和不一样即可其实整体往右挪一位就是答案。 比赛时打得太丑才知道 vector 的 erase 复杂度是 On的过 B 的时候就已经心态崩了
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;#define N 200005int T,n,fst;
long long sum[N],a[N],b[N],pre[N],las[N],now;int main()
{scanf(%d,T);while (T --){scanf(%d,n),sum[0] now 0ll;for (int i 1,x;i n; i)scanf(%lld,a[i]),sum[i] sum[i - 1] a[i],b[i] 0,pre[i] i - 1,las[i] i 1;fst 1;for (int i 1;i n; i){if(i n || (now a[fst] ! sum[i])){b[i] a[fst];now b[i];fst las[a[fst]];}else{b[i] a[las[fst]];now b[i];las[fst] las[las[fst]];}}for (int i 1;i n; i) printf(%lld ,b[i]);printf(\n);}return 0;
}
C. Perform Operations to Maximize Score 题意 给一个序列 a 和一个 01 串 b 可以进行 k 次操作每次操作可以让 b 中为 1 的某一位对应的 a 加上一求 k 次操作之后以下值的最大值 其中 表示序列 a 挖去 之后的序列median 表示中位数。 思路 可以分 0 和 1 讨论。 1. 1 的情况显然让 k 次操作都加在 上最优On扫一遍即可。 2. 0 的情况发现最大的那个 能得到最大的贡献于是我们只用考虑挖去最大的 后的序列让它的中位数尽可能大即可。我们可以二分中位数的值再判断是否合法即可。 好在是压线调出来了以致于没有掉大分。。。
#includecstdio
#includecstring
#includealgorithm
using namespace std;#define N 200005int T,n,mid,m;
long long k,ans,mx1,mx2;struct Node
{int val,b;
}a[N],c[N];long long max(long long x,long long y) { return x y ? x : y ; }int cmp(Node x,Node y) { return x.val y.val ; }int check(int x)
{int tmp m - mid 1;int fl m;for (int i m; i ;-- i)if(c[i].val x) -- tmp,fl i - 1;else break;if(tmp 0) return 1;int now k;for (int i fl; i ;-- i){if(c[i].b) now - x - c[i].val,-- tmp;if(now 0 || tmp 0) break;}if(now 0) return 0;if(tmp 0) return 1;return 0;
}int main()
{scanf(%d,T);while (T --){scanf(%d%lld,n,k),ans a[n 1].val 0ll;mid n / 2;for (int i 1;i n; i){scanf(%lld,a[i].val);if(a[i].val mx1) mx2 mx1,mx1 a[i].val;}for (int i 1;i n; i) scanf(%d,a[i].b);sort(a 1,a n 1,cmp);int bz 0;for (int i 1;i n; i)if(a[i].b){int tp;if(i mid) tp a[mid 1].val;else tp a[mid].val;ans max(ans,a[i].val k tp);}else{bz i;}if(bz){m 0;for (int i 1;i n; i)if(i ! bz) c[ m].b a[i].b,c[m].val a[i].val;ans max(ans,a[bz].val c[mid].val);int l c[mid].val;int r 1e9;while (l r){int md (l r) 1;if(check(md)) l md 1,ans max(ans,a[bz].val md);else r md - 1;}}printf(%lld\n,ans);}return 0;
}
D. Determine Winning Islands in Race 题意 给 n 座岛屿第 i 座和第 i 1 座之间有一座桥基础桥除此之外还有若干座桥附加桥所有桥都是单向的且由标号小的岛屿指向标号大的岛屿。最初Elsie 在 1 号岛屿Bessie 在 s 号岛屿他们都需要前往 n 号岛屿Bessie 只能走基础桥而 Elsie 可以走附加桥。 由 Bessie 率先开始每一轮这个人都可以走一条存在的桥然后他原先所在的岛屿立刻坍塌这意味着所有与原先岛屿相连的桥也同时坍塌如果当前无路可走则这个人终止在这个岛屿。 两个人都采取最优策略对于每个 判断 Bessie 能否到达 n 号岛屿。 思路 假设有一座 u - v 的桥若 E 可以通过这段桥超过 B 则必须要满足一下条件 1. u s 2. v - s t t 是 A 到达 v 所用的最快时间 即 用 BFS 求出 A 到每个点的最短时间再用差分数组统计贡献即可。
#includecstdio
#includecstring
#includequeue
using namespace std;#define N 200005int T,n,m,cnt,st[N],dis[N],vis[N],dif[N];struct Edge
{int next,to;
}ed[N 1];queueint q;void add(int u,int v)
{ed[ cnt].next st[u];ed[cnt].to v;st[u] cnt;return;
}void bfs()
{while (!q.empty()) q.pop(); q.push(1),vis[1] 1;while (!q.empty()){int x q.front();q.pop(),vis[x] 0;for (int i st[x]; ~i ;i ed[i].next){int rec ed[i].to;if(dis[x] 1 dis[rec]){dis[rec] dis[x] 1;if(!vis[rec]) q.push(rec),vis[rec] 1;}int l x 1;int r rec - (dis[x] 1) - 1;if(l r) dif[l],-- dif[r 1];}}return;
}int main()
{scanf(%d,T);while (T --){scanf(%d%d,n,m),cnt 0;for (int i 1;i n; i) st[i] -1,dis[i] n 1,vis[i] dif[i] 0;dis[1] dif[0] 0;for (int i 1;i n; i) add(i,i 1);for (int i 1,u,v;i m; i) scanf(%d%d,u,v),add(u,v);bfs();for (int i 1;i n; i) dif[i] dif[i - 1],printf(%d,(dif[i]) ? 0 : 1);printf(\n);}return 0;
}
E1. Eliminating Balls With Merging (Easy Version) 题意 给一行小球每个小球上面都标有一个分值小球可以通过向左右吃掉分值小于等于自己的球并加上所吃小球的分值。问有多少个小球有可能成为最后剩下的那个小球。 思路 Easy Version 我们可以利用贪心按分值从大到小将球排序从大球到小球进行处理。我们用单调栈记录一下每个小球左右两边第一个比它大的小球分别记作 l 和 r 。容易发现如果 l 或者 r 能成功留下且当前小球可以吃掉它那么当前小球一定可以成功留下反之不行。
#includecstdio
#includecstring
#includealgorithm
#includestack
using namespace std;#define N 200005int T,n,k,l[N],r[N],f[N],mx,ans;
long long a[N],pre[N];struct Node
{long long val,id;
}b[N];stackint q;int cmp(Node x,Node y) { return x.val y.val ; }long long max(long long x,long long y) { return x y ? x : y ; }int main()
{scanf(%d,T);while (T --){scanf(%d%d,n,k),pre[0] f[0] f[n 1] mx ans 0;for (int i 1;i n; i){scanf(%lld,a[i]);b[i].id i,b[i].val a[i],f[i] 0,mx max(mx,a[i]),pre[i] pre[i - 1] a[i];}for (int i 1;i n; i) f[i] (a[i] mx);sort(b 1,b n 1,cmp);while (!q.empty()) q.pop();q.push(0),a[0] 1e9 1ll;for (int i 1;i n; i){while (!q.empty() a[i] a[q.top()]) q.pop();l[i] q.top();q.push(i);}while (!q.empty()) q.pop();q.push(n 1),a[n 1] 1e9 1ll;for (int i n; i ;-- i){while (!q.empty() a[i] a[q.top()]) q.pop();r[i] q.top();q.push(i);}for (int i 1;i n; i){if(b[i].val mx) continue;int now b[i].id;long long sum pre[r[now] - 1] - pre[l[now]];if(sum a[l[now]]) f[now] | f[l[now]];if(sum a[r[now]]) f[now] | f[r[now]];}for (int i 1;i n; i) ans f[i];printf(%d\n,ans);}return 0;
}
E2. Eliminating Balls With Merging (Hard Version) 题意 Hard Version 唯一的区别就是给出一个 x 对于所有 都要统计子序列 1 ~ i 的 Easy Version 的问题。 思路 按 Easy Version 的做法肯定会超时我们试试 “返璞归真” 回归最原始易得的想法。 对于某个球 i 要是想留下来就一定要把 1 ~ i - 1 都吃掉那么我们可以计算想要把 1 ~ i - 1 都吃掉至少需要往右吃到的位置 minr 再根据已经把 1 ~ i - 1 都吃掉的情况下至多往右吃到的位置 maxr 。那么球 i 对答案的贡献区间就是 [minr , maxr] 用差分数组标记即可。 对于求 minr 和 maxr 的过程可以用 ST 表 二分 做循环判断向左最多吃到哪和向右最优吃到哪如果吃不动就跳出。这样是不会超时的因为每次吃到卡住的地方都说明那个位置的分值比你目前拥有的一段区间的分值之和要大也就是说每一次扩散都会让你手上的值至少翻倍因此这一过程的复杂度是 log(最大分值) 的。
#includecstdio
#includecstring
#includestack
using namespace std;#define N 200005int T,n,p,lg[N],dif[N];
long long a[N],pre[N],f[N][22];stacklong long st;long long max(long long x,long long y) { return x y ? x : y ; }void RMQ()
{for (int i 1;i lg[n]; i)for (int j 1;j (1 i) - 1 n; j)f[j][i] max(f[j][i - 1],f[j (1 (i - 1))][i - 1]);return;
}int getMINR(int x)
{int tl,tr;tl tr x;while (tl 1){int ml 1;int mr tl - 1;int now tl;long long sum pre[tr] - pre[tl - 1];int mid,len;while (ml mr){mid (ml mr) 1;len tl - mid;long long mx max(f[mid][lg[len]],f[tl - (1 lg[len])][lg[len]]);if(sum mx) now mid,mr mid - 1;else ml mid 1;}if(tl 1 tl now){ml tr 1;mr n;now tr;sum pre[tr] - pre[tl - 1];while (ml mr){mid (ml mr) 1;len mid - tr;long long mx max(f[tr 1][lg[len]],f[mid - (1 lg[len]) 1][lg[len]]);if(sum mx sum pre[mid] - pre[tr] a[tl - 1]) now mid,mr mid - 1;else if (sum mx) now mid,ml mid 1;else mr mid - 1;}if(now tr){tr -1;break;}else tr now;}else tl now;}return tr;
}int getMAXR(int x)
{while (x n){int ml x 1;int mr n;int now x;long long sum pre[x];while (ml mr){int mid (ml mr) 1;int len mid - x;long long mx max(f[x 1][lg[len]],f[mid - (1 lg[len]) 1][lg[len]]);if(sum mx) now mid,ml mid 1;else mr mid - 1;}if(now x) break;x now;}return x;
}int main()
{lg[1] 0;for (int i 2;i 200000; i) lg[i] lg[i 1] 1;scanf(%d,T);while (T --){scanf(%d%d,n,p),pre[0] 0ll,a[0] a[n 1] 1e9 1,dif[0] 0;for (int i 1;i n; i)scanf(%lld,a[i]),f[i][0] a[i],pre[i] pre[i - 1] a[i],dif[i] 0;RMQ();for (int i 1;i n; i){int mnr getMINR(i);if(mnr -1) continue;int mxr getMAXR(i); dif[mnr],-- dif[mxr 1];}for (int i 1;i n; i){dif[i] dif[i - 1];if(i p) printf(%d ,dif[i]);}printf(\n);}return 0;
} 总结 感觉总是会卡在前三题导致后面一些能做的大分题没时间写看来得多练练 ABC 了。
