1 codancer

尚未进行身份认证

为信仰而战斗

等级
TA的排名 3w+

codancer的CF图论训练(updating...)

2019.9.12580C.KefaandParktags:简单DFS1081D.MaximumDistancetags:带点思维的MST,学会了只联通某些点的并查集

2019-09-12 19:03:28

JSOI2007:字符加密(后缀数组)

题意:将长度为nnn的字符串排成一圈,对于nnn种排列方式构成的字符串按字典序从小到大输出最后一位。题解:1.将原串扩展成2倍(避免有些没有遍历到)。2.建立后缀数组,对于saisa_{i}sai​小于nnn的输出第sai+n−1sa_i+n-1sai​+n−1位即可。代码://luogu-judger-enable-o2#include<bits/stdc++.h>...

2019-09-12 11:11:13

The Preliminary Contest for ICPC Asia Xuzhou 2019

B.soeasy并查集,可能会卡掉map,建议使用unordered_map。#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+100;constintmod=1e9+7;typedeflonglongll;constintINF=0x3f3f3f3f;constllll...

2019-09-09 17:24:15

The Preliminary Contest for ICPC Asia Nanjing 2019

A.Thebeautifulvaluesofthepalace首先对于每个(x,y)(x,y)(x,y),我们可以O(1)O(1)O(1)的查询出这个坐标的值。接下来就将问题转化为了一个106⋅10610^6\cdot10^6106⋅106的矩阵,每次查询子矩阵内的点的和。考虑将所有的yyy离散化,计mpi,jmp_{i,j}mpi,j​表示(1,1)−(i,j)(1,1)-(i...

2019-09-04 11:08:53

AtCoder Beginner Contest 139

A#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+100;constintmod=1e9+7;typedeflonglongll;constintINF=0x3f3f3f3f;constllllINF=0x3f3f3f3f3f3f3f3f;#definerep(i,...

2019-09-01 22:14:48

【codeforces 1026 D】 Shortest Cycle(最小环)

题面题意:一个长度为nnn的数组,如果ai&aj!=0a_{i}\&a_{j}!=0ai​&aj​!=0,那么iii和jjj之间就有一条边,计算所构成图的最小环。(1≤n≤100000,1≤ai≤1018)(1\leqn\leq100000,1\leqa_i\leq10^{18})(1≤n≤100000,1≤ai​≤1018)思路...

2019-08-28 17:43:37

【codeforces 1208D】 Restore Permutation(线段树)

题面题意:一个长度为nnn的排列aaa,现在定义pip_ipi​为数组aaa中下标小于等于iii并且小于aia_iai​的数字的和。现在给定ppp,求aaa。思路:首先可以肯定的是,ppp中最后一个000出现的位置pospospos在aaa中一定是111。我们可以反证:假设aposa_{pos}apos​不为111,假设111在pospospos之前,那么ppos≥1p_{pos}\g...

2019-08-27 11:30:20

【HDU 6714】最短路2(Dijkstra)

题面题意:对于floyedfloyedfloyed算法,Di,jD_{i,j}Di,j​表示最外层循环最小的能够求出来disi,jdis_{i,j}disi,j​的循环次数,计算∑i=1n∑j=1nDi,j\sum_{i=1}^{n}{\sum_{j=1}^{n}{D_{i,j}}}∑i=1n​∑j=1n​Di,j​思路其实Di,jD_{i,j}Di,j​即为iii到jjj的最短路路径上最...

2019-08-25 08:53:39

【HDU 6638】Snowy Smile(线段树求区间连续最大和)

题面题意平面坐标系有nnn个点,第iii个点的坐标为(xi,yi)(x_i,y_i)(xi​,yi​),每个点有个权值wiw_iwi​,现在你需要寻找一个矩形把某些点圈起来使得他们的权值和最大。思路先把各点的纵坐标离散化,然后把所有的点按照横坐标从小到大排序,枚举矩形的左边界,每加入一个新的点,就把它对应纵坐标yyy的权值和w[y]w[y]w[y]更新并更改右边界,当左右边界都确定以后,利...

2019-08-10 10:56:47

【HDU 6627】equation(分段函数求值)

题目链接题意:两个长度为nnn的数组aaa和bbb和一个正整数CCC,计算有多少个xxx满足:∑i=1n∣ai⋅x+bi∣=C\sum_{i=1}^n|a_i\cdotx+b_i|=Ci=1∑n​∣ai​⋅x+bi​∣=C思路:该函数为分段函数,每段的转折点为−biai-\frac{b_i}{a_i}−ai​bi​​,先把转折点排序,计最开始的函数值为x⋅suma+sumbx\...

2019-08-06 10:57:12

2019牛客暑期多校D.Big Integer

题面题意:定义A(n)A(n)A(n)为nnn个1构成的数字,如A(3)=111A(3)=111A(3)=111,计算有多少对(i,j)(i,j)(i,j)使得A(ij)%p=0A(i^j)\%p=0A(ij)%p=0。思路:通过枚举发现是有上面的等式是有循环节的,而且循环节是p−1p-1p−1的因子,因此暴力枚举计算出循环节ddd,接下来就是求有多少对ij%d=0i^j\%d...

2019-08-05 20:32:49

【HDU 6621】 K-th Closest Distance(主席树+二分)

题面题意:一个长度为nnn的数组,有mmm次查询,对于每次查询,查询[l,r][l,r][l,r]内距离ppp第kkk近的距离。强制在线。思路考虑二分距离disdisdis,对于每次的disdisdis,判断在[l,r][l,r][l,r]内在区间[p−dis,p+dis][p-dis,p+dis][p−dis,p+dis]内的数是否超过了kkk个,该操作可以利用主席树来实现,复杂度O(n...

2019-08-05 19:40:16

对主席树的理解以及使用

引入一个长度为nnn的数组,有mmm次查询,每次查询区间[l,r][l,r][l,r]内第kkk小的元素。如果使用暴力,肯定不可以使用线段树?可是我只会查询区间最值啊。那么我们把问题再次简化一下,查询[1,n][1,n][1,n]第kkk小的元素,要求使用线段树来实现。权值线段树为了解决这个问题,我们引入一个名词:权值线段树。那么权值线段树是如何解决上面那个问题的呢?首先,我们对数组...

2019-07-30 15:55:52

2019 牛客多校第二场 D.Kth Minimum Clique(bitset优化)

D.KthMinimumClique(bitset优化)题面题意:求一个无向连通图的第KKK大完全子图。思路:新技能:利用bitsetbitsetbitset存储子图,假设把iii能到达的点的位设置为111,这样我们就可以通过直接进行与运算来判断这个点是否能放到现在的团里面。然后BFS即可。代码:#include<bits/stdc++.h>usingname...

2019-07-23 21:30:10

2019江西省程序设计竞赛

A.Cotree题意:两棵树,你需要连接两个点使得∑i=1i=n∑j=i+1j=ndis(i,j)\sum_{i=1}^{i=n}{\sum_{j=i+1}^{j=n}}{dis(i,j)}∑i=1i=n​∑j=i+1j=n​dis(i,j)最小。思路:对于每棵树进行换根dp,对每棵子树找到一个点使得所有点到这个点的距离和最小,连接这两个点,然后进行一次DFS统计每条边的贡献,累加即可。...

2019-07-21 23:23:31

【 Codeforces Round #572 (Div. 2)】E. Count Pairs(数学)

题面题意:现在有一个长度为nnn的数组aaa,找出有多少对(i,j)(i,j)(i,j)满足1≤1\leq1≤i<ji<ji<j≤n\leqn≤n并且(ai+aj)∗(ai2+aj2)modp==k(a_i+a_j)*(a_i^{2}+a_j^{2})modp==k(ai​+aj​)∗(ai2​+aj2​)modp==k。思路:左右同乘(ai−aj)(a...

2019-07-06 10:05:12

【Educational Codeforces Round 67 (Rated for Div. 2)】E. Tree Painting(换根DP)

题面题意:一棵树,有nnn个节点,现在要找一个点作为根节点使得这棵树的所有子树的大小和最大。求出最大值。思路:先利用一次dfs求出以iii为根的子树的大小sizisiz_isizi​和所有的字数和$$...

2019-07-03 10:49:49

【ABC 132 E】Hopscotch Addict(最短路)

题面题意:一个有向图,从SSS出发,每次只能走三步(即连续三条边),现在问你能否经过若干步到达TTT,如果可以输出最少的步数,否则输出−1-1−1。思路:disi,jdis_{i,j}disi,j​代表S到iS到iS到i的距离disdis%3dis为jjj的最短路,我们要计算的即为disT,0dis_{T,0}disT,0​,BFSBFSBFS即可,注意状态的传递。code:#incl...

2019-06-30 16:40:55

【Codeforces Round #569 (Div. 2)】 题解

A小学数学题#include<bits/stdc++.h>usingnamespacestd;longlongf[102];voidinit(){ f[1]=1; for(inti=2;i<=101;i++){ f[i]=f[i-1]+(i-1)*4; }}intmain(){ init(); intn; cin>>n;...

2019-06-24 11:58:01

【CF 1185G1】Playlist for Polycarp (easy version)(状压DP)

题面题意现在你有nnn首歌,第iii首歌的播放时间为tit_iti​,种类为fif_ifi​,其中1≤fi≤31\leqf_i\leq31≤fi​≤3,现在你从家到学校需要花费TTT的时间,你在路上不想闲着,现在你要选几首歌按照一定的顺序播放,你要保证着几首歌的时间总和为TTT(每首歌只会播放一次),并且在播放的时候不会连续播放同一种类的歌曲,计算共有多少种方案,答案对109+710^...

2019-06-20 20:35:00

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。