AtCoder Regular Contest 066（缺d）

\(AT\_arc066\_a\)
https://www.luogu.com.cn/problem/AT_arc066_a
题解：长度为\(n\)的队列，其\(A\)数组固定，直接判断题目给定\(A\)数组是否符合题意即可。若符合题意，答案为\(2^{\frac{n}{2}}\)，否则答案为\(0\)。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N=1e5+10,P=1e9+7;

int n;
int cnt[N];

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=(LL)res*a%P;
		a=(LL)a*a%P;
		b>>=1;
	}
	return res;
}

int main(){
	cin >> n;
	for(int i=1; i<=n; i++){
		int x;
		cin >> x;
		cnt[x]++;
	}
	bool flag=1;
	for(int i=1-(n%2); i<=n-1; i+=2){
		if(i&&cnt[i]!=2) flag=0;
		if(!i&&cnt[i]!=1) flag=0;
	}
	if(!flag) cout << 0 << endl;
	else cout << qpow(2,n/2) << endl;
	return 0;
}

\(AT\_arc066\_b\)
https://www.luogu.com.cn/problem/AT_arc066_b
题解：设\(u=a\bigoplus b,v=a+b\)。
引理\(1\)：若只考虑满足\(a\& b=a\)的\((a,b)\)可保证答案不重不漏。
证明：移项得\(a=u\bigoplus b,v=b+u\bigoplus b\)，观察式子\(b+u\bigoplus b\)，发现对于\(u\)的二进制表示为\(1\)的位，\(b\)的取值对\(v\)无影响，于是钦定\(u\& b=u\)或钦定\(u\& b=0\)都可以保证不重不漏，这里钦定\(u\& b=u\)，那么\(a=u\bigoplus b\)，可得\(a\& b=a\)，证毕。
接下来考虑枚举\(v\)，令\(f(v)\)表示所有满足条件且\(v_1<=v\)的\((u_1,v_1)\)个数，考虑将当前\(a,b\)的最后一位去掉，由钦定条件\(a\& b=a\)知\(a,b\)最后一位只有可能是\((0,0),(0,1),(1,1)\)，于是有\(f(v)=f(\frac{v}{2})+f(\frac{v-1}{2})+f(\frac{v-2}{2})\)。
引理\(2\)：按\((0,0),(0,1),(1,1)\)划分的三子集内，不会出现相同的\((u,v)\)。
证明：反证法。假设在不同子集内出现相同的\((u,v)\),首先考虑\(v\)的奇偶性，于是只有\((0,0),(1,1)\)可能出现相同\((u,v)\)。由于\(1+1\)的进位，为保证下一位\(v\)的奇偶仍然相同，下一位只有可能是\((0,0),(0,1)\)或者\((0,1),(1,1)\),那么\(u=a\bigoplus b\)的条件就不满足了，证毕。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int P=1e9+7;

map<int,int> f;

int dp(int n){
	if(!n) return 1;
	if(f.count(n)) return f[n];
	return f[n]=(dp(n/2)+dp((n-1)/2)+dp((n-2)/2))%P;
}

signed main(){
	int n;
	cin >> n;
	f[0]=1,f[1]=2;
	cout << dp(n) << endl;
	return 0;
}

\(AT\_arc066\_c\)
https://www.luogu.com.cn/problem/AT_arc066_c
题解：先探究性质。
性质\(1\)：括号只会出现在减号之后，这是因为加号之后的括号是可去的。
性质\(2\)：不会出现相邻的括号对，这是因为括号间有符号才有意义。
性质\(3\)：括号只会嵌套两层。考虑形如\(a_1-(a_2-(a_3-(a_4)))=a_1-a_2+a_3-a_4=a_1-(a_2-a_3)-(a_4)\),所以三层以上嵌套都可被简化为\(1\)层或\(2\)层括号。
考虑\(dp\)，令\(f(i,j)\)为前\(i\)位，当前有\(j\)个未匹配的左括号的最大价值，考虑转移。
转移\(1\)：当前不加括号，\(f(i,j)=f(i-1,j)\pm a_i\)，\(a_i\)前符号根据原符号以及当前嵌套的括号数决定。
转移\(2\)：加一个左括号，\(f(i,j)=f(i-1,j-1)\pm a_i\)，\(a_i\)前符号根据当前嵌套的括号数决定。
转移\(3\)：加一个右括号，\(f(i,j)=f(i-1,j+1)\pm a_i\)，\(a_i\)前符号根据原符号以及当前嵌套的括号数决定。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N=1e5+10;

int n;
int a[2*N],f[N][3];
char s[2*N];

signed main(){
	cin >> n;
	for(int i=1; i<=2*n-1; i++)
		if(i%2) cin >> a[i];
		else cin >> s[i];
	for(int i=0; i<=n; i++)
		for(int j=0; j<=2; j++) f[i][j]=-1e18;
	f[0][0]=0;
	for(int i=1; i<=n; i++)
		for(int j=0; j<=2; j++){
			int cnt=j+(s[2*i-2]=='-');
			if(cnt%2) f[i][j]=max(f[i][j],f[i-1][j]-a[2*i-1]);
			else f[i][j]=max(f[i][j],f[i-1][j]+a[2*i-1]);
			if(s[2*i-2]=='-'&&j){
				cnt=j;
				if(cnt%2) f[i][j]=max(f[i][j],f[i-1][j-1]-a[2*i-1]);
				else f[i][j]=max(f[i][j],f[i-1][j-1]+a[2*i-1]);
			}
			if(j<2){
				cnt=j+1+(s[2*i-2]=='-');
				if(cnt%2) f[i][j]=max(f[i][j],f[i-1][j+1]-a[2*i-1]);
				else f[i][j]=max(f[i][j],f[i-1][j+1]+a[2*i-1]);
			}
		}
	cout << max(f[n][0],max(f[n][1],f[n][2])) << endl;
	return 0;
}

\(AT\_arc066\_d\)
https://www.luogu.com.cn/problem/AT_arc066_d