BZOJ 1045: [HAOI2008] 糖果传递

设第i个小朋友从左边拿bi个 平均数为t
ai+bi-b(i+1)=t 不妨设b1=k
bn    =  k+t-an
bn-1  =  k+2t-an-a(n-1)
bn-2  =  k+3t-an-a(n-1)-a(n-2)
...
费用为sum(|bi|) 似乎3分就可以了?
不 还可以更快 绝对值的式子怎么化简呢?
考虑数形结合 那么就转化成了:k到各个数字的距离 于是就是中位数了!
然而这个复杂度还是nlogn的……
 
这道题好像刘汝佳的训练指南上第一章有讲到过,也可以参考那个的解答
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1000010;
LL n,a[N],t,tmp[N],k,ans;
void read(LL &x){char c;while((c=getchar())<'0'||c>'9');x=c-'0';while((c=getchar())>='0'&&c<='9') x=x*10+c-'0';}
int main(){
	//freopen("1045.in","r",stdin);freopen("1045.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]+=a[i-1];
	t=a[n]/n;
	tmp[n]=0;
	for(int i=1;i<n;i++) tmp[i]=i*t-a[n]+a[n-i];
	std::sort(tmp+1,tmp+n+1);
	k=tmp[(n+1)>>1];
	for(int i=1;i<=n;i++) ans+=abs(k-tmp[i]);
	printf("%lld",ans);
	return 0;
}

 

BZOJ 2875: [Noi2012]随机数生成器

今天颓了一天..就A了两简单题
矩阵乘法快速幂 然而long long 是会溢出的我也不知道怎么办 然后 我查了一下快速乘 得到了一个神奇的东西 
输入x,y 返回x*y%mod 我也不知道为什么这个可以 
听说这篇论文里有说到 论程序底层优化的一些方法与技巧.pdf
inline long long multi(long long x,long long y,long long mod){
	long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
	return tmp<0 ? tmp+mod : tmp;
}
在vijos上又看到一种方法 把快速幂的思想用到乘法上来,就变成了每次被乘数倍增乘数除二了,logn的乘法也是可过的而且是精确计算而不是像上面这样近似计算
 
总之扒了这个代码之后就过了
#include <cstdio>
using namespace std;
typedef long long LL;
LL a,x,c,n,m,g;
inline long long multi(long long x,long long y,long long mod){
	long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
	return tmp<0 ? tmp+mod : tmp;
}
struct mat{
	LL a[4][4];
	void reset(){for(int i=0;i<4;i++) for(int j=0;j<4;j++) a[i][j]=0;}
	void set1(){reset();for(int i=0;i<4;i++) a[i][i]=1;}
	friend mat operator *(mat x,mat y){
		mat z;
		z.reset();
		for(int i=1;i<=3;i++)
			for(int j=1;j<=3;j++)
				for(int k=0;k<=3;k++) (z.a[i][j]+=multi(x.a[i][k],y.a[k][j],m))%=m;
		return z;
	}
}o,tmp,ans;

int main(){
	scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x,&n,&g);
	a%=m,c%=m,x%=m;
	tmp.reset();tmp.a[1][1]=a;tmp.a[2][1]=c;tmp.a[2][2]=1;
	o.reset();o.a[1][1]=x;o.a[1][2]=1;
	ans.set1();
	for(;n;n>>=1){if(n&1) ans=ans*tmp;tmp=tmp*tmp;}
	ans=o*ans;
	printf("%lld",ans.a[1][1]%m%g);
	return 0;
}