NOI2015填坑
Day1
T1 签到题
T2 树剖裸题
T3 神题：
考场上面就没想出来
重新往状压DP方向想了一（hen）下（jiu）发现依旧没想出来
因为每个数大于sqrt(n)的质因数最多只有1个，所以可以状压前8个质数，然后把每个数依次加进来计算方案。
设f(S,T)为第一个人的状态为S且第二个人状态为T的时候的当前方案个数，然后还设个g0/g1(S,T)分别是两个人选择当前这个质因数的时候的方案数，最后处理完这个质因数就把f处理成g0+g1-f，因为两个都不选算了两遍。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 256
#define M 505
#define fr first
#define sc second
#define ll long long
pair <int,int> li[M];
int f[N][N],g[2][N][N],n,m,ans;
const int Prime[]={2,3,5,7,11,13,17,19};
inline int Mod(ll x)
{return (x+m)%m;}
int main()
{
cin >>n>>m;
for (int i=2;i<=500;i++)
{
int k=i;
for (int j=0;j<8&&k-1;j++)
while (k%Prime[j]==0)
k/=Prime[j],li[i-1].sc|=1 << j;
li[i-1].fr=k;
}
sort(li+1,li+n);
f[0][0]=1;
for (int i=1;i<n;i++)
{
if (li[i].fr==1||li[i].fr!=li[i-1].fr)
memcpy(g[0],f,sizeof f),memcpy(g[1],f,sizeof f);
for (int k=N-1;k>=0;k--)
for (int l=N-1;l>=0;l--)
if ((l&li[i].sc)==0)
g[0][k|li[i].sc][l]=Mod(g[0][k|li[i].sc][l]+g[0][k][l]);
for (int k=N-1;k>=0;k--)
if ((k&li[i].sc)==0)
for (int l=N-1;l>=0;l--)
g[1][k][l|li[i].sc]=Mod(g[1][k][l|li[i].sc]+g[1][k][l]);
if (li[i].fr!=li[i+1].fr||li[i].fr==1)
for (int k=0;k<N;k++)
for (int l=0;l<N;l++)
f[k][l]=Mod(g[0][k][l]+g[1][k][l]-f[k][l]);
}
for (int i=0;i<N;i++)
for (int j=0;j<N;j++)
ans=Mod(ans+f[i][j]);
cout <<ans<<endl;
return 0;
}
Day2
T1：按哈弗曼树那样贪心，只不过一次选取最小的k个，并且高度也要贪心选取。如果n%k!=0就补位。
由于是考场上面A的就懒得放代码了= =
T2：后缀排序+并查集，后缀排序之后就求出了两两相邻字典序后缀之间的相似程度，就可以从n-1到0扫一遍，每次用相似程度为i的两对更新答案。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 600050
#define fr first
#define sc second
#define ll long long
pair <int,int> a[N];ll ans,Ans[N][2],s[N],ma[N],mi[N],tot,INF;
int n,m,fa[N],c[N],d[N],sx[N],sy[N],li[N];char b[N];
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
int Find(int x)
{return fa[x]==x?x:(fa[x]=Find(fa[x]));}
inline ll max(ll x,ll y)
{return x<y?y:x;}
inline ll min(ll x,ll y)
{return x<y?x:y;}
void aa(int x)
{
memset(c,0,sizeof(c));memset(d,0,sizeof(d));
memset(sy,0,sizeof(sy));int ri=x;
for (int i=0;i<x;i++) sy[i]=n-i-1;
for (int i=0;i<n;i++)
if (sx[i]>=x) sy[ri++]=sx[i]-x;
for (int i=0;i<n;i++) c[li[i]]++;
for (int i=1;i<=n;i++) c[i]+=c[i-1];
for (int i=0;i<n;i++)
sx[c[li[sy[i]]-1]++]=sy[i];
d[sx[0]]=1;
for (int i=1;i<n;i++)
d[sx[i]]=d[sx[i-1]]+1-(li[sx[i]]==li[sx[i-1]]&&
li[sx[i]+x]==li[sx[i-1]+x]);
for (int i=0;i<n;i++) li[i]=d[i];
}
int main()
{
n=Read();
scanf("%s",b);
for (int i=1;i<=n;i++) ma[i]=mi[i]=Read(),fa[i]=i,s[i]=1;
for (int i=0;i<n;i++) c[b[i]]++;
for (int i=1;i<=256;i++) c[i]+=c[i-1];
for (int i=0;i<n;i++)
sx[c[b[i]-1]+(d[b[i]]++)]=i,
li[i]=c[b[i]];
for (int i=1;i<n;i <<= 1) aa(i);
int now=0,ri=0;ans=INF=-(ll)(1e18);
for (int i=0;i<n;i++)
{
now-=now>0;
if (li[i]==1) continue;
while (i+now<n&&sx[li[i]-2]+now<n&&b[i+now]==b[sx[li[i]-2]+now]) now++;
a[++ri].fr=now;a[ri].sc=i+1;
}
sort(a+1,a+n);ri=n-1;
for (int i=n-1;i>=0;i--)
{
while (ri&&a[ri].fr==i)
{
int k=Find(a[ri].sc),l=Find(sx[li[a[ri].sc-1]-2]+1);
if (k!=l)
fa[k]=l,ans=max(ans,ma[k]*ma[l]),
ans=max(ans,mi[k]*mi[l]),
ma[l]=max(ma[l],ma[k]),mi[l]=min(mi[k],mi[l]),
tot+=s[l]*s[k],s[l]+=s[k];
ri--;
}
Ans[i][0]=tot;Ans[i][1]=ans;
}
for (int i=0;i<n;i++)
printf("%lld %lld\n",Ans[i][0],!Ans[i][0]?0:Ans[i][1]);
return 0;
}
T3这种凶残的题还是不准备现在填坑了= =
2-SAT 乱水
看了下2-SAT，然后随便水了两道题
POJ3207 这个段哥当时讲过，然而我当时十分Naive。。
这题良心到Tarjan都不用写直接写个BCJ就好了因为连边的特殊性
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1050
int n,m,ln[N][2],fa[N],ri,ss=1,st=0,ans=0;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline bool Intersect(int x,int y)
{return ln[x][0]>ln[y][0]&&ln[x][0]<ln[y][1]&&ln[x][1]>ln[y][1];}
int Find(int x)
{return fa[x]==x?x:(fa[x]=Find(fa[x]));}
int main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++)
{
ln[i][0]=Read();ln[i][1]=Read();fa[i]=i;fa[i+m]=i+m;
if (ln[i][0]>ln[i][1]) swap(ln[i][0],ln[i][1]);
}
for (int i=1;i<m;i++)
for (int j=i+1;j<=m;j++)
if (Intersect(i,j)||Intersect(j,i))
fa[Find(i)]=Find(j+m),fa[Find(i+m)]=Find(j);
for (int i=1;i<=m;i++)
if (Find(i)==Find(i+m)) {ans=-1;break;}
if (ans) puts("the evil panda is lying again");else
puts("panda is telling the truth...");
return 0;
}
POJ3678
Tarjan然后求个强连通分量，如果i和i'在同一强连通分量内就肯定是无解的。
至于怎么证并不知道= =，而且这题还没有对称性
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 2050
#define M 3000050
int fi[N],c[M][2],low[N],n,m,ss,ri,li[N],cl[N],st,ln[M][2];
int s[N];bool b[N];char d[20];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;ln[ss][0]=x;ln[ss][1]=y;}
void DFS(int x,int y)
{
int k=++ri;li[ri]=x;low[x]=y;b[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (b[c[i][0]])
low[x]=min(low[x],low[c[i][0]]);else
if (!low[c[i][0]])
DFS(c[i][0],y+1),low[x]=min(low[x],low[c[i][0]]);
if (low[x]==y)
{
st++;
for (int i=k;i<=ri;i++)
b[li[i]]=0,cl[li[i]]=st;
ri=k-1;
}
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++)
{
int q=Read()+1,w=Read()+1,e=Read();
scanf("%s",d);
if (d[0]=='A'&&!e)
Line(q,w+n),Line(w,q+n);else
if (d[0]=='A')
Line(q+n,q),Line(w+n,w);else
if (d[0]=='O'&&!e)
Line(q,q+n),Line(w,w+n);else
if (d[0]=='O')
Line(q+n,w),Line(w+n,q);else
if (e)
Line(q+n,w),Line(q,w+n),Line(w,q+n),Line(w+n,q);else
Line(q,w),Line(w,q),Line(q+n,w+n),Line(w+n,q+n);
}
for (int i=1;i<=n*2;i++)
if (!low[i]) DFS(i,1);
for (int i=1;i<=n;i++)
if (cl[i]==cl[i+n])
{puts("NO");return 0;}
puts("YES");
return 0;
}
还有输出字典序最小解的就是暴力O(nm)DFS
任意解的就是在上面Tarjan的基础上拓扑排序一下，每次选一个出度为0的未染色点，把它的对应点i和i的所有前驱全部标为不选。因为有之前那个性质所以并不用拓扑排序过程中无需判无解。
计划
感觉最近虽然也很废，但是至少不是像之前那样混日子了，现在每天都还是有所收获的
而且从机房里面搬出去之后效率也应该能提升蛮多吧。只不过感觉真心不能作死熬夜了= =不然第二天上午就会睡掉
这周还有5天，先补充姿势水平，把一些还没学的常用的东西比如2-SAT什么什么的学掉。然后USACO Gold还可以刷一些。有时间去填一些比如NOI或者一些BZOJ上面比较经典的系列的坑。按现在这种状态感觉去开刷CF还是很虚的。
然后下周尽量跟上*利的进度吧。
以我的能力还有这种拙计智商，不知道能走多远，走到哪里呢。只是真心不想搞高考啊，而且我还有很多事情想要做的，所以尽量努力吧。
UPD 9.18 好萎啊不知道为什么，感觉吧总是很容易没有动力。
UPD 9.20 我们学校吧根本就没有一个搞OI的氛围，天天有人在摆。他们是没有考虑过省选之后的事情么，或者是真的觉得自己不用努力就能够混到一个很好的成绩么。而且风气也很奇怪，成天D人或者是BB。感觉这本来就不是什么好东西为什么不能控制一下。D人也本来是为了提醒别人但是我不懂成天D人有什么意义。
VFK曾经说过一句话：OI并不是酱油学科。现在想来很有道理。本来就是没有人能够随随便便成功的
只能够希望新一届高一能够不要像我们这样吧
BZOJ 2716/2648
膜了一发K-D Tree这种高端东西
感觉比想象中好写。
但是不用指针就会T，用了指针就跑的飞起只有10+s感觉实在不科学= =
这个版本并没有套上暴力重建，也懒得套暴力重建了= =
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1000050
#define INF 0x7f7f7f7f
struct Point
{int x,y,x1,y1,x2,y2;Point *c[2];};
int n,m;
bool cmp(const Point &x,const Point &y)
{return x.x<y.x;}
bool cpm(const Point &x,const Point &y)
{return x.y<y.y;}
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
struct KD_Tree
{
int st,ans;Point now,*gf,t[N];
inline int Minimum(Point *x,Point y)
{
int k=0;
if (y.x<x->x1) k+=x->x1-y.x;else
if (y.x>x->x2) k+=y.x-x->x2;
if (y.y<x->y1) k+=x->y1-y.y;else
if (y.y>x->y2) k+=y.y-x->y2;
return k;
}
inline int Dis(Point *x,Point y)
{return abs(x->x-y.x)+abs(x->y-y.y);}
inline void Get(int x)
{
t[x].x=t[x].x1=t[x].x2=Read();
t[x].y=t[x].y1=t[x].y2=Read();
}
inline void Update(Point *x,Point *y)
{
x->x1=min(x->x1,y->x1);
x->x2=max(x->x2,y->x2);
x->y1=min(x->y1,y->y1);
x->y2=max(x->y2,y->y2);
}
Point *Build(int x,int y,int z)
{
int k=x + y >> 1;
if (x>=y) return x==y?&t[x]:NULL;
nth_element(t+x,t+k,t+y+1,z?cmp:cpm);
t[k].c[0]=Build(x,k-1,!z);
t[k].c[1]=Build(k+1,y,!z);
if (t[k].c[0]!=NULL) Update(&t[k],t[k].c[0]);
if (t[k].c[1]!=NULL) Update(&t[k],t[k].c[1]);
return &t[k];
}
void Insert(Point *x,int y,int z)
{
int k=(z&&x->x<=t[y].x)||(!z&&x->y<=t[y].y);
if (x->c[k]==NULL)
x->c[k]=&t[y];else
Insert(x->c[k],y,!z);
Update(x,x->c[k]);
}
void query(Point *x,int y)
{
int k=(y&&x->x<=now.x)||(!y&&x->y<=now.y);
ans=min(ans,Dis(x,now));
if (x->c[k]!=NULL&&Minimum(x->c[k],now)<ans)
query(x->c[k],!y);
if (x->c[!k]!=NULL&&Minimum(x->c[!k],now)<ans)
query(x->c[!k],!y);
}
int Query(int y,int x)
{
ans=INF;now.x=x;now.y=y;
query(gf,0);return ans;
}
} A;
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++)
A.Get(i);
A.gf=A.Build(1,n,0);A.st=n;
while (m--)
if (Read()-1)
printf("%d\n",A.Query(Read(),Read()));else
A.Get(++A.st),A.Insert(A.gf,A.st,0);
return 0;
}
USACO Gold题填（bei）坑（nue）计划
做起来果然比Silver带感多了，更能体现我智商癌的本质。
感觉自己还真是萎废，这种题还做得一卡一卡的
BZOJ1230 线段树
BZOJ1231 一开始没想出来，后来发现是状压DP
BZOJ1233 好神的贪心+DP，首先一个草堆要最高必须要底层最瘦。证明好像其它地方有，然后就可以DP了，记录第i个到第n个最优情况下有多瘦、有多高。一开始没注意底层宽度不一定具有单调性，然后就wa了，后来看了一下式子发现要用单调队列优化。
BZOJ1571 直接DP
BZOJ1572 首先把工作按照截止日期排个序，然后从后往前枚举时间点用个set什么的每个时间点选取最大价值的。
BZOJ1574 贪心，把跟那些点相邻的点都打上标记，最后从起点DFS能到达多少没打标记的点，最后用n-cnt就是答案了
BZOJ1575 预处理出每个区间的误差值和，最后DP一下
BZOJ1577 按照右端点排序，然后依次放就好了。
BZOJ1578 一个东西第i天买进第j天卖出相当于每天都买入卖出，所以直接算出每天最多有多少钱，也就是每天背包一下。
BZOJ1581 DP，设ai,j代表前i+j位放了i个0和j个1，有多少种方案。算第k大也是扫一遍什么的就好了
BZOJ1583 直接算，只不过题意是真的艹蛋
BZOJ1584 发现k最大只能是200，所以直接DP好了
BZOJ1585 好久没做网络流的题目了裸的最小割没看出来TAT
BZOJ1589 BFS
BZOJ1590 trie
BZOJ1592 离散化+DP
BZOJ1593 我写的splay,调起来极其带感
BZOJ1596 贪心
BZOJ1597 斜率优化
BZOJ1692 后缀数组
BZOJ1694 DP，算的是这段距离对答案的总贡献所以并没有后效性
BZOJ1697 想到了正解一开始并不敢写= = 对于每个置换环要不就用其中最小的节点在上面移，要不就把全局最小的移进来。
BZOJ1699 重题了
BZOJ1702 前缀和一下然后差分一下然后排个序
BZOJ1703 猜了个结论就是不能确认的关系的对数
BZOJ1704 乱搞
BZOJ1705 DP，因为增加的高度不会太大，但是不能只开到10，我反正开到20才过
BZOJ1706 矩阵快速幂
BZOJ1707 乱搞
BZOJ1708 背包
BZOJ1709 首先找到一个有对手的格子，答案就只能放在它的八个方向的格子上
BZOJ1710 DP
BZOJ1711 TAT果然网络流荒废太久了都不记得了，建图S->F->N->D->T
BZOJ1712 乱搞+快速幂
BZOJ1690 分数规划+二分答案+找负环，感觉好神啊。一开始还没看到路线是个环，感觉无论如何都不能理解= =
BZOJ1604 好神的规律题啊，可以看这里。
BZOJ1598 K短路，然而因为是拓扑图所以可以用A*算法。记得我以前是看过鼎爷的论文的然而已经忘得差不多了= =
