Znzryb's Blog
0%

Posted on Edited on

题目大意

求解无限连分数 x = a + 1/(a + 1/(a + …)) 的值。即求解方程 x = a + 1/x 的正根。

AC代码 牛顿迭代法

x=a+1a+1a+1a+⋯x=a + \frac{1}{a + \frac{1}{a + \frac{1}{a + \cdots}}}

因为是无限的递归，可以把a下面的看成一个整体，其实也是x，然后你就把这个问题转化成了求一元二次方程。

x=a+1xx = a + \frac{1}{x} 

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
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int T;
double a;

double solve(double a) {
    // 使用公式直接计算连分数的解
    return (a + sqrt(a * a + 4)) / 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> T;
    for(int _ = 1; _ <= T; _++) {
        cin >> a;
        double ans = solve(a);
        cout << setprecision(24) << ans << endl;
    }

    return 0;
}
// AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71962585

Posted on Edited on

题目大意

有 N 个候选人争夺 M 个席位，共有 K 张票。目前已知每个候选人已获得的票数，以及剩余未投的票数。对于每个候选人，判断在最坏情况下（即剩余票数的分配对他最不利时），他是否还能通过获得一定数量的剩余票数来确保当选（进入前 M 名）。如果是，求出他至少需要再获得多少票；否则输出 -1。

AC代码

二分答案，检查器的设计重点在于
// 防止选用自己作为自己的竞争对手

1
2
if(idx-needOver-rectifyIdx<0)  // <0 说明人不够了，一共就没那么多人（n=m）
        return true;

https://atcoder.jp/contests/abc373/submissions/58823933

二分检查器的核心行（加粗行）思路

image

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
79
80
81
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const ll N=2e5+10;//                离散化
ll n,m,k,a[N],countedBallots,remain,li[N],ans[N],oa[N],sumA[N];
ll stand=1e18;
inline bool check(ll gainBallots,ll indexOfCandidate) {
    ll currBallots=oa[indexOfCandidate]+gainBallots;
    if(currBallots<stand)
        return false;
    ll idx=upper_bound(&a[1],&a[n+1],currBallots)-&a[0]-1;
    ll diff=0;
    ll overi=n+1-(upper_bound(&a[1],&a[n+1],currBallots)-&a[0]); // 返回的是比他大的数的索引，要包含这个数，n+1-。。。
    ll needOver=m-overi,rectify=0,rectifyIdx=0;
    // 防止选用自己作为自己的竞争对手
    ll candidateIdx=li[indexOfCandidate]-1;
    if(candidateIdx<=idx && candidateIdx>idx-needOver) {
        rectify=oa[indexOfCandidate],rectifyIdx=1;
    }
    // hand 11 过不了原因是n=m，我没有考虑人不够的情况 不知道他给你指到哪里去了
    if(idx-needOver-rectifyIdx<0)  // <0 说明人不够了，一共就没那么多人（n=m）
        return true;
    diff=gainBallots+(currBallots+1)*needOver-(sumA[idx]-sumA[idx-needOver-rectifyIdx]-rectify);
    // 就是下面循环的前缀和写法
    // for(ll i=idx;cnt<needOver;i--) {
    //     diff+=(currBallots+1-a[i]);
    //     cnt++;
    // }
    if(diff>remain)     // diff需要严格大于remain，不能等于，因为等于是可以超过的
        return true;
    return false;
}
inline ll bsearch(ll i) {       // 二分模版
    ll l=0,r=remain;
    while(l<r) {
        ll mid=l+r>>1;
        if(check(mid,i))
            r=mid;      // mid是有可能是答案的，r=mid
        else
            l=mid+1;
    }
    return l;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        countedBallots+=a[i];
        oa[i]=a[i];
    }
    remain=k-countedBallots;
    sort(&a[1],&a[n+1]); // 还是得升序
    for(int i=1;i<=n;i++) {     // 前缀和
        sumA[i]=sumA[i-1]+a[i];
    }
    for(int i=1;i<=n;i++) {
        // 返回第一个比寻找元素大的元素 -&a[0]后就是索引 所以其实lower_bound()不太支持降序排列离散化
        li[i]=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        if(n+1-li[i]<m)
            stand=min(stand,oa[i]);
    }
    for(int i=1;i<=n;i++) {
        if(oa[i]+remain<stand) {    // 直接加都不行，跳过
            ans[i]=-1;continue;
        }
        ans[i]=bsearch(i);
    }
    for(int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    return 0;
}
// 只WA了一个点 https://atcoder.jp/contests/abc373/submissions/58815831
// AC https://www.luogu.com.cn/record/182236761
// AC https://atcoder.jp/contests/abc373/submissions/58823933

心路历程

我现在的想法就是我认为这就是博弈论，就是我投的票要竭力使这个人掉出m人的队列，而然后剩余的票一定是投在这个人身上
ans[i]=ceil((remain-diff)*1.0/(cnt+1));的来历

image

半成品代码

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
79
80
#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
const ll N=2e5+10;//                离散化
ll n,m,k,a[N],countedBallots,remain,li[N],ans[N],oa[N],toli[N]; // toli是通过a下标访问li的转介层
ll borderlineStand=0; // 临界标准，说人话就是不满足条件但最大的。
ll stand=1e18;// 标准与标准i，就是满足条件最小的值以及在a[i]的index
set<ll> vis;
void debug() {
    cout<<"stand: "<<stand<<" borderlineStand:"<<borderlineStand<<endl;
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++) {
        cout<<li[i]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++) {
        cout<<toli[i]<<" ";
    }
    cout<<endl<<"ans: ";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        countedBallots+=a[i];
    }
    remain=k-countedBallots;
    for(int i=1;i<=n;i++) {
        oa[i]=a[i];
    }
    sort(&a[1],&a[n+1]); // 还是得升序
    for(int i=1;i<=n;i++) {
        // 返回第一个比寻找元素大的元素 -&a[0]后就是索引 所以其实lower_bound()不太支持降序排列离散化
        li[i]=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        if(n+1-li[i]<m)
            stand=min(stand,oa[i]);
        else
            borderlineStand=max(borderlineStand,oa[i]);
    }
    for(int i=1;i<=n;i++) {
        if(vis.count(oa[i]))
            continue;
        ll s=lower_bound(&a[1],&a[n+1],oa[i])-&a[0];
        ll e=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        vis.insert(oa[i]);
        for(ll j=s;j<e;j++) {
            toli[j]=i;       // toli 也可以认为是排序后元素位置->排序前元素位置
        }
    }
    for(int i=1;i<=n;i++) {
        ll ia=li[i]-1,vi=oa[i],overi=n+1-li[i];
        if(oa[i]+remain<stand) {
            ans[i]=-1;continue;
        }
        if(oa[i]>=stand) { // 这里是原来就已经选上，如何在剩余选票中保住位置
            ll diff=0,cnt=0,needOver=m-overi;
            for(ll j=ia-1;cnt<needOver;j--)  // 当cnt=needOver时，说明已经加完，此时不应该再加了
                diff+=vi+1-a[j],cnt+=1; //要超到i前面去，至少要比i的值大1吧
            if(remain-diff<0) {
                ans[i]=0;continue;
            }else {     // remain-i-(diff+cnt*i)=0  (方程式，i为需要的)
                ans[i]=ceil((remain-diff)*1.0/(cnt+1));
            }
        }
    }
    debug();
    for(int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    return 0;
}

https://atcoder.jp/contests/abc373/submissions/58808859

五彩缤纷的提交

我做着做着发现完全不需要分两种情况，这个提交是分两种情况的。

然后check（）可以用前缀和优化

像这道题一样

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
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
const ll N=2e5+10;//                离散化
ll n,m,k,a[N],countedBallots,remain,li[N],ans[N],oa[N],sumA[N];
ll stand=1e18;// 标准与标准i，就是满足条件最小的值以及在a[i]的index
set<ll> vis;
inline bool check(ll gainBallots,ll indexOfCandidate) {
    ll currBallots=oa[indexOfCandidate]+gainBallots;
    if(currBallots<stand)
        return false;
    ll idx=upper_bound(&a[1],&a[n+1],currBallots)-&a[0]-1;
    ll overi=n+1-(upper_bound(&a[1],&a[n+1],currBallots)-&a[0]); // 返回的是比他大的数的索引，要包含这个数，n+1-。。。
    ll needOver=m-overi;
    ll cnt=0,diff=gainBallots;
    for(ll i=idx;cnt<needOver;i--) {
        diff+=(currBallots+1-a[i]);
        cnt++;
    }
    if(diff>remain)     // diff需要严格大于remain，不能等于，因为等于是可以超过的
        return true;
    return false;
}
inline ll bsearch(ll i) {       // 二分模版
    ll l=stand-oa[i],r=remain;
    while(l<r) {
        ll mid=l+r>>1;
        if(check(mid,i))
            r=mid;      // mid是有可能是答案的，r=mid
        else
            l=mid+1;
    }
    return l;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        countedBallots+=a[i];
    }
    remain=k-countedBallots;
    for(int i=1;i<=n;i++) {
        oa[i]=a[i];
    }
    sort(&a[1],&a[n+1]); // 还是得升序
    for(int i=1;i<=n;i++) {
        sumA[i]=sumA[i-1]+a[i];
    }
    for(int i=1;i<=n;i++) {
        // 返回第一个比寻找元素大的元素 -&a[0]后就是索引 所以其实lower_bound()不太支持降序排列离散化
        li[i]=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        if(n+1-li[i]<m)
            stand=min(stand,oa[i]);
    }
    for(int i=1;i<=n;i++) {
        if(vis.count(oa[i]))
            continue;
        ll s=lower_bound(&a[1],&a[n+1],oa[i])-&a[0];
        ll e=upper_bound(&a[1],&a[n+1],oa[i])-&a[0];
        vis.insert(oa[i]);
    }
    for(int i=1;i<=n;i++) {
        ll ia=li[i]-1,vi=oa[i],overi=n+1-li[i];
        if(oa[i]+remain<stand) {    // 直接加都不行，跳过
            ans[i]=-1;continue;
        }
        if(oa[i]>=stand) { // 这里是原来就已经选上，如何在剩余选票中保住位置
            ll diff=0,cnt=0,needOver=m-overi;
            for(ll j=ia-1;cnt<needOver;j--)  // 当cnt=needOver时，说明已经加完，此时不应该再加了
                diff+=vi-a[j],cnt+=1; //要超到i前面去，至少要比i的值大1吧
            if(remain-diff<0) {
                ans[i]=0;continue;
            }else {     // remain-i-(diff+cnt*i)=0  (方程式，i为需要的)
                ans[i]=ceil((remain-diff)*1.0/(cnt+1));
            }
        }else {         // 这里是原来没选上，如何在剩余选票中抢到位置
            ans[i]=bsearch(i);
        }
    }
    for(int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    return 0;
}

Posted on Edited on

题目大意

给定一棵树，边有边权。需要在树上选一条长度不超过 s 的路径（核心路径），使得树上所有点到这条路径的距离的最大值最小。

https://www.luogu.com.cn/record/178248030 50pts TLE

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <vector>
#include <deque>
#include <unordered_map>
#include <string>
const int maxn=3e5+7;
using namespace std;    //                   记录路径 支路路径长度                   记录直径及其先后顺序
int n,s,u,v,w,maxDis,disNode,A,B,pa[maxn],dist[maxn],upDis,upNode,I,cnt,flag[maxn],ldis[maxn],ans=2e9+7;
//                                                                                ldis两端路径长度（可通过直径减去其算出另外一端）
int ecc,Lcalibre,Rcalibre,lGive,rGive,L,R,mC;
int sDis[maxn],eDis[maxn],S,E;    // 当点为start || end 时对长度的贡献
bool vis[maxn];
vector<int> g[maxn];
vector<int> calibre;
deque <int> q;
unordered_map<string,int> l;
void dfs(int fa,int dis) {
    for(vector<int>::iterator it=g[fa].begin();it!=g[fa].end();it++) {
        if(vis[*it]==false && flag[*it]==0) {
            vis[*it]=true,pa[*it]=fa;
            string fait=to_string(fa)+'_'+to_string(*it);
            if(dis+l[fait]>maxDis)
                disNode=*it,maxDis=dis+l[fait];
            dfs(*it,dis+l[fait]);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n-1;i++) {
        cin>>u>>v>>w;
        string uv=to_string(u)+'_'+to_string(v);
        string vu=to_string(v)+'_'+to_string(u);
        l[uv]=w;
        l[vu]=w;
        g[u].push_back(v);g[v].push_back(u);
    }
    vis[1]=true;
    dfs(1,0);
    // 复位以及存储 两遍dfs
    A=disNode;
    fill(&vis[1],&vis[n+1],false);
    maxDis=0,vis[A]=true,pa[A]=A;
    dfs(A,0);
    B=disNode;
    I=B;
    while(true) {
        flag[I]=++cnt;
        string IupNode=to_string(I)+'_'+to_string(upNode);
        ldis[I]=upDis+l[IupNode];
        upDis=ldis[I],upNode=I;
        calibre.push_back(I);
        if(I==pa[I])
            break;
        I=pa[I];
    }
    mC=ldis[A]; // mC即直径长度
    fill(&vis[1],&vis[n+1],false);
    for(int i=0;i<calibre.size();i++) {
        maxDis=0,vis[calibre[i]]=true;
        dfs(calibre[i],0);
        dist[calibre[i]]=maxDis;
        // cout<<calibre[i]<<" ";
    }
    // cout<<endl;
    // 填充sdis 通过递推
    for(int i=0;i<calibre.size();i++) {
        int ci=calibre[i],ci_1= i+1<calibre.size() ? calibre[i+1]:calibre[i];
        sDis[ci]=max(dist[ci],S);
        string ciCi_1=to_string(ci)+'_'+to_string(ci_1);
        S=max(S+l[ciCi_1],dist[ci]);
    }
    // 填充edis 通过递推
    for(int i=calibre.size()-1;i>=0;i--) {
        int ci=calibre[i],ci_1= i-1>=0 ? calibre[i-1]:calibre[i];
        eDis[ci]=max(dist[ci],E);
        string ciCi_1=to_string(ci)+'_'+to_string(ci_1);
        E=max(E+l[ciCi_1],dist[ci]);
    }
    // 双指针+单调队列(deque实现，因为要从后面出队，里面存的实际上是编号)
    while(L<=R && R<calibre.size()) {
        int cl=calibre[L],cr=calibre[R];
        if(ldis[cr]-ldis[cl]>s) {
            if(q.front()<L+1)   q.pop_front();  // 判断队首元素是否过期
            L++;
            continue;
        }
        while(!q.empty() && dist[cr]>dist[calibre[q.back()]]) {
            q.pop_back();
        }
        q.push_back(R);
        ecc=max(sDis[cl],eDis[cr]);
        ecc=max(ecc,dist[calibre[q.front()]]);
        ans=min(ecc,ans);
        // cout<<L<<" "<<R<<" "<<ans<<" "<<ecc<<endl;
        R++;
    }
    cout<<ans<<endl;
    // debug
    // for(int i=1;i<=n;i++) {
    //     cout<<sDis[i]<<" ";
    // }
    // cout<<endl;
    // for(int i=1;i<=n;i++) {
    //     cout<<eDis[i]<<" ";
    // }
    return 0;
}

Posted on Edited on

AC代码与思路

反向建边，然后注意bfs的逻辑一定要清楚，要以什么为当前点，什么为父节点，不要混淆。

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
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
typedef long long ll;
const ll MAXN=2e5+10;
ll n,m,ans[MAXN];
bool vis[MAXN];
struct edge {
    ll u,v,w;
};
vector<edge> e[MAXN];
edge make_edge(ll u,ll v,ll w) {
    edge a;a.u=u;a.v=v;a.w=w;
    return a;
}
deque <edge> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        ll ui,vi,wi;
        cin>>ui>>vi>>wi;
        e[ui].push_back(make_edge(ui,vi,wi));   // 其实这里理论上只需要存vi，wi 但因为懒得改就多存了，1024MB用不掉
        e[vi].push_back(make_edge(vi,ui,-wi));  // 反向建边，精髓
    }
    for(int i=1;i<=n;i++) {
        if(vis[i])
            continue;
        q.clear(); //         i为当前点
        q.push_back(make_edge(0,i,0));  // 该连通块起始点可以认为是从i（该连通块起始点）到到0点
        while (!q.empty()) {
            ll ui=q.front().u,vi=q.front().v,wi=q.front().w;
            q.pop_front();
            if(vis[vi])
                continue;
            for(int j=0;j<e[vi].size();j++) {
                if(!vis[e[vi][j].v])
                    q.push_back(make_edge(e[vi][j].u,e[vi][j].v,e[vi][j].w));
            }
            vis[vi]=true;
            ans[vi]=ans[ui]+wi;
        }
    }
    for(int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}
//AC https://atcoder.jp/contests/abc373/submissions/58587858
//AC https://www.luogu.com.cn/record/181055323

心路历程

这个代码稍微有点搞笑，样例都没过

https://atcoder.jp/contests/abc373/submissions/58559275

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
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll MAXN=2e5+10;
ll n,m,ans[MAXN];
struct edge {
    ll u,v,w;
};
vector<edge> e[MAXN];
edge make_edge(ll u,ll v,ll w) {
    edge a;a.u=u;a.v=v;a.w=w;
    return a;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        ll ui,vi,wi;
        cin>>ui>>vi>>wi;
        e[ui].push_back(make_edge(ui,vi,wi));   // 其实这里理论上只需要存vi，wi 但因为懒得改就多存了，1024MB用不掉
    }
    for(int i=1;i<=n;i++) {
        while (!e[i].empty()) {
            ll ui=e[i].back().u,vi=e[i].back().v,wi=e[i].back().w;
            e[i].pop_back();
            ans[vi]=ans[ui]+wi;
        }
    }
    for(int i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}

我仔细想了一下这个问题，发现如果不知道次序就很难解，于是我仔细开始想拓扑排序的可能性。

想不到确实不是。

这句第一个条件其实是没有重复路，二条件是规定有向图，没提到过无环

image

而且就算知道次序也会坐牢

image

可以走反边5→2→1→3→6(其中 2→1 以及 3→6 是反边)

Posted on Edited on

AC代码与思路

相比于最后一次TLE背包提交，加了以下这些

1
for(int j=1;j<=x-sumYen;j++) {  // 背包容量为钱，背包价值为生产力
1
2
if(sumYen>x)
     return false;

主要思路是二分答案加背包dp

背包容量为钱，背包价值为能加工多少产品

通过背包dp让加工产品最大化

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
// https://atcoder.jp/contests/abc374/tasks/abc374_e
#include <iostream>
#include <cmath>
typedef long long ll;
using namespace std;
const ll MAXN=105,MAXANS=static_cast<ll>(1e9)+7,MAXA=1e7+7;
int n,x,mach[MAXN][6];
int dp[MAXA];
inline bool check(ll needCap) {
    ll sumYen=0;
    for(int i=1;i<=n;i++) {
        dp[0]=0;
        int cap1=mach[i][1],p1=mach[i][2],cap2=mach[i][3],p2=mach[i][4];
        bool isBreak=false;
        if(sumYen>x)
            return false;
        for(int j=1;j<=x-sumYen;j++) {  // 背包容量为钱，背包价值为能加工多少产品
            int up1=j-p1,up2=j-p2;
            if(up1>=0)
                dp[j]=dp[up1]+cap1;
            if(up2>=0)
                dp[j]=max(dp[j],dp[up2]+cap2);
            if(dp[j]>=needCap) {
                sumYen+=j;isBreak=true;break;
            }
        }
        if(!isBreak)
            return false;
    }
    if(sumYen<=x)
        return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++) {
            // cap1      price1 per U
        cin>>mach[i][1]>>mach[i][2]>>mach[i][3]>>mach[i][4];
    }
    ll l=0,r=MAXANS;
    while(l<r) {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}
// AC 64 个点 https://atcoder.jp/contests/abc374/submissions/58537183 已经比较接近了
// 就TLE了3个点 https://atcoder.jp/contests/abc374/submissions/58545771
// AC https://atcoder.jp/contests/abc374/submissions/58545889
// AC https://www.luogu.com.cn/record/180827335

以下是错误提交记录与心路历程

这个程序实际上没啥太大问题，但是即便开long long minYen还是超范围溢出了。

这个题目再次证明了，二分的题目r不能设太大，一个是复杂度，还有一个是溢出。

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
// https://atcoder.jp/contests/abc374/tasks/abc374_e
#include <iostream>
typedef long long ll;
using namespace std;
const ll MAXN=105,MAXANS=static_cast<ll>(1e13)+7;
ll n,x,mach[MAXN][6];
inline bool check(ll needCap) {
    ll sumYen=0;
    for(int i=1;i<=n;i++) {
        if(sumYen>x)
            return false;
        ll cap1=mach[i][1],p1=mach[i][2],cap2=mach[i][3],p2=mach[i][4];
        ll minYen=0;ll needMach1=(needCap-1)/cap1+1,needMach2=(needCap-1)/cap2+1; // (a-1)/b +1
        minYen=needMach1*p1;          // 向上取整的trick
        minYen=min(minYen,needMach2*p2); 
        sumYen+=minYen;
    }
    if(sumYen<=x)
        return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++) {
            // cap1      price1 per U
        cin>>mach[i][1]>>mach[i][2]>>mach[i][3]>>mach[i][4];
    }
    ll l=0,r=MAXANS;
    while(l<r) {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}
// AC 34 WA 64 https://atcoder.jp/contests/abc374/submissions/58535735

原来两台机子都能用！那check()函数写起来是比较麻烦

1
2
Both machines S_i and T_i can be used for process i.
If you purchase both machines S_i and T_i, the number of items that can be processed in process i will be the sum of the items processed by both machines.

AC 64 个点 https://atcoder.jp/contests/abc374/submissions/58537475

加上了对于组合的判定

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
// https://atcoder.jp/contests/abc374/tasks/abc374_e
#include <iostream>
typedef long long ll;
using namespace std;
const ll MAXN=105,MAXANS=static_cast<ll>(1e10)+7;
ll n,x,mach[MAXN][6];
inline bool check(ll needCap) {
    ll sumYen=0;
    for(int i=1;i<=n;i++) {
        if(sumYen>x)
            return false;
        ll cap1=mach[i][1],p1=mach[i][2],cap2=mach[i][3],p2=mach[i][4];
        ll minYen;ll needMach1=(needCap-1)/cap1+1,needMach2=(needCap-1)/cap2+1; // (a-1)/b +1
        minYen=min(needMach1*p1,needMach2*p2);
        ll firstMach1=needCap/cap1,remainMach2=(needCap-firstMach1*cap1-1)/cap2+1;
        ll priceComb1=firstMach1*p1+remainMach2*p2;
        ll firstMach2=needCap/cap2,remainMach1=(needCap-firstMach2*cap2-1)/cap1+1;
        ll priceComb2=firstMach2*p2+remainMach1*p1;;
        minYen=min(minYen,min(priceComb1,priceComb2));
        sumYen+=minYen;
    }
    if(sumYen<=x)
        return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++) {
            // cap1      price1 per U
        cin>>mach[i][1]>>mach[i][2]>>mach[i][3]>>mach[i][4];
    }
    ll l=0,r=MAXANS;
    while(l<r) {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}
// AC 64 个点 https://atcoder.jp/contests/abc374/submissions/58537183 已经比较接近了

我怀疑是我的向上取整模版的问题

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <cmath>
using namespace std;
long long a=0;
int main()
{
    cout<<-1/782<<endl;
    std::cout << (0-1)/782+1 << std::endl;   // 模版行
    cout<<ceil(a/1.0/782)<<endl;
    return 0;
}
1
2
3
0
1
0

毫无疑问，0/782=0，你就算加ceil()也应该是0，但显然我们的模版出了问题。

哎，用系统ceil（）提交了一遍，发现又WA了，和前面一模一样，只能说就这样吧，累了。

https://atcoder.jp/contests/abc374/submissions/58539387

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
// https://atcoder.jp/contests/abc374/tasks/abc374_e
#include <iostream>
#include <cmath>
typedef long long ll;
using namespace std;
const ll MAXN=105,MAXANS=static_cast<ll>(1e10)+7;
ll n,x,mach[MAXN][6];
inline bool check(ll needCap) {
    ll sumYen=0;
    for(int i=1;i<=n;i++) {
        if(sumYen>x)
            return false;
        ll cap1=mach[i][1],p1=mach[i][2],cap2=mach[i][3],p2=mach[i][4];
        ll minYen;ll needMach1=ceil(needCap/1.0/cap1),needMach2=ceil(needCap/1.0/cap2); // (a-1)/b +1
        minYen=min(needMach1*p1,needMach2*p2);
        ll firstMach1=needCap/cap1,remainMach2=ceil((needCap-firstMach1*cap1)/1.0/cap2);
        ll priceComb1=firstMach1*p1+remainMach2*p2;
        ll firstMach2=needCap/cap2,remainMach1=ceil((needCap-firstMach2*cap2)/1.0/cap1);
        ll priceComb2=firstMach2*p2+remainMach1*p1;;
        minYen=min(minYen,min(priceComb1,priceComb2));
        sumYen+=minYen;
    }
    if(sumYen<=x)
        return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++) {
            // cap1      price1 per U
        cin>>mach[i][1]>>mach[i][2]>>mach[i][3]>>mach[i][4];
    }
    ll l=0,r=MAXANS;
    while(l<r) {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}
// AC 64 个点 https://atcoder.jp/contests/abc374/submissions/58537183 已经比较接近了

引入了性价比概念，但发现连样例都过不了😂，还是要用dp。

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
// https://atcoder.jp/contests/abc374/tasks/abc374_e
#include <iostream>
#include <cmath>
typedef long long ll;
using namespace std;
const ll MAXN=105,MAXANS=static_cast<ll>(1e9)+7,MAXA=1e7+7;
ll n,x,mach[MAXN][6];
int dp[MAXA];
inline bool check(ll needCap) {
    ll sumYen=0;
    for(int i=1;i<=n;i++) {
        if(sumYen>x)
            return false;
        ll sumCap=0,capA=mach[i][1],pA=mach[i][2],capB=mach[i][3],pB=mach[i][4];
        while (true) {
            if(sumCap>=needCap)
                break;
            ll remainCap=needCap-sumCap;
            double effA=pA*1.0/min(remainCap,capA);   // 采用A机器的零件均摊价格(总消耗钱数/每台机器能做的有贡献零件数)
            double effB=pB*1.0/min(remainCap,capB);   // 采用B机器零件均摊价格
            if(effA<effB)
                sumCap+=capA,sumYen+=pA;
            else
                sumCap+=capB,sumYen+=pB;
        }
    }
    if(sumYen<=x)
        return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++) {
            // cap1      price1 per U
        cin>>mach[i][1]>>mach[i][2]>>mach[i][3]>>mach[i][4];
    }
    // for(int i=1;i<=n;i++) {
    //     if(mach[i][2]/1.0/mach[i][1]>mach[i][4]/1.0/mach[i][3]) {
    //         swap(mach[i][1],mach[i][3]);
    //         swap(mach[i][2],mach[i][4]);
    //     }
    // }
    ll l=0,r=MAXANS;
    while(l<r) {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}

将中间的判定改为了背包dp，果然这种通用做法就是应用性广泛且经过证明
// 就TLE了3个点 https://atcoder.jp/contests/abc374/submissions/58545771

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
// https://atcoder.jp/contests/abc374/tasks/abc374_e
#include <iostream>
#include <cmath>
typedef long long ll;
using namespace std;
const ll MAXN=105,MAXANS=static_cast<ll>(1e9)+7,MAXA=1e7+7;
int n,x,mach[MAXN][6];
int dp[MAXA];
inline bool check(ll needCap) {
    ll sumYen=0;
    for(int i=1;i<=n;i++) {
        dp[0]=0;
        int cap1=mach[i][1],p1=mach[i][2],cap2=mach[i][3],p2=mach[i][4];
        bool isBreak=false;
        if(sumYen>x)
            return false;
        for(int j=1;j<=x-sumYen;j++) {  // 背包容量为钱，背包价值为生产力
            dp[j]=0;
            int up1=j-p1,up2=j-p2;
            if(up1>=0)
                dp[j]=dp[up1]+cap1;
            if(up2>=0)
                dp[j]=max(dp[j],dp[up2]+cap2);
            if(dp[j]>=needCap) {
                sumYen+=j;isBreak=true;break;
            }
        }
        if(!isBreak)
            return false;
    }
    if(sumYen<=x)
        return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++) {
            // cap1      price1 per U
        cin>>mach[i][1]>>mach[i][2]>>mach[i][3]>>mach[i][4];
    }
    // for(int i=1;i<=n;i++) {
    //     if(mach[i][2]/1.0/mach[i][1]>mach[i][4]/1.0/mach[i][3]) {
    //         swap(mach[i][1],mach[i][3]);
    //         swap(mach[i][2],mach[i][4]);
    //     }
    // }
    ll l=0,r=MAXANS;
    while(l<r) {
        ll mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}
// AC 64 个点 https://atcoder.jp/contests/abc374/submissions/58537183 已经比较接近了
// 就TLE了3个点 https://atcoder.jp/contests/abc374/submissions/58545771