8

【题解】洛谷二月月赛div2

 3 years ago
source link: https://blog-e.tk/2021/02/09/%E9%A2%98%E8%A7%A3-%E6%B4%9B%E8%B0%B7%E4%BA%8C%E6%9C%88%E6%9C%88%E8%B5%9Bdiv2/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

这次月赛感觉考的海星，估计是 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∈[0,3])dp[i][j][k](j,k∈[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(N2log(N))O(N2log⁡(N)) 的算法。但是我们发现 5-8 号中可能的最弱冠军会被多次调用（在递推 1-4 号的时候都会用到），所以我们可以开一个 mn 数组，并把 5-8 号中可能的最弱冠军存到 mn[5] 上即可，复杂度 Nlog(N)Nlog⁡(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
本文为作者原创，转载请注明出处：本文链接

阅读量 22

来发评论吧~
Powered By Valine
v1.4.4

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK