3686. 回文串

shwei
#include <bits/stdc++.h>
using namespace std;

vector <int> vec(1000010);
int main (void) {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        vec[i] = num;
    }

    int i = 0, j = n - 1, cnt = 0;
    while (i < j) {
        if (vec[i] == vec[j]) {
           // cout << vec[i] << " " << vec[j] << " " << endl;
            i++;
            j--;
        } else {
            long long left = vec[i] + vec[i + 1];
            long long right = vec[j] + vec[j - 1];
            if (vec[i] < vec[j]) {     
                vec[i]= 0;
                vec[i + 1] = left;
                cnt++;
                i++;
            } else {
                vec[j] = 0;
                vec[j - 1] = right;
                cnt++;
                j--;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}
mansoup

vector泛型应该为long long

shwei

嗯,对的

zasleon

花了大半天,使用了n多种脑残的办法,最终想到一个很简单的办法实现了。
最后卡在第66题,把所有变量从int变为long long就通过了。

include

using namespace std;
long long k;
long long up,down;
int main()
{

long long count;
cin>>down;
long long *kkk=new long long[down];
for(k=0;k<down;k++)
cin>>kkk[k];
up=0;
count=0;

//1 3 2 1 4 5 6 7 5 5 1
//for(k=0;k{if(kkk[up]>kkk[down])
{
//cout<<”kkk[“<kkk[“<<n-i-1<<”]”<<endl;//测试输出2
kkk[down-1]=kkk[down]+kkk[down-1];

down=down-1;count++;

//for(k=0;k<n;)cout<<kkk[k++]<<" ";cout<<endl;//测试输出4
}

else if(kkk[up]<kkk[down])
{
//cout<<”kkk[“<<i<<”]<kkk[“<<n-i-1<<”]”<<endl;//测试输出5
kkk[up+1]=kkk[up]+kkk[up+1]; //cout<<”kkk[“<<i<<”]=”<<kkk[i]<<endl;//测试输出6

    //cout<<"kkk["<<k<<"]="<<kkk[k]<<endl;//测试输出7
up=up+1;count++;  
//for(k=0;k<n;k++) cout<<kkk[k]<<" ";cout<<endl;//测试输出8

}

else if(up>=down) break;
else if(kkk[up]==kkk[down])

}

cout<<count;
return 0;
}

blackducker

我也是测试66卡住,测试跑的是什么,只是将hash[]的int改成了long就通过了,要求在0到1e9之间,int应该可以满足,求解??

include

long hash[1000000];

int main(void){
int n;
for (int i = 0; i < 1000000; i++) {
hash[i]=0;
}
while(scanf(“%d”,&n)!=EOF)
{
int l=0;
int r=n-1;
int num=0;
for (int i = 0; i < n; i++) {
scanf(“%d”,&hash[i]);
}
while(lhash[r])
{
num++;
hash[r-1]=hash[r]+hash[r-1];
r–;
}
else
{
l++;
r–;
}
}
//判断是否成功回文,并输出num,或者返回-1
if(hash[l]==hash[r])
printf(“%d\n”,num);
else
return -1;
}
return 0;
}

dingzy

可能因为这个要好几项一起加起来,可能会超过int的最大值

kworld

你这贴的不完整吧。
我用java搞了一个,卡在8,超过2s(2.3s)

哪位大神看看怎么优化。(逻辑上,好像无法使用多线程,想不出优化方法了)

import java.util.Scanner;

public class MyP2 {
public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    while(sc.hasNext())
    {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        //两头判断小部先合并
        int head=0, tail = n-1;
        int times = 0;
        while(head<tail)
        {
            if(arr[head]>arr[tail])
            {
                //tail部分合并
                arr[tail-1] += arr[tail];
                tail--;
                times++;
            }else if(arr[head]<arr[tail])
            {
                //head部合并
                arr[head+1] += arr[head];
                head++;
                times++;
            }else
            {
                head++;
                tail--;
            }
        }
        System.out.println(times);
    }
    sc.close();
}

}

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