1 条题解
-
0ljt12138 LV 10 @ 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