效实模拟赛3

发布于 2019-08-06  255 次阅读


2.5h六道题,真良(du)心(liu)

不过宋神AK了orz

  • T1

傻叉题(结论题),乱搞搞一下就好了

思路就看代码好了,写的很清楚了

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define int long long

using namespace std;

signed main()
{
	int t,x,y,z,maxn=0;
	cin>>t;
	while (t--)
	{
		cin>>x>>y>>z;
		maxn=max(max(x,y),z);
		maxn*=3;
		if ((maxn%2==0 && (x+y+z)%2==0) || (maxn%2==1 && (x+y+z)%2==1))
		{
			cout<<(maxn-(x+y+z))/2<<endl;
			continue;
		}
		else
		{
			maxn+=3;
			cout<<(maxn-(x+y+z))/2<<endl;
			continue;
		}
	}
	return 0;
}
  • T2

也是一道结论(贪心)题

思路就是连续的0转化成一个0,然后每次搞掉一个0就必须进行一次操作,判断一下哪个更优就好了,需要注意的是必须会有一次染色

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

int a[1000100];

int main()
{
	int n,x,y;
	cin>>n>>x>>y;
	int cnt=1;
	a[0]=-1;
	char c;
	for (int i=1;i<=n;i++)
	{
		cin>>c;
		if (c=='1') a[cnt++]=1;
		if (c=='0' && a[cnt-1]==0) continue;
		if (c=='0') a[cnt++]=0;
	}
	int ans=0;
	for (int i=1;i<cnt;i++)
		if (a[i]==0) ans++;
	if (x>=y) cout<<ans*y<<endl;
	else cout<<(ans-1)*x+y<<endl;
	return 0;
}
  • T3

就是去先枚举第一个翻或者不翻,然后贪心翻当前是1的下一个

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>

using namespace std;

int a[1000010],b[1000010];

int main()
{
	int t,n;
	cin>>t;
	while (t--)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		int ans1=0,ans2=0;
		cin>>n;
		if (n==1)
		{
			int x;
			cin>>x;
			if (x==0) cout<<0<<endl;
			else cout<<1<<endl;
			continue;
		}
		for (int i=1;i<=n;i++)
			cin>>a[i];
		for (int i=n;i>=1;i--)
			b[i]=a[i];
		b[1]=1-b[1],b[2]=1-b[2],ans2++;
		for (int i=1;i<=n-1;i++)
			if (a[i]==1)
			{
				for (int j=i;j<=i+2;j++)
					a[j]=1-a[j];
					ans1++;
			}
		for (int i=1;i<=n-1;i++)
			if (b[i]==1)
			{
				for (int j=i;j<=i+2;j++)
					b[j]=1-b[j];
					ans2++;
			}
		bool flag1=true,flag2=true;
		for (int i=1;i<=n;i++)
			if (a[i]==1) flag1=false;
		for (int i=1;i<=n;i++)
			if (b[i]==1) flag2=false;
		if (flag1 && flag2) cout<<min(ans1,ans2)<<endl;
		if (flag1==false && flag2==true) cout<<ans2<<endl;
		if (flag1==true && flag2==false) cout<<ans1<<endl;
		if (flag1==false && flag2==false) cout<<"Sad Yuu"<<endl;
	}
	return 0;
}
  • T4

img

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

long long f[1000000];
int a[1000000];

int main(){
	int T;
	cin >> T;
	int p=0;
	for (int i=1;i<=T;i++){
		cin >> a[i];
		p=max(p,a[i]);
	}
	f[1]=1;
	f[2]=3;
	f[3]=5;
	int ll=4,k=3,q=3;
	for (int i=4;i<=p;i++){
		f[i]=f[i-1]+ll;
		f[i]%=1000000007; 
		k--;
		if (k==0){
			q++;
			k=q;
			ll*=2;
			ll%=1000000007;
		}
	}
	for (int i=1;i<=T;i++)
		cout << f[a[i]] << endl;
}
  • T5

考试的时候没看这道题嘤嘤嘤,然后就没看出来这是个睿智01背包

#include<iostream>
#include<cstdio>

using namespace std;

int n,f[6666];
int w[6666],v[6666];

int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
		cin>>w[i]>>v[i];
	for (int i=1;i<=n;i++)
		for (int j=n;j>=w[i];j--)
			f[j]=max(f[j],f[j-w[i]]+v[i]);
	cout<<f[n]<<endl;
	return 0;
}
  • T6

就是一个区间DP啦,随便乱搞就好了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

int f[5333][5333];
int a[5333];
int n,t;

int main()
{
	cin>>t;
	while (t--)
	{
		cin>>n;
		for (int i=1;i<=n;i++)
			cin>>a[i];
		for (int i=1;i<=n;i++)
		{
			f[i][i]=1;
			f[i][i+1]=2;
		}
		for (int len=3;len<=n;len++)
			for (int l=1,r=len;r<=n;l++,r++)
					if (a[l]==a[r]) f[l][r]=f[l+1][r-1]+2;
					else f[l][r]=max(f[l+1][r-1],max(f[l+1][r],f[l][r-1]));
		cout<<f[1][n]<<endl;
	}
	return 0;
}

最美好的事情就是和OI一起成长呢。