2018 Multi-University Training hdu Contest 8

Posted on | In , | Visitors:

嚯嚯嚯！补题！

hdu多校总链接

补题： 6题/12题

  • 计算几何
  • 构造
  • 线段树
  • 分类讨论
  • 逆元
  • 组合数学

A. Character Encoding

2018-hdu-8-A

组合计数的隔板法，是将n个木棒分成m组。这样就是在n-1个空隙中插入m-1个隔板，就是c(n-1, m-1)。现在这个k的组合如果没有上界就是一个隔板问题，是将k个木棒分成m份。由于分成的数可以为0，那么就要额外加入m条木棒，以便插板的时候能分出来0。处理完之后这样有k+m-1个空隙，插入m-1个隔板，就是c(k+m-1,m-1)

所以数学的题目，很多都是思路的问题，只要想清楚了，编码就很简单；

感谢WYM的讲解啦！

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int maxn = 2e5+10;
ll fac[maxn],ifac[maxn],inv[maxn];
ll G[maxn];
void init(){
    fac[0]=1;
    for(int i=1;i<=maxn-10;i++)
        fac[i]=fac[i-1]*i%mod;
    inv[1]=1;
    for(int i=2;i<=maxn-10;i++)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    
    ifac[0]=1;
    for(int i=1;i<=maxn-10;i++)
        ifac[i]=ifac[i-1]*inv[i]%mod;
}
ll C(ll m,ll n){ //C nm
    return fac[m]*ifac[n]%mod*ifac[m-n]%mod;
}
ll solve(ll n,ll m){
    if(m<0) return 0;
    return C(m+n-1,n-1);
}
int main(){
    init();
    int T;scanf("%d",&T);
    ll n,m,k;
    while(T--){
        scanf("%lld%lld%lld",&n,&m,&k);
        for(int p=0;p<=m;p++){
            G[p]=C(m, p)*solve(m, k-p*n)%mod;
        }
        for(int i=m-1;i>=0;i--)
            G[i]=(G[i]+mod-G[i+1])%mod;
        printf("%lld\n",G[0]);
    }
    return 0;
}

B. Pizza Hub

画了一下图，分类的情况很多，每种情况需要我分别判断，同时计算这个高度的方法也是不同的

2018-hdu-8-B

不过看标程，貌似也没有那么多种分类的问题，可是代码看不懂！

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
const double EPS = 1e-9;
const double PI = acos(-1.0);
struct Point {
    double x, y;
    void in() {
        scanf("%lf%lf", &x, &y);
    }
};
double dis(Point a, Point b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
int cmp(double a, double b) {
    if (abs(a - b) <= EPS)  return 0;
    if (a - b <= EPS)   return -1;
    return 1;
}
double ans;
void deal(Point a, Point b, Point c, double w) {//处理以ab为底边的情况
    double ba = dis(b, a), bc = dis(b, c), ac = dis(a, c);
    //如果边大于限制不可以
    if(ba>w) return ;
    //如果小于限制之后，判断两个角是否没有钝角
    double anglea=acos((ba*ba+ac*ac-bc*bc)/(2*ba*ac));
    double angleb=acos((ba*ba+bc*bc-ac*ac)/(2*ba*bc));
    //如果都是不是钝角的时候，就可以放入
    double x=cos(anglea),y=cos(angleb);
    if(x>=0&&y>=0){
        ans=min(ans,ac*sin(anglea));
        return ;
    }
    //如果存在钝角的时候，计算是否可以放入
    if(x<0){
        if(cmp(ba-ac*x, w)<=0){
            ans=min(ans, ac*sin(anglea));
        }
    }else{
        if(cmp(ba-bc*y, w)<=0){
            ans=min(ans, bc*sin(angleb));
        }
    }
}
void deal2(Point a, Point b, Point c, double w) {//处理ab为斜边的情况
    double ba = dis(b, a), bc = dis(b, c), ac = dis(a, c);
    //如果ab小于限制就不用计算了
    if(ba<=w) return ;
    //判断两个角是否都在新角的范围内
    double anglea=acos((ba*ba+ac*ac-bc*bc)/(2*ba*ac));
    double angleb=acos((ba*ba+bc*bc-ac*ac)/(2*ba*bc));
    
    double newx=acos(w/ba);
    double newy=asin(w/ba);
    if((cmp(anglea, newx)<=0&&cmp(angleb, newy)<=0)||(cmp(angleb, newx)<=0&&cmp(anglea, newy)<=0)){
        ans=min(ans, ba*sin(newx));
        return ;
    }
    //否则，需要翻转，计算角+新角的值小于等于直角，另一个角+新角的值小于等于180的话，则可以放入
    //放入的时候又有两种情况
    double anglex=anglea+newx;
    int flagx=cmp(anglex, PI/2);
    double angley=angleb+newy;
    int flagy=cmp(angley, PI/2);
    double anglexx=angleb+newx;
    int flagxx=cmp(anglexx, PI/2);
    double angleyy=anglea+newy;
    int flagyy=cmp(angleyy, PI/2);
    
    if(!((flagx<=0&&cmp(angley, PI)<=0)||(flagxx<=0&&cmp(angleyy, PI)<=0))) return ;
    
    //存在一个角等于90
    if(flagx==0) ans=min(ans, max(ac,ba*sin(newx)));
    if(flagxx==0) ans=min(ans,max(bc,ba*sin(newx)));
    if(flagx<0&&flagy==0) ans=min(ans,ba*sin(newx));
    if(flagxx<0&&flagyy==0) ans=min(ans,ba*sin(newx));
    
    //存在一个角等于180
    if(cmp(angley, PI)==0){
        ans=min(ans, ac*sin(anglex));
    }
    
    if(cmp(angleyy, PI)==0){
        ans=min(ans,bc*sin(anglexx));
    }
    
    //两个角都小于90
    if(flagx<0&&flagy<0){
        ans=min(ans,ba*sin(newx));
    }
    if(flagxx<0&&flagyy<0){
        ans=min(ans,ba*sin(newx));
    }
    
    //一个角大于90
    if(flagx<0&&flagy>0){
        ans=min(ans,ac*sin(anglex));
    }
    if(flagxx<0&&flagyy>0){
        ans=min(ans,bc*sin(anglexx));
    }
}
int main() {
    int T;
    scanf("%d", &T);
    Point a, b, c;
    double w;
    while (T--) {
        a.in(); b.in(); c.in(); scanf("%lf", &w);
        ans = 1<<30;
  
        deal(a, b, c, w);
        deal(a, c, b, w);
        deal(b, c, a, w);
        deal2(a, b, c, w);
        deal2(a, c, b, w);
        deal2(b, c, a, w);
        if (cmp(ans, 1<<30) == 0)   printf("impossible\n");
        else    printf("%.7lf\n", ans);
    }
}

D. Parentheses Matrix

首先，第一行、最后一列中最多只有一个能够匹配，第一列、最后一行也只有一个能够匹配（考虑右上角和左下角的括号选取方法），故答案不会超过 w+h−2。

当 h = 2 时，每一列可以构造一对匹配，这样答案已经到达上界。

当 h = 4 时：

1
2
3
4
((((((((
))))((((
(((())))
))))))))

这样答案是 w+h−3。

当 h ≥ 6 时，可以如下构造：

1
2
3
4
5
6
((((((((
()()()()
(()()())
()()()()
(()()()) 
))))))))

答案是 w+h−4。

面向数据编程的代码：

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
char ans[222][222];
int main() {
    // freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--) {
        int row, col;
        scanf("%d%d", &row, &col);
        if (row&1 && col&1) {
            for (int i = 1; i <= row; ++i) {
                for (int j = 1; j <= col; ++j) {
                    printf("(");
                }
                printf("\n");
            }
        } else if (row&1) {
            int cnt = col / 2;
            for (int i = 1; i <= row; ++i) {
                for (int k = 1; k <= cnt; ++k) printf("()");
                printf("\n");
            }
        } else if (col&1) {
            int cnt = row/2;
            for (int i = 1; i <= cnt; ++i) {
                for (int j = 1; j <= col; ++j)  printf("(");
                printf("\n");
            }
            for (int i = cnt + 1; i <= row; ++i) {
                for (int j = 1; j <= col; ++j)  printf(")");
                printf("\n");
            }
        }else if(col==2){
            for(int i=1;i<=row;i++){
                printf("()\n");
            }
        }
        else if(row==2){
            for(int j=1;j<=col;j++){
                printf("(");
            }
            printf("\n");
            for(int j=1;j<=col;j++){
                printf(")");
            }
            printf("\n");
        }
        else if(col==4){
            for(int i=1;i<=row/2;i++){
                printf("()()\n");
            }
            for(int i=1;i<=row/2;i++){
                printf("(())\n");
            }
        }
        else if(row==4){
            for(int j=1;j<=col;j++){
                printf("(");
            }
            printf("\n");
            for(int j=1;j<=col/2;j++){
                printf(")");
            }
            for(int j=1;j<=col/2;j++){
                printf("(");
            }
            printf("\n");
            for(int j=1;j<=col/2;j++){
                printf("(");
            }
            for(int j=1;j<=col/2;j++){
                printf(")");
            }
            printf("\n");
            for(int j=1;j<=col;j++){
                printf(")");
            }
            printf("\n");
        }
        else if (col <= row) {
            for(int i=1;i<=row;i++){
                ans[i][1]='(';
            }
            int nowcol=2;
            while(nowcol<col){
                for(int i=1;i<=row/2;i++){
                    ans[i*2-1][nowcol]='(';
                    ans[i*2][nowcol]=')';
                }
                nowcol++;
                ans[1][nowcol]='(';
                for(int i=1;i<=row/2-1;i++){
                    ans[i*2][nowcol]='(';
                    ans[i*2+1][nowcol]=')';
                }
                ans[row][nowcol]=')';
                nowcol++;
            }
            for(int i=1;i<=row;i++){
                ans[i][col]=')';
            }
            for (int i = 1; i <= row; ++i) {
                for (int j = 1; j <= col; ++j) printf("%c", ans[i][j]);
                printf("\n");
            }
        } else {
            for(int j=1;j<=col;j++){
                printf("(");
            }
            printf("\n");
            int nowrow=2;
            while(nowrow<row){
                for(int j=1;j<=col/2;j++){
                    printf("()");
                }
                printf("\n");
                
                printf("(");
                for(int j=1;j<=col/2-1;j++)
                    printf("()");
                printf(")\n");
                nowrow+=2;
            }
            for(int j=1;j<=col;j++){
                printf(")");
            }
            printf("\n");
        }
    }
}

E. Magic Square

模拟题，C语言题;

让我都不敢写了

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
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
string mmap[3];
string cmd;
void input(){
    for(int i=0;i<3;i++){
        cin>>mmap[i];
    }
}
void clock(int x){
    int i,j;
    if(x==1){
        i=0;j=0;
    }else if(x==2){
        i=0;j=1;
    }else if(x==3){
        i=1;j=0;
    }else{
        i=1;j=1;
    }
    int nexi,nexj;
    nexi=i;nexj=j+1;
    char tmp=mmap[nexi][nexj];
    mmap[nexi][nexj]=mmap[i][j];
    nexi=nexi+1;
    swap(tmp,mmap[nexi][nexj]);
    nexj--;
    swap(tmp,mmap[nexi][nexj]);
    mmap[i][j]=tmp;
}
void notclock(int x){
    int i,j;
    if(x==1){
        i=0;j=0;
    }else if(x==2){
        i=0;j=1;
    }else if(x==3){
        i=1;j=0;
    }else{
        i=1;j=1;
    }
    int nexi,nexj;
    nexi=i+1;nexj=j;
    char tmp=mmap[nexi][nexj];
    mmap[nexi][nexj]=mmap[i][j];
    nexj=nexj+1;
    swap(tmp,mmap[nexi][nexj]);
    nexi--;
    swap(tmp,mmap[nexi][nexj]);
    mmap[i][j]=tmp;
}
int main() {
    int T;cin>>T;
    int n;
    while(T--){
        cin>>n;
        input();
        while(n--){
            cin>>cmd;
            int idx=cmd[0]-'0';
            char c=cmd[1];
            if(c=='C'){
                clock(idx);
            }else{
                notclock(idx);
            }
        }
        for(int i=0;i<3;i++)
            cout<<mmap[i]<<endl;
    }
    return 0;
}

J. Taotao Picks Apples

为博博的线段树鼓掌！

比赛中的思路：

首先，如果这个点在原串中，就是会被吃的，我们称作为关键点；

预处理，dp数组表示包含这点且从这点开始到尾部的严格上升序列的长度

  • 修改第一个点
    • 寻找之后大于它的第一个点pos，1+dp[pos]
  • 是关键点
    • 如果这个数比此点的之前的最大值【这个最大值的位置为pos】还要大的时候，说明，此点不会被取；则dp[1]-dp[pos]+1就是此点的值；然后我们寻找在此点之后，第一个大于前面找到的最大值的位置【pos2】，则后面的长度就是dp[pos2]；两者相加就是结果！
    • 如果这个点【idx】的值比之前序列的最大值还要大的时候，此点必取；找到之后比此值还要大的位置【pos】，则长度为dp[1]-dp[idx]+1+dp[pos]
  • 不是关键点
    • 如果比之前的最大值要小，说明对原序列没有影响
    • 否则的话，寻找在此之前比这点小的最大值（若均相同的时候，取下标小的）【pos】，寻找这点之后比这点大的第一个点【pos2】，则长度为dp[1]-dp[pos]+1+dp[pos2]

看了题解后的思路：

不过不明白：

“到达最大值需要几步”

以及不会做：

使用 ST 维护信息

等我上一场的ST学完后，再来看；

思路是这样的：

先处理从后向前的dp，找到在此右边第一个比他大的数的位置【pos】；若找不到，则dp[i]=1；否则的话，dp[i]=dp[pos]+1

然后对于每一次查询，寻找[1 , idx-1]的最大值的位置【pos】，比较这个值和新修改的值

  • 如果新修改的值小于等于a[pos]的话，则找到在此右边第一个比a[pos]大的数的位置【pos2】,ans=dp[1]-dp[pos]+1+dp[pos2]
  • 否则的话，则找到在此右边第一个比新加的数大的数的位置【pos】，ans=dp[1]-dp[pos]+1+1+dp[pos2]

所以我们需要一个寻找[l,r]区间的第一个大于val的值的位置的函数

这个可以用线段树维护

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
113
114
115
116
117
118
119
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAX = 1e5 + 5;
struct Node1 {
    int l, r, max_;
}t[MAX<<2];
int a[MAX];
void build(int i, int l, int r) {
    t[i].l = l; t[i].r = r;
    if (l == r) {
        t[i].max_ = a[l];
        return ;
    }
    
    int mid = l + r >> 1;
    build(i<<1, l, mid);
    build(i<<1|1, mid + 1, r);
    t[i].max_ = max(t[i<<1].max_, t[i<<1|1].max_);
}
int query1(int i, int l, int r, int val) {//find the first value that is bigger than val
    if (l > r)  return 0;
    if (t[i].max_ <= val)   return 0;
    int mid = t[i].l + t[i].r >> 1;
    if (t[i].l == l && t[i].r == r) {
        if (l == r) return l;
        if (t[i<<1].max_ > val) return query1(i<<1, l, mid, val);
        else if (t[i<<1|1].max_ > val)  return query1(i<<1|1, mid + 1, r, val);
        else    return 0;
    }
    
    if (r <= mid)   return query1(i<<1, l, r, val);
    else if (l > mid)   return query1(i<<1|1, l, r, val);
    else {
        int t = query1(i<<1, l, mid, val);
        if (t != 0) return t;
        return query1(i<<1|1, mid + 1, r, val);
    }
}
int query2(int i, int l, int r) {//find the maximum value in range [l, r]
    if (l > r)  return 0;
    if (t[i].l == l && t[i].r == r)     return t[i].max_;
    
    int mid = t[i].l + t[i].r >> 1;
    if (r <= mid)   return query2(i<<1, l, r);
    else if (l > mid)   return query2(i<<1|1, l, r);
    else    return max(query2(i<<1, l, mid), query2(i<<1|1, mid + 1, r));
}
int dp[MAX], n, q, idx, val, nex[MAX], lst;
bool isCritical[MAX];
void deal() {
    build(1, 1, n);
    dp[n] = 1;
    memset(isCritical, 0, sizeof(isCritical));
    nex[n] = 0;
    for (int i = n - 1; i >= 1; --i) {
        idx = query1(1, i + 1, n, a[i]);
        dp[i] = dp[idx] + 1;
        nex[i] = idx;
    }
    idx = 1;
    while (idx) {
        isCritical[idx] = 1;
        idx = nex[idx];
    }
    isCritical[idx] = 1;
    lst = idx;
}
int query3(int i, int l, int r, int val) {//find the first value that is equal to val
    if (t[i].l == t[i].r)   return l;
    
    int mid = t[i].l + t[i].r >> 1, tt;
    if (t[i].l == l && t[i].r == r) {
        if (t[i<<1].max_ == val)    return query3(i<<1, l, mid, val);
        else if (t[i<<1|1].max_ == val) return query3(i<<1|1, mid + 1, r, val);
        else    return 0;
    }
    
    if (r <= mid)   return query3(i<<1, l, r, val);
    else if (l > mid)   return query3(i<<1|1, l, r, val);
    else {
        tt = query3(i<<1, l, mid, val);
        if (tt != 0) return tt;
        return query3(i<<1|1, mid + 1, r, val);
    }
    
}
int main() {
//    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &q);
        for (int i = 1; i <= n; ++i)    scanf("%d", &a[i]);
        deal();
        
        while (q--) {
            scanf("%d%d", &idx, &val);
            if (n == 1) {
                printf("1\n");
                continue;
            }
            
            if (idx == 1) {
//                cout << query1(1, 2, n, val) << endl;
                printf("%d\n", dp[query1(1, 2, n, val)] + 1);
            } else {
                if (isCritical[idx]) {
                    if (val <= query2(1, 1, idx - 1))   printf("%d\n", dp[query1(1, idx + 1, n, query2(1, 1, idx - 1))] + dp[1] - dp[query3(1, 1, idx - 1, query2(1, 1, idx - 1))] + 1);
                    else    printf("%d\n", dp[1] - dp[idx] + 1 + dp[query1(1, idx + 1, n, val)]);
                } else {
                    if (val <= query2(1, 1, idx - 1))   printf("%d\n", dp[1]);
                    else    printf("%d\n", dp[query1(1, idx + 1, n, val)] + dp[1] - dp[query3(1, 1, idx - 1, query2(1, 1, idx - 1))] + 2);
                }
            }
        }
    }
}

L. From ICPC to ACM

主要是题目的变量太多了，晕乎乎的

模拟题

  • ci 做一台电脑（即一单元）的材料费
  • di 当月需要的电脑台数
  • mi 组装一台电脑的钱
  • pi 当月最多可以组装成的电脑数
  • ei 当月最多可以储存的电脑数
  • Ri 当月存储一单元材料的钱
  • Ei 当月存储一电脑的钱

但是实际上，对于材料我们可以在其$\displaystyle c[i]+\sum^{i-1}_{k=j}R[k]$ j表示购买的日期，如果我用前缀和RR[i]处理过数组以后，算式就变成$\displaystyle c[i]+RR[useday]-RR[i-1]$

所以我用了一个变量存储$c[i]-RR[i-1]$，这样在使用的时候，只要加上$RR[useday]$即可！

然后，对于这个月我最多可以做p[i]台，然后和仓库里的排序，看钱谁最少。这里用了优先队列。

判断队列的个数是否达到此月标准，若不可以，则直接返回-1；

否则，需要更新ans值；

同时更新队列：我们需要将队列中的所有的电脑数的和控制在当月仓库允许的范围内；同时将cost值增加放置一台电脑所需要的价钱。

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
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=5e4+5;
int tot_sum;//剩余可以存储的最多的电脑台数
ll RR[maxn];//材料存储的后缀数组
ll store_material;//存储材料mi+RRi的最小值；计算的时候的花费就是mi-(RRnow-RRi);
int k,c[maxn],d[maxn],m[maxn],p[maxn],e[maxn],R[maxn],E[maxn];
ll ans;
struct PC{
    int cost;//mi+ci-Ei;
    int num;//min(ei,pi-di);
    bool operator<(const PC& o)const{
        return cost>o.cost;
    }
}store,now;
priority_queue<PC>q[2];
int flag;
void input(){
    scanf("%d",&k);
    for(int i=1;i<=k;i++){
        scanf("%d%d%d%d",&c[i],&d[i],&m[i],&p[i]);
    }
    for(int i=1;i<k;i++){
        scanf("%d%d%d",&e[i],&R[i],&E[i]);
    }
}
void init(){//初始化ans，预处理RR数组
    flag=0;
    ans=0;store_material=0x3f3f3f3f;
    while(!q[0].empty()) q[0].pop();
    while(!q[1].empty()) q[1].pop();
    for(int i=1;i<=k;i++){
        RR[i]=RR[i-1]+R[i];
    }
}
void work(int nowday){//处理今天库房里最多只可以有e[nowday]台
    int tmp=0;
    while(!q[flag].empty()){
        now=q[flag].top();q[flag].pop();
        now.cost+=E[nowday];
        
        if(tmp+now.num<=e[nowday]){
            q[flag^1].push(now);
            tmp+=now.num;
        }else{
            now.num=e[nowday]-tmp;
            q[flag^1].push(now);
            break;
        }
    }
    while(!q[flag].empty()) q[flag].pop();
    flag=flag^1;
}
bool add_PC(int need){//增加电脑台数
    while(!q[flag].empty()){
        now=q[flag].top();q[flag].pop();
        if(need<now.num){
            now.num-=need;
            ans+=1LL*now.cost*need;
            need=0;
            q[flag].push(now);
            break;
        }else{
            need-=now.num;
            ans+=1LL*now.cost*now.num;
        }
    }
    
    if(need)
        return false;
    return true;
}
void solve(){
    for(int i=1;i<=k;i++){
        store_material=min((ll)store_material,c[i]-RR[i-1]);
        store.cost=m[i]+store_material+RR[i-1];
        store.num=p[i];
        q[flag].push(store);
        
        if(!add_PC(d[i])){
            ans=-1;
            return ;
        }
        if(i!=k) work(i);
    }
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        input();
        init();
        solve();
        printf("%lld\n",ans);
    }
    return 0;
}

碎碎念

2018.08.16 下午

空调房冻死！

银行卡顺利被我冻结了！

嚯嚯嚯！找时间出门啦！

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽