2018 Multi-University Training NOWCODER

Posted on | In , | Visitors:

嚯嚯嚯！补题！补题！补题！

铺天盖地的补题！

因为会做的太少了呀！

唔，Weibo害死人！

2018 Multi-University Training NOWCODER

Contest 7

补题：4题

A. Minimum Cost Perfect Matching

与运算，要让数字最小，则将有1的和无1的进行抵消

1
2
3
4
5
6
7
8
 000000……000
 ……
 111111……110
 111111……111
 ------------------
1000000……000
1000000……001
……

将对称的部分分别匹配，然后就缩小了范围，继续匹配即可

注意边界即可

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>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX = 5e5 + 5;
int n, a[MAX];
bool cmp(int a, int b) {
    return a > b;
}
void deal(int l, int r) {
    int now = 1;
    if (r == l) return ;
    while ((1<<(now+1)) <= r + 1) ++now;
    int len = r - ((1<<now) - 1);
     
    if (len != 0)   sort(a + r - 2 * len + 1, a + r + 1, cmp);
    if (len == 0)   {
        sort(a, a + r + 1, cmp);
        return ;
    }
    deal(0, r - 2 * len);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) a[i] = i;
    deal(0, n - 1);
    for (int i = 0; i < n - 1; ++i) printf("%d ", a[i]);
    printf("%d\n", a[n - 1]);
    return 0;
}

题解里说的是

当n是2的次幂的时候，非常简单p[i]=n-1-i即可。

否则，设b为<=n最大的2的次幂，对于b <= x < n，交换x和x-b，分别求两边的最优解。

1
2
3
4
5
6
7
8
9
n = 11，初始为 0, 1, 2 ,3, 4, 5, 6, 7, 8, 9, 10
• 取b为8，开始交换 8, 9, 10, 3, 4, 5, 6, 7 / 0, 1, 2
• 取b为2，开始交换 8, 9, 10, 3, 4, 5, 6, 7 / 2, 1 / 0
• 翻转每段得到
• 7, 6, 5, 4, 3, 10, 9, 8 / 1, 2 / 0

I. Sudoku Subrectangles

和题解的思路一样：

• 子矩形最多52行，52列。

• 一个$5252nm$的做法是显然的（可以优化到$52n*m$）【思考中】

• 枚举上下边界（最多差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
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
#include <algorithm>
using namespace std;
typedef long long ll;
ll letter[130];
void pretreatment() {
    ll now = 1;
    for (char c = 'a'; c != 'z'; ++c) {
        letter[c] = 1LL<<now;
        ++now;
    }
    for (char c = 'A'; c != 'Z'; ++c) {
        letter[c] = 1LL<<now;
        ++now;
    }
}
const int MAX = 1e3 + 5;
int row, col, up[MAX][MAX], vis[130], finalUp[MAX][MAX],Left[MAX][MAX],finalLeft[MAX][MAX];
char G[MAX][MAX];
int len[100];
void input() {
    scanf("%d%d", &row, &col);
    for (int i = 0; i < row; ++i) {
        scanf("%s", G[i]);
    }
    //deal with 'Left'
    for (int i = 0; i < row; ++i) {
        memset(vis, 0, sizeof(vis));
        for (int j = 0; j < col; ++j) {
            if (!vis[G[i][j]]) {
                vis[G[i][j]] = j + 1;
            } else {
                Left[i + 1][j + 1] = vis[G[i][j]];
                vis[G[i][j]] = j + 1;
            }
        }
    }
    
    //deal with 'finalLeft'
    char c;
    for (int i = 0; i < row; ++i) {
        memset(vis, 0, sizeof(vis));
        for (int j = 0; j < col; ++j) {
            c = G[i][j];
            if (!vis[c]) {
                vis[c] = 1;
                finalLeft[i + 1][j + 1] = finalLeft[i + 1][j] + 1;
            } else {
                finalLeft[i + 1][j + 1] = min(finalLeft[i + 1][j]+1,j+1-Left[i+1][j+1]);
            }
        }
    }
    //deal with 'up'
    for (int j = 0; j < col; ++j) {
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < row; ++i) {
            if (!vis[G[i][j]]) {
                vis[G[i][j]] = i + 1;
            } else {
                up[i + 1][j + 1] = vis[G[i][j]];
                vis[G[i][j]] = i + 1;
            }
        }
    }
    //deal with 'finalUp'
    for (int j = 0; j < col; ++j) {
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < row; ++i) {
            c = G[i][j];
            if (!vis[c]) {
                vis[c] = 1;
                finalUp[i + 1][j + 1] = finalUp[i][j + 1] + 1;
            } else {
                finalUp[i + 1][j + 1] = min(finalUp[i][j + 1]+1,i+1-up[i+1][j+1]);
            }
        }
    }
}
long long ans = 0;
void solve() {
    for (int j = 1;j <= col; ++j) {
        memset(len, 0, sizeof(len));
        for (int i = 1; i <= row; ++i) {
            //向左延伸
            for(int k=0;k<finalLeft[i][j]&&k<52;k++){
                len[k]=min(finalUp[i][j-k],len[k]+1);
                if(k) len[k]=min(len[k],len[k-1]);
                ans+=len[k];
            }
            for(int k=finalLeft[i][j];k<52;k++)
                len[k]=0;
        }
    }
}
int main() {
    pretreatment();
    input();
    solve();
    printf("%lld\n",ans);
    
    return 0;
}

C. Bit Compression

暴力是3e8的，只需稍稍优化即可！（emmm……压根儿就没算3^18是多少

以为要建树呢！

直接暴力map也可，因为map会可以将重复的部分合在一起；

同时注意这种卡常的题目，输入输出用上printf比较好（看群里有说实际上加上ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);会加快速度；同时如果在cout语句中不用endl的时候，而是用上cout<<'\n';，那么速度可能比printf更快呢！

于是卡过了

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
#include<bits/stdc++.h>
using namespace std;
map<string,int> mp[20];
map<string,int>::iterator it;
int main(){
    int n,num,len;
    string s,sa,sb,sc;
    cin>>n>>s;
    mp[n][s]=1;
    for(int i=n;i>=1;i--){
        for(it=mp[i].begin();it!=mp[i].end();it++){
            s=it->first;
            num=it->second;
            len=1<<i;
            sa=sb=sc="";
            for(int j=0;j<len;j+=2){
                sa+=((s[j]-'0')&(s[j+1]-'0'))+'0';
                sb+=((s[j]-'0')^(s[j+1]-'0'))+'0';
                sc+=((s[j]-'0')|(s[j+1]-'0'))+'0';
            }
            mp[i-1][sa]+=num;
            mp[i-1][sb]+=num;
            mp[i-1][sc]+=num;
        }
    }
    cout<<mp[0]["1"]<<'\n';
    return 0;
}

E. Counting 4-Cliques

郁闷！【快成怨妇了】

构造一个完全图，然后外面五个点，分别和完全图相连的点有x1,x2,x3,x4,x5个，且这五条边格子不相连

至于为什么五个，第一种猜呀！C(70,4)是一个节点，多出5个干什么呢？嗯，第二种打表！其他倒是不知道了！

之后通过枚举x1,x2,x3,x4,看x5是否可行

原理是相同的

先放一份56%的代码，不明白哪里错了【之后继续调试吧！

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll>CT4;
vector<ll>CT3;
ll Ct4(int t){
    if(t<4) return 0;
    ll ans=1LL*t*(t-1)*(t-2)*(t-3)/24;
    return ans;
}
ll Ct3(int t){
    if(t<3) return 0;
    ll ans=1LL*t*(t-1)*(t-2)/6;
    return ans;
}
 
void Print(int t,int x1,int x2,int x3,int x4,int x5){
    //    cout<<t<<" "<<x1<<" "<<x2<<" "<<x3<<" "<<x4<<" "<<x5<<endl;
    int m=t;
    if(x1) m++;if(x2) m++; if(x3) m++;if(x4) m++; if(x5) m++;
    int mm=t*(t-1)/2+x1+x2+x3+x4+x5;
    printf("%d %d\n",m,mm);
     
    //完全图
    for(int i=1;i<=t;i++){
        for(int j=i+1;j<=t;j++){
            printf("%d %d\n",i,j);
        }
    }
     
    //剩余元素
    int idx=1;
    while(x1--){
        printf("%d %d\n",t+1,idx);
        idx++;
    }
    idx=1;
    while(x2--){
        printf("%d %d\n",t+2,idx);
        idx++;
    }
    idx=1;
    while(x3--){
        printf("%d %d\n",t+3,idx);
        idx++;
    }
    idx=1;
    while(x4--){
        printf("%d %d\n",t+4,idx);
        idx++;
    }
    idx=1;
    while(x5--){
        printf("%d %d\n",t+5,idx);
        idx++;
    }
}
 
int main(){
    //预打表，处理CT4
    for(int i=4;i<=75;i++){
        CT4.push_back(Ct4(i));
    }
     
    int n;scanf("%d",&n);
    int t=0;ll now=0;
    for(int i=4;i<=75;i++){
        if(CT4[i-4]<=n){
            t=i;
            now=CT4[i-4];
        }
        else break;
    }
     
    if(now==n){
        Print(t, 0, 0, 0, 0, 0);
        return 0;
    }
     
    CT3.push_back(0);
    for(int i=3;i<=t;i++)
        CT3.push_back(Ct3(i));
     
    int len=CT3.size();
     
    //    for(int i=0;i<len;i++)
    //        cout<<CT3[i]<<endl;
     
    ll tmp;
    for(int x1=len-1;x1>=0;x1--){
        tmp=now+CT3[x1];
        if(tmp>n) continue;
         
        if(tmp==n){
            Print(t, x1+2, 0, 0, 0, 0);
            return 0;
        }
        for(int x2=len-1;x2>=0;x2--){
            if(tmp+CT3[x2]>n) continue;
            tmp+=CT3[x2];
            if(tmp==n){
                Print(t, x1+2, x2+2, 0, 0, 0);
                return 0;
            }
            for(int x3=len-1;x3>=0;x3--){
                if(tmp+CT3[x3]>n) continue;
                tmp+=CT3[x3];
                if(tmp==n){
                    Print(t, x1+2, x2+2, x3+2, 0, 0);
                    return 0;
                }
                for(int x4=len-1;x4>=0;x4--){
                    if(tmp+CT3[x4]>n) continue;
                    tmp+=CT3[x4];
                    if(tmp==n){
                        Print(t, x1+2, x2+2, x3+2, x4+2, 0);
                        return 0;
                    }
                     
                    int l=0,r=len-1;
                    while(l<=r){
                        int mid=(l+r)/2;
                        if(tmp+CT3[mid]>n){
                            r=mid-1;
                        }else if(tmp+CT3[mid]<n){
                            l=mid+1;
                        }else{
                            Print(t, x1+2, x2+2, x3+2, x4+2, mid+2);
                            return 0;
                        }
                    }
                }
            }
        }
    }
    return 0;
}

AC代码
只是main函数变了，所以问题还在main里

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 <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
map<ll,int>CT3;
ll Ct4(int t){
    if(t<4) return 0;
    ll ans=1LL*t*(t-1)*(t-2)*(t-3)/24;
    return ans;
}
ll Ct3(int t){
    if(t<3) return 0;
    ll ans=1LL*t*(t-1)*(t-2)/6;
    return ans;
}
 
void Print(int t,int x1,int x2,int x3,int x4,int x5){
    //    cout<<t<<" "<<x1<<" "<<x2<<" "<<x3<<" "<<x4<<" "<<x5<<endl;
    int m=t;
    if(x1) m++;if(x2) m++; if(x3) m++;if(x4) m++; if(x5) m++;
    int mm=t*(t-1)/2+x1+x2+x3+x4+x5;
    printf("%d %d\n",m,mm);
     
    //完全图
    for(int i=1;i<=t;i++){
        for(int j=i+1;j<=t;j++){
            printf("%d %d\n",i,j);
        }
    }
     
    //剩余元素
    int idx=1;
    while(x1--){
        printf("%d %d\n",t+1,idx);
        idx++;
    }
    idx=1;
    while(x2--){
        printf("%d %d\n",t+2,idx);
        idx++;
    }
    idx=1;
    while(x3--){
        printf("%d %d\n",t+3,idx);
        idx++;
    }
    idx=1;
    while(x4--){
        printf("%d %d\n",t+4,idx);
        idx++;
    }
    idx=1;
    while(x5--){
        printf("%d %d\n",t+5,idx);
        idx++;
    }
}
 
int main(){
    for(int i=2;i<=100;i++)
        CT3[Ct3(i)]=i;
     
    int n;scanf("%d",&n);
    int t=4; int c=70;
    while((t+1)<=70&&Ct4(t+1)<=n){
        t++;
    }
    ll now=Ct4(t);
    int x5=-1;
    for(int x1=t;x1>=2;x1--){
        for(int x2=t;x2>=2;x2--){
            for(int x3=t;x3>=2;x3--){
                for(int x4=t;x4>=2;x4--){
                    ll tmp=Ct3(x1)+Ct3(x2)+Ct3(x3)+Ct3(x4);
                    if(tmp<=n-now&&CT3[n-now-tmp]>=2&&CT3[n-now-tmp]<=t){
                        x5=CT3[n-now-tmp];
                        Print(t, x1, x2, x3, x4, x5);
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}

碎碎念

2018.08.09 晚

学军中学，牛逼！

果然杭城第二呀！

2018.08.10

忘记第一时间抢沙发了

我怕是个假粉吧！💚💚💚💚

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽