分类目录归档：算法

洛谷 [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;
    }
}

洛谷 传纸条

发表评论

题号：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];
    }
}

洛谷 [USACO1.5]数字三角形 Number Triangles

发表评论

题号：1216

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>
#define INF 2e9
using namespace std;
int n, arr[1005][1005];
int f[1005][1005];
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++){
            cin >> arr[i][j];
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++){
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + arr[i][j];
        }
    }
    int m = 0;
    for (int i = 1; i <= n; i++){
        if (f[n][i] > m)m = f[n][i];
    }
    cout << m;
}

洛谷 删数问题

发表评论
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<algorithm>
#include<string>
using namespace std;
int n;
string s;
int main(){
    ios::sync_with_stdio(false);
    cin >> s;
    cin >> n;
    for (int i = 0; i < s.length(); i++){
        if (s[i]>s[i + 1]&&n>0){
            s.erase(i, 1);
            n--;
            i=-1;//注意这里不是i--;因为有可能不符合顺序的数字出现在前面，需要重新返回头去找！
        }
        if (n == 0)break;
    }
    while (n--){
        s.erase(s.length() - 1, 1);
    }
    while (s[0] == '0')s.erase(s.begin());
    if(!s.empty())cout << s;
    else cout << "0";
}

洛谷 凌乱的yyy

发表评论

题号：1803
首先贴一种我一开始的错误做法。

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<iostream>
#include<algorithm>
using namespace std;
int n;
struct s{
    int start;
    int end;
    bool operator < (s & s1){
        if (end != s1.end)return end < s1.end;
        else return start < s1.start;
    }
}arr[1000005];
bool occupied[1000005];
int cnt;
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> arr[i].start >> arr[i].end;
    sort(arr + 1, arr + n + 1);
    for (int i = 1; i <= n; i++){
        if (!occupied[arr[i].start]){
            for (int j = arr[i].start; j < arr[i].end; j++){
                occupied[j] = true;
            }
            cnt++;
        }
    }
    cout << cnt;
}

这里的21行条件判断是错的。为什么呢？仅判断比赛开头有空闲是不能保证后面的时间有空闲的。那么我写一个正确的代码：

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<algorithm>
using namespace std;
int n;
struct s{
    int start;
    int end;
    bool operator < (s & s1){
        if (end != s1.end)return end < s1.end;
        else return start > s1.start;
    }
}arr[1000005];
int cnt;
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> arr[i].start >> arr[i].end;
    sort(arr + 1, arr + n + 1);
    int t = 0;
    for (int i = 1; i <= n; i++){
        if (t<=arr[i].start){
            cnt++;
            t = arr[i].end;
        }
    }
    cout << cnt;
}

这次的21行与之前的上一个比赛结束时间进行比较，如果在结束时间后面才能开始这个比赛。
注意：数组是排过序的，以结束时间、开始时间分别升序排序。