ECNU Algorithm 总结

ECNU“算法设计与分析”课程OJ平台题解及总结。

以下各图片均来源于：https://acm.ecnu.edu.cn/

A.框体排列

ecnu_A

简单题，贪心模拟即可，注意坐标需要预先排序。

 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>
#include <vector>
using namespace std;
int main()
{
    // greedy
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    int res = 1;
    int last = v[0];
    for (int i = 1; i < n; i++)
    {
        if (v[i] - last <= k)
        {
            continue;
        }
        res++;
        last = v[i];
    }
    cout << res << endl;
    return 0;
}

时间复杂度：O(n)
空间复杂度：O(1)

B. 整数排序

ecnu_B

定义为字符串类型，重定义排序规则连接即可。

 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


#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool cmp(string a, string b)
{
    return a + b > b + a;
}
int main()
{
    int n;
    cin >> n;
    vector<string> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    sort(v.begin(), v.end(), cmp);
    string res;
    for (int i = 0; i < n; i++)
    {
        res += v[i];
    }
    if (res[0] == '0')
    {
        cout << 0 << endl;
        return 0;
    }
    cout << res << endl;
    return 0;
}

时间复杂度：O(nlogn)
空间复杂度：O(nlogn)

C. 选择排序（构造）

https://acm.ecnu.edu.cn/problem/3607/

ecnu_C

其实很简单的一道题，但那天中午脑子不清醒。N定义为10^5+5是对的。输出应该为[N,1]或[N-1,0]，但这么简单就是写错了，WA了还以为要多巧妙的构造，就是没仔细检查自己的代码。问了新同学，问问题的过程中发现了错误。不过，因此认识了很多人：该同学、老师、其他同学，一切好像是有缘分在的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int main()
{
    cout << N << endl;
    for (int i = N; i >= 1; i--)
        cout << i << " ";
    cout << endl;
    return 0;
}

D. 合并果子

ecnu_D

最小堆的应用。

 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 <queue>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int num;
    priority_queue<int,vector<int>,greater<int>> q;
    for(int i=0;i<n;i++){
        cin >> num;
        q.push(num);
    }
    int res=0;
    while(q.size()>=2){
        int a=q.top();
        q.pop();
        int b=q.top();
        q.pop();
        q.push(a+b);
        res+=a+b;
    }
    cout << res;
    return 0;
}

时间复杂度：O(n)
空间复杂度：O(n)

E. 差分计数

ecnu_E

1、这题要特别注意输入数值范围：

x和a都是[-2*10^6,2*10^6]

用map会超时，因为底层是红黑树，插入是O(nlogn)。所以开数组作哈希表，但是输入的整数x可能为负数，可以加一个大数将数整体右移映射，因此数组至少开原来范围的2倍以上。

2、0的特殊情况。

因为这里是有序对 (i,j) 个数。没有说下标i和j的大小关系，当x为0时，即可能有i=j i>j i<j共3种情况。

例如：

input:

2 0 1 1

output:

4

有序对为: (0,0) (0,1) (1,0) (1,1)

input:

4 0

1 1 1 1

output:

16

 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


#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int M=3e6;
const int N=6e6;
static int read() {
  int x = 0, w = 1;
  char c = 0;
  while (c < '0' || c > '9') {
    if (c == '-') w = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + (c - '0');
    c = getchar();
  }
  return x * w;
}
int main()
{
    int n=read();
    int x=read();
    x=abs(x);
    vector<long long> a(N,0);
    long long res=0;
    for(int i=0;i<n;i++){
        int num=read();
        a[num+M]+=1;
    }
    if(x==0){
        for(int i=0;i<N;i++){
            if(a[i]==0) continue;
            res+=a[i]*a[i];
        }
    }else{
        for(int i=0;i<N-x;i++){
            res+=a[i]*a[i+x];
        }
    }
    printf("%lld",res);
    return 0;
}

时间复杂度：O(N)
空间复杂度：O(N)

F.制作菜肴

ecnu_F

做题时自己写的test case:

input:

4 4

2 3 4 5

4 2 1 3

3 4 5 2

1 2 3 4

output:

0 0 0 0

0 150 240 0

0 80 160 0

0 0 0 0

很容易看懂的一道题，但刚开始使用什么数据结构如何实现这个过程还是修修改改了几遍，最终思路清晰起来，只要从4个方向遍历即可。写出来下面这个版本，因为数据存储使用了int一直WA，也是请教了同学后改为long才AC的。

ecnu_F2

算是刷LeetCode刷出来的解法：为了不发生越界错误，在四周多加了一层数据-1便于比较大小，因为T是在[1,10^4]之间。

看了那位同学的代码，发现厉害的人的确厉害，思维严谨。他为了越界错误，是分情况讨论的，但他在前一晚很短时间内就完成代码AC了。虽然一直在劝自己对高学历祛魅，高学历!=一切，但是值得从身边不同的人学习。比如这种严谨（真的很想强调这个严谨，目前认识人里最严谨的了，之前认识常春藤本硕的都没这么严谨）和认真。本来就和STJU的基础有差，然后别人又都在很拼，如果我再不努力，日积月累别说缩小差距了，只会越来越大。

P.S. 回去翻聊天记录真的想骂死自己😅，总算是知道了有些人的聊天记录是应该多看几遍的。自己还在这振振有词地总结自己的错误，殊不知人家早就给出了答案（看聊天记录的时间就知道了）。还WA了好几遍发了好几次代码截图过去又请教，果然基础差的我是无知的。

ecnu_F3

 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


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    vector<vector<long>> v(n+1,vector<long>(m+1,-1));
    vector<vector<long>> top_left(n+2,vector<long>(m+2,-1)),
    bottom_left(n+2,vector<long>(m+2,-1)),
    top_right(n+2,vector<long>(m+2,-1)),
    bottom_right(n+2,vector<long>(m+2,-1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%ld",&v[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            top_left[i][j]=max({top_left[i-1][j],top_left[i][j-1],v[i][j]});
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){
            top_right[i][j]=max({top_right[i-1][j],top_right[i][j+1],v[i][j]});
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            bottom_left[i][j]=max({bottom_left[i][j-1],bottom_left[i+1][j],v[i][j]});
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=m;j>=1;j--){
            bottom_right[i][j]=max({bottom_right[i+1][j],bottom_right[i][j+1],v[i][j]});
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j==m){
                printf("0");
            }else if(i==1 || j==1 || i==n){
                printf("0 ");
            }else{
                cout << top_left[i-1][j-1]*
                top_right[i-1][j+1]*
                bottom_left[i+1][j-1]*
                bottom_right[i+1][j+1] << " ";
            }
        }
        printf("\n");
    }
    return 0;
}

时间复杂度：O(nm)
空间复杂度：O(nm)

G. 箱子打包

ecnu_G

贪心算法。

 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 <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n,l;
    cin >> n >> l;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin >> v[i];
    }
    sort(v.begin(),v.end(),[](int a,int b){
        return a>b;
    });
    int left=0,right=n-1;
    int res=0;
    while(left<=right){
        if(v[left]+v[right]<=l){
            res+=1;
            left++;
            right--;
        }else{
            res+=1;
            left++;
        }
    }
    cout << res;
    return 0;
}

时间复杂度：O(nlogn)
空间复杂度：O(nlogn)

H. 大鱼吃小鱼

ecnu_H

这题重点在于吃鱼顺序，即排序方法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


bool cmp(node x,node y){
    if(x.a>0 && y.a>0){
        //positive w小
        return x.w<y.w;
    }else if(x.a<0 && y.a<0){
        //negative w+a大
        return x.w+x.a>y.w+y.a;
    }else{
        //start from positive a to negative a
        return x.a>y.a;
    }
}

w+a排序举例：

[(7.-2), (8,-6)]，此时先吃7（需要初值10）比先吃8（需要初值13）更好。

 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 <vector>
#include <algorithm>
#include <limits.h>
#include <unordered_set>
using namespace std;
struct node{
    long long w,a;
};
bool cmp(node x,node y){
    if(x.a>0 && y.a>0){
        //positive w小
        return x.w<y.w;
    }else if(x.a<0 && y.a<0){
        //negative w+a大
        return x.w+x.a>y.w+y.a;
    }else{
        //start from positive a to negative a
        return x.a>y.a;
    }
}
int main()
{
    long long n;
    scanf("%lld",&n);
    vector<node> wa(n);
    for(int i=0;i<n;i++){
        scanf("%lld %lld",&wa[i].w,&wa[i].a);
    }
    sort(wa.begin(),wa.end(),cmp);
    // for(int i=0;i<n;i++){
    //     cout << wa[i].w << " " << wa[i].a << endl;
    // }
    long long res=1;
    long long sum=0;
    long long size=1;
    for(int i=0;i<n;i++){
        //任何时刻都要保证鱼的大小是正整数。
        if(size>wa[i].w){
            sum=0;
            size+=wa[i].a;
        }else{
            sum=wa[i].w-size;
            size=wa[i].w+wa[i].a;
        }
        if(size<=0){
            sum+=(1-size);
            size=1;
        }
        res+=sum;
    }
    printf("%lld",res);
    return 0;
}

时间复杂度：O(nlogn)
空间复杂度：O(nlogn)

I. 离线缓存

ecnu_I

debug了好多次，每次好几个小时的一道题。之前学OS的时候没发现这个知道未来情况的算法有多难，这道题倒是体会了。

其实每道题都应该：先有一个准确思路——>根据思路写代码——>完善细节。

 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


#include <iostream>
#include <queue>
#include <map>
#include <set>
using namespace std;
map<int, int> mp, flag, nxt;
int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    vector<int> v(n+1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &v[i]);
    }
    for (int i = n; i >= 1; i--)
    {
        if (mp.count(v[i]))
        {
            nxt[i] = mp[v[i]];
        }
        else
        {
            nxt[i] = n + 1;
        }
        mp[v[i]] = i;
    }
    set<pair<int, int> > cache;
    int res = 0;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (flag[v[i]])
        {
            // found, update
            auto it = cache.lower_bound(make_pair(i, v[i]));
            auto temp = *it;
            cache.erase(it);
            temp.first = nxt[i];
            cache.insert(temp);
            continue;
        }
        flag[v[i]] = 1;
        cnt++;
        res++;
        cache.insert(make_pair(nxt[i], v[i]));
        if (cnt > k)
        {
            cnt--;
            flag[(--cache.end())->second] = 0;
            cache.erase(--cache.end());
        }
    }
    printf("%d", res);
    return 0;
}

时间复杂度：O(n)
空间复杂度：O(n)

J. 糖果

ecnu_J

brute-force

60'

 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 <iostream>
#include <algorithm>
#include<vector>
using namespace std;
//a-b:x
//60‘
const int N=1e5+5;
struct node{
    int x,a,b;
}v[N];
int res[N];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    int x,a,b;
    //20' runtime error: SIGSEGV
    // vector<node> v(n+1);
    for(int i=1;i<=k;i++){
        scanf("%d%d%d",&v[i].x,&v[i].a,&v[i].b);
    }
    // vector<int> res(n+1,1);
    //greedy
    for(int i=1;i<=n;i++){
        res[i]=1;
    }
    for(int k=0;k<250;k++){
        for(int i=1;i<=k;i++){
            switch(v[i].x){
                case 1:
                if(res[v[i].a]>res[v[i].b]) res[v[i].b]=res[v[i].a];
                else res[v[i].a]=res[v[i].b];
                break;
                case 2:
                if(res[v[i].a]>=res[v[i].b]) res[v[i].b]=res[v[i].a]+1;
                break;
                case 3:
                if(res[v[i].a]<res[v[i].b]) res[v[i].a]=res[v[i].b];
                break;
                case 4:
                if(res[v[i].a]<=res[v[i].b]) res[v[i].a]=res[v[i].b]+1;
                break;
                case 5:
                if(res[v[i].a]>res[v[i].b]) res[v[i].b]=res[v[i].a];
                break;
            }
        }
    }
    for(int i=1;i<=k;i++){
        if(v[i].x==1){
            if(res[v[i].a]>res[v[i].b]){
                cout << "-1";
                return 0;
            }
        }else if(v[i].x==2){
            if(res[v[i].a]>=res[v[i].b]){
                cout << "-1";
                return 0;
            }
        }else if(v[i].x==3){
            if(res[v[i].a]<res[v[i].b]){
                cout << "-1";
                return 0;
            }
        }else if(v[i].x==4){
            if(res[v[i].a]<=res[v[i].b]){
                cout << "-1";
                return 0;
            }
        }else if(v[i].x==5){
            if(res[v[i].a]>res[v[i].b]){
                cout << "-1";
                return 0;
            }
        }
    }
    long long ans=0;
    for(int i=1;i<=n;i++){
        ans+=res[i];
    }
    cout << ans;
    return 0;
}

SPFA

 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 <iostream>
#include <algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=1e7+5;
struct node{
    int from,to;
    int w;
    int next;
}v[N];
int head[N],vis[N],dis[N],tot[N];
queue<int> q;
int n,k;
int t;
void add(int a,int b,int x){
    v[++t].from=a;
    v[t].to=b;
    v[t].w=x;
    v[t].next=head[a];
    head[a]=t;
}
void SPFA(){
    vis[0]=1;
    q.push(0);
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        vis[cur]=0;
        if(tot[cur]==n-1){
            cout << -1;
            exit(0);
        }
        tot[cur]++;
        for(int i=head[cur];i;i=v[i].next){
            int temp=v[i].to;
            if(dis[temp]<dis[cur]+v[i].w){
                dis[temp]=dis[cur]+v[i].w;
                if(!vis[temp]){
                    vis[temp]=1;
                    q.push(temp);
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    int x,a,b;
    for(int i=1;i<=k;i++){
        scanf("%d%d%d",&x,&a,&b);
        if(x==1){
            add(a,b,0);
            add(b,a,0);
        }else if(x==2){
            if(a==b){
                cout << -1;
                return 0;
            }
            add(a,b,1);
        }else if(x==3){
            add(b,a,0);
        }else if(x==4){
            if(a==b){
                cout << -1;
                return 0;
            }
            add(b,a,1);
        }else if(x==5){
            add(a,b,0);
        }
    }
    for(int i=n;i>=1;i--){
        add(0,i,1);
    }
    SPFA();
    long long res=0;
    for(int i=1;i<=n;i++){
        res+=dis[i];
    }
    cout << res;
    return 0;
}

K. 工具人

ecnu_K

注意：

n: [1,10^6]

a: [0,10^9] 所以刚开始是没有负值的。

 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


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long res,avg;
int main()
{
    int n;
    scanf("%d",&n);
    vector<long long> a(n),b(n);
    for(int i=0;i<n;i++){
        scanf("%lld",&a[i]);
        avg+=a[i];
    }
    if(avg%n!=0){
        printf("-1");
        return 0;
    }
    avg/=n;
    for(int i=0;i<n;i++){
        b[i]=a[i]-avg;
    }
    long long neg_max=0,pos_max=0,sum=0;
    for(int i=0;i<n;i++){
        sum+=b[i];
        if(sum<0 && sum<neg_max){
            neg_max=sum;
        }
        if(sum>0 && sum>pos_max){
            pos_max=sum;
        }
    }
    printf("%lld",abs(neg_max-pos_max));
    return 0;
}

举例：

input:

4

4 0 0 0

avg:1

b[i]=a[i]-avg: 3 -1 -1 -1

sum: 3 2 1 0

neg_max: 0

pos_max: 3

res:3

转换过程：

4 0 0 0

3 1 0 0

2 1 1 0

1 1 1 1

output: 3

input:

4

4 0 0 4

avg:2

b[i]=a[i]-avg: 2 -2 -2 2

sum: 2 0 -2 0

neg_max: -2

pos_max: 2

res:4

L. 数列极差

ecnu_L

优先队列（最大堆、最小堆）的应用。

 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 <queue>
#include <algorithm>
#include <queue>
using namespace std;
int main()
{
    int n;
    cin >> n;
    priority_queue<int,vector<int>,greater<int>> minHeap;
    priority_queue<int> maxHeap;
    int num;
    for(int i=0;i<n;i++){
        cin >> num;
        minHeap.push(num);
        maxHeap.push(num);
    }
    cin >> num;
    int m;
    int a,b;
    for(int i=0;i<n-1;i++){
        a=minHeap.top();
        minHeap.pop();
        b=minHeap.top();
        minHeap.pop();
        minHeap.push(a*b+1);
        
        a=maxHeap.top();
        maxHeap.pop();
        b=maxHeap.top();
        maxHeap.pop();
        maxHeap.push(a*b+1);
    }
    cout << abs(maxHeap.top()-minHeap.top());
    return 0;
}

时间复杂度：O(n)
空间复杂度：O(n)

发现对别人轻而易举很容易的事情，自己总要花很多时间掌握，总会解决的不是吗？也会后悔当时复试前摆烂没有好好刷ECNU OJ平台的题，在想当时努力刷题这次算法课练习会不会容易一些。真的好几道题花了好几次尝试解决，每次都是2小时起步，有天周日debug了一下午“离线缓存”也没有AC，导致那天心情特别低沉。想起之前看过的“当下的你逃避学习的时候，或许是未来的你在向你求救。”，每一份努力的确不会被辜负。清楚发现自己花的时间远远不够，所以真的再用心多动脑。任何困难也都会过去的。Never complain.

Table of Contents