月度归档：2018年08月

洛谷 P1541 乌龟棋

发表评论
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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<cstring>
using namespace std;
int n,m;
int a[355],b[6];
int f[45][45][45][45];
int safeF(int i,int j,int k,int l){
    if(i<0||j<0|k<0||l<0)return 0;
    else return f[i][j][k][l];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
        int t;
        cin>>t;
        b[t]++;
    }
    for(int i=0;i<=b[1];i++)for(int j=0;j<=b[2];j++)for(int k=0;k<=b[3];k++)for(int l=0;l<=b[4];l++){
        f[i][j][k][l]=max(max(safeF(i-1,j,k,l),safeF(i,j-1,k,l)),max(safeF(i,j,k-1,l),safeF(i,j,k,l-1)))+a[i+2*j+3*k+4*l+1];
    }
    cout<<f[b[1]][b[2]][b[3]][b[4]];
}

洛谷 P1880 [NOI1995]石子合并

发表评论

转移方程是看别人的……
参考：易懂https://www.luogu.org/blog/user45556/solution-p1880
区间动规经典题目？

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<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int arr[205];
int presum[205];
int fMax[205][205], fMin[205][205];
int dfsMax(int l, int r) {
    if (l == r)return 0;
    if (fMax[l][r] != 0)return fMax[l][r];
    int dIJ = presum[r] - presum[l - 1];
    int mmax = 0;
    for (int k = l; k < r; k++) mmax = max(mmax, dfsMax(l, k) + dfsMax(k + 1, r) + dIJ);
    return fMax[l][r] = mmax;
}
int dfsMin(int l, int r) {
    if (l == r)return 0;
    if (fMin[l][r] != 0)return fMin[l][r];
    int dIJ = presum[r] - presum[l - 1];
    int mmin = 0x7fffffff;
    for (int k = l; k < r; k++)mmin = min(mmin, dfsMin(l, k) + dfsMin(k + 1, r) + dIJ);
    return fMin[l][r] = mmin;
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> arr[i];
    for (int i = n + 1; i <= 2*n; i++)arr[i] = arr[i - n];
    for (int i = 1; i <= 2 * n; i++)presum[i] = presum[i - 1] + arr[i];
    int mmin = 0x7fffffff;
    for (int i = 1; i <= n; i++) {
        mmin = min(mmin, dfsMin(i, i + n - 1));
    }
    cout << mmin << endl;
    int mmax = 0;
    for (int i = 1; i <= n; i++) {
        mmax = max(mmax, dfsMax(i, i + n - 1));
    }
    cout << mmax << endl;

}

洛谷 P3383 【模板】线性筛素数

发表评论
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
bool prime[10000005];

int main(){
    memset(prime, true, sizeof(prime));
    cin >> n >> m;
    prime[0] = prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (!prime[i])continue;
        for (int j = 2 * i; j <= n; j += i) {
            prime[j] = false;
        }
    }
    for (int i = 1; i <= m; i++) {
        int tmp;
        cin >> tmp;
        cout << (prime[tmp]?"Yes":"No") << endl;
    }
}

洛谷 P3367 【模板】并查集

发表评论

明明记得之前应该有并查集的板子在博客里？怎么找不到了？？

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int father[10005];
int _find(int num) {
    if (father[num] == -1)return num;
    else return father[num] = _find(father[num]);
}
void _union(int v1, int v2) {
    if (_find(v1) == _find(v2))return;
    father[_find(v2)] = v1;
}
int n, m;
int main(){
    memset(father, -1, sizeof(father));
    cin >> n >> m;
    while (m--) {
        int z, x, y;
        cin >> z >> x >> y;
        if (z == 1)_union(x, y);
        else cout << (_find(x) == _find(y) ? 'Y' : 'N') << endl;
    }
}

洛谷 P1020 导弹拦截

发表评论

又是自己改了半天的一道题，忘了……

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
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n=1;
int arr[100005];
int f[100005];
int f2[100005];
int main() {
    while (cin >> arr[n])n++;
    n--;
    arr[0] = 50001;
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        int m = f[0];
        for (int j = 1; j < i; j++) {
            if (f[j]>m&&arr[j]>=arr[i]) {
                m = f[j];
            }
        }
        f[i] = m + 1;
    }
    cout << *max_element(f+1,f+n+1) << endl;
    arr[0] = 0;
    f2[0] = 0;
    for (int i = 1; i <= n; i++) {
        int m = f2[0];
        for (int j = 1; j < i; j++) {
            if (f2[j]>m&&arr[j]<arr[i]) {
                m = f2[j];
            }
        }
        f2[i] = m + 1;
    }
    cout << *max_element(f2+1,f2+n+1) << endl;
}

洛谷 P1233 木棍加工

发表评论

不好做啊……想不出来……看题解……

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<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n;
struct node {
    int l, w;
    bool operator < (const node& n2) const {
        if (l != n2.l)return l > n2.l;
        if (w != n2.w)return w > n2.w;
        return false;
    }
}arr[5005];
bool visited[5005];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].l >> arr[i].w;
    }
    sort(arr + 1, arr + n + 1);
    bool flag = false;
    int cnter = 0, ptr = 0;
    do {
        flag = false;
        for (ptr=1;ptr <= n; ptr++) {
            if (!visited[ptr]) {
                flag = true;
                visited[ptr] = true;
                break;
            }
        }
        if (!flag)break;
        cnter++;
        for (int i = ptr+1; i <= n; i++) {
            if (visited[i] || arr[i].l > arr[ptr].l || arr[i].w > arr[ptr].w) continue;
            visited[i] = true;
            ptr = i;
        }
    } while (flag);
    cout << cnter;
}

洛谷 P1080 国王游戏

发表评论

这题不好写，一个问题在贪心怎么排序，再有的难点就是高精乘/除，都不好写。。
这次正经的写了个高精度乘/除。。留下来备用。

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
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n;
struct bigInt { //For Non-negative Numbers
private:
    string v;
    static string & bIsort(string & v) { //each char has reduced '0'
        for (int i = 0; i < v.length(); i++) {
            if (v[i] > 9) {
                if (i == v.length() - 1)v.append(1, v[i] / 10);
                else v[i + 1] += v[i] / 10;
                v[i] %= 10;
            }
        }
        return v;
    }
    static string lng2str(long long v) {
        string s = "";
        while (v) {
            s.append(1, v % 10 + '0');
            v /= 10;
        }
        reverse(s.begin(), s.end());
        return s;
    }
    static string& trimPre0(string& v3) {
        while (v3.length() != 0 && (*v3.begin()) == '0')v3.erase(v3.begin());
        if (v3.length() == 0)v3 = "0";
        return v3;
    }
public:
    bigInt() {
        v = "0";
    }
    bigInt(long long n) {
        v = lng2str(n);
    }
    bigInt(string s) {
        v = s;
    }
    bigInt& operator = (const bigInt & bI) {
        this->v = bI.v;
        return *this;
    }
    bigInt operator * (bigInt bI2) const {
        string v1 = v, v2 = bI2.v;
        if (v2.length() > v1.length())swap(v1, v2);
        reverse(v1.begin(), v1.end());
        reverse(v2.begin(), v2.end());
        string v3 = "";
        for (int i = 0; i < v1.length(); i++)v1[i] -= '0';
        for (int i = 0; i < v2.length(); i++)v2[i] -= '0';
        v3.resize(v1.length() + v2.length(), 0);
        for (int i = 0; i < v2.length(); i++) {
            for (int j = 0; j < v1.length(); j++) {
                v3[i + j] += v2[i] * v1[j];
            }
            bIsort(v3);
        }
        for (int i = 0; i < v3.length(); i++)v3[i] += '0';
        reverse(v3.begin(), v3.end());
        trimPre0(v3);
        return bigInt(v3);
    }
    bigInt operator / (long long bI2) const {
        string v1 = v;
        for (int i = 0; i < v1.length(); i++)v1[i] -= '0';
        long long v2 = bI2;
        string v3 = "";
        long long div = 0;
        for (int i = 0; i < v1.length(); i++) {
            div *= 10;
            div += v1[i];
            if (div < v2) {
                v3.append(1, '0');
                continue;
            }
            v3.append(lng2str(div / v2));
            div %= v2;
        }
        return bigInt(trimPre0(v3));
    }
    bool operator < (bigInt bI2) const {
        if (v.length() != bI2.v.length())return v.length() < bI2.v.length();
        for (int i = 0; i < v.length(); i++) {
            if (v[i] != bI2.v[i])return v[i] < bI2.v[i];
        }
        return false;
    }
    friend istream& operator >> (istream& in, bigInt& bI) {
        in >> bI.v;
        return in;
    }
    friend ostream& operator << (ostream& out, bigInt& bI) {
        out << bI.v;
        return out;
    }
};
struct p {
    bigInt a;
    int b;
    bool operator < (const p& p2) {
        return a * b < p2.a*p2.b;
    }
}ps[1005];

int main() {
    cin >> n;
    for (int i = 1; i <= n + 1; i++) {
        cin >> ps[i].a >> ps[i].b;
    }
    sort(ps + 2, ps + n + 2);
    bigInt multiply = ps[1].a;
    bigInt mmax("0");
    for (int i = 2; i <= n + 1; i++) {
        mmax = max(mmax, multiply / ps[i].b);
        multiply =multiply* ps[i].a;
    }
    cout << mmax;
}