codeforces 995 div3

A

题目

贪心，要使m-s差最大化，就让每个大于零的ai-b(i+1 )相加，并加上a[n-1]，就是最大值

代码

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 <bits/stdc++.h>
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int a[101],b[101],cache,n,sum=0;
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> cache;
            a[i]=cache;
        }
        for(int i=0;i<n;i++){
            cin >> cache;
            b[i]=cache;
        }
        for(int i=0;i<n-1;i++){
            int j = a[i]-b[i+1];
            if(j>0) sum+=j; 
        }
        cout << sum+a[n-1] << '\n';
    }
    return 0;
}

B

题目

这道题标签是binary二分，但是用二分完全是自讨苦吃，用整除与取模简单得多

3天一组，总路程/3天的路程算有几个完整的组，剩下一个组单独判断要几天

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
signed main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n,a,b,c,res,day=0;
        cin >> n >> a >> b >> c;
        int sum =a+b+c;
        day = 3*(n/sum);
        res = n-(n/sum)*sum;
        if(res!=0){
            if(res<=a) day++;
            else if(res<=a+b) day+=2;
            else day+=3;
        }
        cout << day << '\n';
    }
    return 0;
}

C

题目

模拟题。

两个特判：k<n-1，全部都不能过；k=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
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

const int maxn=3e5;
int lie[maxn+5];
bool bol[maxn+5];

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n,m,k,cache,unknown;
        memset(lie,0,maxn+5);
        memset(bol,0,maxn+5);
        cin >> n >> m >> k;
        for(int i=1;i<=m;i++){
            cin >> cache;
            lie[i]=cache;
        }
        for(int i=0;i<k;i++){
            cin >> cache;
            bol[cache]=1;
        }
        if(k<n-1){
            for(int i=0;i<m;i++) cout << 0;
            cout << '\n';
            continue;
        }
        if(k==n){
            for(int i=0;i<m;i++) cout << 1;
            cout << '\n';
            continue;
        }
        for(int i=1;i<=n;i++)
            if(!bol[i]){
                unknown=i;break;
            }
        for(int i=1;i<=m;i++)
            cout << (lie[i]==unknown ? 1:0);
        cout << '\n';
    }	
    return 0;
}

D

题目

给出一个序列，从序列中删除两个数后，剩下数的和在一个给定的区间内，问你一共可以删多少对这样的数？

先排序 ，便于二分

遍历序列中每个数，用二分找出它的另一半，如果满足条件，那么ans加上相应的值，这样做时间复杂度是O(N logN)，不会超

代码

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 <bits/stdc++.h>
#define int long long
#define check (sum-n1-x >= lie[l] && sum-n1-y <= lie[r]) 
using namespace std;

bool cpa(int a,int b){
    return a<b;
}//这个没必要写的，但是练习的时候可以写写练手感

vector <int> lie;

signed main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n,x,y,cache,sum=0,ans=0;
        lie.clear();
        cin >> n >> x >> y;
        for(int i=0;i<n;i++){
            cin >> cache;
            sum += cache;
            lie.push_back(cache);
        }
        sort(lie.begin(),lie.end(),cpa);
        vector<int>::iterator it;
        it=lie.begin()+1;
        for(int i=0;i<n;i++){
            int n1=lie[i],l,r;
            l=lower_bound(it,lie.end(),sum-n1-y)-lie.begin();
            r=upper_bound(it,lie.end(),sum-n1-x)-lie.begin()-1;
            if(check){
                ans+=r-l+1;
                //cout<<"r:"<<r<<"  l:"<<l<<'\n';
                //cout<<"lie[r]:"<<lie[r]<<"  lie[l]:"<<lie[l]<<"  num1:"<<lie[i]<<'\n';
            }
            it++;
        }
        cout << ans << '\n';
    }	
    return 0;
}

牛客周赛74

A

题目

第一眼以为要用鸽巢原理，第二眼发现是签到…

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int cache;
set <int> s;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    for(int i=0;i<7;i++){
        cin >> cache;
        s.insert(cache);
    }
    cout << *s.begin();
    return 0;
}

B

题目

构造一个矩阵，每一行、列上都要有非零数字。

思路：构造题，直接输出特殊情况

分四种情况：

  1. k< n、m中任何一个数，构造不出来，输出-1
  2. n<m
  3. n>m
  4. n=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
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 <bits/stdc++.h>
using namespace std;

int n,m,k;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> k;
    if(k<n || k<m){
        cout << -1 << '\n';
        return 0;
    }
    if(n<m){
        for(int i=0;i<n-1;i++){
            for(int j=0;j<m;j++){
                if(j==i){
                    cout << 1 << ' ';
                    k--;
                }
                else cout << 0 << ' ';
            }
            cout << '\n';
        }
        for(int j=0;j<m;j++){
            if(j>=n-1 && j!=m-1){
                cout << 1 << ' ';
                k--;
            }else if(j==m-1) cout << k << ' ';
            else cout << 0 << ' ';
        }
        cout << '\n';
    }
    else if(n>m){
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                if(j==i){
                    cout << 1 << ' ';
                    k--;
                }
                else cout << 0 << ' ';
            }
            cout << '\n';
        }
        for(int i=0;i<n-m-1;i++){
            for(int j=0;j<m;j++){
                if(j==0){
                    cout << 1 << ' ';
                    k--;
                }
                else cout << 0 << ' ';
            }
            cout << '\n';
        }
        for(int i=0;i<m;i++){
            if(!i) cout << k << ' ';
            else cout << 0 << ' ';
        }
        cout << '\n';
    }
    else{
        for(int i=0;i<n-1;i++){
            for(int j=0;j<m;j++){
                if(j==i){
                    cout << 1 << ' ';
                    k--;
                }
                else cout << 0 << ' ';
            }
            cout << '\n';
        }
        for(int i=0;i<m;i++){
            if(i==m-1) cout << k;
            else cout << 0 << ' ';
        }
        cout << '\n';
    }
    return 0;
}

C

题目

贪心

对n做三种操作：1. 开根号(向上取整)；2. 减一；3. 除2(向上取整)

当n>=4时开根时最好的，其他情况都是-1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n,m;
        cin >> n >> m;
        while(m--){
            if(n>=4){
                n=ceil(sqrt(n));
                continue;
            }
            else break;
        }
        cout << n-m-1 << '\n';
    }
    return 0;
}

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
27
28
29
#include <bits/stdc++.h>
using namespace std;

vector <int> s;
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n,cache;
        s.clear();
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> cache;
            s.push_back(cache);
        }
        if(n==1){
            cout << -1 << '\n';
            continue;
        }
        sort(s.begin(),s.end(),greater<int>());
        int n1=s[0],n2=s[1];
        if(n1==1) cout << 0 << '\n';
        else if(n2==1) cout << n1-1 << '\n';
        else cout << n1 << '\n';
    }
    return 0;
}

E

题目

依据题意，

  1. 如果有重复元素，不行
  2. 原数组里的连续单调元素在新数组里也能够连续，行

原数组元素和排过序后的元素是一一对应的关系，用map映射简单一些

代码

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 <bits/stdc++.h>
using namespace std;

bool cpa(int a,int b){
    return a<b;
}//练习
 
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n,m,cache;
        vector<int> a,b;
        cin >> n >> m;
        for(int i=0;i<n;i++){
            cin >> cache;
            a.push_back(cache);
            b.push_back(cache);
        }
        sort(b.begin(),b.end(),cpa);
        for(int i=0;i<n-1;i++){
            if(b[i]==b[i+1]){
                cout << "NO\n";
                continue;
            }
        }
        map <int,int> yingshe;
        for(int i=0;i<n-m;i++){
            yingshe[b[i]] = b[i+m];
        }
        //判断单增
        int zeng[n+3]={0};
        for(int i=1;i<n;i++)
            zeng[i]=zeng[i-1]+(a[i]>a[i-1]);
        for(int i=0;i<n-m;i++)
            if(zeng[i+m]-zeng[i]==m && yingshe[a[i]]==a[i+m]){
                cout << "YES\n";
                continue;	
            }
        //单减
        int jian[n+3]={0};
        for(int i=n-1;i>=0;i--)
            jian[i]=jian[i+1]+(a[i]>a[i+1]);
        for(int i=0;i<n-m;i++){
            if(jian[i]-jian[i+m]==m && yingshe[a[i]]==a[i+m]){
                cout << "YES\n";
                continue;
            }
        }
        cout << "NO\n";
    }
    return 0;
}