2014-01-26

■ January Lunchtime 2014 17:59

全完です

1.

やるだけなんだけど i と j を1箇所ミスってて死亡

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pair P;
typedef pair<int,P> P1;
typedef pair P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
#define s second
#define rep(i,x) for(int i=0;i
int main()
{
	srand((unsigned int)time(NULL));
	int t; scanf("%d",&t);
	for(int i=0;iint n; ll s;
		scanf("%d %lld",&n,&s);if(n>=25) assert(0);
		P ora[31];
		for(int j=0;j> ora[j].f >> ora[j].s;
		}
		ll ret=0;
		for(int j=0;j<(1<0,val=0;
			for(int k=0;kif(((j>>k)&1))
				{
					wei+=ora[k].s;
					val+=ora[k].f;
				}
			}
			if(val<=s) ret=max(ret,wei);
		}
		printf("%lld\n",ret);
	}
}  

2.

やるだけ

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
#define s second
#define rep(i,x) for(int i=0;i
char str[100005];
int main()
{
	srand((unsigned int)time(NULL));
	scanf("%s",&str);
	int l=strlen(str);
		int v[5]={};
		map<char,int>ma;
		ma['C']=1;
		ma['H']=2;
		ma['E']=3;
		ma['F']=4;
		v[0]=INF;
		for(int i=0;iint f=ma[str[i]];
			if(v[f-1])
			{
				v[f-1]--;
				v[f]++;
			}
		}
		printf("%d\n",v[4]);
} 

3.

今までの列の最後の値をもつ。

新たな値が出てきたとき、今までの値のうちその値以下での最大値のところに代入する。

最後に0とINFでないものを数える。

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
#define s second
#define rep(i,x) for(int i=0;i
int dp[200002];
int main()
{
	srand((unsigned int)time(NULL));
	int n,ret=0;; scanf("%d",&n);
	for(int i=0;i<=100000;i++) {dp[i]=0; dp[i+100001]=INF;}
	for(int i=0;iint x; scanf("%d",&x);
		int idx=upper_bound(dp,dp+200002,x)-dp;
		idx--;
		dp[idx]=x;
	}
	for(int i=0;i<200002;i++)
	{
		if(dp[i]!=INF && dp[i]!=0)
		{
			ret++;
		}
	}
	cout << ret << endl;
} 

4.

dp[x]=min(dp[x-1],...,dp[x-k])*val[x]であるので

明らかにスライド最小値やるだけ。

値の大小比較は、そのものをもつと自明にoverflowするので

A(<10)*10^Bという形にしてdoubleでA,intでBをもてばよい。

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define mod 1000000007
#define f first
#define s second
#define rep(i,x) for(int i=0;i
int true_ten[100005];
double true_except[100005];
ll dp[100005],val[100005];
int deq[100005];
bool small(int id1,int id2)
{
	//dp[id1]>=dp[id2]?
	if(true_ten[id1]>true_ten[id2]) return 1;
	if(true_ten[id1]return 0;
	return true_except[id1]>=true_except[id2];
}
int main()
{
	srand((unsigned int)time(NULL));
	int n,k;
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&val[i]);
	}
	dp[1]=val[1];
	double v=(double)val[1];
	int kk=0;
	while(v>=10.0)
	{
		kk++;
		v/=10.0;
	}
	true_ten[1]=kk;
	true_except[1]=v;
	int s=0,t=1;
	deq[s]=1;
	//[s,t)
	for(int i=2;i<=n;i++)
	{
		int x=deq[s];
		dp[i]=dp[x]*val[i]%mod;
		true_ten[i]=true_ten[x];
		true_except[i]=(double)val[i]*true_except[x];
		while(true_except[i]>=10.0)
		{
			true_ten[i]++;
			true_except[i]/=10.0;
		}
		while(s1],i)) t--;
		deq[t++]=i;
		if(deq[s]==i-k)
		{
			s++;
		}
	}
	printf("%lld\n",dp[n]);
} 

ツイートする

■ PKU 3667 13:52

segtreeです。

各ノードに

「全部あいてるか全部埋まってるかそうでないか」

「左端の空き部屋」

「右端の空き部屋」

「最大の連続空き部屋」

「全部あいてるか全部埋まってるかそうでないか」を遅延評価するための値

をもって頑張ると解けます。

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
#define s second
#define rep(i,x) for(int i=0;i
#define SIZE (1<<16)
int n,m;
class hotel
{
	public:
	int left[2*SIZE];
	int right[2*SIZE];
	int maxv[2*SIZE];
	int lazy[2*SIZE];
	int state[2*SIZE];
	void init()
	{
		memset(left,0,sizeof(left));
		memset(right,0,sizeof(left));
		memset(maxv,0,sizeof(left));
		memset(lazy,0,sizeof(left));
		memset(state,0,sizeof(left));
	}
	void update(int k,int l,int r)
	{
		if(state[k*2+1]==1 && state[k*2+2]==1)
		{
			left[k]=right[k]=maxv[k]=r-l+1;
		}
		else if(state[k*2+1]==1)
		{
			left[k]=maxv[k*2+1]+left[k*2+2];
			right[k]=right[k*2+2];
			maxv[k]=maxv[k*2+1]+left[k*2+2];
		}
		else if(state[k*2+2]==1)
		{
			left[k]=left[k*2+1];
			right[k]=maxv[k*2+2]+right[k*2+1];
			maxv[k]=maxv[k*2+2]+right[k*2+1];
		}
		else
		{
			left[k]=left[k*2+1];
			right[k]=right[k*2+2];
			maxv[k]=max(max(maxv[k*2+1],maxv[k*2+2]),right[k*2+1]+left[k*2+2]);
		}
		if(maxv[k]==r-l+1) state[k]=1;
		else if(maxv[k]==0) state[k]=2;
		else state[k]=0;
	}
	//checkout
	void checkout(int a,int b,int k,int l,int r)
	{
		if(rreturn;
		if(a<=l && r<=b)
		{
			left[k]=right[k]=maxv[k]=max(0,min(r,n-1)-l+1);
			state[k]=lazy[k]=1;
			return ;
		}
		if(lazy[k] && l!=r)
		{
			state[k*2+1]=lazy[k*2+1]=lazy[k];
			state[k*2+2]=lazy[k*2+2]=lazy[k];
			if(lazy[k]==1)
			{
				left[k*2+1]=right[k*2+1]=maxv[k*2+1]=max(0,min((l+r)/2,n-1)-l+1);
				left[k*2+2]=right[k*2+2]=maxv[k*2+2]=max(0,min(r,n-1)-(l+r)/2);
			}
			else
			{
				left[k*2+1]=right[k*2+1]=maxv[k*2+1]=0;
				left[k*2+2]=right[k*2+2]=maxv[k*2+2]=0;
			}
			lazy[k]=0;
		}
		checkout(a,b,k*2+1,l,(l+r)/2);
		checkout(a,b,k*2+2,(l+r)/2+1,r);
		update(k,l,r);  
	}
	
	//checkin
	void checkin(int a,int b,int k,int l,int r)
	{
		if(rreturn;
		if(a<=l && r<=b)
		{
			left[k]=right[k]=maxv[k]=0;
			state[k]=lazy[k]=2;
			return ;
		}
		if(lazy[k] && l!=r)
		{
			state[k*2+1]=lazy[k*2+1]=lazy[k];
			state[k*2+2]=lazy[k*2+2]=lazy[k];
			if(lazy[k]==1)
			{
				left[k*2+1]=right[k*2+1]=maxv[k*2+1]=max(0,min((l+r)/2,n-1)-l+1);
				left[k*2+2]=right[k*2+2]=maxv[k*2+2]=max(0,min(r,n-1)-(l+r)/2);
			}
			else
			{
				left[k*2+1]=right[k*2+1]=maxv[k*2+1]=0;
				left[k*2+2]=right[k*2+2]=maxv[k*2+2]=0;
			}
			lazy[k]=0;
		}
		checkin(a,b,k*2+1,l,(l+r)/2);
		checkin(a,b,k*2+2,(l+r)/2+1,r);
		update(k,l,r);
	}
	int find(int a,int b,int k,int l,int r,int val)
	{
		if(lazy[k] && l!=r)
		{
			state[k*2+1]=lazy[k*2+1]=lazy[k];
			state[k*2+2]=lazy[k*2+2]=lazy[k];
			if(lazy[k]==1)
			{
				left[k*2+1]=right[k*2+1]=maxv[k*2+1]=max(0,min((l+r)/2,n-1)-l+1);
				left[k*2+2]=right[k*2+2]=maxv[k*2+2]=max(0,min(r,n-1)-(l+r)/2);
			}
			else
			{
				left[k*2+1]=right[k*2+1]=maxv[k*2+1]=0;
				left[k*2+2]=right[k*2+2]=maxv[k*2+2]=0;
			}
			lazy[k]=0;
		}
		if(maxv[k]return INF;
		if(l==r)
		{
			return l;
		}
		if(maxv[k*2+1]>=val) return find(a,b,k*2+1,l,(l+r)/2,val);
		else if(right[k*2+1]+left[k*2+2]>=val)
		{
			return (l+r)/2-(right[k*2+1]-1);
		}
		else
		{
			return find(a,b,k*2+2,(l+r)/2+1,r,val);
		}
	}
}seg;
int main()
{
	srand((unsigned int)time(NULL));
	scanf("%d %d",&n,&m);
	seg.init();
	seg.checkout(0,n-1,0,0,SIZE-1);
	for(int i=0;iint x; scanf("%d",&x);
		if(x==1)
		{
			int v; scanf("%d",&v);
			int res=seg.find(0,SIZE-1,0,0,SIZE-1,v);
			if(res==INF)
			{
				puts("0");
			}
			else
			{
				printf("%d\n",res+1);
				seg.checkin(res,res+v-1,0,0,SIZE-1);
			}
		}
		else
		{
			int v,pos; scanf("%d %d",&v,&pos);
			seg.checkout(v-1,v+pos-2,0,0,SIZE-1);
		}
	}
}

ツイートする