【LOJ】#2010. 「SCOI2015」小凸解密码

题解

断环为链，把链复制两份

用set维护一下全是0的区间，然后查找x + n / 2附近的区间，附近各一个过不去，最后弃疗了改为查附近的两个，然后过掉了= =
熟练掌握stl的应用，你值得拥有（雾
代码

#include <bits/stdc++.h>

//#define ivorysi

#define enter putchar('\n')

#define space putchar(' ')

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define eps 1e-8

#define mo 974711

#define MAXN 200005

#define pii pair<int,int>

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {putchar('-');x = -x;}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N,M;

int A[MAXN * 2],B[MAXN * 2];

char ch[MAXN * 2][3];

set<pii > S;

void Change(int p,int v) {

    if(B[p] == v) return;

    if(B[p] != 0 && v != 0) {B[p] = v;return;}

    if(B[p] == 0) {

	auto k = S.upper_bound(mp(p,4 * N));

	--k;

	pii t = *k;

	S.erase(k);

	if(p - 1 >= t.fi) S.insert(mp(t.fi,p - 1));

	if(p + 1 <= t.se) S.insert(mp(p + 1,t.se));

    }

    else {

	auto k = S.upper_bound(mp(p,4 * N)),g = k;

	--g;

	pii t2 = *k,t1 = *g;

	if(t1.se == p - 1 && t2.fi == p + 1) {

	    S.erase(k);S.erase(g);

	    S.insert(mp(t1.fi,t2.se));

	}

	else if(t1.se == p - 1) {

	    S.erase(g);S.insert(mp(t1.fi,p));

	}

	else if(t2.fi == p + 1) {

	    S.erase(k);S.insert(mp(p,t2.se));

	}

	else {

	    S.insert(mp(p,p));

	}

    }

    B[p] = v;

}

int check(int p,pii t) {

    if(t.fi == 4 * N || t.fi == -4 * N) return 0;

    if((t.fi <= p && t.se >= p) || (t.fi <= p + N && t.se >= p + N)) return 0;

    else return min(t.fi - p,p + N - t.se);

}

int Query(int p) {

    if(S.size() == 2) return -1;

    auto k = S.lower_bound(mp(p + N / 2,4 * N)),g = k,h = k;

    --g;++h;

    int res = 0;

    pii t = *k;

    res = max(check(p,t),res);

    t = *g;

    res = max(check(p,t),res);

    if(h != S.end()) t = *h,res = max(check(p,t),res),++h;

    if(g != S.begin()) {

	--g;t = *g;res = max(check(p,t),res);

    }

    if(h != S.end()) {

	t = *h;res = max(check(p,t),res);

    }

    return res;

}

int calc(int a,int b,char op) {

    if(op == '*') return a * b % 10;

    else return (a + b) % 10;

}

void Solve() {

    read(N);read(M);

    S.insert(mp(4 * N,4 * N));

    S.insert(mp(-4 * N,-4 * N));

    for(int i = 1 ; i <= N ; ++i) {

	read(A[i]);scanf("%s",ch[i] + 1);

    }

    A[0] = A[N];

    for(int i = 1 ; i <= N ; ++i) {

	B[i] = calc(A[i],A[i - 1],ch[i][1]);

    }

    for(int i = 1 ; i <= N ; ++i) B[i + N] = B[i],A[i + N] = A[i];

    int p = -1;

    for(int i = 1 ; i <= 2 * N ; ++i) {

	if(B[i] == 0) {

	    if(p == -1) p = i;

	}

	else if(p != -1) {

	    S.insert(mp(p,i - 1));

	    p = -1;

	}

    }

    if(p != -1) S.insert(mp(p,2 * N));

    int op,num;char s[5];

    for(int i = 1 ; i <= M ; ++i) {

	read(op);

	if(op == 1) {

	    read(p);read(num);scanf("%s",s + 1);

	    ++p;

	    if(p == N) {

		Change(1,calc(A[1],num,ch[1][1]));

		Change(N + 1,calc(A[1],num,ch[1][1]));

	    }

	    else {

		Change(p + 1,calc(A[p + 1],num,ch[p + 1][1]));

		Change(p + 1 + N,calc(A[p + 1],num,ch[p + 1][1]));

	    }

	    A[p] = A[p + N] = num;ch[p][1] = s[1];

	    Change(p,calc(A[p],A[p - 1],s[1]));

	    Change(p + N,calc(A[p],A[p - 1],s[1]));

	    if(p == N) A[0] = num;

	}

	else {

	    read(p);++p;

	    int t = B[p];

	    Change(p,A[p]);

	    out(Query(p));enter;

	    Change(p,t);

	}

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}
巴特西

【LOJ】#2010. 「SCOI2015」小凸解密码

题解

代码

最新文章

热门文章
