Problem #3239 - ECNU Online Judge

Saitama

6 年，7 月前

eoj跑的真他娘的快啊

回复 4 0

Gottfried_Leibniz

4 年，7 月前

此题能够使用枚举法完全是因为数据量过小
O(n^3)的算法在更大的数据量下是完全行不通的
dfs才是此类题目的精髓所在，感兴趣的同学可以细品一下

#include <iostream>
#include <vector>
#include <algorithm>
//#define ACM
#define For(i,m,n) for(int32_t i = m; i < n; i++)
using namespace std;
int32_t ans = 1, T = 0, n = 0;
vector<int32_t>seq;
int32_t dfs(const int32_t& k, const bool& flag, int32_t base);
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
#ifdef ACM
    freopen("最长等差数列.in","r",stdin);
#endif // ACM
    cin >> T;
    For(i,0,T){
        ans = 1;
        cout << "case #" << i << ":\n";
        cin >> n;
        seq = vector<int32_t>(n);;
        For(j,0,n){
            cin >> seq[j];
        }
        sort(seq.begin(),seq.end());
        For(k,0,n-1){
            ans = max(ans,dfs(k,0,0));
        }
        cout << ans << '\n';
    }
    return 0;
}

int32_t dfs(const int32_t& k, const bool& flag, int32_t base)
{
    int32_t len = 1;
    if(k == n - 1){
        return len;
    }
    if(flag == 0){
        int32_t plen = len;
        For(i,k+1,n){
            base = seq[i] - seq[k];
            int32_t tmp = plen + dfs(i,1,base);
            len = max(tmp,len);
        }
    }
    if(flag == 1){
        int32_t plen = len;
        For(i,k+1,n){
            if(seq[i] - seq[k] == base){
                int32_t tmp = plen + dfs(i,1,base);
                len = max(tmp,len);
            }
        }
    }
    return len;
}

回复 3 0

10175102262 LarsPendragon

6 年，7 月前

被暴力标签骗了……直接动手写，后来才发现有问题……然后大改……
虽然说也是暴力没错……
给几组数据自行体会：一、10 1 1 2 2 3 3 4 4 5 5（答案5）；二、7 1 2 4 5 6 8 9（答案4）
附C代码：

#include <stdio.h>
#include <stdlib.h>
int cmp(const void*a, const void*b)
{
    int *p1=(int*)a, *p2=(int*)b;
    return *p1-*p2;
}
int main()
{
    int T, I;
    scanf("%d",&T);
    for(I=0; I<T; I++)
    {
        int n, i, j, k, cnt, max=1, x, y, num[100];
        scanf("%d",&n);
        for(i=0; i<n; i++) scanf("%d",&num[i]);
        qsort(num, n, sizeof(int), cmp);
        if(n==2) max=2;
        else if(n>2)
        {
            for(i=0; i<n-2; i++)
            {
                for(j=i+1; j<n-1; j++)
                {
                    cnt=2;
                    x=num[j]-num[i];
                    y=num[j];
                    for(k=j+1; k<n; k++) if(!(num[k]-y-x)) {y=num[k]; cnt++;}
                    if(cnt>max) max=cnt;
                }
            }
        }
        printf("case #%d:\n%d\n",I,max);
    }
    return 0;
}

回复 3 0

10205101536

3 年，8 月前

include

eoj跑的真的太快了，纯暴力，O（n^3）都给过了。。。。
注意是在数组中选取最多的数组成等差数列，leetcode上有道题是选取子序列组成等差数列，别搞混了。eoj这个可以先把数组排下序，再依次遍历就可以转换成选取子序列的算法了
using namespace std;
int getMax(int a, int b) {
return a > b ? a : b;
}
int main() {
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int n;
cin >> n;
int gap;
vectorarr;
int temp = 0;
int max = 1;
int val;
int tempNum;
for (int i = 0; i < n; i++) {
cin >> val;
arr.push_back(val);
}
sort(arr.begin(),arr.end());
for (int i = 0; i < n; i++) {
for (int k = i + 1; k < n; k++) {
gap = arr[k] - arr[i];
temp = 2;
tempNum = arr[k];
for (int j = k + 1; j < n; j++) {
if (arr[j] - tempNum == gap) {
temp++;
tempNum = arr[j];
}
}
max = getMax(max, temp);
}
}
printf(“case #%d:\n”, i);
cout << max << endl;

}

回复 0 0

FisherKK

3 年，7 月前

EOJ太快了~，我都被自己逗笑了

回复 0 0

FisherKK

3 年，7 月前

#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int T, N;
void solve();
const int MAXN = 100 + 5;
int arr[MAXN];
int sumMax;
int main() {
    #ifndef ONLINE_JUDGE
    freopen("a.txt", "r", stdin);
    #endif
    cin >> T;
    for (int i = 0; i < T; i++) {
        cout << "case #" << i << ":\n";
        cin >> N;
        for (int i = 0; i < N; i++) cin >> arr[i];
        solve();
    }
}
void calSum(int dx) {
    vector<int> Vi;
    for (int i = 0; i < N && (N - i) >= sumMax; i++) {
        Vi.clear(); Vi.push_back(arr[i]);
        for (int j = i + 1; j < N; j++) 
            if (arr[j] - Vi.back() == dx) Vi.push_back(arr[j]);
        if (Vi.size() > sumMax) sumMax = Vi.size();
    }
}
void solve() {
    sort(arr, arr + N);
    sumMax = 0;
    for (int i = 0; i <= 100; i++)
        calSum(i);
    cout << sumMax << endl;
}

回复 0 0

Master X

6 年，7 月前

每次做这种题目的时候
我就在想
又到了挑战EOJ速度的时候了…………
不要想任何骚代码，直接暴力！

1.我们第一个枚举的是起始点i
2.枚举差点j，即我们当前选择的差为a[j]-a[i]（i+1≤j≤n）
3.枚举剩余部分k，我们在遍历时便可以查询是否是等差序列，如果差＞我们选择的差，就可以Break
4.求过程中最大长度
时间复杂度O(nlogn+n^3)

回复 0 0

3239. 最长的等差数列

include

include

include

include

服务

开源

关于我们