练习

ACM

practice

给自己的建议

  1. 英文题一定要认真读，看一些条件有没有涉及到！
  2. WA了n发一定要调整思路，比如最小新整数，不要心态崩了

肿瘤检测

注意边界的定义，没看条件wa了好多发。。。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 100+10;
int mp[maxn][maxn];
bool vis[maxn][maxn];
bool is[maxn][maxn];
int n;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int area, zhou;
bool check(int x, int y){
    if(x<1||x>n||y<1||y>n) return false;
    if(mp[x][y]>50) return false;
    if(vis[x][y]) return false;
    return true;
}
void bfs(int x, int y){
    queue<pii> q;
    while(!q.empty()) q.pop();
    q.push(make_pair(x, y));
    while(!q.empty()){
        pii temp = q.front();
        q.pop();
        int x1 = temp.fi, y1 = temp.se;
        if(vis[x1][y1]) continue;
        area++;
        vis[x1][y1] = true;
        is[x1][y1] = true;
        for(int i=0; i<4; i++){
            int nx=dx[i]+x1;
            int ny=dy[i]+y1;
            if(check(nx, ny)){
                q.push(make_pair(nx, ny));
            }
        }
    }
}
bool judge(int x, int y){
    if(x<1||x>n||y<1||y>n) return false;
    if(mp[x][y]<=50) return false;
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;{
        cls(mp, 0), cls(vis, 0), cls(is, 0);
        area=zhou = 0;
        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin>>mp[i][j];
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(!vis[i][j]&&mp[i][j]<=50){
                    bfs(i, j);
                }
            }
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(is[i][j]){
                    bool flag = false;
                    if(i == 1||i==n||j==1||j==n) {
                        flag = true;
                    }
                    for(int k=0; k<4; k++){
                        int nx = i+dx[k];
                        int ny = j+dy[k];
                        if(judge(nx, ny)){
                            flag = true;
                        }
                    }
                    if(flag) zhou++;
                }
            }
        }
        cout<<area<<" "<<zhou<<endl;
    }
    return 0;
}

railway station (DP)

注意s>t要调换顺序

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e4+10;
int l1, l2, l3;
ll a, b, c;
int n;
int s, t;
int dis[maxn];
ll dp[maxn];
int main(){
    ios::sync_with_stdio(false);
    cin>>l1>>l2>>l3>>a>>b>>c;
    cin>>n;
    cin>>s>>t;
    if(s>t)swap(s, t);
    for(int i=2; i<=n; i++) cin>>dis[i];
    for(int i=0; i<maxn; i++) dp[i] = inf;
    dp[s] = 0;
    for(int i=s+1; i<=t; i++){
        int idx1 = lower_bound(dis+1, dis+1+n, dis[i]-l1)-(dis+1)+1;
        for(int j=idx1; j<i; j++) dp[i] = min(dp[i], dp[j]+a);
        idx1 = lower_bound(dis+1, dis+1+n, dis[i]-l2)-(dis+1)+1;
        for(int j=idx1; j<i; j++) dp[i] = min(dp[i], dp[j]+b);
        idx1 = lower_bound(dis+1, dis+1+n, dis[i]-l3)-(dis+1)+1;
        for(int j=idx1; j<i; j++) dp[i] = min(dp[i], dp[j]+c);
    }
    cout<<dp[t]<<endl;
    return 0;
}

prime path

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
int s, t;
struct Node{
    int num;
    int cost;
    Node(int _num, int _cost):num(_num), cost(_cost){}
};
int mi[10];
int getval(string x){
    int ans = 0;
    int len = x.length();
    for(int i=0; i<x.length(); i++){
        ans += mi[len-i-1]*(x[i]-'0');
    }
    return ans;
}
bool judge(int x){
    for(int i=2; i<=sqrt(x); i++){
        if(x%i == 0) return false;
    }
    return true;
}
unordered_map<int, bool> vis;
void bfs(){
    queue<Node> q;
    q.push(Node(s, 0));
    vis[s] = true;
    while(!q.empty()){
        Node temp = q.front();
        q.pop();
        int num = temp.num;
        //cout<<num<<endl;
        int cost = temp.cost;
        if(num == t) {
            cout<<cost<<endl;
            return ;
        }
        string ha="";
        while(num){
            ha+=char(num%10+'0');
            num/=10;
        }
        reverse(ha.begin(), ha.end());
        for(int i=0; i<ha.length(); i++){
            for(int j=0; j<=9; j++){
                if(j==0&&i==0) continue;
                if(ha[i]-'a' == j) continue;
                string tt = ha;
                ha[i] = char(j+'0');
                int now = getval(ha);
                if(judge(now)&&vis[now] == false){
                    q.push(Node(now, cost+1));
                    vis[now] = true;
                }
                ha = tt;
            }
        }
    }
}
int main(){
    int _;
    mi[0] = 1;
    for(int i=1; i<10; i++) mi[i] = mi[i-1]*10;
    cin>>_;
    while(_--){
        cin>>s>>t;
        vis.clear();
        bfs();
    }
    return 0;
}

list 的模拟

合并后一个不能clear什么鬼。。。至今不知道原因。。。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
#include <list>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e4+10;
map<int, list<int> > mp;
int main(){
    ios::sync_with_stdio(false);
    int _;
    cin>>_;
    string op;
    int a, b;
    while(_--){
        cin>>op;
        if(op == "new"){
            cin>>a;
            mp[a] = list<int>();
        }
        else if(op == "add"){
            cin>>a>>b;
            mp[a].push_back(b);
        }
        else if(op == "out"){
            cin>>a;
            mp[a].sort();
            for(auto&it:mp[a]){
                cout<<it<<" ";
            }
            cout<<endl;
        }
        else if(op == "merge"){
            cin>>a>>b;
            mp[a].merge(mp[b]);
            //mp[b].clear();
        }
        else {
            cin>>a;
            mp[a].sort();
            mp[a].unique();
        }
    }
    return 0;
}

打印三角形

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2048+10;
char mp[maxn][maxn];
int n;
void solve(int x, int y, int depth){
    if(depth == 1){
        mp[x][y] = '/', mp[x][y+1] = mp[x][y+2] = '_', mp[x][y+3] = '\\';
        mp[x-1][y+1] = '/', mp[x-1][y+2] = '\\';
        return ;
    }
    int du = (1<<depth);
    solve(x, y, depth-1), solve(x, y+du, depth-1), solve(x-du/2, y+du/2, depth-1);
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n){
        if(n == 0) break;
        int tot = (1<<n);
//        for(int i=0; i<=tot; i++){
//            for(int j=0; j<=tot*2;j++) mp[i][j] = ' ';
//        }
        cls(mp, 0);
        solve(tot, 0, n);
        for(int i=0; i<=tot; i++){
            int last=0;
            for(int j=0; j<=tot*2; j++) if(mp[i][j]) last = j;
            for(int j=0; j<last; j++) if(!mp[i][j]) mp[i][j] = ' ';
        }
        for(int i=1; i<=tot; i++) cout<<mp[i]<<endl;
        cout<<endl;
    }
    return 0;
}

麦森数

求一个数的位数以及最后的500位，模拟高精度的乘法

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1000+10;
int p;
int ans[maxn], ansl;
int x[maxn], xl;
int c[maxn], cl;
void mul(int a[], int b[], int& al, int bl){
    cls(c, 0);
    cl = 1;
    for(int i=1; i<=al; i++){
        for(int j=1; j<=bl; j++){
            if(i+j-1>500) continue;
            c[i+j-1] += a[i]*b[j];
            if(c[i+j-1]>=10){
                c[i+j] += (c[i+j-1]/10);
                c[i+j-1] %= 10;
            }
        }
    }
    cl = al+bl;
    while(cl>=1&&!c[cl]) --cl;
    al = cl;
    for(int i=1; i<=cl; i++) a[i] = c[i];
}
void quickpow(){
    ans[1] = 1; ansl=1;
    x[1] = 2; xl = 1;
    while(p){
        if(p&1)mul(ans, x, ansl, xl);
        mul(x, x, xl, xl);
        p >>= 1;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>p;
    cout<<int(p*log10(2)+1)<<endl;
    quickpow();
    --ans[1];
    for(int i=1; i<=502; i++){
        if(ans[i]<0) {
            ans[i] += 10;
            ans[i+1]-=1;
        }
    }
    for(int i=9; i>=0; i--){
        for(int j=50; j>=1; j--){
            cout<<ans[i*50+j];
        }
        cout<<endl;
    }
    return 0;
}

集合问题

主要考察一个小根堆的模拟的过程，答案是枚举出来的。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
int a[maxn];
priority_queue<int, vector<int>, greater<int> > pq;
int n;
bool cmp(int a, int b){
    return a>b;
}
int mi = inf;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    int mx_num = -1;
    for(int i=1; i<=n; i++) cin>>a[i], mx_num = max(mx_num, a[i]);
    sort(a+1, a+1+n, cmp);
    int ans = 0;
    for(int i=1; i<=n; i++){
        int cost = 0;
        while(!pq.empty()) pq.pop();
        for(int j=1; j<=i; j++) pq.push(0);
        for(int i=1; i<=n; i++){
            int temp = pq.top();
            pq.pop();
            pq.push(temp+a[i]);
        }
        while(!pq.empty()) {
            int temp  = pq.top();
            pq.pop();
            cost += abs(temp-mx_num);
        }
        if(mi>cost){
            ans = i;
            mi = cost;
        }
    }
    cout<<ans<<endl;
    return 0;
}

最大子矩阵的求法

先枚举列i, j然后再枚举行。

Q：那么最大矩形是怎么维护的？

多重背包的二进制优化

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+10;
int num[maxn];
int dp[maxn];
int main(){
    ios::sync_with_stdio(false);
    int kase = 0;
    while(true){
        int aim = 0;
        for(int i=1; i<=6; i++) cin>>num[i], aim += num[i]*i;
        if(aim == 0) break;
        if(aim%2){
            cout<<"Collection #"<<++kase<<":"<<endl;
            cout<<"Can't be divided."<<endl<<endl;
            continue;
        }
        dp[0] = 0;
        int V = 60000;
        for(int i=1; i<=60000; i++) dp[i] = 0;
        for(int i=1; i<=6; i++){
            for(int k=1; k<num[i]; num[i]-=k, k<<=1)
                for(int j=V; j>=k*i; j--)
                    dp[j] = max(dp[j], dp[j-k*i]+k*i);
            for(int j=V; j>=num[i]*i; j--){
                dp[j] = max(dp[j], dp[j-num[i]*i]+num[i]*i);
            }
        }
        if(dp[aim/2] == aim/2){
            cout<<"Collection #"<<++kase<<":"<<endl;
            cout<<"Can be divided."<<endl<<endl;
        }
        else {
            cout<<"Collection #"<<++kase<<":"<<endl;
            cout<<"Can't be divided."<<endl<<endl;
        }
    }
    return 0;
}

最短路+限制条件

注意是有向图。。。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
int n, m, k;
struct Edge{
    int v, weight, cost;
    int next;
}node[20000+10];
int head[maxn];
int tot = 0;
void addedge(int u, int v, int w, int cost){
    node[tot].v = v, node[tot].weight = w, node[tot].cost = cost, node[tot].next=head[u], head[u] = tot++;
}
bool vis[maxn];
int dis[maxn];
int cc[maxn];
struct Node{
    int s, dis, cost;
    bool operator < (const Node &b) const {
        return dis>b.dis;
    }
    Node(int _s, int _dis, int _cost):s(_s), dis(_dis), cost(_cost){}
};
priority_queue<Node> pq;
void dij(){
    dis[n] = inf;
    //for(int i=head[1]; ~i; i=node[i].next) dis[node[i].v] = node[i].weight;
    while(!pq.empty()) pq.pop();
    pq.push(Node(1, 0, 0));
    while(!pq.empty()){
        Node temp = pq.top();
        pq.pop();
        int u=temp.s, w=temp.dis, c=temp.cost;
        //cout<<u<<" "<<w<<" "<<c<<endl;
        //if(vis[u]) continue;
        if(u == n) {
            dis[n] = w;
            break;
        }
        //vis[u] = true;
        for(int i=head[u]; ~i; i=node[i].next){
            int v = node[i].v;
            //cout<<v<<endl;
            if(node[i].cost+c<=k){
                pq.push(Node(v, w+node[i].weight, c+node[i].cost));
            }
        }
    }
    if(dis[n]!=inf) cout<<dis[n]<<endl;
    else cout<<-1<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>k>>n>>m)
    {
        cls(head, -1), tot=0;
        int u, v, w, c;
        for(int i=0; i<m; i++){
            cin>>u>>v>>w>>c;
            addedge(u, v, w, c);
        }
        dij();
    }
    return 0;
}
/*
1
3 2
1 2 4 1
2 3 4 1
*/

前缀式的计算

使用了递归

中缀式转换为后缀式

真实排名

  1. 注意组合数的求解
  2. (ans += num)%=mod.
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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
const int mod = 998244353;
ll fact[maxn];
ll inv[maxn];
int num[maxn];
int n, m;
ll C(int n, int m){
    if(n<0||m<0||n<m) return 0;
    return (fact[n]*inv[m]%mod)*inv[n-m]%mod;
}
ll powmod(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b&1){
            ans = ans*a%mod;
        }
        a = a*a%mod;
        b>>=1;
    }
    return ans;
}
int a1[maxn];
int main(){
    ios::sync_with_stdio(false);
    fact[0] = 1;
    for(int i=1; i<maxn; i++){
        fact[i] = fact[i-1]*i%mod;
    }
    inv[maxn-1] = powmod(fact[maxn-1], mod-2);
    for(int i=maxn-2; i>=0; i--) inv[i] = inv[i+1]*(i+1)%mod;
    //for(int i=1; i<=10; i++)cout<<inv[i]<<endl;
    //cout<<C(2, 2);
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>num[i], a1[i] = num[i];
    sort(num+1, num+1+n);
    ll ans = 0;
    for(int i=1; i<=n; i++){
        ans = 0;
        if(a1[i] == 0) {cout<<C(n, m)<<endl;continue;}
        //a[i] no change
        int tot = lower_bound(num+1, num+1+n, a1[i])-lower_bound(num+1, num+1+n, (a1[i]+1)/2);
        //cout<<"tot "<<tot<<endl;
        (ans += C(n-tot-1, m))%=mod;
        //a[i] multiple 2
        tot = lower_bound(num+1, num+1+n, a1[i]*2)-lower_bound(num+1, num+1+n, a1[i]);
        //cout<<"tot "<<tot<<endl;
        (ans += C(n-tot, m-tot))%=mod;
        cout<<ans<<endl;
    }
    return 0;
}

任务排序

注意string的排序关系，要先按照string的长度来排序，比如1111, 22, 字典序的话1111小于22， 但是数值上是大的，注意这里的细节。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
struct Node{
    string s[4];
    string raw;
    bool operator  < (const Node &b){
        if(s[3].length()!=b.s[3].length()) return s[3].length()<b.s[3].length();
        if(s[3]!=b.s[3])  return s[3]<b.s[3];
        else {
            if(s[1] != b.s[1]) return s[1]<b.s[1];
            else if(s[2] != b.s[2])return s[2]<b.s[2];
        }
    }
}node[maxn];
int main(){
    ios::sync_with_stdio(false);
    string temp;
    int tot = 1;
    while(getline(cin, temp)){
        if(temp.length() == 0) break;
        node[tot].raw = temp;
        for(int i=0; i<4; i++) node[tot].s[i] = "";
        bool flag = false;
        int idx = 0;
        for(int i=0; i<temp.length(); i++){
            if(temp[i]!=' '&&flag == false){
                flag = true;
                node[tot].s[idx] += temp[i];
            }
            else if(flag &&temp[i]!=' '){
                node[tot].s[idx] += temp[i];
            }
            else if(flag&&temp[i] == ' '){
                idx++;
                flag = false;
            }
        }
        tot++;
    }
    sort(node+1, node+tot);
    for(int i=1; i<tot; i++){
//        int fir=0, last = node[i].raw.length()-1;
//        while(node[i].raw[fir] == ' ') fir++;
//        while(node[i].raw[last] == ' ') last--;
//        for(int j=fir; j<=last; j++){
//            cout<<node[i].raw[j];
//        }
//        cout<<endl;
        cout<<node[i].raw<<endl;
    }
    return 0;
}

中位数

奇怪的精度的问题。。我也不知道什么错误

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<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 250000+10;
long long num[maxn];
int main(){
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld", &num[i]);
    }
    sort(num+1, num+1+n);
    if(n%2 == 0){
        int mid = n/2;
        if((num[mid]+num[mid+1])%2 == 0)
            printf("%.1f\n", (num[mid]+num[mid+1])/2.0);
        else printf("%.1f\n", 1.0*(num[mid]+num[mid+1])/2.0);
    }
    else{
        int mid = n/2+1;
        printf("%.1f\n", num[mid]*1.0);
    }
    return 0;
}

多组数据的二分图。。。

由于没有多组数据读入导致狂wa…

tcl

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 500+10;
int n, m, s, v;
struct Node{
    double x, y;
}node[maxn];
struct Edge{
    int v, next;
}edge[20000+10];
int head[10000+10], tot = 0;
double dis(Node a, Node b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void add_edge(int u, int v){
    edge[tot].v = v, edge[tot].next = head[u], head[u] = tot++;
}
int linker[maxn];
bool used[maxn];
bool dfs(int u){
    for(int i=head[u]; ~i; i=edge[i].next){
        int v = edge[i].v;
        if(!used[v]){
            used[v] = true;
            if(linker[v] == -1 || dfs(linker[v])){
                linker[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungary(){
    int res = 0;
    cls(linker, -1);
    for(int i=1; i<=n; i++){
        cls(used, 0);
        if(dfs(i)) res++;
    }
    return n-res;
}
int main(){
    while(cin>>n>>m>>s>>v){
        cls(head, -1);
        tot = 0;
        for(int i=1; i<=n; i++) cin>>node[i].x>>node[i].y;
        for(int i=n+1; i<=n+m; i++) cin>>node[i].x>>node[i].y;
        for(int i=1; i<=n; i++){
            for(int j=n+1; j<=n+m; j++){
                if(dis(node[i], node[j])/v<=double(s)){
                    add_edge(i, j);
                }
            }
        }
        cout<<hungary()<<endl;
    }
    return 0;
}

完美覆盖

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<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 30+10;
ll dp[maxn];
int main(){
    ios::sync_with_stdio(false);
    dp[0] = 1;
    dp[2] = 3, dp[3] = 0;
    for(int i=4; i<=30; i+=2) dp[i] = dp[i-2]*4-dp[i-4];
    int n;
    while(cin>>n){
        if(n == -1) break;
        cout<<dp[n]<<endl;
    }
    return 0;
}

特殊密码锁

一开始枚举第一位，然后dfs就行了。。。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
string s, t;
bool change[maxn];
int num1[maxn], num2[maxn];
vector<int> ans;
bool check(){
    int temp[40];
    for(int i=0; i<s.length(); i++){
        temp[i] = s[i]-'0';
    }
    for(int i=0; i<s.length(); i++){
        if(change[i]){
            if(i>=1) temp[i-1]^=1;
            temp[i]^=1;
            if(i+1<s.length()) temp[i+1] ^= 1;
        }
    }
    for(int i=0; i<s.length(); i++) if(temp[i]!=num2[i]) return false;
    return true;
}
void dfs(int now){
    if(now == s.length()){
        int tot = 0;
        if(!check()) return;
        for(int i=0; i<s.length(); i++){
            if(change[i]) tot++;
        }
        ans.push_back(tot);
        return ;
    }
    if(now>=1&&num1[now-1]!=num2[now-1]){
        change[now] = true;
        num1[now-1]^=1;
        num1[now] ^= 1;
        if(now+1<s.length()) num1[now+1] ^= 1;
        dfs(now+1);
        change[now] = false;
        num1[now-1]^=1;
        num1[now] ^= 1;
        if(now+1<s.length()) num1[now+1] ^= 1;
    }
    else {
        dfs(now+1);
    }
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>s>>t){
        //cin>>s>>t;
        for(int i=0; i<s.length(); i++) num1[i] = s[i]-'0';
        for(int i=0; i<t.length(); i++) num2[i] = t[i]-'0';
        cls(change, 0);
        ans.clear();
        num1[0] ^= 1;
        if(s.length()>=2) num1[1]^=1;
        change[0] = true;
        dfs(1);
        num1[0] ^= 1;
        if(s.length()>=2) num1[1] ^=1;
        change[0] = false;
        dfs(1);
        int last = inf;
        for(int i=0; i<ans.size(); i++){
            last = min(last, ans[i]);
        }
        if(last == inf) cout<<"impossible"<<endl;
        else cout<<last<<endl;
    }
    return 0;
}

矩形切割，最大面积最小

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 20+10;
int w, h, m;
int dp[maxn][maxn][maxn];
void solve(){
    for(int i=1; i<=w; i++){
        for(int j=1; j<=h; j++) dp[i][j][1] = i*j;
    }
    for(int i=1; i<=w; i++){
        for(int j=1; j<=h; j++){
            for(int k=2; k<=min(i*j, m); k++){
                dp[i][j][k] = inf;
                for(int a=1; a<i; a++){
                    for(int b=1; b<k; b++){
                        dp[i][j][k] = min(dp[i][j][k], max(dp[i-a][j][b], dp[a][j][k-b]));
                    }
                }
                for(int a=1; a<j; a++){
                    for(int b=1; b<k; b++){
                        dp[i][j][k] = min(dp[i][j][k], max(dp[i][j-a][b], dp[i][a][k-b]));
                    }
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>w>>h>>m){
        if(w+h+m == 0) break;
        solve();
        cout<<dp[w][h][m]<<endl;
    }
    return 0;
}

雷涛的猫

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
int tree[2010][5010];
int dp[2010][5010];
int mx[5010];
int n, h, delta;
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>h>>delta){
        cls(dp, 0), cls(tree, 0);
        for(int i=1; i<=n; i++){
            int tot;
            cin>>tot;
            for(int j=1; j<=tot; j++){
                int temp;
                cin>>temp;
                tree[i][temp]++;
            }
        }
        int ans = 0;
        for(int i=1; i<=h; i++){
            mx[i] = dp[1][i-1];
            for(int j=1; j<=n; j++){
                dp[i][j] = dp[i-1][j];
                if(i-delta>=0) dp[i][j] = max(dp[i][j], mx[i-delta]);
                dp[i][j] += tree[j][i];
                mx[i] = max(mx[i], dp[i][j]);
                ans = max(dp[i][j], ans);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

取石子游戏

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
int n, m;
bool dfs(int x, int y, int turn){
    if(x<y) swap(x, y);
    if(x%y == 0 &&turn%2 == 0){
        return true;
    }
    if(x%y == 0 &&turn%2) return false;
    if(x/y>=2 && turn%2==0 ) return true;
    if(x/y>=2 &&turn%2) return false;
    for(int i=1; i<=x/y; i++){
        if(dfs(x-y*i, y, turn+1)) return true;
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
        if(n+m == 0) break;
        if(dfs(n, m, 0)) {
            cout<<"win"<<endl;
        }
        else cout<<"lose"<<endl;
    }
    return 0;
}

分割矩形使得均方差最小

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 20+10;
int num[maxn][maxn];
int sum[maxn][maxn];
int k;
int dp[maxn][maxn][maxn][maxn][maxn];
int get(int x1, int y1, int x2, int y2){
    int a = sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
    return a*a;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>k;
    for(int i=1; i<=8; i++) for(int j=1; j<=8; j++) cin>>num[i][j];
    for(int i=1; i<=8; i++){
        for(int j=1; j<=8; j++){
            sum[i][j] += (sum[i][j-1]+num[i][j]);
        }
        for(int j=1; j<=8; j++){
            sum[i][j] += sum[i-1][j];
        }
    }
    for(int i=1; i<=8; i++){
        for(int j=1; j<=8; j++){
            for(int a=i;a<=8; a++){
                for(int b=j; b<=8; b++){
                    dp[i][j][a][b][0] = get(i, j, a, b);
                }
            }
        }
    }
    for(int ci=1; ci<=k-1; ci++){
        for(int i=1; i<=8; i++){
            for(int j=1; j<=8; j++){
                for(int a=i; a<=8; a++){
                    for(int b=j; b<=8; b++){
                        dp[i][j][a][b][ci] = inf;
                        //横切
                        for(int c=i; c<a; c++){
                            dp[i][j][a][b][ci] = min(dp[i][j][a][b][ci], min(dp[i][j][c][b][0]+dp[c+1][j][a][b][ci-1], dp[i][j][c][b][ci-1]+dp[c+1][j][a][b][0]));
                        }
                        //纵切
                        for(int c=j; c<b; c++){
                            dp[i][j][a][b][ci] = min(dp[i][j][a][b][ci], min(dp[i][j][a][c][0]+dp[i][c+1][a][b][ci-1], dp[i][j][a][c][ci-1]+dp[i][c+1][a][b][0]));
                        }
                    }
                }
            }
        }
    }cout<<fixed<<setprecision(3);
    cout<<sqrt(double(dp[1][1][8][8][k-1])/k-double(sum[8][8])*sum[8][8]/k/k);
    return 0;
}

LIS(nlogn)做法

差分约束系统+堆优化

a-b<=c, b->a一条权值为c的边，然后求最短路

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e4+10;
struct Edge{
    int v, next, weight;
}edge[maxn<<1];
int n, m;
int head[maxn], tot;
void addedge(int u, int v, int weight){
    edge[tot].v = v, edge[tot].weight = weight, edge[tot].next = head[u], head[u] = tot++;
}
bool in[maxn];
int tim[maxn];
int dis[maxn];
struct Node{
    int u, dis;
    bool operator < (const Node &b) const {
        return dis>b.dis;
    }
    Node(int _u, int _dis):u(_u), dis(_dis){}
};
bool spfa(){
    priority_queue<Node> q;
    while(!q.empty()) q.pop();
    for(int i=1; i<=n; i++) dis[i] = inf;
    dis[0]  =0;
    q.push(Node(0, 0));
    in[0] = true, tim[0]++;
    while(!q.empty()){
        Node temp = q.top();
        q.pop();
        int u = temp.u;
        in[u] = false;
        for(int i=head[u]; ~i; i=edge[i].next){
            int v = edge[i].v;
            if(dis[v]>dis[u]+edge[i].weight&&!in[v]){
                dis[v] = dis[u]+edge[i].weight;
                if(!in[v]){
                    in[v] = true;
                    q.push(Node(v, dis[v]));
                    tim[v]++;
                    if(tim[v]>=n) return false;
                }
            }
        }
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int op, u, v, w;
    cls(head, -1);
    for(int i=1; i<=m; i++){
        cin>>op;
        if(op == 3){
            cin>>u>>v;
            addedge(u, v, 0);
            addedge(v, u, 0);
        }
        else{
            cin>>u>>v>>w;
            if(op == 1) addedge(u, v, -w);
            else addedge(v, u, w);
        }
    }
    for(int i=1; i<=n; i++) addedge(0, i, 1);
    //cout<<"ha"<<endl;
    if(spfa()) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

解方程

暴力判断，注意条件，要将string排序

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
map<char, int> table;
int target;
string s;
int num[5];
bool has[30];
bool check(){
    int ans = 0;
    //for(int i=0; i<5; i++) cout<<num[i]<<" ";
    //cout<<endl;
    ans = num[0]-num[1]*num[1]+num[2]*num[2]*num[2]-num[3]*num[3]*num[3]*num[3]+num[4]*num[4]*num[4]*num[4]*num[4];
    return (ans == target);
}
bool dfs(int depth){
    if(depth == 5){
        if(check()){
            for(int i=0; i<5; i++) cout<<char(num[i]+'A'-1);
            cout<<endl;
            return true;
        }
        return false;
    }
    for(int i=s.length()-1; i>=0; i--){
        if(has[table[s[i]]]) continue;
        num[depth] = table[s[i]];
        has[table[s[i]]] = true;
        if(dfs(depth+1)) return true;
        has[table[s[i]]] = false;
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    for(int i=1; i<=26; i++) table[char('A'+i-1)] = i;
    while(cin>>target>>s){
        if(target == 0&&s == "END") break;
        cls(has, 0);
        sort(s.begin(), s.end());
        //cout<<s<<endl;
        if(!dfs(0)){
            cout<<"no solution"<<endl;
        }
    }
    return 0;
}

EXCHANGE RATE

会存在精度问题，然后就乘了100，然后再还原就可以了。

相当于是带浮点数的dp要注意精度问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int dp[400][2];
int main()
{
	int n;
	while (scanf("%d", &n) == 1 && n) {
		int i, j;
		double x;
		dp[0][0] = 100000;
		dp[0][1] = 0;
		for (i = 1; i <= n; ++i) {
			scanf("%lf", &x);
			dp[i][0] = max(dp[i - 1][0], (int)(dp[i - 1][1] * 0.97 * x));
			dp[i][1] = max(dp[i - 1][1], (int)(dp[i - 1][0] * 0.97 / x));
		}
		printf("%d.%02d\n", dp[n][0] / 100, dp[n][0] % 100);
	}
    return 0;
}

divisible

记录方案这样就能减少复杂度

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 10000+10;
int dp[maxn][110];
int num[maxn];
int n, k;
void solve(){
    dp[0][0] = true;
    for(int i=1; i<=n; i++){
        for(int j=0; j<k; j++){
            if(dp[i-1][((j-num[i])%k+k)%k]){
                dp[i][j] = true;
            }
            if(dp[i-1][((j+num[i])%k+k)%k]){
                dp[i][j] = true;
            }
        }
    }
    if(dp[n][0])cout<<"Divisible"<<endl;
    else cout<<"Not divisible"<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1; i<=n; i++) cin>>num[i];
    solve();
    return 0;
}

silver cow

首先想到的是floyd，时间复杂度爆炸，后转化为两次最短路即可。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1000+10;
struct Edge{
    int v, next, weight;
}edge[200000+10];
int n, m, x;
int head[maxn], tot;
void addedge(int u, int v, int weight){
    edge[tot].v=v, edge[tot].weight=weight, edge[tot].next=head[u], head[u]=tot++;
}
int u[200000+10], v[200000+10], w[200000+10];
int ans[maxn];
int dis[maxn];
bool vis[maxn];
struct Node{
    int u, dis;
    Node(int _u, int _dis):u(_u), dis(_dis){}
    bool operator < (const Node & b) const{
        return dis>b.dis;
    }
};
void dij(){
    cls(dis, 0);
    dis[x] = 0;
    for(int i=1; i<=n; i++) if(i!=x) dis[i] = inf;
    cls(vis, 0);
    priority_queue<Node> pq;
    pq.push(Node(x, 0));
    while(!pq.empty()){
        Node temp = pq.top();pq.pop();
        int u=temp.u;
        //cout<<u<<endl;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i=head[u]; ~i; i=edge[i].next){
            int v = edge[i].v;
            if(!vis[v]&&dis[v]>temp.dis+edge[i].weight){
                dis[v] = temp.dis+edge[i].weight;
                pq.push(Node(v, dis[v]));
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>m>>x){
        cls(head, -1);
        for(int i=1; i<=m; i++){
            cin>>u[i]>>v[i]>>w[i];
            addedge(u[i], v[i], w[i]);
        }
        dij();
        for(int i=1; i<=n; i++) ans[i] = dis[i];
        cls(head, -1), tot = 0;
        for(int i=1; i<=m; i++){
            addedge(v[i], u[i], w[i]);
        }
        dij();
        for(int i=1; i<=n; i++) ans[i] += dis[i];
        int mx = -1;
        for(int i=1; i<=n; i++) mx = max(mx, ans[i]);
        cout<<mx<<endl;
    }
    return 0;
}

跑步

自己的转移状态多，然后就疯狂wa,感觉还有些细节没有想清楚。

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<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
int dp[10000+10][500+10];
bool is[10000+10][500+10];
int n, m;
int a[10000+10];
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
        cls(dp, 0);
        for(int i=1; i<=n; i++) cin>>a[i];
        //for(int i=1; i<=n; i++) dp[i][0] = a[i];
        for(int i=1; i<=n; i++){
            dp[i][0] = dp[i-1][0];
            for(int j=1; j<=m; j++){
                if(i-j>=0) dp[i][0] = max(dp[i][0], dp[i-j][j]);
                dp[i][j] = dp[i-1][j-1]+a[i];
            }
        }
        cout<<dp[n][0]<<endl;
    }
    return 0;
}

热血斗兽场

我很sb, 中途中断的时候忘记insert了。。。而且没有给战斗的数值很坑，以为1e9是最大的。。。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int n;
struct Node{
    int id, val;
    bool operator <(const Node &b) const{
        return val<b.val;
    }
    Node(int _id, int _val):id(_id), val(_val){}
    Node (){}
};
set<Node> s;
int main(){
    ios::sync_with_stdio(false);
    scanf("%d", &n);
    Node temp;
    //cin>>temp.id>>temp.val;
    scanf("%d%d", &temp.id, &temp.val);
    cout<<temp.id<<" "<<1<<endl;
    //printf("%d %d\n", temp.id, temp.val);
    s.insert(Node(1, 1000000000));
    s.insert(temp);
    set<Node>::iterator it;
    for(int i=2; i<=n; i++){
        //cin>>temp.id>>temp.val;
        scanf("%d%d", &temp.id, &temp.val);
        //s.insert(temp);
        int idx1, idx2;
        it = s.upper_bound(temp);
        if(it == s.begin()){
            //cout<<temp.id<<" "<<s.begin()->id<<endl;
            printf("%d %d\n", temp.id, s.begin()->id);
            //这边忘记insert了
            s.insert(temp);
            continue;
        }
        if(it == s.end()){
            it = s.end();it--;
            //cout<<temp.id<<" "<<it->id<<endl;
            printf("%d %d\n", temp.id, it->id);
            s.insert(temp);
            continue;
        }
        //cout<<"haha"<<endl;
        int a1 = (prev(s.lower_bound(temp)))->val;
        idx1  = prev(s.lower_bound(temp))->id;
        int a2 = (s.upper_bound(temp))->val;
        idx2 = (s.upper_bound(temp))->id;
        //cout<<"test "<<a1<<" "<<a2<<" "<<idx1<<" "<<idx2<<endl;
        if(abs(a1-temp.val)<abs(a2-temp.val)){
            //cout<<temp.id<<" "<<idx1<<endl;
            printf("%d %d\n", temp.id, idx1);
        }
        else if(abs(a1-temp.val)>abs(a2-temp.val)){
            //cout<<temp.id<<" "<<idx2<<endl;
            printf("%d %d\n", temp.id, idx2);
        }
        else {
            //cout<<temp.id<<" "<<idx1<<endl;
            printf("%d %d\n", temp.id, idx1);
        }
        s.insert(temp);
    }
    return 0;
}

有正负的背包

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
int num[10];
int dp[maxn];
int main(){
    ios::sync_with_stdio(false);
    int _;
    scanf("%d", &_);
    while(_--){
        for(int i=1; i<=6; i++) scanf("%d", &num[i]);
        for(int i=1; i<=2000; i++) dp[i] = inf;
        dp[0] = 0;
        for(int i=1; i<=6; i++){
            for(int j=num[i]; j<=2000; j++){
                dp[j] = min(dp[j], dp[j-num[i]]+1);
            }
        }
        for(int i=1; i<=6; i++){
            for(int j=2000-num[i]; j>=1; j--){
                dp[j] = min(dp[j], dp[j+num[i]]+1);
            }
        }
        int ans = 0;
        for(int i=1; i<=6; i++){
            for(int j=num[i]; j<=2000; j++){
                dp[j] = min(dp[j], dp[j-num[i]]+1);
            }
        }
        int mx = -1;
        for(int i=1;i<=100; i++){
            mx = max(mx, dp[i]);
            ans += dp[i];
        }
        printf("%.2lf %d\n", double(ans)/100.0, mx);
    }
    return 0;
}

逆序对

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 5e5+10;
ll num[maxn];
ll temp[maxn<<1];
int n;
ll ans = 0;
void mer(ll *s, ll *temp, int l, int r){
    int mid = (l+r)/2;
    int i=l, j=mid+1, k=l;
    int point = l;
    while(i<=mid&&j<=r){
        if(s[i]>s[j]){
            temp[k] = s[j];
            while(s[point]<=s[j]&&point<=mid){
                point++;
            }
            if(point!=mid+1){
                ans+=mid-point+1;
            }
            j++;
        }
        else{
            temp[k] = s[i];
            i++;
        }
        k++;
    }
    while(i<=mid){
        temp[k++] = s[i++];
    }
    while(j<=r){
        temp[k++] = s[j++];
    }
    for(int i=l; i<=r; i++){
        s[i] = temp[i];
    }
}
void mergesort(ll *s, ll *temp, int l, int r){
    int mid = (l+r)/2;
    if(l<r){
        mergesort(s, temp, l, mid);
        mergesort(s, temp, mid+1, r);
        mer(s, temp, l, r);
    }
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n){
    if(n == 0) break;
    ans = 0;
    for(int i=1; i<=n; i++) cin>>num[i];
    mergesort(num, temp, 1, n);
    cout<<ans<<endl;
    }
    return 0;
}

未解决的问题

本文标题:练习

文章作者:Babydragon

发布时间:2019-06-28, 10:15:21

最后更新:2019-07-05, 00:09:58

原始链接:http://baolintian.github.io/2019/06/28/练习/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 肿瘤检测
  2. 2. railway station (DP)
  3. 3. prime path
  4. 4. list 的模拟
  5. 5. 打印三角形
  6. 6. 麦森数
  7. 7. 集合问题
  8. 8. 最大子矩阵的求法
  9. 9. Q：那么最大矩形是怎么维护的？
  10. 10. 多重背包的二进制优化
  11. 11. 最短路+限制条件
  12. 12. 前缀式的计算
  13. 13. 中缀式转换为后缀式
  14. 14. 真实排名
  15. 15. 任务排序
  16. 16. 中位数
  17. 17. 多组数据的二分图。。。
  18. 18. 完美覆盖
  19. 19. 特殊密码锁
  20. 20. 矩形切割，最大面积最小
  21. 21. 雷涛的猫
  22. 22. 取石子游戏
  23. 23. 分割矩形使得均方差最小
  24. 24. LIS(nlogn)做法
  25. 25. 差分约束系统+堆优化
  26. 26. 解方程
  27. 27. EXCHANGE RATE
  28. 28. divisible
  29. 29. silver cow
  30. 30. 跑步
  31. 31. 热血斗兽场
  32. 32. 有正负的背包
  33. 33. 逆序对
  34. 34. 未解决的问题
{{ live2d() }}