AT_abc365_d [ABC365D]

前言

又是一道 dp 题……

翻译

先规定石头剪刀布的规则为：R 打败 S，S 打败 P，P 打败 R，出相同的字符视为平局。下简记三种出发为「手法」。

给出对方的 \(n\) 次出法的序列（一个长度为 \(n\) 字符串），要求你出一个对策，满足：

• 你不会输任何一局（若平局不算为输给对方）。
• 你出的相邻两个手法不能重复。

数据保证存在一种策略满足以上要求。

思路

引入

为什么不是贪心？

一种可能的思路是碰到对手一样的出发就隔一个赢一次，但是很幸运的没有过第 3 个样例。

各种分类后发现根本没有通用的方法，故采用 dp。

众所周知 dp 很多都是将暴力指数级算法优化成很多维的算法。但这道题只允许线性或 \(O(n\log n)\) 的算法通过，故确定复杂度且确定为线性 dp。

动态规划

若出了手法 \(s\) 出了下一个就不能 \(s\)，只能出不同于 \(s\) 的另外两个，不妨设另外两个为 \(s_1,s_2\)。

故转移为：\(dp(i,s)=dp(i+1,s_1)+dp(i+1,s_2)\)

其中 \(i\) 表示决策到了第 \(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

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;i++)

using namespace std;

typedef long long ll;
typedef double db;

const int N=2e5+23;

int n;
string s;
int mem[N][5],c[N];

/*
Paper 1
Sissor 2
Rock 3
*/

inline int dp(int d,int lst)
{
    int& ans=mem[d][lst];
    if(ans!=-1) return ans;
    if(d==n+1) return 0;
    int ans1=0,ans2=0;
    if(c[d]==1)
    {
        if(lst!=2) ans1=1+dp(d+1,2);
        if(lst!=1) ans2=dp(d+1,1);
    }
    if(c[d]==2)
    {
        if(lst!=3) ans1=1+dp(d+1,3);
        if(lst!=2) ans2=dp(d+1,2);
    }
    if(c[d]==3)
    {
        if(lst!=1) ans1=1+dp(d+1,1);
        if(lst!=3) ans2=dp(d+1,3);
    }
    return ans=max(ans1,ans2);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin>>n>>s;
    s=' '+s;
    rep(i,1,n)
    {
        if(s[i]=='P') c[i]=1;
        if(s[i]=='S') c[i]=2;
        if(s[i]=='R') c[i]=3;
    }
    memset(mem,-1,sizeof(mem));
    cout<<dp(1,0);
}

实现采用了思路比较清晰的记忆化搜索。

然后就愉快的 AC 了：https://www.luogu.com.cn/record/171653457

总结

类似于博弈、游戏等题目不能局限于贪心或一种方法，可以大胆开拓新的思路。

广告

安利一下我的代码仓库。AtCoder 的部分题目代码即调试信息、避坑可以在这里找到。

前情

当场没做 D 来做 E 是明智的，D 根本想不到的。

题目

翻译一下：

高桥准备 \(n\) 个菜，每个菜肴有甜味值 \(a_i\) 和 咸味值 \(b_i\)。高桥可以按任意顺序排放这些菜肴。Snuke 按排放的顺序吃，当吃的总甜味值大于 \(X\) 或总咸味值大于 \(Y\) 时停止。求吃的菜肴总数的最大值。

思路

Step 1

这道题和 C 题如出一辙，但仔细一看发现未必。这题求的是最大值。

数据范围是 \(n\le 80\) 且 \(X,Y\le 1000\) 显然 dp。

对比 P2240 和 P1048，发现其实和分别这次 C 题和 E 题道理相同。

一眼类似于背包的 dp，不难设计状态转移：

\(dp(i,x,y)=\max\{dp(i+1,x,y),1+dp(i+1,x-a_i,y-b_i)\}\)。

其中 \(i\) 表示考虑了前 \(i\) 个菜肴，\(x,y\) 分别表示能承受的甜味、咸味值还剩余多少，\(t\) 表示已经选了 \(t\) 个菜肴。

事实上，\(x\) 确定了 \(y\) 就确定了，故记忆化时忽略 \(y\)。否则空间肯定开不下。代码中的 cnt 是为了方便编写，实则不必计入状态。

同时不难写出类似于这样的代码（读者别急着写类似于这样的代码）：

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

// 赛时代码
// #define EXT
#include <bits/stdc++.h>
#ifdef EXT
    #include <bits/extc++.h>
#endif

#define i64 long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define fdn(i,r,l) for(int i=(r);i>=(l);i--)
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef double db;
typedef __int128 i128;

const int INF=1<<29;
const ll INFL=1ll<59;

const int N=114;
const int M=10024;

int n,x,y;
int a[N],b[N];
int mem[N][M][N];

inline int dp(int d,int xx,int yy,int cnt)
{
    if(xx<0||yy<0) return cnt;
    if(d==n+1) return cnt;
    int& ans=mem[d][xx][cnt];
    if(ans!=-1) return ans;
    int ans0=0,ans1=0;
    ans0=dp(d+1,xx-a[d],yy-b[d],cnt+1);
    ans1=dp(d+1,xx,yy,cnt);
    return ans=max(ans0,ans1);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("in.out","w",stdout);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    memset(mem,-1,sizeof(mem));
    cin>>n>>x>>y;
    rep(i,1,n) cin>>a[i]>>b[i];
    cout<<dp(1,x,y,0);
}

同：https://atcoder.jp/contests/abc364/submissions/56045157

很可惜，这样的思路是有漏洞的！

Step 2

比赛的时候碰到这种情况一定冷静！

显然，该程序并未考虑顺序问题。

0-1 背包中物体选的顺序是不考虑的。但题目中特别说了：

高桥可以按任意顺序排放这些菜肴。

反例：不妨只考虑甜味值，假设咸味值远远还没有达到极限。假设选的菜肴中有一个菜的甜味值为 \(p\)，另一个在它之前的菜肴甜味值为 \(q\)。假设除去这两个菜肴以外已经选了甜味值 \(m\)，且 \(m+p+q>m+q>X>m+p>m\)。

按照我们之前的方案，最大的甜味值被认为是 \(m+q\)。然而将 \(p\) 和 \(q\) 交换就得到最大甜味值 \(m+p+q\)，所以最大的菜肴数也比原来多 \(1\)，故原方法有漏洞。

很容易想到用排序法修复 Bug。

Step 3

这是我们将咸味值加进来。我们不妨只考虑其中两个临项 \(i\) 和 \(i+1\) 的情况。列表得：

反之：

若 \(x+a_{i+1}>X>x+a_{i}\) 且 \(y+b_{i+1}>Y>y+b_{i}\) 这时一定有 \(a_{i+1}+b_{i+1}>a_{i}+b_{i}\)。也就是说，符合条件的满足：\(a_{i+1}+b_{i+1}>a_{i}+b_{i}\)。那我们可以将 \(a_i+b_i\) 从小到大排序。

补充：不妨考虑满足 \(x+a_{i+1}>X>x+a_{i}\) 但不满足 \(y+b_{i+1}>Y>y+b_{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

// 赛时代码修改
// #define EXT
#include <bits/stdc++.h>
#ifdef EXT
    #include <bits/extc++.h>
#endif

#define i64 long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define fdn(i,r,l) for(int i=(r);i>=(l);i--)
#define pii pair<int,int>

using namespace std;

typedef long long ll;
typedef double db;
typedef __int128 i128;

const int INF=1<<29;
const ll INFL=1ll<59;

const int N=114;
const int M=10024;

int n,x,y;
vector<pair<int,int> > s;
int a[N],b[N];
int mem[N][M][N];

int cmp2(pair<int,int> A,pair<int,int> B)
{
    return A.second+A.first<B.first+B.second;
}

inline int dp(int d,int xx,int yy,int cnt)
{
    if(d==n+1) return cnt;
    int& ans=mem[d][xx][cnt];
    if(ans!=-1) return ans;
    int ans0=0,ans1=0;
    if(xx>=a[d]&&yy>=b[d]) ans0=dp(d+1,xx-a[d],yy-b[d],cnt+1);
    else ans0=cnt+1;
    ans1=dp(d+1,xx,yy,cnt);
    return ans=max(ans0,ans1);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("in.out","w",stdout);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    memset(mem,-1,sizeof(mem));
    cin>>n>>x>>y;
    rep(i,1,n){int ai,bi;cin>>ai>>bi;s.push_back({ai,bi});}
    sort(s.begin(),s.end(),cmp2);
    for(int i=0;i<s.size();++i) a[i+1]=s[i].first,b[i+1]=s[i].second;
    int ans=dp(1,x,y,0);
    cout<<ans;
}

代码中 mem 数组中 cnt 的维度同样可以略去不计。

总结

当场肯定不能像写题解一样考虑，一般来说是用直觉做的（也有一眼看穿证明的）。

这个思路阶梯是我当场真实体验。所以希望大家考虑全面。

但是本题解给出的方法只是思考的时候用的，并不是证明。有疑问或证明欢迎评论！

难度评级：绿或蓝。

WOT 2024 第 1 期日报 27中七下期中游记

Time flies.转眼又考试了.

前两次应该说还好,这次不会炸吧?

2023期中: 286.5 rnk校=(20,30)

2024七上期末: 776 rnk校=19(18?)

题外话,教你们一个查排名的办法: F12. 点击红旗->检查->百分比即排名

切入游记正题.

day 0 (考试前一天,20240414)

呃呃.

晚上押作文.去年湖南长沙考了「平凡的XX」XX不记得了.

day 1(语文)

晚上睡不着,早上起来爆物理(初三第一课).

烦死了,中午也不凡则睡.

下午去的有点晚.天还下着雨,还不小,看着就有不详的预感.

进入考场更是的.每次「请考试将与学科有关的物品...」唯独我一个不出去放——我不临时抱佛脚的.

老师很磨叽,卷子不提前发.开卷第一件事看作文,结果真押对了..qwq.

我暗自庆幸,但事实并不如我所料.默写很顺利.语段顺利.啊?名著题什么东西?wc三空3pts一个不会!全靠蒙!

假设我三个都蒙对,但是...顺序!这样算了只有 \(\frac{1}{6}\) 的胜率!

先空着吧.

什么东西?对联又坑人!经我犹豫填对了.阅读古文不想说,愿无锅吧!

最后是作文.作文真是对的题,但不是特别手到擒来的题.我想了很久才开始写,也尝试写「工整美观」.

时间一分一秒过去.什么?只剩15min了!我我我我!还有100字!

拼命了!我去!结果最后的字迹略微草率.唉总算好了.

我记得去蒙前面的题...qwq

估分120很险.很难.

出来跟lyc交流了一下,ta也说难.

啊!我3空全错你!我暗想:我错,人家也错...qwq

好吧,我家长又要聊天了qwq....

有两个家长,我简记为:小M家长,小N家长.小M成绩在「重点班」(其实是骗子)rnk2,很自以为是;小N是我同学,差的.大概小M比我低1档,N比我低2档,一档10人(我觉得在一个班)

一过了,小M,N就开始...

小N家长:简单!

小M家长:三空我家都对了.

小N家长还拍了TA在watch TV的视频.wc!都觉得简单是吧.我不禁大骂:小心乐极生悲!(我们班主任口头禅)您能想象我的愤怒啊!

废了,被一顿训...qwq你隔着屏幕可以想象的.

人狂必有祸,后来小N默写错!

我劝说我家长:语文炸了,day2&3不一定不会翻盘呢?

家长:反正你rnk班1没了.

没用自己知道行了.sb

补充: 小N是一个非常要面子且吹牛的人,他平时数学[120,130],你知道他水平了.但他每次都说他满分,sb!

day 2 数学

数学,我的天下.

上午先秒杀AH2020疫情中考,成功150.我的信心得到鼓舞下午力争翻盘!

下午是个好天气,阳光明媚(天气真不是我造的,我不是那些没脸的文学家)

还有难度,选择压轴细节,填空有一道我开始没想出来后来1s解决的,大题均设分类讨论,最后一题外角定理秒杀.

我先跟lyc对了一下,wow!150~

我洋溢着喜悦回班见老慈(班主任)

小N: 简单 我心中暗骂:sb 结果他估分140,我们拭目以待.

小M: 150. 我们也拭目以待.他们说话很有水分.我就不..............(此处省略100字qwq)

明天英语继续哦~

补充:

今天,我听有人说「拔剑特训」上有原题,而小M不就是做嘛!结果ta根本不承认.后来在我逼迫下承认的.qwq

day 3 英语

是个阴天.进考场发卷子就狂风大雨.

做完一题不会,估分119-作文[1,2].

对答案,一份不挂.好耶!还是119-作文

上电脑班拿伞被骂nj...qwq

小N: 115-作文

小M: 118-作文

班上同学有点悬,好像有点失误吧他们.

这不就翻盘了吗?

但是没小M高aaa.qwq人家小M是女生qAQ.

day 6 出成绩

中午手机炸了.

查得,390 rnk校=42.

卧槽,小M直接397rnk=8我去他们班一号.

唉,小N就是在吹牛,就360qwq.

啊啊啊,这次怎么被小M整了?

后来,zyz都393就我最差是吧??qwq

没事没事,这次数学英语发挥稳定,语文略有失误.况且这次对题海很友好.qwq

达克.

文章同载于：

• https://www.luogu.com.cn/article/37bpa0ho
• https://lgfriends.us.kg/blog/205-abc-393-ti-jie-zheng-he

fyy 是一个非常珂愛的女孩子。

fyy 认为一个 \(01\) 序列中如果所有 \(1\) 都是连续的，那么这个序列很珂愛。fyy 想通过有限次操作使得一个序列变得珂愛。对于每次操作，她只能交换两个相邻的数。

fyy 问妳最少的操作次数是多少？

讲一下一个假的做法。看到这个题立马想到 ABC 以前的一道题，把所有的 \(1\) 都往最左边的一个移动。错误很显然。

这个问题很迷惑，实际上所有 \(0\) 都是没用的，只需考虑 \(1\)。

钦定最优情况一定是选择一个 \(1\) 作为合并的起始点，将其两边的 \(1\) 逐渐合并。如果最优情况可能是 \(0\) 类似讨论即可。

形式化的说，序列中给出了 \(M\) 个 \(1\)，其中第 \(i\) 个 \(1\) 的位置是 \(X_i\)。选定第 \(k\) 个 \(1\)。

求 \(\sum\limits_{i=1}^{k-1} \left[X_k-X_i-(k-i)\right]+\sum \limits_{i=k+1}^{M} \left[X_i-X_k-(i-k)\right]\) 的最小值（其实上式也可写成绝对值形式）。

不妨考虑一个子问题。给定 \(M\) 个数轴上的点 \((X_1,X_2,\dots,X_M)\)。设 \(x\) 为任意一点。求 \(\sum\limits_{i\in[1,M]}|x-X_i|\) 的最小值。运用几何直观，显然当且仅当 \(x\) 在中间两点所成区间（包含区间断点）内时取得最小值（如果 \(M\) 为奇数那么 \(x=X_{mid}\)，\(mid\) 为 \(1\sim M\) 的中间值 \(\left\lfloor \frac{M}{2}\right\rfloor+1\)）。

对此的证明可以翻开你的人教版七年级第一章有理数的各种教辅资料，应该都有这种题目。

类似于刚才的问题，我们注意到 \(\sum \left|k-i\right|\) 和 \(\sum\left|X_k-X_i\right|\) 都可以在 \(k=\left\lfloor \frac{M}{2}\right\rfloor+1\) 时取得最小值（原因是我们将其抽象转换成刚才的问题）。

于是我们解决了这个问题。下面形式化做法：

• 找出所有点 \((X_1,X_2,\dots,X_M)\)，找出中间点为合并初始点，也就是 \(X_{\left\lfloor \frac{M}{2}\right\rfloor+1}\)。这个点记为 \(X_{mid}\)。
• 求出 \(\sum\limits_{i=1}^{mid} \left[X_{mid}-X_i-(k-i)\right]+\sum \limits_{i=mid+1}^{M} \left[X_i-X_{mid}-(i-k)\right]\) 的值。

下面是代码：

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

int main()
{
    int N; string S;
    cin>>N>>S;
    S=' '+S;
    int mid,M=0,cnt=0;
    rep(i,1,N)
        if(S[i]=='1') M++;
    rep(i,1,N)
        if(S[i]=='1')
        {
            cnt++;
            if(cnt==M/2+1){mid=i; break;}
        }
    M=M/2+1;
    ll ans=0; cnt=0;
    rep(i,1,mid-1)
        if(S[i]=='1')
        {
            cnt++;
            ans+=mid-i-1;
            ans-=(M-cnt-1);
        }
    cnt=M;
    rep(i,mid+1,N)
        if(S[i]=='1')
        {
            cnt++;
            ans+=i-mid-1;
            ans-=(cnt-M-1);
        }
    cout<<ans<<endl;
}

// 路虽远行则将至，事虽难做则必成。

https://atcoder.jp/contests/abc393/submissions/62799606

\(\sum\limits^{n}_{j=1}a_j\)

\[\Phi \Pi \times\]

\[E=mc^2\]

1
2
3
4
5
6
7
8
9
10

ohaaaaaaaaa!

WOT YYDS

  ███╗   ██╗███████╗██╗  ██╗████████╗
  ████╗  ██║██╔════╝╚██╗██╔╝╚══██╔══╝
  ██╔██╗ ██║█████╗   ╚███╔╝    ██║
  ██║╚██╗██║██╔══╝   ██╔██╗    ██║
  ██║ ╚████║███████╗██╔╝ ██╗   ██║
  ╚═╝  ╚═══╝╚══════╝╚═╝  ╚═╝   ╚═╝

WOT GREAT!

TPCpp ...

OH YEAH!

AH Wuhu Jinhu 27 mid

33256

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

\(\sum\)

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment