日度归档：28 6 月, 2018

洛谷 P1120 小木棍 ［数据加强版］

发表评论

写的很绝望……看了三遍所有题解仍然69……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
int n, sum = 0;
int lens[100] = { 0 };
bool visited[100] = { false };
int sums[100] = { 0 };
int o_min = 0, o_max;
vector<int> divisors;
int min_len;
inline bool dfs(int curpos, int curvalue, int groups){
    if (curvalue == min_len){
        if (groups == sum / min_len - 1)return true;
        else{
            int i;
            for (i = 1; i <= n; i++){
                if (!visited[i])break;
            }
            assert(i != n + 1);
            visited[i] = true;
            bool flag = dfs(i, lens[i], groups + 1);
            visited[i] = false;
            return flag;
        }
    }
    bool flag_finished = false;
    for (int i = curpos + 1; i <= n; i++){
        if (curvalue + lens[n] > min_len || curvalue + sums[i]<min_len)break;
        if (visited[i] || curvalue + lens[i] > min_len)continue;
        visited[i] = true;
        if (dfs(i, curvalue + lens[i], groups))flag_finished = true;
        visited[i] = false;
        if (flag_finished)return true;
        for (int j = i + 1; j <= n; j++){
            if (lens[j] != lens[i]){
                i = j - 1;
                break;
            }
        }
    }
    return false;
}
inline bool process(int min_length){
    min_len = min_length;
    visited[1] = true;
    bool flag = dfs(1, lens[1], 0);
    visited[1] = false;
    return flag;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> lens[i];
        if (lens[i] > 50){
            i--;
            n--;
        }
    }
    sort(lens + 1, lens + n + 1, greater<int>());
    for (int i = 1; i <= n; i++){
        o_min = max(o_min, lens[i]);
        sum += lens[i];
    }
    for (int i = n; i >= 1; i--){
        sums[i] = sums[i + 1] + lens[i];
    }
    o_max = sum;
    for (int i = o_min; i <= o_max / 2; i++){
        if (o_max%i == 0)divisors.push_back(i);
    }
    divisors.push_back(o_max);
    for (int i = 0; i < divisors.size(); i++){
        if (process(divisors[i])){
            cout << divisors[i];
            break;
        }
    }
}

20180811日更新：已经AC。
这题真的很麻烦，之前做过一回，69分放弃了，今天又重新做，改到了78AC22TLE，又看题解里的优化终于改到了AC。
题解：https://www.luogu.org/blog/complexity/solution-p1120
https://www.luogu.org/blog/cm-nanyi2018/solution-p1120
https://www.luogu.org/blog/ogawa/solution-p1120

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<functional>
using namespace std;
int n,lens[70],curLen,totSum=0;
int bucket[60],lst[60],lstPtr=0;
vector<int> possibleLen;
inline int check(){
    int i;
    for(i=1;i<=lstPtr;i++)if(bucket[lst[i]]!=0)return i;
    return i;
}
inline bool dfs(int lstPos,int len){//have already added lst[lstPos] before entering this recursive function
    if(len==totSum||len==totSum-curLen)return true;
    if(len%curLen==0){
        int i=check();
        bucket[lst[i]]--;
        bool flag=dfs(i,len+lst[i]);
        bucket[lst[i]]++;
        return flag;
    }
    int curRemain=curLen-len%curLen;
    for(int i=lstPos;i<=lstPtr;i++){
        if(lst[i]>curRemain||bucket[lst[i]]==0)continue;
        bucket[lst[i]]--;
        if(dfs(i,len+lst[i])){
            bucket[lst[i]]++;
            return true;
        }
        bucket[lst[i]]++;
        if(curRemain==lst[i])return false;
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    int maxV=0;
    for(int i=1;i<=n;i++){
        cin>>lens[i];
        if(lens[i]>50){
            i--;n--;
            continue;
        }
        bucket[lens[i]]++;
        maxV=max(maxV,lens[i]);
    }
    for(int i=50;i>=1;i--)if(bucket[i]!=0)lst[++lstPtr]=i;
    for(int i=1;i<=n;i++)totSum+=lens[i];
    for(int i=maxV;i<=totSum/2;i++)if(totSum%i==0)possibleLen.push_back(i);
    possibleLen.push_back(totSum);
    bucket[lst[1]]--;
    for(int i=0;i<possibleLen.size();i++){
        curLen=possibleLen[i];
        if(dfs(1,lst[1])){
            cout<<curLen;
            return 0;
        }
    }
}