这次月赛感觉考的海星，估计是 WC 爆炸时失去的 RP 又回来了吧。前一个小时多点把 abc 都切了，后面都没骗到分（
T1 『MdOI R4』Fun
傻子题，直接模拟即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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) 的状态
转移极度繁琐，但是有很多都是复制粘贴的，详见代码。
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
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)$。
代码实现很短：
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
|
#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;
}
|