- 博客(488)
- 收藏
- 关注
RSS订阅原创 CF 709C
感谢这个题让我进了前1000思路（特殊条件切入）：一开始想跑网络流，但边数、点数太多，所以就需要找此题和常规网络流的区别看到 M/2 ——>尽可能使用M/2这个条件构造解——>少于M/2的全选——>剩下的全是大于M/2的——>如果每天全是两个以上的，必然可以（极限情况两个全取M/2次）——>一天只有一个的必选，判断合法——>剩下的往M/2取，取满了换数#include<bits/stdc++.h>using namespace.
2021-03-22 01:46:59
266
原创 CF 709B
思路（特殊条件切入）：看到加相同数——>等差数列 （1）看到取模——>+n*mod （2）由（1）（2）知数列每一项加上一个n*mod，构成等差数列 ——>差值1、差值为正（1）没有>mod，则此为c（2）取过mod，则c为 a+n*mod，可知mod可取无穷大2、差值为负一定取过mod，且差值为c-n*mod，由于要找最大的mod，故取差值为c-mod，不影响数列合法性分类讨论：一、差值不同，为正由1知两种情况都没有确定的c...
2021-03-22 01:37:04
218
原创 CF 709A
思路（根据法则构造）：看到联通——>应该形成一个连通块时破坏墙数最少——>构造一种：每个格子破一面，形成一条连线——>n*m#include<bits/stdc++.h>using namespace std;#define ll long longll n,m,a,ans,ansl,T;int i,j,k,l;int main(){scanf("%lld",&T);while(T--){ scanf("%d%d",&n,&...
2021-03-22 01:14:57
198
原创 CF 706D
非常典型的CF题，代码量不大，但细节扣得很死，题也容易读错思路（分类讨论）：看到一个往低处走，一个往高处走，尽可能走的最远——>想到最长单调子列以单调子列长度为依据讨论：1、A选非最长列上一点，则B可选最长列上最低点，A必败2、A选最长列上一点，{1} A选最长列中间的点，B直接选在下方，A必败{2}A选最长列最高点（1）B选另一条最长列，A必败（2）最长列数量唯一，B和A选中同一条最长列。 [1]A和B对着走，取决于路径奇偶 [2]A和...
2021-03-12 03:47:42
106
原创 CF 706C
思路（数学证明+归纳）：看到对称——>坐标取绝对值——>对两个人，取距离不交叉的点代价小于距离交叉的点(两边和大于第三边)——>以此类推，对所有人，都不要有交叉的——>每个人必须取最近的，不然必有交叉#include<bits/stdc++.h>using namespace std;#define ll long longll k,n,m,a[100005],ans,ansl,b,A;int i,j,l,r,T;char ch[150];i..
2021-03-10 23:11:16
90
原创 CF 706B
思路（特殊条件切入）：看到（a+b）/2上取整——>范围在（a,b]——>思考a和b大小关系若mex<max——>永远不可能=a,下一次操作和这一次结果相同——>统计这一次的结果若mex>max——>=a，新增一个最大的数——>下一次操作构成循环，增量为轮数#include<bits/stdc++.h>using namespace std;#define ll long longll k,n,m,a[100005],..
2021-03-10 23:04:03
79
原创 CF 706A
读题艰难。思路（根据法则构造）：看到划分回文子串，求方案可不可行——>一个串可能有多种划分方式——>尝试找到最多能划几个，最少能划几个。#include<bits/stdc++.h>using namespace std;#define ll long longll m,a,ans,ansl;int n,i,j,k,l,r;char ch[150];int main(){scanf("%d",&n);while(n--){...
2021-03-10 22:53:16
84
原创 CF 1C
思路（根据题目特殊条件切入）：1、看到边数<=100 ——> 可以枚举2、看到正多边形 ——>研究正多边形顶点之间的角度（X，无明显规律） 正多边形在圆上（√）——>三个点在圆上于是就可以通过找圆心、算夹角、枚举边数、检验是否为最小角度倍数，来找到最小圆，从而得到面积注意：1、特判斜率2、误差范围不能太大，玄学#include<bits/stdc++.h>using namespace std;#define ll long ...
2021-03-09 15:05:22
139
原创 CF 1B
模拟进制，但要注意字母并不完全是26进制，可以发现第n位和第n-1位有可能是等值的 A0=Z，所以从个位开始转十进制数字的时候特判Z，遇到Z写0，并向高位进一。#include<bits/stdc++.h>using namespace std;#define ll long longll n,m,a,ans,ans2;int i,j,k;char iptch[999];char ansch[99];int anschlen;void num2a(int o){int i
2021-03-09 13:31:54
233
原创 长远打算
unity会的不少了，感觉做一些小型的开发项目已经足够了。。所以现在的问题在于提升自身综合素质了比如 搞搞竞赛题，搞搞acm（吃老本），顺便还可能搞搞电子设计大赛，找找英语材料，也可能会整一些公式，学一下AI、网络编程什么的。。总之往学习方向靠吧，感觉整些虚的好像用处不大，或者能出现的机会太少了而且一直玩的游戏基本已经倒了，而且电脑打csgo都热的卡，二次元、美剧啥的看一会也就没兴趣了，所以反而感觉娱乐不舒适了。...
2020-05-21 03:44:37
242
原创 C#中结构体排序方法（Array.sort() + ICompare）
感觉C#比C++麻烦许多，资料也少，找了半天竟然没有找到一个能用的结构体排序。这是待排序的结构体： public struct la { public int id; public int sb; };首先，C#需要调用一个空间（类似头文件）using System.Collect...
2019-08-29 00:54:11
3384
6
原创 bzoj3944 Sum 杜教筛
模板题，注意杜教筛化式子的技巧：1、构造求和函数2、利用积性函数约数性质3、做差算出单项4、约数倍数转化贡献5、分块求商码：#include<iostream>#include<cstdio>#include<map>#include<cmath>using namespace std;#define M 3000000#define l...
2018-03-16 14:54:22
267
原创 bzoj4820 [Sdoi2017]硬币游戏 高斯消元+概率+kmp
有环的概率是可以高斯消元的由于匹配情况可能从一个串转移到另一个串，所以需要建一个转移关系的图就可以建一个ac自动机，但节点数是nm的。就可以设未知数，然后凑一些方程。设N表示没有任何人获胜的概率（允许有前缀）然后N+ A串/B串/...n串 一定会停止。一定会停止的情况只有N + n种串。若 A=HTH B=THTN + HTH = （...A + TH ） + （......
2018-03-09 15:04:50
321
原创 bzoj4600 [Sdoi2016]硬币游戏 sg函数+结论
sg[maxQ][二的次数][三的次数]=前面的都是正面的胜负状态C不一样的相互独立首先顺序是不重要的，因为他有一个模仿关系。比如 9,3是0 必胜策略是 选9翻9 、3 由于是异或，所以必胜策略可以理解为 选9 翻 9 ，这样3的位置就需要翻两遍，也就相当于翻0次就可以理解为3这位置状态已经是0（实际操作相当于可以模仿掉）所以如果存在必胜策略，一定可以拆为每个点sg值的若干组合。选...
2018-03-07 10:50:22
435
原创 bzoj4598 [Sdoi2016]模式字符串 hash+点分
哈希也是有技巧的。不然很容易错。匹配串范围是1e6的，所以普通hash错误概率也是很大的所以就要利用匹配的特性（长度与匹配串一一对应）来hash，这样错误概率会小，相当于hash挂链吧。一开始写的每个前缀hash存位置。这样一个hash里就有1e6个值。码：#include<iostream>#include<cstdio>#include<vector>...
2018-03-06 20:18:19
279
原创 bzoj4515 [Sdoi2016]游戏 标记永久线段树+链剖+差分
树上路径问题还有一个比较好的差分就是利用到根节点的信息。。题目的形式显然是一个一次函数，于是想到维护一次函数最小值上升路径就是： A(d[x]-d[o])+B = -Ad[o]+(B-Ad[x]);下降路径： A(d[x]+d[o]-2*d[lca])+B = Ad[o]+(B+A(d[o]-2*d[lca]))维护新函数 ，查询的时候分下去查。。由于需要区间答案，所以就需要u...
2018-03-04 10:33:37
242
原创 bzoj1568 [JSOI2008]Blue Mary开公司 标记永久化线段树
维护n条直线，保存斜率和截距。注意维护的时候分类讨论：1、两端都大于2、两端都小于3、交点在中点左4、交点在中点右注：点数不是询问数初值码：#include<iostream>#include<cstdio>using namespace std;#define N 100005double k[N<<2],ans,b[N<<2],K,B;...
2018-03-03 14:12:28
166
原创 bzoj4513 [Sdoi2016]储能表 dp
这种数位dp第一次见。。其实应该是利用位运算相互独立来避免后效性一般的数位dp只有一个范围 这个题有三个范围。。由于数位和整个数的大小没直接关系，所以就需要用状态记录首先不合法的一定不转移，对于n和m的限制 ，一位合法的话有可能出现后面无论如何都合法， 与后面的数不能小于剩下的数，由于比他大的都不合法了，所以剩下的一定是与n、m前面几位相同的所以就设计状态1表示前面几位都与n/m/k相同 0表示...
2018-02-27 15:00:42
181
原创 bzoj4514 [Sdoi2016]数字配对 费用流
千万不要想复杂了，倍数和质数仅仅是判断两点之间能不能匹配的条件。。主要问题还是一个分配问题一开始想贪心，但好像不对，然后就由反例推出了关系图，然后就是二分匹配问题。。由于每个点入的量+出的量==数量，由于一次匹配要流两条边，对于原图是很难限制的；但由于对称性，所以就直接建两个方向的边即可。。码：#include<iostream>#include<cstdio>#inc...
2018-02-25 21:00:43
220
原创 bzoj4602 [Sdoi2016]齿轮 边权并查集
把并查集的树形结构画出来，尝试路径压缩，就是直接把边权乘起来，表示当前节点转1圈，父节点转几圈。。如果卡精度可以用取log或分解质因数。码：#include<iostream>#include<cstdio>using namespace std;int mb;double la,lb;long double v[10005],a,b;int x,y,fu[10...
2018-02-25 16:24:40
211
原创 bzoj2756 [SCOI2012]奇怪的游戏 结论+网络流
首先这个题有一些情况不满足二分的性质，即黑白块数不相等的情况，这种情况满足的最后数字是可以直接求出来的因为有解的条件 x*cnt1-ans1==x*cnt0-ans0，x是唯一解相等的情况 上式就等价于x=x。。所以另外一个解的判定方法就是按照当前x能不能及时分配完，由于点与点之间的关系连成一片，要用网络流注意eps的大小！！码：#include<iostream>#include...
2018-02-24 20:34:23
188
原创 bzoj1296 [SCOI2009]粉刷匠 区间dp+背包
每一条都是独立的，所以可以分开处理对于一条，粉刷一定是粉刷完完整的一条是最优的（不会有比它优的），所以枚举次数起点转移不同条之间就是分组背包的关系了。。码：#include<iostream>#include<cstdio>#include<cstring>using namespace std;int ff[5555],fff[5555],g[5555...
2018-02-24 15:36:42
264
原创 bzoj1069 [SCOI2007]最大土地面积 凸包+单调性
先做凸包 枚举对角线，然后两个指针单调的扫。。枚举的顺序有时候也会创造性质注意重点不能选！码：#include<iostream>#include<cstdio>#include<algorithm>using namespace std;int top,i,n,sta[9999],l,r,j;long double ans;struct la{...
2018-02-24 14:46:32
218
原创 bzoj1293 [SCOI2009]生日礼物 单调队列
比较好想的单调队列码：#include<iostream>#include<cstdio>#include<algorithm>#include<map>using namespace std;long long l,r,ans=2147483649,x;map<long long,int>ma; int b[99999],...
2018-02-23 18:16:23
196
原创 bzoj1024 [SCOI2009]生日快乐 结论+dfs
一定不要想复杂了，虽然他看起来和二分的条件一模一样切的时候一定是切在等分点上，所以就枚举等分点切就可以了。。感觉应该有更简单的结论码：#include<iostream>#include<cstdio>using namespace std;double x,y;int n;double dfs(double x,double y,int ys){ if(ys...
2018-02-23 15:49:27
166
原创 bzoj2460 [BeiJing2011]元素 贪心+线性基
线性基其实和向量关系很近。只是他们都是单位向量然后重复的01组判断方式类似高斯消元判无消方程的情况由于出现无解方程类似于一个环，所以这个线性无关组就类似一棵树，所以就可以用类似kruskal的方法求最大线性无关组相当于带权最大生成树码：#include<iostream>#include<cstdio>#include<algorithm>#define ...
2018-02-22 12:26:59
179
原创 bzoj1193 [HNOI2006]马步距离 构造+枚举
首先肯定不是直接按xy跳，因为会有几个特殊位置：(0,0)到(1,1)(0,0)到(1,0)(0,0)到(4,4)正常逼近是那长距离跳2，短距离跳1，但在这几个类似的点上是不行的首先，一定会有一段两个坐标都逼近的一部分，而且还很多都逼近的话，一定是当前位置最优解，但只逼近的话，当前位置不一定能落在目标点上通过手玩可以发现，这种情况，离目标点的距离已经非常近，在考虑接下来怎么走，实际上也可以考虑成从...
2018-02-18 16:50:50
286
原创 bzoj 2962 序列操作 线段树
这个题卡常数。。首先c比较小，所以可以考虑dp转移，对于合并子序列就直接枚举跨区间的就可以了对于反转操作，要注意只有奇数位置才会变成相反数对于增加操作，可以考虑抽象成组合数学问题：对于(a1+b)*(a2+b)+(a1+b)*(a3+b)+(a2+b)*(a3+b)，拆下来就是每一项都会和不同的两项相乘，转化到上图上就相当于每组选k个左边的，c-k个右边的，然后组合数学算一下就可以了码：#incl...
2018-02-11 07:45:57
299
原创 bzoj2127 happiness 最小割
不要往费用流上想，要往最小割上想，舍弃的权值最小，然后就想一下放到哪边有哪些贡献，不同位置会割掉不同贡献的边，然后枚举各种割的情况，赋边权就可以了码：#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;#define N ...
2018-02-08 14:48:52
199
原创 bzoj1070 [SCOI2007]修车 费用流+拆分
这个题一开始容易想到最暴力的建法，由于前面的决策影响后面的人的等待时间，所以就枚举第几个选第几辆，由于有后面受前面影响，所以也可以看成前面对后面影响，影响的最多n个，所以就枚举影响建图，由于3辆车 安排4个一定不如3个优，就没有后效性了码：#include#include#include#includeusing namespace std;int tot=-1,ho
2018-02-07 21:34:32
180
原创 bzoj3190 [JLOI2013]赛车 半平面交
思路和求凸包有点像首先根据初始位置排序，然后同位置按斜率升序然后加一条直线就暴力找就可以了（可以二分）存每条直线的选取区间，然后由于有效的斜率单增，所以若覆盖了就是最后一个要注意多条直线交于区间端点和 直线重合，由于后面的点一定被覆盖 ，直接加进前一条直线即可，然后这条直线加在最后面，作为最后一个区间的最高直线码：#include#include#include
2018-02-07 17:36:16
220
原创 bzoj3192 [JLOI2013]删除物品 树状数组
每次操作一定是直接换到当前最大的，所以相当于来回移动求移动次数把两个栈拼在一起就是一个队列，然后就直接查询个数+删点统计答案，用树状数组码：#include#include#include#includeusing namespace std;int n,v[100005],n1,n2,a[100005],lin[100005],i,wz[100005],zz,l,r
2018-02-07 10:14:14
190
原创 bzoj3551 [ONTAK2010]Peaks加强版 kruskal重构树
最大边最小，就是最小生成树，可以考虑用主席树维护father数组，但不能遍历子集查找然后就只能牺牲一部分空间时间来多存一些东西多存的就是边值大小顺序，本来以为是用主席树排边值，结果由于此题有2种数据（边值、点值）要排，所以每加一个边维护点值排序空间是不对的然后就按照边重构一棵树，尽量利用以前的结果，由于主席树类似桶排，利于合并，所以就直接指针指过去就可以了就是在原来并查集合并的基础
2018-02-06 21:26:34
181
原创 bzoj4569 [Scoi2016]萌萌哒 并查集+st表
这个题非常巧妙，它描述了一种新的延迟标记关系。。正常的线段树是用n*4的空间描述一个序列，所以对于一段区间，有可能会有log个点对应一个点而线段树是利用尽量小的空间使查询变为logst表是nlogn的空间，对于一段区间，是可以做到一一对应的，它只是预处理比线段树暴力了一些所以这个题要放到线段树上的话就需要对两个区间进行拆分，在线段树的节点上更新father数组这样散开的点有可能
2018-02-05 20:01:03
211
原创 bzoj4415 [Shoi2013]发牌 线段树
相当于找区间第k个数，同时支持删点这个题的线段树操作和noiD1T1有点像。所以调了半天。注意对size取模，注意查找区间第k的时候的特判码：#include#includeusing namespace std;#define zuo o<<1,l,mid#define you o<<1|1,mid+1,r#define N 700005int sz[N<<4
2018-02-03 20:15:43
219
原创 bzoj4417 [Shoi2013]超级跳马 矩乘
在手玩的时候找转移的规律，发现可以奇偶分类，不同奇偶的点相邻3行全都可以+1转移，同奇偶的点不可以转移所以对于每一行，都记录奇偶两种的前缀和，就可以省去扫同行的点注意，由于是两两转移，要注意区分12->34 中的1->4和 1->2，为了避免3->4就需要独立的12->3 12->4可以以3为桥梁 12->3->4，注意写清楚不要乱注意特判n=1码：#inc
2018-02-03 17:34:05
310
原创 bzoj4419 [Shoi2013]发微博 差分
这种题一般都是差分，而且只用推一层，所以对于加边和删边就直接差分消除影响即可注意统计答案的时候还在的边也要统计，相当于做删除处理，扫一遍加边删边即可判断，注意在vector里可能出现多次，只统计一次码：#include#include#includeusing namespace std;vectorv[200005],chu[200005];int n
2018-02-03 10:52:50
176
原创 bzoj1935 [Shoi2007]Tree 园丁的烦恼 二维偏序
其实这个题就是一个二维偏序，注意不要往树套树上想了用容斥求出4个点的偏虚前缀和保证y保证x>要求点，就树状数组求前缀和码：#include#include#include#includeusing namespace std;struct dian {int x,y,id,wz; }D[2000005],W[8000005];int v[12000007],n
2018-02-02 21:46:02
245
原创 bzoj1934 [Shoi2007]Vote 善意的投票 最小割
一上来容易想到缩点dp，但由于一个集合是没法用状态表示的，所以不能dp然后就可以想到最小割，即通过割边和代价完成分配；就比较好做了，默认选0就和0连边，默认选1就和1连边，朋友之间连边，如果在同一个集合里不会产生流量，如果在不同集合里会产生代价为1的流量码：#include#include#include#includeusing namespace std;#defin
2018-02-02 14:23:22
178
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人