【做題記錄】雜題亂做

LG P13280 「CZOI-R4」午夜巡游

不難發(fā)現(xiàn)除了 \(k\) 之外的其他數(shù)都是等價(jià)的，于是我們只需要計(jì)算 \(k\) 出現(xiàn)了幾次即可。

考慮將所有 \(i\in[1,n]\) 連一條 \(i\to p_i\) 的有向邊，這張圖一定由若干個(gè)環(huán)組成。而最終答案為 \(k\) 等價(jià)于 \(k\) 所在的這個(gè)環(huán)的長(zhǎng)度 \(x\mid m\)。于是我們枚舉 \(x\in[1,n]\land x\mid m\)，計(jì)算有多少個(gè)排列滿足 \(k\) 所在的環(huán)長(zhǎng)度為 \(x\)。不難算出這個(gè)數(shù)量為 \(\operatorname{A}_{n-1}^{x-1}\times(n-x)!\)。時(shí)間復(fù)雜度 \(O(T\sqrt{m})\)。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e7+5,mod=998244353;
int T,n,m,kk,fac[maxn],inv[maxn],tot,ans; 
il int pls(int x,int y){
	return x+y<mod?x+y:x+y-mod;
}
il int sub(int x,int y){
	return x<y?x-y+mod:x-y;
}
il void add(int &x,int y){
	x=pls(x,y);
}
il void mns(int &x,int y){
	x=sub(x,y);
}
il int qpow(int x,int y=mod-2){
	int res=1;
	while(y){
		if(y&1){
			res=res*1ll*x%mod;
		}
		x=x*1ll*x%mod,y>>=1;
	}
	return res;
}
il int A(int x,int y){
	if(x<y||y<0){
		return 0;
	}
//	cout<<x<<' '<<x-y<<'\n';
	return fac[x]*1ll*inv[x-y]%mod;
}
il int C(int x,int y){
	if(x<y||y<0){
		return 0;
	}
	return fac[x]*1ll*inv[y]%mod*inv[x-y]%mod;
}
il void init(int n=1e7){
	fac[0]=1;
	for(int i=1;i<=n;i++){
		fac[i]=fac[i-1]*1ll*i%mod;
	}
	inv[n]=qpow(fac[n]);
	for(int i=n;i;i--){
		inv[i-1]=inv[i]*1ll*i%mod;
	}
}
il void solve(int x){
	if(x>n){
		return ;
	}
	int num=A(n-1,x-1)*1ll*fac[n-x]%mod;
	mns(tot,num),add(ans,num*1ll*kk%mod);
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	init();
	cin>>T;
	while(T--){
		cin>>n>>m>>kk;
		if(!m){
			cout<<fac[n]*1ll*kk%mod<<'\n';
			continue;
		}
		ans=0,tot=fac[n];
		for(int i=1;i<=m/i;i++){
			if(m%i==0){
				solve(i);
				if(i!=m/i){
					solve(m/i);
				}
			}
		}
		add(ans,(n*1ll*(n+1)/2-kk)%mod*tot%mod*qpow(n-1)%mod);
		cout<<ans<<'\n';
	}
	return 0;
}
}
int main(){return asbt::main();}

LG P8880 無(wú)知時(shí)詆毀原神

首先發(fā)現(xiàn)這個(gè)排列是詐騙，記錄每個(gè)值的位置即可。打個(gè)表出來(lái)，發(fā)現(xiàn) \(n\) 為偶數(shù)時(shí)無(wú)解，\(n\) 為奇數(shù)時(shí)對(duì)于 \(c=\{0,1,2,\dots,n-1\}\)，\(\begin{cases}\begin{aligned}a&=\{0,n-1,n-2,n-3,\dots,1\}\\b&=\{0,2,4,6,\dots,n-1,1,3,5,\dots,n-2\}\end{aligned}\end{cases}\) 為一組可行解。這組可行解的正確性顯然，考慮偶數(shù)無(wú)解的證明。~~雖然此時(shí)你已經(jīng)完全可以寫出 AC 代碼了~~

排列 \(c\) 中的數(shù)之和為 \(\frac{n(n-1)}{2}\)，當(dāng) \(n\) 為偶數(shù)時(shí)，\(n-1\) 為奇數(shù)，于是顯然有 \(n\nmid \frac{n(n-1)}{2}\)。而排列 \(a\) 與 \(b\) 中的數(shù)之和為 \(n(n-1)\)，顯然 \(n\mid n(n-1)\)。于是 \(\sum a+\sum b\equiv 0\not\equiv\sum c\pmod{n}\)，于是無(wú)解。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,c[maxn],a[maxn],b[maxn];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	if(n%2==0){
		cout<<-1;
		return 0;
	}
	for(int i=0,x;i<n;i++){
		cin>>x;
		c[x]=i;
	}
	for(int i=1,j=2;i<n;i++){
		a[c[i]]=n-i;
		b[c[i]]=j,j=(j+2)%n;
	}
	for(int i=0;i<n;i++){
		cout<<a[i]<<' ';
	}
	cout<<'\n';
	for(int i=0;i<n;i++){
		cout<<b[i]<<' ';
	}
	return 0;
}
}
int main(){return asbt::main();}

LG P10655 [ROI 2017] 反物質(zhì) (Day 2)

設(shè) \(dp_i\) 表示當(dāng)前有 \(i\) 克反物質(zhì)，未來(lái)最壞情況下最多獲得的利潤(rùn)加 \(i\times10^9\) 的值，轉(zhuǎn)移方程是 \(dp_i=\max(i\times10^9,\max\limits_{j\,\operatorname{s.t.}i+r_j\le a}\{\min_{k=i+l_j}^{i+r_j}\{dp_k-c_j\}\})\)。相當(dāng)于是倒著 DP，在每次實(shí)驗(yàn)的開(kāi)頭再計(jì)算成本。

時(shí)間復(fù)雜度 \(O(na^2)\) 無(wú)法接受，考慮優(yōu)化。一個(gè)直接的思路是開(kāi) \(n\) 個(gè)單調(diào)隊(duì)列，但這樣空間太大。那么我們不妨維護(hù)每個(gè)實(shí)驗(yàn)對(duì)應(yīng)的最小值的位置。具體地，用單調(diào)棧維護(hù) \(L_i\) 表示 \(i\) 左側(cè)第一個(gè) \(dp\) 值比 \(dp_i\) 小的位置，轉(zhuǎn)移時(shí)尋找對(duì)于實(shí)驗(yàn) \(j\) 可轉(zhuǎn)移的最小的 \(dp\) 值的位置即可。于是時(shí)間復(fù)雜度 \(O(na)\)。

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e6+5;
int n,m,ll[105],rr[105],cc[105],pos[105];
int dp[maxn],stk[maxn],top,L[maxn];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>ll[i]>>rr[i]>>cc[i];
		pos[i]=m+1;
	}
	for(int i=m;~i;i--){
		dp[i]=i*1e9;
		for(int j=1;j<=n;j++){
			pos[j]=min(pos[j],i+rr[j]);
			while(L[pos[j]]>=i+ll[j]){
				pos[j]=L[pos[j]];
			}
			dp[i]=max(dp[i],dp[pos[j]]-cc[j]);
		}
		while(top&&dp[stk[top]]>dp[i]){
			L[stk[top--]]=i;
		}
		stk[++top]=i;
	}
	cout<<dp[0];
	return 0;
}
}
signed main(){return asbt::main();}

UVA10900 你想當(dāng)2^n元富翁嗎？ So you want to be a 2n-aire?

概期考慮倒著 DP，設(shè) \(f_i\) 表示答對(duì)第 \(i\) 題后的最大期望，假設(shè)答對(duì)第 \(i+1\) 道題的概率為 \(p\)，于是 \(f_i=\max(2^i,p\times f_{i+1})\)。但是 \(p\) 不是固定的，于是我們需要對(duì) \(2^i\) 和 \(p\times f_{i+1}\) 進(jìn)行分類討論。具體地，設(shè) \(p_0=\frac{2^i}{f_{i+1}}\)，那么如果 \(p<p_0\)，選擇 \(2^i\) 更優(yōu)，概率為 \(\frac{p_0-t}{1-t}\)；否則選擇 \(p\times f_{i+1}\) 更優(yōu)，\(p\) 取平均值 \(\frac{1+p_0}{2}\)，概率為 \(\frac{1-p_0}{1-t}\)。所以我們得到了最終的轉(zhuǎn)移方程：

\[f_i=\frac{p_0-t}{1-t}2^i+\frac{(1-p_0)(1+p_0)}{2(1-t)}f_{i+1} \]

初始狀態(tài) \(f_n=2^n\)，答案即為 \(f_0\)。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
int n;
double m,f[39];
int main(){
	while(~scanf("%d%lf",&n,&m)&&n){
		f[n]=1<<n;
		for(int i=n;i;i--){
			double p0=max(m,(1<<(i-1))*1.0/f[i]);
			f[i-1]=(p0-m)/(1-m)*(1<<(i-1))+(1-p0)*(1+p0)/2/(1-m)*f[i];
		}
		printf("%.3f\n",f[0]);
	}
	return 0;
}
}
int main(){return asbt::main();}

UVA297 四分樹(shù) Quadtrees

同時(shí) dfs 兩棵樹(shù)，黑點(diǎn)覆蓋灰點(diǎn)和白點(diǎn)，灰點(diǎn)覆蓋白點(diǎn)，在相應(yīng)層累加答案即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int num[]={1024,256,64,16,4,1};
int T,ans,ca,cb;
string a,b;
il void dfs(bool fa,bool fb,bool fr,int d){
//	cout<<ca<<' '<<a[ca]<<' '<<cb<<' '<<b[cb]<<' '<<fa<<' '<<fb<<' '<<fr<<' '<<d<<'\n';
	if(!fb){
		char cha=a[ca++];
		if(cha=='f'){
			if(fr){
				ans+=num[d];
			}
		}
		else if(cha=='p'){
			dfs(fa,fb,fr,d+1);
			dfs(fa,fb,fr,d+1);
			dfs(fa,fb,fr,d+1);
			dfs(fa,fb,fr,d+1);
		}
	}
	else if(!fa){
		char chb=b[cb++];
		if(chb=='f'){
			if(fr){
				ans+=num[d];
			}
		}
		else if(chb=='p'){
			dfs(fa,fb,fr,d+1);
			dfs(fa,fb,fr,d+1);
			dfs(fa,fb,fr,d+1);
			dfs(fa,fb,fr,d+1);
		}
	}
	else{
		char cha=a[ca++],chb=b[cb++];
		if(cha=='f'){
			ans+=num[d];
			if(chb=='p'){
				dfs(0,1,0,d+1);
				dfs(0,1,0,d+1);
				dfs(0,1,0,d+1);
				dfs(0,1,0,d+1);
			}
		}
		else if(cha=='p'){
			if(chb=='f'){
				ans+=num[d];
				dfs(1,0,0,d+1);
				dfs(1,0,0,d+1);
				dfs(1,0,0,d+1);
				dfs(1,0,0,d+1);
			}
			else if(chb=='p'){
				dfs(1,1,1,d+1);
				dfs(1,1,1,d+1);
				dfs(1,1,1,d+1);
				dfs(1,1,1,d+1);
			}
			else{
				dfs(1,0,1,d+1);
				dfs(1,0,1,d+1);
				dfs(1,0,1,d+1);
				dfs(1,0,1,d+1);
			}
		}
		else{
			if(chb=='f'){
				ans+=num[d];
			}
			else if(chb=='p'){
				dfs(0,1,1,d+1);
				dfs(0,1,1,d+1);
				dfs(0,1,1,d+1);
				dfs(0,1,1,d+1);
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		cin>>a>>b;
		ca=cb=ans=0;
		dfs(1,1,1,0);
//		cout<<a.size()<<' '<<b.size()<<' '<<ca<<' '<<cb<<'\n';
		cout<<"There are "<<ans<<" black pixels.\n";
	}
	return 0;
}
}
int main(){return asbt::main();}

LG P10184 [YDOI R1] whk

顯然答案可以二分。在 \(x\) 天中我們只需要做 \(x\times t\) 道題就可以了。如果某個(gè)科目 \(a_i\ge x\)，那么它只能貢獻(xiàn) \(x\) 道題；否則可以貢獻(xiàn) \(a_i\) 道題。時(shí)間復(fù)雜度線性對(duì)數(shù)。

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e5+5;
int n,m,a[maxn];
il bool check(int x){
	int tot=0;
	for(int i=1;i<=n;i++){
		tot+=min(a[i],x);
	}
	return tot>=x*m;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int l=0,r=5e11;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(check(mid)){
			l=mid;
		}
		else{
			r=mid-1;
		}
	}
	cout<<l;
	return 0;
}
}
signed main(){return asbt::main();}

AT_dp_t Permutation

考慮設(shè) \(f_{i,j}\) 表示在第 \(i\) 個(gè)位置填 \(j\) 的方案數(shù)，但是我們不確定當(dāng)前填入了哪些數(shù)，難以轉(zhuǎn)移。于是增加限制，強(qiáng)制此時(shí)填入的是 \(1\) 到 \(i\) 中的數(shù)。對(duì)于在 \(i+1\) 填 \(j\) 的情況，我們可以將前 \(i\) 個(gè)數(shù)中 \(\ge j\) 的數(shù)全部加一以保證不漏情況。于是可以轉(zhuǎn)移：

\[f_{i,j}=\begin{cases}\begin{aligned} &\sum_{k=1}^{j-1}f_{i-1,k}\quad&s_{i-1}='<'\\ &\sum_{k=j}^{i-1}f_{i-1,k}\quad&s_{i-1}='>' \end{aligned}\end{cases} \]

前綴和優(yōu)化即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=3e3+5,mod=1e9+7;
il int pls(int x,int y){
	return x+y<mod?x+y:x+y-mod;
}
il int sub(int x,int y){
	return x<y?x-y+mod:x-y;
}
int n,f[maxn][maxn],g[maxn][maxn];
string s;
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>s;
	s=" "+s;
	f[1][1]=g[1][1]=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			if(s[i-1]=='<'){
				f[i][j]=g[i-1][j-1];
			}
			else{
				f[i][j]=sub(g[i-1][i-1],g[i-1][j-1]);
			}
			g[i][j]=pls(g[i][j-1],f[i][j]);
		}
	}
	cout<<g[n][n];
	return 0;
}
}
int main(){return asbt::main();}

LG P6862 [RC-03] 隨機(jī)樹(shù)生成器

總數(shù)等于總方案數(shù)乘期望，于是我們求期望即可。對(duì)于 \(i\)，所有 \(j>i\) 都會(huì)產(chǎn)生 \(\frac{1}{j-1}\) 的貢獻(xiàn)，預(yù)處理出逆元的前綴和即可 \(O(1)\) 求解。別忘了加上父親的貢獻(xiàn)。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e7+5,mod=1e9+9;
int T,n,m,fac[maxn],inv[maxn];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	fac[0]=fac[1]=inv[1]=1;
	for(int i=2;i<=1e7;i++){
		fac[i]=fac[i-1]*1ll*i%mod;
		inv[i]=inv[mod%i]*1ll*(mod-mod/i)%mod;
	}
	for(int i=1;i<=1e7;i++){
		(inv[i]+=inv[i-1])%=mod;
	}
	cin>>T;
	while(T--){
		cin>>n>>m;
		cout<<(inv[n-1]-inv[m-1]+mod+(m>1))*1ll*fac[n-1]%mod<<'\n';
	}
	return 0;
}
}
int main(){return asbt::main();}

CF1608E The Cells on the Paper

顯然答案可二分，考慮如何 \(check\)。考慮三個(gè)矩形的分布，不難發(fā)現(xiàn)只有以下幾種：

而三種顏色有六種排列，總共就有三十六種情況。只需考慮其中的兩種，其它的可以旋轉(zhuǎn)同理。

從左往右，先滿足紅色數(shù)量 \(\ge mid\) 個(gè)，然后滿足綠色，最后檢驗(yàn)藍(lán)色。

先從下往上滿足藍(lán)色 \(\ge mid\) 個(gè)，然后在上面的區(qū)域從左往右滿足紅色，最后檢驗(yàn)綠色。

時(shí)間復(fù)雜度 \(O(36n\log n)\)。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lwrb lower_bound
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,cnt[3],lsx[maxn],tx,lsy[maxn],ty,cx[3][maxn],cy[3][maxn];
struct node{
	int xx,yy;
}a[3][maxn],b[3][maxn];
il bool cmp1(node x,node y){
	return x.xx<y.xx;
}
il bool cmp2(node x,node y){
	return x.yy<y.yy;
}
il bool check(int kk){
	// 1
	for(int x:{0,1,2}){
		int i=1,cnt=0;
		for(;i<=ty;i++){
			cnt+=cy[x][i];
			if(cnt>=kk){
				goto togo11;
			}
		}
		continue;
		togo11:;
		for(int y:{0,1,2}){
			if(x==y){
				continue;
			}
			int j=i+1;
			for(cnt=0;j<=ty;j++){
				cnt+=cy[y][j];
				if(cnt>=kk){
					goto togo12;
				}
			}
			continue;
			togo12:;
			for(int z:{0,1,2}){
				if(x==z||y==z){
					continue;
				}
				int k=j+1;
				for(cnt=0;k<=ty;k++){
					cnt+=cy[z][k];
					if(cnt>=kk){
						return 1;
					}
				}
			}
		}
	}
	// 2
	for(int x:{0,1,2}){
		int i=1,cnt=0;
		for(;i<=tx;i++){
			cnt+=cx[x][i];
			if(cnt>=kk){
				goto togo21;
			}
		}
		continue;
		togo21:;
		for(int y:{0,1,2}){
			if(x==y){
				continue;
			}
			int j=i+1;
			for(cnt=0;j<=tx;j++){
				cnt+=cx[y][j];
				if(cnt>=kk){
					goto togo22;
				}
			}
			continue;
			togo22:;
			for(int z:{0,1,2}){
				if(x==z||y==z){
					continue;
				}
				int k=j+1;
				for(cnt=0;k<=tx;k++){
					cnt+=cx[z][k];
					if(cnt>=kk){
						return 1;
					}
				}
			}
		}
	}
	// 3
	for(int x:{0,1,2}){
		int i=1,cnt=0;
		for(;i<=ty;i++){
			cnt+=cy[x][i];
			if(cnt>=kk){
				goto togo31;
			}
		}
		continue;
		togo31:;
		for(int y:{0,1,2}){
			if(x==y){
				continue;
			}
			int j=0;cnt=0;
			for(int k=1;k<=n;k++){
				if(a[y][k].yy>i){
					if(++cnt==kk){
						j=a[y][k].xx;
						goto togo32;
					}
				}
			}
			continue;
			togo32:;
			for(int z:{0,1,2}){
				if(x==z||y==z){
					continue;
				}
				cnt=0;
				for(int k=n;k&&a[z][k].xx>j;k--){
					if(a[z][k].yy>i){
						if(++cnt==kk){
							return 1;
						}
					}
				}
			}
		}
	}
	// 4
	for(int x:{0,1,2}){
		int i=ty,cnt=0;
		for(;i;i--){
			cnt+=cy[x][i];
			if(cnt>=kk){
				goto togo41;
			}
		}
		continue;
		togo41:;
		for(int y:{0,1,2}){
			if(x==y){
				continue;
			}
			int j=0;cnt=0;
			for(int k=1;k<=n;k++){
				if(a[y][k].yy<i){
					if(++cnt==kk){
						j=a[y][k].xx;
						goto togo42;
					}
				}
			}
			continue;
			togo42:;
			for(int z:{0,1,2}){
				if(x==z||y==z){
					continue;
				}
				cnt=0;
				for(int k=n;k&&a[z][k].xx>j;k--){
					if(a[z][k].yy<i){
						if(++cnt==kk){
							return 1;
						}
					}
				}
			}
		}
	}
	// 5
	for(int x:{0,1,2}){
		int i=1,cnt=0;
		for(;i<=tx;i++){
			cnt+=cx[x][i];
			if(cnt>=kk){
				goto togo51;
			}
		}
		continue;
		togo51:;
		for(int y:{0,1,2}){
			if(x==y){
				continue;
			}
			int j=0;cnt=0;
			for(int k=1;k<=n;k++){
				if(b[y][k].xx>i){
					if(++cnt==kk){
						j=b[y][k].yy;
						goto togo52;
					}
				}
			}
			continue;
			togo52:;
			for(int z:{0,1,2}){
				if(x==z||y==z){
					continue;
				}
				cnt=0;
				for(int k=n;k&&b[z][k].yy>j;k--){
					if(b[z][k].xx>i){
						if(++cnt==kk){
							return 1;
						}
					}
				}
			}
		}
	}
	// 6
	for(int x:{0,1,2}){
		int i=tx,cnt=0;
		for(;i;i--){
			cnt+=cx[x][i];
			if(cnt>=kk){
				goto togo61;
			}
		}
		continue;
		togo61:;
		for(int y:{0,1,2}){
			if(x==y){
				continue;
			}
			int j=0;cnt=0;
			for(int k=1;k<=n;k++){
				if(b[y][k].xx<i){
					if(++cnt==kk){
						j=b[y][k].yy;
						goto togo62;
					}
				}
			}
			continue;
			togo62:;
			for(int z:{0,1,2}){
				if(x==z||y==z){
					continue;
				}
				cnt=0;
				for(int k=n;k&&b[z][k].yy>j;k--){
					if(b[z][k].xx<i){
						if(++cnt==kk){
							return 1;
						}
					}
				}
			}
		}
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1,x,y,z;i<=n;i++){
		cin>>x>>y>>z;
		lsx[++tx]=x,lsy[++ty]=y,z--;
		a[z][++cnt[z]]={x,y};
	}
	n/=3;
	sort(lsx+1,lsx+tx+1);
	tx=unique(lsx+1,lsx+tx+1)-lsx-1;
	sort(lsy+1,lsy+ty+1);
	ty=unique(lsy+1,lsy+ty+1)-lsy-1;
	for(int i=1;i<=n;i++){
		for(int j:{0,1,2}){
			a[j][i].xx=lwrb(lsx+1,lsx+tx+1,a[j][i].xx)-lsx;
			a[j][i].yy=lwrb(lsy+1,lsy+ty+1,a[j][i].yy)-lsy;
			cx[j][a[j][i].xx]++,cy[j][a[j][i].yy]++;
			b[j][i]=a[j][i];
		}
	}
	for(int i:{0,1,2}){
		sort(a[i]+1,a[i]+n+1,cmp1);
		sort(b[i]+1,b[i]+n+1,cmp2);
	}
	int l=1,r=n;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(check(mid)){
			l=mid;
		}
		else{
			r=mid-1;
		}
	}
	cout<<l*3;
	return 0;
}
}
int main(){return asbt::main();}

LG P3174 [HAOI2009] 毛毛蟲(chóng)

treedp，分別計(jì)算子樹(shù)中以根為端點(diǎn)和穿過(guò)根的最長(zhǎng)的毛毛蟲(chóng)長(zhǎng)度，轉(zhuǎn)移時(shí)記錄最大值和次大值即可，不要忘了穿過(guò) \(u\) 時(shí) \(fa_u\) 也可以算在毛毛蟲(chóng)上。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=3e5+5;
int n,m,ans,f[maxn],g[maxn];
vector<int> e[maxn];
il void dfs(int u,int fa){
	int mx[3]={},son=0;
	for(int v:e[u]){
		if(v==fa){
			continue;
		}
		son++,dfs(v,u),mx[2]=g[v];
		sort(mx,mx+3,greater<int>());
	}
	switch(son){
		case 0:
		case 1:g[u]=mx[0]+1,f[u]=mx[0]+(fa?2:1);break;
		default:g[u]=mx[0]+son,f[u]=mx[0]+mx[1]+son-(fa?0:1);break;
	}
	ans=max(ans,f[u]);
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		e[u].pb(v),e[v].pb(u);
	}
	dfs(1,0);
	cout<<ans;
	return 0;
}
}
int main(){return asbt::main();}

UVA557 漢堡 Burger

正難則反，考慮最后剩下兩個(gè)不同的漢堡的概率，即前面 \(n-2\) 個(gè)位置每種漢堡正好有 \(\frac{n}{2}-1\) 個(gè)，而每次選擇的概率都是 \(\frac{1}{2}\)，于是概率即為：

\[{n-2\choose\frac{n}{2}-1}(\frac{1}{2})^{n-2} \]

但是有多測(cè)，考慮預(yù)處理。記上面那個(gè)式子為 \(f_n\)，顯然 \(n\) 為偶數(shù)，于是考慮從 \(f_{n-2}\) 遞推。有：

\[f_{n-2}={n-4\choose\frac{n}{2}-2}(\frac{1}{2})^{n-4} \]

于是可得 \(f_n=\frac{n-3}{n-2}f_{n-2}\)。線性預(yù)處理，\(O(1)\) 回答即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int T,n; 
double f[maxn];
int main(){
	f[2]=1;
	for(int i=4;i<=1e5;i+=2){
		f[i]=f[i-2]/(i-2)*(i-3);
	}
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		printf("%.4f\n",1-f[n]);
	}
	return 0;
}
}
int main(){return asbt::main();}

CodeChef - SOD3 Yet another SOD problem

差分后數(shù)位 DP 即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
int T,dig[21];
ll L,R,dp[21][3];
il ll dfs(int i,int j,bool limit){
	if(!limit&&~dp[i][j]){
		return dp[i][j];
	}
	if(i==1){
		int mx=limit?dig[1]:9,res=0;
		for(int k=0;k<=mx;k++){
			if(k%3==j){
				res++;
			}
		}
		if(!limit){
			dp[i][j]=res;
		}
		return res;
	}
	int mx=limit?dig[i]:9;
	ll res=0;
	for(int k=0;k<=mx;k++){
		res+=dfs(i-1,(j-k+9)%3,limit&&k==mx);
	}
	if(!limit){
		dp[i][j]=res;
	}
	return res;
}
il ll solve(ll x){
	int cnt=0;
	do{
		dig[++cnt]=x%10,x/=10;
	}while(x);
	return dfs(cnt,0,1);
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	memset(dp,-1,sizeof(dp));
	cin>>T;
	while(T--){
		cin>>L>>R;
		cout<<solve(R)-solve(L-1)<<'\n';
	}
	return 0;
}
}
int main(){return asbt::main();}

SP39 PIGBANK - Piggy-Bank

直接跑完全背包即可。~~UVA 和 SPOJ 的綠題都好水~~

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int inf=1e9;
int T,n,m,a[505],b[505],dp[10005];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m,m-=n,cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i]>>b[i];
		}
		memset(dp,0x3f,sizeof(dp));
		dp[0]=0;
		for(int i=1;i<=n;i++){
			for(int j=b[i];j<=m;j++){
				dp[j]=min(dp[j],dp[j-b[i]]+a[i]);
			}
		}
		if(dp[m]>=inf){
			cout<<"This is impossible.\n";
		}
		else{
			cout<<"The minimum amount of money in the piggy-bank is "<<dp[m]<<".\n";
		}
	}
	return 0;
}
}
int main(){return asbt::main();}

SP57 SUPPER - Supernumbers in a permutation

用樹(shù)狀數(shù)組維護(hù)出每個(gè)數(shù)為結(jié)尾、開(kāi)頭的 LIS，與答案比較即可。時(shí)間復(fù)雜度線性對(duì)數(shù)。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,a[maxn],pre[maxn],suf[maxn]; 
vector<int> ans;
struct{
	int tr[maxn];
	#define lowbit(x) (x&-x)
	il void init(){
		for(int i=1;i<=n;i++){
			tr[i]=0;
		}
	}
	il void upd(int p,int v){
		for(;p<=n;p+=lowbit(p)){
			tr[p]=max(tr[p],v);
		}
	}
	il int query(int p){
		int res=0;
		for(;p;p-=lowbit(p)){
			res=max(res,tr[p]);
		}
		return res;
	}
	#undef lowbit
}F;
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	while(cin>>n){
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		int len=0;
		F.init();
		for(int i=1;i<=n;i++){
			pre[a[i]]=F.query(a[i]);
			F.upd(a[i],pre[a[i]]+1);
			len=max(len,pre[a[i]]+1);
		}
		F.init();
		for(int i=n;i;i--){
			suf[a[i]]=F.query(n-a[i]+1);
			F.upd(n-a[i]+1,suf[a[i]]+1);
		}
		ans.clear();
		for(int i=1;i<=n;i++){
			if(pre[i]+suf[i]+1==len){
				ans.pb(i);
			}
		}
		cout<<ans.size()<<'\n';
		for(int i:ans){
			cout<<i<<' ';
		}
		cout<<'\n';
	}
	return 0;
}
}
int main(){return asbt::main();}

CF949E Binary Cards

首先可以發(fā)現(xiàn)對(duì)于每個(gè) \(k\)，只選 \(2^k\) 或只選 \(-2^k\) 或二者都不選一定是最優(yōu)的。于是考慮每一位，如果當(dāng)前所有數(shù)這一位有 \(1\)，那么我們就需要一個(gè) \(2^k\) 或一個(gè) \(-2^k\)，然后將所有數(shù)除以 \(2\) 遞歸。爆搜看似過(guò)不去，但是每次遞歸后值域都會(huì)減少一半，去重即可。時(shí)空都是線性對(duì)數(shù)的。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n;
vector<int> a;
il vector<int> dfs(int dep){
//	cout<<a[0]<<'\n';
	a.erase(unique(a.begin(),a.end()),a.end());
	for(auto i=a.begin();i<a.end();i++){
//		cout<<*i<<' ';
		if(*i==0){
			a.erase(i);
			break;
		}
	}
//	cout<<'\n';
	if(a.empty()){
//		puts("666");
		return vector<int>();
	}
	if(a.size()==1){
		if(a[0]==1){
			return vector<int>(1,1<<dep);
		}
		if(a[0]==-1){
			return vector<int>(1,-1<<dep);
		}
	}
//	if(a[0]==0){
//		puts("NB");
//		cout<<a.size()<<'\n';
//	}
	for(int x:a){
		if(x&1){
			goto togo;
		}
	}
	for(int &x:a){
		x>>=1;
	}
	return dfs(dep+1);
	togo:;
	vector<int> b=a;
	for(int &x:a){
		if(x&1){
			x--;
		}
		x>>=1;
	}
	vector<int> ra=dfs(dep+1);
	ra.pb(1<<dep);
	a=b;
	for(int &x:a){
		if(x&1){
			x++;
		}
		x>>=1;
	}
	vector<int> rb=dfs(dep+1);
	rb.pb(-1<<dep);
	return ra.size()<rb.size()?ra:rb;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1,x;i<=n;i++){
		cin>>x,a.pb(x);
	}
	sort(a.begin(),a.end());
	vector<int> ans=dfs(0);
	cout<<ans.size()<<'\n';
	for(int x:ans){
		cout<<x<<' ';
	}
	return 0;
}
}
int main(){return asbt::main();}

AT_dp_y Grid 2

設(shè) \(dp_i\) 表示走到第 \(i\) 個(gè)障礙物、不經(jīng)過(guò)其他障礙物的方案數(shù)，容斥即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=3e3+5,maxm=2e5+5,mod=1e9+7;
int n,m,kk,fac[maxm],inv[maxm],dp[maxn];
struct node{
	int x,y;
	il bool operator<(const node &b)const{
		return x<b.x||x==b.x&&y<b.y;
	}
}a[maxn];
il void init(int n=2e5){
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++){
		fac[i]=fac[i-1]*1ll*i%mod;
		inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;
	}
	for(int i=2;i<=n;i++){
		inv[i]=inv[i]*1ll*inv[i-1]%mod;
	}
}
il int C(int x,int y){
	return fac[x]*1ll*inv[y]%mod*inv[x-y]%mod;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>kk;
	for(int i=1;i<=kk;i++){
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+kk+1);
	if(a[kk].x!=n||a[kk].y!=m){
		a[++kk]={n,m};
	}
	init();
	for(int i=1,x,y;i<=kk;i++){
		x=a[i].x,y=a[i].y;
		dp[i]=C(x+y-2,x-1);
		for(int j=1;j<i;j++){
			if(a[j].y<=y){
				dp[i]=(dp[i]-dp[j]*1ll*C(x-a[j].x+y-a[j].y,x-a[j].x)%mod+mod)%mod;
			}
		}
	}
	cout<<dp[kk];
	return 0;
}
}
int main(){return asbt::main();}

SP6779 GSS7 - Can you answer these queries VII

樹(shù)剖 + 線段樹(shù)維護(hù)即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,a[maxn],dfn[maxn],cnt,sz[maxn],stk[maxn];
int hes[maxn],top[maxn],dep[maxn],fa[maxn];
int tag[maxn<<2];
bool fp[maxn<<2];
vector<int> e[maxn];
il void dfs1(int u,int fth){
	fa[u]=fth,sz[u]=1;
	dep[u]=dep[fth]+1;
	int mxs=0;
	for(int v:e[u]){
		if(v==fth){
			continue;
		}
		dfs1(v,u);
		sz[u]+=sz[v];
		if(mxs<sz[v]){
			mxs=sz[v],hes[u]=v;
		}
	}
}
il void dfs2(int u){
	dfn[u]=++cnt,stk[cnt]=u;
	if(!top[u]){
		top[u]=u;
	}
	if(hes[u]){
		top[hes[u]]=top[u];
		dfs2(hes[u]);
	}
	for(int v:e[u]){
		if(v==fa[u]||v==hes[u]){
			continue;
		}
		dfs2(v);
	}
}
struct node{
	int sum,lm,rm,mm;
	node(int sum=0,int lm=0,int rm=0,int mm=0):sum(sum),lm(lm),rm(rm),mm(mm){}
	il node operator+(const node &x)const{
		return node(sum+x.sum,max(lm,sum+x.lm),max(x.rm,rm+x.sum),max({mm,x.mm,rm+x.lm}));
	}
}tr[maxn<<2];
il void pushup(int id){
	tr[id]=tr[lid]+tr[rid];
}
il void pushtag(int id,int l,int r,int v){
	fp[id]=1,tag[id]=v;
	if(v>=0){
		tr[id]=node(v*(r-l+1),v*(r-l+1),v*(r-l+1),v*(r-l+1));
	}
	else{
		tr[id]=node(v*(r-l+1),v,v,v);
	}
}
il void pushdown(int id,int l,int r){
	if(fp[id]){
		int mid=(l+r)>>1;
		pushtag(lid,l,mid,tag[id]);
		pushtag(rid,mid+1,r,tag[id]);
		fp[id]=0;
	}
}
il void build(int id,int l,int r){
	if(l==r){
		tr[id]=node(a[stk[l]],a[stk[l]],a[stk[l]],a[stk[l]]);
		return ;
	}
	int mid=(l+r)>>1;
	build(lid,l,mid);
	build(rid,mid+1,r);
	pushup(id);
}
il void upd(int id,int L,int R,int l,int r,int v){
	if(L>=l&&R<=r){
		pushtag(id,L,R,v);
		return ;
	}
	pushdown(id,L,R);
	int mid=(L+R)>>1;
	if(l<=mid){
		upd(lid,L,mid,l,r,v);
	}
	if(r>mid){
		upd(rid,mid+1,R,l,r,v);
	}
	pushup(id);
}
il node query(int id,int L,int R,int l,int r){
	if(L>=l&&R<=r){
		return tr[id];
	}
	pushdown(id,L,R);
	int mid=(L+R)>>1;
	if(r<=mid){
		return query(lid,L,mid,l,r);
	}
	if(l>mid){
		return query(rid,mid+1,R,l,r);
	}
	return query(lid,L,mid,l,r)+query(rid,mid+1,R,l,r);
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		e[u].pb(v),e[v].pb(u);
	}
	dfs1(1,0),dfs2(1);
	build(1,1,n);
	cin>>m;
	while(m--){
		int opt,u,v,c;
		cin>>opt>>u>>v;
		if(opt==1){
			node resu,resv;
			while(top[u]!=top[v]){
				if(dep[top[u]]<dep[top[v]]){
					resv=query(1,1,n,dfn[top[v]],dfn[v])+resv;
					v=fa[top[v]];
				}
				else{
					resu=query(1,1,n,dfn[top[u]],dfn[u])+resu;
					u=fa[top[u]];
				}
			}
			if(dep[u]<dep[v]){
				resv=query(1,1,n,dfn[u],dfn[v])+resv;
			}
			else{
				resu=query(1,1,n,dfn[v],dfn[u])+resu;
			}
			cout<<max({resu.mm,resv.mm,resu.lm+resv.lm})<<'\n';
		}
		else{
			cin>>c;
			while(top[u]!=top[v]){
				if(dep[top[u]]<dep[top[v]]){
					swap(u,v);
				}
				upd(1,1,n,dfn[top[u]],dfn[u],c);
				u=fa[top[u]];
			}
			if(dep[u]>dep[v]){
				swap(u,v);
			}
			upd(1,1,n,dfn[u],dfn[v],c);
		}
	}
	return 0;
}
}
int main(){return asbt::main();}

LG P4626 一道水題 II

我們要求的，實(shí)際上是這個(gè)式子：

\[\prod_kp_k^{\lfloor\log_{p_k}n\rfloor} \]

其中 \(p_k\) 是第 \(k\) 個(gè)質(zhì)數(shù)。注意到當(dāng) \(p_k>\sqrt{n}\) 時(shí)，\(\lfloor\log_{p_k}n\rfloor=1\)。將 \(10^8\) 內(nèi)的質(zhì)數(shù)全都篩出來(lái)不是很可能，考慮我們能接受怎樣的復(fù)雜度。不妨按塊長(zhǎng) \(B=10^6\) 分塊，于是從第 \(2\) 塊開(kāi)始的質(zhì)數(shù)的指數(shù)都為 \(1\)。于是我們給后面這些塊做一個(gè)前綴積，打表打出來(lái)。對(duì)于 \(n\)，首先暴力算出 \(1\sim10^6\) 的貢獻(xiàn)，然后整塊查表，散塊區(qū)間篩即可。

打表：

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e6+5,mod=1e8+7,B=1e6;
int prm[maxn],prn;
bool npr[maxn];
il void esieve(int n=1e6){
	for(int i=2;i<=n;i++){
		if(!npr[i]){
			prm[++prn]=i;
			for(int j=i*i;j<=n;j+=i){
				npr[j]=1;
			}
		}
	}
}
int main(){
	freopen("P4626.txt","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	esieve();
	cout<<"1,1";
	int ans=1;
	for(int i=1;i<100;i++){
		for(int j=1;j<=B;j++){
			npr[j]=0;
		}
		int st=i*B+1,ed=(i+1)*B;
		for(int j=1;j<=prn;j++){
			for(int k=max((st+prm[j]-1)/prm[j],prm[j])*prm[j];k<=ed;k+=prm[j]){
				npr[k-i*B]=1;
			}
		}
		for(int j=1;j<=B;j++){
			if(!npr[j]){
				ans=ans*1ll*(j+i*B)%mod;
			}
		}
		cout<<','<<ans;
	}
	return 0;
}
}
signed main(){return asbt::main();}

AC Code：

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e6+5,mod=1e8+7,B=1e6;
const int pre[]={1,1,4279041,78522927,97275812,6626498,90103459,19755829,89404363,31420837,78259116,79495350,63384896,76365496,77671792,60888616,14364168,69179499,73237343,47511561,98202707,9638787,8923490,19377161,14025453,83914297,99211028,91698985,11861010,41728948,85011248,2957451,96835040,13279739,65389333,35674577,69539515,43558531,90167843,65612508,96727630,84411969,10432978,81144826,76822534,44673268,48780356,42026053,71419640,925833,75468296,56122076,11730540,24214526,57670707,87561236,60795551,16258057,38969193,93135220,99449198,86687779,48716439,54282180,9747238,6014664,88132693,90624798,78394444,54259153,2424434,71634841,6763549,80339105,74090298,10910559,39590831,57807866,78084208,54389248,4052287,74604335,99190428,89368783,73470487,32097770,29222100,30538785,3048397,89311543,48798411,36895907,88691881,24323948,4724247,97882710,84490696,93965490,66087028,92642640,55440368};
int n,prm[maxn],prn;
bool npr[maxn];
il void esieve(int n=1e6){
	for(int i=2;i<=n;i++){
		if(!npr[i]){
			prm[++prn]=i;
			for(int j=i*i;j<=n;j+=i){
				npr[j]=1;
			}
		}
	}
}
il int calc(int x){
	int res=1;
	while(res*x<=n){
		res*=x;
	}
	return res;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	esieve();
	int ans=1;
	if(n<=B){
		for(int i=1;i<=prn&&prm[i]<=n;i++){
			(ans*=calc(prm[i]))%=mod;
		}
	}else{
		for(int i=1;i<=prn;i++){
			(ans*=calc(prm[i]))%=mod;
		}
		int id=n/B,st=n/B*B+1,ed=n;
		(ans*=pre[n/B])%=mod;
		for(int i=1;i<=B;i++){
			npr[i]=0;
		}
		for(int i=1;i<=prn;i++){
			for(int k=max((st+prm[i]-1)/prm[i],prm[i])*prm[i];k<=ed;k+=prm[i]){
				npr[k-id*B]=1;
			}
		}
		for(int i=st;i<=ed;i++){
			if(!npr[i-id*B]){
				(ans*=i)%=mod;
			}
		}
	}
	cout<<ans;
	return 0;
}
}
signed main(){return asbt::main();}

UVA930 Polynomial Roots

對(duì)于每個(gè)根做大除法降冪，然后二次方程求根即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int T,n;
double A[maxn],B[maxn];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=n;~i;i--){
			cin>>A[i];
		}
		for(int i=1,n0=n;i<=n-2;i++){
			double x;
			cin>>x;
			for(int j=n0-1;~j;j--){
				B[j]=A[j+1];
				A[j]+=A[j+1]*x;
			}
			n0--;
			for(int j=0;j<=n0;j++){
				A[j]=B[j];
			}
		}
		double a=A[2],b=A[1],c=A[0];
		double x1=(-b+sqrt(b*b-4*a*c))/2/a,x2=(-b-sqrt(b*b-4*a*c))/2/a;
		cout<<fixed<<setprecision(1)<<max(x1,x2)<<'\n'<<min(x1,x2)<<'\n';
	}
	return 0;
}
}
int main(){return asbt::main();}

UVA970 Particles

區(qū)間可行性 DP 即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
int T,n;
bool f[105][105][3];
string s;
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		string s;
		cin>>s;
		n=s.size(),s=" "+s;
		for(int i=1;i<=n;i++){
			f[i][i][0]=f[i][i][1]=f[i][i][2]=0;
			f[i][i][s[i]-'X']=1;
		}
		for(int len=2;len<=n;len++){
			for(int l=1,r=len;r<=n;l++,r++){
				f[l][r][0]=f[l][r][1]=f[l][r][2]=0;
				for(int p=l;p<r;p++){
					f[l][r][0]|=f[l][p][0]&&f[p+1][r][1]||f[l][p][1]&&f[p+1][r][0]||f[l][p][2]&&f[p+1][r][2];
					f[l][r][1]|=f[l][p][0]&&f[p+1][r][0]||f[l][p][1]&&f[p+1][r][1]||f[l][p][1]&&f[p+1][r][2]||f[l][p][2]&&f[p+1][r][1];
					f[l][r][2]|=f[l][p][0]&&f[p+1][r][2]||f[l][p][2]&&f[p+1][r][0];
				}
			}
		}
		cout<<(f[1][n][2]?'Z':(f[1][n][1]?'Y':'X'))<<'\n';
	}
	return 0;
}
}
int main(){return asbt::main();}

UVA177 折紙痕 Paper Folding

每次相當(dāng)于將圖上的每個(gè)點(diǎn)繞上一張圖的終點(diǎn)順時(shí)針旋轉(zhuǎn) 90°，起點(diǎn)旋轉(zhuǎn)后的點(diǎn)即為這一張圖的終點(diǎn)。對(duì)每一條邊建三個(gè)點(diǎn)（兩個(gè)會(huì)導(dǎo)致整張圖連成一坨），可以直接模擬。然后再?gòu)狞c(diǎn)陣還原邊即可。注意 \(n=1\) 時(shí)不應(yīng)該輸出開(kāi)頭的空格，特判一下。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
int n;
struct{
	int L,R,U,D;
	int sx,sy,tx,ty;
	bool vis[400][400];
}a[15];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	a[1].sx=200,a[1].sy=200;
	a[1].tx=202,a[1].ty=202;
	a[1].L=200,a[1].R=202,a[1].U=202,a[1].D=200;
	a[1].vis[200][200]=a[1].vis[201][200]=a[1].vis[202][200]=a[1].vis[202][201]=a[1].vis[202][202]=1;
	for(int p=2;p<=13;p++){
		a[p].L=400,a[p].R=0,a[p].U=0,a[p].D=400;
		for(int i=a[p-1].L;i<=a[p-1].R;i++){
			for(int j=a[p-1].D;j<=a[p-1].U;j++){
				if(a[p-1].vis[i][j]){
					a[p].vis[i][j]=1;
					int x=i-a[p-1].tx,y=j-a[p-1].ty;
					a[p].vis[a[p-1].tx+y][a[p-1].ty-x]=1;
					a[p].L=min({a[p].L,i,a[p-1].tx+y});
					a[p].R=max({a[p].R,i,a[p-1].tx+y});
					a[p].U=max({a[p].U,j,a[p-1].ty-x});
					a[p].D=min({a[p].D,j,a[p-1].ty-x});
					if(i==a[p-1].sx&&j==a[p-1].sy){
						a[p].sx=i,a[p].sy=j;
						a[p].tx=a[p-1].tx+y,a[p].ty=a[p-1].ty-x;
					}
				}
			}
		}
//		cout<<a[p].L<<' '<<a[p].R<<' '<<a[p].U<<' '<<a[p].D<<'\n';
	}
//	for(int p=1;p<=13;p++){
//		cout<<p<<":\n";
//		for(int i=a[p].U;i>=a[p].D;i--){
//			for(int j=a[p].L;j<=a[p].R;j++){
//				cout<<(a[p].vis[j][i]?'*':' ');
//			}
//			cout<<'\n';
//		}
//	}
	while(cin>>n&&n){
		if(n==1){
			cout<<"_|\n^\n";
			continue;
		}
		string s[400];
		int p=1;
		bool flag=0;
		for(int i=a[n].L,j=a[n].U;i<=a[n].R;i++){
			if(a[n].vis[i][j]&&a[n].vis[i-1][j]&&a[n].vis[i+1][j]){
				s[p]+='_';
				flag=1;
			}else{
				s[p]+=' ';
			}
		}
		if(!flag){
			p=0;
			s[1].clear();
		}
		for(int i=a[n].U-2;i>=a[n].D;i-=2){
			p++;
			for(int j=a[n].L;j<=a[n].R;j++){
				if(a[n].vis[j][i+1]){
					s[p]+='|';
				}else if(a[n].vis[j][i]&&a[n].vis[j-1][i]&&a[n].vis[j+1][i]){
					s[p]+='_';
				}else{
					s[p]+=' ';
				}
			}
		}
		for(int i=1;i<=p;i++){
			while(s[i].back()==' '){
				s[i].pop_back();
			}
			cout<<s[i]<<'\n';
		}
		cout<<"^\n";
	}
	return 0;
}
}
int main(){return asbt::main();}

UVA10723 電子人的基因 Cyborg Genes

第一問(wèn)很容易想到求 LCS，用兩串長(zhǎng)度相加在減掉即可。但這樣第二問(wèn)不好求，直接組合數(shù)學(xué)是很不可做的，我們希望也可以 DP 求。于是對(duì)于第一問(wèn)，我們?cè)O(shè) \(f_{i,j}\) 直接表示考慮到 \(a_i\) 和 \(b_j\) 的答案。然后對(duì)于第二問(wèn)，再設(shè) \(g_{i,j}\) 表示方案數(shù)，轉(zhuǎn)移過(guò)程中考察 \(f_{i,j}\) 從哪里轉(zhuǎn)移過(guò)來(lái)就好了。

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
int T,n,m,f[35][35],g[35][35];
string a,b;
il int F(int i,int j){
	if(!i||!j){
		return i+j;
	}
	if(~f[i][j]){
		return f[i][j];
	}
	if(a[i]==b[j]){
		return f[i][j]=F(i-1,j-1)+1;
	}
	return f[i][j]=min(F(i-1,j),F(i,j-1))+1;
}
il int G(int i,int j){
	if(!i||!j){
		return 1;
	}
	if(~g[i][j]){
		return g[i][j];
	}
	if(a[i]==b[j]){
		return g[i][j]=G(i-1,j-1);
	}
	int p=F(i-1,j),q=F(i,j-1);
	if(p==q){
		return g[i][j]=G(i-1,j)+G(i,j-1);
	}else if(p<q){
		return g[i][j]=G(i-1,j);
	}else{
		return g[i][j]=G(i,j-1);
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T,cin.get();
	for(int _=1;_<=T;_++){
		getline(cin,a),getline(cin,b);
//		cout<<a<<' '<<b<<'\n';
		n=a.size(),m=b.size();
		a=" "+a,b=" "+b;
		memset(f,-1,sizeof(f));
		memset(g,-1,sizeof(g));
		cout<<"Case #"<<_<<": "<<F(n,m)<<' '<<G(n,m)<<'\n';
	}
	return 0;
}
}
signed main(){return asbt::main();}

LG P14339 [JOI2020 預(yù)選賽 R2] 剪刀石頭布 / Rock-Scissors-Paper Expression

計(jì)數(shù) DP，記 \(f_{0/1/2}\) 表示表達(dá)式的值為 R/S/P 的方案數(shù)，在中綴表達(dá)式求值的過(guò)程中轉(zhuǎn)移即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e5+5,mod=1e9+7;
il int calc1(int x,int y){
	if(x==0&&y==1){
		return 0;
	}else if(x==0&&y==2){
		return 2;
	}else if(x==1&&y==0){
		return 0;
	}else if(x==1&&y==2){
		return 1;
	}else if(x==2&&y==0){
		return 2;
	}else if(x==2&&y==1){
		return 1;
	}
}          
il int calc2(int x,int y){
	return x+y-calc1(x,y);
}          
il int calc3(int x,int y){
	return 3-x-y;
}          
struct node{
	int f[3]; 
	node(char x=0){
		f[0]=f[1]=f[2]=0;
		switch(x){
			case 'R':f[0]=1;break;
			case 'S':f[1]=1;break;
			case 'P':f[2]=1;break;
			case '?':f[0]=f[1]=f[2]=1;break;
		}
	}
	il int&operator[](int x){
		return f[x];
	}
	il node operator+(node g)const{
		node h;
		for(int i:{0,1,2}){
			for(int j:{0,1,2}){
				if(i==j){
					h[i]=(f[i]*1ll*g[j]+h[i])%mod;
				}else{
					int x=calc1(i,j);
					h[x]=(f[i]*1ll*g[j]+h[x])%mod;
				}
			}
		}
		return h;
	}
	il node operator-(node g)const{
		node h;
		for(int i:{0,1,2}){
			for(int j:{0,1,2}){
				if(i==j){
					h[i]=(f[i]*1ll*g[j]+h[i])%mod;
				}else{
					int x=calc2(i,j);
					h[x]=(f[i]*1ll*g[j]+h[x])%mod;
				}
			}
		}
		return h;
	}
	il node operator*(node g)const{
		node h;
		for(int i:{0,1,2}){
			for(int j:{0,1,2}){
				if(i==j){
					h[i]=(f[i]*1ll*g[j]+h[i])%mod;
				}else{
					int x=calc3(i,j);
					h[x]=(f[i]*1ll*g[j]+h[x])%mod;
				}
			}
		}
		return h;
	}
};
il node calc(node x,node y,char z){
	return z=='+'?x+y:z=='-'?x-y:x*y;
}
int n;
char a,tc[maxn];
node tn[maxn];
string s;
stack<node> sn;
stack<char> sc;
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>s>>a;
	for(int i=0;i<n;i++){
		switch(s[i]){
			case '(':
			case '+':
			case '-':
			case '*':sc.push(s[i]);break;
			case ')':{
				int cnt=0;
				while(sc.top()!='('){
					tn[++cnt]=sn.top(),sn.pop();
					tc[cnt]=sc.top(),sc.pop();
				}
				node t=sn.top();
				sn.pop(),sc.pop();
				for(int i=cnt;i;i--){
					t=calc(t,tn[i],tc[i]);
				}
				if(sc.size()&&sc.top()=='*'){
					t=calc(sn.top(),t,sc.top());
					sn.pop(),sc.pop();
				}
				sn.push(t);
				break;
			}
			default:{
				node t=s[i];
				if(sc.size()&&sc.top()=='*'){
					t=calc(sn.top(),t,sc.top());
					sn.pop(),sc.pop();
				}
				sn.push(t);
				break;
			}
		}
	}
	int cnt=0;
	while(sc.size()){
		tn[++cnt]=sn.top(),sn.pop();
		tc[cnt]=sc.top(),sc.pop();
	}
	node t=sn.top();
	for(int i=cnt;i;i--){
		t=calc(t,tn[i],tc[i]);
	}
	cout<<t[a=='R'?0:a=='S'?1:2];
	return 0;
}
}
int main(){return asbt::main();}

LG P14152 千手百眼，天下人間

撤銷 \(3\) 操作還需要恢復(fù)操作，非常麻煩。發(fā)現(xiàn)最后一個(gè)操作必然執(zhí)行。進(jìn)一步，可以先倒著跑一遍，處理出哪些操作需要執(zhí)行，需要區(qū)間打標(biāo)記，差分即可。然后再正著跑，使用線段樹(shù)即可。

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
#define lwrb lower_bound
#define uprb  upper_bound
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=5e5+5,inf=1e18;
int n,m,d[maxn],ans[maxn],a[maxn],c[maxn],tr[maxn<<2],tag[maxn<<2];
struct node{
	int opt,id,l,r,t,k;
}b[maxn];
il void pushup(int id){
	tr[id]=max(tr[lid],tr[rid]);
}
il void pushtag(int id,int x){
	tr[id]+=x,tag[id]+=x;
}
il void pushdown(int id){
	if(tag[id]){
		pushtag(lid,tag[id]);
		pushtag(rid,tag[id]);
		tag[id]=0;
	}
}
il void build(int id,int l,int r){
	if(l==r){
		tr[id]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(lid,l,mid);
	build(rid,mid+1,r);
	pushup(id);
}
il void add(int id,int L,int R,int l,int r,int x){
	if(L>=l&&R<=r){
		pushtag(id,x);
		return ;
	}
	pushdown(id);
	int mid=(L+R)>>1;
	if(l<=mid){
		add(lid,L,mid,l,r,x);
	}
	if(r>mid){
		add(rid,mid+1,R,l,r,x);
	}
	pushup(id);
}
il int query(int id,int L,int R,int l,int r){
	if(L>=l&&R<=r){
		return tr[id];
	}
	pushdown(id);
	int mid=(L+R)>>1,res=-inf;
	if(l<=mid){
		res=max(res,query(lid,L,mid,l,r));
	}
	if(r>mid){
		res=max(res,query(rid,mid+1,R,l,r));
	}
	return res;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>b[i].opt>>b[i].t>>b[i].l>>b[i].r;
		if(b[i].opt==1){
			cin>>b[i].k;
		}
		b[i].id=i;
	}
	sort(b+1,b+m+1,[](node x,node y){return x.t<y.t||x.t==y.t&&x.id<y.id;});
	for(int i=1;i<=m;i++){
		c[i]=b[i].t;
	}
	for(int i=m;i;i--){
		d[i]+=d[i+1];
		if(!d[i]&&b[i].opt==3){
			int l=lwrb(c+1,c+m+1,b[i].l)-c,r=uprb(c+1,c+m+1,b[i].r)-c-1;
			d[r]++,d[l-1]--;
		}
	}
	build(1,1,n);
	int cnt=0;
	for(int i=1;i<=m;i++){
		if(!d[i]&&b[i].opt<3){
			if(b[i].opt==1){
				add(1,1,n,b[i].l,b[i].r,b[i].k);
			}else{
				ans[++cnt]=query(1,1,n,b[i].l,b[i].r);
			}
		}
	}
	cout<<cnt<<'\n';
	for(int i=1;i<=cnt;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}
}
signed main(){return asbt::main();}

LG P13994 【MX-X19-T3】「LAOI-14」Another Round

\(\operatorname{mex}\) 難以維護(hù)，直接枚舉它。

假設(shè)當(dāng)前枚舉到了 \(p\)，我們要求的就是不選 \(b_i=p\) 的 \(i\)，能取到的 \(\max\{a_i\}\)，在值域上做個(gè)前后綴最大值即可。于是假設(shè)有 \(c_p\) 個(gè) \(i\) 滿足 \(a_i=p\)，則對(duì)于所有 \(k\in[1,n-c_p]\) 的答案有貢獻(xiàn) \(\max\{a_i\}-p\)。

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e6+5,inf=1e18;
int T,n,a[maxn],b[maxn];
int pre[maxn],suf[maxn];
int c[maxn],ans[maxn];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=0;i<=n;i++){
			pre[i]=suf[i]=-inf;
			c[i]=0,ans[i]=-inf;
		}
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int i=1;i<=n;i++){
			cin>>b[i];
			b[i]=min(b[i],n);
			c[b[i]]++;
			pre[b[i]]=max(pre[b[i]],a[i]);
			suf[b[i]]=max(suf[b[i]],a[i]);
		}
		for(int i=1;i<=n;i++){
			pre[i]=max(pre[i],pre[i-1]);
		}
		for(int i=n-1;~i;i--){
			suf[i]=max(suf[i],suf[i+1]);
		}
//		for(int i=0;i<=n;i++){
//			cout<<pre[i]<<' ';
//		}
//		cout<<'\n';
//		for(int i=0;i<=n;i++){
//			cout<<suf[i]<<' ';
//		}
//		cout<<'\n';
		for(int i=0;i<=n;i++){
			ans[n-c[i]]=max(ans[n-c[i]],max(i?pre[i-1]:-inf,i<n?suf[i+1]:-inf)-i);
//			cout<<i<<' '<<c[i]<<' '<<max(i?pre[i-1]:-inf,i<n?suf[i+1]:-inf)<<'\n';
		}
		for(int i=n-1;i;i--){
			ans[i]=max(ans[i],ans[i+1]);
		}
		for(int i=1;i<=n;i++){
			cout<<ans[i]<<'\n';
		}
	}
	return 0;
}
}
signed main(){return asbt::main();}

LG P14011 [POCamp 2023] 珿求 / bootfall

翻譯好評(píng)??

預(yù)處理一個(gè) \(f_i\) 表示 \(A\ge i\) 時(shí) \(D\) 最大是多少，DP 即可。對(duì)于詢問(wèn) \((A',D')\)，我們分進(jìn)不進(jìn)球進(jìn)行討論：

進(jìn)球，則 \(A>D'\)。此時(shí)我們?nèi)绻脍A，則要求 \(A-D'>A'-D\Leftrightarrow A+D>A'+D'\)，預(yù)處理后綴 \(\max\{f_i+i\}\) 即可 \(O(1)\) 求。而如果只能做到 \(A+D=A'+D'\)，那么就是平局。但如果只能做到 \(A+D<A'+D'\)，并不一定就會(huì)輸，因?yàn)楫?dāng) \(A'<D\) 時(shí)對(duì)方是不進(jìn)球的，進(jìn)入下一情況即可。
不進(jìn)球，\(A\le D'\)。此時(shí)不可能贏，如果能做到 \(D\ge A'\) 則平局，否則就只好輸了。

時(shí)間復(fù)雜度 \(O(nV^2)\)。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1.6e5+5,inf=1e9;
int n,m,f[maxn],g[maxn];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	memset(f,-0x3f,sizeof(f));
	f[0]=0;
	for(int i=1,a,b;i<=n;i++){
		cin>>a>>b;
		for(int j=1.6e5;~j;j--){
			f[j]=max({f[j]+b,j>=a?f[j-a]:-inf,f[j+1]});
		}
	}
	memset(g,-0x3f,sizeof(g));
	for(int i=1.6e5;~i;i--){
		g[i]=max(g[i+1],f[i]+i);
	}
//	for(int i=0;i<=15;i++){
//		cout<<f[i]<<' ';
//	}
//	cout<<'\n';
//	for(int i=0;i<=15;i++){
//		cout<<g[i]<<' ';
//	}
//	cout<<'\n';
	int cnt1=0,cnt2=0,cnt3=0;
	cin>>m;
	while(m--){
		int a,b;
		cin>>a>>b;
		if(g[b+1]>a+b){
			cnt1++;
		}else if(g[b+1]==a+b||f[0]>=a){
			cnt2++;
		}else{
			cnt3++;
		}
	}
	cout<<cnt1<<' '<<cnt2<<' '<<cnt3<<'\n';
	return 0;
}
}
int main(){return asbt::main();}

LG P14207 [ROI 2016 Day1] 捕撈，還是不捕撈？

我們的路線，顯然是先向上游走一段把一路上的魚全都帶上，再在向下游走的過(guò)程中賣掉。于是枚舉向上游走到了哪。此時(shí)我們賣魚的地方顯然是 \(c_i\) 在值域上的一段后綴，寫一個(gè)線段樹(shù)二分狀物即可。時(shí)間復(fù)雜度 \(O(n\log V)\)。

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=5e5+5;
int n,m,kk,tr[maxn<<3],sum[maxn<<3];
struct node{
	int p,b,c;
}a[maxn<<1];
il void pushup(int id){
	tr[id]=tr[lid]+tr[rid];
	sum[id]=sum[lid]+sum[rid];
}
il void add(int id,int l,int r,int p,int x){
	if(l==r){
		tr[id]+=p*x,sum[id]+=x;
		return ;
	}
	int mid=(l+r)>>1;
	if(p<=mid){
		add(lid,l,mid,p,x);
	}else{
		add(rid,mid+1,r,p,x);
	}
	pushup(id);
}
il int query(int id,int l,int r,int x){
	if(sum[id]<=x){
		return tr[id];
	}
	if(l==r){
		return l*x;
	}
	int mid=(l+r)>>1;
	if(sum[rid]>=x){
		return query(rid,mid+1,r,x);
	}else{
		return query(lid,l,mid,x-sum[rid])+tr[rid];
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>kk;
	for(int i=1;i<=n;i++){
		cin>>a[i].p>>a[i].b;
		a[i].c=-1;
	}
	for(int i=1;i<=m;i++){
		cin>>a[n+i].p>>a[n+i].b>>a[n+i].c;
	}
	sort(a+1,a+n+m+1,[](node x,node y){return x.p<y.p||x.p==y.p&&x.c>y.c;});
	int ans=0,sum=0;
	for(int i=1;i<=n+m;i++){
		if(~a[i].c){
			add(1,0,1e6,a[i].c,a[i].b);
		}else{
			sum+=a[i].b;
		}
		ans=max(ans,query(1,0,1e6,sum)-kk*a[i].p);
	}
	cout<<ans;
	return 0;
}
}
signed main(){return asbt::main();}

posted @ 2025-09-05 21:57 zhangxy__hp 閱讀(24) 評(píng)論(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部

zhangxyhp

【做題記錄】雜題亂做

LG P13280 「CZOI-R4」午夜巡游

LG P8880 無(wú)知時(shí)詆毀原神

LG P10655 [ROI 2017] 反物質(zhì) (Day 2)

UVA10900 你想當(dāng)2^n元富翁嗎？ So you want to be a 2n-aire?

UVA297 四分樹(shù) Quadtrees

LG P10184 [YDOI R1] whk

AT_dp_t Permutation

LG P6862 [RC-03] 隨機(jī)樹(shù)生成器

CF1608E The Cells on the Paper

LG P3174 [HAOI2009] 毛毛蟲(chóng)

UVA557 漢堡 Burger

CodeChef - SOD3 Yet another SOD problem

SP39 PIGBANK - Piggy-Bank

SP57 SUPPER - Supernumbers in a permutation

CF949E Binary Cards

AT_dp_y Grid 2

SP6779 GSS7 - Can you answer these queries VII

LG P4626 一道水題 II

UVA930 Polynomial Roots

UVA970 Particles

UVA177 折紙痕 Paper Folding

UVA10723 電子人的基因 Cyborg Genes

LG P14339 [JOI2020 預(yù)選賽 R2] 剪刀石頭布 / Rock-Scissors-Paper Expression

LG P14152 千手百眼，天下人間

LG P13994 【MX-X19-T3】「LAOI-14」Another Round

LG P14011 [POCamp 2023] 珿求 / bootfall

LG P14207 [ROI 2016 Day1] 捕撈，還是不捕撈？