DAY2

小田的消消乐游戏(题目传送门)

思路

用一个for来枚举一个分割点，如果分割点左边的区间首尾一致并且分割点右边的区间首尾一致，那么就是2次，否则-1。还要加一个特判，如果数组本来首尾就一致的情况 是1

代码

#include<bits/stdc++.h>
using namespace std;
int a[500010]; 
int main()
{
	freopen("num.in","r",stdin);
	freopen("num.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(n==1) cout<<-1;
	else if(a[1]==a[n]) cout<<1;
	else
	{
		for(int i=2;i<n-1;i++)
		{
			if(a[1]==a[i]&&a[i+1]==a[n])
			{
				cout<<2;
				return 0;
			}
		}
		cout<<-1;
	}
}

错误原因

当时没认真去想，只想着骗分

小田的气球爆炸啦(题目传送门)

思路

分类讨论，一共有4种情况，如果n是1那么,不会有气球爆炸,就是1；如果·n是2并且2种气球数一样，那么不会有有气球留下，否则只有1种能留下。如果有一种气球数比其他的都多，那么他就可以爆炸掉所有气球，只留下自己这一种。最后，只要这种气球数比1大 或者 其他气球刚好爆炸完 他就可以留下 再统计个数即可

代码

#include<bits/stdc++.h>
using namespace std;
long long a[100010];
int main()
{
	freopen("balloon.in","r",stdin);
	freopen("balloon.out","w",stdout);
	long long n,num,ans=-1,cnt=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		num=num+a[i];
		ans=max(ans,a[i]);
	}
	if(n==1) cout<<1;
	else if(n==2)
	{
		if(a[1]==a[2]) cout<<0;
		else cout<<1;
	}
	else if(ans>=num-ans)
	{
		cout<<1;
	}
	else
	{
		for(int i=1;i<=n;i++)
		{
			if(a[i]!=1||(num-a[i])%2==0) cnt++;
		}
		cout<<cnt;
	}
}

错误原因

思路没好好想，只想对部分。

小k的加减游戏(题目传送门)

思路

利用深搜，只要搜到一种就直接输出 否则输出-1（本题可以直接模拟，如果途中有一个变成了-1 直接输出no 否则把加1的输出出来）

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	string oz,jg;
	long long n,a,b,c;
	cin>>n>>a>>b>>c;
	for(int i=1;i<=n;i++)
	{
		cin>>oz;
		if(oz=="AB")
		{
			if(a<=b)
			{
				a=a+1;
				b=b-1;
				jg=jg+"A";
			}
			else
			{
				b=b+1;
				a=a-1;
				jg=jg+"B";
			}
		}
		if(oz=="AC")
		{
			if(a<=c)
			{
				a=a+1;
				c=c-1;
				jg=jg+"A";
			}
			else
			{
				c=c+1;
				a=a-1;
				jg=jg+"C";
			}
		}
		if(oz=="BC")
		{
			if(c<=b)
			{
				c=c+1;
				b=b-1;
				jg=jg+"C";
			}
			else
			{
				b=b+1;
				c=c-1;
				jg=jg+"B";
			}
		}
		if(a<0||b<0||c<0)
		{
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	for(int i=0;i<=jg.size()-1;i++) cout<<jg[i]<<endl;
}

错误原因 无

蓬莱山仙峰台(题目传送门)

思路

可以先将每一个观景台都标记为仙峰台，

代码

#include<bits/stdc++.h>
using namespace std;
int a[100010],st[100010];
int main()
{
    freopen("penglai.in","r",stdin);
	freopen("penglai.out","w",stdout);
    int n,m,cnt=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        st[i]=1;
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        if(a[u]>a[v]) st[v]=0;
        if(a[v]>a[u]) st[u]=0;
        else if(a[u]==a[v]) 
		{
			st[u]=0;
			st[v]=0;
		}
    }
    for(int i=1;i<=n;i++) if(st[i]==1)cnt++;
    cout<<cnt;
}

数学题1(题目传送门)

思路

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	freopen("math1.in","r",stdin);
	freopen("math1.out","w",stdout);
	int n,m,cnt=0;
	cin>>n>>m;
	for(int j=1;j<=m;j++)
	{	
		cnt=cnt+((n+j)/j/j); 
	}
++	cout<<cnt-1;
}

小z的徒步旅行(题目传送门)

思路

代码

#include
using namespace std;
const int MOD=1e9+7;
long long dp[1010][110],s[110],l[110],r[110];
int main()
{
	freopen("walk.in","r",stdin);
	freopen("walk.out","w",stdout);
	long long  m,n,ans=0;
	cin>>m>>n;
	for(int i=1;i<=m;i++) cin>>s[i];
	for(int i=1;i<=m;i++)
	{
		cin>>l[i];
		r[i]=l[i]+s[i];
	}
	dp[0][1]=1;
	//dp[i][j]是第i天到达第j个小屋的路径数
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			long long sum=0;
			for(int k=1;k<=m;k++)
			{
				sum+=(r[j]*r[k]-l[j]*l[k])*dp[i-1][k];
				sum=sum%MOD;
			}
			dp[i][j]=sum;
		}
	}
	for(int j=1;j<=m;j++)
	{
			ans+=dp[n][j];
			ans=ans%MOD;
	}
	cout<<ans;
}