题解

1 条题解

  • 0
    @ 2016-09-03 10:51:32
    测试数据 #0: Accepted, time = 0 ms, mem = 16212 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 16208 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 16212 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 16212 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 16212 KiB, score = 10
    测试数据 #5: Accepted, time = 46 ms, mem = 16212 KiB, score = 10
    测试数据 #6: Accepted, time = 62 ms, mem = 16208 KiB, score = 10
    测试数据 #7: Accepted, time = 515 ms, mem = 16212 KiB, score = 10
    测试数据 #8: Accepted, time = 328 ms, mem = 16208 KiB, score = 10
    测试数据 #9: Accepted, time = 703 ms, mem = 16216 KiB, score = 10
    
    Accepted, time = 1669 ms, mem = 16216 KiB, score = 100
    

    坑,全是坑

    09-03   Accepted
    09-03   Wrong Answer
    09-03   Time Exceeded
    09-03   Wrong Answer
    09-03   Wrong Answer
    09-03   Wrong Answer
    09-03   Wrong Answer
    09-03   Wrong Answer
    

    思路

    差分建图,列方程,解方程即可。需要分n%3 == 0和n%3 != 0。
    1. n%3 == 0时,t[0] = t[1] = 1(其实本应该是0的,数据有误),递推即可
    2. 否则,可以证明差分建图会构建联通的有向图,设某一个点i为x(delta[i] = 0),利用bfs求出所有delta[k] = t[k] - x.再代入每一个b数组进行验证即可。


    1. #2和#8超出了int范围
    2. #7和#8为n%3 == 0,注意t[0] = t[1] = 1。
    3. 没有数据使得输出为-1.直接输出-1会爆零

    例程
    ```c++
    #include <bits/stdc++.h>
    using namespace std;

    typedef long long ll;

    ll read()
    {
    ll a = 0;
    int c;
    do c = getchar(); while(!isdigit(c));
    while(isdigit(c)) {
    a = a*10+c-'0';
    c = getchar();
    }
    return a;
    }

    const int maxn = 1000005;
    ll b[maxn], delta[maxn], n;
    queue<ll> que;

    inline int modn(int i)
    {
    return (i%n+n)%n;
    }

    inline int next(int i)
    {
    return modn(i+3);
    }

    inline int prev(int i)
    {
    return modn(i-3);
    }

    int main()
    {
    n = read();
    for (int i = 0; i < n; i++)
    b[i] = read();
    if (n%3 == 0) {
    delta[0] = delta[1] = delta[2] = 0;
    for (int i = 3; i < n; i++) {
    delta[i] = delta[i-3] + b[i-1] - b[i-2];
    //cout << delta[i] << " ";
    }
    ll standard = b[1];
    if (standard != b[0] - delta[n-1] || standard != b[n-1] - delta[n-2] - delta[n-1])
    puts("-1");
    else {
    for (int i = 0; i < n; i++)
    if (i%3 == 0 || i%3 == 1)
    printf("%lld ", delta[i] + 1);
    else
    printf("%lld ", delta[i] + b[1] - 2);
    }
    } else {
    memset(delta, -1, sizeof delta);
    delta[0] = 0;
    que.push(0);
    while (!que.empty()) {
    ll t = que.front(); que.pop();
    if (delta[next(t)] == -1) {
    delta[next(t)] = delta[t] + b[modn(t+2)] - b[modn(t+1)];
    que.push(next(t));
    }
    if (delta[prev(t)] == -1) {
    delta[prev(t)] = delta[t] + b[modn(t-2)] - b[modn(t-1)];
    que.push(prev(t));
    }
    }
    ll x = (b[0] - (delta[n-1] + delta[0] + delta[1]))/3;
    for (int i = 0; i < n; i++)
    if ((b[i] - delta[i] - delta[modn(i-1)] - delta[modn(i+1)])%3 != 0 ||
    (b[i] - delta[i] - delta[modn(i-1)] - delta[modn(i+1)])/3 != x) {
    puts("-1");
    return 0;
    }
    for (int i = 0; i < n; i++)
    printf("%lld ", x+delta[i]);
    }
    return 0;
    }

    ```

    vijos生第一次沙发。顺便,纪念本题5th AC & 历史最快。

  • 1

信息

ID
1928
难度
8
分类
a 点击显示
标签
(无)
递交数
92
已通过
14
通过率
15%
被复制
2
上传者