- 博客(232)
- 收藏
- 关注
RSS订阅原创 AtCoder Beginner Contest 183
貌似昨天能第一场自主ak…都怪火锅…吃完回家就睡着了…A.#include <bits/stdc++.h>using namespace std;int n;int main(){ scanf("%d",&n); printf("%d\n",max(0,n));return 0;}B.#include <bits/stdc++.h>using namespace std;double x,y,xx,yy,h,l,k,ans;int main(
2020-11-16 20:17:55
162
原创 20201028笔记
1.给定一个整数序列，修改最少的个数，使得修改后序列为不严格递增。（ans=len-最长不下降序列）2.给定一个整数序列，修改最少的个数，使得修改后序列为严格递增。（a[i]=a[i]-i，ans=len-最长不下降序列）3.如果只需要求常数个组合数，那么就只需要知道常数个inv就好了，不要傻傻的把1-n的inv[i]全都算出来！！！inv[i]=pow(bin[i],MOD-2)，在组合数中直接写pow(bin[i],MOD-2)就好了…...
2020-10-28 19:07:38
152
原创 ARC064补题
C.很明显，不满足条件是尽量多删后面的#include <bits/stdc++.h>#define int long longusing namespace std;const int N=1e5+5; int n,x,ans;int a[N];signed main(){ scanf("%lld%lld",&n,&x); for (register int i=1; i<=n; ++i) scanf("%lld",&a[i]); for
2020-10-15 02:33:30
169
原创 ARC063补题
C.#include <bits/stdc++.h>using namespace std;int n,ans;char str[100005];int main(){ scanf("%s",str+1); n=strlen(str+1); for (register int i=2; i<=n; ++i) if (str[i]!=str[i-1]) ans++; printf("%d\n",ans);return 0; }D.找a[i]<a[j]且a[j
2020-10-15 02:02:33
138
原创 ARC060补题
C.若干个的平均数为k，那么就相当于总和为i*k。设f[i][i * k]表示用了i个，总和为i*k的方案数。（注意是用了i个而不是前i个）#include <bits/stdc++.h>#define int long longusing namespace std;const int N=51;int n,k,x,ans;int f[N][N*N];signed main(){ scanf("%lld%lld",&n,&k); f[0][0]=1; f
2020-10-15 01:40:05
133
原创 ARC059补题
C.从-100到100枚举一遍。#include <bits/stdc++.h>using namespace std;int n,ans,sum;int a[105];int main(){ scanf("%d",&n); for (register int i=1; i<=n; ++i) scanf("%d",&a[i]); ans=2e9; for (register int i=-100; i<=100; ++i) { sum=0;
2020-10-15 01:11:51
111
原创 ARC058补题
C.发现枚举到1e5即可覆盖所有情况。#include <bits/stdc++.h>using namespace std;int n,k,x;bool vis[10];int main(){ scanf("%d%d",&n,&k); for (register int i=1; i<=k; ++i) { scanf("%d",&x); vis[x]=true; } for (register int i=n; i<=9999
2020-10-15 01:04:28
134
原创 CF1059E Split the Tree
ans[u]:覆盖完u的子树需要的最少次数。f[u]:花费最少次数覆盖完u的子树后，u还可以向上延伸的最大长度。len[u]:从u开始可以向上延伸的最大长度。正常情况下：ans[u]+=ans[e[i].to]],f[u]=max(f[e[i].to])若u为叶节点：ans[u]=1,f[u]=len[u]若到u时，f[e[i].to]刚好全部空了：ans[u]+=ans[e[i].to],ans++,f[u]=len[u]len[u]通过倍增可得，ans[u],f[u]树形dp即可。#
2020-10-09 23:36:44
109
原创 CF1029E Tree with Small Distances
记根节点的深度为1。对于深度>3且当前深度最大的若干点来说，想要使得它们与根节点距离不超过2，只有两个选择：1.向它们连边；2.向它们的父节点连边。显然是向父节点连边优秀，因为向父节点连边，可以消掉最深节点的兄弟节点和祖父节点；而向最深节点连边，则只能消掉最深节点本身和父节点。所以我们把不符合要求的点放入堆中，不断取出堆中深度最大的节点，向该节点的父节点连边，并消除能消除的点（即与父节点相邻的点），同时记录总次数即可。#include <bits/stdc++.h>using n
2020-10-09 23:29:07
99
原创 [ZJOI2004]嗅探器
所求点一定是一个x，y以外的割点。我们可以强制当前根为x，那么，若找到一个割点且该割点分割了x,y，那么该割点即为所求。如何判断是否分割了x,y呢？low[y]>=dfn[u]即可。#include <bits/stdc++.h>using namespace std;const int N=2e5+5,M=5e5+5;int n,u,v,x,y,ans;int now,dfn[N],low[N];int cnt,head[N];struct edge{int next
2020-10-09 23:22:04
125
原创 [HNOI2012]矿场搭建
对于每一个连通块来讲，若连通块内存在割点：首先我们处理出该连通块内的所有点双，将每一个点双标号后，那么我们一定可以得到一棵"类似树" 。1.若一个点双为树中叶节点(只含有一个割点)，那么必须在该点双的不是割点的任意一个地方建一个出口，因为叶节点如果不建，一旦割点坍塌就出不去了。（ans+=1，all*=sum）2.若一个点双为树中的非叶节点(含有两个或两个以上的割点的点双)，那么就不用在这个点双内再建新的出口了，因为它的任意一个割点坍塌后，也可以从另一个割点走到一个叶节点，而叶节点，之前是已经建有出口
2020-10-09 23:19:05
224
原创 [POI2008]BLO-Blockade
将割点与非割点分类讨论。#include <bits/stdc++.h>#define int long longusing namespace std;const int N=1e5+5,M=5e5+5;int n,m,u,v,ans[N];int now,dfn[N],low[N],size[N];bool cut[N];int cnt,head[N];struct edge{int next,to;}e[M<<1];inline void add(int
2020-10-09 15:18:09
94
原创 洛谷 P2731 [USACO3.3]骑马修栅栏 Riding the Fences
欧拉回路貌似挺好写的，那么我们就找到最小的可以作为起点的点后，开始一个个枚举点i与当前点之间是否存在连边，存在则dfs(i)。然后i每次从1-500枚举，那么dfs的次数为n+1次，每次枚举次数为500，所以复杂度是O(n^2)。#include <bits/stdc++.h>using namespace std;const int N=2e3+5;int n,i,j,u,v,s,ss;int du[N],g[N][N],b[N]; int d=1e8;inline void
2020-10-09 14:04:52
185
原创 洛谷 P3388 【模板】割点（割顶）
这里求的割点的意义仅仅指的是：去掉这个点后，不能使得原图联通的点。当然可能还会有别的各种各样的奇怪树，图中的不同含义的“割点”。#include <bits/stdc++.h>using namespace std;const int N=1e5+5;int n,m,u,v,now,cnt,ans;int head[N],dfn[N],low[N];bool cut[N];struct edge{int next,to;}e[2*N];inline void add(int
2020-10-09 13:25:31
362
原创 CF566A Matching Names
将字符串的信息放到trie树以后，贪心地合并深度最深的姓名和笔名。若某深度中有一些姓名和笔名剩余，那么就将剩余的部分上传至深度减一的节点中去，企图与深度减一的姓名和笔名进行合并。#include <bits/stdc++.h>#define ll long longusing namespace std;const int N=8e5+5;int n;ll ans;int tot,ch[N][26];vector<int>cnt[N][2];string s;st
2020-10-06 21:21:30
764
1
原创 CF1416C XOR Inverse
考虑将每一个数二进制拆位。若a[i],a[j] (i<j)拆位后的最高位不同，那么当a[i]异或上x，假设最高位变成1时，很明显a[j]的该位会变成0，从而对逆序对产生一个贡献；而如果最高位变为0，a[j]的该位则变为1，那么就不会产生这一个贡献。因为最高位是具有最高话语权的，所以我们构造的x的最高位，需要使得a数组异或上x之后的逆序对尽可能小，所以就可以贪心地从高位到低位构造x的每一位是0还是1。我们可以建0/1trie树来维护插入的数的下标。之后计算每一位填0的贡献和填1的贡献，分治下去即可
2020-10-06 21:16:42
220
原创 CF1420D Rescue Nibel!
很套路地把线段拆为左端点为+1，右端点为-1的两个点后，按照位置从小到大扫过去，当某点为右端点时，统计当前集合中线段个数，然后累加C(sum,k)。（因为左右端点赋了权值，所以集合中线段个数即为当前权值和）这样做后发现是会有重复的，样例1就很良心地提醒了这一点。考虑如何容斥，发现不会…所以改变一下组合数的含义，每次统计时，我们强制当前的最后一条线段必选选，那么现在，就需要在另外的sum-1条线段中选取k-1条了。累加C(sum-1,k-1)，不需要去重。#include <bits/stdc+
2020-10-01 12:02:54
260
2
原创 CF264C Choosing Balls
设f[c[i]]表示：最后一个选的是颜色为c[i]的球的最大贡献。可知f[c[i]]有以下三种转移得到：f[c[i]]=f[c[j]]+u*a[i]（1<=j<i,c[j]=c[i]）f[c[i]]=f[c[j]]+v*a[i]（1<=j<i,c[j]!=c[i]）f[c[i]]=v*a[i]所以我们如果能迅速得到最大的f[c[j]] (1<=j<i,c[j]!=c[i])的值，那么就可以实现复杂度：O(T n)。记f[t1]为之前出现过的最大的f[c[i]]
2020-10-01 10:38:37
182
原创 CF1060E Sergey and Subway
考虑原图：对于原图中一条长度为偶数len的路径，新图长度为len/2；对于原图中一条长度为奇数len的路径，新图长度为(len+1)/2。设原图长度为偶数的路径总长为A，长度为奇数的路径总长为B，长度为奇数路径有C条，那么新图路径总长即为：(A+B+C)/2。A+B即为原图的所有路径总长，算每一条边的贡献可得。C为原图奇数路径条数，可以发现，一条奇数路径的两顶点的深度，一定是一奇一偶。#include <bits/stdc++.h>#define int long longusing
2020-09-30 00:18:33
129
原创 CF868F Yet Another Minimization Problem
对于暴力dp的状态以及复杂度瓶颈就不再描述，假设前置内容大家都会了。f[j][i]:前i个分了j组的最小费用。记calc(l,r)表示：[l,r]分为一组的费用。对于这个dp方程，我们可以得到一个性质，若：f[j][i]=f[j-1][p]+calc(p+1,i)，f[j][ii]=f[j-1][pp]+calc(pp+1,ii)，则i<=ii。（不会证明，只能说是多画点图后猜测的…，当然，也蛮显然的）而这个就是决策单调性优化dp的标志了。总而言之就是：由于刚刚猜测的式子，所以当我们做当前的
2020-09-29 18:54:16
154
原创 CF487B Strip
#include <bits/stdc++.h>using namespace std;const int N=1e5+5;int n,s,l,inf;int a[N],LOG[N],minn[N][18],maxn[N][18],f[N];inline int query(int l,int r){ int s=LOG[r-l+1]; return max(maxn[l][s],maxn[r-(1<<s)+1][s])-min(minn[l][s],minn[r.
2020-09-29 16:30:04
147
原创 Codeforces Round #674 (Div. 3)
A.Floor Number对于第一层要分开来算；当不整除时注意加一。#include <bits/stdc++.h>using namespace std;int T;int n,x,ans;int main(){ scanf("%d",&T); while (T--) { scanf("%d%d",&n,&x); n-=2; ans=1; if (n<=0) { printf("%d\n",ans); contin
2020-09-29 07:53:22
362
1
原创 CF1092E Minimal Diameter Forest
和CF455C Civilization貌似挺像。我们求出每棵树的直径和中点，找到直径最大的树后，将别的树的中点与直径最大的树的中点相连，即可完成构造。#include <bits/stdc++.h>using namespace std;const int N=1e5+5;int n,m,u,v,ans,p,mid,pos;int f[N];bool vis[N],jay;int cnt,head[N];struct edge{int next,to;}e[N<<
2020-09-28 23:50:34
283
原创 CF461B Appleman and Tree
感觉这题的dp挺神奇的，不是特别显然…所以也不会什么递推式的证明…#include <bits/stdc++.h>#define int long longusing namespace std;const int N=2e5+5,MOD=1e9+7;int n,u,v;int f[N][2],a[N];int cnt,head[N];struct edge{int next,to;}e[N<<1];inline void add(int u,int v){
2020-09-28 11:29:07
100
原创 CF478D Red-Green Towers
考虑a+b的最优情况，那么最大层数刚好为：sqrt(2*(a+b))。有可能由于a与b相差较大，则不能到达这个理论最大层数，但是没有关系，我们在dp过程中，保证当前每一步的转移是合法的，则最后倒序枚举合法的最大层数即可。对于dp状态的解释，写在了注释中。#include <bits/stdc++.h>#define int long longusing namespace std;const int N=4e5+5,MOD=1e9+7;int a,b,n;int f[2][N],
2020-09-27 22:37:29
166
原创 Atcoder ACL Beginner Contest
D.Flat Subsequencef[i]表示：数列最后一个为第i个的最大值，它可以由之前的，数值差绝对值在m以内的若干个f[j]转移而来。所以我们用一棵线段树，在a[j]的位置上把f[j]存下来，然后对于第i个值来说，只要查询：[max(a[i]-m,0),min(a[i]+m,300000)]区间内的最大f值即可。#include <bits/stdc++.h>using namespace std;const int N=3e5+5;int n,m,l,r,mid,ans;
2020-09-27 21:51:35
246
原创 9.22记
针对某神仙说的“写无聊的题解”这一言论，我是这样想的：尽可能地把自己之前写的题，都记录到CSDN上来，而对于某些较简单的题，题解自然也就几句甚至一句话带过了。毕竟这也是自己两年学习的点滴，想在AFO前，尽可能地多留下一点痕迹，说不定以后哪天自己有兴致了就会随便翻翻呢？也说不定某篇只有几句话甚至一句话的题解，被某位oier看到后觉得有学习价值，哪怕只是一点，那也是好的。所以最近自己写的题，只要有时间，基本都会放到CSDN上来。至于之前的，可能就得咕咕咕了。...
2020-09-22 21:07:22
100
1
原创 Connected Components
对并查集做前后缀和。对于并查集的前后缀中的节点i来说，如果它在前缀后所属的连通块与它在后缀中所属的连通块不同，那么说明i就是前后缀两个不同连通块的连接点，所以可以把前后缀的两个不同连通块，并为同一连通块。之后就是求连通块个数即可。#include <bits/stdc++.h>using namespace std;const int M=1e4+5,N=505;int n,m,xx,yy,ans,q,x,y;int u[M],v[M],l[M][N],r[M][N],f[N];
2020-09-21 20:37:39
360
原创 [NOI2016]区间
我们只需要关注需要的线段中的最大值和最小值即可，所以若存在若干条不相关的线段，但长度在最小值与最大值之间，那么它不会对答案产生影响，所以我们把这样的不相关的线段全部放进去也没有任何关系。考虑可以用尺取法。按照线段长度排序后，设连续的一段线段的左右端点为i和j，根据两端点中的全部线段是否有至少m条拥有一个同样的点来移动i和j。如何判断两端点中的全部线段是否有至少m条拥有一个同样的点呢？ 线段树进行区间累加并维护区间最大和。注意对坐标进行离散化。应该算是最套路的NOI题了吧…#include <
2020-09-21 20:28:14
101
原创 [POI2013]LUK-Triumphal arch
二分枚举答案后，做一个可行性dp来检验。#include <bits/stdc++.h>using namespace std;const int N=3e5+5;int n,u,v,l,r,mid,ans;int f[N];int cnt,head[N];struct edge{int next,to;}e[N<<1];inline void add(int u,int v){ cnt++; e[cnt].next=head[u]; e[cnt].to=v
2020-09-21 20:20:49
95
原创 Noip2019 括号树
f[i]表示：以i结尾的合法序列的个数。我们用栈来记录’(‘的位置，对于当前出现的一个’(’，我们将它放入栈中；对于当前出现的一个’)’,如果栈为空，则无贡献，如果栈不为空，则可得：f[i]+=f[fa[sta[top]]]。因为f[i]表示以i结尾的合法序列的个数，所以最后需要将以i节点的若干个祖先节点为结尾的合法序列的个数，累加至f[i]中，即:f[i]+=f[fa[i]]。#include <bits/stdc++.h>#define int long longusing nam
2020-09-21 20:19:33
176
原创 CF427C Checkposts
记录每个强连通分量中，最小值与最小值个数。#include <bits/stdc++.h>#define int long longusing namespace std;const int N=3e5+5,MOD=1e9+7; int n,m,u,v,ans1,ans2;int now,top,col,dfn[N],low[N],sta[N],color[N],minn[N],sum[N],a[N];int cnt,head[N];struct edge{int next,to
2020-09-21 20:15:21
120
1
原创 CF1000E We Need More Bosses
对无向图进行缩点后求树直径即为答案。#include <bits/stdc++.h>using namespace std;const int N=3e5+5;int n,m,u[N],v[N],ans,p;int now,top,col,dfn[N],low[N],sta[N],color[N];int cnt=1,head[N];struct edge{int next,to; bool vis;}e[N<<1];inline void add(int u,int
2020-09-21 20:14:13
144
原创 CF490F Treeland Tour
以每个点为起点，做一次朴素的nlogn复杂度的lis，共n个点做n次，总复杂度：O(n^2 log n)注意树上操作时的还原操作。#include <bits/stdc++.h>using namespace std;const int N=6e3+5;int n,u,v,ans;int a[N],f[N];int cnt,head[N];struct edge{int next,to;}e[N<<1];inline void add(int u,int v){
2020-09-21 20:12:30
178
原创 CF356A Knight Tournament
对m个操作倒序进行操作，利用线段树实现区间赋值。#include <bits/stdc++.h>using namespace std;const int N=3e5+5;int n,m;int l[N],r[N],x[N],sum[N<<2],add[N<<2],ans[N];inline void pushdown(int k){ if (add[k]) { sum[k<<1]=sum[k<<1|1]=add[k];
2020-09-21 20:10:15
122
原创 CF999E Reachability from the Capital
对于缩点后得到的DAG，我们求出入度为0的强连通分量的个数，即为最少的需要添加的边。（注意判断首都所在的强连通分量的入度）#include <bits/stdc++.h>using namespace std;const int N=5e3+5;int n,m,s,u[N],v[N],ans,du[N];int now,top,col,dfn[N],low[N],sta[N],color[N];int cnt,head[N];struct edge{int next,to;}e[N
2020-09-21 20:08:53
98
原创 CF1120C Compress String
朴素算法n^2求最长公共后缀#include <bits/stdc++.h>using namespace std;const int N=5e3+5;int n,a,b;int f[N],g[N][N];char str[N];int main(){ scanf("%d%d%d",&n,&a,&b); scanf("%s",str+1); for (register int i=1; i<n; ++i) for (register int
2020-09-21 20:05:02
148
原创 [JSOI2007]字符加密
将字符串进行复制，后缀排序后，对sa[i]进行查找。若sa[i]<=len，则输出s[sa[i]+len-1]即可。应该算是SA最裸的题了，不需要求height。#include <bits/stdc++.h>using namespace std;const int N=2e6+5;int n,m,len;int sum[N],rk[N],rk2[N],tp[N],sa[N],height[N];char s[N];inline void qsort(){ for
2020-09-19 09:00:17
868
原创 [USACO06DEC]Milk Patterns G
我们想要得到一个：至少出现k次的子串的最长长度。后缀排序后可得：含有这个"出现k次的子串"的后缀，必定是连续的，且前若共有k个连续的后缀拥有这个“出现k次的子串”，那么他们连续的区间一段lcp的最小值，一定就是这个“出现k次的子串”的最大值了。所以，求出height以后，找出：区间长度为k-1的区间的最大的最小值。单调队列或二分求解。由于本菜菜单调队列还是会的（单调栈实在恶心），所以就偷懒写这个码量较小的了…#include <bits/stdc++.h>using namespac
2020-09-18 20:29:35
177
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人