把假日没写出来的34写一写
：（
3
dp这列过去的那列的dp
又是轮转位移
不相邻有点像抢房子
这种资料结构比较复杂的
我都写到头脑烧坏：（
原本用vector+hashmap 1560ms
后来用offset改array有快一点
924ms
using ll = long long;
class Solution {
public:
int countWinningSequences(string s) {
// F > E > W > F
vector<vector<int>> dir = { {1, 2}, {0, 2}, {0, 1} };
vector<vector<int>> add = { {0, -1, 1}, {1, 0, -1}, {-1, 1, 0} };
// for bob
int m = 1e9 + 7;
int len = s.length();
//cnt range: -1000 to 1000
int offset = 1000;
int dp[1000][3][2002] = {{{-1}}};
//vector<vector<unordered_map<int, int>>> dp(len, vector<unordered_map<int, int>>(3));
//dp for Bob's sequence, bob's point
//dp[i][0] = F, dp[i][1] = E, dp[i][2] = W
//map< key = point , cnt >
vector<int> mod;
if(s[0] == 'F'){
mod = add[0];
}
else if(s[0] == 'E'){
mod = add[1];
}
else{//'W
mod = add[2];
}
dp[0][0][mod[0] + offset]++;
dp[0][1][mod[1] + offset]++;
dp[0][2][mod[2] + offset]++;
for(int i = 1; i < len; i++){
char c = s[i];
if(c == 'F'){
mod = add[0];
}
else if(c == 'E'){
mod = add[1];
}
else{ // c == 'W'
mod = add[2];
}
//to dp[i-1]
for(int last = 0; last < 3; last++){
for(int point = offset - (len - 1 - i); point <= i + offset ; point++){
if(dp[i-1][last][point] == -1) continue;
for(int next: dir[last]){
if(dp[i][next][(point + mod[next])] == -1)
dp[i][next][(point + mod[next])] = dp[i-1][last][point];
else{
ll cnt = dp[i][next][(point + mod[next])] + dp[i-1][last][point];
cnt %= m;
dp[i][next][(point+ mod[next])] = cnt;
}
}
}
}
}
ll res = 0;
for(int few = 0; few < 3; few++){
for(int point = offset + 1; point <= 2000 ; point++){
if(dp[len-1][few][point] > 0) res += dp[len-1][few][point];
res %= m;
}
}
return res;
}
};
4.
想要他照cnt, num排序
但又要用num find 再 modify
一开始用pq兜不出来
想一想发现
我想要二分搜又maxheap
那不就是treap吗
虽然感觉有够不平衡
但我试着建树发现
我不知道怎么维护前x个==
每次都找一遍也太白痴了
最后情不得已改成map排序
对每个num记他的position (iterator)
然后发现沃草multimap只会排key
不会排后面的value
再改成set==
是要多忙
然后还卡long long
没必要吧这个
944ms
using ll = long long;
class Solution {
public:
//multimap<int, int> outX;
//multimap<int, int> Xsum;
set<pair<int, int>> outX;
// <cnt, num> nums not in Xsum
unordered_map<int, std::set<pair<int, int>>::iterator> idout;
// <num, it of out>
set<pair<int, int>> Xsum;
// <cnt, num>
unordered_map<int, std::set<pair<int, int>>::iterator> idx;
// <num, it of Xsum>
ll sum ;
int coda;
vector<long long> findXSum(vector<int>& nums, int k, int x) {
int n = nums.size();
sum = 0;
coda = x;
for(int i = 0; i < k; i++){
int num = nums[i];
if(idx.count(num)){
to_X(num);
}
// num not in Xsum
else if(coda > 0){
if(outX.size() == 0){
to_X(num);
}
else {
to_out(num);
out_to_X();
}
}
else{
// x = 0, Xsum full
// insert outX
to_out(num);
// put outX.rbegin() into Xsum, idx
out_to_X();
// put Xsum.begin() into outX, idout
X_to_out();
}
}
vector<ll> res;
res.push_back(sum);
for(int i = k; i < n; i++){
//print_X();
int last = nums[i-k];
int num = nums[i];
if(last == num){
res.push_back(sum);
continue;
}
// add num
if(idx.count(num)){
to_X(num);
}
else if(coda > 0){
if(outX.size() == 0){
to_X(num);
}
else {
to_out(num);
}
}
else{
to_out(num);
}
//sub last
if(idx.count(last)){
sub_X(last);
}
else{
sub_out(last);
}
while(coda >= 0 and outX.size() > 0){
out_to_X();
}
while(coda < 0){
X_to_out();
}
res.push_back(sum);
}
return res;
}
void print_X(){
for(auto [cnt, num]: Xsum){
cout << cnt << ", " << num << "; ";
}
cout << '\n';
}
void sub_X(int num){
auto it = idx[num];
int cnt = it->first - 1;
Xsum.erase(it);
idx.erase(num);
if(cnt > 0)
idx[num] = Xsum.insert(make_pair(cnt, num)).first;
else coda++;
sum -= num;
}
void sub_out(int num){
auto it = idout[num];
int cnt = it->first - 1;
outX.erase(it);
idout.erase(num);
if(cnt > 0)
idout[num] = outX.insert(make_pair(cnt, num)).first;
}
void to_X(int num){
if(idx.count(num)){
auto it = idx[num];
int cnt = it->first + 1;
Xsum.erase(it);
idx[num] = Xsum.insert(make_pair(cnt, num)).first;
}
else{
idx[num] = Xsum.insert(make_pair(1, num)).first;
coda