好的,在h^ovny的安利下做了此题 模拟退火中的大水题，想当年联赛的时候都差点打了退火，正解貌似是三分套三分，我记得上一道三分套三分的题我就是退火水过去的... 貌似B班在讲退火这个大玄学...   这题还是比较简单的啦~ 随机化坐标x,y就可以啦 然而格式错了n遍.....死的心都有了 最后输出是四舍五入！！！四舍五入！！！四舍五入！！！ 两组答案中间有空行！！！有空行！！！有空行！！！   然后只要会退火的板子就可以啦   //LevenKoko#include<bits/stdc++.h> using namespace std; inline...

题目描述：   给定一个 n个点m 条边的带权无向连通图 ，以及一个大小为k 的关键点集合S 。有个人要从点s走到点t,现在可以对所有边加上一个非负整数a,问最大的a，使得加上a后，满足：s到t的最短路长度=s到t且只能经过S中的点的最短路长度。 题目分析：   暴力   记x为只经过关键点的最短路长度，其路径条数为n   记y为可经过任意点的最短路长度，其路径条数为m    tip:路径条数意思这里指 覆盖最短路的边数   显然全部加上a之后最短路是不变的   也就是说我们要求这个东西 $$a*n+x=a*m+y$$ $$a=(\frac{y-x}{n-m})_...

哈希+分治+stack 题目： 给你一个由小写字母组成的字符串s，要你构造一个字典序最小的（认为左括号的字典序比右括号小）合法的括号 序列与这个字符串匹配，字符串和括号序列匹配定义为：首先长度必须相等，其次对于一对匹配的左括号和右括号 i,j，必须有s[i]==s[j] 无解输出-1   很坑：括号配对原来是最近的左括号右括号算一对...我以为随便怎么配只要左括号右括号数量相等且能左右分离就好了... 首先是判断无解情况：开一个stack，碰到和top相同的弹掉，如果最后stack不空就必然无解   然后是分治即可 显然对于Solve(l,r)的l元素的'('我们要找离其最远的...

  由于这里机房电脑不太适应，导致一系列问题   下了一个chrome最新版的安装包却发现压缩包里面是空的   网上解决方案基本上是没(che)用(dan)的，什么压缩包就是空的，有密码之类的   正解是下载最新的压缩软件，并且用这个软件重新打开刚刚下载的压缩包就可以了

比较easy的一道题 裸字符串哈希即可 前置知识简单易证: S(l,r-x/p)=S(l+x/p,r)和S(l,r-x/p)是S(l,r)的循环节 这两个命题是互为充要条件的 (x是当前求出的循环节长度，p是x的因子) HASH一下枚举x比较S(l,r-x/p)和S(l+x/p,r)即可 1 #include<bits/stdc++.h> 2 #define ull unsigned long long 3 using namespace std; 4 inline int read(){ 5 int ans=0,f=1;char chr=get...

原来这个也叫做倍增... 懒得打$lat_{e}^x$，就直接贴图了   这个数据正解应该是矩阵快速幂的，但是大佬们想出了各种神奇的方法，一个个数竞的一样... 实现的话要记忆化，因为是二维的大数，所以直接用map就好了 然后的话，因为组合数要求的其实很小，你直接杨辉三角上是一样的..   1 #include<bits/stdc++.h> 2 #define int long long 3 using namespace std; 4 inline int read(){ 5 int ans=0,f=1;char chr=getchar(...

竞赛课想找一道水一点的tarjan题，看看这么久没做题手感有没有掉... 结果这题貌似不是tarjan啊...应该是LCA...假的标签！！ 一遍过样例+一遍AC祭（好吧这么水的题也没啥好开心的）   大概就是给一棵树，和两条路径，判断两条路径有无公共顶点。   随便画一棵树，然后会发现，两条路径有公共部分的话，必定有一条路径（的两个端点）的LCA在另一条路径上 这样我们只要判断一个节点是否在一条路径上即可 然后联想到绝对值的几何意义（反正我是这么想到的...）满足以下规律的才有可能满足节点lca在路径a-b上 $$dis(lca,a)+dis(lca,b)==dis(a,b...

跟那个某省省选题(具体忘了)游走差不多... 把边搞到点上然后按套路Gauss即可 貌似有人说卡精度，$eps≤1e-13$，然而我$1e-12$也可以过... 代码： 1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #define writeln(x) write(x),puts("") 6 #define writep(x) write(x),putchar(' ') 7 us...

高斯消元裸题。。。 方法一：暴力，O（2^n）20分 方法二：直接Gauss,加点玄学技巧搞得好的话70分 方法三：使用bitset优化，复杂度：$O(\frac{n^3}{ω})$   不会的同学看一下代码吧，跟裸Gauss差不多...只不过消元地方用异或消 真的是代码一看就懂了呢...   1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<bitset> 5 #define writeln(x) write(x),pu...

祭一下第一道独立做出来的高斯消元(虽然在各大佬看来都是水题...) 首先这道题给了你n+1个一次方程，n个未知数 其中有一个方程是错误的 求解在合法的前提下最大的未知数是多少... 显然高斯消元... 关注到\(n≤100\)所以\(n^4\)的算法是极限 高斯消元复杂度是\(n^3\)所以我们可以暴力枚举那个方程是错误的 之后判断合法性即可... 总之也不是很难啊，关键是不要忘记illegal...刚开始程序末尾的illegal忘了然后就Subtask2 WA了一个点... 直接看代码直观一点呢 #include<cstdio> #include<ios...

并不知道今天有比赛 比赛13:15开始，然而13:35才到机房... 只有我和jjc... 于是想起数学作业单元AB还没改...又改+订正了好久... 14:15左右被通知去机房3打比赛... 然后忙着把剩下的题写完之后有人来QQ找我... 回复了一下...本来想着晚上再说的...结果貌似那个人下线了... 总之大概14:30左右开始的比赛...   %%%MinamotoAK虐全场%%%初二神仙lch%%% 又掉rating了....   第一题： 好像很水的样子... 水了个树形DP... 然鹅样例RE了... 忘记return了... 既然好像大家都做出...

rctc: 模拟赛T1map大暴力水过了...T3在GTX大佬一句“SPFA就好了呀”下乱口胡了一个SPFA里面套个DP竟然也A了...感觉RP用光了 题目描述   小 H 是个善于思考的学生，她正在思考一个有关序列的问题。 她的面前浮现出了一个长度为 n 的序列{ai}，她想找出两个非空的集合 S、T。 这两个集合要满足以下的条件： 1. 两个集合中的元素都为整数，且都在 [1, n] 里，即 Si，Ti ∈ [1, n]。 2. 对于集合 S 中任意一个元素 x，集合 T 中任意一个元素 y，满足 x < y。 3. 对于大小分别为 p, q 的集合 S 与 T，满足 ...

很早就看到这题了...但因为有个IOI标志，拖到现在才做 由于是以前在书上看到的，就没有想过其他算法，直接区间DP了... 方程式也挺好想的 跟我们平时做数学题求几个数乘积最大差不多 最大的*最大的 最小的*最小的（可能是负数） 这样两种情况 由于求最大中要用到最小值，我们在维护最大同时维护最小 最小的*最小的 最小的*最大的 也是两种情况 再考虑加法 最大：最大+最大 最小：最小+最小 各有一种情况 Tip 上面所述的类似于最大*最大都是左区间最大/小 和右区间最大/小 表达起来大概是这样的 ...

来一发大暴力 树链剖分无疑了 对于某个询问节点，二分答案所在的深度，若该深度到该节点上的区间和>0，说明其中有满足条件的点，增加深度继续二分，否则减小深度 线段树上的操作：单点修改+区间查询（区间和） 关于时间： 时间复杂度\(O(nlog^{2}n)\) 虽然不是最优解法，但能过了，稍微卡一下，总时间大概900ms,最大点300ms,如果\(O(nlogn)\)的玩家太注重卡常的话还是可以碾的,当然我的代码还有优化余地...（比如传参部分可以用空间换时间，卡常玩家可以尝试一下（还有fread之类的都可以尝试一下）） 关于最优解法：我有一个绝妙的思路，这里篇幅太小写不小，你...