题目链接：C. Pekora and Trampoline 思路：差分，经过仔细思考可以发现，最优解一定是都在1这个位置进行跳跃，因为假设1这个位置上的a[1]=1，那么他会跳到2，也就是具有传递性，直到跳到一个value不为1的地方，这和一开始就在该位置跳是一样的。证明了这个之后，我们进一步思考可以发现，i这个位置，可以对后面[i+2,min(a[i]+i,n)]产生影响，产生的影响是后面这些用跳的次数-1，然后再根据a[i]=1的传递性，如果位置j的value已经降...
题：https://codeforces.com/contest/1257/problem/E题意：给定3个数组，可行操作：每个数都可以跳到另外俩个数组中去，实行多步操作后使三个数组拼接起来形成升序。 输出最小操作次数dp：#include<bits/stdc++.h> usingnamespace std; constint M=2e5+5; int dp[M][3]; int a[M]; ///dp[i][0]表示前i个数全属于第一个数组所要花费的最小代价 ///dp[i][1]表示前i个数全属于第一、二个数组所要花费的最小代价 ///！！dp[i][1]必...
大意: 给定n个不相交的圆, 求将n个圆划分成两部分, 使得阴影部分面积最大. 贪心, 考虑每个连通块, 最外层大圆分成一部分, 剩余分成一部分一定最优.#include <iostream> #include <iostream> #include <algorithm> #include <cstdio> #include <math.h> #include <set> #include <map> #include <queue> #include <string> #include <string.h> #include <bitset> #define REP(i,a,n) for(int i=a;i<=n;++i) #define PER(i,a,n) fo...
对于两个贴在边上的顶点$A$,$B$,面积等于围成三角形面积减去$AB$围成的部分多边形面积。围成的多边形面积是确定的，我们希望三角形面积尽量小。设$C$为墙角顶点，那么$C$位于以$AB$为直径的圆上，显然希望$C$距离$AB$最近，所以当多边形的某条边贴在墙壁上时三角形面积最小。我们发现$A$,$B$存在单调性，那么可以双指针维护，面积则进行三角剖分维护，复杂度$O(n)$。#include <bits/stdc++.h> usingnamespace std; typedef longlon...
Codeforces Round #679 (Div. 1, based on Technocup 2021 Elimination Round 1)T1 Perform Easilymean\(\quad\)给你6个数\(a_{1} a_{2} ... a_{6}\) ，再给你\(n\)个数\(b_{1} b_{2} ... b{n}\) ，问当所有\(b\)都减去任意一个\(a\)时,最大值减去最小值的最小值是多少idea\(\quad\)我们考虑将所有的\(b_{i}\)都与任何一个\(a_{j}\)相减，那么就可以得到一个预处理好的结构，我们考虑这个结构具有两种属性相减之后的数值，我们简数...
A. Treasure time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Malek has recently found a treasure map. While he was looking for a treasure he found a locked door. There was a string s written on the door consistingof characters ‘(‘, ‘)‘ and ‘#‘.Below there was a manual on how to open the door. After spending a long time Malek manage...
题意：解法： 发现数位和与数的顺序无关,只和每种数位的个数有关.枚举a的个数i,判断i个a和(n-i)个b组合能否是极好的数, 如果是,那么答案累加C(n,i).code： #include <bits/stdc++.h> #define int long long using namespace std; const int maxm=2e6+5; const int mod=1e9+7; int fac[maxm],inv[maxm]; int ppow(int a,int b,int mod){int ans=1%mod;a%=mod;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans; } void in...
题目链接给出一个图， 每个节点只有三种情况， a，b, c。 a能和a, b连边， b能和a, b, c,连边， c能和b, c连边， 且无重边以及自环。给出初始的连边情况， 判断这个图是否满足条件。 由题意可以推出来b必然和其他的n-1个点都有连边， 所以初始将度数为n-1的点全都编号为b。 然后任选一个与b相连且无编号的点， 编号为1. 然后所有与1无连边的点都是3.然后O（n^2)检查一下是否合理。#include <iostream> #include <vector> #include ...
Recently Luba bought a monitor. Monitor is a rectangular matrix of size n?×?m. But then she started to notice that some pixels cease to work properly. Luba thinks that the monitor will become broken the first moment when it contains a square k?×?k consisting entirely of broken pixels. She knows that q pixels are already broken, and for each of them she knows the moment when it stopped working. Hel...
A. GCD Sum 题目描述 设 \(s(i)\) 为 \(i\) 的数位和，求第一个 \(\geq n\) 满足下式的 \(x\)： \[\gcd(x,s(x))>1 \]\(1\leq n\leq 10^{18}\)，数据组数不超过 \(10^4\) 组 解法 一开始没想法，然后打了个爆搜过掉了。 根据小学奥数可知若 \(x\) 为 \(3\) 的倍数则 \(\gcd(x,s(x))=3\)，所以就算是爆搜也只需要搜三次。 B. Box Fitting 题目描述 点此看题 解法 又猜了结论，就是能填大的就暴力填大的。 证明就考虑如果某次放弃了填...
题意略。思路：对于随机产生的一个数列，对于某个儿子，其兄弟在其前面的概率为 1 / 2。所以这个兄弟对期望的贡献为son[v] / 2，所有兄弟加起来即为(tot - 1) / 2。 详见代码：#include<bits/stdc++.h> usingnamespace std; constint maxn = 1e5 + 5;int son[maxn],n,fa; vector<int> graph[maxn]; double ans[maxn];void dfs(int cur){son[cur] = 1;for(int i = 0;i < graph[cur].size();++i){int v = graph[cur][i];dfs(v);son[c...
心得：打这个比赛的时候由于读题，自己变成一个大傻逼了，反思了一晚上 ，确实还是自己做的不够好，下面我口胡一篇自己的对于这几个题的解答。 比赛地址传送门 开始了： A题意：给出长度为N 的数组和可以操作的最大次数，然后要求你找出 非负的最小的数组字典序，然后有一个操作，选择一个数组+1，一个数组-1，直到找到最小字典序，或者操作做完。 题解：直接就是把所有的数字[1–n-1]这个范围的数字依次减 然后+到第N个数上，特别...
847E - Packmen思路：二分时间。代码： #include<bits/stdc++.h> usingnamespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) int n; string s;bool check(int t) {int now=-1,bean=-2;//now是上一个P覆盖到的位置，bean是没有被上一个P覆盖到的第一个星星 for(int i=0;i<n;i++){if(s[i]==‘*‘){if(bean<=now)bean=i;}elseif(s[i]==‘P‘){if(now<bean){if(i-bean>t)returnfalse;el...
题目大意：给定一个区间[l,r]/**/，你需要在这个区间中选择最多k/**/个不同的数，使得异或和最小当r?l+1≤4/**/时，暴力枚举集合即可 当r?l+1≥5/**/时，讨论： 若k≥4/**/，则[l,r]/**/中一定存在一组数为2k,2k+1,2k+2,2k+3/**/，故答案为0 若k=1/**/，则只能取l/**/ 若k=2/**/，则只能取2k,2k+1/**/，异或值为1 若k=3/**/，由于我们可以只取2k,2k+1/**/，因此答案上界不会超过1 我们只需要判断能否在[l,r]/**/区间内找到3个...
DescriptionPolycarpus loves hamburgers very much. He especially adores the hamburgers he makes with his own hands. Polycarpus thinks that there are only three decent ingredients to make hamburgers from: a bread, sausage and cheese. He writes down the recipe of his favorite "Le Hamburger de Polycarpus" as a string of letters ‘B‘ (bread), ‘S‘ (sausage) и ‘C‘ (cheese). The ingredients in the r...