AtCoder Beginner Contest 307

A - Weekly Records

Problem Statement

题意：告诉你有几个礼拜，问你每个礼拜走的路程和。

Solution

思路：按题意模拟，每7天加起来就行。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int n;
	cin>>n;
	ll sum = 0;
	for(int i = 1;i<=n*7;i++)
	{
		ll x;
		cin>>x;
		sum += x;
		if(i%7==0)
		{
			cout<<sum<<" ";
			sum = 0;
		}
	}
	return 0;
}

B - racecar

Problem Statement

题意：给你\(N\)个串，问你是否存在两个串连接起来是个回文串。

Solution

思路：暴力for每一个，两两连接，看看是不是。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
string s[110];
int main()
{
	cin>>n;
	for(int i = 1;i<=n;i++)
		cin>>s[i];
	for(int i = 1;i<=n;i++)
	{
		for(int j = i+1;j<=n;j++)
		{
			string t1 = s[i]+s[j];
			string t2 = s[j]+s[i];
			string t3 = t1,t4 = t2;
			reverse(t1.begin(), t1.end());
			reverse(t2.begin(), t2.end());
			if(t1==t3||t2==t4)
			{
				cout<<"Yes\n";
				return 0;
			}
		}
	}
	cout<<"No\n";
	return 0;
}

C - Ideal Sheet

Problem Statement

题意：给你三个图，要求你用前两个图拼成第三个图，且黑色(#)部分是要全部都保留，可以进行裁剪(不能裁剪掉黑色部分)，问能否拼成？

Solution

思路：emmm...是个大模拟，数据范围只有10，显然是暴力，但是感觉不好写QAQ。

枚举\(A\)图和\(B\)图的粘贴位置，暴力和目标图匹配，因为黑色全要，那还要判断一下黑色是不是都在。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
array<int ,3>h,w;
array<vector<string>,3>d;
array<int,3>blk{};
bool check(int x1,int y1,int x2,int y2)
{
	int cnt = 0;
	for(int i = 0;i<h[2];i++)
	{
		for(int j = 0;j<w[2];j++)
		{
			int t = (d[2][i][j]=='#');
			int b1 = (i>=x1&&j>=y1&&i-x1<h[0]&&j-y1<w[0]&&d[0][i-x1][j-y1]=='#');
			int b2 = (i>=x2&&j>=y2&&i-x2<h[1]&&j-y2<w[1]&&d[1][i-x2][j-y2]=='#');
			cnt += (b1+b2);
			if(t!=(b1||b2))return false;
		}
	}
	return (cnt==blk[0]+blk[1]);
}


int main()
{
	ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
	for(int i = 0;i<3;i++)
	{
		cin>>h[i]>>w[i];
		d[i].resize(h[i]);
		for(int j = 0;j<h[i];j++)
		{
			cin>>d[i][j];
			blk[i] += count(d[i][j].begin(), d[i][j].end(),'#');
		}
	}

	bool ok = false;
	for(int i = -10;i<=10;i++)
	{
		for(int j = -10;j<=10;j++)
		{
			for(int k = -10;k<=10;k++)
			{
				for(int l = -10;l<=10;l++)
				{
					if(check(i,j,k,l))
					{
						ok = true;
						break;
					}
				}
			}
		}
	}
	if(ok)cout<<"Yes\n";
	else cout<<"No\n";

	return 0;
}

D - Mismatched Parentheses

Problem Statement

题意：给你一个长度为\(N\)的字符串，包含小写字母和括号()。

在一对括号内的要删掉，问最后的串是什么样子。

Solution

思路：简单的栈模拟。碰到左括号和小写字母入栈,如果是左括号cnt++，遇到右括号如果cnt有，cnt--,到最近的那个(包含这个(都出栈，最后输出即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int n;
	cin>>n;
	string s;
	cin>>s;
	s = "?"+s;
	int cnt = 0;
	stack<int>st;
	for(int i = 1;i<=n;i++)
	{
		st.push(s[i]);
		if(s[i]=='(')
			cnt++;
		else if(s[i]==')')
		{

			if(cnt)
			{
				//cout<<"cnt="<<cnt<<endl;
				while(st.top()!='(')
				{
					st.pop();
				}
				st.pop();
				cnt--;
			}
		}
	}
	string t;
	while(!st.empty())
	{
		t += st.top();
		st.pop();
	}
	reverse(t.begin(), t.end());
	cout<<t<<endl;
	return 0;
}

E - Distinct Adjacent

Problem Statement

题意：有\(N\)个人，围成一个圈，这\(N\)个人用\(0\)~\(M\)去编号，且相邻两个的数字不能一样，问一共有多少种。

Solution

思路：先考虑线性的情况，对于第一个人有\(M\)种选择，后面的每一个人都是\((M-1)\)种选择，那答案显然就是\(M*(N-1)*(M-1)\)

但是现在是环形的，那我们要考虑第一个和倒数第二个人的颜色一不一样，这将影响最后一个人人颜色情况。

如果第一个和倒数第二个人颜色一样，答案就是\(M*(N-1)*(M-1)\)
如果第一个和倒数第二个人颜色不一样，答案就是\(M*(N-1)*(M-2)\)

考虑\(dp[i][0/1]\)表示考虑前\(i\)个人第一个和最后一个颜色一不一样(因为当前的最后一个就相当于我们上面讨论的倒数第二个，因为我们现在要放这一轮的最后一个)。

如果第一个和最后一个不一样，如果再放上一个还是和最后一个不一样，那\(dp[i+1][0] += dp[i][0]*(m-2)\)。

如果第一个和最后一个颜色一样，但再放上一个后第一个和当前最后一个不一样，那\(dp[i+1][0]+=dp[i][1]*(M-1)\)

如果再加入一个后，第一个和最后一个颜色一样，那当前最后一个颜色是确定的了，且相邻两个颜色要不同，那上一个一定和第一个不一样，那情况数是1，那\(dp[i+1][1] += dp[i][0]*1\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 1e6+10;
ll dp[N][3];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
	ll n,m;
	cin>>n>>m;
	dp[1][1] = m;
	for(int i = 1;i<n;i++)
	{
		dp[i+1][0] += dp[i][0]*(m-2);
		dp[i+1][0] += dp[i][1]*(m-1);
		dp[i+1][1] += dp[i][0];
		dp[i+1][0]%=mod;
		dp[i+1][1]%=mod;
	}
	cout<<(1ll*dp[n][0]) % mod<<endl;
	
	return 0;
}