【题解】洛谷二月月赛div2

25%的时间获得了自己100%的得分

Posted by ethan-zhou on February 9, 2021

这次月赛感觉考的海星,估计是 WC 爆炸时失去的 RP 又回来了吧。前一个小时多点把 abc 都切了,后面都没骗到分(

T1 『MdOI R4』Fun

傻子题,直接模拟即可。

ll n,m,k;
ll arr[MXN];
inline void solve(){
	//codes
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		cin>>arr[i];
	ll cnt=0;
	for(int i=1;i<=n;i++){
		ll tmp;
		cin>>tmp;
		cnt+=tmp&arr[i];
	}
	cout<<n-cnt+min(cnt,m);
}

T2 『MdOI R4』Color

我写的是一个 dp,常数超大且细节巨多,不知道其他人咋写的,个个 40ms。我的做法思路倒是很好想:

\(dp[i][j][k]\ (j,k\in[0,3])\) 表示染色到 i 这列时

  • j=0 时,表示 (1,i) 没有被覆盖
  • j=1 时,表示 (1,i) 和 (1,i-1) 被一起盖住了
  • j=2 时,表示 (1,i) 和 (1,i+1) 被一起盖住了
  • j=3 时,表示 (1,i) 和 (2,i) 被一起该住了 k 代表的意义也类似,不过k表示的是 (2,i) 的状态

转移极度繁琐,但是有很多都是复制粘贴的,详见代码。

ll n,m,k;
ll arr[3][MXN];
char str[3][MXN];
bool dp[MXN][4][4];
inline void solve(){
    //codes
	cin>>n>>(str[1]+1)>>(str[2]+1);
	for(int i=1;i<=2;i++)
		for(int j=1;j<=n;j++)
			arr[i][j]=str[i][j]-'0';
	/*
	 * 0=空
	 * 1=向左
	 * 2=向右
	 * 3=向上/下
	 */
	for(int i=0;i<=n;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<4;k++)
				dp[i][j][k]=0;
	dp[0][3][3]=1;
	for(int i=0;i<n;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<4;k++){
				if(!dp[i][j][k])continue;

				if((arr[1][i+1]&arr[2][i+1])==0 && j!=2 && k!=2)
					dp[i+1][3][3]=1;

				
				for(int x=0;x<3;x++){
					if(x==0){
						if(j==2)continue;
						if(arr[1][i+1])continue;
					}
					if(x==1){
						if(j!=2)continue;
						if(arr[1][i+1]&arr[1][i])continue;
					}
					if(x==2){
						if(i+1==n)continue;
						if(arr[1][i+1]&arr[1][i+2])continue;
					}
					for(int y=0;y<3;y++){
						if(y==0){
							if(k==2)continue;
							if(arr[2][i+1])continue;
						}
						if(y==1){
							if(k!=2)continue;
							if(arr[2][i+1]&arr[2][i])continue;
						}
						if(y==2){
							if(i+1==n)continue;
							if(arr[2][i+1]&arr[2][i+2])continue;
						}
						dp[i+1][x][y]=1;
					}
				}
			}
	for(int j=0;j<4;j++)
		for(int k=0;k<4;k++)
			if(dp[n][j][k]){
				cout<<"RP"<<endl;
				return;
			}
	cout<<"++"<<endl;
}

T3 『MdOI R4』Kotori

我们需要维护每个选手是否有可能晋级到第 i 轮比赛,可以一轮一轮的递推。

第三轮比赛为例:

当前,每四名选手都决出了一个冠军。

  • 不妨设 1 号选手可以晋级到第三轮比赛,我们需要看他可不可能再晋级一轮。

  • 1 号选手本场比赛需要与前两轮中 5-8 号选手中决出的冠军对阵,所以我们希望这个冠军越越好(这样 1 号选手就更可能获胜)
  • 即求 5-8 号选手中,可以晋级到第三轮的最弱的选手

以上面的方法暴力就可以得到 $O(N^2\log(N))$ 的算法。但是我们发现 5-8 号中可能的最弱冠军会被多次调用(在递推 1-4 号的时候都会用到),所以我们可以开一个 mn 数组,并把 5-8 号中可能的最弱冠军存到 mn[5] 上即可,复杂度 $N\log(N)$。

代码实现很短:

#include<iostream>
using namespace std;
typedef long long ll;
const ll INF=1e18;
const ll MXN=3e5;
ll n,m,k;
ll arr[MXN],mn[MXN],tmp[MXN];
void cal(ll lv){
	ll t=1<<lv;
	ll tt=t<<1;
	ll ft=~(t-1);
	ll ft1=~(tt-1);

	for(int i=0;i<n;i+=t)tmp[i]=INF;
	for(int i=0;i<n;i++){
		ll ol=(i&ft)^t;
		ll cl1=i&ft1;
		if(arr[i]+m<mn[ol])
			arr[i]=INF;
		tmp[cl1]=min(tmp[cl1],arr[i]);
	}
	for(int i=0;i<n;i+=tt)
		mn[i]=tmp[i];
}
inline void solve(){
	cin>>k>>m;
	n=1<<k;
	for(int i=0;i<n;i++){
		cin>>arr[i];
		mn[i]=arr[i];
	}
	for(int i=0;i<k;i++){
		cal(i);
        if(arr[0]==INF){
            cout<<"Yoshino\n";
            return;
        }
    }
	cout<<"Kotori\n";
}
int main(){
	ll tq;cin>>tq;
	while(tq--)solve();
	return 0;
}

作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接



icon