uoj14 DZY Loves Graph

看起来很有趣的样子。。

Solution

如果没有恢复操作，那么插入和删除的总量是 $O(m)$ 的，所以可以暴力删边。只会删除大边，不会删除小边，所以不存在断开需要重新链接的情况。用一个栈实现就行。

MD撤销指的是撤销前一次操作qwq。。'

折样的话，把操作离线，就可以知道下一个操作是不是return。如果是的话特殊处理一下就好了。。

Code

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	bool isValid(char ch) {
		return ch!='\r' && ch!='\n' && ch!=' ' && ch!=EOF;
	}
	Istream &operator >>(char &ch) {
		while(!isValid(ch=getchar()));
		return *this;
	}
	Istream &operator >>(char *s) {
		while(!isValid(*s=getchar()));
		while(isValid(*++s=getchar()));
		*s=0;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
const int MAXN=3e5+11,MAXQ=5e5+11;
struct OffQ {
	int opt,a,b,k;
}p[MAXQ];
int dsu[MAXN],size[MAXN];
int Root(int x) {
	return dsu[x]?Root(dsu[x]):x;
}
int Merge(int x,int y) {
	if(size[x]<size[y]) {
		std::swap(x,y);
	}
	dsu[y]=x;
	size[x]+=size[y];
	return y;
}
void CutOff(int x) {
	size[dsu[x]]-=size[x];
	dsu[x]=0;
}
int main() {
	int n,Q;is>>n>>Q;
	for(int i=1;i<=Q;++i) {
		OffQ &o=p[i];
		char opt[20];
		is>>opt;
		switch(opt[0]) {
			case 'A': {
				o.opt=1;
				is>>o.a>>o.b;
			} break;
			case 'D': {
				o.opt=2;
				is>>o.k;
			} break;
			case 'R': {
				o.opt=3;
			}
		}
	}
	for(int i=1;i<=n;size[i++]=1);
	static int stack[MAXQ],top,opu[MAXQ],cnt[MAXQ];
	static int64 weight[MAXQ];
	for(int i=1;i<=Q;++i) {
		OffQ &o=p[i];
		switch(o.opt) {
			case 1: {
				stack[++top]=i;
				opu[i]=Root(o.a)==Root(o.b)
					?(cnt[top]=cnt[top-1],weight[top]=weight[top-1],0)
					:(cnt[top]=cnt[top-1]+1,weight[top]=weight[top-1]+i,Merge(Root(o.a),Root(o.b)));
				os<<(cnt[top]==n-1?weight[top]:0)<<'\n';
				if(p[i+1].opt==3) {
					if(opu[stack[top]]) {
						CutOff(opu[stack[top]]);
					}
					top--;
					os<<(cnt[top]==n-1?weight[top]:0)<<'\n';
					++i;
				}
			} break;
			case 2: {
				if(p[i+1].opt!=3) {
					for(int rep=1;rep<=o.k;++rep) {
						if(opu[stack[top]]) {
							CutOff(opu[stack[top]]);
						}
						top--;
					}
					os<<(cnt[top]==n-1?weight[top]:0)<<'\n';
				} else {
					os<<(cnt[top-o.k]==n-1?weight[top-o.k]:0)<<'\n'<<(cnt[top]==n-1?weight[top]:0)<<'\n';
					++i;
				}
			} break;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
#include <ext/rope>
#define ext __gnu_cxx
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	bool isValid(char ch) {
		return ch!='\r' && ch!='\n' && ch!=' ' && ch!=EOF;
	}
	Istream &operator >>(char &ch) {
		while(!isValid(ch=getchar()));
		return *this;
	}
	Istream &operator >>(char *s) {
		while(!isValid(*s=getchar()));
		while(isValid(*++s=getchar()));
		*s=0;
		return *this;
	}
}is;struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
const int MAXN=3e5+11,MAXQ=5e5+11,MAXLOGQ=20;
int n;
struct State {
	ext::rope<int> dsu,size;
	int64 weight;int cnt,par[MAXLOGQ];
	State& operator =(State const &other) {
		new(&dsu) ext::rope<int>(other.dsu);
		new(&size) ext::rope<int>(other.size);
		weight=other.weight;
		cnt=other.cnt;
		for(int i=0;i<=19;par[i]=other.par[i],++i);
		return *this;
	}
	int Root(int x) {
		return dsu[x]?Root(dsu[x]):x;
	}
	void AddEdge(int x,int y,int c) {
		x=Root(x),y=Root(y);
		if(x!=y) {
			weight+=c;
			cnt++;
			if(size[x]<size[y]) {
				std::swap(x,y);
			}
			dsu.replace(y,x);
			size.replace(x,size[x]+size[y]);
		}
	}
	void Show() {
		os<<(cnt==n-1?weight:0)<<'\n';
	}
}state[MAXQ];
int Jump(int x,int k) {
	for(int lg=19;~lg;--lg) {
		if(k>>lg&1) {
			x=state[x].par[lg];
		}
	}
	return x;
}
int main() {
	int Q;is>>n>>Q;
	static int temp[MAXN];
	state[0].weight=state[0].cnt=0;
	new(&state[0].dsu) ext::rope<int>(temp,temp+1+n);
	for(int i=1;i<=n;temp[i++]=1);
	new(&state[0].size) ext::rope<int>(temp,temp+1+n);
	int lastAdd=0;
	for(int i=1;i<=Q;++i) {
		char opt[20];
		is>>opt;
		switch(opt[0]) {
			case 'A': {
				state[i]=state[i-1];
				int x,y;is>>x>>y;
				state[i].AddEdge(x,y,i);
				state[i].par[0]=lastAdd;
				for(int lg=1;lg<=19;++lg) {
					state[i].par[lg]=state[state[i].par[lg-1]].par[lg-1];
				}
				lastAdd=i;
			} break;
			case 'D': {
				int k;is>>k;
				state[i]=state[lastAdd=Jump(i-1,k)];
			} break;
			case 'R': {
				state[i]=state[i-2];
			} break;
		}
		state[i].Show();
	}
	return 0;
}

可持久化的做法，MLE自不必说，居然还有WA？但是不想调了。。

uoj21 缩进优化

答案居然不是单峰的qwq

但是对于所有/ts不变的块内的最小值是单峰的，答案肯定在那里面。

~~于是我会了一种 $O(n\sqrt a)$ 的做法。。MDZZ~~

Solution

整除不禁让人想起了经典的数论分块。。

要分块就要想办法把这个mod消掉

只要对 $a_i$ 的个数搞一个前缀和就可以得到 $70$ 分啦！！

然后呢？

为什么要枚举 $a_i$ 呢？枚举 $[\frac {a_i}x]$ 啊！然后就AC了。

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
template <class T> inline
bool Relax(T &a,T const &b) {
	return a<b?a=b,1:0;
}
const int MAXN=1e6+11;
int main() {
	static int a[MAXN],cnt[MAXN];
	int n;is>>n;
	int64 sum=0;
	int maxA=0;
	for(int i=1;i<=n;++i) {
		is>>a[i];
		++cnt[a[i]];
		sum+=a[i];
		Relax(maxA,a[i]);
	}
	for(int i=1;i<=maxA;cnt[i]+=cnt[i-1],++i);
	int64 maxs=0;
	for(int ts=2;ts<=maxA;++ts) {
		int64 temp=0;
		for(int dv=1;dv*ts<=maxA;++dv) {
			temp+=(int64)(cnt[std::min(maxA,dv*ts+ts-1)]-cnt[dv*ts-1])*dv;
		}
		Relax(maxs,temp*=(ts-1));
	}
	int64 Ans=sum-maxs;
	os<<Ans<<'\n';
	return 0;
}

uoj22 外星人

在模的过程中，值一定是越来越小的，绝对值越来越大。
然后我想想？
大的永远不会影响，可以用组合数计算

Solution

先想如何求最大值？？

一个点后面所有比它大的值都不会影响答案。

一个有效的操作序列是一个下降序列。

相当于排完序求一个子序列，膜完剩下最大。然后随便DP，就有36分。

依然延续求第一问的思路，现在考虑如何求出方案数。

其实都是一样的，也就是分两种情况讨论一下：废掉这个，还是用掉这个。

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
const int MAXN=1e3+11,MAXA=5e3+11,P=(7*17<<23)+1;
int main() {
	int n=is,x=is;
	static int a[MAXN];
	for(int i=1;i<=n;is>>a[i++]);
	std::sort(a+1,a+1+n,std::greater<int>());
	static int64 f[MAXN][MAXA];
	f[0][x]=1;
	for(int i=1;i<=n;++i) {
		for(int v=0;v<=x;++v) {
			(f[i][v%a[i]]+=f[i-1][v])%=P;
			(f[i][v]+=f[i-1][v]*(n-i)%P)%=P;
		}
	}
	int mxv=x;
	for(;!f[n][mxv];mxv--);
	os<<mxv<<' '<<f[n][mxv]<<'\n';
	return 0;
}

弄明白之后才感觉自己真SB。

跳蚤国王下江南

毒瘤啊。。

uoj31 猪猪侠再战括号序列

直接暴力构造应该就有50分吧。。

并不是。。暴力构造可能会有 $2n$ 步。。zz.

最多只需要转 $n$ 下。

用Splay维护就A了？2333

~~可以看成一次操作需要成全一对我忽略了什么？为什么毫无思路？？？？？？~~

def fuck():
	print "Fuck You"
while 1:
	fuck()

Solution

正解的思路，和暴力构造是一个意思。

只是找左括号的时候要找右边第一个。

你猜怎么着？中间都是右括号，根本不会变，翻转变成 $O(1)$ 的了！！！

而左括号的位置是有单调性的！！！

Tips

错误的估计了暴力的正确性qwq 否则应该还是能想出来的

Code

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
	bool isValid(char ch) {
		return ch!='\r' && ch!='\n' && ch!=' ' && ch!=EOF;
	}
	Istream &operator >>(char *s) {
		while(!isValid(*s=getchar()));
		while(isValid(*++s=getchar()));
		*s=0;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
const int MAXN=1e5+11;
template <class T> inline
bool Relax(T &a,T const &b) {
	return a<b?a=b,1:0;
}
int main() {
	static char s[MAXN<<1];
	is>>(s+1);
	int n=strlen(s+1)/2;
	std::vector<std::pair<int,int> > Ans;
	for(int i=1,pt=1,sum=0;i<=n*2;++i) {
		if((sum+=s[i]=='('?1:-1)<0) {
			for(Relax(pt,i+1);s[pt]!='(';++pt);
			Ans.push_back(std::pair<int,int>(i,pt));
			std::swap(s[i],s[pt]);
			sum+=2;
		}
	}
	os<<Ans.size()<<'\n';
	for(size_t i=0;i<Ans.size();++i) {
		os<<Ans[i].first<<' '<<Ans[i].second<<'\n';
	}
	return 0;
}

uoj32 跳蚤公路

先SCC一下。求出每个SCC的最大最小值一个点的答案就是从1能到、且能到v的scc中去一个交集还是二分吗折样的话这一部分总复杂度是 $O(nm\log x)$ 的然后就能搞了？？没法直接二分啊XD 应该可以二分。。但是会很麻烦啊qwq ~~## Tips 发现满足可二分性质的东西，看看是否可以列成一个可以解的式子，由判定转为求值为什么不会分成两段？？？？~~

Solution

真是一道好题。。。。。

写一个详细的Solution吧。。。

开始口胡

首先题意中的挣钱道路就是负权回路。判断一张图有没有负权回路是“经典问题”，可以用Bellman-Ford来做。再想想，不存在负权回路的应该是数轴上一段连续的区间，所以满足可二分性。至于怎么二分？先代入一下最大值，再代入一下最小值，如果是负的就二分找正的，否则二分找负的。

直接做复杂度是 $O(n^2m\log 10^{31})$ 的，显然不科学。

考虑一点性质：一个SCC里面，所有点不存在负权回路的上下界都应该相同。所以可以对每个SCC单独搞，计算答案的时候，找出所有能到达的SCC把上下界取交集即可。。最后应该能 $O(nm\log {10^{31}})$ 了吧。。。

这个应该能做啊。。但我想出来之后去看题解发现这个似乎不科学？？？

口胡结束

于是学习了一番std

判断是否有负权回路，经典做法是Bellman-Ford。在第 $n$ 次松弛如果依然有被松弛的说明它就在一个含有负权回路的路径上。

而现在还存在这一个系数 $k\in [-n,n]$ ，那就设 $f[s][k][p]$ 表示走了 $s$ 步，系数为 $k$ ，到了点 $p$ 的最短路，转移显然。

最后要满足的条件，是 $\forall p\ \min\{kx+f[n][k][p]\}\ge \min\{hx+f[n][h][p]\}$

这个条件怎么解呢？

首先显然不同的 $p$ 是独立的，那就固定 $p$ ，然后，再固定一维 $k$ 。 $p$ 可行区间就是对每个 $k$ 解出来 $kx+f[n][k][p]\ge \min\{hx+f[n][h][p]\}$ 最后把范围取个交集。

最后考虑这个怎么解 $kx+f[n][k][p]\ge hx+f[n][h][p]$ 。其实就是对每个 $h$ 解出来把范围取个并集。

先并集后交集这个很难搞，那就转化成对补集先交集再并集。补集的并集也没什么好办法，用vector存下来就行了。

最后计算答案，就枚举一下所有从1能到，而且能到 $p$ 的点 $u$ ，把 $u$ 的那些补集都插入到一个vector。最后把这些补集取个并集，再补集一下就是答案。这个部分就简单多了：因为众所周知最后的答案一定是一个连续的区间，那么补集之多只会出现一段的空缺。找出这一段，就是最后的答案了。

Code

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
const int MAXN=1e2+11,MAXM=1e4+11;
const int64 INF=0x1f1f1f1f1f1f1f1f;
template <class T> inline bool Tension(T &a,T const &b) { return a>b?a=b,1:0; }
template <class T> inline bool Relax(T &a,T const &b) { return a<b?a=b,1:0; }
int64 Floor(int64 const &a,int64 const &b) { return a/b-((a>0)!=(b>0)); }
int64 Ceil(int64 const &a,int64 const &b) { return a/b+((a>0)==(b>0)); }
int main() {
	static bool con[MAXN][MAXN];
	static struct Edge { int x,y,w,k; }edges[MAXM];
	int n=is,m=is;
	for(int i=1;i<=m;++i) {
		Edge &e=edges[i];
		is>>e.x>>e.y>>e.w>>e.k;
		con[e.x][e.y]=1;
	}
	for(int i=1;i<=n;con[i][i]=1,++i);
	for(int k=1;k<=n;++k) {
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=n;++j) {
				con[i][j]|=con[i][k] & con[k][j];
			}
		}
	}

	static int64 f[MAXN][MAXN<<1][MAXN];//走几步 系数是多少 停在哪里 最短路
	memset(f[0],31,sizeof(f[0]));
#define MG(i) ((i)+n)
	f[0][MG(0)][1]=0;
	for(int st=0;st<=n-1;++st) {
		memcpy(f[st+1],f[st],sizeof(f[st]));
		for(int k=-st;k<=st;++k) {
			for(int i=1;i<=m;++i) {
				Edge &e=edges[i];
				f[st][MG(k)][e.x]!=INF && Tension(f[st+1][MG(k)+e.k][e.y],f[st][MG(k)][e.x]+e.w);
			}
		}
	}
	static std::vector<std::pair<int64,int64> > isci[MAXN];
	for(int pos=1;pos<=n;++pos) {
		int64 kv,hv;
		for(int k=-n;k<=n;++k) if((kv=f[n][MG(k)][pos])!=INF) {
			int64 l=-INF,r=INF;
			for(int h=-n;h<=n;++h) if((hv=f[n-1][MG(h)][pos])!=INF) {
				if(k>h) {
					Tension(r,(hv-kv)%(k-h)==0?(hv-kv)/(k-h)-1:Floor(hv-kv,k-h));
				} else if(k<h) {
					Relax(l,(hv-kv)%(k-h)==0?(hv-kv)/(k-h)+1:Ceil(hv-kv,k-h));
				} else if(kv>=hv) {
					l=INF;
					r=-INF;
					break;
				}
			}
			if(l<=r) {
				isci[pos].push_back(std::pair<int64,int64>(l,r));
			}
		}
	}
	for(int pos=1;pos<=n;++pos) {
		std::vector<std::pair<int64,int64> > isc;
		for(int u=1;u<=n;++u) if(con[1][u] && con[u][pos]) {
			std::copy(isci[u].begin(),isci[u].end(),std::back_inserter(isc));
		}
		std::sort(isc.begin(),isc.end());
		int64 l=INF,r=-INF;
		if(isc.empty()) {
			l=-INF,r=INF;
		} else if(isc.front().first!=-INF) {
			l=-INF;r=isc.front().first-1;
		} else {
			int64 cm=-INF;bool found=0;
			for(size_t i=0;i<isc.size();++i) {
				if(isc[i].first>cm+1) {
					l=cm+1;
					r=isc[i].first-1;
					found=1;
					break;
				}
				Relax(cm,isc[i].second);
			}
			if(!found && cm!=INF) {
				l=cm+1;
				r=INF;
			}
		}
		if(l>r) {
			os<<0<<'\n';
		} else {
			os<<(l==-INF || r==INF?-1:r-l+1)<<'\n';
		}
	}
	return 0;
}

uoj33 树上gcd

看着就好神啊。。。。。

直接点分治？？分个头。。

怎么做怎么做？？？？？？？？？？

Solution

官方题解给了两种做法, $O(n\sqrt n)$ 和 $O(n\sqrt n\log n)$

$O(n\sqrt n\log n)$

这种做法复杂度不优秀但是比较好写，也比较神奇。

要求 $\gcd(d_u,d_v)=x$ 的数目，可以转化成 $x|d_u,x|d_v$ 的数目，最后反演一下就好了！！！（蒟蒻觉得很腻害！）

首先在一条链上的比较好做。。这一部分不用反演。一个点对答案的贡献是区间+1，这样用差分实现，最后一遍前缀和就行了。

剩下的部分，也就是不是直上直下的点对，咋做？

对于 $d\le \sqrt n$ ，大力dp

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
const int MAXN=2e5+11;
const int SB=10;
#define int64 long long
std::vector<int> son[MAXN],h[MAXN];
int64 Ans[MAXN];
int dep[MAXN],fa[MAXN],f[MAXN][SB+1],g[MAXN][SB+1];
void DFS(int pos) {
	static int stack[MAXN],top;
	stack[++top]=pos;
	for(int u : son[pos]) {
		DFS(u);
	}
	if(pos!=1) {
		//f 正好的 g 差1的
		for(int d=1;d<=SB;++d) {//必须要算满SB 因为还有下面的！！见2、3行
			g[stack[std::max(top-d+1,0)]][d]+=f[pos][d]+1;
			Ans[d]+=(int64)f[fa[pos]][d]*g[pos][d];
			f[fa[pos]][d]+=g[pos][d];
		}
		h[pos].push_back(1);
		if(h[fa[pos]].size()<h[pos].size()) {
			std::swap(h[fa[pos]],h[pos]);
		}
		std::vector<int> &a=h[fa[pos]],&b=h[pos];
		int sizeA=a.size(),sizeB=b.size();
		if(sizeA>SB && sizeB>SB) {
			for(int d=SB+1;d<=sizeB;++d) {
				int sumA=0;
				for(int len=d;len<=sizeA;sumA+=a[sizeA-len],len+=d);
				int sumB=0;
				for(int len=d;len<=sizeB;sumB+=b[sizeB-len],len+=d);
				Ans[d]+=(int64)sumA*sumB;
			}
		}
		for(int d=1;d<=sizeB;a[sizeA-d]+=b[sizeB-d],++d);
		b.clear();
	}
	top--;
}
int main() {
	int n=is;
	static int64 cnt[MAXN];
	for(int i=2;i<=n;++i) {
		dep[i]=dep[fa[i]=is]+1;
		++cnt[1];--cnt[dep[i]+1];
		son[fa[i]].push_back(i);
	}
	for(int i=1;i<=n-1;cnt[i]+=cnt[i-1],++i);
	DFS(1);
	for(int i=n-1;i>=1;--i) {
		for(int j=i*2;j<=n-1;j+=i) {
			Ans[i]-=Ans[j];
		}
	}
	for(int i=1;i<=n-1;++i) {
		Ans[i]+=cnt[i];
		os<<Ans[i]<<'\n';
	}
	return 0;
}

uoj48 核聚变反应强度

大水题啊。。不写了。。

uoj49 铀仓库

可以三分套二分吧。。 $O(n\log^2n)$

不需要三分时间，只需要二分距离！

MD各种爆int爆ll被卡晕了

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
const int MAXN=5e5+11;
int n,a[MAXN],x[MAXN];
long long tlim,pref_sum[MAXN];
bool check(long long cnt) {
	if(cnt==a[0]) {
		return 1;
	} else {
		static int chs[MAXN];
		std::fill(chs+1,chs+1+n,0);
		int l=1,r=1;chs[1]=a[1];long double tuse=0;
		for(long long sum=a[1];sum<cnt;) {
			++r;
			chs[r]=sum+a[r]<=cnt?a[r]:cnt-sum;
			sum+=chs[r];
			tuse+=(long double)(chs[r])*(x[r]-x[1]);
		}
		if(2*tuse<=tlim) return 1;
		for(int i=2;i<=n;++i) {
			tuse+=(long double)(x[i]-x[i-1])*((pref_sum[i-1]-pref_sum[l]+chs[l])-(pref_sum[r-1]-pref_sum[i-1]+chs[r]));
			while(x[i]-x[l]>x[r]-x[i]) {
				int d=std::min(a[r]-chs[r],chs[l]);
				tuse+=(long double)(d)*(x[l]+x[r]-2*x[i]);
				(chs[l]-=d)==0 && ++l;
				(chs[r]+=d)==a[r] && ++r;
			}
			if(2*tuse<=tlim) return 1;
		}
		return 0;
	}
}
int main() {
	is>>n>>tlim;
	for(int i=1;i<=n;is>>x[i++]);
	x[n+1]=2e9+1e8;
	for(int i=1;i<=n;pref_sum[i]=pref_sum[i-1]+(a[i]=is),++i);
	long long L=a[0]=*std::max_element(a+1,a+1+n),R=pref_sum[n];
	while(L!=R) {
		long long M=(L+R+1)>>1;
		check(M)?L=M:R=M-1;
	}
	os<<L<<'\n';
	return 0;
}
//WA??

uoj50 链式反应

现在我知道这道题是fft。。然后呢？？

每个中子呈树状展开，最后有多少棵(带编号)不同的树

转移明显是没有后效性的。。吗并不是。。因为死光的操作很烦人。。 $f[i]$ 一个点爆炸后面有 $i$ 个完好的方案数枚举中子打到的位置 $O(n^2)$ 可以把那 $i$ 个分成三段再枚举射死多少 $O(n)$ 再枚举在三段里面分别射死多少 $O(n^2)$ 就可以DP了吧复杂度 $O(n^6)$ 不行。。 $f[i][j]$

MDZZ

要么这个囧-2333原子变为了囧-2334 并不再参与后续反应

又tm没看题目！！！！！

那就好做点了吗？

$f[i]$ 表示 $i$ 的答案。

转移的时候不枚举编号，枚举梓树大小！！！还是用树的思维来思考，从大小来考虑好一些。因为大小是比编号更加重要的因素，而知道编号没法推出大小，但是知道大小可以随便重编号！！！树树树！！！

40pts

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	bool isValid(char ch) { return ch!='\r' && ch!='\n' && ch!=' ' && ch!=EOF; }
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	Istream &operator >>(char *s) {
		while(!isValid(*s=getchar()));
		while(isValid(*++s=getchar()));
		*s=0;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
const int MAXN=200+11,P=(7*17<<23)+1,inv2=499122177;
int main() {
	int n=is;
	static char s[MAXN];
	is>>s;
	static long long C[MAXN][MAXN];
	for(int i=0;i<=n;++i) 
		for(int j=0;j<=i;++j) 
			C[i][j]=j==0 || j==i?1:(C[i-1][j-1]+C[i-1][j])%P;
	static long long f[MAXN];
	f[1]=1;
	f[2]=0;
	for(int i=3;i<=n;++i)
		for(int j=1;j<=i-1;++j) 
			for(int k=1;k<=i-1-j;++k)
				if(s[i-1-j-k]=='1') 
					(f[i]+=C[i-1][i-1-j-k]*C[j+k][j]%P*f[j]%P*f[k]%P*inv2%P)%=P;
	for(int i=1;i<=n;++i) 
		os<<f[i]<<(i==n?'\n':' ');

	return 0;
}
//诡异的类型转换

uoj51 元旦三侠的游戏

Solution

如果 $n$ 小一些的话就能做了吗。

Tips

调用sqrt()不总能达到想要的效果。。要求高的整数开方可以自行二分。。。。

Code

#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	template <class T>
	operator T() {
		static T x;
		*this>>x;
		return x;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
	template <class T>
	Ostream &operator <<(T *s) {
		while(*s) *this<<*s++;
		return *this;
	}
}os;
const int MAXSQRTN=4e4,MAXLOGN=31;
int main() {
	int n=is,Q=is,m=1;
	while((m+1)*(m+1)<=n) ++m;
	static int end[MAXSQRTN],win[MAXSQRTN][MAXLOGN];
	for(int a=2;a<=m;++a) {
		end[a]=0;
		for(long long x=1;x<=n;x*=a,++end[a]);
	}
	end[m+1]=1;
	for(int a=m;a>=2;--a)
		for(int b=end[a]-1;b>=1;--b)
			win[a][b]=(b+1<end[a] && !win[a][b+1]) || (b<end[a+1] && !win[a+1][b]);
	while(Q--) {
		int a=is,b=is;
		os<<((a<=m?win[a][b]:(n-a)&1)?"Yes":"No")<<'\n';
	}
	return 0;
}

Solution

Code

Solution

Solution

跳蚤国王下江南

Solution

Tips

Code

Solution

Code

Solution

O(nnlogn)O(n\sqrt n\log n)O(n√​n​​​logn)

Solution

Tips

Code

$O(n\sqrt n\log n)$