ToRapture's Blog

A Programmer

0%

Posted on Edited on Disqus: 
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
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

typedef long long LL;
using namespace std;

const int N = 512;
LL ans[N][128], tmp[N][128];
int main(int argc, char **argv) {
    int n; while(~scanf("%d", &n)) {
        int v[] = {0, 1, 5, 10, 25, 50};
        memset(ans, 0, sizeof(ans));
        for(int i = 0; i <= 100; ++i) ans[i][i] = 1;
        memset(tmp, 0, sizeof(tmp));
        for(int i = 2; i <= 5; ++i) {
          for(int e = 0; e <= n; ++e)
            for(int take = 0; take <= 100 && e + take * v[i] <= n; ++take)
                for(int p_take = 0; take + p_take <= 100; ++p_take) {
                tmp[e + take * v[i]][take + p_take] += ans[e][p_take];
            }
            memcpy(ans, tmp, sizeof(tmp));
            memset(tmp, 0, sizeof(tmp));
        }
        LL res = 0;
        for(int i = 0; i <= 100; ++i) res += ans[n][i];
        printf("%lld\n", res);
    }
    return 0;
}

Posted on Edited on Disqus: 
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
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

typedef long long LL;
using namespace std;
const int MAX_SUM = 250000 + 16;
const int N = 128;
LL ans[MAX_SUM], tmp[MAX_SUM];
int num[N], v[N];
int main(int argc, char **argv) {
    int n;
    while(~scanf("%d", &n) && n >= 0) {
        int tot = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%d%d", &v[i], &num[i]);
            tot += v[i] * num[i];
        }
        memset(ans, 0, sizeof(ans));
        memset(tmp, 0, sizeof(tmp));
        for(int i = 0; i <= num[1]; ++i) ans[i * v[1]] = 1;
        for(int i = 2; i <= n; ++i) {
          for(int e = 0; e <= tot; ++e) 
              for(int take = 0; take <= num[i] && e + take * v[i] <= tot; ++take)
                tmp[e + take * v[i]] += ans[e];
            memcpy(ans, tmp, sizeof(tmp));
            memset(tmp, 0, sizeof(tmp));
        }
        int l = tot, r = 0, diff = tot;
        for(int i = 0; i <= tot; ++i) if(ans[i]) {
            int ll = i, rr = tot - i;
            int df = abs(rr - ll);
            if(ll >= rr && df < diff) {
                l = ll;
                r = rr;
                diff = df;
            }
        }
        printf("%d %d\n", l, r);
    }
    return 0;
}

Posted on Edited on Disqus:

令\(sum(l, r) = \sum\limits_{i \in [l, r]} a_i\)，求\(\max\{\min_{i=l}^ra_i \times sum(l, r) \ |\ 1 \le l \le r \le n \}\)。 对于每一个\(a_i\)，用单调栈维护出一个长度最大的区间\([L_i, R_i]\)，使得\(\min_{j=L_i}^{R_i} a_j = a_i\)，答案转换为\(\max\{sum(L_i, R_i) \times a_i \ | \ i \in [1, n]\}\)。

证明

问题等价

\(ans(l, r) = \min_{i=l}^r \times sum(l,r)\) 对于每一个\([l, r]\)，有唯一二元组\((i, a_i)\)满足\(a_i=\min_{j=l}^r\)且下标\(i\)最小。 令\([L,R]\)为包含这个二元组的长度最大的区间，则有\(a_i=\min_{j=L}^{R}\)。 所以\(ans(L,R)=\min_{i=L}^{R}a_i \times sum(L,R)\)，又因\(sum(l,r) \le sum(L,R)\)，则有\(ans(l,r) \le ans(L,R)\)。 而一个这样的\([L,R]\)对应多个\([l,r]\)，每一个\([L_i,R_i]\)又与\((i, a_i)\)一一对应，答案即为\(\max\{sum(L_i, R_i) \times a_i \ | \ i \in [1, n]\}\)。

单调栈维护

对于每一个\(a_i\)，使用递增单调栈\(STK\)处理出\([L_i,R_i]\)。 每考虑到一个元素\(a_i\)时，\(L_i\)在\(a_i\)入栈时被处理好，\(R_i\)在\(a_i\)出栈时处理。 若\(a_i > a_j, i < j\)，根据\(L\)的定义，有\(L_j \le L_i\)。 

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int N = 100000 + 16;

LL a[N], sum[N];
int STK[N], top;
int L[N];
int main(int argc, char **argv) {
    int n;
    while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]); a[++n] = -1;
        for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];

        pair<LL, pair<int, int>> ans = make_pair(-1, make_pair(-1, -1));
        top = 0;
        for(int i = 1; i <= n; ++i) {
            if(top == 0 || a[i] >= a[STK[top]]) {
                L[i] = i;
                STK[++top] = i;
            } else {
                while(top && a[i] < a[STK[top]]) {
                    int x = STK[top--];
                    int l = L[x], r = i - 1;
                    LL res = (sum[r] - sum[l - 1]) * a[x];
                    ans = max(ans, make_pair(res, make_pair(l, r)));
                    L[i] = L[x];
                }
                STK[++top] = i;
            }
        }
        printf("%lld\n", ans.first);
        printf("%d %d\n", ans.second.first, ans.second.second);
    }
    return 0;
}

Posted on Edited on Disqus: 
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
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

typedef long long LL;
using namespace std;

int main(int argc, char **argv) {
    string str;
    while(cin >> str) {
        unordered_map<char, int> vis;
        int ans = INT_MAX;
        int l = 0, r = 0;
        ++vis[str[r]];
        int num = 1;
        while(l <= r && r < str.size()) {
            if(num == 26) {
                ans = min(ans, r - l + 1);
                if(--vis[str[l++]] == 0) --num;
            } else {
                if(vis[str[++r]]++ == 0) ++num;
            }
        }
        if(ans == INT_MAX) cout << "No Solution" << endl;
        else cout << ans << endl;
    }
    return 0;
}

/**
BVCABCDEFFGHIJKLMMNOPQRSTUVWXZYZZ

28
*/

Posted on Edited on Disqus:

远程连接Mysql时发生错误，提示为ERROR 1030 (HY000): Got error 28 from storage engine.

Google这个错误说是由于硬盘满了，连接到服务器上查了一下发现果然是这样。

 

然后开始猜测发生的原因。

之前的几个月服务器上只运行着Web应用，而且很稳定，近期的变动只有新安装了polipo，怎么配置的忘了。

首先猜到的是Mysql相关的文件和其他应用的日志文件。

在根目录下执行sudo du -s -h ./*，发现/var占用空间很多，

再进入/var/中定位，发现/var/cache/占用空间很多，

sudo apt-get remove --purge polipo卸载polipo之后磁盘空间恢复，具体为什么polipo占了这么多空间我也不知道，可能是因为使用的姿势有问题？