A.淘宝商品价格大PK

题意

给定一个长度为$n(0\leq n\leq 100)$的数组，任意去掉一个数使得整个数组的最长上升子序列长度减少，求这样的数的个数。

方法

• 因为n的数据量很小，我们只要先算出原数组的最长上升子序列，然后逐个去掉每个数算最长上升子序列与原数组比较，如果小了则加到答案里面。
• 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int n,a[maxn],now[maxn],max_l,ans,tmp;
//now是一个临时数组，求最长上升子序列就是对这个数组求的
//max_l为原数组的最长上升子序列的长度
//ans为答案
//tmp为去掉任意一个数后的数组的最长上升子序列
int lis(int len){//len为数组长度，返回值为最长上升子序列的长度
	int dp[maxn],max_t=0;
	for(int i=0;i<len;i++){
		dp[i]=1;
		for(int j=0;j<i;j++){
			if(now[j]<now[i]){
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
		max_t=max(dp[i],max_t);
	}
	return max_t;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=0;i<n;i++){//输入
		cin>>a[i];
	}
	for(int i=0;i<n;i++){//将原数组复制到now中
		now[i]=a[i];
	}
	max_l=lis(n);
	for(int i=0;i<n;i++){
		int pos=0;
		for(int j=0;j<n;j++){
			if(j!=i){//去掉下标为i的数获得新的临时数组
				now[pos++]=a[j];
			}
		}
		tmp=lis(n-1);
		if(tmp<max_l){//比较长度是否变小
			ans++;
		}
	}
	cout<<ans<<"\n";
}

D.阿里巴巴协助征战SARS

题意

给定长度$n$，构造长度为$n$的字符串满足如下条件：字符串只包含$A、T、C、G$；$A$出现偶数次（包括$0$）；$C$出现偶数次（包括$0$），求这样的字符串的个数。

方法

• 首先是先看了$BCD$有什么不同，发现只有$n$的范围不一样，而且D题的$n\leq 10^{10^5}$，然后题目大概可以排列组合来做，而排列组合又跟$2^n$有关，通过这两个线索就想到了欧拉降幂。
• 然后大概写了一下排列组合的公式，大概长这样

$$
\sum_{a=1}^nC_n^a[a\%2=0]\sum_{b=1}^aC_a^b[b\%2=0]2^{n-a}
$$

• 所以应该是两个$2^n$变化一点点乘起来的，不然就不容易计算，也只有欧拉降幂可以支持这么大的n。
• 然后看样例推测，当时通过$n=1，2，3$没猜出公式，然后就手算了一下$n=4$的情况，算出来是$72$。然后就猜公式是$(2^{n-1})*(2^{n-1}+1)$。
• 然后验证了一下样例的$n=100$的情况，$A$了！
• 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll maxn=1e5+5,m=1e9+7;
ll ans;
char s[100005];
ll qpow(ll a,ll b){//快速幂
	ll r=1,base=a;
	while(b){
		if(b%2){
			r=r*base%m;
		}
		base=base*base%m;
		b>>=1;
	}
	return r;
}

ll mod(){//求b%f(m)
	ll len=strlen(s),ans=0;
	for(int i=0;i<len;i++){
		ans=ans*10+(s[i]-'0');
		ans%=(m-1);
	}
	return ans;
}

int main(){
	scanf("%s",s);
	while(s[0]!='0'){
		ll t=mod();
		ans=qpow(2,t-1)*(qpow(2,t-1)+1)%m;
		printf("%lld\n",ans);
		scanf("%s",s);
	}
}

B题的dp方法

• $dp[i][0…3]$表示长度为$i$的的字符串，第二位$0$表示$A、C$出现的次数为偶数次；$1$表示$A$出现奇数次，$C$出现偶数次；$2$表示$C$出现奇数次，$A$出现偶数次；$3$表示$A、C$出现的次数为奇数次。
• 初始状态：$dp[1][0]=2,dp[1][1]=1,dp[1][2]=1,dp[1][3]=0$。
• 状态转移方程：

$$
\begin{cases}
dp[i][0]=dp[i-1][0]*2+dp[i-1][1]+dp[i-1][2]\\
dp[i][1]=dp[i-1][0]+dp[i-1][3]+dp[i-1][1]*2\\
dp[i][2]=dp[i-1][0]+dp[i-1][3]+dp[i-1][2]*2\\
dp[i][3]=dp[i-1][1]+dp[i-1][2]+dp[i-1][3]*2
\end{cases}
$$

return 0;

本文链接：
https://luojinrong.github.io/2019/06/01/2019计蒜之道初赛第三场/