From The Stupid

BZOJ 3110: [Zjoi2013]K大数查询

学了一下整体二分，就拿这题练练手- -

线段树标记下传的时候把+=写成了=调了N久也是醉

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=50010,INF=~0u>>1;
struct ask{int op,cur,ans,tmp,l,r,c,id;}qs[N],q[N*4],q1[N*4],q2[N*4];
int T[N*4],tag[N*4],L[N*4],R[N*4],ans[N*4],n,m;
typedef long long LL;
void up(int x){T[x]=T[x<<1]+T[x<<1|1];}
void down(int x){
	if(tag[x]){
		T[x<<1]+=(R[x<<1]-L[x<<1]+1)*tag[x];tag[x<<1]+=tag[x];
		T[x<<1|1]+=(R[x<<1|1]-L[x<<1|1]+1)*tag[x];tag[x<<1|1]+=tag[x];
		tag[x]=0;
	}
}
void build(int x,int l,int r){
	L[x]=l;R[x]=r;
	if(l==r){T[x]=0;return;}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);build(x<<1|1,mid+1,r);
	up(x);
}
void change(int x,int l,int r,int d){
	if(l<=L[x] && R[x]<=r) {tag[x]+=d;T[x]+=d*(R[x]-L[x]+1);return;}
	int mid=(L[x]+R[x])>>1;
	down(x);
	if(mid>=l) change(x<<1,l,r,d);
	if(mid<r) change(x<<1|1,l,r,d);
	up(x);
}
int query(int x,int l,int r){
	if(l<=L[x] && R[x]<=r) {return T[x];}
	int mid=(L[x]+R[x])>>1,ret=0;
	down(x);
	if(mid>=l) ret+=query(x<<1,l,r);
	if(mid<r) ret+=query(x<<1|1,l,r);
	return ret;
}
void solve(int s,int t,LL l,LL r){
	if(s>t) return ; 
	if(l==r) {for(int i=s;i<=t;i++) if(q[i].op==2) ans[q[i].id]=l;return;}
	int mid=(l+r)>>1,t1=0,t2=0;
	for(int i=s;i<=t;i++){
		if(q[i].op==1 && q[i].c>mid) change(1,q[i].l,q[i].r,1);
		if(q[i].op==2)q[i].tmp=query(1,q[i].l,q[i].r);
	}
	for(int i=s;i<=t;i++) if(q[i].op==1 && q[i].c>mid) change(1,q[i].l,q[i].r,-1); 
	for(int i=s;i<=t;i++) 
		if(q[i].op==2){
			if(q[i].cur+q[i].tmp>=q[i].c) q1[++t1]=q[i];
			else q[i].cur+=q[i].tmp,q2[++t2]=q[i];
		}else{ 
			if(q[i].c>mid) q1[++t1]=q[i];else q2[++t2]=q[i];
		}
	for(int i=1;i<=t1;i++) q[s+i-1]=q1[i];
	for(int i=1;i<=t2;i++) q[s+t1+i-1]=q2[i];
	solve(s,s+t1-1,mid+1,r);
	solve(s+t1,t,l,mid);
}
int main(){
	//freopen("3110.in","r",stdin);freopen("3110.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d%d",&qs[i].op,&qs[i].l,&qs[i].r,&qs[i].c),qs[i].id=i,q[i]=qs[i];
	build(1,1,n);
	solve(1,m,-INF,INF);
	for(int i=1;i<=m;i++) if(qs[i].op==2)printf("%d\n",ans[i]==INF?0:ans[i]);
	return 0;
}

BZOJ 1257: [CQOI2007]余数之和sum

注意一个性质 k%n=k-k/(k/n)

于是可以化简成n*k-(k/i)*i (1<=i<=min(n,k))

只要枚举k/i就可以了，令枚举的这个k/i为t

每一个满足 k/i=t的都在一个区间里

在这里说一下枚举的方法这个方法复杂度是$\sqrt{n}$

for(int a=1;a<=min(n,k);a= k/(k/a)+1){
	//todo 两个a之间就是对应k/i= k/a 的区间
}

代码如下

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n,k,ans,t;
LL min(LL a,LL b){return a<b?a:b;}
int main(){
	// freopen("1257.in","r",stdin);freopen("1257.out","w",stdout);
	scanf("%lld%lld",&n,&k);
	for(t=1;t<=min(n,k);t=k/(k/t)+1){
		LL nxt=min(k/(k/t),n);
		nxt=min(nxt,k);
		ans+=(k/t)*(t+ nxt )*(nxt-t+1)/2;
	}
	ans=n*k-ans;
	printf("%lld",ans);
	return 0;
}
for(int a=1;a<=min(n,k);a= k/(k/a)+1){
	//todo
}

BZOJ 1024: [SCOI2009]生日快乐

搜索

每次切的时候肯定是按比例切的所以搜索当前块切成的块数，传递x，y和块数就可以了

#include <cstdio>
#include <algorithm>
using namespace std;
int x,y,n;
double ans=0;
double cut(double x,double y,int k){//当前块的长和宽和需要切成的块数
	double ans1,ans2,ret=99999999;
	if(k==1) return x>y?x/y:y/x;
	for(int i=1;i<k;i++){
		ans1=max(cut(x/k*i,y,i),cut(x/k*(k-i),y,k-i)); //横着切，除法体现了按比例切分
		ans2=max(cut(x,y/k*i,i),cut(x,y/k*(k-i),k-i)); //竖着切
		ret=min(ans1,ret);
		ret=min(ans2,ret);
	}
	return ret;
}
int main(){
	//freopen("1024.in","r",stdin);freopen("1024.out","w",stdout);
	scanf("%d%d%d",&x,&y,&n);
	ans=cut((double)x,(double)y,n);
	printf("%.6f",ans);
	return 0;
}

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 1191: [HNOI2006]超级英雄Hero

二分图匹配从第一个开始找匹配找到第一个无法匹配的break并输出

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1010;
int help[N][2],from[N],n,m,ans,flag[N];
bool hungary(int x){
	for(int i=0;i<=1;i++) {
		int tmp=help[x][i];
		if(flag[tmp]) continue;else flag[tmp]=1;
		if(!from[tmp] || hungary(from[tmp])){from[tmp]=x;return true;}
	}
	return false;
}
int main(){
	//freopen("1191.in","r",stdin);freopen("1191.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&help[i][0],&help[i][1]);
	for(int i=1;i<=m;i++){
		memset(flag,0,sizeof(flag));
		if(hungary(i)) ans++;else break;
	}
	printf("%d",ans);
	return 0;
}

BZOJ 1088: [SCOI2005]扫雷Mine

暴搜每一个点是否是雷优化：每次搜之前判断一下可行性

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=10010;
int a[N],mine[N],n,cnt;
int check(int x){//计算这个位置现在已经有多少颗雷了
	int tmp=0;
	for(int i=x-1;i<=x+1;i++) tmp+=mine[i];
	return tmp;
}
void dfs(int x){
	if(x>n) {if(check(x-1)==a[x-1]) cnt++;return;}
	for(int i=0;i<=1;i++){
		mine[x]=i;
		if(x==1 || (check(x-1)==a[x-1] && check(x)<=a[x])) dfs(x+1);
		mine[x]=0;
	}
}
int main(){
	//freopen("1088.in","r",stdin);freopen("1088.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	dfs(1);
	printf("%d",cnt);
	return 0;
}

树状数组支持区间加减和求区间和的方法

在此感谢一下Claris教我这个方法,而我当时居然没看到……

CA爷说得好：学长给你讲啥你要好好听..就算听完不会也得问问..

设delta[i]=a[i]-a[i-1] 即delta[i]为delta的增量则$a[i]=\sum_{k=1}^{i}delta[k]$

修改的时候（令[s,t]+c）就很显然了 delta[s]+=c,delta[t+1]-=c;

比较麻烦的是求和

我们要求区间(1,t)的和 $\sum_{k=1}^{t}a[i]=\sum_{k=1}(t-k+1)delta[k]=(t+1)\sum_{k=1}^{t}delta[k]-(\sum_{k=1}^{t}k*delta[k])$

在这里我们只要快速计算出delta[k]的前缀和以及 k*delta[k]的前缀和即可用两个树状数组维护这两个值就好了

至此我们可以用两个树状数组动态维护数组的区间加减和求区间和了

代码的话以后等我写了再补

BZOJ 2190: [SDOI2008]仪仗队

有一个结论一个点(x,y)到原点经过gcd(x,y)个点自己试一下就知道了

于是这题只要求一下$(\sum_{i=1}^{n-1}phi(i)*2)+1$就好了 n的范围很小没必要用线性筛

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=40010;
int p[N],phi[N],n,vis[N],ans;
int main(){
	scanf("%d",&n);
	phi[1]=p[1]=1;
	for(int i=2;i<=n;i++) if(!vis[i]){
			p[i]=1;
			phi[i]=i-1;
			for(int j=2;j*i<=n;j++){
				if(!phi[i*j]) phi[i*j]=i*j;
				vis[i*j]=1;
				phi[i*j]=phi[i*j]*(i-1)/i;
			}
		}
	for(int i=1;i<n;i++) ans+=phi[i]*2;
	printf("%d",ans+1);
	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;
}

BZOJ 1070 [SCOI2007]修车

今天看到这题，这TM不是上星期BC的最后一题吗！！！！！！！！于是整个人都不好了，为什么我没有早点开始做BZOJ！！

于是用上星期在题解里看到的方法A了这题

这道题的思路是拆点

由于每一个人的选择只会对后边来修车的人有影响我们只要考虑这个人是倒数第几个人来修车的就好了

新建s，t。

将每个店员拆成n个点，其中第t个点代表倒数第t个修。比如我是第一个人是倒数第二个人来修车的，那么我这个选择就会让我自己和我后面的人总共等2*T[i][j]的时间，所以只要连一条容量为1的边，费用为倒数第k个 k*T[i][j]就好了。剩下来就是 s连到每个人容量1费用0，店员连到t，容量1，费用0就好了

巧妙的构图考试的时候根本没想到。

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=100010,INF=1049999654;
LL n,m,to[N*4],from[N*4],pre[N*4],now[N*2],cost[N*4],flow[N*4],tail=1,prev[N],dis[N],ans,inq[N],l,r,q[N],tmp;
void add(int u,int v,int f,int co){
	to[++tail]=v;from[tail]=u;flow[tail]=f;pre[tail]=now[u];now[u]=tail;cost[tail]=co;
	to[++tail]=u;from[tail]=v;flow[tail]=0;pre[tail]=now[v];now[v]=tail;cost[tail]=-co;
}
bool spfa(int s,int t){
	for(int i=1;i<=n+m*n+2;i++) inq[i]=0,dis[i]=INF,prev[i]=0;
	l=r=0;dis[s]=0;q[++r]=s;inq[s]=1;
	while(l<r){
		int x=q[(++l)%N];inq[x]=0;
		for(int i=now[x];i;i=pre[i]) if(flow[i]>0 && dis[to[i]]>dis[x]+cost[i]){
			dis[to[i]]=dis[x]+cost[i];prev[to[i]]=i;
			if(!inq[to[i]]) q[(++r)%N]=to[i],inq[to[i]]=1;
		}
	}
	return dis[t]!=INF;
}
void zg(int s,int t){
	LL f=INF;
	for(int i=t;i!=s;i=from[prev[i]]) f=min(f,flow[prev[i]]);
	for(int i=t;i!=s;i=from[prev[i]]) {flow[prev[i]]-=f;flow[prev[i]^1]+=f;ans+=f*cost[prev[i]];}
}
int main(){
	scanf("%lld%lld",&m,&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) {
			scanf("%lld",&tmp);
			for(int T=1;T<=n;T++) add(i,j*n+T,1,T*tmp);
		}
	}
	for(int i=n+1;i<=n+m*n;i++) add(i,n+m*n+2,1,0);
	for(int i=1;i<=n;i++) add(n+m*n+1,i,1,0);
	while(spfa(n+m*n+1,n+m*n+2)) zg(n+m*n+1,n+m*n+2);
	printf("%.2lf",(double)ans/n);
}