NOI之前的杂题就放这儿了
现在做了几道：
18
【BZOJ4144】有一个结论，如果我们可以从$A$直接走到$B$，其中$A$和$B$都是加油站，那么这条路径一定是一开始离得最近的加油站是$A$，过一会儿变成$B$，一直到$B$为止。为什么呢？不妨设中间出现了一个点$X$离$C$最近，那么我们大可以从$A$到$X$，然后从$X$到$C$，从$C$返回$X$，再从$X$到$B$。这样一定不会差。所以$A,B$之间是否有边就看是否满足这样的条件。首先我们可以$dijkstra$求出每个点距离最近的加油站。那么每一条边就给我们提供了最近从$A$到$B$的分界点，我们按每条边可以构建出一条新的边。然后要求最大边最小，只要$MST$然后倍增就好了。
【BZOJ4152】我们如果将点按x轴排序，那么我们发现$dist(a_1,a_3)<=dist(a_1,a_2)+dist(a_2,a_3)$。所以我们只需要相邻的边就可以。
然后在按y轴排序建一遍边，跑最短路即可。
【IPSC2015F】题目大意是有$n$对夫妇，一对夫妇熟悉当且仅当丈夫之间是朋友且妻子之间也是朋友。现在有$q$个事件，每次都是$x$和$y$的丈夫成为朋友或妻子成为朋友。朋友之间具有传递性。求每个时刻熟悉的$cp$的对数。$n,q<=1000000$
考场上一直在想并查集无果。看了题解发现好神啊。我们不用并查集而用启发式合并，每次把小的合并到大的上。
这样♂和♀的所属集合都很好维护，一对$cp$同属一个集合当且仅当♂所在集合和♀所在集合都相同。我们可以在暴力合并♂或♀的所属集合的时候顺便合并$cp$所在的集合。代码的实现由很多技巧。
map<pa,int>mp;
int n,m,now;
struct rec
{
int fa[maxn],size[maxn],head[maxn],tot;
struct edge{int go,next;}e[maxn];
inline void clear()
{
for1(i,n)fa[i]=size[i]=head[i]=0;tot=0;
}
inline void add(int x,int y)
{
e[++tot]=(edge){y,head[x]};head[x]=tot;
}
inline void merge(int xx,int yy)
{
if(xx==yy)return;
if(size[xx]>size[yy])swap(xx,yy);
size[yy]+=size[xx];
int tmp=0;
for4(i,xx){fa[y]=yy;if(e[i].next==0)tmp=i;}
e[tmp].next=head[yy];
head[yy]=head[xx];
}
}a,b,c;
inline void merge(int aa,int bb,int cc,int dd)
{
int x=mp[pa(aa,bb)],y=mp[pa(cc,dd)];
// cout<<aa<<' '<<bb<<' '<<cc<<' '<<dd<<' '<<x<<' '<<y<<endl;
if(c.fa[x]==c.fa[y])return;
(now+=(ll)c.size[c.fa[x]]*c.size[c.fa[y]]%mod)%=mod;;
if(!y)mp[pa(cc,dd)]=c.fa[x];
else c.merge(c.fa[x],c.fa[y]);
}
int main()
{
freopen("f2.in","r",stdin);
freopen("output.txt","w",stdout);
int T=read();
while(T--)
{
n=read();m=read();int ans=0;now=0;
mp.clear();
for1(i,n)
{
a.fa[i]=b.fa[i]=c.fa[i]=i;
a.size[i]=b.size[i]=c.size[i]=1;
a.add(i,i);b.add(i,i);c.add(i,i);
mp[pa(i,i)]=i;
// cout<<i<<endl;
}
for1(j,m)
{
int t=read(),xxx=read(),yyy=read();//cout<<t<<' '<<xxx<<' '<<yyy<<endl;
if(t==1)
{
int xx=a.fa[xxx],yy=a.fa[yyy];
if(xx!=yy)
{
if(a.size[xx]>a.size[yy])swap(xx,yy);
for5(a,i,xx)merge(a.fa[y],b.fa[y],yy,b.fa[y]);
a.merge(xx,yy);
}
}else
{
int xx=b.fa[xxx],yy=b.fa[yyy];
if(xx!=yy)
{
if(b.size[xx]>b.size[yy])swap(xx,yy);
for5(b,i,xx)merge(a.fa[y],b.fa[y],a.fa[y],yy);
b.merge(xx,yy);
}
}
(ans+=(ll)now*j%mod)%=mod;
//cout<<j<<' '<<now<<endl;
}
cout<<ans<<endl;
a.clear();b.clear();c.clear();
}
return 0;
}
【IPSC2015G】题目大意就是给你一颗$n$个节点的树，每个节点有一个颜色，每次可以输入$x，y，z$，把$x$子树中离$x$距离不超过$y$的点的颜色改为$z$，或者询问$x$的颜色。$n,q<=1000000$
比赛的时候想$bfs$序，写出来发现子树内的点并不一定是连续的
所以说$bfs$序能维护什么呢？
看题解发现好神啊！！！
因为每次修改的$dep$是连续的，那我们以$dep$为值建立线段树，每个线段树里面放上属于该$dep$范围的点。那这个顺序按什么呢？
很容易想到按$dfs$序，因为一个$dep$确定了之后，点按$dfs$序排列的话，$x$子树内的点就是连续的了。我们可以再放棵线段树。
修改直接打标记即可。每次新标记覆盖旧标记。查询的话遍历$O（logn）$棵线段树，查找最近一次的标记即可。
【BZOJ4145】很容易想到$dp_{i,j}$表示考虑了前$i$个商店，然后买的物品集合是$j$的最小花费。如何转移呢？如果我们枚举子集来做的话，这样复杂度是$O（n3^m）$，无法承受。考虑对于一个物品选或不选进行背包，这样复杂度就是$O（nm2^m）$。可以通过。
【BZOJ2396】真是黑科技啊。判断两个矩阵相乘是否等于另一个矩阵。我们随机一个$1×n$的矩阵然后乘到两边，判是否相等。据说错的概率$<=\frac{1}{2}$
【BZOJ4151】这题有点儿厉害啊。首先暴力判肯定不行，然而要是每次把符合条件的$ans++$，这样也不好搞，因为满足条件的分布的并不十分有规律，可以说十分零散，不能整体修改。那我们就考虑构造型的解法，不放认为现在处在$1$，那么如果满足所有条件的话，输出就好了。否则不放认为我们不满足$（x，y，z）$的限制，也就是说$dist(1,x)+dist(1,y)>z$，那我们就必须沿着$LCA(x,y)$的方向走若干步，至少也得到达$LCA(x,y)$的$\frac{z-dist(x,y)}{2}$级祖先。那我们根据$m$个条件就可以得出许多这样的条件，如果有两个要求不在同一棵子树内，显然无解。否则我们就走到最深的这个祖先，然后判一下是否合法就行了。正确性显然。
【BZOJ4149】一道水题。。。我们发现固定右端点，左端点并不单调，所以不能用单调队列。我们考虑计算贡献，对于一个数$a[i]$来说，不妨认为它作为唯一的最小最远扩展到两边是$[l,r]$，也就是说任选左端点$∈[l,i]$，右端点$∈[i,r]$，那么这段区间的最小值都唯一且是$i$。所以我们可以考虑把所有这些区间都$++$。最大值类似这样去$++$。那么如果一个区间被加了两次，显然就是符合条件的一个区间。然而上述矩形加，我们可以用差分+线段树，而对答案的查询我们就是枚举起点算最远的$=2$的点，这样也直接用线段树查询就可以了。复杂度$O（nlogn）$。一开始抱着这么好写的题写不错的态度交了$T$了几发，后来改成标记永久化还是$T$。最后要来数据发现区间修改写成单点了。不过也因此$get了clock()$的使用方法。
【BZOJ1576】被USACO的题虐了
题解君 我比较好奇 次短路一定只有一条非树边吗？不可能经过走多条吗？
【BZOJ2216】就是求$max(a[j]+\sqrt{i-j})$，显然$O（n\sqrt{n})$的算法随意，只要枚举后面那部分，前面最大用一个$st$表搞就好了。这其实是个$dp$。$dp$优化显然就是单调队列，决策单调性，四边形不等式什么的。这题我们可以考虑 如果某个时刻$i$的最优值在$j$选，那么$i$之后的点根本不会以$j$之前的点作为最优决策点。因为$f(x)=\sqrt{x}$这个函数的导数是递减的，所以更前面的值增加的还慢。所以就有决策单调性了。可以维护一个栈二分，也可以直接写分治。
【BZOJ4033】令$dp[i][j]$表示$i$的子树中选了$j$个黑点的代价，而这个代价应该是什么呢？应该是这$j$个黑点之间两两的距离以及这$j$个黑点对其他所有黑点的距离的贡献以及白点balabala，这样一定具有子问题最优性。所以才可以$dp$。然后转移的话就暴力好了。复杂度$O（n^2）$的。因为这个复杂度和枚举所有的点对的复杂度是一样的。可以意会一下。
【51nod算法马拉松3A】数据范围这么小，爆搜！T的不行，强行快超时的时候退出。
【51nod算法马拉松3B】强行最小到大加进去就完了
【51nod算法马拉松3C】会做4033这题就是傻逼了
【51nod算法马拉松3D】区间询问最容易想到的就是线段树，所以搞搞搞！记录一下左右端点选不选然后balabala
【51nod算法马拉松3F】比赛的时候非常傻逼，不知道从哪里下手。看了题解发现其实很简单，$<=\sqrt{n}$的质数至多只有$11$个，$>\sqrt{n}$的质数至多只有$157$个，而一个数里顶多有一个$>\sqrt{n}$的质数，所以就直接无脑状压$dp$，$dp_{i,j}$表示已经用了前$i$个$>\sqrt{n}$的质数，然后$<=\sqrt{n}$的质数的使用情况是$j$。然后枚举这次用的。这一步如果用子集的话会$T$。鉴于数据这么小，我们可以直接枚举合法的。这样就是$O（168*\sqrt{n}*2^{11}）$
【BZOJ3288】求行列式肯定不能定义来搞，我们高斯消元然后把对角线上的数乘起来就是答案。这题的话打个表发现对角线上就是$fai(i)$,那么直接暴力算$fai$就好了。以后碰到这种题不打表就剁手！
【BZOJ3067】区间统计问题用前缀和比较好，$f[i][j]$表示前$i$个字符中$j$字符出现的次数$/%2$。然后$[l,r]$可以是回文的充要条件是$f[r]$和$f[l-1]$至多只有一位不同，那么就和spring这题的想法一样了。$hash$即可。我被卡常数卡到死最后实在受不鸟了交了别人的代码
评论 (0)
