2017-07-27 • 于 2017 阅读

day5

exam
简单的贪心
注意细节，long long就可以ac了

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define D "%lld"
#define prf printf
#define scf scanf
#define ll long long
ll n,r,v,t,tot,ans;
struct stu{
	ll x,y;
}s[199999];
int cmp(const stu a,const stu b){
	if(a.y<b.y)
	return 1;
	return 0;
} 
int main()
{
	freopen("exam.in","r",stdin);
	freopen("exam.out","w",stdout);
	scf(D D D,&n,&r,&v);
	for(int i=1;i<=n;i++)
	{
		scf(D D,&s[i].x,&s[i].y);
		ans+=s[i].x;
	}
	sort(s+1,s+n+1,cmp);
	
	while(ans<v*n)
	{
		t++;
		
		if((ans+(r-s[t].x))<=v*n)
		ans+=r-s[t].x,tot+=(r-s[t].x)*s[t].y;
		else tot+=(v*n-ans)*s[t].y,ans=v*n;
	}
	prf(D,tot);
}

lift
电梯，之前不懂什么叫滚动数组，现在明白了
就是用两个数组，防止重复使用空间
这个题是动态规划
很容易想到
f[j]+=f[i]
j是每一个可以由i扩展到的地方
这样就可以用n^3的算法做了
第一层枚举第几次乘电梯
第二层枚举当前位置
第三层枚举可以到的电梯，加上值
这样能过60的数据
但区间加值可以用差值维护来优化这样局可以n^2完成了，就ac了
注意要减去之前的值因为转移出去的话要清零
60

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
ll tot;int n,a,b,k;
const int p=1000000007;ll f[5099],w[5999];
int main()
{
	freopen("lift.in","r",stdin);
	freopen("lift.out","w",stdout);
	scanf("%d%d%d%d",&n,&a,&b,&k);
	
	f[a]=1;
	for(int i=1;i<=k;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(j!=b&&f[j])
			{
				for(int q=1;q<abs(j-b);q++)
				{
					if(j+q!=b)
					w[j+q]+=f[j],w[j+q]%=p;
					if(j-q!=b)
					w[j-q]+=f[j],w[j-q]%=p;
				}
			}
		}
		for(int j=1;j<=n;j++)	
		{
			f[j]=w[j];
			w[j]=0;
		}
	}
	for(int i=1;i<=n;i++)
	{
		tot+=f[i];
		tot%=p;
	}
	printf("%lld",tot%p);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

100

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define D "%d"
#define prf printf
#define scf scanf
#define ll long long
#define p 1000000007
int n,a,b,k;
int f[5999][2],e,g,ans,nl[19999],nr[19999];
int main(){
	//freopen("lift.in", "r", stdin);
	//freopen("lift.out", "w", stdout);
	scf(D D D D,&n,&a,&b,&k);
	
	 e=0,g=1;
	f[a][e]=1;
	for(int i=1;i<=n;i++)
	{
		int dis=abs(i-b);
		nl[i]=max(1,i-dis+1);
		nr[i]=min(n,i+dis-1);
	}

	for(int i=1;i<=k;i++)
	{
		for(int j=1;j<=n;j++)
		f[j][g]=0;
	 	for(int j=1;j<=n;j++)
	 	{
	 		
	 			(f[nl[j]][g]+=f[j][e])%=p;
	 			(f[nr[j]+1][g]-=f[j][e])%=p;
	 	}
	 	for(int j=1;j<=n;j++)
	 	(f[j][g]+=f[j-1][g])%=p;
	 	for(int j=1;j<=n;j++)
	 	(f[j][g]-=f[j][e])%=p;
	 	for(int j=1;j<=n;j++)
	 	printf("%d ",f[j][e]);
	 	printf("\n");
	 	swap(e,g);
	}
	for(int i=1;i<=n;i++)
	
	(ans+=f[i][e])%=p;
	prf(D,(ans+p)%p);
}

game
枚举一个小局的t
用二分查找找先的t分的，统计胜的局数
胜的多的就是答案
但有几种情况不行
1.两人胜的局数相同
2.胜得多的不是最后胜的
3.打到最后也没结束
这样就可以做完了

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
int n,a[199999];int w1,w2,ww1,ww2,www,ans,ans1[199999],ans2[109999],s1[190099],s2[100100];
//int check(int j,int x,int t)
struct stu{
	int s,t;
}e[199199];
int cmp(const stu a,const stu b)
{
	if(a.s<b.s) return 1;
	if(a.s==b.s&&a.t<b.t)return 1;
	return 0;
}
int main(){
	freopen("game.in ","r",stdin);
	freopen("game.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]==1)
		s1[i]=s1[i-1]+1;
		else s1[i]=s1[i-1];
		if(a[i]==2)
		s2[i]=s2[i-1]+1;
		else s2[i]=s2[i-1];
	}
	for(int t=1;t<=n;t++)
	{
		w1=w2=ww1=ww2=www=0;
		int r=0;
		while(r<n)
		{
		w1=lower_bound(s1+1,s1+n+1,t+s1[r])-s1;
		w2=lower_bound(s2+1,s2+n+1,t+s2[r])-s2;
		//printf("%d %d\n",w1,w2);
		r=min(w1,w2);
		if(w1<w2)
		ww1++,w1=0,w2=0,www=1;
		if(w2<w1)ww2++,w2=0,w1=0,www=2;
		} 
		//printf("   %d %d\n",ww1,ww2);
		if(ww1!=ww2&&w2==0&&w1==0&&((ww2>ww1&&www==2)||(ww1>ww2&&www==1))) 
		ans++,e[ans].t=t,e[ans].s=max(ww1,ww2);
	}
	printf("%d\n",ans);
	sort(e+1,e+ans+1,cmp);
	for(int i=1;i<=ans;i++)
	{
		printf("%d %d\n",e[i].s,e[i].t);
	}
}

wspl09876

day5

day6

摄像头