BZOJ – GNAQ 的心语屋

2019年2月12日2019年3月17日

BZOJ 1478 | 1488 | 1815 无标号无向完全有色图计数

给定一个无向完全图，边有颜色，求所有不同构的图的数量。

这里我们考虑所有边的置换，边的置换太大了，发现边的置换和点的置换是有关的，而且点的置换和图的同构是有关的，所以我们枚举所有点的置换。

但是这样是 $n!$ 的复杂度。我们发现对于两个置换，如果对于每一个大小的轮换，他们都具有相同的轮换个数，那么对于答案的贡献就是等价的。

那么我们就可以枚举整数拆分了。复杂度变成点数的拆分数了。

这样我们对于每一种置换都求一下对答案的贡献，然后乘一下轮换个数就好了。

轮换个数怎么算呢……首先是根据拆分组合数搞一下

int rest = n;
for (int i = 1; i &lt;= m; i++)
{
	plan = plan * C(rest, div_num[i]);
	rest -= div_num[i];
}

int rest = n;

for (int i = 1; i <= m; i++)

{

plan = plan * C(rest, div_num[i]);

rest -= div_num[i];

}

其中 div_num 是拆分数组。

然后考虑假设大小为 $x$ 的轮换有 $y$ 个，那么我们还要除以 $y!$ 。

然后注意到每个循环排列方式只和第一个点有关，或者说，因为这是个圆排列所以要去重（除掉 $div\_num[i]$ ），所以我们还要挨个乘 $(div\_num[i]-1)!$ 。

然后后面就是考虑怎么算边的轮换大小了，见这里：

https://fancydreams.ink/2018/12/01/%E4%BB%8E%E5%B0%8F%E5%AD%A6%E5%BC%80%E5%A7%8B%E7%9A%84%E6%95%B0%E6%95%B0/

代码：

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstdlib&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
#include&lt;vector&gt;
#include&lt;queue&gt;
#include&lt;map&gt;
#include&lt;set&gt;
typedef long long ll;
using namespace std;

int fac[100010],ifac[100010];
int n,m,modd,ans,gcd_arr[110][110];

const ll mod = 999999937;

template&lt;typename inp_typ&gt;
inline void readx(inp_typ&amp; x)
{
	x=0; char ch=0;
	while (ch&lt;'0' || ch&gt;'9') ch=getchar();
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
}

inline int fastpow(int an,int p)
{
	int ret=1;
	for (;p;p&gt;&gt;=1,an=1LL*an*an%mod) if (p&amp;1) ret=1LL*ret*an%mod;
	return ret;
}

inline void Init_fac(int lim) // lim &gt;= mod !!
{
	fac[0]=1;
	for (int i=1;i&lt;=lim;i++) fac[i]=1LL*fac[i-1]*i%mod;
	for (int i=0;i&lt;=lim;i++) ifac[i]=fastpow(fac[i],mod-2);
}

inline int C(int _n,int _m)
{
	return 1LL*fac[_n]*ifac[_m]%mod*ifac[_n-_m]%mod;
}

int gcd(int a1,int a2)
{
	if (gcd_arr[a1][a2]) return gcd_arr[a1][a2];
	if (gcd_arr[a2][a1]) return gcd_arr[a2][a1];
	if (!a2) return a1;
	return gcd_arr[a1][a2]=gcd_arr[a2][a1]=gcd(a2,a1%a2);
}

int dfs_seq[1010];
int bac[1010];
void DFS(int rest,int now_num,int dep)
{
	if (!rest)
	{
		// calc plans
		// xjb 算轮换出现次数
		register int plan=1,cir_siz=0,tmp_n=n;
		for (int i=1;i&lt;=dep;i++) // n 个点放进 m 个循环
		{
			plan=1LL*plan*C(tmp_n,dfs_seq[i])%mod;
			tmp_n-=dfs_seq[i];
		}
		
		for (int i=1;i&lt;=dep;i++) plan=1LL*plan*fac[dfs_seq[i]-1]%mod; // 注意每个循环排列方式只和第一个点有关
		
		// 多组长度相等的轮换也要除一下个数的阶乘
		for (int i=1;i&lt;=n;i++) if (bac[i])
			plan=1LL*plan*ifac[bac[i]]%mod;
		
		// 算循环节数
		for (int i=1;i&lt;=dep;i++)
		{
			cir_siz+=dfs_seq[i]/2;
			for (int j=1;j&lt;i;j++) cir_siz+=gcd(dfs_seq[j],dfs_seq[i]);
		}
		
		// Polya
		ans=(ans+1LL*fastpow(m,cir_siz)*plan%mod)%mod;
		return;
	}
	for (int i=now_num;i&lt;=rest;i++)
	{
		dfs_seq[dep+1]=i; bac[i]++;
		DFS(rest-i,i,dep+1);
		dfs_seq[dep+1]=0; bac[i]--;
	}
}

int main()
{
	readx(n); readx(m); readx(modd);
	Init_fac(n*n);
	
	DFS(n,1,0);
	
	ans=1LL*ans*ifac[n]%mod;
	printf("%d\n",ans);
}

100

101

102

103

104

105

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<iterator>

#include<vector>

#include<queue>

#include<map>

#include<set>

typedef long long ll;

using namespace std;

int fac[100010],ifac[100010];

int n,m,modd,ans,gcd_arr[110][110];

const ll mod = 999999937;

template<typename inp_typ>

inline void readx(inp_typ& x)

{

x=0; char ch=0;

while (ch<'0' || ch>'9') ch=getchar();

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

}

inline int fastpow(int an,int p)

{

int ret=1;

for (;p;p>>=1,an=1LL*an*an%mod) if (p&1) ret=1LL*ret*an%mod;

return ret;

}

inline void Init_fac(int lim) // lim >= mod !!

{

fac[0]=1;

for (int i=1;i<=lim;i++) fac[i]=1LL*fac[i-1]*i%mod;

for (int i=0;i<=lim;i++) ifac[i]=fastpow(fac[i],mod-2);

}

inline int C(int _n,int _m)

{

return 1LL*fac[_n]*ifac[_m]%mod*ifac[_n-_m]%mod;

}

int gcd(int a1,int a2)

{

if (gcd_arr[a1][a2]) return gcd_arr[a1][a2];

if (gcd_arr[a2][a1]) return gcd_arr[a2][a1];

if (!a2) return a1;

return gcd_arr[a1][a2]=gcd_arr[a2][a1]=gcd(a2,a1%a2);

}

int dfs_seq[1010];

int bac[1010];

void DFS(int rest,int now_num,int dep)

{

if (!rest)

{

// calc plans

// xjb 算轮换出现次数

for (int i=1;i<=dep;i++) // n 个点放进 m 个循环

{

plan=1LL*plan*C(tmp_n,dfs_seq[i])%mod;

tmp_n-=dfs_seq[i];

}

for (int i=1;i<=dep;i++) plan=1LL*plan*fac[dfs_seq[i]-1]%mod; // 注意每个循环排列方式只和第一个点有关

// 多组长度相等的轮换也要除一下个数的阶乘

for (int i=1;i<=n;i++) if (bac[i])

plan=1LL*plan*ifac[bac[i]]%mod;

// 算循环节数

for (int i=1;i<=dep;i++)

{

cir_siz+=dfs_seq[i]/2;

for (int j=1;j<i;j++) cir_siz+=gcd(dfs_seq[j],dfs_seq[i]);

}

// Polya

ans=(ans+1LL*fastpow(m,cir_siz)*plan%mod)%mod;

return;

}

for (int i=now_num;i<=rest;i++)

{

dfs_seq[dep+1]=i; bac[i]++;

DFS(rest-i,i,dep+1);

dfs_seq[dep+1]=0; bac[i]--;

}

int main()

{

readx(n); readx(m); readx(modd);

Init_fac(n*n);

DFS(n,1,0);

ans=1LL*ans*ifac[n]%mod;

printf("%d\n",ans);

}

2019年1月14日

BZOJ 3632 | 蒙特卡罗随机化

大概就是让你求一般图的最大团。

直接随机化。然后我们把点序当 PEO 打乱，假装第一个点在最大团里。

然后就判一下其余点的连通就好了。

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;cstdlib&gt;
#include&lt;iterator&gt;
#include&lt;queue&gt;
#include&lt;vector&gt;
#include&lt;map&gt;
#include&lt;set&gt;
#define ll long long
using namespace std;

int n,ans,G[55][55];
int at=1,ptr[110];

int per[110];
bool vis[110];

template&lt;typename int_t&gt;
void readx(int_t&amp; x)
{
	x=0; int_t k=1; char ch=0;
	while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

void Randomize()
{
	for (int i=1;i&lt;=n;i++) swap(per[i],per[rand()%i+1]);
}
	
void Process()
{
	memset(vis,0,sizeof vis);
	int tmp=0;
	for (int i=1;i&lt;=n;i++) if (!vis[i])
	{
		tmp++;
		for (int j=i+1;j&lt;=n;j++) if (!G[per[i]][per[j]]) vis[j]=1;
	}
	ans=max(ans,tmp);
}

int main()
{
	srand(20010929);
	readx(n); int fx,tx;
	while (scanf("%d%d",&amp;fx,&amp;tx)!=EOF)
		G[tx][fx]=G[fx][tx]=1;
	for (int i=1;i&lt;=n;i++) per[i]=i;
	
	for (int w=1;w&lt;=10000;w++)
	{
		Randomize();
		Process();
	}
	printf("%d\n",ans);
}

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<cstdlib>

#include<iterator>

#include<queue>

#include<vector>

#include<map>

#include<set>

#define ll long long

using namespace std;

int n,ans,G[55][55];

int at=1,ptr[110];

int per[110];

bool vis[110];

template<typename int_t>

void readx(int_t& x)

{

x=0; int_t k=1; char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

void Randomize()

{

for (int i=1;i<=n;i++) swap(per[i],per[rand()%i+1]);

}

void Process()

{

memset(vis,0,sizeof vis);

int tmp=0;

for (int i=1;i<=n;i++) if (!vis[i])

{

tmp++;

for (int j=i+1;j<=n;j++) if (!G[per[i]][per[j]]) vis[j]=1;

}

ans=max(ans,tmp);

}

int main()

{

srand(20010929);

readx(n); int fx,tx;

while (scanf("%d%d",&fx,&tx)!=EOF)

G[tx][fx]=G[fx][tx]=1;

for (int i=1;i<=n;i++) per[i]=i;

for (int w=1;w<=10000;w++)

{

Randomize();

Process();

}

printf("%d\n",ans);

}

2018年12月28日2018年12月28日

BZOJ2532 | CERC2010 Casting Spells

首先跑马拉车。

然后对于每个位置 $i$ 我们求出他的回文对称半径 $r_i$ 。比如说图上假设 $i$ 是回文子串的中心（如果是偶数长度那就是中心的右侧），然后红色位置是子串的右末端，那么 $r_i$ 就是：

然后有了 $r_i$ 之后我们考虑合法的串长什么样子：

于是我们的任务就是找到满足以下条件的 $j$ ：

$j+r_j \geqslant i$
$j \geqslant i-\frac{r_i}{2}$

然后就可以了。那么这里有一个 $O(n \log n)$ 的搞法：从左到右枚举 $i$ ，并同时维护两个集合：一个是当前所有满足条件 [1] 的 $j$ 的位置集合，这个集合以 $r_j+j$ 排序，并记录每个 $r_j+j$ 对应的 $j$ 。

另一个集合维护所有当前的合法位置 $j$ ，并按照 $j$ 排序。

每次扫到一个 $i$ 只需先清空位置集合所有 $r_j+j < i$ 的 $r_j+j$ 和合法集合对应的 $j$ 。

然后求合法集合里 $i - \frac{r_i}{2}$ 的后继即可。

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;cstdlib&gt;
#include&lt;iterator&gt;
#include&lt;set&gt;
#define ll long long
using namespace std;

int mnc[600010],ans,n,ri[600010],L;
char chs[600010];
set&lt;int&gt; posset;
set&lt; pair&lt;int,int&gt; &gt; setx;

template&lt;typename int_t&gt;
void readx(int_t&amp; x)
{
	x=0; int_t k=1; char ch=0;
	while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

bool isword(char vc)
{
	if (vc&gt;='a' &amp;&amp; vc&lt;='z') return true;
	if (vc&gt;='A' &amp;&amp; vc&lt;='Z') return true;
	return false;
}

void All_Clear()
{
	memset(mnc,0,sizeof mnc);
	ans=0; L=0; 
	posset.clear();
	setx.clear();
}

void Manacher(char chs[],int mnc[],int len)
{
	int mid=1,maxr=1;
	for (int i=1;i&lt;=len;i++)
	{
		if (i&lt;maxr) mnc[i]=min(maxr-i,mnc[mid*2-i]);
		else mnc[i]=1;
		while (chs[i-mnc[i]]==chs[i+mnc[i]]) mnc[i]++;
		if (maxr&lt;i+mnc[i])
		{
			maxr=i+mnc[i];
			mid=i;
		}
	}
}

int ReadChs()
{
	chs[0]='~'; chs[1]='[latex]'; char ch=0; int len=2;
	while (!isword(ch)) ch=getchar();
	while (isword(ch))
	{
		chs[len]=ch; chs[len+1]='[/latex]';
		len+=2; ch=getchar(); L++;
	}
	return len-1;
}

int main()
{
	readx(n);
	while (n--)
	{
		All_Clear();
		int len=ReadChs();
		
		Manacher(chs,mnc,len);
		for (int i=2;i&lt;=len;i+=2) ri[i/2]=mnc[i-1]/2;

		for (int i=2;i&lt;=L;i++)
		{
			posset.insert(i-1); setx.insert(make_pair(i-1+ri[i-1],i-1));
			while ((!setx.empty()) &amp;&amp; ( (*setx.begin()).first&lt;i )) 
			{
				posset.erase((*setx.begin()).second);
				setx.erase(setx.begin());
			}
			
			set&lt;int&gt;::iterator itr=posset.lower_bound(i-ri[i]/2);
			if (itr!=posset.end()) ans=max(ans,4*(i-(*itr)));
		}
		printf("%d\n",ans);
	}		
}

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<cstdlib>

#include<iterator>

#include<set>

#define ll long long

using namespace std;

int mnc[600010],ans,n,ri[600010],L;

char chs[600010];

set<int> posset;

set< pair<int,int> > setx;

template<typename int_t>

void readx(int_t& x)

{

x=0; int_t k=1; char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

bool isword(char vc)

{

if (vc>='a' && vc<='z') return true;

if (vc>='A' && vc<='Z') return true;

return false;

}

void All_Clear()

{

memset(mnc,0,sizeof mnc);

ans=0; L=0;

posset.clear();

setx.clear();

}

void Manacher(char chs[],int mnc[],int len)

{

int mid=1,maxr=1;

for (int i=1;i<=len;i++)

{

if (i<maxr) mnc[i]=min(maxr-i,mnc[mid*2-i]);

else mnc[i]=1;

while (chs[i-mnc[i]]==chs[i+mnc[i]]) mnc[i]++;

if (maxr<i+mnc[i])

{

maxr=i+mnc[i];

mid=i;

}

int ReadChs()

{

chs[0]='~'; chs[1]='[latex]'; char ch=0; int len=2;

while (!isword(ch)) ch=getchar();

while (isword(ch))

{

chs[len]=ch; chs[len+1]='[/latex]';

len+=2; ch=getchar(); L++;

}

return len-1;

}

int main()

{

readx(n);

while (n--)

{

All_Clear();

int len=ReadChs();

Manacher(chs,mnc,len);

for (int i=2;i<=len;i+=2) ri[i/2]=mnc[i-1]/2;

for (int i=2;i<=L;i++)

{

posset.insert(i-1); setx.insert(make_pair(i-1+ri[i-1],i-1));

while ((!setx.empty()) && ( (*setx.begin()).first<i ))

{

posset.erase((*setx.begin()).second);

setx.erase(setx.begin());

}

set<int>::iterator itr=posset.lower_bound(i-ri[i]/2);

if (itr!=posset.end()) ans=max(ans,4*(i-(*itr)));

}

printf("%d\n",ans);

}

2018年12月19日2018年12月19日

BZOJ3895 取石子

这题思路不错。

首先考虑对于一个 $>1$ 的堆，如果合并他对先手有利，那么这堆石子在取完之前一定会被先手合并。同理如果对后手有利也是。

既然合并这个动作要不就是对先手有利要么就是对后手有利，那肯定这堆石子最后会被合并。

并且在取完之前，合并这个动作无论在何时发生，都等同于在对这堆石子操作时的前两步内发生。

那么我们就可以把充裕堆 ( 大小 $>1$ 的堆 ) 先提前合并了，然后在 DAG 游戏图上记搜 $\mathrm{SG}$ 值。

操作分为几种：

拿走一个孤单堆
拿走充裕堆的一个石子
把一个孤单堆合并到充裕堆内
把两个孤单堆合并，成为充裕堆的一部分

然后就写个代码就好了。复杂度大概是 $O(T \cdot \sum{a_i})$ 的。

#include&lt;cstdio&gt;
#include&lt;cstring&gt;
#include&lt;cstdlib&gt;
#include&lt;algorithm&gt;
#include&lt;cmath&gt;
#define ll long long
using namespace std;
 
int T,n,seq[10010];
int sg[55][50010];
 
template&lt;typename int_t&gt;
void readx(int_t&amp; x)
{
    x=0; int_t k=1; char ch=0;
    while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}
 
int SG(int x,int y) // x -&gt; LonelyHeap || y -&gt; WealthyHeap
{
    if (sg[x][y]!=-1) return sg[x][y];
    if (y==1) return SG(x+1,0);
     
    sg[x][y]=0;
    if (x &amp;&amp; !SG(x-1,y)) sg[x][y]=1;
    else if (y &amp;&amp; !SG(x,y-1)) sg[x][y]=1;
    else if (x &amp;&amp; y &amp;&amp; !SG(x-1,y+1)) sg[x][y]=1;
    else if (x&gt;1 &amp;&amp; ( (!y &amp;&amp; !SG(x-2,2)) || (y &amp;&amp; !SG(x-2,y+3)) )) sg[x][y]=1;
    return sg[x][y];
}
 
int main()
{
    memset(sg,-1,sizeof sg);
    readx(T);
    while (T--)
    {
        readx(n); for (int i=1;i&lt;=n;i++) readx(seq[i]);
        int one=0,mul=0;
        for (int i=1;i&lt;=n;i++) 
        {
            if (seq[i]==1) one++;
            else mul+=seq[i]+1;
        }
        if (mul) mul--;
        if (SG(one,mul)) printf("YES\n");
        else printf("NO\n");
    }
}

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#define ll long long

using namespace std;

int T,n,seq[10010];

int sg[55][50010];

template<typename int_t>

void readx(int_t& x)

{

x=0; int_t k=1; char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

int SG(int x,int y) // x -> LonelyHeap || y -> WealthyHeap

{

if (sg[x][y]!=-1) return sg[x][y];

if (y==1) return SG(x+1,0);

sg[x][y]=0;

if (x && !SG(x-1,y)) sg[x][y]=1;

else if (y && !SG(x,y-1)) sg[x][y]=1;

else if (x && y && !SG(x-1,y+1)) sg[x][y]=1;

else if (x>1 && ( (!y && !SG(x-2,2)) || (y && !SG(x-2,y+3)) )) sg[x][y]=1;

return sg[x][y];

}

int main()

{

memset(sg,-1,sizeof sg);

readx(T);

while (T--)

{

readx(n); for (int i=1;i<=n;i++) readx(seq[i]);

int one=0,mul=0;

for (int i=1;i<=n;i++)

{

if (seq[i]==1) one++;

else mul+=seq[i]+1;

}

if (mul) mul--;

if (SG(one,mul)) printf("YES\n");

else printf("NO\n");

}

2018年9月3日

[Zzz]趁着不太清醒赶紧把题解补完 | JLOI2014

[JLOI2014]天天酷跑

某优雅的DP题。

dp[i][j][k]表示在位置 $(i,j)$ 并且用了 $k$ 次连跳的答案。

转移分三种：一是如果 $j=0$ 也就是在地面那可以跑一格

或者 $k<q$ 可以跳一下

或者如果可以的话，下落。

可以枚举跳跃高度和次数然后记搜。

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;cstdlib&gt;
#define ll long long
using namespace std;

int n,m,w,q,c1,c2,mapx[100003][21]={0};
int dp[100003][21][6]={0};
bool vis[100003][21][6]={0};

inline void readx(int&amp; x)
{
    x=0; int k=1; register char ch=0;
    while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}


inline int _DP(int nx,int ny,int use)
{
    if (ny&gt;n) return 0;
    else if (mapx[ny][nx]==-1) return -1*1e9;
    else if (vis[ny][nx][use]) return dp[ny][nx][use];
    if (nx==1) use=0;
    
    int rec=-1e9;
    if (use&lt;q)
    {
        char flag=1; int tmp=0;
        for (int i=1;i&lt;w;i++)
        {
            if (mapx[ny+i][nx+i]==-1) { flag=0; break; }
            tmp+=mapx[ny+i][nx+i];
        }
        if (flag) rec=max(rec,_DP(nx+w,ny+w,use+1)+tmp);
    }
    if (nx==1) rec=max(rec,_DP(nx,ny+1,0));
    if (nx&gt;1) rec=max(rec,_DP(nx-1,ny+1,use));
    vis[ny][nx][use]=1; dp[ny][nx][use]=rec+mapx[ny][nx];
    return dp[ny][nx][use];	
}


int main()
{
    readx(n); readx(m); readx(c1); readx(c2);
    for (int i=1;i&lt;=m;i++)
        for (int j=1;j&lt;=n;j++) readx(mapx[j][i]);
    
    int _ans=-1e9,ans1,ans2;
    for (q=1;q&lt;=5;q++)
        for (w=1;w*q&lt;m;w++)
        {
            memset(dp,0,sizeof dp);
            memset(vis,0,sizeof vis);
            int qwq=_DP(1,0,0)-c1*(w-1)-c2*(q-1);
            if (qwq&gt;_ans) { _ans=qwq; ans1=q; ans2=w; }
        }
    
    if (_ans&lt;0) printf("mission failed\n");
    else printf("%d %d %d\n",_ans,ans1,ans2);
    return 0;
}

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<cstdlib>

#define ll long long

using namespace std;

int n,m,w,q,c1,c2,mapx[100003][21]={0};

int dp[100003][21][6]={0};

bool vis[100003][21][6]={0};

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline int _DP(int nx,int ny,int use)

{

if (ny>n) return 0;

else if (mapx[ny][nx]==-1) return -1*1e9;

else if (vis[ny][nx][use]) return dp[ny][nx][use];

if (nx==1) use=0;

int rec=-1e9;

if (use<q)

{

char flag=1; int tmp=0;

for (int i=1;i<w;i++)

{

if (mapx[ny+i][nx+i]==-1) { flag=0; break; }

tmp+=mapx[ny+i][nx+i];

}

if (flag) rec=max(rec,_DP(nx+w,ny+w,use+1)+tmp);

}

if (nx==1) rec=max(rec,_DP(nx,ny+1,0));

if (nx>1) rec=max(rec,_DP(nx-1,ny+1,use));

vis[ny][nx][use]=1; dp[ny][nx][use]=rec+mapx[ny][nx];

return dp[ny][nx][use];

}

int main()

{

readx(n); readx(m); readx(c1); readx(c2);

for (int i=1;i<=m;i++)

for (int j=1;j<=n;j++) readx(mapx[j][i]);

int _ans=-1e9,ans1,ans2;

for (q=1;q<=5;q++)

for (w=1;w*q<m;w++)

{

memset(dp,0,sizeof dp);

memset(vis,0,sizeof vis);

int qwq=_DP(1,0,0)-c1*(w-1)-c2*(q-1);

if (qwq>_ans) { _ans=qwq; ans1=q; ans2=w; }

}

if (_ans<0) printf("mission failed\n");

else printf("%d %d %d\n",_ans,ans1,ans2);

return 0;

}

[JLOI2014]松鼠的新家

年代久远了。如果我没记错应该是一个树上差分问题。

好像是什么树上差分的板子……随便写写。

这是我元旦那天做的第一题，或者也可以说18年第一道题。

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;algorithm&gt;
#include&lt;cstdlib&gt;
#include&lt;cmath&gt;
#include&lt;iterator&gt;
using namespace std;

struct ed
{
    int pre,to;
}edge[600010]={0};
int nodenum,fx,tx,at=1,pointer[300010]={0};
bool vis[300010]={0};

struct tr
{
    int depth,father;
}tree[300010]={0};
int l[300010][22]={0},u,v,uvlca;

int spr[300010]={0},opt[300010]={0},ans=0;

inline void readx(int&amp; x)
{
    x=0; int k=1; register char ch=0;
    while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}

inline void Insert()
{
    edge[at].pre=pointer[fx];
    edge[at].to=tx;
    pointer[fx]=at;
    at++;
    edge[at].pre=pointer[tx];
    edge[at].to=fx;
    pointer[tx]=at;
    at++;
}

inline void BuildTree(int nownode)
{
    l[nownode][0]=tree[nownode].father;
    for (int i=1;i&lt;=21;i++) l[nownode][i]=l[l[nownode][i-1]][i-1];
    
    vis[nownode]=1;
    int prex=pointer[nownode];
    while (prex)
    {
        if (!vis[edge[prex].to])
        {
            tree[edge[prex].to].depth=tree[nownode].depth+1;
            tree[edge[prex].to].father=nownode;
            BuildTree(edge[prex].to);
        }
        prex=edge[prex].pre;
    }
}

inline int LCA(int u,int v)
{
    for (int i=21;i&gt;=0;i--) if (tree[l[u][i]].depth&gt;=tree[v].depth) u=l[u][i];
    if (u==v) return u;
    for (int i=21;i&gt;=0;i--) if (l[u][i]!=l[v][i])
    {
        v=l[v][i]; u=l[u][i];
    }
    return tree[u].father;
}

inline void process(int nownode)
{
    vis[nownode]=1;
    int prex=pointer[nownode];
    while (prex)
    {
        if (!vis[edge[prex].to]) 
        {
            process(edge[prex].to);
            spr[nownode]+=spr[edge[prex].to];
        }
        prex=edge[prex].pre;
    }
}

int main()
{
    readx(nodenum);
    for (int i=1;i&lt;=nodenum;i++) readx(opt[i]);
    for (int i=1;i&lt;nodenum;i++)
    {
        readx(fx); readx(tx);
        Insert();
    }
    
    tree[1].depth=1;
    BuildTree(1);
    
    for (int i=1;i&lt;nodenum;i++)
    {
        u=opt[i]; v=opt[i+1];
        
        if (tree[u].depth&lt;tree[v].depth) 
        {
            swap(u,v);
            uvlca=LCA(u,v);
            swap(u,v);
        }
        else uvlca=LCA(u,v);
        
        spr[u]+=1;	spr[tree[v].father]+=1;
        spr[uvlca]-=1; spr[tree[uvlca].father]-=1;
    }

    memset(vis,0,sizeof(vis));
    process(1);
    
    for (int i=1;i&lt;=nodenum;i++) printf("%d\n",spr[i]);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#include<iterator>

using namespace std;

struct ed

{

int pre,to;

}edge[600010]={0};

int nodenum,fx,tx,at=1,pointer[300010]={0};

bool vis[300010]={0};

struct tr

{

int depth,father;

}tree[300010]={0};

int l[300010][22]={0},u,v,uvlca;

int spr[300010]={0},opt[300010]={0},ans=0;

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline void Insert()

{

edge[at].pre=pointer[fx];

edge[at].to=tx;

pointer[fx]=at;

at++;

edge[at].pre=pointer[tx];

edge[at].to=fx;

pointer[tx]=at;

at++;

}

inline void BuildTree(int nownode)

{

l[nownode][0]=tree[nownode].father;

for (int i=1;i<=21;i++) l[nownode][i]=l[l[nownode][i-1]][i-1];

vis[nownode]=1;

int prex=pointer[nownode];

while (prex)

{

if (!vis[edge[prex].to])

{

tree[edge[prex].to].depth=tree[nownode].depth+1;

tree[edge[prex].to].father=nownode;

BuildTree(edge[prex].to);

}

prex=edge[prex].pre;

}

inline int LCA(int u,int v)

{

for (int i=21;i>=0;i--) if (tree[l[u][i]].depth>=tree[v].depth) u=l[u][i];

if (u==v) return u;

for (int i=21;i>=0;i--) if (l[u][i]!=l[v][i])

{

v=l[v][i]; u=l[u][i];

}

return tree[u].father;

}

inline void process(int nownode)

{

vis[nownode]=1;

int prex=pointer[nownode];

while (prex)

{

if (!vis[edge[prex].to])

{

process(edge[prex].to);

spr[nownode]+=spr[edge[prex].to];

}

prex=edge[prex].pre;

}

int main()

{

readx(nodenum);

for (int i=1;i<=nodenum;i++) readx(opt[i]);

for (int i=1;i<nodenum;i++)

{

readx(fx); readx(tx);

Insert();

}

tree[1].depth=1;

BuildTree(1);

for (int i=1;i<nodenum;i++)

{

u=opt[i]; v=opt[i+1];

if (tree[u].depth<tree[v].depth)

{

swap(u,v);

uvlca=LCA(u,v);

swap(u,v);

}

else uvlca=LCA(u,v);

spr[u]+=1; spr[tree[v].father]+=1;

spr[uvlca]-=1; spr[tree[uvlca].father]-=1;

}

memset(vis,0,sizeof(vis));

process(1);

for (int i=1;i<=nodenum;i++) printf("%d\n",spr[i]);

return 0;

}

[JLOI2014]路径规划

这题劲啊！这题可劲了

考虑对 $k$ 也就是过红绿灯的次数分层。

然后还是不好搞，没有办法之后我们可以分第二层。

对 $k$ 分层之后，对于每一层，枚举所有加油站，计算出这个加油站 $i$ 分别到所有层的所有加油站的最短路。

然后这样建新图，直接在加油站-加油站之间连边。然后跑对于 $k$ 的分层图最短路。

SPFA 不会被卡。

期望等待长度是 $\frac{R^2}{2 \cdot (R+G)}$ 。

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;algorithm&gt;
#include&lt;cstdlib&gt;
#include&lt;iterator&gt;
#include&lt;cmath&gt;
#include&lt;map&gt;
#include&lt;set&gt;
#include&lt;vector&gt;
#include&lt;queue&gt;
#define ll long long
using namespace std;

struct ed { int pre,to; double w; };
ed edge[50010],EDGE[12][6010];
int n,m,at,AT[12]={0},ptr[10010]={0},PTR[12][110],ss,tt;
int K,_lim,_co;

//node part
struct _Node { int typ,R,G,cod; }node[10010];
string ins; map&lt;string,int&gt; nmap;
int GAS[60]={0},Gr=0,S,T;

//SSSP1 part
struct nodexx { int cod,tim; };
queue&lt;nodexx&gt; que;
double dis[12][10010]; bool vis[12][10010];

inline void readx(int&amp; x)
{
    x=0; int k=1; register char ch=0;
    while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}

inline void Insert(int fx,int tx,double wx)
{
    at++;
    edge[at].pre=ptr[fx];
    edge[at].to=tx;
    edge[at].w=wx;
    ptr[fx]=at;
    at++;
    edge[at].pre=ptr[tx];
    edge[at].to=fx;
    edge[at].w=wx;
    ptr[tx]=at;
}

inline void Insert2(int kx,int fx,int tx,double wx)
{
    AT[kx]++;
    EDGE[kx][AT[kx]].pre=PTR[kx][fx];
    EDGE[kx][AT[kx]].to=tx;
    EDGE[kx][AT[kx]].w=wx;
    PTR[kx][fx]=AT[kx];
    AT[kx]++;
    EDGE[kx][AT[kx]].pre=PTR[kx][tx];
    EDGE[kx][AT[kx]].to=fx;
    EDGE[kx][AT[kx]].w=wx;
    PTR[kx][tx]=AT[kx];
}

inline void SPFA1(int St)
{
    memset(dis,0x43,sizeof dis); memset(vis,0,sizeof vis);
    nodexx cac1,cac2;
    dis[0][St]=0; cac1.cod=St; cac1.tim=0; que.push(cac1);
    
    while (!que.empty())
    {
        cac1=que.front(); que.pop(); vis[cac1.tim][cac1.cod]=false;
        for (int prex=ptr[cac1.cod];prex;prex=edge[prex].pre)
        {
            cac2.tim=cac1.tim; cac2.cod=edge[prex].to;
            if (node[edge[prex].to].R) cac2.tim++;
            if (cac2.tim&lt;=K &amp;&amp; dis[cac1.tim][cac1.cod]+edge[prex].w&lt;=_lim)
                if (dis[cac2.tim][cac2.cod]&gt;dis[cac1.tim][cac1.cod]+edge[prex].w)
                {
                    dis[cac2.tim][cac2.cod]=dis[cac1.tim][cac1.cod]+edge[prex].w;
                    if (!vis[cac2.tim][cac2.cod])
                    {
                        vis[cac2.tim][cac2.cod]=1;
                        que.push(cac2);
                    }
                }
        }
    }
}

inline void SPFA2()
{
    memset(dis,0x43,sizeof dis); memset(vis,0,sizeof vis);
    nodexx cac1,cac2; dis[0][S]=0;
    cac1.tim=0; cac1.cod=S; que.push(cac1);
    while (!que.empty())
    {
        cac1=que.front(); que.pop(); vis[cac1.tim][cac1.cod]=false;
        for (int w=0;w+cac1.tim&lt;=K;w++)
            for (int prex=PTR[w][cac1.cod];prex;prex=EDGE[w][prex].pre)
            {
                cac2.cod=EDGE[w][prex].to; cac2.tim=cac1.tim+w;
                if (dis[cac2.tim][cac2.cod]&gt;dis[cac1.tim][cac1.cod]+EDGE[w][prex].w+_co)
                {
                    dis[cac2.tim][cac2.cod]=dis[cac1.tim][cac1.cod]+EDGE[w][prex].w+_co;
                    if (!vis[cac2.tim][cac2.cod])
                    {
                        vis[cac2.tim][cac2.cod]=1;
                        que.push(cac2);
                    }
                }
            }
    }
    
    double ans=2*1e12;
    for (int i=0;i&lt;=K;i++) ans=min(ans,dis[i][T]);
    printf("%.3lf\n",ans-_co);
}

inline int node_typmatch(string tmp)
{
    if (tmp=="start") return -1;
    else if (tmp=="end") return -2;
    else if (tmp.find("gas")!=string::npos) return 1;
    return 0;
}
inline void _input()
{
    int fx,tx,wx; char chr[30]={0},cht[30]={0},chs[30]={0};
    readx(n); readx(m); readx(K); readx(_lim); readx(_co);
    for (int i=1;i&lt;=n;i++)
    {
        scanf("%s",chr+1); ins=chr+1;
        readx(node[i].R); readx(node[i].G);
        node[i].typ=node_typmatch(ins);
        node[i].cod=i;
        nmap[ins]=i;
        if (node[i].typ==-1) ss=i;
        else if (node[i].typ==-2) tt=i;
        if (node[i].typ!=0) GAS[++Gr]=i;
    }
    string uch,vch;
    for (int i=1;i&lt;=m;i++)
    {
        scanf("%s%s%s",chr+1,cht+1,chs+1); readx(wx);
        uch=chr+1; vch=cht+1; fx=nmap[uch]; tx=nmap[vch];
        Insert(fx,tx,(double)wx);
    }
}

int main()
{
    _input();
    for (int i=1;i&lt;=n;i++) if (node[i].R)
        for (int prex=ptr[i];prex;prex=edge[prex].pre)
            edge[prex].w+=(double)(node[i].R*node[i].R)/(double)(2*(node[i].R+node[i].G));
    for (int i=1;i&lt;=Gr;i++)
    {
        SPFA1(GAS[i]);
        for (int j=1;j&lt;=Gr;j++) if (i!=j)
            for (int k=0;k&lt;=K;k++) if (dis[k][GAS[j]]&lt;1e9)
                Insert2(k,i,j,dis[k][GAS[j]]);
    }
    for (int i=1;i&lt;=Gr;i++) 
    {
        if (GAS[i]==tt) T=i;
        else if (GAS[i]==ss) S=i;
    }
    SPFA2();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cstdlib>

#include<iterator>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<queue>

#define ll long long

using namespace std;

struct ed { int pre,to; double w; };

ed edge[50010],EDGE[12][6010];

int n,m,at,AT[12]={0},ptr[10010]={0},PTR[12][110],ss,tt;

int K,_lim,_co;

//node part

struct _Node { int typ,R,G,cod; }node[10010];

string ins; map<string,int> nmap;

int GAS[60]={0},Gr=0,S,T;

//SSSP1 part

struct nodexx { int cod,tim; };

queue<nodexx> que;

double dis[12][10010]; bool vis[12][10010];

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline void Insert(int fx,int tx,double wx)

{

at++;

edge[at].pre=ptr[fx];

edge[at].to=tx;

edge[at].w=wx;

ptr[fx]=at;

at++;

edge[at].pre=ptr[tx];

edge[at].to=fx;

edge[at].w=wx;

ptr[tx]=at;

}

inline void Insert2(int kx,int fx,int tx,double wx)

{

AT[kx]++;

EDGE[kx][AT[kx]].pre=PTR[kx][fx];

EDGE[kx][AT[kx]].to=tx;

EDGE[kx][AT[kx]].w=wx;

PTR[kx][fx]=AT[kx];

AT[kx]++;

EDGE[kx][AT[kx]].pre=PTR[kx][tx];

EDGE[kx][AT[kx]].to=fx;

EDGE[kx][AT[kx]].w=wx;

PTR[kx][tx]=AT[kx];

}

inline void SPFA1(int St)

{

memset(dis,0x43,sizeof dis); memset(vis,0,sizeof vis);

nodexx cac1,cac2;

dis[0][St]=0; cac1.cod=St; cac1.tim=0; que.push(cac1);

while (!que.empty())

{

cac1=que.front(); que.pop(); vis[cac1.tim][cac1.cod]=false;

for (int prex=ptr[cac1.cod];prex;prex=edge[prex].pre)

{

cac2.tim=cac1.tim; cac2.cod=edge[prex].to;

if (node[edge[prex].to].R) cac2.tim++;

if (cac2.tim<=K && dis[cac1.tim][cac1.cod]+edge[prex].w<=_lim)

if (dis[cac2.tim][cac2.cod]>dis[cac1.tim][cac1.cod]+edge[prex].w)

{

dis[cac2.tim][cac2.cod]=dis[cac1.tim][cac1.cod]+edge[prex].w;

if (!vis[cac2.tim][cac2.cod])

{

vis[cac2.tim][cac2.cod]=1;

que.push(cac2);

}

inline void SPFA2()

{

memset(dis,0x43,sizeof dis); memset(vis,0,sizeof vis);

nodexx cac1,cac2; dis[0][S]=0;

cac1.tim=0; cac1.cod=S; que.push(cac1);

while (!que.empty())

{

cac1=que.front(); que.pop(); vis[cac1.tim][cac1.cod]=false;

for (int w=0;w+cac1.tim<=K;w++)

for (int prex=PTR[w][cac1.cod];prex;prex=EDGE[w][prex].pre)

{

cac2.cod=EDGE[w][prex].to; cac2.tim=cac1.tim+w;

if (dis[cac2.tim][cac2.cod]>dis[cac1.tim][cac1.cod]+EDGE[w][prex].w+_co)

{

dis[cac2.tim][cac2.cod]=dis[cac1.tim][cac1.cod]+EDGE[w][prex].w+_co;

if (!vis[cac2.tim][cac2.cod])

{

vis[cac2.tim][cac2.cod]=1;

que.push(cac2);

}

double ans=2*1e12;

for (int i=0;i<=K;i++) ans=min(ans,dis[i][T]);

printf("%.3lf\n",ans-_co);

}

inline int node_typmatch(string tmp)

{

if (tmp=="start") return -1;

else if (tmp=="end") return -2;

else if (tmp.find("gas")!=string::npos) return 1;

return 0;

}

inline void _input()

{

int fx,tx,wx; char chr[30]={0},cht[30]={0},chs[30]={0};

readx(n); readx(m); readx(K); readx(_lim); readx(_co);

for (int i=1;i<=n;i++)

{

scanf("%s",chr+1); ins=chr+1;

readx(node[i].R); readx(node[i].G);

node[i].typ=node_typmatch(ins);

node[i].cod=i;

nmap[ins]=i;

if (node[i].typ==-1) ss=i;

else if (node[i].typ==-2) tt=i;

if (node[i].typ!=0) GAS[++Gr]=i;

}

string uch,vch;

for (int i=1;i<=m;i++)

{

scanf("%s%s%s",chr+1,cht+1,chs+1); readx(wx);

uch=chr+1; vch=cht+1; fx=nmap[uch]; tx=nmap[vch];

Insert(fx,tx,(double)wx);

}

int main()

{

_input();

for (int i=1;i<=n;i++) if (node[i].R)

for (int prex=ptr[i];prex;prex=edge[prex].pre)

edge[prex].w+=(double)(node[i].R*node[i].R)/(double)(2*(node[i].R+node[i].G));

for (int i=1;i<=Gr;i++)

{

SPFA1(GAS[i]);

for (int j=1;j<=Gr;j++) if (i!=j)

for (int k=0;k<=K;k++) if (dis[k][GAS[j]]<1e9)

Insert2(k,i,j,dis[k][GAS[j]]);

}

for (int i=1;i<=Gr;i++)

{

if (GAS[i]==tt) T=i;

else if (GAS[i]==ss) S=i;

}

SPFA2();

return 0;

}

[JLOI2014]镜面通道

hhh如果想知道证明可以评论

可以证明如果透气就一定透光。

不会构造出虽然透气，但是光线一直循环地反射，从而出不去的情况。

简单计算几何+最小鸽

每个几何图形做一个点，连边双向边。

圆与正方形交的时候，如果解方程，注意精度。

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;cstdlib&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
#include&lt;vector&gt;
#include&lt;queue&gt;
#include&lt;map&gt;
#include&lt;set&gt;
#define ll long long
#define eps 1e-8
using namespace std;

struct ed
{
    int pre,to,capx;
}edge[360010]={0};
int n,m,at=1,ptr[1010]={0},tt=1002,ss;

queue&lt;int&gt; que;
int cur[1010]={0},level[1010]={0};

struct _square { int x[4],y[4]; }S[310];
struct _circle { int x,y,r; }C[310];
int Cr=0,Sr=0;

inline void readx(int&amp; x)
{
    x=0; int k=1; register char ch=0;
    while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}

inline void Insert(int fx,int tx,int cx)
{
    at++;
    edge[at].pre=ptr[fx];
    edge[at].to=tx;
    edge[at].capx=cx;
    ptr[fx]=at;
    at++;
    edge[at].pre=ptr[tx];
    edge[at].to=fx;
    ptr[tx]=at;
}
inline char BFS()
{
    int cac=0;
    memset(level,0,sizeof level);
    que.push(ss); level[ss]=1;
    while (!que.empty())
    {
        cac=que.front(); que.pop();
        for (int prex=ptr[cac];prex;prex=edge[prex].pre) if ((!level[edge[prex].to]) &amp;&amp; edge[prex].capx)
        {
            level[edge[prex].to]=level[cac]+1;
            que.push(edge[prex].to);
        }
    }
    if (!level[tt]) return false;
    memcpy(cur,ptr,sizeof ptr);
    return true;
}
inline int DFS(int now,int minf)
{
    if ((!minf) || now==tt) return minf;
    int sumf=0,needf;
    for (int prex=cur[now];prex;prex=edge[prex].pre)
    {
        cur[now]=prex;
        if (level[edge[prex].to]==level[now]+1)
            if (needf=DFS(edge[prex].to,min(minf,edge[prex].capx)))
            {
                sumf+=needf; minf-=needf;
                edge[prex].capx-=needf; edge[prex^1].capx+=needf;
                if (!minf) break;
            }
    }
    return sumf;
}

inline double dist(int _x1,int _y1,int _x2,int _y2) { return sqrt((_x1-_x2)*(_x1-_x2)+(_y1-_y2)*(_y1-_y2)); }
inline bool Judge1(_circle a,_circle b) { return dist(a.x,a.y,b.x,b.y)&lt;=(double)(a.r+b.r); }
inline bool Judge2(_circle a,_square b)
{
    for (int i=0;i&lt;=3;i++) if (dist(a.x,a.y,b.x[i],b.y[i])&lt;=(double)a.r) return true;
    if (a.x&gt;=b.x[0] &amp;&amp; a.x&lt;=b.x[3] &amp;&amp; a.y+a.r&lt;=b.y[3] &amp;&amp; a.y+a.r&gt;=b.y[0]) return true;
    if (a.x&gt;=b.x[0] &amp;&amp; a.x&lt;=b.x[3] &amp;&amp; a.y-a.r&lt;=b.y[3] &amp;&amp; a.y-a.r&gt;=b.y[0]) return true;
    if (a.y&gt;=b.y[0] &amp;&amp; a.y&lt;=b.y[3] &amp;&amp; a.x+a.r&gt;=b.x[0] &amp;&amp; a.x+a.r&lt;=b.x[3]) return true;
    if (a.y&gt;=b.y[0] &amp;&amp; a.y&lt;=b.y[3] &amp;&amp; a.x-a.r&gt;=b.x[0] &amp;&amp; a.x-a.r&lt;=b.x[3]) return true;
    return false;
}
inline bool Judge3(_square a,_square b)
{
    for (int i=0;i&lt;=3;i++)
    {
        int _x=a.x[i],_y=a.y[i];
        if ( _x&gt;=b.x[0] &amp;&amp; _x&lt;=b.x[3] &amp;&amp; _y&gt;=b.y[0] &amp;&amp; _y&lt;=b.y[3] ) return true;
    }
    return false;
}

int main()
{
    int typ,c_x,c_y;
    readx(c_x); readx(c_y); readx(n);
    for (int i=1;i&lt;=n;i++)
    {
        readx(typ);
        if (typ==1) { Cr++; readx(C[Cr].x); readx(C[Cr].y); readx(C[Cr].r); }
        else
        {
            Sr++;
            readx(S[Sr].x[0]); readx(S[Sr].y[0]); readx(S[Sr].x[3]); readx(S[Sr].y[3]);
            S[Sr].x[1]=S[Sr].x[0]; S[Sr].y[1]=S[Sr].y[3];
            S[Sr].x[2]=S[Sr].x[3]; S[Sr].y[2]=S[Sr].y[0];
        }
    }
    
    for (int i=1;i&lt;=Cr;i++)
    {
        for (int j=i+1;j&lt;=Cr;j++) if (Judge1(C[i],C[j]))
            { Insert(Cr+i,j,2*1e9); Insert(Cr+j,i,2*1e9); }
            
        for (int j=1;j&lt;=Sr;j++) if (Judge2(C[i],S[j]))
            { Insert(Cr+i,2*Cr+j,2*1e9); Insert(2*Cr+Sr+j,i,2*1e9); }
            
        if (C[i].y&lt;=C[i].r) Insert(ss,i,2*1e9);
        if (C[i].y+C[i].r&gt;=c_y) Insert(Cr+i,tt,2*1e9);
    }
    for (int i=1;i&lt;=Sr;i++)
    {
        for (int j=i+1;j&lt;=Sr;j++) if (Judge3(S[i],S[j]))
            { Insert(2*Cr+Sr+i,2*Cr+j,2*1e9); Insert(2*Cr+Sr+j,2*Cr+i,2*1e9); }
            
        if (S[i].y[0]&lt;=0) Insert(ss,2*Cr+i,2*1e9);
        if (S[i].y[3]&gt;=c_y) Insert(2*Cr+Sr+i,tt,2*1e9);
    }
    for (int i=1;i&lt;=Cr;i++) Insert(i,i+Cr,1);
    for (int i=1;i&lt;=Sr;i++) Insert(2*Cr+i,2*Cr+Sr+i,1);
    
    int ans=0;
    while (BFS()) ans+=DFS(ss,2*1e9);
    printf("%d\n",ans);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#include<iterator>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define eps 1e-8

using namespace std;

struct ed

{

int pre,to,capx;

}edge[360010]={0};

int n,m,at=1,ptr[1010]={0},tt=1002,ss;

queue<int> que;

int cur[1010]={0},level[1010]={0};

struct _square { int x[4],y[4]; }S[310];

struct _circle { int x,y,r; }C[310];

int Cr=0,Sr=0;

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline void Insert(int fx,int tx,int cx)

{

at++;

edge[at].pre=ptr[fx];

edge[at].to=tx;

edge[at].capx=cx;

ptr[fx]=at;

at++;

edge[at].pre=ptr[tx];

edge[at].to=fx;

ptr[tx]=at;

}

inline char BFS()

{

int cac=0;

memset(level,0,sizeof level);

que.push(ss); level[ss]=1;

while (!que.empty())

{

cac=que.front(); que.pop();

for (int prex=ptr[cac];prex;prex=edge[prex].pre) if ((!level[edge[prex].to]) && edge[prex].capx)

{

level[edge[prex].to]=level[cac]+1;

que.push(edge[prex].to);

}

if (!level[tt]) return false;

memcpy(cur,ptr,sizeof ptr);

return true;

}

inline int DFS(int now,int minf)

{

if ((!minf) || now==tt) return minf;

int sumf=0,needf;

for (int prex=cur[now];prex;prex=edge[prex].pre)

{

cur[now]=prex;

if (level[edge[prex].to]==level[now]+1)

if (needf=DFS(edge[prex].to,min(minf,edge[prex].capx)))

{

sumf+=needf; minf-=needf;

edge[prex].capx-=needf; edge[prex^1].capx+=needf;

if (!minf) break;

}

return sumf;

}

inline double dist(int _x1,int _y1,int _x2,int _y2) { return sqrt((_x1-_x2)*(_x1-_x2)+(_y1-_y2)*(_y1-_y2)); }

inline bool Judge1(_circle a,_circle b) { return dist(a.x,a.y,b.x,b.y)<=(double)(a.r+b.r); }

inline bool Judge2(_circle a,_square b)

{

for (int i=0;i<=3;i++) if (dist(a.x,a.y,b.x[i],b.y[i])<=(double)a.r) return true;

if (a.x>=b.x[0] && a.x<=b.x[3] && a.y+a.r<=b.y[3] && a.y+a.r>=b.y[0]) return true;

if (a.x>=b.x[0] && a.x<=b.x[3] && a.y-a.r<=b.y[3] && a.y-a.r>=b.y[0]) return true;

if (a.y>=b.y[0] && a.y<=b.y[3] && a.x+a.r>=b.x[0] && a.x+a.r<=b.x[3]) return true;

if (a.y>=b.y[0] && a.y<=b.y[3] && a.x-a.r>=b.x[0] && a.x-a.r<=b.x[3]) return true;

return false;

}

inline bool Judge3(_square a,_square b)

{

for (int i=0;i<=3;i++)

{

int _x=a.x[i],_y=a.y[i];

if ( _x>=b.x[0] && _x<=b.x[3] && _y>=b.y[0] && _y<=b.y[3] ) return true;

}

return false;

}

int main()

{

int typ,c_x,c_y;

readx(c_x); readx(c_y); readx(n);

for (int i=1;i<=n;i++)

{

readx(typ);

if (typ==1) { Cr++; readx(C[Cr].x); readx(C[Cr].y); readx(C[Cr].r); }

else

{

Sr++;

readx(S[Sr].x[0]); readx(S[Sr].y[0]); readx(S[Sr].x[3]); readx(S[Sr].y[3]);

S[Sr].x[1]=S[Sr].x[0]; S[Sr].y[1]=S[Sr].y[3];

S[Sr].x[2]=S[Sr].x[3]; S[Sr].y[2]=S[Sr].y[0];

}

for (int i=1;i<=Cr;i++)

{

for (int j=i+1;j<=Cr;j++) if (Judge1(C[i],C[j]))

{ Insert(Cr+i,j,2*1e9); Insert(Cr+j,i,2*1e9); }

for (int j=1;j<=Sr;j++) if (Judge2(C[i],S[j]))

{ Insert(Cr+i,2*Cr+j,2*1e9); Insert(2*Cr+Sr+j,i,2*1e9); }

if (C[i].y<=C[i].r) Insert(ss,i,2*1e9);

if (C[i].y+C[i].r>=c_y) Insert(Cr+i,tt,2*1e9);

}

for (int i=1;i<=Sr;i++)

{

for (int j=i+1;j<=Sr;j++) if (Judge3(S[i],S[j]))

{ Insert(2*Cr+Sr+i,2*Cr+j,2*1e9); Insert(2*Cr+Sr+j,2*Cr+i,2*1e9); }

if (S[i].y[0]<=0) Insert(ss,2*Cr+i,2*1e9);

if (S[i].y[3]>=c_y) Insert(2*Cr+Sr+i,tt,2*1e9);

}

for (int i=1;i<=Cr;i++) Insert(i,i+Cr,1);

for (int i=1;i<=Sr;i++) Insert(2*Cr+i,2*Cr+Sr+i,1);

int ans=0;

while (BFS()) ans+=DFS(ss,2*1e9);

printf("%d\n",ans);

return 0;

}

[JLOI2014]聪明的燕姿

数学题！

首先对于一个数字 $x$ 的唯一分解式设为 $\prod _{i=1} ^{n} p_i^{a_i}$ 。

那么约数和就是 $\prod _{i=1} ^{n} \sum _{j=0} ^{a_i} p_i^j$ ，这个非常显然 (?)

那么……我们可以猜出 $x$ 和 $S$ 是同级的。

那么显然 $p_i \leqslant \sqrt{S}$ 。

那么可以暴搜。枚举 $p_i$ 和 $a_i$ 。

一个特判是如果当前的剩余数字 $S_i$ 减去 $1$ 之后为一个质数，并且不小于当前枚举到的最大质数，那么也要算进答案。

需要证明请在评论区留言。

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
#include&lt;cstdlib&gt;
#include&lt;vector&gt;
#include&lt;queue&gt;
#include&lt;map&gt;
#include&lt;set&gt;
#define ll long long
using namespace std;

ll pnum[100010]={0},ptr;
char nnum[100010]={0};

ll S,anses[200010]={0},ctr=0;
ll seq[100010]={0};

inline void readx(int&amp; x)
{
    x=0; int k=1; register char ch=0;
    while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}

inline void Prime_Shake(int upat)
{
    nnum[0]=nnum[1]=1;
    for (int i=2;i&lt;=upat;i++)
    {
        if (!nnum[i]) pnum[++ptr]=i;
        for (int j=1;j&lt;=ptr &amp;&amp; pnum[j]*i&lt;=upat;j++)
        {
            nnum[pnum[j]*i]=true;
            if (!(i%pnum[j])) break;
        }
    }
}

inline bool is_prime(int inx)
{
    if (inx&lt;=1) return false;
    if (inx&lt;=100000) return nnum[inx]^1;
    for (int i=1;pnum[i]*pnum[i]&lt;=inx;i++)
        if (!(inx%pnum[i])) return false;
    return true;
}

inline void DFS(ll _x,ll _sum,int _inx)
{
    if (_x==1) { anses[++ctr]=_sum; return; }
    if (_x-1&gt;=pnum[_inx] &amp;&amp; is_prime(_x-1)) anses[++ctr]=_sum*(_x-1);
    
    ll tmp=0,rec;
    for (int i=_inx;pnum[i]*pnum[i]&lt;=_x;i++)
    {
        tmp=pnum[i]; rec=pnum[i]+1;
        for (;rec&lt;=_x;tmp*=pnum[i],rec+=tmp) if (!(_x%rec)) DFS(_x/rec,_sum*tmp,i+1);
    }
}

int main()
{
    Prime_Shake(100000);
    while (scanf("%lld",&amp;S)!=EOF)
    {
        memset(anses,0,sizeof anses); ctr=0;
        DFS(S,1LL,1);
        sort(anses+1,anses+ctr+1);
        printf("%lld\n",ctr);
        for (int i=1;i&lt;=ctr;i++) printf("%lld%c",anses[i]," \n"[i==ctr]);
    }
}

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<iterator>

#include<cstdlib>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

using namespace std;

ll pnum[100010]={0},ptr;

char nnum[100010]={0};

ll S,anses[200010]={0},ctr=0;

ll seq[100010]={0};

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline void Prime_Shake(int upat)

{

nnum[0]=nnum[1]=1;

for (int i=2;i<=upat;i++)

{

if (!nnum[i]) pnum[++ptr]=i;

for (int j=1;j<=ptr && pnum[j]*i<=upat;j++)

{

nnum[pnum[j]*i]=true;

if (!(i%pnum[j])) break;

}

inline bool is_prime(int inx)

{

if (inx<=1) return false;

if (inx<=100000) return nnum[inx]^1;

for (int i=1;pnum[i]*pnum[i]<=inx;i++)

if (!(inx%pnum[i])) return false;

return true;

}

inline void DFS(ll _x,ll _sum,int _inx)

{

if (_x==1) { anses[++ctr]=_sum; return; }

if (_x-1>=pnum[_inx] && is_prime(_x-1)) anses[++ctr]=_sum*(_x-1);

ll tmp=0,rec;

for (int i=_inx;pnum[i]*pnum[i]<=_x;i++)

{

tmp=pnum[i]; rec=pnum[i]+1;

for (;rec<=_x;tmp*=pnum[i],rec+=tmp) if (!(_x%rec)) DFS(_x/rec,_sum*tmp,i+1);

}

int main()

{

Prime_Shake(100000);

while (scanf("%lld",&S)!=EOF)

{

memset(anses,0,sizeof anses); ctr=0;

DFS(S,1LL,1);

sort(anses+1,anses+ctr+1);

printf("%lld\n",ctr);

for (int i=1;i<=ctr;i++) printf("%lld%c",anses[i]," \n"[i==ctr]);

}

QAQ (一瓶咖啡灌下去) 差不多清醒了…

2018年7月31日2018年7月31日

JLOI2010 世界杯租房

数据很水，偷偷看了下好像 $T \leqslant 100$

嗯，DP+输出方案。记得为了字典序最小我们要倒着DP。。

然后没了。。别写龊了写炸复杂度就好。

$O(Tmn^2)$

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
#include&lt;cstdlib&gt;
#include&lt;vector&gt;
#include&lt;cmath&gt;
#include&lt;string&gt;
#include&lt;cstdlib&gt;
#include&lt;map&gt;
#include&lt;set&gt;
#define ll long long
#define PAUSE system("pause")
using namespace std;

int n=1,m=1,s,t,_Ctr=0;
bool vis[110][110]={0};
char chs[100]={0};

int dp[110][30]={0},pre[110][30]={0},otpt[110]={0};

inline void readx(int&amp; x)
{
	x=0; int k=1; register char ch=0;
	while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline void clear_all()
{
	s=t=0;
	memset(vis,0,sizeof vis);
	memset(dp,0,sizeof dp);
	memset(pre,0,sizeof pre);
	memset(otpt,0,sizeof otpt);
	memset(chs,0,sizeof chs);
}

inline void output(int i,int j)
{
	if (i!=t) output(i+1,pre[i][j]);
	if (pre[i][j]!=j) otpt[i+1]=pre[i][j]+'A'-1;
}

int main()
{
	while (1)
	{
		_Ctr++; clear_all();
		readx(m); readx(n); 
		if (m==0 || n==0) return 0;
		if (_Ctr&gt;1) putchar('\n');
		
		for (int i=1;i&lt;=m;i++)
		{
			scanf("%s",chs+1);
			for (int j=1;j&lt;=n;j++) vis[i][j]=(chs[j]=='X');
		}
		readx(s); readx(t); t--;
		
		memset(dp,0x3f,sizeof dp);
		for (int i=1;i&lt;=n;i++) if (!vis[t][i]) dp[t][i]=0;
		for (int i=t-1;i&gt;=s;i--)
			for (int j=1;j&lt;=n;j++) if (!vis[i][j])
			{
				for (int k=1;k&lt;=n;k++) if (!vis[i+1][k])
				{
					if (dp[i+1][k]+(j!=k)&lt;dp[i][j])
					{
						dp[i][j]=dp[i+1][k]+(j!=k);
						pre[i][j]=k;
					}
				}
			}
		printf("Case %d:\n\n",_Ctr);
		
		int ans=2*1e9,ptr=0;
		for (int i=1;i&lt;=n;i++) if (dp[s][i]&lt;ans)
			{ ans=dp[s][i]; ptr=i; }
		if (ans&gt;200)  { printf("Not available\n"); continue; }
		
		output(s,ptr); int qwq=s; otpt[qwq]=ptr+'A'-1;
		for (int i=s+1;i&lt;=t;i++) if (otpt[i]!=0)
		{
			printf("%c: %d-%d\n",otpt[qwq],qwq,i);
			qwq=i;
		}
		printf("%c: %d-%d\n",otpt[qwq],qwq,t+1);
	}
	return 0;
}

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<iterator>

#include<cstdlib>

#include<vector>

#include<cmath>

#include<string>

#include<cstdlib>

#include<map>

#include<set>

#define ll long long

#define PAUSE system("pause")

using namespace std;

int n=1,m=1,s,t,_Ctr=0;

bool vis[110][110]={0};

char chs[100]={0};

int dp[110][30]={0},pre[110][30]={0},otpt[110]={0};

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline void clear_all()

{

s=t=0;

memset(vis,0,sizeof vis);

memset(dp,0,sizeof dp);

memset(pre,0,sizeof pre);

memset(otpt,0,sizeof otpt);

memset(chs,0,sizeof chs);

}

inline void output(int i,int j)

{

if (i!=t) output(i+1,pre[i][j]);

if (pre[i][j]!=j) otpt[i+1]=pre[i][j]+'A'-1;

}

int main()

{

while (1)

{

_Ctr++; clear_all();

readx(m); readx(n);

if (m==0 || n==0) return 0;

if (_Ctr>1) putchar('\n');

for (int i=1;i<=m;i++)

{

scanf("%s",chs+1);

for (int j=1;j<=n;j++) vis[i][j]=(chs[j]=='X');

}

readx(s); readx(t); t--;

memset(dp,0x3f,sizeof dp);

for (int i=1;i<=n;i++) if (!vis[t][i]) dp[t][i]=0;

for (int i=t-1;i>=s;i--)

for (int j=1;j<=n;j++) if (!vis[i][j])

{

for (int k=1;k<=n;k++) if (!vis[i+1][k])

{

if (dp[i+1][k]+(j!=k)<dp[i][j])

{

dp[i][j]=dp[i+1][k]+(j!=k);

pre[i][j]=k;

}

printf("Case %d:\n\n",_Ctr);

int ans=2*1e9,ptr=0;

for (int i=1;i<=n;i++) if (dp[s][i]<ans)

{ ans=dp[s][i]; ptr=i; }

if (ans>200) { printf("Not available\n"); continue; }

output(s,ptr); int qwq=s; otpt[qwq]=ptr+'A'-1;

for (int i=s+1;i<=t;i++) if (otpt[i]!=0)

{

printf("%c: %d-%d\n",otpt[qwq],qwq,i);

qwq=i;

}

printf("%c: %d-%d\n",otpt[qwq],qwq,t+1);

}

return 0;

}

2018年4月3日

BZOJ3083 遥远的国度

遥远的行星？神奇的国度？

NO，遥远的国度.

这题真皮OVO

考虑换根之后只有两种情况答案会变

一是根与询问点重合答案整棵树

二是在询问点的子树内，这时候需要……枚举子树树根！

然后用dfs序来判断，这玩意是连续的（嗯……？），而且在每个子树内也是连续的（！）

锁定在哪颗子树内！

if (dfn[child]&lt;=dfn[croot] &amp;&amp; dfn[child]+tsize[child]-1&gt;=dfn[croot])

1	if (dfn[child]<=dfn[croot] && dfn[child]+tsize[child]-1>=dfn[croot])

然后你抓着这个子树的根节点把它拎起来，这整棵树其余的部分就耷拉到下面了

然后你就会发现这时候实际是询问这个红色的部分

然后就行了。

画风奇怪？？

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
#include&lt;cstdlib&gt;
#include&lt;queue&gt;
#include&lt;vector&gt;
using namespace std;

struct segment_tree { int l,r,w,tag; bool has_tag; } SGT[400010]={0};
struct ed { int pre,to; } edge[200010]={0};
int nodenum,at=1,pointer[100010]={0},fx,tx,nodev[100010]={0},croot;

int anc[100010],topx[100010],tsize[100010],hson[100010],dfn[100010],depth[100010];
int tstamp=0,nnv[100010]={0};
int l[100010][22]={0};

int opt,lx,rx,val,typ,ux,vx;

inline void readx(int&amp; x)
{
	x=0; int k=1; register char ch=0;
	while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}
inline void Insert()
{
	at++;
	edge[at].pre=pointer[fx];
	edge[at].to=tx;
	pointer[fx]=at;
	at++;
	edge[at].pre=pointer[tx];
	edge[at].to=fx;
	pointer[tx]=at;
}

inline void Fancy(int nownode,int nowdep,int fa)
{
	//LCA
	l[nownode][0]=fa;
	for (int i=1;i&lt;=20;i++) l[nownode][i]=l[l[nownode][i-1]][i-1];
	
	//find heavy son
	depth[nownode]=nowdep; anc[nownode]=fa; tsize[nownode]=1;
	for (int prex=pointer[nownode];prex;prex=edge[prex].pre) if (edge[prex].to!=fa)
	{
		Fancy(edge[prex].to,nowdep+1,nownode);
		tsize[nownode]+=tsize[edge[prex].to];
		if (tsize[edge[prex].to]&gt;tsize[hson[nownode]]) hson[nownode]=edge[prex].to;
	}
}
inline void Dreams(int nownode,int src)
{
	topx[nownode]=src; dfn[nownode]=++tstamp; nnv[tstamp]=nodev[nownode];
	if (hson[nownode]) Dreams(hson[nownode],src);
	for (int prex=pointer[nownode];prex;prex=edge[prex].pre) 
		if (edge[prex].to!=hson[nownode] &amp;&amp; edge[prex].to!=anc[nownode]) Dreams(edge[prex].to,edge[prex].to);
}

inline void BuildTree(int lxx,int rxx,int inx)
{
	SGT[inx].l=lxx; SGT[inx].r=rxx;
	if (lxx==rxx) { SGT[inx].w=nnv[lxx]; return; }
	int mid=(lxx+rxx)&gt;&gt;1;
	BuildTree(lxx,mid,inx&lt;&lt;1);
	BuildTree(mid+1,rxx,inx&lt;&lt;1|1);
	SGT[inx].w=min(SGT[inx&lt;&lt;1].w,SGT[inx&lt;&lt;1|1].w);
}
inline void pushdown(int inx)
{
	SGT[inx&lt;&lt;1].tag=SGT[inx&lt;&lt;1|1].tag=SGT[inx].tag;
	SGT[inx&lt;&lt;1].has_tag=SGT[inx&lt;&lt;1|1].has_tag=true;
	SGT[inx&lt;&lt;1].w=SGT[inx&lt;&lt;1|1].w=SGT[inx].tag;
	SGT[inx].tag=0; SGT[inx].has_tag=false;
}
inline void update(int inx)
{
	if (SGT[inx].l&gt;=lx &amp;&amp; SGT[inx].r&lt;=rx)
	{
		SGT[inx].w=val; SGT[inx].tag=val; SGT[inx].has_tag=true;
		return;
	}
	if (SGT[inx].has_tag) pushdown(inx);
	int mid=(SGT[inx].l+SGT[inx].r)&gt;&gt;1;
	if (lx&lt;=mid) update(inx&lt;&lt;1);
	if (rx&gt;mid) update(inx&lt;&lt;1|1);
	SGT[inx].w=min(SGT[inx&lt;&lt;1].w,SGT[inx&lt;&lt;1|1].w);
}
inline int query(int inx)
{
	if (SGT[inx].l&gt;=lx &amp;&amp; SGT[inx].r&lt;=rx) return SGT[inx].w;
	if (SGT[inx].has_tag) pushdown(inx);
	int mid=(SGT[inx].l+SGT[inx].r)&gt;&gt;1,ret=2*1e9;
	if (lx&lt;=mid) ret=query(inx&lt;&lt;1);
	if (rx&gt;mid) ret=min(ret,query(inx&lt;&lt;1|1));
	SGT[inx].w=min(SGT[inx&lt;&lt;1].w,SGT[inx&lt;&lt;1|1].w);
	return ret;
}

inline int LCA(int u,int v)
{
	if (depth[u]&lt;depth[v]) swap(u,v);
	for (int i=20;i&gt;=0;i--) if (depth[l[u][i]]&gt;=depth[v]) u=l[u][i];
	if (u==v) return u;
	for (int i=20;i&gt;=0;i--) if (l[u][i]!=l[v][i]) { u=l[u][i]; v=l[v][i]; }
	return anc[u];
}

inline void upd_range(int u,int v)
{
	while (topx[u]!=topx[v])
	{
		if (depth[topx[u]]&lt;depth[topx[v]]) swap(u,v);
		lx=dfn[topx[u]]; rx=dfn[u]; update(1);
		u=anc[topx[u]];
	}
	if (depth[u]&lt;depth[v]) swap(u,v);
	lx=dfn[v]; rx=dfn[u]; update(1);
}
inline int solve(int u)
{
	if (u==croot) { lx=1; rx=tstamp; return query(1); }
	else if (LCA(croot,u)!=u)
	{
		lx=dfn[u]; rx=dfn[u]+tsize[u]-1;
		return query(1);
	}
	else
	{
		int ret=2*1e9;
		for (int prex=pointer[u];prex;prex=edge[prex].pre) if (edge[prex].to!=anc[u])
		{
			if (dfn[edge[prex].to]&lt;=dfn[croot] &amp;&amp; dfn[edge[prex].to]+tsize[edge[prex].to]-1&gt;=dfn[croot])
			{
				lx=1; rx=dfn[edge[prex].to]-1;
				if (rx&gt;=lx) ret=min(ret,query(1));
				lx=dfn[edge[prex].to]+tsize[edge[prex].to]; rx=tstamp;
				if (rx&gt;=lx) ret=min(ret,query(1));
			}
		}
		return ret;
	}
}

int main()
{
	readx(nodenum); readx(opt);
	for (int i=1;i&lt;nodenum;i++)
	{
		readx(fx); readx(tx); 
		Insert();
	}
	for (int i=1;i&lt;=nodenum;i++) readx(nodev[i]);
	readx(croot);
	
	Fancy(1,1,0); Dreams(1,1);
	BuildTree(1,tstamp,1);

	for (int i=1;i&lt;=opt;i++)
	{
		readx(typ);
		if (typ==1) readx(croot);
		else if (typ==2)
		{
			readx(ux); readx(vx); readx(val);
			upd_range(ux,vx);
		}
		else { readx(ux); printf("%d\n",solve(ux)); }
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<iterator>

#include<cstdlib>

#include<queue>

#include<vector>

using namespace std;

struct segment_tree { int l,r,w,tag; bool has_tag; } SGT[400010]={0};

struct ed { int pre,to; } edge[200010]={0};

int nodenum,at=1,pointer[100010]={0},fx,tx,nodev[100010]={0},croot;

int anc[100010],topx[100010],tsize[100010],hson[100010],dfn[100010],depth[100010];

int tstamp=0,nnv[100010]={0};

int l[100010][22]={0};

int opt,lx,rx,val,typ,ux,vx;

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline void Insert()

{

at++;

edge[at].pre=pointer[fx];

edge[at].to=tx;

pointer[fx]=at;

at++;

edge[at].pre=pointer[tx];

edge[at].to=fx;

pointer[tx]=at;

}

inline void Fancy(int nownode,int nowdep,int fa)

{

//LCA

l[nownode][0]=fa;

for (int i=1;i<=20;i++) l[nownode][i]=l[l[nownode][i-1]][i-1];

//find heavy son

depth[nownode]=nowdep; anc[nownode]=fa; tsize[nownode]=1;

for (int prex=pointer[nownode];prex;prex=edge[prex].pre) if (edge[prex].to!=fa)

{

Fancy(edge[prex].to,nowdep+1,nownode);

tsize[nownode]+=tsize[edge[prex].to];

if (tsize[edge[prex].to]>tsize[hson[nownode]]) hson[nownode]=edge[prex].to;

}

inline void Dreams(int nownode,int src)

{

topx[nownode]=src; dfn[nownode]=++tstamp; nnv[tstamp]=nodev[nownode];

if (hson[nownode]) Dreams(hson[nownode],src);

for (int prex=pointer[nownode];prex;prex=edge[prex].pre)

if (edge[prex].to!=hson[nownode] && edge[prex].to!=anc[nownode]) Dreams(edge[prex].to,edge[prex].to);

}

inline void BuildTree(int lxx,int rxx,int inx)

{

SGT[inx].l=lxx; SGT[inx].r=rxx;

if (lxx==rxx) { SGT[inx].w=nnv[lxx]; return; }

int mid=(lxx+rxx)>>1;

BuildTree(lxx,mid,inx<<1);

BuildTree(mid+1,rxx,inx<<1|1);

SGT[inx].w=min(SGT[inx<<1].w,SGT[inx<<1|1].w);

}

inline void pushdown(int inx)

{

SGT[inx<<1].tag=SGT[inx<<1|1].tag=SGT[inx].tag;

SGT[inx<<1].has_tag=SGT[inx<<1|1].has_tag=true;

SGT[inx<<1].w=SGT[inx<<1|1].w=SGT[inx].tag;

SGT[inx].tag=0; SGT[inx].has_tag=false;

}

inline void update(int inx)

{

if (SGT[inx].l>=lx && SGT[inx].r<=rx)

{

SGT[inx].w=val; SGT[inx].tag=val; SGT[inx].has_tag=true;

return;

}

if (SGT[inx].has_tag) pushdown(inx);

int mid=(SGT[inx].l+SGT[inx].r)>>1;

if (lx<=mid) update(inx<<1);

if (rx>mid) update(inx<<1|1);

SGT[inx].w=min(SGT[inx<<1].w,SGT[inx<<1|1].w);

}

inline int query(int inx)

{

if (SGT[inx].l>=lx && SGT[inx].r<=rx) return SGT[inx].w;

if (SGT[inx].has_tag) pushdown(inx);

int mid=(SGT[inx].l+SGT[inx].r)>>1,ret=2*1e9;

if (lx<=mid) ret=query(inx<<1);

if (rx>mid) ret=min(ret,query(inx<<1|1));

SGT[inx].w=min(SGT[inx<<1].w,SGT[inx<<1|1].w);

return ret;

}

inline int LCA(int u,int v)

{

if (depth[u]<depth[v]) swap(u,v);

for (int i=20;i>=0;i--) if (depth[l[u][i]]>=depth[v]) u=l[u][i];

if (u==v) return u;

for (int i=20;i>=0;i--) if (l[u][i]!=l[v][i]) { u=l[u][i]; v=l[v][i]; }

return anc[u];

}

inline void upd_range(int u,int v)

{

while (topx[u]!=topx[v])

{

if (depth[topx[u]]<depth[topx[v]]) swap(u,v);

lx=dfn[topx[u]]; rx=dfn[u]; update(1);

u=anc[topx[u]];

}

if (depth[u]<depth[v]) swap(u,v);

lx=dfn[v]; rx=dfn[u]; update(1);

}

inline int solve(int u)

{

if (u==croot) { lx=1; rx=tstamp; return query(1); }

else if (LCA(croot,u)!=u)

{

lx=dfn[u]; rx=dfn[u]+tsize[u]-1;

return query(1);

}

else

{

int ret=2*1e9;

for (int prex=pointer[u];prex;prex=edge[prex].pre) if (edge[prex].to!=anc[u])

{

if (dfn[edge[prex].to]<=dfn[croot] && dfn[edge[prex].to]+tsize[edge[prex].to]-1>=dfn[croot])

{

lx=1; rx=dfn[edge[prex].to]-1;

if (rx>=lx) ret=min(ret,query(1));

lx=dfn[edge[prex].to]+tsize[edge[prex].to]; rx=tstamp;

if (rx>=lx) ret=min(ret,query(1));

}

return ret;

}

int main()

{

readx(nodenum); readx(opt);

for (int i=1;i<nodenum;i++)

{

readx(fx); readx(tx);

Insert();

}

for (int i=1;i<=nodenum;i++) readx(nodev[i]);

readx(croot);

Fancy(1,1,0); Dreams(1,1);

BuildTree(1,tstamp,1);

for (int i=1;i<=opt;i++)

{

readx(typ);

if (typ==1) readx(croot);

else if (typ==2)

{

readx(ux); readx(vx); readx(val);

upd_range(ux,vx);

}

else { readx(ux); printf("%d\n",solve(ux)); }

}

return 0;

}

2018年4月3日

BZOJ4196 | NOI2015 软件包管理器

呀，我又来骗访问了QAQ

其实就是刨的模板题，不过题面真tm长

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
#include&lt;cstdlib&gt;
#include&lt;queue&gt;
#include&lt;vector&gt;
using namespace std;

struct segment_tree { int l,r,w,tag; } SGT[400100]={0};
struct ed { int pre,to; } edge[200010]={0};
int nodenum,fx,tx,at=0,pointer[100010]={0};

int topx[100010]={0},hson[100010]={0},anc[100010]={0},tsize[100010]={0};
int depth[100010]={0},dfn[100010]={0},tstamp=0;

int lx,rx,val;
char chs[10]={0};

inline void readx(int&amp; x)
{
	x=0; int k=1; register char ch=0;
	while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline void Insert()
{
	at++;
	edge[at].pre=pointer[fx];
	edge[at].to=tx;
	pointer[fx]=at;
	at++;
	edge[at].pre=pointer[tx];
	edge[at].to=fx;
	pointer[tx]=at;
}

inline void Fancy(int nownode,int nowdep,int fa)
{
	depth[nownode]=nowdep; anc[nownode]=fa; tsize[nownode]=1;
	for (int prex=pointer[nownode];prex;prex=edge[prex].pre)
	{
		if (edge[prex].to!=fa)
		{
			Fancy(edge[prex].to,nowdep+1,nownode);
			tsize[nownode]+=tsize[edge[prex].to];
			if (tsize[hson[nownode]]&lt;tsize[edge[prex].to]) hson[nownode]=edge[prex].to;
		}
	}
}
inline void Dreams(int nownode,int src)
{
	topx[nownode]=src; dfn[nownode]=++tstamp;
	if (hson[nownode]) Dreams(hson[nownode],src);
	for (int prex=pointer[nownode];prex;prex=edge[prex].pre)
		if (edge[prex].to!=anc[nownode] &amp;&amp; edge[prex].to!=hson[nownode]) Dreams(edge[prex].to,edge[prex].to);
}

inline void BuildTree(int lxx,int rxx,int inx)
{
	SGT[inx].l=lxx; SGT[inx].r=rxx;
	if (lxx==rxx) return;
	int mid=(lxx+rxx)&gt;&gt;1;
	BuildTree(lxx,mid,inx&lt;&lt;1);
	BuildTree(mid+1,rxx,inx&lt;&lt;1|1);
}
inline void pushdown(int inx)
{
	SGT[inx&lt;&lt;1].tag=SGT[inx&lt;&lt;1|1].tag=SGT[inx].tag;
	if (SGT[inx].tag==1) SGT[inx&lt;&lt;1].w=SGT[inx&lt;&lt;1|1].w=0;
	if (SGT[inx].tag==2)
	{
		SGT[inx&lt;&lt;1].w=(SGT[inx&lt;&lt;1].r-SGT[inx&lt;&lt;1].l+1);
		SGT[inx&lt;&lt;1|1].w=(SGT[inx&lt;&lt;1|1].r-SGT[inx&lt;&lt;1|1].l+1);
	}
	SGT[inx].tag=0;
}
inline void update(int inx)
{
	if (SGT[inx].l&gt;=lx &amp;&amp; SGT[inx].r&lt;=rx)
	{
		SGT[inx].w=val*(SGT[inx].r-SGT[inx].l+1);
		SGT[inx].tag=val+1;
		return;
	}
	if (SGT[inx].tag) pushdown(inx);
	int mid=(SGT[inx].l+SGT[inx].r)&gt;&gt;1;
	if (lx&lt;=mid) update(inx&lt;&lt;1);
	if (rx&gt;mid) update(inx&lt;&lt;1|1);
	SGT[inx].w=SGT[inx&lt;&lt;1].w+SGT[inx&lt;&lt;1|1].w;
}
inline int query(int inx)
{
	if (SGT[inx].l&gt;=lx &amp;&amp; SGT[inx].r&lt;=rx) return SGT[inx].w;
	if (SGT[inx].tag) pushdown(inx);
	int mid=(SGT[inx].l+SGT[inx].r)&gt;&gt;1,ret=0;
	if (lx&lt;=mid) ret+=query(inx&lt;&lt;1);
	if (rx&gt;mid) ret+=query(inx&lt;&lt;1|1);
	SGT[inx].w=SGT[inx&lt;&lt;1].w+SGT[inx&lt;&lt;1|1].w;
	return ret;
}

inline int solve_subt(int u)//uninstall some software
{
	lx=dfn[u]; rx=dfn[u]+tsize[u]-1;
	int ans=query(1);
	val=0; update(1);
	return ans;
}

inline int solve_range(int u)//install new software
{
	int ret=0; val=1;
	while (topx[u]!=1)
	{
		lx=dfn[topx[u]]; rx=dfn[u];
		ret+=(depth[u]-depth[topx[u]]+1-query(1));
		update(1);
		u=anc[topx[u]];
	}
	lx=1; rx=dfn[u]; 
	ret+=(depth[u]-query(1));
	update(1);
	return ret;
}

int main()
{
	readx(nodenum);
	for (int i=2;i&lt;=nodenum;i++) { tx=i; readx(fx); fx++; Insert(); }
	
	Fancy(1,1,-1); Dreams(1,1);
	BuildTree(1,tstamp,1);
	
	int opt,ux; readx(opt);
	for (int i=1;i&lt;=opt;i++)
	{
		scanf("%s",chs); readx(ux); ux++;
		if (chs[0]=='u') printf("%d\n",solve_subt(ux));
		else printf("%d\n",solve_range(ux));
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<iterator>

#include<cstdlib>

#include<queue>

#include<vector>

using namespace std;

struct segment_tree { int l,r,w,tag; } SGT[400100]={0};

struct ed { int pre,to; } edge[200010]={0};

int nodenum,fx,tx,at=0,pointer[100010]={0};

int topx[100010]={0},hson[100010]={0},anc[100010]={0},tsize[100010]={0};

int depth[100010]={0},dfn[100010]={0},tstamp=0;

int lx,rx,val;

char chs[10]={0};

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline void Insert()

{

at++;

edge[at].pre=pointer[fx];

edge[at].to=tx;

pointer[fx]=at;

at++;

edge[at].pre=pointer[tx];

edge[at].to=fx;

pointer[tx]=at;

}

inline void Fancy(int nownode,int nowdep,int fa)

{

depth[nownode]=nowdep; anc[nownode]=fa; tsize[nownode]=1;

for (int prex=pointer[nownode];prex;prex=edge[prex].pre)

{

if (edge[prex].to!=fa)

{

Fancy(edge[prex].to,nowdep+1,nownode);

tsize[nownode]+=tsize[edge[prex].to];

if (tsize[hson[nownode]]<tsize[edge[prex].to]) hson[nownode]=edge[prex].to;

}

inline void Dreams(int nownode,int src)

{

topx[nownode]=src; dfn[nownode]=++tstamp;

if (hson[nownode]) Dreams(hson[nownode],src);

for (int prex=pointer[nownode];prex;prex=edge[prex].pre)

if (edge[prex].to!=anc[nownode] && edge[prex].to!=hson[nownode]) Dreams(edge[prex].to,edge[prex].to);

}

inline void BuildTree(int lxx,int rxx,int inx)

{

SGT[inx].l=lxx; SGT[inx].r=rxx;

if (lxx==rxx) return;

int mid=(lxx+rxx)>>1;

BuildTree(lxx,mid,inx<<1);

BuildTree(mid+1,rxx,inx<<1|1);

}

inline void pushdown(int inx)

{

SGT[inx<<1].tag=SGT[inx<<1|1].tag=SGT[inx].tag;

if (SGT[inx].tag==1) SGT[inx<<1].w=SGT[inx<<1|1].w=0;

if (SGT[inx].tag==2)

{

SGT[inx<<1].w=(SGT[inx<<1].r-SGT[inx<<1].l+1);

SGT[inx<<1|1].w=(SGT[inx<<1|1].r-SGT[inx<<1|1].l+1);

}

SGT[inx].tag=0;

}

inline void update(int inx)

{

if (SGT[inx].l>=lx && SGT[inx].r<=rx)

{

SGT[inx].w=val*(SGT[inx].r-SGT[inx].l+1);

SGT[inx].tag=val+1;

return;

}

if (SGT[inx].tag) pushdown(inx);

int mid=(SGT[inx].l+SGT[inx].r)>>1;

if (lx<=mid) update(inx<<1);

if (rx>mid) update(inx<<1|1);

SGT[inx].w=SGT[inx<<1].w+SGT[inx<<1|1].w;

}

inline int query(int inx)

{

if (SGT[inx].l>=lx && SGT[inx].r<=rx) return SGT[inx].w;

if (SGT[inx].tag) pushdown(inx);

int mid=(SGT[inx].l+SGT[inx].r)>>1,ret=0;

if (lx<=mid) ret+=query(inx<<1);

if (rx>mid) ret+=query(inx<<1|1);

SGT[inx].w=SGT[inx<<1].w+SGT[inx<<1|1].w;

return ret;

}

inline int solve_subt(int u)//uninstall some software

{

lx=dfn[u]; rx=dfn[u]+tsize[u]-1;

int ans=query(1);

val=0; update(1);

return ans;

}

inline int solve_range(int u)//install new software

{

int ret=0; val=1;

while (topx[u]!=1)

{

lx=dfn[topx[u]]; rx=dfn[u];

ret+=(depth[u]-depth[topx[u]]+1-query(1));

update(1);

u=anc[topx[u]];

}

lx=1; rx=dfn[u];

ret+=(depth[u]-query(1));

update(1);

return ret;

}

int main()

{

readx(nodenum);

for (int i=2;i<=nodenum;i++) { tx=i; readx(fx); fx++; Insert(); }

Fancy(1,1,-1); Dreams(1,1);

BuildTree(1,tstamp,1);

int opt,ux; readx(opt);

for (int i=1;i<=opt;i++)

{

scanf("%s",chs); readx(ux); ux++;

if (chs[0]=='u') printf("%d\n",solve_subt(ux));

else printf("%d\n",solve_range(ux));

}

return 0;

}

2018年4月2日2018年4月2日

BZOJ3158&3275 [双倍经验] Number|千钧一发

这俩是一个题。

拿「千钧一发」说吧，你会发现显然如果对于一个 $i$ ，如果 $a_i$ 是偶数的话，他一定满足条件 $2$ ，反过来如果 $a_i$ 是奇数的话，他一定满足条件 $1$ ，很好证明，就不说了。

然后你会发现这样一件事情：二分图

我们考虑补集转化，求最少的必须不选的 $b_i$ 们，这大概……就是一个最小割。

最小割。怎么建图？源点汇点分别连所有奇数/偶数，边权 $b_i$ ，然后奇偶之间互相连边，边权 $\rm{INF}$ 。

为什么是 $\rm{INF}$ ?

因为……呃……表示这条边一定不会被割掉，那我们假设他连接了 $u \; , \; v$ 两个结点，你需要挑一个，把他和源点或者汇点的边割掉。也就意味着最小割增加了 $b_u$ 或者 $b_v$ 的权，也就是不选其中一个。

然后这样就形成了超级复杂的关系网络~~然后就瞎跑Dinic就可以过了~~

注意！邻接表要开很大，而且两个题范围不一样！

~~（但是奇怪的是范围较大的 $\rm{Number}$ 却跑得快~~

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
#include&lt;cstdlib&gt;
#include&lt;queue&gt;
#include&lt;vector&gt;
#define ll long long
using namespace std;

struct ed { int capx,pre,to; }edge[2500010]={0};
int nodenum=0,at=1,pointer[2010]={0},fx,tx,cx,ss,tt;

int nodev[2010]={0},seq[2010]={0},n;
int codex[2010]={0};

queue&lt;int&gt; que;
int level[2010]={0},cache1; bool vis[2010]={0};
ll ans=0,ansb=0;

inline void readx(int&amp; x)
{
	x=0; int k=1; register char ch=0;
	while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}
inline void Insert()
{
	at++;
	edge[at].pre=pointer[fx];
	edge[at].to=tx;
	edge[at].capx=cx;
	pointer[fx]=at;
	at++;
	edge[at].pre=pointer[tx];
	edge[at].to=fx;
	pointer[tx]=at;
}

inline ll gcd(ll a,ll b)
{
	if (!b) return a;
	return gcd(b,a%b);
}
inline bool check(ll a,ll b)
{
	ll t=sqrt(a*a+b*b);
	if (t*t==a*a+b*b) return true;
	return false;
}

inline bool BFS()
{
	memset(vis,0,sizeof(vis)); memset(level,0,sizeof(level));
	level[ss]=1; vis[ss]=true; que.push(ss);
	while (!que.empty())
	{
		cache1=que.front(); que.pop();
		for (int prex=pointer[cache1];prex;prex=edge[prex].pre)
		{
			if (!vis[edge[prex].to] &amp;&amp; edge[prex].capx)
			{
				level[edge[prex].to]=level[cache1]+1;
				vis[edge[prex].to]=true; que.push(edge[prex].to);
			}
		}
	}
	return vis[tt];
}
inline int DFS(int nownode,int minf)
{
	if ((!minf) || nownode==tt) return minf;
	int sumf=0,needf=0;
	for (int prex=pointer[nownode];prex;prex=edge[prex].pre)
	{
		if (level[edge[prex].to]==level[nownode]+1)
		{
			if (needf=DFS(edge[prex].to,min(minf,edge[prex].capx)))
			{
				sumf+=needf; minf-=needf;
				edge[prex].capx-=needf; edge[prex^1].capx+=needf;
				if (!minf) break;
			}
		}
	}
	return sumf;
}

inline void init1()
{
	fx=ss;
	for (int i=1;i&lt;=n;i++) if (!(seq[i]%2))
	{
		nodenum++; codex[i]=nodenum;
		tx=nodenum; cx=nodev[i]; Insert();
	}
	tx=tt;
	for (int i=1;i&lt;=n;i++) if (seq[i]%2)
	{
		nodenum++; codex[i]=nodenum;
		fx=nodenum; cx=nodev[i]; Insert();
	}
}

int main()
{
	readx(n); ss=n+1; tt=n+2;
	for (int i=1;i&lt;=n;i++) readx(seq[i]);
	for (int i=1;i&lt;=n;i++) { readx(nodev[i]); ansb+=nodev[i]; }
	
	init1();
	
	cx=2*1e9;
	for (int i=1;i&lt;=n;i++) if (!(seq[i]%2))
	{
		fx=codex[i];
		for (int j=1;j&lt;=n;j++) if (seq[j]%2)
			if (check(seq[i],seq[j]) &amp;&amp; gcd(seq[i],seq[j])==1) { tx=codex[j]; Insert(); }
	}
	
	while (BFS()) ans+=DFS(ss,2*1e9);
	printf("%lld\n",ansb-ans);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<iterator>

#include<cstdlib>

#include<queue>

#include<vector>

#define ll long long

using namespace std;

struct ed { int capx,pre,to; }edge[2500010]={0};

int nodenum=0,at=1,pointer[2010]={0},fx,tx,cx,ss,tt;

int nodev[2010]={0},seq[2010]={0},n;

int codex[2010]={0};

queue<int> que;

int level[2010]={0},cache1; bool vis[2010]={0};

ll ans=0,ansb=0;

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline void Insert()

{

at++;

edge[at].pre=pointer[fx];

edge[at].to=tx;

edge[at].capx=cx;

pointer[fx]=at;

at++;

edge[at].pre=pointer[tx];

edge[at].to=fx;

pointer[tx]=at;

}

inline ll gcd(ll a,ll b)

{

if (!b) return a;

return gcd(b,a%b);

}

inline bool check(ll a,ll b)

{

ll t=sqrt(a*a+b*b);

if (t*t==a*a+b*b) return true;

return false;

}

inline bool BFS()

{

memset(vis,0,sizeof(vis)); memset(level,0,sizeof(level));

level[ss]=1; vis[ss]=true; que.push(ss);

while (!que.empty())

{

cache1=que.front(); que.pop();

for (int prex=pointer[cache1];prex;prex=edge[prex].pre)

{

if (!vis[edge[prex].to] && edge[prex].capx)

{

level[edge[prex].to]=level[cache1]+1;

vis[edge[prex].to]=true; que.push(edge[prex].to);

}

return vis[tt];

}

inline int DFS(int nownode,int minf)

{

if ((!minf) || nownode==tt) return minf;

int sumf=0,needf=0;

for (int prex=pointer[nownode];prex;prex=edge[prex].pre)

{

if (level[edge[prex].to]==level[nownode]+1)

{

if (needf=DFS(edge[prex].to,min(minf,edge[prex].capx)))

{

sumf+=needf; minf-=needf;

edge[prex].capx-=needf; edge[prex^1].capx+=needf;

if (!minf) break;

}

return sumf;

}

inline void init1()

{

fx=ss;

for (int i=1;i<=n;i++) if (!(seq[i]%2))

{

nodenum++; codex[i]=nodenum;

tx=nodenum; cx=nodev[i]; Insert();

}

tx=tt;

for (int i=1;i<=n;i++) if (seq[i]%2)

{

nodenum++; codex[i]=nodenum;

fx=nodenum; cx=nodev[i]; Insert();

}

int main()

{

readx(n); ss=n+1; tt=n+2;

for (int i=1;i<=n;i++) readx(seq[i]);

for (int i=1;i<=n;i++) { readx(nodev[i]); ansb+=nodev[i]; }

init1();

cx=2*1e9;

for (int i=1;i<=n;i++) if (!(seq[i]%2))

{

fx=codex[i];

for (int j=1;j<=n;j++) if (seq[j]%2)

if (check(seq[i],seq[j]) && gcd(seq[i],seq[j])==1) { tx=codex[j]; Insert(); }

}

while (BFS()) ans+=DFS(ss,2*1e9);

printf("%lld\n",ansb-ans);

return 0;

}

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
#include&lt;cstdlib&gt;
#include&lt;queue&gt;
#include&lt;vector&gt;
#define ll long long
using namespace std;

struct ed { int capx,pre,to; }edge[4300010]={0};
int nodenum=0,at=1,pointer[6010]={0},fx,tx,cx,ss,tt;

int nodev[6010]={0},n;
int codex[6010]={0};

queue&lt;int&gt; que;
int level[6010]={0},cache1; bool vis[6010]={0};
ll ans=0,ansb=0;

inline void readx(int&amp; x)
{
	x=0; int k=1; register char ch=0;
	while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}
inline void Insert()
{
	at++;
	edge[at].pre=pointer[fx];
	edge[at].to=tx;
	edge[at].capx=cx;
	pointer[fx]=at;
	at++;
	edge[at].pre=pointer[tx];
	edge[at].to=fx;
	pointer[tx]=at;
}

inline ll gcd(ll a,ll b)
{
	if (!b) return a;
	return gcd(b,a%b);
}
inline bool check(ll a,ll b)
{
	ll t=sqrt(a*a+b*b);
	if (t*t==a*a+b*b) return true;
	return false;
}

inline bool BFS()
{
	memset(vis,0,sizeof(vis)); memset(level,0,sizeof(level));
	level[ss]=1; vis[ss]=true; que.push(ss);
	while (!que.empty())
	{
		cache1=que.front(); que.pop();
		for (int prex=pointer[cache1];prex;prex=edge[prex].pre)
		{
			if (!vis[edge[prex].to] &amp;&amp; edge[prex].capx)
			{
				level[edge[prex].to]=level[cache1]+1;
				vis[edge[prex].to]=true; que.push(edge[prex].to);
			}
		}
	}
	return vis[tt];
}
inline int DFS(int nownode,int minf)
{
	if ((!minf) || nownode==tt) return minf;
	int sumf=0,needf=0;
	for (int prex=pointer[nownode];prex;prex=edge[prex].pre)
	{
		if (level[edge[prex].to]==level[nownode]+1)
		{
			if (needf=DFS(edge[prex].to,min(minf,edge[prex].capx)))
			{
				sumf+=needf; minf-=needf;
				edge[prex].capx-=needf; edge[prex^1].capx+=needf;
				if (!minf) break;
			}
		}
	}
	return sumf;
}

inline void init1()
{
	fx=ss;
	for (int i=1;i&lt;=n;i++) if (!(nodev[i]%2))
	{
		nodenum++; codex[i]=nodenum;
		tx=nodenum; cx=nodev[i]; Insert();
	}
	tx=tt;
	for (int i=1;i&lt;=n;i++) if (nodev[i]%2)
	{
		nodenum++; codex[i]=nodenum;
		fx=nodenum; cx=nodev[i]; Insert();
	}
}

int main()
{
	readx(n); ss=n+1; tt=n+2;
	for (int i=1;i&lt;=n;i++) { readx(nodev[i]); ansb+=nodev[i]; }
	
	init1();
	
	cx=2*1e9;
	for (int i=1;i&lt;=n;i++) if (!(nodev[i]%2))
	{
		fx=codex[i];
		for (int j=1;j&lt;=n;j++) if (nodev[j]%2)
			if (check(nodev[i],nodev[j]) &amp;&amp; gcd(nodev[i],nodev[j])==1) { tx=codex[j]; Insert(); }
	}
	
	while (BFS()) ans+=DFS(ss,2*1e9);
	printf("%lld\n",ansb-ans);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<iterator>

#include<cstdlib>

#include<queue>

#include<vector>

#define ll long long

using namespace std;

struct ed { int capx,pre,to; }edge[4300010]={0};

int nodenum=0,at=1,pointer[6010]={0},fx,tx,cx,ss,tt;

int nodev[6010]={0},n;

int codex[6010]={0};

queue<int> que;

int level[6010]={0},cache1; bool vis[6010]={0};

ll ans=0,ansb=0;

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline void Insert()

{

at++;

edge[at].pre=pointer[fx];

edge[at].to=tx;

edge[at].capx=cx;

pointer[fx]=at;

at++;

edge[at].pre=pointer[tx];

edge[at].to=fx;

pointer[tx]=at;

}

inline ll gcd(ll a,ll b)

{

if (!b) return a;

return gcd(b,a%b);

}

inline bool check(ll a,ll b)

{

ll t=sqrt(a*a+b*b);

if (t*t==a*a+b*b) return true;

return false;

}

inline bool BFS()

{

memset(vis,0,sizeof(vis)); memset(level,0,sizeof(level));

level[ss]=1; vis[ss]=true; que.push(ss);

while (!que.empty())

{

cache1=que.front(); que.pop();

for (int prex=pointer[cache1];prex;prex=edge[prex].pre)

{

if (!vis[edge[prex].to] && edge[prex].capx)

{

level[edge[prex].to]=level[cache1]+1;

vis[edge[prex].to]=true; que.push(edge[prex].to);

}

return vis[tt];

}

inline int DFS(int nownode,int minf)

{

if ((!minf) || nownode==tt) return minf;

int sumf=0,needf=0;

for (int prex=pointer[nownode];prex;prex=edge[prex].pre)

{

if (level[edge[prex].to]==level[nownode]+1)

{

if (needf=DFS(edge[prex].to,min(minf,edge[prex].capx)))

{

sumf+=needf; minf-=needf;

edge[prex].capx-=needf; edge[prex^1].capx+=needf;

if (!minf) break;

}

return sumf;

}

inline void init1()

{

fx=ss;

for (int i=1;i<=n;i++) if (!(nodev[i]%2))

{

nodenum++; codex[i]=nodenum;

tx=nodenum; cx=nodev[i]; Insert();

}

tx=tt;

for (int i=1;i<=n;i++) if (nodev[i]%2)

{

nodenum++; codex[i]=nodenum;

fx=nodenum; cx=nodev[i]; Insert();

}

int main()

{

readx(n); ss=n+1; tt=n+2;

for (int i=1;i<=n;i++) { readx(nodev[i]); ansb+=nodev[i]; }

init1();

cx=2*1e9;

for (int i=1;i<=n;i++) if (!(nodev[i]%2))

{

fx=codex[i];

for (int j=1;j<=n;j++) if (nodev[j]%2)

if (check(nodev[i],nodev[j]) && gcd(nodev[i],nodev[j])==1) { tx=codex[j]; Insert(); }

}

while (BFS()) ans+=DFS(ss,2*1e9);

printf("%lld\n",ansb-ans);

return 0;

}

2018年4月2日

BZOJ1016 | JSOI2008 最小生成树计数

题面不放

这是道好题一开始还以为是 $\rm{Matrix Tree}$ 定理，后来发现不是QAQ

其实暴搜可过

先一遍Kruskal，顺便把权值相等的边们分到一个块里面，随便怎么实现都行记录一下每个块有多少边在MST中出现过

然后重置一下并查集，枚举块，每个块跑DFS选哪些边（注意连通性，如果这条边加入成环就不能选，这很显然qwq），答案是所有块的方案数的乘积。

这里用了一个性质就是不同的MST中边权相等的边出现次数相等，证明？

开始时，每个点单独构成一个集合。

首先只考虑权值最小的边，将它们全部添加进图中，并去掉环，由于是全部尝试添加，那么只要是用这种权值的边能够连通的点，最终就一定能在一个集合中。

那么不管添加的是哪些边，最终形成的集合数都是一定的，且集合的划分情况一定相同。那么真正添加的边数也是相同的。因为每添加一条边集合的数目便减少1.

那么权值第二小的边呢？我们将之间得到的集合每个集合都缩为一个点，那么权值第二小的边就变成了当前权值最小的边，也有上述的结论。

因此每个阶段，添加的边数都是相同的。我们以权值划分阶段，那么也就意味着某种权值的边的数目是完全相同的。

上文不是我写的。引用一下。

然后就能愉快的切掉这个水题。

哦，还有，这段代码BZOJ编译会CE，不知道为什么她就是不支持C++11 [摊手]

#include&lt;cstdio&gt;
#include&lt;iostream&gt;
#include&lt;cstring&gt;
#include&lt;string&gt;
#include&lt;cmath&gt;
#include&lt;algorithm&gt;
#include&lt;iterator&gt;
#include&lt;cstdlib&gt;
#include&lt;queue&gt;
#include&lt;vector&gt;
#define mo 31011
#define ll long long
using namespace std;

struct ed { int fr,to,w; }edge[100010]={0};
struct gr { int w,cnt; } gro[100010]={0};
struct blocks { int lx,rx,num; } blk[100010]={0};
int nodenum,edgenum,mstnum=0,blkm=0,nblk,ans=1,ansx;
int fa[100010]={0};

inline void readx(int&amp; x)
{
	x=0; int k=1; register char ch=0;
	while (ch&lt;'0' || ch&gt;'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch&gt;='0' &amp;&amp; ch&lt;='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline int findx(int e) { if (fa[e]!=e) return findx(fa[e]); return fa[e]; }

inline void dfs(int npos,int used)
{
	if (npos==blk[nblk].rx+1)
	{
		if (used==blk[nblk].num) ansx++;
		return;
	}
	int u=findx(edge[npos].fr),v=findx(edge[npos].to);
	if (u!=v)
	{
		fa[u]=v;
		dfs(npos+1,used+1);
		fa[u]=u; fa[v]=v;
	}
	dfs(npos+1,used);
}

int main()
{
	readx(nodenum); readx(edgenum);
	for (int i=1;i&lt;=edgenum;i++) { readx(edge[i].fr); readx(edge[i].to); readx(edge[i].w); }
	for (int i=1;i&lt;=nodenum;i++) fa[i]=i;
	sort(edge+1,edge+edgenum+1,[](ed a,ed b){return a.w&lt;b.w;});
	
	for (int i=1;i&lt;=edgenum;i++)
	{
		if (edge[i].w!=edge[i-1].w) { blk[blkm].rx=i-1; blk[++blkm].lx=i; }
		if (findx(edge[i].fr)!=findx(edge[i].to))
		{
			fa[findx(edge[i].fr)]=findx(edge[i].to); mstnum++;
			blk[blkm].num++;
		}
	}
	if (mstnum&lt;nodenum-1) { printf("0\n"); return 0; }
	
	blk[blkm].rx=edgenum;
	for (int i=1;i&lt;=nodenum;i++) fa[i]=i;
	
	for (int i=1;i&lt;=blkm;i++)
	{
		nblk=i; ansx=0;
		dfs(blk[i].lx,0); ans=(ans*ansx)%mo;
		for (int j=blk[i].lx;j&lt;=blk[i].rx;j++) if (findx(edge[j].fr)!=findx(edge[j].to)) 
			fa[findx(edge[j].fr)]=findx(edge[j].to);
	}
	printf("%d\n",ans);
	return 0;
}

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<iterator>

#include<cstdlib>

#include<queue>

#include<vector>

#define mo 31011

#define ll long long

using namespace std;

struct ed { int fr,to,w; }edge[100010]={0};

struct gr { int w,cnt; } gro[100010]={0};

struct blocks { int lx,rx,num; } blk[100010]={0};

int nodenum,edgenum,mstnum=0,blkm=0,nblk,ans=1,ansx;

int fa[100010]={0};

inline void readx(int& x)

{

x=0; int k=1; register char ch=0;

while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }

while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

x*=k;

}

inline int findx(int e) { if (fa[e]!=e) return findx(fa[e]); return fa[e]; }

inline void dfs(int npos,int used)

{

if (npos==blk[nblk].rx+1)

{

if (used==blk[nblk].num) ansx++;

return;

}

int u=findx(edge[npos].fr),v=findx(edge[npos].to);

if (u!=v)

{

fa[u]=v;

dfs(npos+1,used+1);

fa[u]=u; fa[v]=v;

}

dfs(npos+1,used);

}

int main()

{

readx(nodenum); readx(edgenum);

for (int i=1;i<=edgenum;i++) { readx(edge[i].fr); readx(edge[i].to); readx(edge[i].w); }

for (int i=1;i<=nodenum;i++) fa[i]=i;

sort(edge+1,edge+edgenum+1,[](ed a,ed b){return a.w<b.w;});

for (int i=1;i<=edgenum;i++)

{

if (edge[i].w!=edge[i-1].w) { blk[blkm].rx=i-1; blk[++blkm].lx=i; }

if (findx(edge[i].fr)!=findx(edge[i].to))

{

fa[findx(edge[i].fr)]=findx(edge[i].to); mstnum++;

blk[blkm].num++;

}

if (mstnum<nodenum-1) { printf("0\n"); return 0; }

blk[blkm].rx=edgenum;

for (int i=1;i<=nodenum;i++) fa[i]=i;

for (int i=1;i<=blkm;i++)

{

nblk=i; ansx=0;

dfs(blk[i].lx,0); ans=(ans*ansx)%mo;

for (int j=blk[i].lx;j<=blk[i].rx;j++) if (findx(edge[j].fr)!=findx(edge[j].to))

fa[findx(edge[j].fr)]=findx(edge[j].to);

}

printf("%d\n",ans);

return 0;

}