ACM-ICPC 2018 徐州赛区网络预赛（6/11）

A.Hard to prepare
枚举第一个选的，接下来的那个不能取前一个的取反
\(DP[i][0]\)表示选和第一个相同的
\(DP[i][1]\)表示选和第一个取反的
\(DP[i][2]\)表示选其他的
状态转移方程直接看代码好了

//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e6+7;
typedef long long int LL;
const LL MOD = 1e9+7;
int n,k;
LL qpow(LL a, LL b){
    LL ret = 1;
    while(b){
        if(b&1) ret = ret * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return ret;
}
LL f[2][3];
void solve(){
    cin >> n >> k;
    LL pk = qpow(2,k);
    LL pk_1 = (pk-1+MOD)%MOD;
    LL pk_2 = (pk-2+MOD)%MOD;
    LL pk_3 = (pk-3+MOD)%MOD;
    int ID = 0;
    f[0][0] = 1; f[0][1] = 0; f[0][2] = 0;
    //0 自身    1 自身取反     2.其他
    for(int i = 2; i <= n; i++){
        ID ^= 1;
        f[ID][0] = (f[ID^1][0]+f[ID^1][2]) % MOD;
        f[ID][1] = (f[ID^1][1]+f[ID^1][2]) % MOD;
        f[ID][2] = (f[ID^1][0]*pk_2%MOD + f[ID^1][1]*pk_2%MOD + f[ID^1][2]*pk_3%MOD) % MOD;
    }
    cout << pk * (f[ID][0] + f[ID][2]) % MOD << endl;
}
int main(){
    ____();
    int T;
    for(cin >> T; T; T--) solve();   
    return 0;
}

B.BE, GE or NE
Game + DP || 记忆化搜索
到每个人选的时候必然在三种选择中选择最合适自己的，记忆化到每个位置\(i\)当前值是\(x\)的情况下的解

//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1111;
const int D = 100;
const int INF = 0x3f3f3f3f;
int n,f[MAXN][D<<2],m,l,r;
tuple<int,int,int> ops[MAXN];
int ending(int score){
    if(score>=r) return 1;
    if(score<=l) return -1;
    return 0;
}
int search(int pos, int v){
    if(f[pos][v+D]!=INF) return f[pos][v+D];
    if(pos==n+1) return f[pos][v+D] = ending(v);
    vector<int> opt;
    if(get<0>(ops[pos])) opt.emplace_back(search(pos+1,min(D,v+get<0>(ops[pos]))));
    if(get<1>(ops[pos])) opt.emplace_back(search(pos+1,max(-D,v-get<1>(ops[pos]))));
    if(get<2>(ops[pos])) opt.emplace_back(search(pos+1,-v));
    sort(opt.begin(),opt.end());
    if(pos&1) f[pos][v+D] = opt.back();
    else f[pos][v+D] = opt.front();
    return f[pos][v+D];
}
int main(){
    ____();
    cin >> n >> m >> r >> l;
    for(int i = 1; i <= n; i++) cin >> get<0>(ops[i]) >> get<1>(ops[i]) >> get<2>(ops[i]);
    memset(f,0x3f,sizeof(f));
    int ret = search(1,m);
    if(ret==-1) cout << "Bad Ending" << endl;
    else if(ret==0) cout << "Normal Ending" << endl;
    else if(ret==1) cout << "Good Ending" << endl;
    return 0;
}

C.Cacti Lottery

D.Easy Math

E.End Fantasy VIX

F.Features Track
map搞一下就好了

//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e5+7;
map<pair<int,int>,int> msk[2];
void solve(){
    int ret = 1, n;
    scanf("%d",&n);
    int ID = 0;
    msk[0].clear(); msk[1].clear();
    for(int i = 1; i <= n; i++){
        int k; scanf("%d",&k);
        ID ^= 1;
        msk[ID].clear();
        for(int j = 1; j <= k; j++){
            pair<int,int> p; scanf("%d %d",&p.first,&p.second);
            if(msk[ID^1].count(p)) msk[ID].insert(make_pair(p,msk[ID^1].at(p)+1));
            else msk[ID].insert(make_pair(p,1));
            ret = max(ret,msk[ID].at(p));
        }
    }
    printf("%d\n",ret);
}
int main(){
    int T;
    for(scanf("%d",&T); T; T--) solve();
    return 0;
}

G.Trace
线段树+离散化
可以把\(x\)和\(y\)两个维度分开来做
以计算\(x\)轴方向总长度为例
从最后一个\(wave\)开始向前遍历，找在他之后且\(y\)方向坐标位置大于当前\(wave\)的\(x\)的最大值，贡献就是当前的\(x\)，减去在他之后的最大的\(x\)，可以通过离散化+线段树的方法来做

//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 5e4+7;
typedef long long int LL;
int n;
class SegmentTree{
private:
    int l[MAXN<<2],r[MAXN<<2],maxx[MAXN<<2];
    #define ls(rt) rt << 1
    #define rs(rt) rt << 1 | 1
    #define pushup(rt) maxx[rt] = max(maxx[ls(rt)],maxx[rs(rt)])
public:
    void build(int L, int R, int rt = 1){
        l[rt] = L; r[rt] = R;
        maxx[rt] = 0;
        if(L+1==R) return;
        int mid = (L+R) >> 1;
        build(L,mid,ls(rt)); build(mid,R,rs(rt));
    }
    void update(int pos, int x, int rt = 1){
        if(l[rt]+1==r[rt]){
            maxx[rt] = max(maxx[rt],x);
            return;
        }
        int mid = (l[rt] + r[rt]) >> 1;
        if(pos<mid) update(pos,x,ls(rt));
        else update(pos,x,rs(rt));
        pushup(rt);
    }
    int qmax(int L, int R, int rt = 1){
        if(l[rt]>=R or L>=r[rt]) return 0;
        if(L<=l[rt] and r[rt]<=R) return maxx[rt];
        return max(qmax(L,R,ls(rt)),qmax(L,R,rs(rt)));
    }
}ST;
void solve(vector<pair<int,int> > &rect, LL &ret){
    vector<int> vec;
    for(int i = 0; i < (int)rect.size(); i++) vec.emplace_back(rect[i].second);
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    ST.build(1,vec.size()+1);
    for(int i = 0; i < (int)rect.size(); i++){
        int y = lower_bound(vec.begin(),vec.end(),rect[i].second) - vec.begin() + 1;
        ret += rect[i].first - ST.qmax(y,vec.size()+1);
        ST.update(y,rect[i].first);
    }
}
int main(){
    ____();
    cin >> n;
    vector<pair<int,int> > rect(n);
    for(int i = 0; i < n; i++) cin >> rect[i].first >> rect[i].second;
    reverse(rect.begin(),rect.end());
    LL ret = 0;
    solve(rect,ret);
    for(int i = 0; i < n; i++) swap(rect[i].first,rect[i].second);
    solve(rect,ret);
    cout << ret << endl;
    return 0;
}

H.Ryuji doesn‘t want to study
线段树

//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e5+7;
typedef long long int LL;
int n,m;
class SegmentTree{
private:
    int l[MAXN<<2], r[MAXN<<2];
    LL sum1[MAXN<<2],sum2[MAXN<<2];
    #define ls(rt) rt << 1
    #define rs(rt) rt << 1 | 1 
    void pushup(int rt){
        sum1[rt] = sum1[ls(rt)] + sum1[rs(rt)];
        sum2[rt] = sum2[ls(rt)] + sum2[rs(rt)];
    }
public:
    void build(int L, int R, int rt = 1){
        l[rt] = L; r[rt] = R;
        if(L+1==R){
            cin >> sum1[rt];
            sum2[rt] = sum1[rt] * (n + 1ll - L);
            return;
        }
        int mid = (L+R) >> 1;
        build(L,mid,ls(rt)); build(mid,R,rs(rt));
        pushup(rt);
    }
    void update(int pos, int x, int rt = 1){
        if(l[rt] + 1 == r[rt]){
            sum1[rt] = x;
            sum2[rt] = sum1[rt] * (n + 1ll - l[rt]);
            return;
        }
        int mid = (l[rt] + r[rt]) >> 1;
        if(pos<mid) update(pos,x,ls(rt));
        else update(pos,x,rs(rt));
        pushup(rt);
    }
    pair<LL,LL> query(int L, int R, int rt = 1){
        if(l[rt]>=R or L>=r[rt]) return make_pair(0,0);
        if(L<=l[rt] and r[rt]<=R) return make_pair(sum1[rt],sum2[rt]);
        auto p1 = query(L,R,ls(rt));
        auto p2 = query(L,R,rs(rt));
        return make_pair(p1.first+p2.first,p1.second+p2.second);
    }
}ST;
//维护两个值 1.A[i]， 2.A[i] * (n+1-i)                  区间和
int main(){
    ____();
    cin >> n >> m;
    ST.build(1,n+1);
    while(m--){
        int op,a,b;
        cin >> op >> a >> b;
        if(op==1){
            auto p = ST.query(a,b+1);
            cout << p.second - p.first * (n - b) << endl;
        }
        else ST.update(a,b);
    }
    return 0;
}

I.Characters with Hash
签到

//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e6+7;
int n;
char s[MAXN],st[2];
void solve(){
    cin >> n >> st >> s;
    for(int i = 0; i < n; i++){
        if(s[i]!=st[0]){
            if(abs(s[i]-st[0])>=10) cout << (n-i) * 2  << endl;
            else cout << (n-i) * 2 - 1 << endl;
            return;
        }
    }
    cout << 1 << endl;
}
int main(){
    ____();
    int T; for(cin >> T; T; T--) solve();
    return 0;
}

J.Maze Designer

K.Morgana Net

ACM-ICPC 2018 徐州赛区网络预赛（6/11）

原文：https://www.cnblogs.com/kikokiko/p/12842938.html