2021牛客OI赛前集训营-提高组（第三场）-（重现赛）赛后总结

注：买的去年的题，本地OI赛制，排名按当年的计算。

越来越菜了，T3居然把freopen注释掉了，真是服了我这个老六……

A.变换

这个dp应该不难想，设 $d{p}_{i,j,0\mathrm{/}1\mathrm{/}2}dp\_\{i,j,0/1/2\}$ 表示已确定了 $ii$ 个数，有 $jj$ 个数是下降的，$00$ 表示当前数不下降且后一个数也不下降，$11$ 表示当前数下降，$22$ 表示当前数不下降且后一个数下降。

dp 方程：

$d{p}_{i,j,1}=d{p}_{i-1,j-1,2}+\min \{a_i,\min \{a_{i-1},a_{i+1}\}-1\}dp\_\{i,j,1\}=dp\_\{i-1,j-1,2\}+\backslash min\backslash \{a\_i,\backslash min\backslash \{a\_\{i-1\},a\_\{i+1\}\backslash \}-1\backslash \}$

$d{p}_{i,j,2}=\max \{d{p}_{i-1,j,0},d{p}_{i-1,j,1}\}dp\_\{i,j,2\}=\backslash max\backslash \{dp\_\{i-1,j,0\},dp\_\{i-1,j,1\}\backslash \}$

代码：

#include<bits/stdc++.h>
using namespace std;
 
const int MAXN=2005;
int a[MAXN];
long long dp[MAXN][MAXN][3];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    memset(dp,-0x3f,sizeof(dp));
    dp[0][0][0]=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<=k;++j)
        {
            if(i>1 && i<n && j>0) dp[i][j][1]=dp[i-1][j-1][2]+min(a[i],min(a[i-1],a[i+1])-1);
            dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][0]+(a[i]<a[i-1] && a[i]<a[i+1])*a[i]);
            if(i>2) dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][1]);
            dp[i][j][2]=max(dp[i][j][2],dp[i-1][j][0]);
            if(i>2) dp[i][j][2]=max(dp[i][j][2],dp[i-1][j][1]);
        }
    }
    long long ans=0;
    for(int i=0;i<=k;++i) ans=max(ans,dp[n][i][0]);
    cout<<ans;
    return 0;
}

B.交替

打表，不难发现当 $nn$ 为奇数时，答案为 ${\sum }_{i=0}^{\frac{n-1}{2}}{C}_{\frac{n-1}{2}}^2\times (-1{)}^i\times a_i\backslash sum\backslash limits\_\{i=0\}^\{\backslash frac\{n-1\}\{2\}\}C\_\{\backslash frac\{n-1\}\{2\}\}^2\backslash times(-1)^i\backslash times\; a\_i$。

$nn$ 为偶数，只要一次就可以变为奇数，然后按奇数的方式处理即可。

可以预处理阶乘及其逆元时间复杂度 $\mathcal{O}(n)\backslash mathcal\{O\}(n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
 
#define inv(x) quick_pow(x,MOD-2)
typedef long long ll;
const int MAXN=1e5+5;
const int MOD=1e9+7;
int a[MAXN],fac[MAXN],inv_fac[MAXN];
int quick_pow(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1) ret=(ll)ret*a%MOD;
        a=(ll)a*a%MOD,b>>=1;
    }
    return ret;
}
int C(int n,int m){return (ll)fac[n]*inv_fac[m]%MOD*inv_fac[n-m]%MOD;}
void upd(int &x,int y)
{
    x+=y;
    if(x>=MOD) x-=MOD;
    if(x<0) x+=MOD;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    if(n%2==0)
    {
        for(int i=1;i<n;++i) upd(a[i],a[i+1]);
        --n;
    }
    int m=(n-1)/2;
    fac[0]=1;
    for(int i=1;i<=m;++i) fac[i]=(ll)fac[i-1]*i%MOD;
    inv_fac[m]=inv(fac[m]);
    for(int i=m-1;i>=0;--i) inv_fac[i]=(ll)inv_fac[i+1]*(i+1)%MOD;
    int ans=0;
    for(int i=0;i<=m;++i) upd(ans,(ll)C(m,i)*a[i*2+1]%MOD*((i&1)?-1:1));
    cout<<ans;
    return 0;
}

C.打拳

正解 dp 式子没看懂，目前就只补了个 $\mathcal{O}(n(2^n)!)\backslash mathcal\{O\}(n(2^n)!)$ 的暴力。

代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=605;
int MOD;
vector<int>win;
int p[MAXN],dp[MAXN];
bool vis[MAXN];
int work(int l,int r)
{
	if(l==r) return p[l];
	int mid=(l+r)>>1;
	int x=work(l,mid),y=work(mid+1,r);
	if(x==1 && vis[y]){win.push_back(y);return x;}
	else if(y==1 && vis[x]){win.push_back(x);return y;}
	else return max(x,y);
}
int main()
{
	int n,m,k;
	cin>>n>>m>>k>>MOD;
	int x;
	for(int i=1;i<=m;++i) scanf("%d",&x),vis[x]=1;
	for(int i=1;i<=(1<<n);++i) p[i]=i;
	int ans=0;
	do
	{
		win.clear();
		win.push_back(0);
		if(work(1,(1<<n))!=1) continue;
		int len=win.size()-1,maxn=0;
		for(int i=1;i<=len;++i)
		{
			dp[i]=1;
			for(int j=1;j<i;++j)
				if(win[j]<win[i])
					dp[i]=max(dp[i],dp[j]+1);
			maxn=max(maxn,dp[i]);
		}
		if(maxn>=k) ++ans;
	}while(next_permutation(p+1,p+(1<<n)+1));
	cout<<ans;
	return 0;
}

D.扑克

本题有两个注意事项：

1. 最终的手牌若点数相同，则按花色从大到小输出，但枚举答案时，若两种花色都能胜智乃，如：智乃是方块，鸡尾酒出红桃或黑桃都能赢时，应优先选择红桃。

2. 智乃是不知道鸡尾酒有隐形眼镜的，因此鸡尾酒想象出的牌虽然不能是自己手里的，但可以是智乃手里的。

这样暴力枚举剩下两张牌是什么期望得分是 $7070$，但可能我还有些情况没有考虑到只拿下 $5050$（大样例过了）。

这里有一个小技巧，对于每个五元组给其赋一个权值，之后就可以根据权值直接比大小了。当然，要用14进制。

#include<bits/stdc++.h>
using namespace std;

const int MAXN=55;
const int INF=2e9;
struct node
{
	int num,col;
	friend bool operator < (const node x,const node y){return x.num==y.num?x.col<y.col:x.num<y.num;}
	friend bool operator > (const node x,const node y){return x.num==y.num?x.col>y.col:x.num>y.num;}
};
node card[MAXN],a[6],b[6],tmp[6],ans[6];
int number[200],color[200];
char out_num[200],out_col[200];
bool vis1[MAXN],vis2[MAXN],flag=0;
bool one_pair()
{
	for(int i=1;i<=4;++i) if(tmp[i].num==tmp[i+1].num) return 1;
	return 0;
}
bool two_pair()
{
	if((tmp[2].num==tmp[3].num && tmp[4].num==tmp[5].num) || (tmp[1].num==tmp[2].num && tmp[4].num==tmp[5].num) || (tmp[1].num==tmp[2].num && tmp[3].num==tmp[4].num)) return 1;
	return 0;
}
bool full_house()
{
	if((tmp[1].num==tmp[3].num && tmp[4].num==tmp[5].num) || (tmp[1].num==tmp[2].num && tmp[3].num==tmp[5].num)) return 1;
	return 0;
}
bool four_of_a_kind()
{
	if(tmp[1].num==tmp[4].num || tmp[2].num==tmp[5].num) return 1;
	return 0;
}
bool three_of_a_kind()
{
	if(tmp[1].num==tmp[3].num || tmp[2].num==tmp[4].num || tmp[3].num==tmp[5].num) return 1;
	return 0;
}
bool straight()
{
	for(int i=2;i<=5;++i) if(tmp[i].num!=tmp[i-1].num+1) return 0;
	return 1;
}
bool flush()
{
	for(int i=2;i<=5;++i) if(tmp[i].col!=tmp[1].col) return 0;
	return 1;
}
bool straight_flush()
{
	if(straight() && flush()) return 1;
	return 0;
}
bool royal_flush()
{
	if(!straight_flush()) return 0;
	if(tmp[1].num==10) return 1;
	return 0;
}
bool cmp(node x,node y){return x.num==y.num?x.col>y.col:x.num<y.num;}
int get_val()
{
	sort(tmp+1,tmp+6,cmp);
	int ret=0;
	if(royal_flush()) ret=1e9;
	else if(straight_flush()) ret=1163876+tmp[1].num-1;
	else if(four_of_a_kind())
	{
		if(tmp[1].num==tmp[4].num) ret=1163680+(tmp[1].num-1)*14+tmp[5].num-1;
		else ret=1163680+(tmp[2].num-1)*14+tmp[1].num-1;
	}
	else if(full_house())
	{
		if(tmp[1].num==tmp[3].num) ret=1163484+(tmp[1].num-1)*14+tmp[4].num-1;
		else ret=1163484+(tmp[3].num-1)*14+tmp[1].num-1;
	}
	else
	{
		if(straight()) ret=581728+tmp[1].num-1;
		else if(three_of_a_kind())
		{
			if(tmp[1].num==tmp[3].num) ret=578984+(tmp[1].num-1)*14*14+(tmp[5].num-1)*14+tmp[4].num-1;
			else if(tmp[2].num==tmp[4].num) ret=578984+(tmp[2].num-1)*14*14+(tmp[5].num-1)*14+tmp[1].num-1;
			else ret=578984+(tmp[3].num-1)*14*14+(tmp[2].num-1)*14+tmp[1].num-1;
		}
		else if(two_pair())
		{
			if(tmp[1].num==tmp[2].num && tmp[3].num==tmp[4].num) ret=576240+(tmp[3].num-1)*14*14+(tmp[1].num-1)*14+tmp[5].num-1;
			else if(tmp[1].num==tmp[2].num && tmp[4].num==tmp[5].num) ret=576240+(tmp[4].num-1)*14*14+(tmp[1].num-1)*14+tmp[3].num-1;
			else ret=576240+(tmp[4].num-1)*14*14+(tmp[2].num-1)*14+tmp[1].num-1;
		}
		else if(one_pair())
		{
			if(tmp[1].num==tmp[2].num) ret=537824+(tmp[1].num-1)*14*14*14+(tmp[5].num-1)*14*14+(tmp[4].num-1)*14+tmp[3].num-1;
			else if(tmp[2].num==tmp[3].num) ret=537824+(tmp[2].num-1)*14*14*14+(tmp[5].num-1)*14*14+(tmp[4].num-1)*14+tmp[1].num-1;
			else if(tmp[3].num==tmp[4].num) ret=537824+(tmp[3].num-1)*14*14*14+(tmp[5].num-1)*14*14+(tmp[2].num-1)*14+tmp[1].num-1;
			else ret=537824+(tmp[4].num-1)*14*14*14+(tmp[3].num-1)*14*14+(tmp[3].num-1)*14+tmp[2].num-1;
		}
		else for(int i=5;i>=1;--i) ret=ret*14+tmp[i].num-1;
		if(flush()) ret+=581742;
	}
	return ret;
}
int main()
{
	for(int i=2;i<=9;++i) number[i+'0']=i,out_num[i]=i+'0';
	number['T']=10,number['J']=11,number['Q']=12,number['K']=13,number['A']=14;
	out_num[10]='T',out_num[11]='J',out_num[12]='Q',out_num[13]='K',out_num[14]='A';
	color['S']=4,color['H']=3,color['C']=2,color['D']=1;
	out_col[4]='S',out_col[3]='H',out_col[2]='C',out_col[1]='D';
	int cnt=0;
	for(int i=2;i<=14;++i) for(int j=1;j<=4;++j) card[++cnt]=(node){i,j};
	int T;
	cin>>T;
	char ch[5];
	for(int t=1;t<=T;++t)
	{
		memset(vis1,0,sizeof(vis1));
		memset(vis2,0,sizeof(vis2));
		for(int i=1;i<=3;++i)
		{
			scanf("%s",ch);
			a[i]=(node){number[(int)ch[1]],color[(int)ch[0]]};
			int pos=lower_bound(card+1,card+cnt+1,a[i])-card;
			vis1[pos]=1;
		}
		for(int i=1;i<=3;++i)
		{
			scanf("%s",ch);
			b[i]=(node){number[(int)ch[1]],color[(int)ch[0]]};
			int pos=lower_bound(card+1,card+cnt+1,b[i])-card;
			vis2[pos]=1;
		}
		int maxb=0;
		for(int i=1;i<cnt;++i)
		{
			if(vis2[i]) continue;
			b[4]=card[i];
			for(int j=i+1;j<=cnt;++j)
			{
				if(vis2[j]) continue;
				b[5]=card[j];
				memcpy(tmp,b,sizeof(tmp));
				maxb=max(maxb,get_val());
			}
		}
		int ansa=2e9;
		for(int i=1;i<cnt;++i)
		{
			if(vis1[i]) continue;
			a[4]=card[i];
			for(int j=i+1;j<=cnt;++j)
			{
				if(vis1[j]) continue;
				a[5]=card[j];
				memcpy(tmp,a,sizeof(tmp));
				int now=get_val();
				if(now>maxb && now<ansa)
				{
					ansa=now;
					memcpy(ans,tmp,sizeof(ans));
				}
			}
		}
		if(ansa==INF) printf("-1\n");
		else
		{
			for(int i=1;i<=5;++i) putchar(out_col[ans[i].col]),putchar(out_num[ans[i].num]),putchar(' ');
			printf("\n");
		}
	}
	return 0;
}

//后记&总结：其实这场考试前期节奏把控的还不错，前两题基本是 1h 一道(包括写暴力程序对拍时间)，T3本来就只打了个暴力打算之后再想正解，没想到T4大模拟直接被带节奏了，不过好在之前已经写过2次德州扑克（包括多校那次刚好是我负责那道题），在最后10min中过了第一个大样例，然而由于没弄清楚这些注意事项第二个大样例怎么都调不过只能遗憾离场，仓促间忘记检查T3文件输入输出直接白给20，希望NOIP能够掌控好节奏，不被难题吓倒，发挥出正常水准。

笔者能力有限，有未述详尽或有误之处，欢迎指正。