Category Archives: 信息学
膜拜各路神犇。
埃及卢克索wf游记
Day -1：
托渡渡鸟的福，成功获得了取luxor旅游的机会。本来应该去年就能去了，结果遇到了战争又又又推迟了，多灾多难的一天。。。。
做动车来到了广东省，看到ddd它们还在泡澡。。最后直到机场才会和。
在广州火车站到机场的路上做的ingress mission
到埃及开罗转Luxor的时候发现自己机票不是连买的，来不及取托运行李了。。结果行李·就落在开罗到Luxor的时候就剩包了。。我就不应该托运行李。。。
到了Luxor以后和xjtu的人聊天，还有2个人没到。。老师不来了。。。还在想我行李的事。之后和jc，jiangly，等等人聚会。。。
中间去了主办方华为那里休息，因为天气很热大家在前台手续很慢的原因大家在那滞留了一段时间
午餐是华为请的比萨。
晚上去华为那里研究如何拿回行李。。填行李牌。。早知道背包空手来了。。
晚上睡过了差点没赶上晚餐。。
这里酒店晚餐很丰盛 差点错过
晚上和dls等人进行了热烈友好的交流 就icpc发展，和算法竞赛培训交换了意见。着重讨论了如何帮助选手进步，如何减小弱校强校之前的差距之类的问题。
Day 0：
今天去报到。，。。上午又来一个·人取拍照。。下午估计还要再来一个人。。
下午
(未完待续）
期末考期间作死囤题的我12月乱做——囤题计划4
期末考期间作死囤题的我12月乱做——囤题计划4
- [Upd 2016.12.29] 话说统一下格式会死吗……写了4份囤题用了4种格式……还好我不是处女……
- [Upd 2016 1.6]今天CF研究了shift-and算法，居然超时我&^(^*&)
- [Upd 2016.1.9] 居然丢失了一部分文档……已经补在后面了……
- [Upd 2016.1.10] 过了facebookHackCup的资格赛……因为网络延时只交了1题好气啊……投诉主席！不过还好总算是过了.今天栗子考完电磁场了大家会不会轻松一点？
【BZOJ 1209:[HNOI2004]最佳包裹】3d凸包
【BZOJ 4247: 挂饰】 背包
int n;
struct arr{
ll a[10000];
ll &operator[](int i) {
if (i<-n) i=-n; if (i>n) i=n;
return a[5000+i];
}
}f;
//这个数组写法好评【BZOJ 1071: [SCOI2007]组队】将题意化简为平面上有一堆点，你需要用某个直角三角形（保证直角边平行坐标轴不能旋转斜边方向为\），问最多能框住几个点。
O(n^2)暴力双指针，这里注意斜边顺序入队，丨边顺序出队。
【BZOJ 4373: 算术天才⑨与等差数列】hash+线段树
【BZOJ 4589: Hard Nim】裸的FFT，见正文
【BZOJ 3670: [Noi2014]动物园】kmp
【BZOJ 2561: 最小生成树】只要看出是最小割就行了。
【BZOJ 2761: [JLOI2011]不重复数字】暴力
【BZOJ 1189: [HNOI2007]紧急疏散evacuate】BFS计算出每个人离每个出口的距离，网络流，二分+拆点，注意一个人不能路过一个出口到达另一个出口（因为出口格子有人数限制）d。
【BZOJ 4551: [Tjoi2016&Heoi2016]树】倒序，并查集
【BZOJ 4195: [Noi2015]程序自动分析】 并查集
【BZOJ 4196: [Noi2015]软件包管理器】 树链剖分
BZOJ 4197: [Noi2015]寿司晚宴】小素数状压dp，每次处理一个大素数
【BZOJ 4198: [Noi2015]荷马史诗】 哈夫曼树，如果k>2时，要通过填0使n\mod(k-1)=1
【BZOJ 4199: [Noi2015]品酒大会】
【BZOJ 4128: Matrix】？？？ BSGS 矩阵
【BZOJ 4180: 字符串计数】矩阵乘法+SAM// 不想写
【BZOJ 4747: [Usaco2016 Dec]Counting Haybales】set
【BZOJ 4748: [Usaco2016 Dec]Cities and States】哈希
【BZOJ 4749: [Usaco2016 Dec]Moocast】暴力建图
【BZOJ 4746: [Usaco2016 Dec]Lasers and Mirrors】直接bfs（变为权限题无法提交）
【BZOJ 2302: [HAOI2011]Problem c】组合数学
【BZOJ 4036: [HAOI2015]按位或】论文题
http://ydc.blog.uoj.ac/blog/336
【BZOJ 4766: 文艺计算姬】矩阵树定理
【BZOJ 4519: [Cqoi2016]不同的最小割】Gusfield算法
【BZOJ 4320: ShangHai2006 Homework】分段讨论
【BZOJ 2671: Calc】mobius反演
大爷题解：http://blog.csdn.net/popoqqq/article/details/45095601
【BZOJ 2661: [BeiJing wc2012]连连看】费用流
【BZOJ 2751: [HAOI2012]容易题(easy)】没修改的数用快速幂求解，修改的暴力
【BZOJ 2731: [HNOI2012]三角形覆盖问题】
【BZOJ 3224: Tyvj 1728 普通平衡树】Treap
【BZOJ 3196: Tyvj 1730 二逼平衡树】Treap
【BZOJ 2733: [HNOI2012]永无乡】Treap+启发式合并
【BZOJ 3287: Mato的刷屏计划】打表找规律
【BZOJ 1797: [Ahoi2009]Mincut 最小割】如何判断一条边在不在最小割上（残余网络跑强连通分量）
【BZOJ 1951: [Sdoi2010]古代猪文】lucas+费马小定理
【BZOJ 4776: [Usaco2017 Open]Modern Art】想法题，2维前缀和
【BZOJ 4804: 欧拉心算】mobius反演
【BZOJ 4805: 欧拉函数求和】杜教筛
【BZOJ 4809: 皇后】就是n皇后
【BZOJ 4800: [Ceoi2015]Ice Hockey World Championship】meet in the middle 搜素，数据范围提示了
【BZOJ 4807: 車】 ans=C(max(n,m),min(n,m))
【BZOJ 4808: 马】二分图最大独立集
【BZOJ 1801: [Ahoi2009]chess 中国象棋】dp,f[i][j][k]为前i行有j列有一个炮 k列有两个炮
【BZOJ 4801:[Lydsy2017年4月月赛]打牌】分类讨论
【BZOJ 4810: [Ynoi2017]由乃的玉米田】bitset+莫队
【BZOJ 4811: [Ynoi2017]由乃的OJ】树链剖分
【BZOJ 4542: [Hnoi2016]大数】如果gcd(p,10)=1,显然一个子串是k的倍数当且仅当它的2个后缀mod p余数相同。
当p是2，5的时候可以根据最后一位判断。
这2种情况都可以用莫队。
【BZOJ 4813: [Cqoi2017]小Q的棋盘】由于起点必须是0号点，不难发现最优决策是走最远点，此时最长链上的边代价为1，其余为2，注意考虑能访问的点不能超过点数
【BZOJ 1078: [SCOI2008]斜堆】模拟斜堆的操作，发现最后一个节点是从根往左一直走直到第一个没有右节点的节点（如果有左节点再向左走一步，那么倒推即可
【BZOJ 4806: 炮】同BZOJ 1801
【BZOJ 3242: [Noi2013]快餐店】树形dp，要么最远点在同一颗树上（dp），要么在不同树上，此时答案=去掉任何一条边后形成的树的答案的最小值，我们枚举去掉的那条边。
由于答案=s[i]-s[j]+dis[i]+dis[j]，i，j可以分开考虑，也可以用线段树解决。
【BZOJ 4878: [Lydsy2017年5月月赛]挑战NP-Hard】染色问题，每次沿边染max，注意最后如果颜色数超过k，则可以按(k+1)-k-...-1的简单路径
FWT代码-BZOJ 4589 Hard Nim
题目：给n个不超过m的素数，求xor和=0的方案数，FWT变换裸题。
题目
2关于F逆元的公式： inv(2)=(F+1)>>1
证： [(F+1)>>1]*2 \pmod F=F+1 \pmod F =1
代码：
#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll F=1000000007LL;
ll iv2=F+1>>1; //Õâ¸ö¼ÆËã˼·ºÃÆÀ
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
void fwt(int*a,int n){
int i,j,k,x;
for(k=2;k<=n;k<<=1){
for(i=0;i<n;i+=k){
for(j=i;j<i+(k>>1);j++){
x=a[j]+a[j+(k>>1)];if(x>=F) x-=F;
a[j]=a[j]-a[j+(k>>1)];if(a[j]<0) a[j]+=F;
a[j+(k>>1)]=x;
}
}
}
}
void twf(int*a,int n){
int i,j,k,x;
for(k=n;k>=2;k>>=1){
for(i=0;i<n;i+=k){
for(j=i;j<i+(k>>1);j++){
x=a[j]+a[j+(k>>1)];
a[j+(k>>1)]=(int)(1LL*(a[j+(k>>1)]-a[j]+F)*iv2%F);
a[j]=(int)(1LL*x*iv2%F);
}
}
}
}
ll pow2(ll a,ll b){
if (!b) return 1%F;
ll p=pow2(a,b/2);
p=mul(p,p);
if (b&1) p=mul(p,a);
return p;
}
#define MAXN (50000<<3)
int b[MAXN],a[MAXN];
ll n,m;
int main()
{
// freopen("bzoj4589.in","r",stdin);
// freopen(".out","w",stdout);
n=50000;
MEM(b) b[1]=b[0]=1;
Fork(i,2,n) if (!b[i]) {
for(int j=2;i*j<=n;j++)
b[i*j]=1;
}
while(cin>>n>>m) {
int len=1;
while(len<=m) len<<=1;
Rep(i,len) a[i]=(!b[i])&&(i<=m);
fwt(a,len);
Rep(i,len) a[i]=pow2(a[i],n);
twf(a,len);
printf("%d\n",a[0]);
}
return 0;
}
BZOJ 五月胡乱补题
BZOJ 五月胡乱补题
@(ACM)
【BZOJ 4806: 炮】同BZOJ 1801
【BZOJ 3242: [Noi2013]快餐店】树形dp，要么最远点在同一颗树上（dp），要么在不同树上，此时答案=去掉任何一条边后形成的树的答案的最小值，我们枚举去掉的那条边。
由于答案=s[i]-s[j]+dis[i]+dis[j]，i，j可以分开考虑，也可以用线段树解决。
【BZOJ 4878: [Lydsy2017年5月月赛]挑战NP-Hard】染色问题，每次沿边染max，注意最后如果颜色数超过k，则可以按(k+1)-k-...-1的简单路径
【4879: [Lydsy2017年5月月赛]失控的数位板】只要把所有的点的最后一次涂色时间求出来就行了。
【BZOJ 4894: 天赋】有向图生成树计数的基尔霍夫矩阵
【BZOJ 3534: [Sdoi2014]重建】 变元矩阵-树定理，求所有生成树边权积的和。把度数改为连出的边权和，A[i][j]=-边权，A[i][i]=连出的边权和.
【BZOJ 4031: [HEOI2015]小Z的房间】矩阵树定理，注意gauss消元辗转相除的写法
【BZOJ 4837: [Lydsy2017年4月月赛]LRU算法】模拟
【BZOJ 4596: [Shoi2016]黑暗前的幻想乡】矩阵树定理+容斥
【BZOJ 3517: 翻硬币】
【BZOJ 4917: [Lydsy六月月赛]Hash Killer IV】
对于t = t + (t << 10); 即 t=t*(1+2^10) mod 2^64 这种操作，
对于 t = t ^ (t >> 6); 显然
【BZOJ 4919: [Lydsy六月月赛]大根堆】树dp
【BZOJ 4488: [Jsoi2015]最大公约数】固定左端点时最多有LogAi个GCD
【BZOJ 1188: [HNOI2007]分裂游戏】算SG
【BZOJ 4950: [Wf2017]Mission Improbable】网络流
【BZOJ 4953: [Wf2017]Posterize】dp
【BZOJ 4956: [Wf2017]Secret Chamber at Mount Rushmore】签到
【BZOJ 4952: [Wf2017]Need for Speed】签到
【BZOJ 2161: 布娃娃】
【BZOJ 4561: [JLoi2016]圆的异或并】考虑一个圆被嵌套了几次，可以扫描线维护
【BZOJ 4556: [Tjoi2016&Heoi2016]字符串】sam
【BZOJ 2143: 飞飞侠】最短路
【BZOJ 2007: [Noi2010]海拔】显然每个关键点的海拔不是1就是0，于是可以用最短路
【BZOJ 4972: [Lydsy八月月赛]小Q的方格纸】前缀和
【BZOJ 4974: [Lydsy八月月赛]字符串大师】KMP
【BZOJ 4975: [Lydsy八月月赛]区间翻转】没执行一次操作，区间逆序对数的奇偶性必然变化。
【BZOJ 4976: [Lydsy八月月赛]宝石镶嵌】n-k\ge log(max(a_i))时，答案显然为所有数的or和，否则n<=116可以暴力
【BZOJ 3659: Which Dreamed It】
【BZOJ 4971: 记忆中的背包】
【BZOJ 5039: [Jsoi2014]序列维护】区间加区间乘区间和，线段树
【BZOJ 4803: 逆欧拉函数】根据Phi(n)的因子反推n可能存在的素数因子，然后暴搜
【BZOJ 3643: Phi的反函数】同4803
【】
BZOJ水题大乱斗2
[upd 2016.9.29] 今天好无聊不如来刷排位
[upd 2016.10.22] 干脆在vjudge上屯着吧
[upd 2016.10.23] 周末10题斩~
[upd 2016.10.28] bc89 fst了B，可怜我的RATING
[upd 2016.10.29] 19点做完！撒花
#50/50
| 题目 | 解法 |
|---|---|
| 2653: middle | 经典题，静态数列强制在线询问区间中位数，可持久化线段树+二分 |
| 3207: 花神的嘲讽计划Ⅰ | 可持久化线段树+uint hash |
| 3932: [CQOI2015]任务查询系统 | 可持久化线段树，离线处理，单点修改，区间前k大和 |
| 2588: Spoj 10628. Count on a tree | 可持久化线段树，静态树，强制在线链上第k小 |
| 3123: [Sdoi2013]森林 | 可持久化线段树，森林，强制在线支持连边，链上第k小，把小的树暴力重构就行 |
| 3744: Gty的妹子序列 | 可持久化线段树，强制在线区间逆序对数 |
| 3289: Mato的文件管理 | 莫队，区间逆序对数 |
| 1025: [SCOI2009]游戏 | \(f{i,j}\)表示前\(i\)个质数中\(\sum_{i=1}^m{p_i ^{m_i}}\) 为j的数的个数，则显然\(f_{i,j}=f_{i-1,j}+\sum_k f_{i-1,j-p^k}\), 初始值\(f_{0,0}=1\),\(ans=\sum_{i=0}^n f_{tot,i}\) |
| 1058: [ZJOI2007]报表统计 | 开2个set |
| 3930: [CQOI2015]选数 | 安利 http://blog.csdn.net/popoqqq/article/details/44917831 |
| 4451 : [Cerc2015]Frightful Formula | fft mod 1e9+7 分块写法 安利http://www.cnblogs.com/clrs97/p/5308851.html 交题在LA7329 |
| 1061: [Noi2008]志愿者招募 | 安利PoPoQQQ的题解[单纯形][http://blog.csdn.net/popoqqq/article/details/44310605] |
| 3112: [Zjoi2013]防守战线 | 和上题没差，单纯形的对偶就是A换成\(A^T\),b,c对调，n,m互换。\(Ay\ge b,min(Cy)\) |
| BZOJ 3308/tyvj P1564: 九月的咖啡店 | 神结论题，只有1， 单个质数的若干幂次，两个质数a,b(\(a<\sqrt n < b\))的幂次的乘积可能取到,附大爷[题解][http://blog.csdn.net/popoqqq/article/details/45725661] |
| 1821: [JSOI2010]Group 部落划分 Group | 对点对连边并排序，并查集贪心 |
| 3555: [Ctsc2014]企鹅QQ | 枚举不同字母的位置，然后2遍hash |
| 3212: Pku3468 A Simple Problem with Integers | 呵呵 |
| 3680: 吊打XXX | 爬山算法http://hzwer.com/4139.html |
| 1193: [HNOI2006]马步距离 | 大范围搜索，小范围暴搜，假设当前(0,0),目标(x,y)贪心的具体方法：当\(x\ge y,x-4\ge 2y\)时，走\((4,0)\),否则走\((4,2)\) |
| 1876: [SDOI2009]SuperGCD | 普通的高精度要处理高精%高精，显然不行，于是使用[stein][http://baike.baidu.com/link?url=QtSt9ZVKwuGIjELH8a3jSuqaVmngX8LDull4siXeR971xC37AK5BTIEOgWNAILEbTJn_PWAEUtMewPiwRm4t3q]加速(Stein算法是针对欧几里德算法在对大整数进行运算时，需要试商导致增加运算时间的缺陷而提出的改进算法) |
| 2843: 极地旅行社 | LCT裸题!板子里居然没有find_root(),o(︶︿︶)o 唉 |
| 2134: 单选错位 | 期望=可能情况/总情况，单独考虑每道题，\(ans=\sum_1^n{\frac {min(a,b)} {ab} }= \sum_1^n{\frac {1} {max(a,b)} }\),其中a,b为相邻两道题的选项数 |
| 1077: [SCOI2008]天平 | 由于天平重量只有1,2,3我们可以计算2个砝码重量差值的上下界，然后dp，安利http://blog.csdn.net/scyjcp/article/details/52622261 |
| 1103: [POI2007]大都市meg | dfs手写栈，求出dfs序，然后用树状数组处理前缀和 |
| 1303: [CQOI2009]中位数图 | 暴力从中位数向两边走 |
| 1304: [CQOI2009]叶子的染色 | 显然随便取一个根节点，然后设\(f_{i,j}\)为子树i在点i染颜色j时的最小染色数，显然有\(f_{i,j}=\sum_{v}min(f_{v,j}-1,f_{v,j\bigwedge 1})\) |
| 1305: [CQOI2009]dance跳舞 | 二分+网络流，将男生成一条容量为k的边\(x\to y\)，如果和喜欢的人，就从x走，否则从y走，女生同理。 |
| 3171: [Tjoi2013]循环格 | 循环格是完美的当且仅当每个点入度出度均为1，所以可以建立2分图跑最小费用流。 |
| 3442: 学习小组 | 本来以为是带上下界的最小费用可行流，结果看到了[Tunix][http://www.cnblogs.com/Tunix/p/4354843.html]的解法，可以跑最小费用最大流了 |
| 3440: 传球游戏 | 找出一堆环加外向树，然后各种特判 |
| 3444: 最后的晚餐 | 显然存在大于3个点的环，或者存在点度数>2是无解的。于是发现有解的充要条件是暗恋关系形成链。\(ans=(a+b)!2^b\) 其中a+b是连通块个数，b是点数\(\ge 2\)的链个数，注意重边 |
| 4236: JOIOJI | 设JOI分别出现x,y,z次，记录前缀的(y-x,z-x)的出现最早位置，扫一遍。 |
| 4706: B君的多边形 | 打表，OEIS - A001003 - super-Catalan numbers or little Schroeder numbers |
| 2741: 【FOTILE模拟赛】L | 分块枚举段首+可持久化字典树 |
| 4260: Codechef REBXOR | 可持久化线段树维护前后缀最优值.jpg) |
| 1019: [SHOI2008]汉诺塔 | 考虑2种移动方法http://blog.sina.com.cn/s/blog_76f6777d0101b8l1.html |
| 1021: [SHOI2008]Debt 循环的债务 | \(f_{i,j,k}\)表示前i种面值分完后，A和B分别有j和k元的最小步数 |
| 3439: Kpm的MC密码 | 反转字符串并把它们丢入字典树，然后用dfs序+主席树求第k大 |
| 1044: [HAOI2008]木棍分割 | 第一问二分答案，第二问dp，滚动数组+双指针优化 |
| 1862: [Zjoi2006]GameZ游戏排名系统 | 同1056 |
| 2780: [Spoj]8093 Sevenk Love Oimaster | 广义SAM求parent树,dfs序求区间内有多少不同权值 |
| 1786: [Ahoi2008]Pair 配对 | 通过交换法可以发现填入的数单调不降，且k很小，可以用O(nk)的dp解决 |
| 1831: [AHOI2008]逆序对 | 同上 |
| 4524: [Cqoi2016]伪光滑数 | http://blog.csdn.net/lych_cys/article/details/51158560, |
| 2734: [HNOI2012]集合选数 | 神奇的dp，http://blog.csdn.net/aarongzk/article/details/50753250 |
| 3438: 小M的作物 | 最大权闭合子图版题 |
| 4245: [ONTAK2015]OR-XOR | 拆位，贪心，每次留下“可选分割点”的位置的集合 |
| 1060: [ZJOI2007]时态同步 | 令\(f_i\)为\(i\)为根的子树的最远叶节点距，然后贪心 |
| 1053: [HAOI2007]反素数ant | 假设x是反质数，设x的约数个数\(\tau(x)=(k1+1)(k2+1)\dots(kn+1)\),和取哪个质数无关，故可认为取的是前k个质数，且k单调不增。。。暴搜 |
| 1087: [SCOI2005]互不侵犯King | 状压dp |
CCPC长春游记
今年下半年赛季第一场比赛，我们去了长春。
Day1：
被强行起了个大早，大约9点出的门，然而比起主席天没亮就出门还是太晚[话说他真的睡了吗]，先是打车去了酒店，然后大巴去了机场，中间耽误了好久，大巴上看到主席在鄂尔多斯~~烤羊腿~~转机的画面……我还是继续睡觉吧……
到了机场已经是接近中午了，由于起得太早没来得及吃早餐（主席：喵~），一行人在机场吃50一份的快餐，可能是由于没糍早餐的报应，lz和mg都糍完了我的那份还在Loading，出门就涱了一波RP。
一路在飞机上睡觉，中途在通辽转机发现主席一伙人已经坐电车~~出去玩了~~找酒店，话说通辽机场阳光好充裕啊去晒日光浴……我还是睡觉吧。。
到了长春才发现自己带的旅行箱完全没用，本来以为零下几十度结果连零都没下1，到旅店时已经很晚了。本来想在下榻的酒店随便叫份外卖，结果被mg拉出去吃烤肉（为什么是烤肉），中间mg策划我们一行人去看电影（嘛反正我平常是不去这种资本主义横行的地方~~还不是因为穷~~），中间主席跑过来说要一起看，结果为了看电影，我点的最后一道菜只好打包带走
大晚上看了最晚一场电影看到半夜，话说明天还起得来吗？
Day2：
没有任何悬念的错过了酒店早餐，和主席它们跑去报道，从南边进去以后看到了一片建筑工地差点以为走错地方，向右拐进入一个小门，话说吉大好厉害好大好豪华好奢侈好享受好度假村，校园里居然有网吧游泳池商厦台球馆电影院美食城汉堡王，一行人打算在汉堡王刷关送的饭票，尽管门口有写让用实际上并不让用，然而等知道了这点的时候队都排完了……なるほど ，那个告示是故意引人入店的》
下午测试赛，发现我们的校徽被人换掉了-((‵□′))- 。我先看了A，结果由于没看出successive 是连续的意思，结果没做出来……，mg开启手算第二题模式，最后仔细一看发现不是Catalan数吗……实力1A，lz徒手找规律，过掉一到本来好像要gauss期望dp的题，我分类讨论一波，强行过掉C。我们队成功开启·真·无双做题模式，1人1T1A，结果榜单上没有我们，仔细一看交错号了（GG)，交到了中科大（喵）去了
然后我们去了伪满皇宫，由于关门进不去，去了旁边的抗日战争主题博物馆，中间大家走散了，出来的时候，主席骗mg说我还没出来，结果mg已经出来了在出口的树下，，敢情被坑的是我……话说都快比赛了这么掉RP没问题吗~
晚上一行人去万达玩密室逃脱，路上被主席一路tc，我们玩得是星际迷航主题，开局是转盘语音容错率低差评，中途逃生舱把写得英文看成请误触碰（我不是故意的……），中间把密码器当工作人员使用的了（自带跳过重要线索光环），后面不明意义的圆盘需要跳回前几个房间，没注意到不做评价，解方程没有使用Hints好评，最后那个Hash表沦落到用Hint（不好意思说自己是竞赛党了），最后结局开船意义不明（强行凑谜题个数）
Day3：
早上起来随便喝了点豆浆上战场，开局看标题，mg默默给题目打上送分，进阶，不可做题的标签2
，开局mg开始手速题，迅速过了Triangle，忘了n=1时\(/gcd\)稍微在 Fraction 下欠了一个罚时，我开局看 Binary Indexed Tree不会做3,改看其它题，中途mg开kmp的Sequence I,由于白书kmp板子有点小问题稍微发了点时间，途中我给出了Harmonic Value Description的构造解做法，一共就几行，稍微挽回了一点罚时。
中途我把Ugly Problem 的解构造出来了，由于要用高精，mg让我上Java，然后mg和lz讨论其他题去了，由于之前想当然漏掉几种特判，再加上太久没用java差点交文件时把类名写错，不辛坑了一波队友（我对不起你们），将近1h才过掉这题，此时只剩下一个多小时了。
继续看题发现Sequence II 之前好像在哪里做过，好开心这不是主席树么（主席：喵~）。二话不说敲了10min板子，结果不小心写了动态开节点的线段树的板子（考得这么残念罪魁祸首），最终mg强行主席树手写成功（中途由于节点数开小了re了一发），然后最后剩15min实在写不了题，进入喝茶聊天给其它队制造压力mode。
考完后弦歌队刚飞机先遛了，留下我们和隔壁西电成员讨论题目解法，话说这次考这么惨4好伤心啊……败北航队dalao，%%众dalao，这次SJTU出的题目质量不错，但最后没有讲题差评。
晚上去了之前玩密室的万达，要么怎么说人家吉大地理位置好。接下来mg带我们队玩了一波街机厅，然后又去打了台球，中途去吃了日本寿司,mg点的太多结果又剩了一堆没吃完。晚上被mg带去网吧~~玩守望~~学习，话说网吧机子配置好好难怪mg经常去网吧。
Day4：
半夜本来想交Uber， 被mg说动走回酒店，结果走了0.5h发现南门校门锁了（bad end），没办法原路返回(0.5 h) ,结果实在受不了打车回去，打车地点离网吧不远sad story. 回到酒店，叫了pizza，结果左等右等pizza就是不来，mg由于手被冻僵了就先去睡了，我等着等着睡着了（最好3点半送到匹萨的时候我意识模糊的接了电话，让它放在楼下，话说直到最后我都没见到pizza）。
虽然和mg立志一定要吃到早餐，然而由于睡前实力忘了闹钟，结果睡到了中午12点5（mg表示中途起来叫我，我翻面继续睡，然后他也继续睡了……）。 为了弥补遗憾，我们一行人去了东北菜馆，点了一桌子菜，结果菜上来才发现是8个人的量，只好打包带走……
本来还打算试试电车，结果由于时间紧，又只好叫了Uber，就这样离开了长春还真是充满了遗憾呢……不过我还是先补完作业再说吧。
后记：主席又打算和妹子出去玩我就不写在正文里了。
BZOJ 水题50乱做
[TOC]
1051: [HAOI2006]受欢迎的牛
显然受欢迎的牛一定在一个强连通分量里,缩点后看看有没有出度为0的点，如果有多个那么无解
4690: Never Wait for Weights
加权并查集
1269: [AHOI2006]文本编辑器editor
rope的使用方法http://blog.csdn.net/iamzky/article/details/38348653
1031: [JSOI2007]字符加密Cipher
后缀数组裸题
3238: [Ahoi2013]差异
后缀数组裸题
1041: [HAOI2008]圆上的整点
数学题，求(a^2+b^2=c^2)(c已知),a,b的正整数解个数
http://blog.csdn.net/csyzcyj/article/details/10044629
1014: [JSOI2008]火星人prefix
splay+hash+二分
1069: [SCOI2007]最大土地面积
平面土地上有N个点，选择其中的四个点，求围成的多边形最大面积。
n<=2000
求凸包，O(n^2)枚举对角线，两侧的点有决策单调性，用一个指针O(1)求
1090: [SCOI2003]字符串折叠
区间dp
3998: [TJOI2015]弦论
SAM
1066: [SCOI2007]蜥蜴
网络流，拆点
1015: [JSOI2008]星球大战starwar
倒着并查集
4443: [Scoi2015]小凸玩矩阵
网络流，动态加边/二分都行
1067: [SCOI2007]降雨量
线段树/RMQ都行，要分类讨论
1042: [HAOI2008]硬币购物
我们先算出不考虑限制时的方案数\(f_s\),如果一个硬币超出限制，那么至少要使用\(d_i+1\)次，此时答案为\(f_{s-c_i*(d_i+1)}\),我们可以用容斥定理解决问题
2298: [HAOI2011]problem a
考虑一个人的话：“有ai个人分数比我高，bi个人分数比我低”等价于“我的排名在\([L,R]\)区间中，这个区间中人的成绩相同“，然后就可以变成线段覆盖问题，贪心即可。
4653: [Noi2016]区间
将区间按长度排序，枚举最长区间长度，显然最短区间长度满足单调性，只需要确认“m个区间共同包含至少一个位置”，用线段树维护最大值即可。
1192: [HNOI2006]鬼谷子的钱袋
k个钱袋最多能凑出\(2^k-1\)的所有钱数
1800: [Ahoi2009]fly 飞行棋
暴力。
1856: [Scoi2010]字符串
回顾卡特兰数的推导过程，发现\(ans=C(n+m,n)-C(n+m,n+1)\)
1801: [Ahoi2009]chess 中国象棋
炮的攻击范围为，横行竖行，跳过一个棋子打一个，距离不限
故原题为求\(n*m\)的矩阵中同行同列只能放至多2个炮的方案数
\(f_{i,j,k}\)表示到第i行，j列放了一个，k列放了2个的方案数
4641: 基因改造
在允许置换的情况下kmp是可以的，hash应该也行
我觉得我应该改改KMP的模板了。。
4602: [Sdoi2016]齿轮
dfs走一遍
3926: [Zjoi2015]诸神眷顾的幻想乡
由于叶子节点不超过20个，所以可以用SAM。
注意拷贝叶子节点时只拷贝c个节点不然会TLE.
4627: [BeiJing2016]回转寿司
线段树裸题
4619: [Wf2016]Swap Space
贪心，证明看得不是很懂
http://www.cnblogs.com/gangding/p/5705400.html
1016: [JSOI2008]最小生成树计数
回忆Kruskal的建立方法，显然每个长度后图的连通性是一定的，具有相同权值的边不会超过10条，dfs就行。
1061: [Noi2008]志愿者招募
经典的问题
https://www.byvoid.com/blog/noi-2008-employee/
3295: [Cqoi2011]动态逆序对
cdq，三维偏序（白书原题）
3996: [TJOI2015]线性代数
经过一堆变形我们发现\(ans=\sum_{i=1}^{n}\sum_{j=1}^{n} B_{i,j}a_i a_j-\sum_{i=1}^nC_ia_i\)
我们把这转化为最大权闭合子图最小割
答案=所有点正权值之和-最小割
3875: [Ahoi2014]骑士游戏
令f_i为杀死i的最小代价，那么有\(f_i=min(K_i,\sum_v{f_{v_i}})\)
状态之前的转移有环，我们考虑《SPFA算法的优化及应用》中提到的算法
3997: [TJOI2015]组合数学
安利Dilworth定理：http://blog.csdn.net/popoqqq/article/details/45171469
4448: [Scoi2015]情报传递
询问离线，树链剖分
1070: [SCOI2007]修车
费用流经典模型
http://www.cnblogs.com/Sky-Grey/p/3862019.html
4418: [Shoi2013]扇形面积并
扫描线，用树状数组+二分判断
1406: [AHOI2007]密码箱
\(x^2=1 \mod n\)等价于\(n|(x-1)(x+1)\)然后暴力枚举因子就行
1038: [ZJOI2008]瞭望塔
半平面交，把分段点（包括边界）取出来
2618: [Cqoi2006]凸多边形
拆成一堆直线半平面交
4517: [Sdoi2016]排列计数
错排公式\(D(0)=1,D(1)=0,D(i)=(i-1)(D(i-1)+D(i-2))\)
有个求一段阶乘的逆元的小技巧
4516: [Sdoi2016]生成魔咒
1.裸sam+map
2.求出反序后字符串的SA,每次添加一个字符串，考虑其对height前后字符串的影响
4514: [Sdoi2016]数字配对
我们发现两个数能配对，则它们分解质因子后的数的个数奇偶性不同，我们可以建出二分图，费用流乱搞
2243: [SDOI2011]染色
树链刨分，把情况转成子节点到父节点的两条链会比较好讨论
3531: [Sdoi2014]旅行
树链剖分，拆成n棵树。记得动态开点减少结点数
3631: [JLOI2014]松鼠的新家
对于加法操作差分，将对链的操作转换为点始末节点的操作，避免后效性,在子节点\(s_i\)+1表示从它开始到根节点均+1，最后统计一遍就行
4034: [HAOI2015]T2
树链剖分时，可用dfs序剖分
3626: [LNOI2014]LCA
操作离线，然后
后加每个点的时候是把从这个点到根的路径的点权全部+1
然后查询就是查询某个点到根的路径的点权和
1191: [HNOI2006]超级英雄Hero
二分图匹配
1143: [CTSC2008]祭祀river
用floyd求传递闭包，建图，原题求最长反链=最小链覆盖
证明：http://www.bubuko.com/infodetail-664202.html
路径不能相交的最小路径覆盖可以用二分图做
路径可以相交的最小路径覆盖（也就是最小链覆盖）可以用floyd求传递闭包建图，转成前面那个用二分图做
2227: [Zjoi2011]看电影(movie)
公式题：ans=(k+1)^(n-1)*(k-n+1)/k^n
神一般的证明：http://www.cnblogs.com/devilpi/articles/3817691.html
1179: [Apio2009]Atm
tarjen缩点+跑一遍dij
4419: [Shoi2013]发微博
用户没有传递性（SB读错题），只有直接关系能看到信息
差分后得到，\(ans_i=t2-t1+t3-t4+...+t_n-t_{n-1}\)暴力维护
CoderCup 2015 游记
:-O 我果然还是没忍住写了这篇游记
以下内容均为黑历史，大家忘掉即可。
话说2015年暑假，在经历过延后1月放假，和提早一周开学集训（请允许我做个悲伤の表情）后，突然从王冠教练那里得到了这份邀请函。
本着不去白不去的念头（喂！！），我给Prime队报上了名（Flag起）
然后出发前一周突然得知王伟戌缓考马哲没法来！！（事后才知道它没参加考试老师却给了73的事）
反正最后把神犇mg拉过来了，一行人浩浩荡荡地杀向北京。
Day -1：
明明和hobo说好提前准备行李，收拾的，可是那天晚上他没把箱子拿来(出发前只打算拿一个箱子登机)，结果不得不明天早起拿箱子。
Day 1：
6：00 AM 我做什么虐大早上起来收拾行李各种吵醒同学伤不起。
到了临时据点（hobo的土豪思远社）之后，又被拉回去叫请假条（我真的不想吵醒同学），回来以后简单的吃了M记
艰难的从西安一路辗转北京然后是地铁，到旅馆后发现mg走错地方了，只好在旅馆等他。
然而hobo去人大泡妹子去了，于是我顺便跟去见最强德语系Acmer CCR， 估计是我认识的Oier中专业最猎奇的。。然而人赢
去了以后看到CCR在外语系招生处搭台顺带 和妹子聊天，聊到了xjtu， 之后回去放东西，一边参观人大，一边看到了妹子i,j,k,l,n 这个人赢
之后去食堂吃饭，据说人大20多处食堂，CCR一年未能尝遍一半，想象xjtu满打满算才2个（康桥，梧桐）不禁以泪洗面..
CCR请客，带我去新专修的食堂，他点了份咖喱鸡，我要了份鱼丸（说这个绝对不是tucaoXJTU） ，看来他在人大混得不错。。。和2妹子组队+CF红名（红名改革后失去该成就）人赢
晚上遇见mg,大家一起刷BZOJ水题。。
Day 2：
今天只是去看场地，反正最后只有景琦去。。
我和mg一觉睡到中午，午餐外卖日料，之后水题一下午。。
晚上的时候让景琦带插板回来*（最后他忘了），得知他这一天主要在泡妹子（换了一个）
Day 3：
一大早去了场地，mg拿出了他心爱的HKB神级键盘，由于我不懂VIM只能觉得这个键盘小巧又漂亮。。
开始练习赛，反正未能抢到一血。。
然后我看场地它们出去上厕所成功遇到岛娘（我错过了），之后我也被赶出去了。。
正赛开始。，。
mg开A题抢一血，中间我们过了水题H,G,然后mg线段树 1小时左右轻松过A
mg发现I题是模板高斯消元开始手速场，然而由于用了景琦提供的错误的sjtu模板不幸被坑，，后来终于AC 2小时
中间我试图过C ,然而看错题， 试图过B 然而OutputLimit exceed
于是我们在接下来卡题模式开启，，我和mg轮流做C，反正最后dp没过。。
没过。。。
没过。。
（柏拉图说：重要的事情说3遍）
由于在2：30以后基本是我在敲代码，，，我获得【 1个黑锅】
于是就这么结束了，
Cu牌。。
下午，它们领我们去颁奖时都不好意思去，，，（后来才知道不去取消奖项，详见北大，这样就没有路费了的说）
最后mg回宾馆，jq又去报妹子（怎么我身边全是人赢）
我悲伤的在颁奖现场画圈圈。。一个两个。。三个四个。。
值得一提的是当时现场抽了10+次奖，奖品从iwatch到奇奇怪怪手机不等，，考虑到实际到场人数，不得不说获奖概率极高。。
（我旁边有人抽到奖，有人被抽到多次（生日攻击） ） 。。。然而好像还是没我什么事的样子。。
最后啃完了现场送的M记以后拍照走人。。我站在后面应该不会被拍进去？？
晚上回到宿舍和mg它们聊天。。
mg和hobo 就 高端烧耳机 》》高端烧键盘？？ hobo高端烧外语游戏(我觉得这个还是有希望的。。）mg高端烧各种音游。。（经过尝试得出自己好像没希望）。。
大家都是人赢啊。。人赢啊。。人赢啊。。
我的Ipad的充电线不见了666666
由于第二天mg要去四川成都看女友（都说凡是认识我的都人赢的反向Flag啊。。）
大晚上晕晕昏昏沉沉的睡着了（真”没心没肺）
Day 4：
一大早去了欢乐谷决定放松心情，，决定拍几张照片放微博以试签到）
(然而由于种种原因手机没电了。。我wtf连个照都拍不了装逼失败，，
为了惩罚自己做了2次过山车。。。（要排很长的队） 话说为什么我一点都不害怕（都说没心没肺。。）
Day 5：
今天因为要打长春的·区域赛~网络赛 所以呆在房间。。
然而由于各种原因 景琦跑出去看妹子了（据说没换。。存疑。。）
最后只有我留在房间打，做了1T以后 不得不下去退房。，。。12：00在宾馆门口提着行李箱风中凌乱。。。
都 是 景琦 害得拉。。 （最后那场区域赛网络赛我xjtu一个名额都没有。。这锅他得背）
于是索性去五棵松会见高中时的同桌+死党 王永鑫。。
他高考后跑到HK刷了一堆经验点以后，成功混入中财大。。现在大一。。
我告诉了大二的悲伤生活。。他默默地莞尔一笑。。
中午我们在五棵松附近不知名快餐店见面，，他请了我一份鸡腿饭+豆浆（说好的全聚德呢），我们在五棵松拍照留念发微信。。如果景琦的VPN给力的话我就发到FB上。。
然后我们去钟楼玩耍，，因为搞错地点被Taxi撂在了离钟楼1km Manhattan距离的：钟楼地铁站
话说这钟楼风格的M记怎么和福州三坊七巷那家那么像。。。怎么又是M记
本来想去不过因为门票太贵没去
最后去逛了逛钟楼附近有名的电玩一条街。。
之后王永鑫和他另外2个同学走了
我一边啃冰棍，一边看路上车追尾的时候
被jq一个电话叫去机场，，，让我歇会儿会死你个人赢。。
最后到机场搞到很晚才走。。
本来想拿行程单结果硬是要用寄的，，不知道寄了多久。。
到学校8，9点了发现自己居然来得及去洗洗澡。。
真是充(dao)实(mei)的1 week
全篇完
Codeforces Round #320 (Div. 1) [Bayan Thanks-Round] 题解
A.
There is a polyline going through points (0, 0) – (x, x) – (2x, 0) – (3x, x) – (4x, 0) – ... - (2kx, 0) – (2kx + x, x) – ....
We know that the polyline passes through the point (a, b). Find minimum positive value x such that it is true or determine that there is no such x.
题解：所有线的斜率均为k=\pm1
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i< =n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x< <1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define eps (1e-10)
#define F (100000007)
typedef long long ll;
typedef double ld;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
ld a,b;
int main()
{
// freopen("A.in","r",stdin);
// freopen(".out","w",stdout);
cin>>a>>b;
if (a
B."Or" Game
已知n个数，执行k次操作：将任意一个数乘x，求最大or和
(1 ≤ n ≤ 200 000, 1 ≤ k ≤ 10, 2 ≤ x ≤ 8).
解法：由于 \(x\geqslant2\) 我们应该将位数最大的那个1挪到尽可能高位，因此，应反复乘同一个数
用线段树预处理区间or和，然后枚举执行操作的数即可
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i< =n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x< <1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (200000+10)
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
ll a[MAXN],x;
int n,k;
class SegmentTree
{
ll minv[MAXN*4];
int n;
public:
SegmentTree(){MEM(minv) }
SegmentTree(int _n):n(_n){ MEM(minv) }
void mem(int _n)
{
n=_n;
MEM(minv)
}
void build(int x,int L,int R)
{
int M=(L+R)>>1;
if (L==R) {minv[x]=a[L];return;}
else
{
if (L< =M) build(Lson,L,M);
if (Mql=ql,this->qr=qr;
if (ql>qr) return 0;
return _query_min(1,1,n);
}
ll _query_min(int x,int L,int R)
{
if (ql< =L&&R<=qr) return minv[x];
ll ans=0,M=(L+R)>>1;
if (ql< =M) ans|=_query_min(Lson,L,M);
if (M< qr) ans|=_query_min(Rson,M+1,R);
return ans;
}
}S;
int main()
{
// freopen("B.in","r",stdin);
// freopen(".out","w",stdout);
cin>>n>>k>>x;
For(i,n) scanf("%I64d",&a[i]);
sort(a+1,a+1+n);
S.mem(n);
S.build(1,1,n);
ll e=0;
For(i,n)
{
ll ans=0;
ans|=S.query_min(1,i-1);
ans|=S.query_min(i+1,n);
ll t=a[i];
For(i,k) t*=x;
ans|=t;
e=max(e,ans);
}
cout<
C .已知序列a1, a2, ..., an (|ai| ≤ 10 000,1 ≤ n ≤ 200 000). 求x,
使序列a1 - x, a2 - x, ..., an - x 的子段和的绝对值最小.
解法：二分x，如果最大子段和与最小子段和平均值\(\geqslant 0\),则说明x太大.
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i< =n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x< <1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define eps (1e-8)
#define MAXN (200000+10)
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int n;
double a[MAXN];
double ans;
bool check(double x)
{
double mins=a[1]-x,maxs=a[1]-x;
double t1=0,t2=0;
For(i,n) {
t1=max(t1+a[i]-x,a[i]-x);
maxs=max(maxs,t1);
t2=min(t2+a[i]-x,a[i]-x);
mins=min(mins,t2);
}
ans=maxs;
return (mins+maxs)/2 <0;
}
int main()
{
// freopen("c.in","r",stdin);
// freopen(".out","w",stdout);
cin>>n;
For(i,n) scanf("%lf",&a[i]);
double l=-2000000000,r=2000000000;
int k=150;
while (k--)
{
double m=(l+r)/2;
if (check(m)) r=m;
else l=m;
}
check((l+r)/2);
printf("%.7lf\n",ans);
return 0;
}