http://codeforces.com/contest/301

A题

注意到在若干次操作后,我们可以使序列中的 0,2,4,... 个元素改变符号,并且,当n为奇数的时候,我们可以改变奇数个元素的符号。从而在n为奇数时我们可以改变任意多个元素的符号,而在n为偶数时只能改变偶数个与元素的符号。
继续讨论n为偶数的情况,若负数有偶数个,则都变为正即可;若负数有奇数个,则需要看绝对值最小的那个在原序列中是负数还是正数,若是负数则不改,若是整数则把那个负数改为正。

附 Python 代码:

n = input()
a = map(int, raw_input().split())
aa = map(abs, a)
print sum(aa) - (1 - n % 2) * len([i for i in a if i < 0]) % 2 * 2 * min(aa)

B题

很明显,每条边i-j的权值为(abs(x[i] - x[j]) + abs(y[i] - y[j])) * c - a[i]

(只贴出与题目有关的代码,宏定义见 GitHub

const int mx = int(1e2) + 5;

int d[mx][mx], a[mx], x[mx], y[mx];
int floyd(int n) {int i, j, k; For(k, n) For(i, n) For(j, n) Qmin(d[i][j], d[i][k] + d[k][j]); return d[0][n - 1];}

int main()
{
    int n, c, i, j;
    SII(n, c);
    SA(a + 1, i, n - 2);
    For(i, n) SII(x[i], y[i]);
    For(i, n) For(j, n) if (j != i) d[i][j] = (abs(x[i] - x[j]) + abs(y[i] - y[j])) * c - a[i];
    PI(floyd(n));
    return 0;
}

D题

只有查询,必然离线。
由于序列是1~n的某个全排列,我们可以从1~n逐步更新,同时进行计算。
我们可以用1~R的对数减去1~L-1的对数,但是这样算的结果包含了一个属于1~L-1另一个属于L~R的对数,减之。(在写的过程中还有很多细节,详见代码)

代码:

(只贴出与题目有关的代码,宏定义见 GitHub

/* 622 ms, 13900 KB */
const int mx = int(2e5) + 5;

int tree[mx], n, m;
inline void U(int pos, int val = 1) {for (; pos <= n; pos += pos & -pos) tree[pos] += val;}
inline int sum(int pos) {int sum = 0; for (; pos; pos &= pos - 1) sum += tree[pos]; return sum;} 
inline int Q(int l, int r) {return sum(r) - sum(l - 1);} // 闭区间

int a[mx], pos[mx], l[mx], r[mx], ans[mx];
vector<int> Lid[mx], Rid[mx];

int main()
{
    int i, j;
    SII(n, m);
    Forr(i, 1, n + 1) SI(a[i]), pos[a[i]] = i;
    Forr(i, 1, m + 1) SII(l[i], r[i]), Lid[l[i]].PB(i), Rid[r[i]].PB(i);
    Forr(i, 1, n + 1)
    {
        For(j, Lid[i].size()) ans[Lid[i][j]] -= Q(i, r[Lid[i][j]]); // 现在只更新了[1,L-1]内的关系以及[1,L-1]与后面元素的关系,故应在此时减去「一个属于[1,L-1],另一个属于[L,R]的」对数
        for (j = 1; j * a[i] <= n; ++j) U(pos[j * a[i]]);
        For(j, Rid[i].size()) ans[Rid[i][j]] += Q(l[Rid[i][j]], i); // 现在[1,R]内的关系均已求出,故在此时用[1,R]的对数减去[1,L-1]的对数
    }
    Forr(i, 1, m + 1) PI(ans[i]);
    return 0;
}

Comments

comments powered by Disqus