首页 > 其他分享 >3 月杂题 - 下

3 月杂题 - 下

时间：2024-03-28 10:23:12浏览次数：18  
标签：return int ll len fa 杂题 dp

设 \(dp_{i,p,j}\) 为填了后 \(i\) 个卡片，最后一个填的是 \(p\) 位置，\(j\) 个“divine pair”已经确定。

转移的话就是，上上个是放在 \(p\) 的前面还是后面，会有不同的影响。

  • 如果放在前面，则上一个 \(j'\) 是 \(j-p+2\)，\(dp_{i,p,j}=\sum_{k=1}^{p-1} dp_{i-1,k,j-p+2}\)。

  • 如果放在后面，则上一个 \(j'\) 是 \(j-p+1\)，\(dp_{i,p,j}=\sum_{k=p}^{n} dp_{i-1,k,j-p+1}\)。

这个可以前缀和优化，时间复杂度 \(\mathcal{O}(n^3)\)。

Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 755;
const ll mod = 987654321;

ll dp[2][N][N],ans[N][N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	dp[1][1][0]=1;
	ans[0][0]=ans[1][0]=1;
	for (int i=2; i<N; i++){
		for (int pos=1; pos<=i; pos++){
			for (int j=0; j<N; j++){
				dp[i&1][pos][j]=0;
				int lst=j-pos+2;
				if (lst>=0){
					dp[i&1][pos][j]=dp[i&1^1][pos-1][lst];
				}
				lst--;
				if (lst>=0){
					(dp[i&1][pos][j]+=dp[i&1^1][i-1][lst]-dp[i&1^1][pos-1][lst]+mod)%=mod;
				}
				(ans[i][j]+=dp[i&1][pos][j])%=mod;
				(dp[i&1][pos][j]+=dp[i&1][pos-1][j])%=mod;
			}
		}
	}
	int tc;
	cin>>tc;
	while (tc--){
		int n,k;
		cin>>n>>k;
		cout<<ans[n][k]<<"\n";
	}
	return 0;
}

首先有一个结论，就是最大匹配等于最小点覆盖。所以，我们可以枚举最小点覆盖是什么。

这个要 \(\mathcal{O}(2^n)\)。然后，我们把只含一个端点的边（其实因为是最小点覆盖，而且是最小化答案，直接有端点在里面就可以）按照权值从小到大贪心选。如果选了 \(n-1\) 条边，说明一定构成了一个树，就更新答案。

最终复杂度 \(\mathcal{O}(2^n\times n^2)\)。

Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 22;
const int M = 1e6+6;

ll n,c,fa[N];

int ff(int x){
	return fa[x]==x?x:fa[x]=ff(fa[x]);
}

int sm(int x,int y){
	return ff(x)==ff(y);
}

void merge(int x,int y){
	x=ff(x);
	y=ff(y);
	fa[x]=y;
}

struct node {
	ll w,u,v;
	bool operator < (const node &x) const {
		return w<x.w;
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>c;
	vector<node> v;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++){
			ll w;
			cin>>w;
			if (w && i<j){
				v.push_back({w,i,j});
			}
		}
	}
	sort(v.begin(),v.end());
	ll ans=2e18;
	for (int i=0; i<(1<<n); i++){
		for (int j=1; j<=n; j++){
			fa[j]=j;
		}
		ll cnt=0,sum=0;
		for (auto p : v){
			if ((((i>>p.u-1)&1) || ((i>>p.v-1)&1)) && !sm(p.u,p.v)){
				cnt++,sum+=p.w;
				merge(p.u,p.v);
			}
		}
		if (cnt==n-1){
			ans=min(ans,sum+c*__builtin_popcount(i));
		}
	}
	cout<<ans<<"\n";
	return 0;
}

首先求出来 \(ind_{msk}\)，代表知道了集合 \(msk\) 中的元素，那么还是不能区别的字符串是那些。这个很好求。具体来说，先对于每两个字符串 \(i,j\)，求 \(sm\) 表示 \(i,j\) 相同的部分，再 \(ind_{sm}|=2^i\)。然后 \(ind_{msk}|=ind_{msk|(2^i)}\)，其中 \(i\) 不在 \(msk\) 中。

求这个有什么用？我们尝试用它表示答案。首先，我们要求的期望次数其实就是所有 \(msk\) 被访问的期望次数之和。我们把每一个 \(msk\) 被访问到的期望次数加起来就可以了。（\(msk\) 是你已经问了的位置集合）对于 \(msk\) 的答案是，\(\frac{\texttt{popcnt}(ind_{msk})}{n\times \binom{len}{\texttt{popcnt}(msk)}}\)，其中 \(len\) 是每一个字符串的长度。

为什么呢？因为要访问到 \(msk\)，你必须：

  • 不能问道 \(msk\) 的子集就已经知道答案。

  • 不能问不在 \(msk\) 中的元素。

满足第一个，要只能答案是 \(ind_{msk}\) 里的元素，即有 \(\frac{\texttt{popcnt}(ind_{msk})}{n}\)。满足第二个，在选 \(\texttt{popcnt}(msk)\) 个地方问的情况里只有一种是可以的，因此要乘上一个 \(\frac{1}{\binom{len}{\texttt{popcnt}(msk)}}\)。

Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

int n;
string s[55];
ll ind[1<<20];
ld dp[1<<20],C[21][21];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n;
	for (int i=0; i<=20; i++){
		C[i][0]=1;
		for (int j=1; j<=i; j++){
			C[i][j]=C[i-1][j-1]+C[i-1][j];
		}
	}
	for (int i=0; i<n; i++){
		cin>>s[i];
	}
	int m=s[0].size();
	for (int i=0; i<n; i++){
		for (int j=0; j<n; j++){
			if (i!=j){
				int sm=0;
				for (int k=0; k<m; k++){
					if (s[i][k]==s[j][k]){
						sm|=(1<<k);
					}
				}
				ind[sm]|=(1ll<<i);
			}
		}
	}
	ld ans=0;
	for (int msk=(1<<m)-1; msk>=0; msk--){
		for (int i=0; i<m; i++){
			if (!(msk>>i&1)){
				ind[msk]|=ind[msk|(1<<i)];
			}
		}
		if (ind[msk]){
			int pop1=__builtin_popcountll(ind[msk]);
			int pop2=__builtin_popcountll(msk);
			ans+=1.*pop1/n/C[m][pop2];		
		}
	}
	cout<<fixed<<setprecision(10)<<ans<<"\n";
	return 0;
}

感觉不蠢的 \(2k3\)。

首先，这个是换根 dp。第一次 dp 算出以 \(1\) 为根的答案。可以设 \(dp_u\) 为以 \(u\) 为根的方案数。则有两种情况（\(u\) 到儿子 \(v\)）：

  • 这条路不修，那么 \(v\) 子树内的必须修，贡献 \(1\)。

  • 这条路修，那么贡献 \(dp_v\)。

那么，有转移方程 \(dp_{u}=\prod_{v\in \texttt{son}(u)}(dp_v+1)\)。

怎么换根呢？怎么把根从 \(u\) 移到 \(v\)？容易发现，dp 值只有 \(i\) 和 \(j\) 会变。具体来说，
设 \(dp'_i\) 为 \(i\) 改变了以后的值。则：

  • \(dp'_u=\prod_{w\in \texttt{son}(u)\cap w\neq v} (dp_w+1)\)。

  • \(dp'_v=dp_v\times (dp_u+1)\)。

注意到 \(dp'_u\) 是所有乘积扣掉一个点，这个可以用前缀/后缀积来计算。

时间复杂度 \(\mathcal{O}(n)\)。

Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll mod = 1e9+7;

const int N = 2e5+5; 

ll n,f[N],ans[N];
vector<int> g[N];

void dfs1(int u,int fa){
	f[u]=1;
	for (auto v : g[u]){
		if (v^fa){
			dfs1(v,u);
			(f[u]*=f[v]+1)%=mod;
		}
	}
}

void dfs2(int u,int fa){
	ans[u]=1;
	vector<ll> pre,suf;
	for (auto v : g[u]){
		(ans[u]*=f[v]+1)%=mod;
		if (v^fa){
			pre.push_back(f[v]+1);
			suf.push_back(f[v]+1);
		}
	}
	for (int i=1; i<pre.size(); i++){
		(pre[i]*=pre[i-1])%=mod;
	}
	for (int i=suf.size()-2; i>=0; i--){
		(suf[i]*=suf[i+1])%=mod;
	}
	int pos=0;
	for (auto v : g[u]){
		if (v^fa){
			f[u]=1;
			if (fa){
				f[u]=f[fa]+1;
			}
			if (pos){
				(f[u]*=pre[pos-1])%=mod;
			}
			if (pos<suf.size()-1){
				(f[u]*=suf[pos+1])%=mod;
			}
			dfs2(v,u);
			pos++;
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n;
	for (int i=2; i<=n; i++){
		int p;
		cin>>p;
		g[p].push_back(i);
		g[i].push_back(p);
	}
	dfs1(1,0);
	dfs2(1,0);
	for (int i=1; i<=n; i++){
		cout<<ans[i]<<" ";
	}
	cout<<"\n";
	return 0;
}

具体见 this。

学了广义 SAM 但是做这题用了伪广义 SAM，嘻嘻。

首先，我们可以建出 \(T_{1\sim n}\) 的（伪）广义 SAM。我们可以求出所有 \(pr\) 在 SAM 上对应哪一个点，设为 \(ed_{pr}\)，以及对于每一个 \(pr\)，最左的 \(pl\) 是什么，最长长度记为 \(mxl_{pr}\)。如果一个询问 \(pr-pl+1\le mxl_{pr}\)，我们可以倍增求出 \(pl\) 对应的节点。

因为我们要求 \(T_{l,r}\) 中哪一个最多，我们可以尝试用线段树。我们给每一个 SAM 中的节点开一个权值线段树，线段树中 \([l,r]\) 代表用 \(T_{l\sim r}\) 的最大次数。因为一个节点的子树内都有这个串作为子串，我们进行一个线段树合并往上合并就可以了。

要求最多的，我们其实就是求一个子树内的颜色出现最多次数，这个就是线段树合并模板题。可以见 CF 600 E。

还有就是一个题外话。合并中是节点直接记录最大的是多少个。那么为什么 3 3 1 1 1 和 3 3 2 2 2 不会合并成只有 \(3\) 个而不是 \(4\) 个呢？因为以 merge 的时候是先和并左儿子和右儿子的，这个走到相同的点会直接加起来，更新父亲的时候就不会出现问题啦。比如说这个代码：

int merge(int a,int b,int l,int r){
	if (!a || !b){
		return a+b;
	}
	int nn=++tot;
	if (l==r){
		mx[nn].first=mx[a].first+mx[b].first;
		mx[nn].second=mx[a].second;
		return nn;
	}
	int mid=l+r>>1;
	ls[nn]=merge(ls[a],ls[b],l,mid);
	rs[nn]=merge(rs[a],rs[b],mid+1,r);
	mx[nn]=lar(mx[ls[nn]],mx[rs[nn]]);
	return nn;
}

l==r 的时候直接 +，先 ls，rs 再更新。

这个是 666 E 的代码片段。.first 是个数，.second 是颜色编号。lar 函数如下：

Code 
bool sma(const pair<int,int> &x,const pair<int,int> &y){
	return x.first==y.first?x.second>y.second:x.first<y.first;
}
pair<int,int> lar(const pair<int,int> &x,const pair<int,int> &y){
	return sma(x,y)?y:x;
}

这题就做完了。

Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e6+6;

int rt[N];

struct psegtree {
	int ls[N<<5],rs[N<<5],tot;
	pair<int,int> mx[N<<5];
	bool sma(const pair<int,int> &x,const pair<int,int> &y){
		return x.first==y.first?x.second>y.second:x.first<y.first;
	}
	pair<int,int> lar(const pair<int,int> &x,const pair<int,int> &y){
		return sma(x,y)?y:x;
	}
	void pu(int p){
		mx[p]=lar(mx[ls[p]],mx[rs[p]]);
	}
	void ins(int &p,int l,int r,int x){
		if (!p){
			p=++tot;
		}
		if (l==r){
			mx[p].first++;
			mx[p].second=l;
			return;
		}
		int mid=l+r>>1;
		if (x<=mid){
			ins(ls[p],l,mid,x);
		}
		else{
			ins(rs[p],mid+1,r,x);
		}
		pu(p);
	}
	int merge(int a,int b,int l,int r){
		if (!a || !b){
			return a+b;
		}
		int nn=++tot;
		if (l==r){
			mx[nn].first=mx[a].first+mx[b].first;
			mx[nn].second=mx[a].second;
			return nn;
		}
		int mid=l+r>>1;
		ls[nn]=merge(ls[a],ls[b],l,mid);
		rs[nn]=merge(rs[a],rs[b],mid+1,r);
		mx[nn]=lar(mx[ls[nn]],mx[rs[nn]]);
		return nn;
	}
	pair<int,int> qy(int p,int ql,int qr,int l,int r){
		if (!p){
			return {0,0};
		}
		if (r<ql || l>qr){
			return {0,0};
		}
		if (ql<=l && r<=qr){
			return mx[p];
		}
		int mid=l+r>>1;
		pair<int,int> ans={0,0};
		ans=lar(ans,qy(ls[p],ql,qr,l,mid));
		ans=lar(ans,qy(rs[p],ql,qr,mid+1,r));
		return ans;
	}
} st;

int n;
string s;
vector<int> g[N];
int ed[N],mxl[N];

struct SAM {
	struct sam {
		int fa,len,ch[26];
	} t[N];
	int tot=1,pos[N],lst=1;
	void ins(int c,int id){
		int p=lst,np=++tot,fl=0;
		lst=np;
		st.ins(rt[np],1,n,id);
		t[np].len=t[p].len+1;
		while (p && !t[p].ch[c]){
			t[p].ch[c]=np;
			p=t[p].fa;
		}
		if (!p){
			t[np].fa=1;
			return;
		}
		int q=t[p].ch[c];
		if (t[q].len==t[p].len+1){
			t[np].fa=q;
			return;
		}
		int nq=++tot;
		t[nq]=t[q];
		t[nq].len=t[p].len+1;
		t[q].fa=t[np].fa=nq;
		while (p && t[p].ch[c]==q){
			t[p].ch[c]=nq;
			p=t[p].fa;
		}
	}
} sam;

int fa[N][20];

void dfs(int u){
	for (auto v : g[u]){
		fa[v][0]=u;
		dfs(v);
		rt[u]=st.merge(rt[u],rt[v],1,n);
	}
}

pair<int,int> qy(int l,int r,int pl,int pr){
	if (pr-pl+1>mxl[pr]){
		return {0,l};
	}
	int pos=ed[pr];
	for (int i=18; i>=0; i--){
		if (fa[pos][i] && sam.t[fa[pos][i]].len>=pr-pl+1){
			pos=fa[pos][i];
		}
	}
	pair<int,int> ret=st.qy(rt[pos],l,r,1,n);
	if (!ret.first){
		ret.second=l;
	}
	return ret;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>s>>n;
	for (int i=1; i<=n; i++){
		string t;
		cin>>t;
		t=" "+t;
		sam.lst=1;
		for (int j=1; j<t.size(); j++){
			sam.ins(t[j]-'a',i);
		}
	}
	int p=1,len=0;
	s=" "+s;
	for (int i=1; i<s.size(); i++){
		int c=s[i]-'a';
		while (p && !sam.t[p].ch[c]){
			p=sam.t[p].fa;
			len=sam.t[p].len;
		}
		if (sam.t[p].ch[c]){
			p=sam.t[p].ch[c];
			len++;
		}
		else{
			p=1;
			len=0;
		}
		ed[i]=p;
		mxl[i]=len;
	}
	for (int i=2; i<=sam.tot; i++){
		g[sam.t[i].fa].push_back(i);
	}
	dfs(1);
	for (int w=1; w<=18; w++){
		for (int i=1; i<=sam.tot; i++){
			fa[i][w]=fa[fa[i][w-1]][w-1];
		}
	}
	int qys;
	cin>>qys;
	while (qys--){
		int l,r,pl,pr;
		cin>>l>>r>>pl>>pr;
		pair<int,int> res=qy(l,r,pl,pr);
		cout<<res.second<<" "<<res.first<<"\n";
	}
	return 0;
}

\(2022/12\) 做过这道题，当时没有理解，但是刚做还是 WA 了一次，哎。

首先建出 SAM。求出出现次数可以在 parent tree 上面 dp。注意：如果是 clone 的点，不能记录出现了 \(1\) 次！这样会 WA 5。

因为 SAM 一个节点对应的是 \([len(fa_v)+1,len(v)]\) 的长度区间，且一个串只能在一个节点（否则不是 DFA 了），所以一个结点的权值直接是 \(\frac{dp_u\times (dp_u+1)\times (len(u)-len(fa_u)}{2}\)。

Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int tot=1,lst=1;

const int N = 2e5+5;

struct sam {
	int len,ch[27],fa;
} t[N];

int n;
string s;
vector<int> g[N];
ll ans,dp[N];

void ins(int c){
	int p=lst,np=++tot;
	t[np].len=t[p].len+1;
	dp[np]=1;
	lst=np;
	while (p && !t[p].ch[c]){
		t[p].ch[c]=np;
		p=t[p].fa;
	}
	if (!p){
		t[np].fa=1;
		return;
	}
	int q=t[p].ch[c];
	if (t[q].len==t[p].len+1){
		t[np].fa=q;
		return;
	}
	int nq=++tot;
	t[nq]=t[q];
	t[nq].len=t[p].len+1;
	t[q].fa=t[np].fa=nq;
	while (p && t[p].ch[c]==q){
		t[p].ch[c]=nq;
		p=t[p].fa;
	}
}

void dfs(int u){
	for (auto v : g[u]){
		dfs(v);
		dp[u]+=dp[v];
	}
	if (u!=1){
		ll cnt=t[u].len-t[t[u].fa].len;
		ans+=dp[u]*(dp[u]+1)/2*cnt;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>s;
	n=s.size();
	s=" "+s;
	for (int i=1; i<=n; i++){
		ins(s[i]-'a');
	}
	for (int i=2; i<=tot; i++){
		g[t[i].fa].push_back(i);
	}
	dfs(1);
	cout<<ans<<"\n";
	return 0;
}

首先，是循环同构，所以可以把这个串复制一遍，\(x\rightarrow x+x\)。把 \(S\) 的 SAM 建出来，然后我们要找到的就是 SAM 上匹配长度 \(\ge |x|\) 的位置。

在匹配的时候设现在在 SAM 上点 \(p\)。如果 \(trans(p,c)\neq null\)，可以直接走，匹配长度加一；否则就要一直跳 \(fa(p)\) 直到有，如果没有，就直接设为 \(p=t_0\)，反之长度变为 \(len(p)+1\)，\(p\leftarrow trans(p,c)\)。这个时候，也许长度 \(>|x|\)，我们真正匹配不是现在的。这个时候就要 \(p\leftarrow fa(p)\) 直到 \(len(fa(p))<|x|\)。

因为 \(x\) 有可能有循环节，所以要去重。这个呢直接用一个 \(vis\) 数组记录上一个访问这个状态的是哪一个询问的 \(x\)。

Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2e6+6;

int tot=1,lst=1,vis[N];

struct sam {
	int len,ch[27],fa;
} t[N];

int n;
string s;
vector<int> g[N];
ll ans,dp[N];

void ins(int c){
	int p=lst,np=++tot;
	t[np].len=t[p].len+1;
	dp[np]=1;
	lst=np;
	while (p && !t[p].ch[c]){
		t[p].ch[c]=np;
		p=t[p].fa;
	}
	if (!p){
		t[np].fa=1;
		return;
	}
	int q=t[p].ch[c];
	if (t[q].len==t[p].len+1){
		t[np].fa=q;
		return;
	}
	int nq=++tot;
	t[nq]=t[q];
	t[nq].len=t[p].len+1;
	t[q].fa=t[np].fa=nq;
	while (p && t[p].ch[c]==q){
		t[p].ch[c]=nq;
		p=t[p].fa;
	}
}

void dfs(int u){
	for (auto v : g[u]){
		dfs(v);
		dp[u]+=dp[v];
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>s;
	n=s.size();
	s=" "+s;
	for (int i=1; i<=n; i++){
		ins(s[i]-'a');
	}
	for (int i=2; i<=tot; i++){
		g[t[i].fa].push_back(i);
	}
	dfs(1);
	int T;
	cin>>T;
	for (int tc=1; tc<=T; tc++){
		string x;
		cin>>x;
		int m=x.size();
		x+=x;
		x=" "+x;
		int p=1,l=0,ans=0;
		for (int i=1; i<=2*m; i++){
			int c=x[i]-'a';
			if (t[p].ch[c]){
				l++;
				p=t[p].ch[c];
			}
			else{
				while (p && !t[p].ch[c]){
					p=t[p].fa;
				}
				if (p==0){
					p=1,l=0;
				}
				else{
					l=t[p].len+1;
					p=t[p].ch[c];
				}
			}
			if (i>=m && l>=m){
				while (t[t[p].fa].len>=m){
					p=t[p].fa;
				}
				if (vis[p]<tc){
					ans+=dp[p];
					vis[p]=tc;
				}
				l=m;
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}

哎，\(2k3\) 又卡我。

首先，我们把位置按照 \(a_{i,j}\) 从小到大排序，这样就有转移的顺序了。很容易得出一个 dp 方程：\(f_{i}=\sum_{a_j<a_i}\frac{(x_i-x_j)^2+(y_i-y_j)^2+f_j}{num}=f_{i}=\sum_{a_j<a_i}\frac{x_i^2+x_j^2+y_i^2+y_j^2-2x_ix_j-2y_iy_j+f_j}{num}\)。\(num\) 是所有 \(j\) 的个数。很容易想到可以前缀和优化。

Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e6+6;
const ll mod = 998244353;

struct node {
	ll x,y,val;
	bool operator < (const node &a) const {
		return val<a.val;
	}
} a[N];

ll pw(ll x,ll y){
	ll res=1;
	while (y){
		if (y&1){
			(res*=x)%=mod;
		}
		x=x*x%mod;
		y>>=1;
	}
	return res;
}

int n,m,r,c;
ll nm,nx,ny,nx2,ny2;
ll nn,nnx,nny,nnx2,nny2;
ll sf,nsf,f[N],g[N],inv[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>m;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			int id=(i-1)*m+j;
			cin>>a[id].val;
			a[id].x=i,a[id].y=j;
		}
	}
	cin>>r>>c;
	sort(a+1,a+1+n*m);
	inv[1]=1;
	for (int i=2; i<=n*m; i++){
		inv[i]=pw(i,mod-2);
	}
	for (int i=1; i<=n*m; i++){
		if (a[i].val!=a[i-1].val){
			nm+=nn;
			nx+=nnx;
			ny+=nny;
			nx2+=nnx2;
			ny2+=nny2;
			sf+=nsf;
			nn=nnx=nny=nnx2=nny2=nsf=0;
		}
		f[i]=(nm*(a[i].x*a[i].x+a[i].y*a[i].y)%mod+nx2+ny2-2*a[i].x*nx%mod-2*a[i].y*ny%mod+sf)%mod*inv[nm]%mod;
		nn++;
		(nnx+=a[i].x)%=mod;
		(nny+=a[i].y)%=mod;
		(nnx2+=a[i].x*a[i].x)%=mod;
		(nny2+=a[i].y*a[i].y)%=mod;
		(nsf+=f[i])%=mod;
		if (a[i].x==r && a[i].y==c){
			cout<<f[i]<<"\n";
			return 0;
		}
	}
	return 0;
}

矩阵树定理模板题。具体的，对于边 \((u,v,w)\)，\(a_{i,i}=\sum_{v\rightarrow u} w\)，\(i\neq j\) 时 \(a_{i,j}=\sum_{u=i,v=j} w\)，去掉 \(a\) 第一行第一列，\(\det(a)\) 就是答案。

Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int mod = 1e9+7;
const int N = 305;

ll pw(ll x,ll y=mod-2){
	ll ans=1;
	while (y){
		if (y&1){
			ans=ans*x%mod;
		}
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}

ll n,m,op,*a[N],_a[N][N];

ll det(ll **a){
	ll ans=1;
	bool fl=0;
	for (int j=1; j<n; j++){
		for (int i=j; i<n; i++){
			if (a[i][j]){
				if (i!=j){
					swap(a[i],a[j]);
					fl^=1;
				}
				break;
			}
		}
		if (a[j][j]==0){
			return 0;
		}
		(ans*=a[j][j])%=mod;
		ll t=pw(a[j][j]);
		for (int k=j; k<n; k++){
			a[j][k]=t*a[j][k]%mod;
		}
		for (int i=j+1; i<n; i++){
			t=mod-a[i][j];
			for (int k=j; k<n; k++){
				(a[i][k]+=t*a[j][k])%=mod;
			}
		}
	}
	return fl?(mod-ans)%mod:ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>m>>op;
	for (int i=1; i<=n; i++){
		a[i]=_a[i];
	}
	for (int i=1; i<=m; i++){
		ll u,v,w;
		cin>>u>>v>>w;
		if (u==n){
			u=1;
		}
		else if (u==1){
			u=n;
		}
		if (v==n){
			v=1;
		}
		else if (v==1){
			v=n;
		}
		if (op==0){
			a[u][v]=(a[u][v]-w+mod)%mod;
			a[v][v]=(a[v][v]+w)%mod;
			a[v][u]=(a[v][u]-w+mod)%mod;
			a[u][u]=(a[u][u]+w)%mod;
		}
		else{
			a[u][v]=(a[u][v]-w+mod)%mod;
			a[v][v]=(a[v][v]+w)%mod;
		}
	}
	cout<<det(a)<<"\n";
	return 0;
}

我们要求 \(\displaystyle \sum_{T}(\Pi_{e\in T}p_e\Pi_{e\notin T}(1-p_e))=\sum_T(\Pi_{e\in T}p_e\frac{\Pi_e(1-p_e)}{\Pi_{e\in T}(1-p_e)})=\prod_e(1-p_e)(\sum_{T}\Pi_{e\in T}\frac{p_e}{1-p_e})\)。这个东西套上矩阵树模板即可。（模板可以求 \(\sum_T\prod _{e\in T} w_e\)。）

Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int N = 77;
const ld eps = 1e-7;

ll n;
ld *a[N],_a[N][N],d[N][N];

ld det(ld **a){
	ld ans=1;
	bool fl=0;
	for (int j=1; j<n; j++){
		for (int i=j; i<n; i++){
			if (a[i][j]){
				if (i!=j){
					swap(a[i],a[j]);
					fl^=1;
				}
				break;
			}
		}
		if (a[j][j]==0){
			return 0;
		}
		ans*=a[j][j];
		ld t=1./a[j][j];
		for (int k=j; k<n; k++){
			a[j][k]=t*a[j][k];
		}
		for (int i=j+1; i<n; i++){
			t=-a[i][j];
			for (int k=j; k<n; k++){
				a[i][k]+=t*a[j][k];
			}
		}
	}
	return fl?-ans:ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n;
	for (int i=1; i<=n; i++){
		a[i]=_a[i];
	}
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++){
			cin>>d[i][j];
		}
	}
	ld ans=1.;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++){
			if (fabs(d[i][j])<eps){
				d[i][j]=eps;
			}
			else if (fabs(1.0-d[i][j])<eps){
				d[i][j]=1.0-eps;
			}
			if (j>i){
				ans*=(1.0-d[i][j]);
			}
			d[i][j]=d[i][j]/(1-d[i][j]);
		}
	}
	for (int i=1; i<=n; i++){
		d[i][i]=0;
		for (int j=1; j<=n; j++){
			if (i!=j){
				d[i][i]+=d[i][j];
				d[i][j]=-d[i][j];
			}
		}
	}
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++){
			a[i][j]=d[i][j];
		}
	}
	cout<<fixed<<setprecision(10)<<ans*det(a)<<"\n";
	return 0;
}

可爱 \(2k9\)。

考虑分成一段一段，一段一段 dp。如果在 \([l,r]\) 至少有一个 \(0/1\)，那么在 \(r\) 左边第一个 \(0/1\) 要 \(\ge l\)。

我们设一个 dp：\(f_i\) 代表以 \(i\) 结尾的一段全是 \(0\)，\(g_i\) 代表以 \(i\) 结尾的一段全是 \(1\)，\(h_i\) 代表以 \(i\) 结尾的一段有 \(0\) 也有 \(1\)。

\(f,g\) 的转移是枚举上一个 \(0/1\) 在哪一段，\(h\) 的转移是 \((2^{l_i}-2)\times (f_{i-1}+g_{i-1}+h_{i-1})\)。\(l_i\) 是以 \(i\) 结尾的段的长度。\(f,g\) 的转移前缀和优化即可。

Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2e6+6;
const ll mod = 1e9+7;

int k,n,m,p[N],cnt,p1[N],p2[N]; // 1 0; 2 1
// max~i have 0/1
ll f[N],g[N],h[N],fs[N],gs[N],hs[N];
pair<int,int> a[N],b[N];

ll pw(ll x,ll y){
	ll res=1;
	while (y){
		if (y&1){
			res=res*x%mod;
		}
		x=x*x%mod;
		y>>=1;
	}
	return res;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>k>>n>>m;
	p[++cnt]=0;
	p[++cnt]=k;
	for (int i=1; i<=n; i++){
		cin>>a[i].first>>a[i].second;
		a[i].first--;
		p[++cnt]=a[i].first;
		p[++cnt]=a[i].second;
	}
	for (int i=1; i<=m; i++){
		cin>>b[i].first>>b[i].second;
		b[i].first--;
		p[++cnt]=b[i].first;
		p[++cnt]=b[i].second;
	}
	sort(p+1,p+1+cnt);
	cnt=unique(p+1,p+1+cnt)-p-1;
	for (int i=1; i<=n; i++){
		int pf=lower_bound(p+1,p+1+cnt,a[i].first)-p;
		int ps=lower_bound(p+1,p+1+cnt,a[i].second)-p;
		p1[ps]=max(p1[ps],pf);
	}
	for (int i=1; i<=m; i++){
		int pf=lower_bound(p+1,p+1+cnt,b[i].first)-p;
		int ps=lower_bound(p+1,p+1+cnt,b[i].second)-p;
		p2[ps]=max(p2[ps],pf);
	}
	for (int i=1; i<=cnt; i++){
		p1[i]=max(p1[i],p1[i-1]);
		p2[i]=max(p2[i],p2[i-1]);
	}
	h[1]=1;
	hs[1]=1;
	for (int i=2; i<=cnt; i++){
		f[i]=(gs[i-1]-gs[p1[i]]+mod+hs[i-1]-hs[p1[i]]+mod)%mod;
		g[i]=(fs[i-1]-fs[p2[i]]+mod+hs[i-1]-hs[p2[i]]+mod)%mod;
		h[i]=(pw(2,p[i]-p[i-1])-2+mod)%mod*((f[i-1]+g[i-1]+h[i-1])%mod)%mod;
		fs[i]=(fs[i-1]+f[i])%mod;
		gs[i]=(gs[i-1]+g[i])%mod;
		hs[i]=(hs[i-1]+h[i])%mod;
	}
	cout<<(f[cnt]+g[cnt]+h[cnt])%mod<<"\n";
	return 0;
}

最不会算复杂度的一集。抽象成 \((a,b)\) 为平面直角坐标系的一个点，每一个 \(1\) 可以让给我们切掉左边的一些，\(2\) 让我们切掉下面的一些，\(3\) 让我们切掉右上角的一个矩形。因为 \(3\) 比较难处理，我们就只考虑 \(1,2\)。

显然的想法是，每一次能切掉一半就可以了。但这样有点难处理。我们考虑切掉的东西渐渐接近 \((a,b)\)。可以采用类似倍增的方法。具体来讲，

  • 定义 \((ca,cb)\) 为现在的增量，\((ma,mb)\) 是现在已经确定的 \(\le a,\le b\) 的值。

  • 如果回应 \(1,2\)，可以 \(ma/mb\) 相应增加 \(ca/cb\)，\(ca/cb\) 相应乘以 \(2\)。

  • 否则，\(ca,cb\) 均除以 \(2\)。（这边要么 \(ca\) 大了要么 \(cb\) 大了）

复杂度和 \(\log n\) 同阶，但是常数是啥，不知道！

代码有点不同，但是思路相同。(思路混乱)

点击查看代码 
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
ll n;
pair<ll,ll> la,lb;
 
ll ask(ll x,ll y){
	cout<<x<<" "<<y<<endl;
	fflush(stdout);
	ll z;
	cin>>z;
	return z;
}
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
 
	cin>>n;
	la=lb={1,n};
	ll ca=1,cb=1;
	while (true){
		ll ma=la.second-la.first+1;
		ll mb=lb.second-lb.first+1;
		ca=min(ca,ma);
		cb=min(cb,mb);
		ll d=ask(la.first+ca-1,lb.first+cb-1);
		if (d==0){
			return 0;
		}
		if (d==1){
			la.first+=ca;
			ca*=2ll;
		}
		else if (d==2){
			lb.first+=cb;
			cb*=2ll;
		}
		else{
			ca/=2;
			cb/=2;
			ca=max(ca,1ll);
			cb=max(cb,1ll);
		}
	}
	return 0;
}

sxy 开始学凸包喽！

不是很理解叉乘，所以用斜率算。分别求出上凸包、下凸包。先按照 \((x,y)\) 排序。上凸包顺时针一定是斜率一直在减，下凸包反之。用一个单调栈维护即可！

点击查看代码 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int N = 1e5+5;

struct node {
	ld x,y;
} p[N];

int n,st[N],top;
ld ans;

#define sq(x) ((x)*(x)) 
#define inf 123456789

bool cmp(node a,node b){
	return a.x==b.x?a.y<b.y:a.x<b.x;
}

ld dis(int x,int y){
	return sqrt(sq(p[x].x-p[y].x)+sq(p[x].y-p[y].y));
}

ld K(int x,int y){
	return p[x].x==p[y].x?inf:(p[x].y-p[y].y)/(p[x].x-p[y].x);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n;
	for (int i=1; i<=n; i++){
		cin>>p[i].x>>p[i].y;
	}
	sort(p+1,p+1+n,cmp);
	for (int i=1; i<=n; i++){
		st[++top]=i;
		while (top>2 && K(st[top],st[top-2])<K(st[top-1],st[top-2])){
			st[top-1]=st[top];
			top--;
		}
	}
	for (int i=1; i<top; i++){
		ans+=dis(st[i],st[i+1]);
	}
	top=0;
	for (int i=n; i; i--){
		st[++top]=i;
		while (top>2 && K(st[top],st[top-2])<K(st[top-1],st[top-2])){
			st[top-1]=st[top];
			top--;
		}
	}
	for (int i=1; i<top; i++){
		ans+=dis(st[i],st[i+1]);
	}
	cout<<fixed<<setprecision(2)<<ans<<"\n";
	return 0;
}

凸包练习题！

如果不考虑一个山遮挡另一个山，我们求出每一个山谷对应的能照亮他能放的灯的区间 \([l,r]\)，我们要选择一些点使得每一个线段都包含点。这是一个经典的贪心问题。

如果有遮挡呢？那么他的 \([l,r]\) 会被前面/后面的山挡住。我们求出凸包就可以了。

Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int N = 1e6+6; 

int n,ans;
ld h,x[N],y[N];
int stk[N],top;
ld l[N],r[N];

ld K(int i,int j){
	return (y[i]-y[j])/(x[i]-x[j]);
}

void ch(){
	top=1;
	stk[top]=1;
	for (int i=2; i<=n; i++){
		while (top>1 && K(stk[top],stk[top-1])<K(i,stk[top])){
			top--;
		}
		if (i&1){
			l[i]=x[stk[top]]-(x[i]-x[stk[top]])/(y[stk[top]]-y[i])*(h-y[stk[top]]);
		}
		stk[++top]=i;
	}
	top=1;
	stk[top]=n;
	for (int i=n-1; i; i--){
		while (top>1 && K(stk[top],stk[top-1])>K(i,stk[top])){
			top--;
		}
		if (i&1){
			r[i]=x[stk[top]]+(-x[i]+x[stk[top]])/(y[stk[top]]-y[i])*(h-y[stk[top]]);
		}
		stk[++top]=i;
	}
}

struct seg {
	ld l,r;
	bool operator < (const seg &x) const {
		return r==x.r?l>x.l:r<x.r;
	}
}e[N];

int m;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>h;
	for (int i=1; i<=n; i++){
		cin>>x[i]>>y[i];
	}
	ch();
	for (int i=3; i<n; i++){
		if (i&1){
			e[++m]={l[i],r[i]};
		}
	}
	sort(e+1,e+1+m);
	ld lst=-1e18*1.;
	for (int i=1; i<=m; i++){
		if (lst<e[i].l){
			ans++;
			lst=e[i].r;
		}
	}
	cout<<ans<<"\n";
	return 0;
}

标签：return,int,ll,len,fa,杂题,dp
From： https://www.cnblogs.com/SFlyer/p/18080699

相关文章

  • 「杂题乱刷」洛谷 P2572
    先上AC代码：点击查看代码/*Tips:你数组开小了吗？你MLE了吗？你觉得是贪心，是不是该想想dp？一个小时没调出来，是不是该考虑换题？*/#include<bits/stdc++.h>usingnamespacestd;#definemapunordered_map#defineforl(i,a,b)for(registerlonglongi=a;i<=b;i++)#define......
  • QOJ杂题合集
    QOJ杂题合集QOJ#151.NiceLinesQOJ#838.HorribleCyclesQOJ#894.LongestLooseSegmentQOJ#895.Color给定一个有\(n\)个节点的无向完全图\(G\)，每条边都被染成了\(m\)种颜色中的一种，颜色编号为\(1\simm\)。我们称一个无向完全图合法，当且仅当对于\(\forallx......
  • 「杂题乱刷」洛谷 P1708
    题目链接P1708解题思路解法一：考虑预处理，这部分可以直接打表。其他题解这部分讲的比较详细了，在此不再赘述。期望得分\(100\)分。解法二：考虑数位dp。这里采用记搜的写法。dfs(last,sum,maxsum,_1)分别表示还需要枚举几位数，目前枚举的数位和，可以枚举的最大数位和，是否均......
  • 3 月杂题记
    过了几个月，又回来了，3.7之前的懒得补了。3.7P2487[SDOI2011]拦截导弹最近在学CDQ。花了我好久调试。CDQ优化DP模板。将转移条件转化成三维偏序。在CDQ中求。至于每个点在最长的二维最长升子序列的出现次数，多开一个数组\(f[0/1][i]\)存，转移还是使用树状数组顺带做了......
  • 「杂题乱刷」CF1846E1 & CF1846E2
    E1链接一眼题。直接预处理即可。时间复杂度\(O(n\log_2(n))\)。难度1。代码：点击查看代码/*Tips:你数组开小了吗？你MLE了吗？你觉得是贪心，是不是该想想dp？一个小时没调出来，是不是该考虑换题？*/#include<bits/stdc++.h>usingnamespacestd;#definemapunordered_m......
  • 「杂题乱刷」洛谷 P4801
    链接套路题。最小值：排序后直接分讨即可。最大值：排序后枚举开头为\(a_1\)，\(a_n\)的情况后双指针贪心即可。代码：点击查看代码/*Tips:你数组开小了吗？你MLE了吗？你觉得是贪心，是不是该想想dp？一个小时没调出来，是不是该考虑换题？*/#include<bits/stdc++.h>usingnamespa......
  • dp&图论 杂题选做
    开个新坑qwq。upd：CSP前一周暂时停更。upd：暂时不会更了。P1099经典套路题。算法一：枚举。先dfs求出树的直径，再枚举直径上的每条路径，再dfs一遍求出最小偏心距即可。时间复杂度\(O(n^3)\)，足以通过本题（由此可见本题有多水）。算法二：双指针。通过观察可以发现，在固定左端......
  • 点分治杂题总结
    前言由于已经点明是点分治，所以我们在文章中约定，题解只叙述：求经过当前递归到的\(x\)对于答案的贡献，用以减少文章冗余程度。如有错误，欢迎指出。\(\texttt{1.[BJOI2017]树的难题}\)其实还是比较简单一题，做多了自然就会。首先我们先\(\texttt{dfs}\)，在\(x\)的子树上处理一......
  • 240302 杂题
    小知识：VSCode通过调整Editor:CursorSurroundingLines可以达到Typora打字机模式的效果。调到任意一个超过屏幕总行数的值可以让焦点居中。很舒服。T1movehttp://222.180.160.110:1024/contest/5006/problem/1注意到\(x\)和\(y\)的绝对值是分开计算的，只用分类讨论......
  • 杂题乱做
    记录一些有意思的题。其他模拟赛linkCF1858E2\(*2600\).维护一个当前指针endpos，指向序列末尾，同时维护一个set<pair<int,int>>，表示每个数第一次出现的位置。加操作可以直接加入，如果当前这个数已经出现过直接右移指针，否则维护一棵树状数组，加上贡献。减操作直接将endpos左......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99