4题代码求助
  • 板块题目总版
  • 楼主WangLianda
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/9/25 04:51
  • 上次更新2023/10/27 10:03:42
查看原帖
4题代码求助
643820
WangLianda楼主2022/9/25 04:51

今天做学习总结，发现好几道以前积压的题目，应该都是思路正确但是代码调不出来的，求助各位大佬！

1

P3919 【模板】可持久化线段树 1（可持久化数组）

正常思路，样例过了，但是我写的可持久化线段树好像和主流的不太一样，没看过板子，自己憋出来的。常数略大，需开O2。

32分代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
struct node {
	int l,r,v,lc,rc;
} t[(int)25e6];
int top;
int root[(int)1e6+5];
int& newnode(int&u) {//newnode
	return u=top++;
}
void build(int&u,int l,int r) {
	t[newnode(u)]={l,r,0};
	if(l==r) return;
	int mid=l+r>>1;
	build(t[u].lc,l,mid);
	build(t[u].rc,mid+1,r);	
}
void push(int h/*history*/,int u,int p,int v) {
	t[u]=t[h];
	if(t[u].l==t[u].r&&t[u].r==p) {t[u].v=v;return;}
	int mid=t[u].l+t[u].r>>1;
	if(p<=mid)  push(t[h].lc,h==u?t[h].lc:newnode(t[u].lc),p,v);
	if(p>mid) push(t[h].rc,h==u?t[h].rc:newnode(t[u].rc),p,v);
}
int find(int u,int p) {
	if(t[u].l==t[u].r&&t[u].r==p) return t[u].v;
	int mid=t[u].l+t[u].r>>1;
	if(p<=mid) return find(t[u].lc,p);
	if(p>mid) return find(t[u].rc,p);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	int n,m;
	cin>>n>>m;
	build(root[0],1,n);
	for(int i=1;i<=n;i++) {
		int v;
		cin>>v;
		push(root[0],root[0],i,v);
	}
	for(int i=1;i<=m;i++) {
		int a,b,c,d;
		cin>>a>>b>>c;
		if(b==1) {
			cin>>d;
			push(a,newnode(root[i]),c,d);
		}
		else {
//			cout<<"***";
			cout<<find(root[a],c)<<endl;
			t[newnode(root[i])]=t[root[a]];
		}
	}
	return 0;
}

2

P4168 [Violet]蒲公英

分块，正常思路，样例已过。

0分代码如下：

#include<iostream>
#include<algorithm>
#include<climits>
#include<cmath>
using namespace std;
int block[205];
int a[40005],ap[40005],b[40005];
int t[205][40005];
int T[40005];
int pre[205][40005];
//pre[i][j]表示前i个块里大小为j的数字出现的个数之和
int k;
int n,m;
int block_l(int x) {//O(1)
	return 1+(x-1)*k;
}
int block_r(int x) {//O(1)
	return x*k;
}
void disc() {//O(nlogn)
	for(int i=1; i<=n; i++)
		ap[i]=a[i];
	sort(ap+1,ap+1+n);
	int end=unique(ap+1 ,ap+1+n)-ap;
	for(int i=1; i<=n; i++)
		b[i]=lower_bound(ap+1,ap+end,a[i])-ap;
}
int gb(int x) {//O(1)
	return (x+k-1)/k;
}
void push_up(int x,int v) {//O(1)
	int y=gb(x);
	if(t[y][block[y]]<t[y][v]||(t[y][block[y]]==t[y][v]&&block[y]>v))
		block[y]=v;
}
void push(int x,int v) {//O(1) 
	t[gb(x)][v]++;
	push_up(x,v);
}
void make_pre() {//O(n*sqrt n)
	for(int i=1; i<=gb(n); i++)
		for(int j=1; j<=40000; j++)
			pre[i][j]=pre[i-1][j]+t[i][j];
}
void change(int i,int lb,int rb) {
	if(!T[b[i]])
		T[b[i]]+=pre[rb][b[i]]-pre[lb-1][b[i]]+1;
	else
		T[b[i]]++;
}
int find(int l,int r) {//O(sqrt n)
	if(l>r)
		swap(l,r);
	int maxx=1;
	if(r-l+1<(k<<1)) {
		//暴力
		for(int i=l;i<=r;i++) 
			T[b[i]]++;
		for(int i=l;i<=r;i++) 
			if(T[maxx]<T[b[i]]||(T[maxx]==T[b[i]]&&maxx>b[i]))
				maxx=b[i];
		for(int i=l;i<=r;i++) 
			T[b[i]]=0;
	} else {
		for(int i=l;i<=block_r(gb(l));i++) 
			change(i,gb(l)+1,gb(r)-1);
		for(int i=block_l(gb(r));i<=r;i++)
			change(i,gb(l)+1,gb(r)-1);
		for(int i=gb(l)+1;i<=gb(r)-1;i++) 
			if(!T[block[i]])
				T[block[i]]+=pre[gb(r)-1][block[i]]-pre[gb(l)+1-1][block[i]];	
		for(int i=l;i<=block_r(gb(l));i++) 
			if(T[maxx]<T[b[i]]||(T[maxx]==T[b[i]]&&maxx>b[i]))
				maxx=b[i];
		for(int i=block_l(gb(r));i<=r;i++)
			if(T[maxx]<T[b[i]]||(T[maxx]==T[b[i]]&&maxx>b[i]))
				maxx=b[i];
		for(int i=l;i<=block_r(gb(l));i++) 
			T[b[i]]=0;
		for(int i=block_l(gb(r));i<=r;i++)
			T[b[i]]=0;
		for(int i=gb(l)+1;i<=gb(r)-1;i++) 
			T[block[i]]=0;
	}
	return maxx;
}
int main() {
	cin>>n>>m;
	k=sqrt(n);
	for(int i=1; i<=n; i++)
		cin>>a[i];
	disc();
	for(int i=1; i<=n; i++)
		push(i,b[i]);
	make_pre();
	int x=0,l,r;
	while(m--) {
		cin>>l>>r;
//		cout<<"***";
		cout<<(x=ap[find((l+x-1)%n+1,(r+x-1)%n+1)])<<endl;
	}
	return 0;
}

3

P3052 [USACO12MAR]Cows in a Skyscraper G

状压DP，设f[i]表示i情况下的最小分组数量。

16分代码如下：

#include<iostream>
#include<climits>
using namespace std;
long long f[(long long)1<<19];
long long s[(long long)1<<19];
long long a[20],n,w;
long long sigma(long long x) {
	long long sum=0;
	int c=1;
	while(x) {
		if(x&1) sum+=a[c];
		c++;
		x>>=1;
	}
	return sum;
}
int main() {
	for(auto&i:f)
		i=1e10;
	cin>>n>>w;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<(1<<n); i++)
		if((s[i]=sigma(i))<=w)
			f[i]=1;
	for(long long i=1; i<(1<<n); i++)
		for(long long k=0; k<=n; k++) {
			if(!((i>>k)&1)) continue;
			long long j=i^(1<<k);
			if(s[i]+s[1<<k]>w)
				f[i]=min(f[i],f[j]+f[i-j]);
			else
				f[i]=min(f[i],f[j]+1);
		}
	cout<<f[(1<<n)-1];
	return 0;
}

4

P3017 [USACO11MAR]Brownie Slicing G

二分答案，正常思路。

10分代码如下：

#include<iostream>
using namespace std;
int a[505][505],pre[505][505];
int x,y,n,m;
inline int sum(int X1,int Y1,int X2,int Y2) {
	return pre[X2][Y2]-pre[X2][Y1-1]-pre[X1-1][Y2]+pre[X1-1][Y1-1];
}
bool judge_line(int X1,int X2,int K) {
	int cy=1;
	for(int i=1; i<m; i++) {
		int j=i;
		while(j<=m&&sum(X1,i,X2,j)<K)
			j++;
		i=j;
		if(++cy==y) {
			bool t=i<m?sum(X1,i+1,X2,m)>=K:true;
//			if(t)
//				cout<<"line "<<X1<<"~"<<X2<<" dis in "<<j<<'\n';
			return t;
		}
	}
	return false;
}
bool judge(int K) {
//	cout<<"judge in K="<<K<<endl;
	int cx=1;
	for(int i=1; i<n; i++) {
		int j=i;
		while(j<=n&&!(judge_line(i,j,K)))
			j++;
		i=j;
		if(++cx==x)
			return i<n?judge_line(i+1,n,K):true;
	}
	return false;
}
int main() {
	cin>>n>>m>>x>>y;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			cin>>a[i][j];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			pre[i][j]=pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1]+a[i][j];
	int l=0,r=pre[n][m]/(x*y);
	int mid=l+r+1>>1;
	while(l<r)
		if(judge(mid=l+r+1>>1))
			l=mid;
		else
			r=mid-1;
	cout<<l;
	return 0;
}
2022/9/25 04:51