「JoyOI」五月有奖赛暨Loi 55 Round #1 Day2

2015年5月1日3,1810

抱枕被抢走了QAQ

为何ZJ神犇要来虐蒟蒻

控油刚捡肥皂

#include<cmath>
#include<cstdio>
#include<complex>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long 
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int bin[20];
int n,W,K;
int w[305],s[305],t[305];
int f[105][1024],g[105][1024];
int main()
{
	bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
	n=read();W=read();K=read();
	for(int i=1;i<=n;i++)
		w[i]=read(),s[i]=read(),t[i]=read();
	memset(f,-1,sizeof(f));
	memset(g,-1,sizeof(g));
	f[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=W;j++)
				for(int k=0;k<bin[K];k++)
					if(f[j][k]!=-1)
					{
						g[j][k]=max(g[j][k],f[j][k]);
						if(j+w[i]<=W)g[j+w[i]][k|bin[t[i]-1]]=max(g[j+w[i]][k|bin[t[i]-1]],f[j][k]+s[i]);			
					}
		for(int j=0;j<=W;j++)
			for(int k=0;k<bin[K];k++)
				f[j][k]=g[j][k],g[j][k]=-1;
	}
	int mx=0,ans=0;
	for(int i=0;i<=W;i++)
		for(int k=0;k<bin[K];k++)
			if(f[i][k]!=-1)
			{
				int tot=0;
				for(int j=0;j<K;j++)
					if(k&bin[j])tot++;
				if(tot>mx)mx=tot,ans=0;
				if(tot==mx)ans=max(ans,f[i][k]);
			}
	printf("%d %d\n",mx,ans);
	return 0;
}

#include<cmath>

#include<cstdio>

#include<complex>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int bin[20];

int n,W,K;

int w[305],s[305],t[305];

int f[105][1024],g[105][1024];

int main()

{

bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;

n=read();W=read();K=read();

for(int i=1;i<=n;i++)

w[i]=read(),s[i]=read(),t[i]=read();

memset(f,-1,sizeof(f));

memset(g,-1,sizeof(g));

f[0][0]=0;

for(int i=1;i<=n;i++)

{

for(int j=0;j<=W;j++)

for(int k=0;k<bin[K];k++)

if(f[j][k]!=-1)

{

g[j][k]=max(g[j][k],f[j][k]);

if(j+w[i]<=W)g[j+w[i]][k|bin[t[i]-1]]=max(g[j+w[i]][k|bin[t[i]-1]],f[j][k]+s[i]);

}

for(int j=0;j<=W;j++)

for(int k=0;k<bin[K];k++)

f[j][k]=g[j][k],g[j][k]=-1;

}

int mx=0,ans=0;

for(int i=0;i<=W;i++)

for(int k=0;k<bin[K];k++)

if(f[i][k]!=-1)

{

int tot=0;

for(int j=0;j<K;j++)

if(k&bin[j])tot++;

if(tot>mx)mx=tot,ans=0;

if(tot==mx)ans=max(ans,f[i][k]);

}

printf("%d %d\n",mx,ans);

return 0;

}

dC 和俄罗斯方块

我yy了一个奇怪的dp，高精模板太傻了就写了python

f=[[0]*5 for i in range(100005)];
n=int(raw_input());
f[1][0]=1;
for i in range(1,n+1):
    f[i][1]=f[i][1]+f[i][0];
    f[i][2]=f[i][2]+f[i][0];
    f[i+1][3]=f[i+1][3]+f[i][0]+f[i][0];
    f[i+1][0]=f[i+1][0]+f[i][1]+f[i][3];
    f[i+2][0]=f[i+2][0]+f[i][1]+f[i][2]+f[i][3];
print f[n+1][0];

f=[[0]*5 for i in range(100005)];

n=int(raw_input());

f[1][0]=1;

for i in range(1,n+1):

f[i][1]=f[i][1]+f[i][0];

f[i][2]=f[i][2]+f[i][0];

f[i+1][3]=f[i+1][3]+f[i][0]+f[i][0];

f[i+1][0]=f[i+1][0]+f[i][1]+f[i][3];

f[i+2][0]=f[i+2][0]+f[i][1]+f[i][2]+f[i][3];

print f[n+1][0];

Loi_M的Yo Gi Oh计划（by Loi_imcy）

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 1000000000
#define p(x,y) make_pair(x,y)
#define atk(a) a.first
#define sta(a) a.second
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,x,y,h1,h2,cnt;
vector<pair<int,int> >a1,a2,b1,b2;
pair<int,int>q1[205],q2[205];
int solve()
{
	cnt++;
	int tot=0;
	if(!b1.empty()&&a1.size()<5)
	{
		a1.push_back(b1.back());b1.pop_back();
		sort(a1.begin(),a1.end());
	}
	if(a1.size()&&a2.size())
	{
		for(int i=a1.size()-1,j=0;i>=0&&j<a2.size();i--,j++)
			if(atk(a1[i])-atk(a2[j])>0)tot+=atk(a1[i])-atk(a2[j]);
		if(tot>=h2)return 1;
		for(int i=a1.size()-1;i>=0;i--)
			for(int j=a2.size()-1;j>=0;j--)
				if(a1[i]>a2[j])
				{
					h2-=atk(a1[i])-atk(a2[j]);
					if(h2<=0)return 1;
					a2.erase(a2.begin()+j);
					sort(a2.begin(),a2.end());break;
			   }
	}
	while(b1.size()>6)b1.erase(b1.begin());
	if(!b2.empty()&&a2.size()<5)
	{
		a2.push_back(b2.back());b2.pop_back();
		sort(a2.begin(),a2.end());
	}
	cnt++;
	tot=0;
	if(a1.size()&&a2.size())
	{
		for(int i=a2.size()-1,j=0;i>=0&&j<a1.size();i--,j++)
			if(atk(a2[i])-atk(a1[j])>0)tot+=atk(a2[i])-atk(a1[j]);
		if(tot>=h1)return 2;
		for(int i=a2.size()-1;i>=0;i--)
			for(int j=a1.size()-1;j>=0;j--)
				if(a2[i]>a1[j])
				{
					h1-=atk(a2[i])-atk(a1[j]);
					if(h1<=0)return 2;
					a1.erase(a1.begin()+j);
					sort(a1.begin(),a1.end());break;
				}
	}
	while(b2.size()>6)b2.erase(b2.begin());
	return 0;
}
int main()
{
	n=read();
	for(int i=1;i<=5;i++)
	{
		y=read(),x=read();
		b1.push_back(p(x,y));
	}
	for(int i=1;i<=5;i++)
	{
		y=read(),x=read();
		b2.push_back(p(x,y));
	}
	for(int i=1;i<=n;i++)
	{
		y=read(),x=read();
		q1[i]=p(x,y);
		y=read(),x=read();
		q2[i]=p(x,y);
	}
	h1=h2=8000;
	for(int i=1;i<=200;i++)
	{
		if(i<=n)b1.push_back(p(atk(q1[i]),sta(q1[i])));
		if(i<=n)b2.push_back(p(atk(q2[i]),sta(q2[i])));
		sort(b1.begin(),b1.end());
		sort(b2.begin(),b2.end());
		int t=solve();
		if(t==1){printf("win %d\n",cnt);return 0;}
		if(t==2){printf("lose %d\n",cnt);return 0;}
	}
	puts("both are baka!");
	return 0;
}

100

101

102

103

104

105

106

107

#include<cmath>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define mod 1000000000

#define p(x,y) make_pair(x,y)

#define atk(a) a.first

#define sta(a) a.second

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,x,y,h1,h2,cnt;

vector<pair<int,int> >a1,a2,b1,b2;

pair<int,int>q1[205],q2[205];

int solve()

{

cnt++;

int tot=0;

if(!b1.empty()&&a1.size()<5)

{

a1.push_back(b1.back());b1.pop_back();

sort(a1.begin(),a1.end());

}

if(a1.size()&&a2.size())

{

for(int i=a1.size()-1,j=0;i>=0&&j<a2.size();i--,j++)

if(atk(a1[i])-atk(a2[j])>0)tot+=atk(a1[i])-atk(a2[j]);

if(tot>=h2)return 1;

for(int i=a1.size()-1;i>=0;i--)

for(int j=a2.size()-1;j>=0;j--)

if(a1[i]>a2[j])

{

h2-=atk(a1[i])-atk(a2[j]);

if(h2<=0)return 1;

a2.erase(a2.begin()+j);

sort(a2.begin(),a2.end());break;

}

while(b1.size()>6)b1.erase(b1.begin());

if(!b2.empty()&&a2.size()<5)

{

a2.push_back(b2.back());b2.pop_back();

sort(a2.begin(),a2.end());

}

cnt++;

tot=0;

if(a1.size()&&a2.size())

{

for(int i=a2.size()-1,j=0;i>=0&&j<a1.size();i--,j++)

if(atk(a2[i])-atk(a1[j])>0)tot+=atk(a2[i])-atk(a1[j]);

if(tot>=h1)return 2;

for(int i=a2.size()-1;i>=0;i--)

for(int j=a1.size()-1;j>=0;j--)

if(a2[i]>a1[j])

{

h1-=atk(a2[i])-atk(a1[j]);

if(h1<=0)return 2;

a1.erase(a1.begin()+j);

sort(a1.begin(),a1.end());break;

}

while(b2.size()>6)b2.erase(b2.begin());

return 0;

}

int main()

{

n=read();

for(int i=1;i<=5;i++)

{

y=read(),x=read();

b1.push_back(p(x,y));

}

for(int i=1;i<=5;i++)

{

y=read(),x=read();

b2.push_back(p(x,y));

}

for(int i=1;i<=n;i++)

{

y=read(),x=read();

q1[i]=p(x,y);

y=read(),x=read();

q2[i]=p(x,y);

}

h1=h2=8000;

for(int i=1;i<=200;i++)

{

if(i<=n)b1.push_back(p(atk(q1[i]),sta(q1[i])));

if(i<=n)b2.push_back(p(atk(q2[i]),sta(q2[i])));

sort(b1.begin(),b1.end());

sort(b2.begin(),b2.end());

int t=solve();

if(t==1){printf("win %d\n",cnt);return 0;}

if(t==2){printf("lose %d\n",cnt);return 0;}

}

puts("both are baka!");

return 0;

}

« 「JoyOI」五月有奖赛暨Loi 55 Round #1 Day1 「BZOJ4011」[HNOI2015] 落忆枫音 »

hzwer.com _ Home | http://hzwer.com

「JoyOI」五月有奖赛暨Loi 55 Round #1 Day2

分类目录

热门文章

Myfriends

近期评论

hzwer.com _ Home | http://hzwer.com

「JoyOI」五月有奖赛 暨Loi 55 Round #1 Day2

分类目录

热门文章

Myfriends

近期评论

「JoyOI」五月有奖赛暨Loi 55 Round #1 Day2