月度归档：2017年08月

洛谷 [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行与之前的上一个比赛结束时间进行比较，如果在结束时间后面才能开始这个比赛。
注意：数组是排过序的，以结束时间、开始时间分别升序排序。

洛谷 智力大冲浪

发表评论

题号：1230
一开始想排完序之后直接从前到后由时间1到时间n依次安排，这样做是不对的。
完全可以从一个任务的截止时间开始从后往前安排，哪里有空缺位置就放在那里。
一开始的想法忽略了其他任务也可以放在前面。（说的不太清楚）

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

洛谷 关押罪犯

发表评论

题号：1525
参见题解：作者: 超级范范 更新时间: 2017-07-23 17:05
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1525

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<algorithm>
#include<cstring>
using namespace std;
int father[40005];
struct s{
    int u, v, w;
    bool operator < (s & s1){
        return w>s1.w;
    }
}arr[100005];
int _find(int node){
    if (father[node] == -1)return node;
    return father[node] = _find(father[node]);
}
void merge(int x, int y){
    x = _find(x);
    y = _find(y);
    if (x != y)father[x] = y;
}
bool sameset(int x, int y){
    return _find(x) == _find(y);
}
int main(){
    memset(father, -1, sizeof(father));
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> arr[i].u >> arr[i].v >> arr[i].w;
    }
    sort(arr + 1, arr + m + 1);
    int maxw = 0;
    for (int i = 1; i <= m; i++){
        if (sameset(arr[i].u, arr[i].v)){
            if (arr[i].w > maxw){
                cout << arr[i].w;
                return 0;
            }
        }
        else{
            merge(arr[i].u, arr[i].v + n);
            merge(arr[i].v, arr[i].u + n);
        }
    }
    cout << 0;
}

20180814更新：除了并查集做法还有二分图做法，应该也很好做，不写了。
题解：https://www.luogu.org/blog/Kesdiael3/solution-p1525

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<algorithm>
using namespace std;
int n,m;
struct p{
    int a,b,c;
    bool operator < (const p& p2) const{
        return c>p2.c;
    }
}ps[100005];
int father[40005];
int _find(int x){
    if(father[x]==0)return x;
    return father[x]=_find(father[x]);
}
bool _union(int x,int y){
    if(_find(x)==_find(y))return false;
    father[_find(x)]=_find(y);
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>ps[i].a>>ps[i].b>>ps[i].c;
    sort(ps+1,ps+m+1);
    for(int i=1;i<=m;i++){
        if(_find(ps[i].a)==_find(ps[i].b)){
            cout<<ps[i].c;
            return 0;
        }else{
            _union(ps[i].a,ps[i].b+n);
            _union(ps[i].b,ps[i].a+n);
        }
    }
    cout<<0;
}

洛谷 封锁阳光大学

发表评论

题号：1330
这个属于搜索中的染色问题，之前不会，以后要多多学习。

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
#include<iostream>
#include<algorithm>
#include<list>
#include<queue>
using namespace std;
list<int> edge[100005];
int n, m;
int point[100005];
inline int color(int x){
    if (x == 1)return 2;
    else return 1;
}
int BFS(int i){
    int cnter1 = 0, cnter2 = 0;
    queue<pair<int, int>> q;
    q.push(pair<int, int>(i, 1));
    while (!q.empty()){
        pair<int, int> cur = q.front(); q.pop();
        if (point[cur.first] != 0){
            if (point[cur.first] != cur.second)return -1;
            continue;
        }
        point[cur.first] = cur.second;
        if (cur.second == 1)cnter1++;
        if (cur.second == 2)cnter2++;
        for (auto iter = edge[cur.first].begin(); iter != edge[cur.first].end(); iter++){
            q.push(pair<int, int>((*iter), color(cur.second)));
        }
    }
    return cnter1 < cnter2 ? cnter1 : cnter2;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    int sum = 0;
    for (int i = 1; i <= n; i++){
        if (point[i] == 0){
            int t=BFS(i);
            if (t == -1){
                cout << "Impossible";
                return 0;
            }
            else
                sum += t;
        }
    }
    cout << sum;
}

20180806：基本上自己做出来了！！哈哈！有个小细节忽略了：是每个互不联通子图分别找出最小值加起来，不是整图统计。

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n, m;
vector<int> edges[10005];
int color[10005];
inline int getOppoColor(int x) {
    if (x == 1)return 2;
    else return 1;
}
int BFS(int s) {
    int color1 = 0, color2 = 0;
    queue<int> q;
    color[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int node = q.front();
        if (color[node] == 1)color1++;
        else color2++;
        q.pop();
        for (int i = 0; i < edges[node].size(); i++) {
            if (color[edges[node][i]] == 0) {
                color[edges[node][i]] = getOppoColor(color[node]);
                q.push(edges[node][i]);
            }
            else if (color[edges[node][i]] == color[node]) {
                return 0;
            }
        }
    }
    return min(color1, color2);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    int cnter = 0;
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0 && edges[i].size() != 0) {
            int cur = BFS(i);
            if (cur == 0) {
                cout << "Impossible";
                return 0;
            }
            cnter += cur;
        }
    }

    cout << cnter;
}