生活随笔
收集整理的這篇文章主要介紹了
Codeforces Round #723 (Div. 2) D. Kill Anton 线段树 + 暴力
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
傳送門
文章目錄
題意：
給你一個(gè)只有ANTOANTOANTO四個(gè)字母的字符串，你每次可以交換相鄰兩個(gè)，花費(fèi)為111，讓后讓你打亂字符串，使得將打亂的字符串還原為原來的字符串的花費(fèi)最小。
n≤1e5n\le1e5n≤1e5
思路：
打了這么長(zhǎng)時(shí)間acmacmacm了，還能因?yàn)闆]開LLLLLL掛題，賽后又交了將近一頁(yè)，真是越來越菜了。
首先這個(gè)題通過打表以及第六感可以發(fā)現(xiàn)，將所有相同的字母放在一起是最優(yōu)的，所以可以4!4!4!枚舉所有位置，讓后checkcheckcheck一下取最大的花費(fèi)即可，現(xiàn)在瓶頸就是在怎么快速求出花費(fèi)來。
我們假設(shè)原來的串為aaa，現(xiàn)在的串為bbb，首先我們可以從頭遍歷aaa，讓后對(duì)于aaa的每一個(gè)字符我們肯定都找其在bbb中第一次出現(xiàn)的位置，用完之后刪掉這個(gè)位置。可是我們將某一個(gè)刪除的時(shí)候，他們的某些位置可能會(huì)變化，比如aaa從111開始，初始的時(shí)候bbb的位置是1,2,3,4,51,2,3,4,51,2,3,4,5，現(xiàn)在將444這個(gè)位置刪掉，花費(fèi)為333，那么現(xiàn)在bbb變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">1,2,3,51,2,3,51,2,3,5，下次需要選333這里刪掉的時(shí)候就會(huì)出現(xiàn)問題了，因?yàn)榘凑丈厦娴脑捇ㄙM(fèi)應(yīng)該是3?2=13-2=13?2=1，但是實(shí)際花費(fèi)是222，問題也很明顯了，我們將444刪掉后，應(yīng)該讓444前面的所有位置都+1+1+1，即變成2,3,4,52,3,4,52,3,4,5即可，這個(gè)就很好維護(hù)了，用線段樹實(shí)現(xiàn)區(qū)間加即可。
代碼寫的丑的一批。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
#define int long long
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;string s
,ps
;
string mp
[10];
int a
[20];
vector
<int>v
[20];
struct Node {int l
,r
;int cnt
,lazy
;
}tr
[N
<<2];void pushup(int u
) {tr
[u
].cnt
=tr
[L
].cnt
+tr
[R
].cnt
;
}void pushdown(int u
) {if(!tr
[u
].lazy
) return;int lazy
=tr
[u
].lazy
; tr
[u
].lazy
=0;tr
[L
].lazy
+=lazy
; tr
[R
].lazy
+=lazy
;tr
[L
].cnt
+=lazy
; tr
[R
].cnt
+=lazy
;
}void build(int u
,int l
,int r
) {tr
[u
]={l
,r
,1,0};if(l
==r
) {tr
[u
].cnt
=l
;return;}build(L
,l
,Mid
); build(R
,Mid
+1,r
);pushup(u
);
} void change(int u
,int l
,int r
,int c
) {if(tr
[u
].l
>=l
&&tr
[u
].r
<=r
) {tr
[u
].cnt
+=c
;tr
[u
].lazy
+=c
;return;}if(l
<=Mid
) change(L
,l
,r
,c
);if(r
>Mid
) change(R
,l
,r
,c
);pushup(u
);
}int query(int u
,int l
,int r
) {if(tr
[u
].l
>=l
&&tr
[u
].r
<=r
) return tr
[u
].cnt
;int ans
=0;pushdown(u
);if(l
<=Mid
) ans
+=query(L
,l
,r
);if(r
>Mid
) ans
+=query(R
,l
,r
);return ans
;
}int check(string ps
) {int ans
=0;build(1,1,ps
.length());for(int i
=0;i
<4;i
++) v
[i
].clear();for(int i
=s
.length()-1;i
>=0;i
--) {if(ps
[i
]=='A') v
[0].pb(i
+1);else if(ps
[i
]=='N') v
[1].pb(i
+1);else if(ps
[i
]=='O') v
[2].pb(i
+1);else v
[3].pb(i
+1);}for(int i
=0;i
<s
.length();i
++) {int pos
;if(s
[i
]=='A') pos
=v
[0].back(),v
[0].pop_back();else if(s
[i
]=='N') pos
=v
[1].back(),v
[1].pop_back();else if(s
[i
]=='O') pos
=v
[2].back(),v
[2].pop_back();else pos
=v
[3].back(),v
[3].pop_back();int now
=query(1,pos
,pos
);ans
+=abs(now
-(i
+1));change(1,1,pos
-1,1);}return ans
;
}signed main()
{ios
::sync_with_stdio(false);cin
.tie(0);int _
; cin
>>_
;while(_
--) {for(int i
=0;i
<4;i
++) mp
[i
]="",a
[i
]=i
;cin
>>ps
; s
=ps
;for(int i
=0;i
<ps
.length();i
++) {if(ps
[i
]=='A') mp
[0]+='A';else if(ps
[i
]=='N') mp
[1]+='N';else if(ps
[i
]=='O') mp
[2]+='O';else mp
[3]+='T';}int ans
=-1;string res
;do {string now
="";for(int i
=0;i
<4;i
++) now
+=mp
[a
[i
]];int x
=check(now
);if(x
>ans
) ans
=x
,res
=now
;}while(next_permutation(a
,a
+4));cout
<<res
<<endl
;}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的Codeforces Round #723 (Div. 2) D. Kill Anton 线段树 + 暴力的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
