http://codeforces.com/contest/427

A题手速题,2min AC
B题用RMQ过的。。其实只要维护一个<=t的cnt计数值就行了。。

int ans = 0, cnt = 0;
while (n--)
{
    scanf("%d", &val);
    if (val <= t) ++cnt;
    else cnt = 0;
    if (cnt >= c) ++ans;
}
printf("%d", ans);

C题强联通分量,注意用long long【怎么还有这么裸的模板题。。
D题后缀数组,建好高度数组后判断h[i]>h[i-1]&&h[i]>h[i+1]即可(代码太长,贴在最下方)
E题要计算路线和值,我们可以换个思路来累加——不按时间顺序累加,而是按这段路重复走的次数累加:

// 输入已经保证是有序的
ll ans = 0LL;
for (int i = 0, j = n - 1; i < j; i += m, j -= m) ans += (ll)(a[j] - a[i]);
printf("%I64d\n", ans << 1LL);

D题代码:

/*46ms,260KB*/

const int mx = 10005;

char s[mx], s2[mx >> 1];
int lens, n;

/// lens为全局变量,用于判断sa[i]是否与sa[i-1]不同组:
/// if ((sa[i] < lens) != (sa[i - 1] < lens))
inline void cat() /// 连接两字符串,同时获取n和lens
{
    s[lens = strlen(s)] = '$';
    n = strlen(strcat(s, s2));
}

int sa[mx];
int t[mx], t2[mx], c[mx]; /// 辅助数组

void build_sa(int m)
{
    int i, *x = t, *y = t2, p;
    For(i, m) c[i] = 0;
    For(i, n) c[x[i] = s[i]]++;
    Forr(i, 1, m) c[i] += c[i - 1];
    rFor(i, n - 1) sa[--c[x[i]]] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        p = 0;
        Forr(i, n - k, n) y[p++] = i;
        For(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
        For(i, m) c[i] = 0;
        For(i, n) c[x[y[i]]]++;
        Forr(i, 1, m) c[i] += c[i - 1];
        rFor(i, n - 1) sa[--c[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1;
        x[sa[0]] = 0;
        Forr(i, 1, n) x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++);
        if (p >= n) break;
        m = p;
    }
}

int rk[mx], h[mx];

void build_h()
{
    int i, j, hh = 0;
    For(i, n) rk[sa[i]] = i;
    For(i, n)
    {
        if (hh) --hh;
        j = sa[rk[i] - 1];
        while (s[i + hh] == s[j + hh]) ++hh;
        h[rk[i]] = hh;
    }
}

int solve()
{
    int i, ans = inf;
    Forr(i, 2, n)
    {
        if ((sa[i] < lens) != (sa[i - 1] < lens)) /// sa[i]与sa[i-1]处于不同字符
     {
            if (h[i] > h[i - 1] && h[i] > h[i + 1]) /// 必须是凸的
             ans = min(ans, 1 + max(h[i - 1], h[i + 1])); /// 注意值的选取
     }
    }
    return ans == inf ? -1 : ans;
}

int main()
{
    gets(s), gets(s2);
    cat();
    build_sa(123);
    build_h();
    PI(solve());
    return 0;
}

Comments

comments powered by Disqus