nowcoder contest-5

ACM

nowcoder contest-5

E-room

题解

问的是最小的交换的人数，反问题就是最大能够不交换的人数。
然后就是很显然是一个二分图的问题。
感觉问题反向转化的思想很神奇，将复杂的问题化简。

ac code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2+10;
int x[maxn][4];
int y[maxn][4];
int n;
double eps = 1e-8;
const int INF = 1e9;
int love[maxn][maxn];   // 记录每个妹子和每个男生的好感度
int ex_girl[maxn];      // 每个妹子的期望值
int ex_boy[maxn];       // 每个男生的期望值
bool vis_girl[maxn];    // 记录每一轮匹配匹配过的女生
bool vis_boy[maxn];     // 记录每一轮匹配匹配过的男生
int match[maxn];        // 记录每个男生匹配到的妹子 如果没有则为-1
//double slack[MAXN];        // 记录每个汉子如果能被妹子倾心最少还需要多少期望值
bool dfs(int girl)
{
    vis_girl[girl] = true;
    for (int boy = 0; boy < n; ++boy) {
        if (vis_boy[boy]) continue; // 每一轮匹配 每个男生只尝试一次
        double gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];
        if (fabs(gap) <= eps) {  // 如果符合要求
            vis_boy[boy] = true;
            if (match[boy] == -1 || dfs( match[boy] )) {    // 找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
                match[boy] = girl;
                return true;
            }
        }
    }
    return false;
}
int  KM()
{
    memset(match, -1, sizeof(match));    // 初始每个男生都没有匹配的女生
    memset(ex_boy, 0, sizeof(ex_boy));   // 初始每个男生的期望值为0
    // 每个女生的初始期望值是与她相连的男生最大的好感度
    for (int i = 0; i < n; ++i) {
        ex_girl[i] = love[i][0];
        for (int j = 1; j < n; ++j) {
            ex_girl[i] = max(ex_girl[i], love[i][j]);
        }
    }
    // 尝试为每一个女生解决归宿问题
    for(int i = 0; i < n; ++i) {
        //fill(slack, slack + N, INF);    // 因为要取最小值 初始化为无穷大
        while (1) {
            // 为每个女生解决归宿问题的方法是 ：如果找不到就降低期望值，直到找到为止
            // 记录每轮匹配中男生女生是否被尝试匹配过
            memset(vis_girl, false, sizeof(vis_girl));
            memset(vis_boy, false, sizeof(vis_boy));
            if (dfs(i)) break;  // 找到归宿 退出
            // 如果不能找到 就降低期望值
            // 最小可降低的期望值
            int d = INF;
            for(int i=0; i<n; i++)if(vis_girl[i]){
                for(int j=0; j<n; j++){
                    if(!vis_boy[j]){
                        d = min(d, ex_girl[i]+ex_boy[j]-love[i][j]);
                    }
                }
            }
            for (int j = 0; j < n; ++j) {
                // 所有访问过的女生降低期望值
                if (vis_girl[j]) ex_girl[j] -= d;
                // 所有访问过的男生增加期望值
                if (vis_boy[j]) ex_boy[j] += d;
                // 没有访问过的boy 因为girl们的期望值降低，距离得到女生倾心又进了一步！
            }
        }
    }
    int ans = 0;
    for(int i=0; i<n; i++){
        ans+=(ex_boy[i]+ex_girl[i]);
    }
    return ans;
}
int cal(int* a, int *b){
    int ans = 0;
    for(int i=0; i<4; i++){
        for(int j=0; j<4; j++){
            if(a[i] == b[j]){
                ans++;
                break;
            }
        }
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n){
        for(int i=0; i<n; i++){
            cin>>x[i][0]>>x[i][1]>>x[i][2]>>x[i][3];
        }
        for(int i=0; i<n; i++){
            cin>>y[i][0]>>y[i][1]>>y[i][2]>>y[i][3];
        }
        int num;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                num = cal(x[i], y[j]);
                love[i][j] = num;
            }
        }
        int ans = KM();
        cout<<4*n-ans<<endl;
    }
    return 0;
}

F take

hdu 4417

hdu 4417 super mario

统计区间的小于等于某个数值的个数。
首先要对查询进行排序,区间值进行排序，然后对有贡献的进行统计。

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
int n, m;
int ans[maxn];
int c[maxn];
struct Node{
    int h, id;
}node[maxn];
struct Query{
    int l, r, h, id;
}qnode[maxn];
bool cmp1(Node a, Node b){
    return a.h<b.h;
}
bool cmp2(Query a, Query b){
    return a.h<b.h;
}
int lowbit(int x){
    return (x&(-x));
}
void add(int x, int val){
    while(x<=n){
        c[x] += val;
        x += lowbit(x);
    }
}
int query(int x){
    int ans = 0;
    while(x>0){
        ans+=c[x];
        x -= lowbit(x);
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    int kase = 0;
    while(t--){
        memset(c, 0, sizeof(c));
        cin>>n>>m;
        for(int i=1; i<=n; i++){
            cin>>node[i].h;
            node[i].id = i;
        }
        for(int i=1; i<=m; i++){
            cin>>qnode[i].l>>qnode[i].r>>qnode[i].h;
            //查询区间会从0开始，所以区间都要向右偏移1
            qnode[i].l++, qnode[i].r++;
            qnode[i].id = i;
        }
        sort(node+1, node+n+1, cmp1);
        sort(qnode+1, qnode+m+1, cmp2);
        int num = 1;
        for(int i=1, num=1; i<=m; i++){
            while(qnode[i].h>=node[num].h&&num<=n){
                add(node[num].id, 1);
                num++;
            }
            //区间右移一位
            ans[qnode[i].id] = query(qnode[i].r)-query(qnode[i].l-1);
        }
        cout<<"Case "<<++kase<<":"<<endl;
        for(int i=1; i<=m; i++){
            cout<<ans[i]<<endl;
        }
    }
    return 0;
}

小v的滑板鞋

注意数据范围，对一个变量进行大小的比较，对另外一个变量进行数量的统计(树状数组)。

ac code

max

结论： 相邻的两个数必然是互质的。

nth-number;

vcd

有四种情况：
对于|S|=1，他显然是好的
对于|S|=2，只要两个点的y 坐标不相同，那么这个集合也是好的
对于|S|=3，三个点的形状必须是< 型
对于|S|>3，不可能任何三个点都是< 型，所以一定不是好的
用树状数组统计一下就好了

题解

针对第三种情况，先对x进行排序，然后对y进行树状数组进行统计。
x相等的时候要进行相应的标记。

ac code

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 <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
typedef long long ll;
const int maxn = 1e5+10;
struct Node{
    int x, y;
}node[maxn];
int n;
int y[maxn];
ll c[maxn];
bool cmp(Node a, Node b){
    return a.x>b.x;
}
int lowbit(int x){
    return x&(-x);
}
void add(int x, int val){
    while(x<maxn){
        c[x] += val;
        x += lowbit(x);
    }
}
int query(int x){
    ll ans = 0;
    while(x>0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
int vis[maxn];
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n){
        memset(c, 0, sizeof(c));
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<n; i++){
            cin>>node[i].x>>node[i].y;
            y[i] = node[i].y;
        }
        sort(y, y+n);
        int mx = -1;
        for(int i=0; i<n; i++){
            node[i].y = lower_bound(y, y+n, node[i].y)-y+1;
            vis[node[i].y]++;
            mx = max(mx, node[i].y);
        }
        sort(node, node+n, cmp);
        ll ans = 0;
        ll shang,xia;
        ll tot;
        int pre = 0;
        for(int i=0; i<n; i++){
            tot = query(1e5);
            shang = tot - query(node[i].y);
            xia = query(node[i].y-1);
            ans = (ans+shang*xia%mod)%mod;
            if(node[i].x!=node[i+1].x){
                for(;pre<=i; pre++){
                    add(node[pre].y, 1);
                }
            }
        }
        ll ans1 = 0;
        for(int i=1; i<=mx; i++){
            ans1 += (n-vis[i])*vis[i];
        }
        ans1/=2;
        ans = (ans+n+ans1)%mod;
        cout<<ans<<endl;
    }
    return 0;
}

div pell方程

subsequence

可持久化线段树或者是树状数组来维护。

div

统计逆序对的个数。
这个逆序对有特殊的性质，因此分为两部分进行相应的统计

  1. 偶数之间的逆序对的个数
  2. 根据最佳的逆序对的个数进行相应的统计，小的偶数数字一定会放在大的偶数的后面，又因为奇数是按照顺序摆放的，因此只需要统计最大值和此时要插进去的偶数的差值的大小就行了。

ac code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
int a[maxn];
ll c[maxn];
int n;
int lowbit(int x){
    return x&-x;
}
void add(int x,int val){
    while(x<=n){
        c[x] += val;
        x += lowbit(x);
    }
}
int query(int x){
    int ans = 0;
    while(x>0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    priority_queue<int> pq;
    while(cin>>n){
        n /= 2;
        while(!pq.empty()) pq.pop();
        memset(c, 0, sizeof(c));
        for(int i=1; i<=n; i++){
            cin>>a[i];
            a[i] /= 2;
        }
        ll ans = 0;
        //统计偶数的逆序对的个数
        for(int i=1; i<=n; i++){
            add(a[i], 1);
            ans += i-query(a[i]);
        }
        for(int i=1; i<=n; i++){
            if(!pq.empty()&&pq.top()>a[i]){
                //根据最优的策略，必然是小数放在大数的后面的
                ans += pq.top()-a[i];
                pq.pop();
                //pq.push(a[i]);
            }
            pq.push(a[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

未解决的问题

本文标题:nowcoder contest-5

文章作者:Babydragon

发布时间:2018-08-02, 18:38:46

最后更新:2018-08-05, 09:46:54

原始链接:http://baolintian.github.io/2018/08/02/nowcoder-contest-5/

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

文章目录
  1. 1. E-room
    1. 1.1. 题解
    2. 1.2. ac code
  2. 2. F take
    1. 2.1. hdu 4417 super mario
    2. 2.2. 小v的滑板鞋
      1. 2.2.1. ac code
  3. 3. max
  4. 4. vcd
    1. 4.1. 题解
    2. 4.2. ac code
  5. 5. div pell方程
  6. 6. subsequence
  7. 7. div
    1. 7.1. ac code
  8. 8. 未解决的问题
{{ live2d() }}