T1 打地鼠 全场就俩人没切,还有一个是忘关$freopen$了. $code:$ 1 #include<bits/stdc++.h> 2 #define rin register signed 3 using namespace std; 4 const int NN=2e3+5; 5 int n,k,pre[NN][NN],ans; 6 char ch[NN]; 7 inline int read(){ 8 int x=0,f=1; char ch=getchar(); 9 while(c

Description In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the o

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4612 简单图论题,先求图的边双连通分量,注意,此题有重边(admin还逗比的说没有重边),在用targan算法求的时候,处理反向边需要标记边,然后缩点,在树上求最长链.. 此题在比赛的时候,我的模板数组开小,WA一下午,sd.... //STATUS:C++_AC_734MS_37312KB #include <functional> #include <algorithm> #inc

[问题背景] zhx 和他的妹子(们)做游戏. [问题描述] 考虑 N 个人玩一个游戏, 任意两个人之间进行一场游戏 (共 N*(N-)/ 场) , 且每场一定能分出胜负. 现在,你需要在其中找到三个人构成“剪刀石头步”局面:三个人 A,B,C 满足 A 战胜 B,B 战胜 C,C 战胜 A. [输入格式] 第一行一个正整数 N,表示参加游戏的人数. 接下来 N 行,每行 N 个数 /,中间没有空格隔开.第 i 行第 j 列数字为 表示 i 在游戏中战胜了 j.所有对角线元素(即第 i 行第 i

题目链接 \(Description\) 给出一个n个点的有向图,任意两个点之间有且仅一条有向边.对于每个点v,求出从v出发的一条经过点数最多,且没有重复经过同一个点一次以上的简单路径. n<=2000 \(Solution\) 详细题解在这 竞赛图缩点后得到的拓扑图一定是一条链,因为竞赛图任意两点前后关系确定,所以只有一种拓扑序列 从前边强连通分量中的任意一点出来 都可以到达后边强连通分量的任意一点 因为竞赛图的每个强连通分量一定存在一条哈密顿回路 所以只需要求出每一个强连通分量的哈密顿回路,

4727: [POI2017]Turysta Time Limit: 20 Sec  Memory Limit: 128 MBSec  Special JudgeSubmit: 117  Solved: 39[Submit][Status][Discuss] Description 给出一个n个点的有向图,任意两个点之间有且仅一条有向边.对于每个点v,求出从v出发的一条经过点数最多, 且没有重复经过同一个点两次以上的简单路径. Input 第一行包含一个正整数n(2<=n<=2000),表示点

因为是我这只蒟蒻个人的汇总嘛,可能有些奇♂怪的东西或者不规范的语言出现啦,见谅见谅 搬了一些到知识汇总里,删了一些过时和无用的,少了好多=.= 1.STL_queue 经实践验证,!qs.empty()快于qs.size() 2.luogu p2114 起床困难综合症 if(位运算) 括号++; update on 2018.7.2: 发现位运算的优先级比小于号那一堆还低... 3.luogu p1853 投资的最大效益 当背包问题中代价/价值为$kn$时可以在循环中用$kn/k$来表示,这样可

目录 DP 四边形不等式 数论 & 数学 数据结构 树链剖分 左偏树的性质及\(O(n)\)的构造 图论 树 二分图 竞赛图 平面图 双连通分量 字符串 后缀自动机 复杂度分析 没什么好写的..(懒得补) 一些博客:http://www.cnblogs.com/GuessYCB/p/9090878.html http://www.cnblogs.com/fenghaoran/p/remember.html DP 四边形不等式 参考 一般对于如下形式状态转移方程:\(f[i][j]=\min\ o

使用说明:题意和数据范围都只是回忆内容,仅供参考.题解陆续补上. Day 1 第一题 题意:给定n个数字,要求划分成k的连续段使得每个连续段内的数字之和相同,求最大的k.n,Σai<=10^6. 算法:模拟 题解一:记sum=Σai,从大到小枚举sum的因子暴力O(n)判断,10^6范围内的因子个数至多200~300个,且数据无法构造卡到上限(中途退出),可以轻松通过. 题解二:统计所有前缀和记录到同数组b[]中(即b[i]表示存在大小为i的前缀和),从大到小枚举sum的因子x后,计算每一个k*

Description 在Byteland一共有n个城市,编号依次为1到n,它们之间计划修建n(n-1)/2条单向道路,对于任意两个不同的点i和 j,在它们之间有且仅有一条单向道路,方向要么是i到j,要么是j到i.换句话说,这是一个n个点的竞赛图.Byte asar居住在1号城市,他希望从1号城市出发,沿着单向道路不重复地访问一些城市,使得访问的城市数尽可能多. 请写一个程序,帮助Byteasar计算有多少种道路修建方式,使得从1号点出发的最长简单路径经过点数恰好为k,由 于答案可能很大,请对P

题意: 做法来自 首先竞赛图缩点后是一条链,\(1\)号节点在开头的那个\(SCC\)中,因此从\(1\)号节点出发的最长链即为\(1\)号节点所在的\(SCC\)的大小\(+1\)号节点拓扑序之后的所有\(SCC\)的大小之和. 设\(f_i\)表示\(i\)个点的竞赛图数量,显然有\(f_i=2^{\frac{n*(n-1)}{2}}\). 设\(g_i\)表示大小为\(i\)的竞赛图且是\(SCC\)方案数,有: \(g_i=f_i-\sum\limits_{j=1}^{i-1}C_i^j

并没有传送门qwq 思路 首先要知道一个结论(或者说是一个套路):一个竞赛图缩点之后必定是一条链. 那么强联通分量的个数,就是这条链的边数+1. 考虑一条边什么时候会出现:当且仅当点集可以被分成\(S,T\)两个集合且他们之间的边全都是\(S\rightarrow T\)的. 那么\(m=0\)时可以枚举点集大小,那么答案就是 \[ 1+\sum_{i=1}^{n-1} {n\choose i} (\frac 1 2)^{i(n-i)} \] \(m>0\)时仍然考虑枚举点集大小,此时每条链上的

5215: [Lydsy2017省队十连测]商店购物 可能FFT学傻了,第一反应是前面300*300背包,后面FFT... 实际上前面背包,后面组合数即可．只是这是一道卡常题,需要注意常数．． //Achen #include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #incl

HZ 游记 Day -1 收拾东西,准备出发. 话说这几天一直比较懒,也没什么心情和效率学习,颓废好几天了,希望到衡水以后能感觉好点. 不知道衡水有没有妹子 非常想看看衡水的样子,但是又害怕封闭式教学QWQ. 不过不知道为什么总感觉,接下来在衡水除了学OI还会得到些很重要的东西. (预言flag) QAQ Day 0 晕车1小时到南站,差点吐到车上. 到了以后一个人也没没到,开始调教输入法. 看Alan火柴人一直到Cyber_tree十点多来. 车上玩一会阿瑞斯病毒玩一会群星有点晕,Cyber_

T1:农场 题意:有一个长为 $n$ 的序列 $a$,要求将其分成尽可能多的部分,使得每一部分的 $a_i$ 的和相等.求最多能分成的部分数. $30\%:1\le n\le 1000$ $80\%:1\le n\le 10^5$ $100\%:1\le a_i\le 10,1\le \sum a_i\le 10^6$ 这题不难,说一下我在考场的思路: 首先答案应该是 $\sum a_i$ 的约数.那么可以转化一下,变成找到满足要求的最小的和(也是其约数) 进一步想到前缀和.我们发现 $x$ 满

day1 100+95+0=195 T1 二分答案,并查集,很像noip2017 day2 T1 T2 缩环,然后数据结构维护求答案,貌似也是原题 T3 树形dp,比赛上没有做出来, day2 90+70++60=220 T1 dp随便维护一下,比赛上没看清题意,没有注意到-1的情况 T2 树链剖分,我打错一些细节,只有70分 T3 正解圆方树,要缩点双. 我一开始以为可以缩边双+树链剖分,结果水了60分 day3 30+10+10=50 T1 坑,被水淹没,不知所措. 亦或就相当于于交换,连边

建造城市 题解 先思考一个简单问题 10个$toot$ 放进5间房屋,每个房屋至少有1个$toot$,方案数 思考:插板法,$10$个$toot$有$9$个缝隙,$5$间房屋转化为$4$个挡板,放在toot缝隙之间得到$C_{9}^{4}$ 10个$toot$ 放进$5$间房屋,每个房屋里可以没有$toot$,方案数 思考:插板法使用条件必须是每组至少有1个,那么我们事先在每个房屋中放一个$toot$变成$15$个$toot$放进$5$个房屋,可以插板法,与上一题类似$C_{14}^{4}$ 那

\(\color{white}{\mathbb{百般红紫博众爱,正是芳菲斗艳时,名之以:牡丹}}\) %%% szs巨佬AK \(t1\).\(t4\) 都会做,剩下两道好像都不太会,再次扫描到知识盲区--竞赛图 特殊的 \(dp\) 题还是很难设计出一个标准的状态 (t1过水已隐藏) B. 竞赛图 数据范围小一看是状压,然而并不知道竞赛图的性质,于是瞎推一阵后只打了个 \(tarjan\) 暴力,一测 \(19\) 的点跑了 \(2.3s\),以为能蹭过 \(60\) 的点(然而最后并没有)

洛谷题面传送门 nb tea 一道! 首先考虑怎样入手分析这个看似非常不可做的问题.首先题目涉及高度无穷的树,根本枚举不了.不过我们冷静一下就会发现,如果我们记 \(mx=\max\limits_{i=1}^{n}\text{dep}(T_i)\),那么由于初始树的集合中不存在深度 \(>mx\) 的树,因此所有可以生成的深度 \(>mx\) 的树都经过了生长操作,也是说: Observation \(1\). 对于某个深度 \(d>mx\),存在深度为 \(d\) 的树不能通过生长得到

Warm up Problem Description   N planets are connected by M bidirectional channels that allow instant transportation. It's always possible to travel between any two planets through these channels. If we can isolate some planets from others by breaking