2982. 三元斐波纳奇数列

题面 统计数据 讨论
10175102262 LarsPendragon
7 年，8 月前

巨坑的一个测试点：（测试点8）4 10 10 -1 20。如果不注意程序会输出0，但正确答案是-1，因为数列中数的取值范围是1~1,000,000，不包括0。
最简单的思路大概就是分情况，-1在前三个数是一种情况，在3以后又是一种情况，因为数据少，可以直接无脑循环判断是否满足数列条件。

#include <stdio.h>
int main(void)
{
    int T, I, n, a, i;
    scanf("%d",&T);
    for(I=0; I<T; I++)
    {
        scanf("%d",&n);
        int num[n];
        for(i=0; i<n; i++){
            scanf("%d",&num[i]);
            if(num[i]==-1)
                a=i;}
        if(a==0) num[0]=num[3]-num[2]-num[1];
        else if(a==1) num[1]=num[3]-num[2]-num[0];
        else if(a==2) num[2]=num[3]-num[1]-num[0];
        else num[a]=num[a-1]+num[a-2]+num[a-3];
        for(i=0; i<n-3; i++)
            if(num[i]+num[i+1]+num[i+2]!=num[i+3] || num[i]==0 || num[i+1]==0 || num[i+2]==0 || num[i+3]==0)
                break;
        if(i==n-3)
            printf("case #%d:\n%d\n",I,num[a]);
        else
            printf("case #%d:\n-1\n",I);
    }
    return 0;
}
回复
10175102262 LarsPendragon
7 年，5 月前

C语言（C班）D题题解（溜

回复
╮ 潜心 ╰
7 年，4 月前

:::CPP

#include <stdio.h>

int fei(int num[],int n);

int main()
{
        // insert code here...
        int T;
        scanf("%d",&T);
        int t=0;
        for(t=0;t<T;t++)
        {
                int n,i;
                scanf("%d",&n);
                int num[n];
                for(i=0;i<n;i++)scanf("%d",&num[i]);
                printf("case #%d:\n%d\n",t, fei(num,n));


        }
        return 0;
}

int fei(int num[], int n)
{
        int i;
        for (i=0; i<n; i++)
        {
                if(num[i]==-1)
                {
                        if(i>=3)
                        {
                                num[i]=num[i-1]+num[i-2]+num[i-3];
                                break;
                        }
                        else if(i==0)
                        {
                                num[i]=num[3]-num[2]-num[1];
                                break;
                        }
                        else if(i==1)
                        {
                                num[i]=num[3]-num[2]-num[0];
                                break;
                        }
                        else if(i==2)
                        {
                                num[i]=num[3]-num[1]-num[0];
                                break;
                        }
                }
        }

        int answer=num[i];
        for(i=0;i<n;i++)
                if(num[i]==0)
                        return -1;
        for(i=3;i<n;i++)
        {
                if( num[i]==num[i-1]+num[i-2]+num[i-3])
                        ;
                else
                        break;

        }
        return (i==n)? answer:-1;
}
回复
aiden
5 年，7 月前 
#include <iostream>
using namespace std;

int main()
{
    int t;
    cin >> t;
    for (auto z = 0; z < t; ++z)
    {
        int A[21] = {};
        int m;
        cin >> m;
        for (auto i = 1; i <= m; ++i)
            cin >> A[i];
        int ans = 0;
        for (auto i = 1; i <= m; ++i)
        {
            if (A[i] == -1)
            {
                if (i == 1)
                    A[i] = A[i + 3] - A[i + 2] - A[i + 1];
                else if (i == 2)
                    A[i] = A[i + 2] - A[i + 1] - A[i - 1];
                else if (i == 3)
                    A[i] = A[i + 1] - A[i - 1] - A[i - 2];
                else
                    A[i] = A[i - 1] + A[i - 2] + A[i - 3];
                ans = A[i];
            }
        }
        bool legal = true;
        for (auto i = 1; i <= m; ++i)
        {
            if (A[i] <= 0)
            {
                legal = false;
                break;
            }
            else if (i >= 4 && A[i] != A[i - 1] + A[i - 2] + A[i - 3])
            {
                legal = false;
                break;
            }
        }
        cout << "case #" << z << ":" << endl;
        if (legal)
            cout << ans << endl;
        else
            cout << "-1" << endl;
    }
    return 0;
}
回复
awzhuang
4 年，7 月前

这题做的好烦躁啊= - =

include

using namespace std;

int arr[11][21];
int N[11];
int n[11];
int res[11];
int main(){
int T;
scanf(“%d”,&T);
for(int i=1;i<=T;i++){
scanf(“%d”,&n[i]);
for(int j=1;j<=n[i];j++){
scanf(“%d”,&arr[i][j]);
if(arr[i][j]==-1){
N[i]=j;
}
}
}
for(int i=1;i<=T;i++){
if(N[i]==1){
arr[i][N[i]]=arr[i][4]-arr[i][3]-arr[i][2];
}
else if(N[i]==3||N[i]==n[i]-1){
arr[i][N[i]]=arr[i][N[i]+1]-arr[i][N[i]-1]-arr[i][N[i]-2];
}
else if(N[i]==2||N[i]==n[i]-2){
arr[i][N[i]]=arr[i][N[i]+2]-arr[i][N[i]-1]-arr[i][N[i]+1];
}
else{
arr[i][N[i]]=arr[i][N[i]-3]+arr[i][N[i]-2]+arr[i][N[i]-1];
}
}
for(int i=1;i<=T;i++){
if(arr[i][N[i]]<=0){
res[i]=-1;
}
else{
res[i]=arr[i][N[i]];
}
}
for(int i=1;i<=T;i++){
for(int j=4;j<=n[i];j++){
if(arr[i][j]!=arr[i][j-3]+arr[i][j-2]+arr[i][j-1]){
res[i]=-1;
}
}
printf(“%s%d%s\n%d\n”,”case #”,i-1,”:”,res[i]);
}
}

回复
Li Dao
8 年，7 月前

来一发题解

include

using namespace std;
int T,n;
vector V;
int solve()
{
int ret;
for(int i=0;i<V.size()-3;i++)
if(V[i]==-1 || V[i+1]==-1 || V[i+2]==-1 || V[i+3]==-1)
{
if(V[i+3]==-1) ret=V[i+3]=V[i]+V[i+1]+V[i+2];
else if(V[i+2]==-1) ret=V[i+2]=V[i+3]-V[i+1]-V[i];
else if(V[i+1]==-1) ret=V[i+1]=V[i+3]-V[i+2]-V[i];
else if(V[i]==-1) ret=V[i]=V[i+3]-V[i+2]-V[i+1];
}
if(ret<=0) return -1;
for(int i=0;i>T;
for(int step=0;step>n;
V.clear();
for(int i=1;i<=n;i++)
{
int xx;cin>>xx;
V.push_back(xx);
}
printf(“case #%d:\n”,step);
cout<<solve()<<endl;
}
return 0;
}

怎么写都感觉烦，干脆，四个四个看，有-1就其他三个数算出-1那个位置的
再看是否矛盾。
如果-1那里填了负数或0，也是输出-1，这点要注意

回复
carpediem
10 年，7 月前

这个为什么不对
[em:03][em:02][em:05] 这题目坑啊。。。

回复
heliangda
5 年，8 月前

主要思路是判断-1是不是在前面三项，如果是，补全函数直接根据第四项和剩余两项计算出来， 在第四项以后就根据定义补全。
再根据补全的数，判断一下这个序列是不是三元斐波纳奇数列即可。
需要注意，如果补全的数小于等于0，则需要输出-1，而不是所填的数。
Python3 代码如下
def completeF(L, pos):
if pos == 0 :
return L[3] - L[2] - L[1]
if pos == 1 :
return L[3] - L[2] - L[0]
if pos == 2 :
return L[3] - L[1] - L[0]
if pos >= 3 :
return L[pos-1] + L[pos-2] + L[pos-3]

def checkF(L):
if len(L) < 4:
return False
for i in range(3,len(L)):
if L[i] != L[i-1] + L[i-2] + L[i-3]:
return False
return True

def return_1(L):
for i in range(len(L)):
if L[i] == -1:
return i

l = []

times = eval(input())
for i in range(times):
s = input().split()
N = int(s[0])
for j in range(1,len(s)):
l.append(int(s[j]))
pos = return_1(l)
res = completeF(l,pos)
l[pos] = res
if checkF(l) == False or res <= 0:
res = -1
l = []
print(“case #”,i,”:”,sep=”“)
print(res)

回复
10165102222
8 年，6 月前

检测多组数据都是正确的,提交上去为wrong,求大神指导

include

include

int judge(int x[],int m)
{int i;
for(i=3;i<m;)
{if(x[i]!=(x[i-1]+x[i-2]+x[i-3]))
break;
i++;}
if(i==m)return 1;
else return 0;
}
void solve()
{
int k,m,i,j,a[25],b[25];
scanf(“%d”,&m);
for(j=0;j<m;j++)
scanf(“%d”,&a[j]);
if(a[0]==-1) {a[0]=(a[3]-a[2]-a[1]);k=0;}
else if(a[1]==-1) {a[1]=(a[3]-a[2]-a[0]);k=1;}
else if(a[2]==-1) {a[2]=(a[3]-a[0]-a[1]);k=2;}
for(i=3;i<m;i++)
{if(a[i]!=-1);
else {a[i]=(a[i-1]+a[i-2]+a[i-3]);k=i;}
}if(judge(a,m))
printf(“%d\n”,a[k]);
else printf(“-1\n”);
}
int main()
{int t,i;
scanf(“%d”,&t);
for(i=0;i<t;i++)
{printf(“case #%d:\n”,i);
solve();
}return 0;
}

回复
xia4533
3 年，11 月前

注意：数列是大于1的数，不存在小于等于0的项。test2就在测这个呢、

回复
Saitama
7 年，5 月前 
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int T;
    cin >> T;
    for(int i = 0; i < T; i++)
    {
        printf("case #%d:\n", i);
        int M;
        cin >> M;
        vector <int> a(M);
        for(int j = 0; j < M; j++)
            cin >> a[j];
        int N;
        for(int j = 0; j < M; j++)
        {
            if(a[j] == -1)
            {
                if(j == 0)
                {
                    a[j] = a[j + 3] - a[j + 2] - a[j + 1];
                    N = a[j];
                    break;
                }
                else if(j == 1)
                {
                    a[j] = a[j + 2] - a[j + 1] - a[j - 1];
                    N = a[j];
                    break;
                }
                else if(j == 2)
                {
                    a[j] = a[j + 1] - a[j - 1] - a[j - 2];
                    N = a[j];
                    break;
                }
                else
                {
                    a[j] = a[j - 3] + a[j - 2] + a[j - 1];
                    N = a[j];
                    break;
                }
            }
        }
        int flag = 1;
        for(int j = 3; j < M; j++)
        {
            if(a[j] != a[j - 1] + a[j - 2] + a[j - 3])
                flag = 0;
        }
        if(flag == 1 && N >= 1 && N <= 1000000)
            cout << N << endl;
        else
            cout << -1 << endl;

    }
    return 0;
}

重做基本题

回复
Master X
7 年，7 月前

本题坑点较多。
我的解法是先输入，再遍历，把-1项替换后，比较判断。

include

using namespace std;
void solve()
{
int n;
cin>>n;
int a[n];
int wei;
int k=0;
for(int i=0;i>a[i];

}
for(int i=0;i<n;i++)
{
    if(a[i]==-1) {
    wei=i;
    if(i>=3)
    a[i]=a[i-1]+a[i-2]+a[i-3];
    if(i==0)
    a[i]=a[i+3]-a[i+2]-a[i+1];
    if(i==1)
    a[i]=a[i+2]-a[i+1]-a[i-1];
    if(i==2)
    a[i]=a[i+1]-a[i-1]-a[i-2];
          }
}

for(int i=3;i<n;i++)
{
    if(a[i]!=a[i-1]+a[i-2]+a[i-3]) {k=1;break;}
}
if(k==0&&a[wei]>=1&&a[wei]<=1000000) cout<<a[wei]<<endl;
else cout<<"-1"<<endl;

}

int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
printf(“case #%d:\n”,i);
solve();
}
}

回复
你当前正在回复 博客/题目
存在问题！

服务

首页 反馈 Polygon Wiki

开源

Github eJudge

关于我们

团队: @ultmaster, @zerol, @kblack.
联系方式: acmsupport@admin.ecnu.edu.cn