关于我把初始化注释掉就过了这件事
查看原帖
关于我把初始化注释掉就过了这件事
138106
tgs9311楼主2022/3/25 20:46

为什么我的初始化memset出问题了???

去掉就AC了???

求解释

代码:

#include<bits/stdc++.h>
using namespace std;
namespace FAST_IO
{
	template<typename T> void read(T &a)
	{
		a=0;
		int f=1;
		char c=getchar();
		while(!isdigit(c))
		{
			if(c=='-')
			{
				f=-1;
			}
			c=getchar();
		}
		while(isdigit(c))
		{
			a=a*10+c-'0';
			c=getchar();
		}
		a=a*f;
	}
	template <typename T> void write(T a)
	{
		if(a<0)
		{
			a=-a;
			putchar('-');
		}
		if(a>9)
		{
			write(a/10);
		}
		putchar(a%10+'0');
	}
	template <typename T> void writeln(T a)
	{
		write(a);
		puts("");
	}
}
const int maxn=2e5+100;
const long double ma=1e18;
int t;
int n,l,p;
string s[maxn];
int len[maxn];
long double sum[maxn],Next[maxn];
long double dp[maxn];
int last[maxn];
struct node
{
	int c,l,r;
};
node q[maxn];
int head=1,tail=1;
long double power(long double a,long long n)
{
	long double result=1;
	while(n)
	{
		if(n&1)
		{
			result*=a;
		}
		a*=a;
		n>>=1;
	}
	return (result);
}
long double _abs(long double x)
{
	if(x<0)
	{
		return -x;
	}
	return x;
}
long double val(int j,int i)//dp[j]->dp[i]
{
	return dp[j]+power(_abs(sum[i]-sum[j]+i-j-1-l),p);
}
void output()
{
	if(dp[n]>ma)
	{
		puts("Too hard to arrange");
	}
	else
	{
		printf("%.0Lf\n",dp[n]);
		for(int i=n; i; i=last[i])
		{
			Next[last[i]]=i;
		}
		int now=0;
		for(int i=1; i<=n; ++i)
		{
			now=Next[now];
			for(int j=i; j<now; ++j)
			{
				cout<<s[j]<<" ";
			}
			cout<<s[now]<<endl;
			i=now;
		}
	}
	puts("--------------------");
}
int main()
{
//	freopen("P1912_2.in","r",stdin);
//	freopen("P1912_2.ans","w",stdout);
	cin>>t;
	while(t--)
	{
//		memset(last,0,sizeof(last));
//		memset(sum,0,sizeof(sum));
//		memset(q,0,sizeof(q));
//		memset(dp,0,sizeof(dp));
		cin>>n>>l>>p;
		for(int i=1; i<=n; i++)
		{
			cin>>s[i];
			len[i]=s[i].size();
			sum[i]=sum[i-1]+len[i];
		}
		head=tail=1;
		q[1]=(node)
		{
			0,1,n
		};
		//	memset(dp,0x3f,sizeof(dp));
		//	dp[0]=0;
		for(int i=1; i<=n; i++)
		{
			int pos=n+1;
			while(head<tail&&q[head].r<i)
			{
				head++;
			}
			q[head].l=i;
			dp[i]=val(q[head].c,i);
			last[i]=q[head].c;
			while(head<tail&&val(i,q[tail].l)<=val(q[tail].c,q[tail].l))
			{
				pos=q[tail].l;
				tail--;
			}
			if(head<tail&&val(i,q[tail].r)>=val(q[tail].c,q[tail].r))//c means choose
			{
				goto A;
			}
			else
			{
				//只要在tail上二分 
				int now=q[tail].c;
				int ls=q[tail].l,rs=q[tail].r;
				while(ls<=rs)
				{
					int mid=ls+rs>>1;
					if(val(i,mid)<=val(now,mid))
					{
						rs=mid-1;
						pos=mid;
					}
					else
					{
						ls=mid+1;
					}
				}
				q[tail].r=pos-1;
			}
			A:
            if(pos!=n+1)
            {
			    tail++;
			    q[tail]=(node){i,pos,n};
            }
//			for(int j=0;j<i;j++)
//			{
//				dp[i]=min(dp[i],dp[j]+(long long)pow(abs(sumlen[i]-sumlen[j]+i-j-1-l),p));
//			}
		}
		output();
	}
}
2022/3/25 20:46
加载中...