月度归档：2017年08月

洛谷 [USACO1.1]坏掉的项链Broken Necklace

发表评论

题号：1203
并不知道为什么AC，本来45分瞎改了改AC的。。。这破题也是神烦……

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
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int n;
string s;
char search(int start, int ptr){
    for (int i = ptr; i - start +1 <= n; i++){
        if (s[i] != 'w')return s[i];
    }
    return 'w';
}
int run(int start,char c, char a){
    int tmax = 0;
    bool flag = false;
    int ptr = start;
    char cur;
    if (s[start] == a)return 0;
    while (1){
        if (!flag){
            if (s[ptr] == c || s[ptr] == 'w')tmax++;
            else {
                flag = true;
                tmax++;
                cur = search(start, ptr); //就这里，我觉得reference 2应该是ptr+1才对。。
            }
        }
        else{
            if (s[ptr] == cur || s[ptr] == 'w')tmax++;
            else break;
        }
        ptr++;
        if (ptr - start >= n){
           
            break;
        }
    }
    return tmax;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> s;
    s.append(s);
    int m = 0;
    for (int i = 0; i <= n; i++){
        int t = run(i, 'b', 'r');
        if (t>m)m = t;
        t = run(i, 'r', 'b');
        if (t > m)m = t;
    }
    cout << m;
}

洛谷 过河

发表评论

题号：1052
参考题解：
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1052
作者: CoolTeam 更新时间: 2015-08-11 18:26
作者: shutdown 更新时间: 2013-07-30 20:20
作者: VengefulSpirit 更新时间: 2013-06-25 11:17
作者: sb123 更新时间: 2017-08-07 17:58

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
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int f[20005];
int Mk[105],M[105];
//ifstream cin("in.txt");
//ofstream cout("out.txt");
int main(){
    ios::sync_with_stdio(false);
    int l, s, t, m,ans=0;
    cin >> l >> s >> t >> m;
    for (int i = 1; i <= m; i++){
        cin >> Mk[i];//存入M的临时数组
    }
    if (s == t){//当s==t时是特殊情况，只需判断为s/t倍数的点有无石子即可 ；参考CoolTeam。为啥用动态规划过不了，我也不知道
        for (int i = 1; i <= m; i++){
            if (Mk[i] % s == 0)ans++;
        }
        cout << ans;
        return 0;
    } //否则需要使用动态规划
    memset(f, 0x7f, sizeof(f));
    f[0] = 0;
    sort(Mk + 1, Mk + m + 1); //先给临时数组排个序
    for (int i = 1; i <= m; i++){
        if (Mk[i] - Mk[i - 1] >= 100)M[i] = M[i - 1] + 100; //如果两相邻石子之间距离大于100，就将他们之间的距离缩小到100 ；参考shutdown的结论，VengefulSpirit的证明过程
        else M[i] = M[i - 1] + Mk[i] - Mk[i - 1];
    }
    int M_cnt = 1;
    for (int i = 1; i <= M[m]+t; i++){ //比较容易的动态规划 ；参考sb123的动规转移方程
        for (int j = i-s; j >= max(i - t,0); j--){
            f[i] = min(f[j], f[i]);
        }
        if (M[M_cnt] == i){
            f[i]++;
            M_cnt++;
        }
    }
    ans = 10000;
    for (int i = M[m] + t-1; i >= M[m]; i--)ans = min(ans, f[i]);  //遍历从最后一个石子到最后一个石子+t-1的最短距离
    cout << ans;
}

20180805更新，表示缩点/离散化恶心死了，写了半天60，迫不得已看题解了。、
参考题解：https://www.luogu.org/blog/GXu/solution-p1052
https://peerless.blog.luogu.org/guo-he-xie-ti-bao-gao

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>
#include<functional>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int l;
int s, t, m;
int pos[105];
int d[105];
bool stone[400000];
int f[400000];
int main() {
    cin >> l >> s >> t >> m;
    for (int i = 1; i <= m; i++)cin >> pos[i];
    sort(pos + 1, pos + m + 1);
    for (int i = 1; i <= m; i++)d[i] = (pos[i] - pos[i - 1]) % 2520;
    for (int i = 1; i <= m; i++) {
        pos[i] = pos[i - 1] + d[i];
        stone[pos[i]] = true;
    }
    l = pos[m];
    for (int i = 1; i <= l + t; i++)f[i] = m;
    for (int i = 1; i <= l + t; i++) {
        for (int j = s; j <= t; j++) {
            if (i >= j)f[i] = min(f[i], f[i - j]);
            f[i] += stone[i];
        }
    }
    int ans = m;
    for (int i = l; i < l + t; i++)ans = min(ans, f[i]);
    cout << ans;
}

洛谷 A % B Problem

发表评论

题目编号：1865
用到的思想，一维前缀和，埃式素数筛

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
bool prime[1000005];
int prefixsum[1000005];
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    memset(prime,true,sizeof(prime));
    prime[1]=false;
    for(int i=2;i<=m;i++){
        if(!prime[i])continue;
        for(int j=2;i*j<=m;j++){
            prime[i*j]=false;
        }
    }
    for(int i=1;i<=m;i++){
        prefixsum[i]=prefixsum[i-1]+prime[i];
    }
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        if(l<1||r>m){
            cout<<"Crossing the line"<<endl;
            continue;
        }
        cout<<prefixsum[r]-prefixsum[l-1]<<endl;
    }
}

洛谷 最大正方形

发表评论

题号：1387
参考题解：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1387
作者: hychychyc 更新时间: 2017-06-06 11:25

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
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int n, m;
int arr[105][105];
int sum[105][105];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> arr[i][j];
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + arr[i][j]; //二维前缀和
        }
    }
    int maxn = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            for (int e = maxn; i + e <= n&&j + e <= m; e++){
                int w = sum[i + e][j + e] - sum[i][j + e] - sum[i + e][j] + sum[i][j];  //这个用二维前缀和计算正方形和
                if (e*e == w){
                    maxn = max(maxn, e);
                }
                else
                    break;
            }
        }
    }
    cout << maxn;
}

放上一张前缀和的图片，写的也很不清楚，也许有助于理解。

20180802更新：
上面代码都是错误的！！！！！！！！！
二维前缀和方程是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
int arr[105][105];
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)cin >> arr[i][j];
    for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + arr[i][j];
    for (int k = min(n, m); k > 0; k--) {
        for (int i = 1; i <= n - k + 1; i++) {
            for (int j = 1; j <= m - k + 1; j++) {
                if (k*k == arr[i + k - 1][j + k - 1] - arr[i - 1][j + k - 1] - arr[i + k - 1][j - 1] + arr[i - 1][j - 1]) { //参考这里
                    cout << k;
                    return 0;
                }
            }
        }
    }
}

动态规划做法：题解https://www.luogu.org/blog/user23035/solution-p1387

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
int arr[105][105];
int main() {
    cin >> n >> m;
    int ans = 0;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        cin >> arr[i][j];
        if(arr[i][j])arr[i][j] = min(min(arr[i - 1][j], arr[i][j - 1]), arr[i - 1][j - 1]) + 1;
        ans = max(ans, arr[i][j]);
    }
    cout << ans;
}

洛谷 传纸条

发表评论

题号：1006
同方格取数，只不过是有个别的地方需要一些变动。我傻傻的有一些地方没变……2333

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<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int m,n;
int f[55][55][55][55],arr[55][55];
int main(){
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            cin >> arr[i][j];
        }
    }
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n; j++){
            for (int k = 1; k <= m; k++){
                for (int l = 1; l <= n; l++){
                    f[i][j][k][l] = max(f[i - 1][j][k - 1][l], f[i][j - 1][k - 1][l]);
                    f[i][j][k][l] = max(f[i][j][k][l], f[i - 1][j][k][l - 1]);
                    f[i][j][k][l] = max(f[i][j][k][l], f[i][j - 1][k][l - 1]);
                    if (i == k && j == l)f[i][j][k][l] += arr[i][j];
                    else f[i][j][k][l] += arr[i][j] + arr[k][l];
                }
            }
        }
    }
    cout << f[m][n][m][n];
}

20180802
做的烦得要死。。。上面的代码没看懂^^^^……………….
https://www.luogu.org/blog/user20197/solution-p1006
https://www.luogu.org/blog/user26182/solution-p1006

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int m, n;
int arr[205][205];
int f[55][55][55][55];
int main() {
    cin >> m >> n;
    for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)cin >> arr[i][j];
    for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)for (int k = 1; k <= m; k++)for (int l = j + 1; l <= n; l++) {
        f[i][j][k][l] = max(max(f[i - 1][j][k - 1][l], f[i - 1][j][k][l - 1]), max(f[i][j - 1][k - 1][l], f[i][j - 1][k][l - 1])) + arr[i][j] + arr[k][l];
    }
    cout << f[m][n-1][m-1][n];
}

洛谷 方格取数

发表评论

题号：1004
这题还是比较简单的……虽然我看了题解，但是还是能看得懂的。。
参考题解：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1004
作者: sb123 更新时间: 2017-08-07 14:52

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<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int n;
int f[12][12][12][12],arr[12][12];
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    int rf1, rf2, rf3;
    while (cin >> rf1 >> rf2 >> rf3){
        if (rf1 == 0 && rf2 == 0 && rf3 == 0)break;
        arr[rf1][rf2] = rf3;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            for (int k = 1; k <= n; k++){
                for (int l = 1; l <= n; l++){
                    f[i][j][k][l] = max(f[i - 1][j][k - 1][l], f[i][j - 1][k - 1][l]);
                    f[i][j][k][l] = max(f[i][j][k][l], f[i - 1][j][k][l - 1]);
                    f[i][j][k][l] = max(f[i][j][k][l], f[i][j - 1][k][l - 1]);
                    if (i == k && j == l)f[i][j][k][l] += arr[i][j];
                    else f[i][j][k][l] += arr[i][j] + arr[k][l];
                }
            }
        }
    }
    cout << f[n][n][n][n];
}

洛谷 Likecloud-吃、吃、吃

发表评论

题号：1508
感动哭，第一个自己不用想状态转移方程就写出来的动规超级简单题……我是有多辣鸡……
这样的题一天做20道都没问题啊，要是NOIP全考这个就好了（逃）

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
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int n, m;
int f[205][205],arr[205][205];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> arr[i][j];
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            f[i][j] = max(max(f[i - 1][j], f[i - 1][j - 1]), f[i - 1][j + 1]) + arr[i][j];
        }
    }
    cout << max(max(f[n][m / 2 + 1],f[n][m/2]),f[n][m/2+2]);
}

20180802更新：
呃呃呃。。。。因为之前做过这样的题所以才觉得很简单。。。。。。。。。。。

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 m, n;
int arr[205][205];
int main() {
    memset(arr, 0x80, sizeof(arr));
    cin >> m >> n;
    for (int i = 1; i <= n; i++)arr[0][i] = 0;
    arr[m+1][(n + 1) / 2] = 0;
    for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)cin >> arr[i][j];
    for (int i = m; i >= 0; i--) {
        for (int j = 1; j <= n; j++) {
            arr[i][j] += max(max(arr[i + 1][j - 1], arr[i + 1][j]), arr[i + 1][j + 1]);
        }
    }
    int  mmax = 0;
    for (int i = 1; i <= n; i++) {
        mmax = max(mmax, arr[0][i]);
    }
    cout << mmax;
}

洛谷 A*B Problem（高精度）

发表评论

题号：P1303

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<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<cstring>
#include<utility>
using namespace std;
int num1[5000], num2[5000], num3[5000];
char str1[5000], str2[5000];
int main(){
    cin >> str1 >> str2;
    if (str1[0] == '0' || str2[0] == '0'){
        cout << 0;
        return 0;
    }
    int len1 = strlen(str1) - 1, len2 = strlen(str2) - 1;
    for (int i = len1; i >= 0; i--)num1[len1 - i + 1] = str1[i] - '0';
    for (int i = len2; i >= 0; i--)num2[len2 - i + 1] = str2[i] - '0';
    len1++;
    len2++;
    for (int i = 1; i <= len1; i++){
        for (int j = 1; j <= len2; j++){
            num3[i + j - 1] += num1[i] * num2[j];
        }
    }
    int i;
    for (i = 1; i<=len1+len2-1; i++){
        num3[i + 1] += num3[i] / 10;
        num3[i] %= 10;
    }
    for (int i = len1 + len2 - 1; i >= 1; i--){
        cout << num3[i];
    }
}

洛谷 银河英雄传说

发表评论

题号：P1196
参见题解：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1196
结合源代码阅读才好……
推荐题解作者：作者: 超神火星人 更新时间: 2017-04-29 09:14

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
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<cstring>
#include<utility>
int father[30005],size[30005],front[30005];
using namespace std;
int sfind(int node){
    if (father[node] == -1)return node;
    int fn = sfind(father[node]);
    front[node] += front[father[node]];
    return father[node]=fn;
}
int main(){
    for (int i = 1; i <= 30000; i++){
        father[i] = -1;
        size[i] = 1;
        front[i] = 0;
    }
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    while (n--){
        char c;
        int rf1, rf2;
        cin >> c >> rf1 >> rf2;
        int fa1 = sfind(rf1);
        int fa2 = sfind(rf2);
        switch (c){
        case 'M':
            front[fa1] += size[fa2];
            father[fa1] = fa2;
            size[fa2] += size[fa1];
            size[fa1] = 0;
            break;
        case 'C':
            if (fa1 != fa2)cout << "-1" << endl;
            else cout << abs(front[rf1] - front[rf2])-1 << endl;
            break;
        }
    }
}

20180815更新：
重做了这道题，还是看的这个人的题解。。。。

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<iostream>
using namespace std;
int t;
int father[30005],front[30005],num[30005];
int _find(int node){
    if(father[node]==0)return node;
    int fn=_find(father[node]);
    front[node]+=front[father[node]];
    return father[node]=fn;
}
int main(){
    ios::sync_with_stdio(false);
    for(int i=1;i<=30000;i++)num[i]=1;
    cin>>t;
    while(t--){
        char op;
        int x,y;
        cin>>op>>x>>y;
        int fx=_find(x),fy=_find(y);
        if(op=='M'){
            front[fx]+=num[fy];
            father[fx]=fy;
            num[fy]+=num[fx];
            num[fx]=0;
        }else{
            if(fx!=fy)cout<<-1<<endl;
            else cout<<abs(front[x]-front[y])-1<<endl;
        }
    }  
}

发现越到后面就越感觉是在抄题解怎么办，想也想不出来。