Pluto_Rabbit's Blog

蒟蒻妹纸一枚，轻拍

【蒟蒻】BZOJ-LYDSY的各种

Jacinth posted @ 2015年10月07日 14:14 in BZOJ-LYDSY with tags BZOJ , 628 阅读

感谢lbn187提供了一份非常详尽的BZOJ题目表，然后就造成了一场惊天动地的灾难

不知道是谁先开始刷的，然后就gg了，一天被逼着刷了11道（然而感觉好像忘了截图留念）

然而还是被mars_cat大神给碾压了，怪我？

于是这就是一个蒟蒻的记录（不要问我为什么这些题看上去都这么简单，因为窝太弱了！！）

BZOJ-2463

小学奥数（才不会说窝数学渣呢），不必多讲QAQ

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int n;
int main()
{
	scanf("%d",&n);
	while (n)
	{
		if (n&1) puts("Bob"); else puts("Alice"); scanf("%d",&n);
	}
	return 0;
}

BZOJ-1192

找规律，分别选取2^0,2^1,2^2……等数就可以满足要求咯

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int n,xx,tot,x;
int main()
{
	scanf("%d",&n);
	tot=0;
	while (n) tot++,n>>=1;
	printf("%d\n",tot);
	return 0;
}

BZOJ-1968

算是一道规律题吧，计算每个数在1到n中作为约数出现了几次，事实上就是[n/i]

加起来就可以啦

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int ans,n;
int main()
{
	scanf("%d",&n);
	ans=0;
	for (int i=1;i<=n;++i) ans+=n/i;
	printf("%d\n",ans);
	return 0;
}

BZOJ-2748

DP题，一开始弄成一维了，然后就WA

后来醒悟过来原来它只能从上一次的地方转移过来，然后就欢快得gg了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

int n,s,t,ans;
int a[100];
bool f[60][1010];

int main()
{
	scanf("%d%d%d",&n,&s,&t);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	memset(f,0,sizeof(f));
	f[0][s]=1;
	ans=0;
	for (int i=1;i<=n;++i)
	{
		bool ff=0;
		for (int j=0;j<=t;++j)
		if (f[i-1][j])
		{
			if (j-a[i]>=0) 
			{
				f[i][j-a[i]]=1,ff=1;
				if (i==n && j-a[i]>ans) ans=j-a[i];
			}
			if (j+a[i]<=t)
			{
				f[i][j+a[i]]=1,ff=1;
				if (i==n && j+a[i]>ans) ans=j+a[i];
			}
		}
		if (!ff) {
			puts("-1"); return 0;
		}
	}
	printf("%d\n",ans);
	return 0;
}

BZOJ-1088

DP题，考虑前两个如何安排的就可以推算出之后的所有了

感觉有点像分类讨论哎

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define NN 10010
using namespace std;

int a[NN],f[NN];
int n,ans;

int Check()
{
	for (int i=2;i<n;++i)
	{
		f[i+1]=a[i]-f[i]-f[i-1];
		if (f[i+1]<0) return 0;
	}
	if (a[n]-f[n]-f[n-1]!=0) return 0;
	return 1;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	if (a[1]==0)
	{
		memset(f,0,sizeof(f)); ans+=Check();
	}
	else
	if (a[1]==1)
	{
		memset(f,0,sizeof(f));
		f[1]=1; ans+=Check();
		memset(f,0,sizeof(f)); 
		f[2]=1; ans+=Check();
	}
	else
	{
		memset(f,0,sizeof(f));
		f[1]=f[2]=1; ans+=Check();
	}
	printf("%d\n",ans);
	return 0;
}

BZOJ-4143

按照日期排个序，算每一天最早结束和最晚开始的会议是否有重合就可以了（这算贪心吧？）

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;

struct REC
{
	int a,b,num,d;
};
REC s[500050];
int k,n,m,max_begin,min_end,max_begin_num,min_end_num;
bool cmp(REC xx,REC yy)
{
	return xx.d<yy.d;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].d),s[i].num=i;
	sort(s+1,s+1+n,cmp);
	k=0;
	for (int i=1;i<=m;++i)
	{
		while (s[k].d<i) k++;
		if (s[k].d!=i)
		{	puts("NIE"); continue;	}
		max_begin=s[k].a; min_end=s[k].b; max_begin_num=min_end_num=s[k].num;
		while (s[k+1].d==i)
		{
			k++;
			if (s[k].a>max_begin) max_begin=s[k].a,max_begin_num=s[k].num;
			if (s[k].b<min_end) min_end=s[k].b,min_end_num=s[k].num;
		}
		if (max_begin<=min_end) puts("NIE");
		else {
			printf("TAK %d %d\n",max_begin_num,min_end_num);
		}
	}
	return 0;
}

BZOJ-1207

又是一道DP题，打一次鼹鼠必定是从以前的某一次打鼹鼠转移过来的，f[i]表示打掉第i只鼹鼠时最多打死了几只，最后求一下最大值

据说某黑科技可以缩短时间（吗？）

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define NN 10010
using namespace std;

int n,m,ans;
int f[NN],dp[NN],x[NN],y[NN],t[NN];

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i) scanf("%d%d%d",&t[i],&x[i],&y[i]);
	f[1]=1; dp[1]=1; ans=1;
	for (int i=2;i<=m;++i)
	{
		f[i]=1;
		for (int j=i-1;j>=1;--j)
		{
			if (dp[j]+1<=f[i]) break;
			if (f[j]+1>f[i])
			{
				if (abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]) f[i]=f[j]+1;
			}
		}
		dp[i]=max(dp[i-1],f[i]);
		if (f[i]>ans) ans=f[i];
	}
	printf("%d\n",ans);
	return 0;
}

BZOJ-1083

最小生成树题，第一问的答案必定是n-1（怪我？），于是事实上就可以排个序，从小到大开始生成最小生成树，最后加进来的就是答案了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

struct REC
{
	int u,v,c;
};
REC a[10010];
int father[330];
int ans,n,m;

int find_father(int xx)
{
	return (xx==father[xx]?xx:(father[xx]=find_father(father[xx])));
}

bool cmp(REC xx,REC yy)
{
	return xx.c<yy.c;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i) scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].c);
	for (int i=1;i<=n;++i) father[i]=i;
	sort(a+1,a+1+m,cmp);
	ans=0;
	for (int i=1;i<=m;++i)
	{
		int xx=find_father(a[i].u),yy=find_father(a[i].v);
		if (xx!=yy)
		{
			father[xx]=yy;
			ans=a[i].c;
		}
	}
	printf("%d %d\n",n-1,ans);
	return 0;
}

============================这是一条欢快的分割线，据说以上题目NOIP普及组难度

BZOJ-1821

最小生成树&贪心辣

先排序，我们把边权最小的全分给n个部落的内部，然后剩下的边最小的就是答案。将边权较小的边分给k个部落，用并查集生成最小树，使得内部的边总是小于连到外部的边。然后分剩下k个点即可，剩下的k个点的那条边一定是部落之间最小的且最长的边。（语文渣只能拉一小段题解了，我错了）

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#define NN 1010
using namespace std;
struct REC
{
	int x,y;
};
REC p[NN];
struct Edeg
{
	int x,y,len;
};
Edeg e[NN*NN];
int tot,n,k,ans;
int father[NN];

int find_father(int xx)
{
	return xx==father[xx]?xx:(father[xx]=find_father(father[xx]));
}
int Len(int xx,int yy)
{
	int x=p[xx].x-p[yy].x,y=p[xx].y-p[yy].y;
	return x*x+y*y;
}

bool cmp(Edeg xx,Edeg yy)
{
	return xx.len<yy.len;
}
int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;++i) scanf("%d%d",&p[i].x,&p[i].y),father[i]=i;
	tot=0;
	for (int i=1;i<=n;++i)
		for (int j=i+1;j<=n;++j)
		{
			e[++tot].x=i; e[tot].y=j; e[tot].len=Len(i,j);
		}
	sort(e+1,e+tot+1,cmp); ans=0;
	for (int i=1;i<=tot;++i)
	{
		int xx=find_father(e[i].x),yy=find_father(e[i].y);
		if (xx!=yy)
		{
			if (n>k) n--,father[xx]=yy;
			else {printf("%.2f\n",sqrt(e[i].len)); return 0;}
		}
	}
	return 0;
}

BZOJ-1034

排个序，然后贪心，大的对战大的，反正总而言之要让a数组赢

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define NN 100010
using namespace std;

int a[NN],b[NN];
int n;

bool cmp(int xx,int yy) {return xx<yy;}

int work(int *xx,int *yy)
{
	int tmp=0,lx,ly,rx,ry;
	lx=ly=1; rx=ry=n;
	while (lx<=rx && ly<=ry)
	{
		if (xx[lx]>yy[ly])	{tmp+=2; lx++; ly++;}
		else if (xx[rx]>yy[ry])	{tmp+=2; rx--; ry--;}
		else {tmp+=(xx[lx]==yy[ry]); lx++; ry--;}
	}
	return tmp;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	for (int i=1;i<=n;++i) scanf("%d",&b[i]);
	sort(a+1,a+1+n,cmp); sort(b+1,b+1+n,cmp);
	printf("%d %d\n",work(a,b),2*n-work(b,a));
	return 0;
}

BZOJ-4145

状压DP，每个商店内跑一个背包就可以了，复杂度O（nm2^m)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

int m,n,mm;
int dp[110][1<<16],d[110],c[110][20];

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)
	{
		scanf("%d",&d[i]);
		for (int j=1;j<=m;++j) scanf("%d",&c[i][j]);
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0; mm=1<<m;
	for (int i=1;i<=n;++i)
	{
		for (int j=0;j<mm;++j) dp[i][j]=dp[i-1][j]+d[i];
		for (int k=1;k<=m;++k)
			for (int j=0;j<mm;++j)
				if (~j & (1<<(k-1)))
					dp[i][j|(1<<(k-1))]=min(dp[i][j|(1<<(k-1))],dp[i][j]+c[i][k]);
		for (int j=0;j<mm;++j) dp[i][j]=min(dp[i][j],dp[i-1][j]);
	}
	printf("%d\n",dp[n][mm-1]);
	return 0;
}

BZOJ-2563

考虑先手选择每个点对答案的影响

我们先预先把所有的权值都在初始答案中减掉，最后就是：

一个点如果不选，本身对答案的贡献是0；一个点如果选，本身对答案的贡献是2*w；

一条边如果两个端点都不选，对答案的贡献是0；如果两个端点中只选择一个，对答案的贡献是c；如果两个端点都选，对答案的贡献是2*c

计算所有点的贡献，然后排序轮流取

#include <iostream>
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NN 10010
using namespace std;

int ans,n,m,x,y,z;
int a[NN];

int main()
{
	scanf("%d%d",&n,&m);
	memset(a,0,sizeof(a)); ans=0;
	for (int i=1;i<=n;++i)
	{
		scanf("%d",&x); 
		ans-=x; a[i]=x<<1;
	}
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[x]+=z,a[y]+=z,ans-=z;
	}
	sort(a+1,a+1+n);
	for (int i=2;i<=n;i+=2)
		ans+=a[i];
	printf("%d\n",ans);
	return 0;
}

BZOJ-1303

数学题，计算前后多几个少几个的组合个数，然后前后互为相反数的乘起来

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define midd 100001
#define NN 200100
using namespace std;

int mid,ans,tmp,n,m;
int x[NN],y[NN],a[NN];

int main()
{
    scanf("%d%d",&n,&m); mid=0;
    memset(x,0,sizeof(x)); memset(y,0,sizeof(y));
    for (int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        if (a[i]==m) mid=i;
    }
    x[midd]=y[midd]=1;//注意初值
    tmp=midd;
    for (int i=mid-1;i>=1;--i)
    {
        if (a[i]<m) tmp--; else tmp++;
        x[tmp]++;
    }
    tmp=midd;
    for (int i=mid+1;i<=n;++i)
    {
        if (a[i]<m) tmp--; else tmp++;
        y[tmp]++;
    }
    ans=0;
    for (int i=midd-n;i<=midd+n;++i)
        ans+=y[i]*x[(midd<<1)-i];
    printf("%d\n",ans);
    return 0;
}

BZOJ-4001

算一下前面几个找规律（窝才不会说其实有严格证明的呢，然而其实窝数学渣，具体证明并没有看懂QAQcrying）

证明见此→_→： http://blog.miskcoo.com/2015/04/bzoj-4001

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int main()
{
	scanf("%d",&n);
	printf("%.9lf\n",(double)(n/2.0/(2*n-1)*(n+1)));
	return 0;
}

BZOJ-1024

DFS题，表示具体什么的详见程序吧（此题有压代码嫌疑）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int x,y,n;

double DFS(double xx,double yy,int nn)
{
	if (nn==1) return (double)(max(xx,yy)/min(xx,yy));
	double temp=1e30;
	for (int i=1;i<nn;++i)
	{
		double tmp=min(max(DFS(xx/nn*i,yy,i),DFS(xx/nn*(nn-i),yy,nn-i)),max(DFS(xx,yy/nn*i,i),DFS(xx,yy/nn*(nn-i),nn-i)));
		temp=min(tmp,temp);
	}
	return temp;
}

int main()
{
	scanf("%d%d%d",&x,&y,&n);
	printf ("%.6f\n",DFS(x,y,n));
	return 0;
}

BZOJ-1037

又是一道DP题

i表示选择了几个人，j表示选择了几个男生，x表示男生比女生多几个，y表示女生比男生多几个

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdlib>
#define mod 12345678
#define KK 25
#define NN 160
using namespace std;

int f[NN<<1][NN][KK][KK]; 
int ans,n,m,k;

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	memset(f,0,sizeof(f));
	f[0][0][0][0]=1;
	for (int i=0;i<n+m;++i)
		for (int j=0;j<=n;++j)
			for (int x=0;x<=k;++x)
				for (int y=0;y<=k;++y)
				if (f[i][j][x][y])
				{
					if (j+1<=n && x+1<=k) 
						f[i+1][j+1][x+1][max(y-1,0)]=(f[i+1][j+1][x+1][max(y-1,0)]+f[i][j][x][y])%mod;
					if (i-j+1<=m && y+1<=k) 
						f[i+1][j][max(x-1,0)][y+1]=(f[i+1][j][max(x-1,0)][y+1]+f[i][j][x][y])%mod;
				}
	ans=0;
	for (int i=0;i<=n;++i)
		for (int x=0;x<=k;++x)
			for (int y=0;y<=k;++y)
				ans=(ans+f[n+m][i][x][y])%mod;
	printf("%d\n",ans);
	return 0;
}

BZOJ-1296

DP题（此题有故意拉长代码嫌疑）

对每一块进行一个三次方的DP，然后再总的弄个背包

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#define NN 60
#define TT 2510
using namespace std;

int f[NN][NN];
int dp[NN][TT];
int sum[NN];
int n,m,t,ans;
char s[100];

int main()
{
	scanf("%d%d%d",&n,&m,&t);
	memset(f,0,sizeof(f));
	memset(dp,0,sizeof(dp));
	for (int i=1;i<=n;++i)
	{	
		scanf("%s",s+1);
		for (int j=1;j<=m;++j) 
			if (s[j]=='1')
				sum[j]=sum[j-1]+1;
			else sum[j]=sum[j-1];
		for (int j=1;j<=m;++j)
			for (int x=1;x<=m;++x)
			{
				f[x][j]=0;
				for (int y=0;y<x;++y)
				{
					int tmp; 
					tmp=sum[x]-sum[y];
					tmp=max(tmp,x-y-tmp);
					f[x][j]=max(f[x][j],f[y][j-1]+tmp);
				}
			}
		for (int j=1;j<=t;++j)
		{
			int tmp=min(m,j);
			for (int x=1;x<=tmp;++x)
			{
				dp[i][j]=max(dp[i][j],dp[i-1][j-x]+f[m][x]);
			}
		}
	}
	ans=0;
	for (int i=1;i<=t;++i) 
		ans=max(ans,dp[n][i]);
	printf("%d\n",ans);  
	return 0;
}

BZOJ-1029

主要是贪心，按照截止时间排序然后按次序判断剩余时间是否足够

若足够就加入，不足够则判断

若其持续时间比已加入的最大值长则放弃

若比最大值短，放弃最大值的那个把新的加进去

其中要用到堆来维护（STL大发好）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define NN 150100
using namespace std;

struct REC
{
	int ta,tb;
};
REC a[NN];

int n,recent;
bool cmp(const REC xx,const REC yy)
{
	return xx.tb<yy.tb;
}

priority_queue <int,vector<int>,less<int> > que;

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d%d",&a[i].ta,&a[i].tb);
	sort(a+1,a+1+n,cmp);
	recent=0;
	for (int i=1;i<=n;++i)
	{
		if (recent+a[i].ta<=a[i].tb)
		{
			recent+=a[i].ta;
			que.push(a[i].ta);
		}
		else
		if (que.size())
		{
			int tmp=que.top();
			if (tmp<a[i].ta) continue;
			que.pop();
			que.push(a[i].ta);
			recent-=(tmp-a[i].ta);
		}
	}
	printf("%d\n",que.size());
	return 0;
}

BZOJ-1216

堆的处理，就是写完有点晕

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

struct REC 
{
	int num,st,l,yx;
};
REC a[1000010];
struct NODE
{
	int t,d;
	
};
bool operator <(const NODE xx,const NODE yy) 
{
	if (a[xx.d].yx==a[yy.d].yx) return a[xx.d].st>a[yy.d].st;
	else return a[xx.d].yx<a[yy.d].yx;
}
struct rec
{
	int t,d;
};
bool cmp(rec xx,rec yy)
{
	return xx.t<yy.t;
}

rec ans[1000010];
priority_queue <NODE,vector<NODE> > que;
int k,now;

int main()
{
	k=1;
	while (scanf("%d%d%d%d",&a[k].num,&a[k].st,&a[k].l,&a[k].yx)!=EOF) ans[k].d=k,k++;
	a[k].st=0x7fffffff; now=0;
	for (int i=1;i<=k;++i)
	{
		int t=a[i].st-now;
		while (!que.empty() && que.top().t<=t)
		{
			now+=que.top().t;
			ans[que.top().d].t=now;
			t-=que.top().t;
			que.pop();
		}
		if (i==k) break;
		if (!que.empty() && t)
		{
			NODE xx=que.top(); que.pop();
			xx.t-=t; que.push(xx);
		}
		now=a[i].st;
		NODE x; x.t=a[i].l,x.d=i;
		que.push(x);
	}
	sort(ans+1,ans+k,cmp);
	for (int i=1;i<k;++i) printf("%d %d\n",a[ans[i].d].num,ans[i].t);
	return 0;
}

BZOJ-2456

神题一枚，据说窝删几个库就从Memory_Limit_Exceed到Accepted了

#include <cstdio>
using namespace std;
int now,t,n,xx;
int main() 
{
	scanf("%d",&n);
	now=0; t=0;
	while (n--)
	{
		scanf("%d",&xx);
		if (xx==now) t++;
		else
		{
			t--;
			if (t<=0) t=1,now=xx; 
		}
	}
	printf("%d\n",now);
	return 0;
}

BZOJ-2761

论如何使用set去重

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>
using namespace std;

set <int> se;
int T,n,xx,tot;
int a[50010];

int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		se.clear();
		tot=0;
		for (int i=1;i<=n;++i) 
		{
			scanf("%d",&xx);
			if (se.find(xx)!=se.end()) continue;
			else a[++tot]=xx,se.insert(xx);
		}
		for (int i=1;i<tot;++i) printf("%d ",a[i]);
		printf("%d\n",a[tot]);
	}
	return 0;
}

BZOJ-2005

数学题~~~不过要倒着来，然后暴力容斥

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define LL long long
using namespace std;

LL f[100010],ans;
int n,m;

int main()
{
	scanf("%d%d",&n,&m);
	ans=0;
	for (int i=min(n,m);i>=1;--i)
	{
		f[i]=(LL)(n/i)*(LL)(m/i);
		for (int j=2;j<=min(n,m)/i;++j) f[i]-=f[i*j];
		ans+=(f[i]*(2*i-1));
	}
	printf("%lld\n",ans);
	return 0;
}

BZOJ-1491

可以算是比较典型的Floyd题目了吧，只是在计算的同时要记录经过的边数

#include <iostream> 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;

int n,m,x,y,z;
int mp[110][110];
double a[110][110];
double ans[110];

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j) 
			mp[i][j]=1e9;
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		mp[x][y]=mp[y][x]=z;
		a[x][y]=a[y][x]=1;
	}
	for (int k=1;k<=n;++k)
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
			{
				if (mp[i][k]+mp[k][j]<mp[i][j])
					mp[i][j]=mp[i][k]+mp[k][j],a[i][j]=0;
				if (mp[i][j]==mp[i][k]+mp[k][j])
					a[i][j]+=a[i][k]*a[k][j];
			}
	for (int i=1;i<=n;++i) 
		a[i][i]=0;
	for (int k=1;k<=n;++k)
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
			{
				if (mp[i][j]==mp[i][k]+mp[k][j] && a[i][j]>0)
					ans[k]+=a[i][k]*a[k][j]/a[i][j];
			}
	for (int i=1;i<=n;++i) printf("%.3lf\n",ans[i]);
	return 0;
}

BZOJ-1025

事实上是求n的任意拆分最小公倍数有几种可能

#include <iostream> 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define NN 1001
#define LL long long
using namespace std;

int tot,n;
int prime[NN];
bool ff[NN];
LL dp[NN][NN];
LL ans;

int main()
{
	scanf("%d",&n);
	memset(ff,0,sizeof(ff));
	memset(prime,0,sizeof(prime));
	memset(dp,0,sizeof(dp));
	tot=0;
	for (int i=2;i<=NN;i++)
	{
		if (!ff[i]) prime[++tot]=i;
		for (int j=1;j<=tot;++j)
		{
			if (i*prime[j]>NN) break;
			ff[i*prime[j]]=1;
			if (i%prime[j]==0) break;
		}
	}
	dp[0][0]=1;
	for (int i=1;i<=tot;++i)
	{
		for (int j=0;j<=n;++j) 
			dp[i][j]=dp[i-1][j];
		for (int j=prime[i];j<=n;j*=prime[i])
			{
				for (int k=0;k<=n-j;++k)
					dp[i][k+j]+=dp[i-1][k];
			}
	}
	ans=0;
	for (int i=0;i<=n;++i) ans+=dp[tot][i];
	printf("%lld\n",ans);
	return 0;
}

BZOJ-2957

想着要学习一下分块的算法，然后就往下找到了某题上赫然写着分块二字，就开始被虐了TAT。。。蒟蒻第一次写分块啊，可惜发现自己把最后计算答案的地方写炸了，表示脑残了，早知道不手打二分直接用lower_bound了，害得窝对自己的二分很没有信心QAQ，然后浪费了好多查错的时间╮(╯▽╰)╭

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#define I int
#define D double
#define NN 100005
#define NNN 330
using namespace std;

struct REC
{
	int l;
	D num[NNN];
	void add(D xx)	{num[++l]=xx;}
	int finds(D xx)
	{
		int left=1,right=l,tmp=0;
		while (left<=right)
		{
			int mid=(left+right)>>1;
			if (num[mid]>xx) tmp=mid,right=mid-1; else left=mid+1;
		}
		return tmp;
	}
};
REC q[NN];
int n,m,x,y,len,cnt,now,ans,lenn[NN];
D w[NN],maxx;

int main()
{
	scanf("%d%d",&n,&m);
	len=(I)sqrt((D)n);
	while (len*len>n) len--;
	cnt=n/len+(n%len==0?0:1);
	for (int i=1;i<cnt;++i) lenn[i]=len;
	lenn[cnt]=n-(cnt-1)*len;
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		w[x]=(D)y/(D)x;
		now=(x-1)/len+1;
		maxx=0; q[now].l=0;
		for (int j=len*(now-1)+1;j<=len*(now-1)+lenn[now];++j)
		if (w[j]>maxx)
			q[now].add(w[j]),maxx=w[j];
		ans=q[1].l;
		maxx=q[1].num[ans];
		for (int j=2;j<=cnt;++j)
		if (q[j].num[q[j].l]>maxx)
		{
			ans+=q[j].l-q[j].finds(maxx)+1;
			maxx=q[j].num[q[j].l];
		}
		printf("%d\n",ans);
	}
	return 0;
}

BZOJ-1050

最小生成树，先排序，然后暴力枚举开头的那条边辣，求个最小值，约个分，不过要注意整除的情况辣

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define D double 
using namespace std;

struct REC
{
	int x,y,v;
};
REC a[5005];
int mn,mx,k,fa[505],n,m,s,t;
D minn;
int gcd(int a,int b){while (a)a ^= b ^= a ^= b %= a; return b;}
int FF(int xx) {return (fa[xx]==xx?xx:(fa[xx]=FF(fa[xx])));}
bool cmp(REC xx,REC yy) {return xx.v<yy.v;}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
	sort(a+1,a+1+m,cmp);
	scanf("%d%d",&s,&t);
	minn=0x7fffffff;
	for (int w=1;w<=m;++w)
	{
		for (int i=1;i<=n;++i) fa[i]=i;
		for (int i=w;i<=m;++i)
		{
			fa[FF(a[i].x)]=FF(a[i].y);
			if (FF(s)==FF(t))
			{
				D tmp=(D)a[i].v/(D)a[w].v;
				if (tmp<minn)
				{
					minn=tmp,mx=a[i].v,mn=a[w].v; break;
				}
			}
		}
	}
	if (minn==0x7fffffff) puts("IMPOSSIBLE");
	else
	{
		k=gcd(mn,mx);
		mn/=k,mx/=k;
		if (mn==1) printf("%d\n",mx); else	printf("%d/%d\n",mx,mn);
	}
	return 0;
}

BZOJ-1007

唔，判断写炸错了好久哎(╥╯^╰╥)

其实就是先按斜率排序，再将最小的两条线入栈，然后依次处理每条线，如果其与栈顶元素的交点在上一个点的左边，则将栈顶元素出栈。因为对如任意一个开口向上的半凸包，从左到右依次观察每条边和每个顶点，发现其斜率不断增大，顶点的横坐标也不断增大。 （以上来自网络）_(:зゝ∠)_

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define eps 1e-8
#define D double
#define NN 50010
using namespace std;

struct REC {D x,y; int num;};
REC a[NN],st[NN];
int tot,n,ans[NN];
bool cmp(REC xx,REC yy)
{
	if (fabs(xx.x-yy.x)<eps) return xx.y<yy.y;
	else return xx.x<yy.x;
}
D cacl(REC xx,REC yy) {return (D)(xx.y-yy.y)/(D)(yy.x-xx.x);}
bool Judge(REC xx,REC yy,REC zz) {return cacl(xx,yy)>=cacl(xx,zz);}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%lf%lf",&a[i].x,&a[i].y),a[i].num=i;
	sort(a+1,a+1+n,cmp);
	st[1]=a[1],tot=1,ans[1]=a[1].num;
	for (int i=2;i<=n;++i)
	{
		while (tot)
		{
			if (tot>=1 && fabs(st[tot].x-a[i].x)<eps) tot--; else
			if (tot>1 && Judge(st[tot-1],st[tot],a[i])) tot--; else break;
		}
		st[++tot]=a[i],ans[tot]=a[i].num;
	}
	sort(ans+1,ans+1+tot);
	for (int i=1;i<=tot;++i) printf("%d ",ans[i]); puts("");
	return 0;
}

BZOJ-2150

实际上就是二分图匹配吧，先处理一下能走的点弄成一张图，然后就暴力了

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define NN 55
using namespace std;

struct REC
{
	int ne,v;
};
REC e[NN*NN*4];
int head[NN*NN],match[NN*NN],a[NN][NN],m,n,r,c,sum=0,tot=0,ans=0;
bool vis[NN*NN];
char ch[NN];
void Build(int xx,int yy){e[++tot].ne=head[xx]; head[xx]=tot; e[tot].v=yy;}
void judge(int s,int xx,int yy)
{
	if (xx<=0 || yy<=0 || xx>m || yy>n) return;
	if (a[xx][yy]) Build(s,a[xx][yy]);
}
bool Check(int xx)
{
	for (int i=head[xx];i;i=e[i].ne)
	{
		int vv=e[i].v;
		if (!vis[vv])
		{
			vis[vv]=1;
			if (!match[vv] || Check(match[vv])) 
			{
				match[vv]=xx; return 1;
			}
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d%d%d",&m,&n,&r,&c);
	memset(a,0,sizeof(a)); memset(match,0,sizeof(match)); memset(e,0,sizeof(e));
	sum=0;
	for (int i=1;i<=m;++i)
	{
		scanf("%s",ch);
		for (int j=0;j<n;++j)
			if (ch[j]=='.') a[i][j+1]=++sum;
	}
	for (int i=1;i<=m;++i)
		for (int j=1;j<=n;++j)
		if (a[i][j])
		{
			judge(a[i][j],i+r,j+c); judge(a[i][j],i+r,j-c);
			judge(a[i][j],i+c,j+r); judge(a[i][j],i+c,j-r);
		}
	for (int i=1;i<=sum;++i)
	{
		memset(vis,0,sizeof(vis));
		if (Check(i)) ++ans;
	}
	printf("%d\n",sum-ans);
	return 0;
}

BZOJ-4029

感觉想起来还是挺有难度的贪心题。。。不过写起来还是蛮容易的辣

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;

int T,l,r,minn,ans;
int add(int xx)
{
	int sum=1;
	while (xx%10==0) xx/=10,sum*=10;
	return sum;
}

int calc(int xx)
{
	while (xx%10==0) xx/=10;
	int tmp=xx%10,a=0;
	while (xx) xx/=10,a++;
	if (tmp==5) return 2*a-1; else return 2*a;
}

int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d%d",&l,&r);
		minn=calc(l); ans=l;
		while (l<=r)
		{
			l+=add(l);
			if (l>r) break;
			int tmp=calc(l);
			if (tmp<minn) minn=tmp,ans=l;
		}
		printf("%d\n",ans);
	}
	return 0;
}

某天吐槽：一下子做这么多题，记录起来真累

从此以后感觉这里成了一个坑

Small_feed 评论 (1)
1
[回复]
Avatar_small
hhw 说:
2015年10月13日 19:41

%%%日切11题大爷


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter