20181011 NOIP集训 Test1 – [题组/考试]

T3 : 序列修正 – [二分]

题解 :

我们存一下每次的操作类型, 以及做完这次操作之后的长度.

对于一次询问, 我们递归的求解.

对于求解x, 我们先二分出它是哪次操作产生的, 直接在len上用lower_bound即可

若这次操作是操作1, 那么直接输出存下来的这次操作所读入的值L[i]

否则, 这次操作一定是由在前L[i]个数的某个数复制来, 我们把x\mod L[i]得到的新x就是在之前L[i]的位置

注意如果新x是0, 代表它实际上是L[i]

我们递归求解新x即可

复杂度最坏情况下应该是每次log级别的, 因为考虑一次取模最多剩10^5, 若L[i]很小(指小于\frac{10^5}{2}, 下次取模就会减小一半, 否则因为c至少是1, 会减少\frac{2}{L_i}, 还是至少减少一半.

代码 :

#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
#define int long long
const int N = 100010;
int typ[N], L[N], c[N], n, m;
ll len[N];
int solve(ll x) {
    int pos = lower_bound(len+1, len+n+1, x)-len;
    if(typ[pos] == 1) return L[pos];
    ll now = x-len[pos-1];
    now %= L[pos];
    if(now == 0) now = L[pos];
    return solve(now);
}
signed main() {
    freopen("fix.in", "r", stdin); freopen("fix.out", "w", stdout);
    scanf("%lld", &n);
    for(int i = 1; i <= n; i ++ ) {
        scanf("%lld%lld", &typ[i], &L[i]);
        if(typ[i] == 1) {
            len[i] = len[i-1]+1;
        } else {
            scanf("%lld", &c[i]);
            len[i] = len[i-1]+(ll)L[i]*c[i];
        }
    }
    scanf("%lld", &m);
    for(int i = 1; i <= m; i ++ ) {
        ll x; scanf("%lld", &x);
        printf("%lld\n", solve(x));
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注