首页 > 其他 > 详细

2020.6.1 习题练习四

时间：2020-06-04 21:28:27      阅读：46      评论：0      收藏：0      [点我收藏+]

A - Dreamoon and Ranking Collection

题意：给一串数，要求从小到大要连续起来（1、2、……）可以补上x个数，问最大能连续到多少

做法：用两个数组，一个标记，一个储存，之后因为最多到100，直接循环到100，遇到没标记的就计数，之后分两种情况，一种是x够用，一种是不够用，输出即可

代码：

//去吧马里奥！把AC公主救回来！
//        ********
//       ************
//       ####....#.
//     #..###.....##....
//     ###.......######
//        ...........
//       ##*#######
//    ####*******######
//   ...#***.****.*###....
//   ....**********##.....
//   ....****    *****....
//     ####        ####
//   ######        ######
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#include<map>
#include<sstream>
#include<cstring>
#include<vector>
#include<iomanip>
#include<queue>
#include<set>
#define LL long long
#define _64 __int64
const double PI = atan(1.)*4.;
using namespace std;

int a[2000],b[2000];

int main(){
    int t;
    cin >> t;
    while(t--){
        int n,x;
        cin >> n >> x;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i = 0;i < n;i++){
            cin >> a[i];
            b[a[i]] = 1;
        }
        int num = 0;
        int ans = 0;
        int flag = 1;
        for(int i = 1;i <= 100;i++){
            if(b[i] != 1){
                num++;
                if(num > x){
                    ans = i;
                    flag = 0;
                    break;
                }
            }
        }

        if(flag == 0){
            cout << ans-1 << endl;
        }else{

            cout << 100+x-num << endl;
        }




    }
}

B - Dreamoon Likes Permutations

题意：给出一个序列，可不可以将序列分成两段，前面那段所有数都只出现一次，后面那段数也只出现一次，有范围[1~最大数]

做法：就是判断全排列，先看前半，最大的数要等于个数，且小于最大值的数的个数要等于最大值，后半同理，写两个循环一个从前往后一个从后往前即可

代码：

//去吧马里奥！把AC公主救回来！
//        ********
//       ************
//       ####....#.
//     #..###.....##....
//     ###.......######
//        ...........
//       ##*#######
//    ####*******######
//   ...#***.****.*###....
//   ....**********##.....
//   ....****    *****....
//     ####        ####
//   ######        ######
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#include<map>
#include<sstream>
#include<cstring>
#include<vector>
#include<iomanip>
#include<queue>
#include<set>
#define LL long long
#define _64 __int64
const double PI = atan(1.)*4.;
using namespace std;

int a[200009];
int vis1[200009];
int vis2[200009];

int f1[200009];
int f2[200009];

int main(){
    int t;
    cin >> t;
    while(t--){
        memset(vis1,0,sizeof(vis1));
        memset(vis2,0,sizeof(vis2));
        memset(f1,0,sizeof(f1));
        memset(f2,0,sizeof(f2));
        int n;
        cin >> n;
        for(int i = 1;i <= n;i++){
            cin >> a[i];
        }

        int num1 = 0;
        int maxn1 = 0;
        for(int i = 1;i <= n;i++){
            maxn1 = max(maxn1,a[i]);
            if(vis1[a[i]] == 1){
                continue;
            }
            if(a[i] <= maxn1){
                vis1[a[i]] = 1;
                num1++;
            }

            if(num1 == maxn1 && num1 == i){
                f1[i] = 1;
            }
        }

        int num2 = 0;
        int maxn2 = 0;
        for(int i = n;i >= 1;i--){
            maxn2 = max(maxn2,a[i]);
            if(vis2[a[i]] == 1){
                continue;
            }
            if(a[i] <= maxn2){
                vis2[a[i]] = 1;
                num2++;
            }

            if(num2 == maxn2 && num2 == n-i+1){
                f2[i] = 1;
            }
        }

        int ans = 0;
        for(int i = 1;i <= n-1;i++){
            if(f1[i] == 1 && f2[i+1] == 1){
                ans++;
            }
        }
        cout << ans << endl;
        for(int i = 1;i <= n-1;i++){
            if(f1[i] == 1 && f2[i+1] == 1){
                cout << i << " " << n-i << endl;
            }
        }

    }
}

C - Exercising Walk

题意：说一只猫散步，初始位置已知，给出四个方向移动步数，问最后猫的位置在不在划定范围内

做法：首先猫不可能不动，之后有不水平移动或不竖直运动的情况，再就是正常情况，写几个if判断即可

代码：

//去吧马里奥！把AC公主救回来！
//        ********
//       ************
//       ####....#.
//     #..###.....##....
//     ###.......######
//        ...........
//       ##*#######
//    ####*******######
//   ...#***.****.*###....
//   ....**********##.....
//   ....****    *****....
//     ####        ####
//   ######        ######
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#include<map>
#include<sstream>
#include<cstring>
#include<vector>
#include<iomanip>
#include<queue>
#include<set>
#define LL long long
#define _64 __int64
const double PI = atan(1.)*4.;
using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        int a,b,c,d;
        int x,y,x1,x2,y1,y2;
        cin >> a >> b >> c >> d;
        cin >> x >> y >> x1 >> y1 >> x2 >> y2;

        int flag = 1;

        if(x1 == x2 && a + b != 0){
            flag = 0;
        }else if(y1 == y2 && c + d != 0){
            flag = 0;
        }

        int ansx,ansy;
        ansx = x + b - a;
        ansy = y + d - c;

        if(ansx < x1 || ansx > x2 || ansy < y1 || ansy > y2){
            flag = 0;
        }

        if(flag == 0){
            cout << "No" << endl;
        }else{
            cout << "Yes" << endl;
        }
    }
}

D - Composite Coloring

题意：一个合数质数的问题，给出n个合数，用最多11种颜色染色，当两个合数都含同一质数的时候就可以用同一种颜色

做法：提示很明显了，因为小于1000的质数一共就11个，先筛出来，之后边读边判断，标记计数就行

代码：

//去吧马里奥！把AC公主救回来！
//        ********
//       ************
//       ####....#.
//     #..###.....##....
//     ###.......######
//        ...........
//       ##*#######
//    ####*******######
//   ...#***.****.*###....
//   ....**********##.....
//   ....****    *****....
//     ####        ####
//   ######        ######
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#include<map>
#include<sstream>
#include<cstring>
#include<vector>
#include<iomanip>
#include<queue>
#include<set>
#define LL long long
#define _64 __int64
const double PI = atan(1.)*4.;
using namespace std;

int num;
int prime[2000];
int vis[2000];
int co[2000];
int color;
int ans[2000];
int m;

void primes(int n){
    for(int i = 2; i <= n; i++){
        if(vis[i]){
            continue;
        }
        prime[++m] = i;
        for(int j = i; j <= n/i;j++){
            vis[i*j] = 1;
        }
    }
}

int main(){
    primes(1000);
    int t;
    cin >> t;
    while(t--){
        memset(co,0,sizeof(co));
        memset(ans,0,sizeof(ans));
        color = 0;
        int n;
        cin >> n;
        for(int i = 1;i <= n;i++){
            int x;
            cin >> x;
            for(int j = 1;j <= m;j++){
                if(x % prime[j] == 0){
                    if(co[prime[j]] == 0){
                        color++;
                        co[prime[j]] = color;
                    }
                    ans[i] = co[prime[j]];
                    break;
                }
            }
        }

        cout << color << endl;
        for(int i = 1;i <= n;i++){
            cout << ans[i] << " ";
        }
        cout << endl;
    }
}

E - K-th Beautiful String

题意：简单说就是给出n，之后会产生长度为n，由2个b和n-2个a组成的字符串，给出k，让你输出第k个串

做法：有规律，先找左数第一个，在倒数第二位置有一个，倒数第3位置两个，倒数第4位置3个……这就是规律，先找这个，之后再找第二个就ok

代码：

//去吧马里奥！把AC公主救回来！
//        ********
//       ************
//       ####....#.
//     #..###.....##....
//     ###.......######
//        ...........
//       ##*#######
//    ####*******######
//   ...#***.****.*###....
//   ....**********##.....
//   ....****    *****....
//     ####        ####
//   ######        ######
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#include<map>
#include<sstream>
#include<cstring>
#include<vector>
#include<iomanip>
#include<queue>
#include<set>
#define LL long long
#define _64 __int64
const double PI = atan(1.)*4.;
using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        int n,k;
        cin >> n >> k;
        int sum = 0;
        int i = 0;
        while(1){

            if(sum + i >= k ){
                break;
            }
            sum += i;
            i++;
        }
        int ans;
        ans = k - sum - 1;
        //cout << ans <<‘ ‘ << k<< ‘ ‘<<i<< endl;
        for(int j = 0;j < n;j++){
            if(j == n-i-1 || j == n-ans-1){
                cout << ‘b‘;
            }else{
                cout << ‘a‘;
            }

        }
        cout << endl;
    }
}

F - Carousel

题意：一个环，有若干种不同的动物种类，要给他们上色，要求很简单，就是不同种类的相邻动物不同色就行，求用的颜色数最小

做法：看的题解，全是if else差点没给绕死，需要分情况讨论

如果全一个种类或者只有一个，就全上一种颜色

如果有偶数个动物，就相间上色，两种颜色

如果有奇数个动物就还要分，首先最后一个可能和第一个动物同类；还可能和倒数第二个同类，还可能都不同类

如果是前两者可以只用2种颜色解决，如果第三者则最好倒数第二个和第一个是同一个颜色，如果不是那必须要用三种颜色才能解决了

代码：

//去吧马里奥！把AC公主救回来！
//        ********
//       ************
//       ####....#.
//     #..###.....##....
//     ###.......######
//        ...........
//       ##*#######
//    ####*******######
//   ...#***.****.*###....
//   ....**********##.....
//   ....****    *****....
//     ####        ####
//   ######        ######
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#include<map>
#include<sstream>
#include<cstring>
#include<vector>
#include<iomanip>
#include<queue>
#include<set>
#define LL long long
#define _64 __int64
const double PI = atan(1.)*4.;
using namespace std;

const int maxn=2*1e5+9;
int t[maxn],q,n,a[maxn],k;

void print(int k,int w){
    cout<<k<<endl;
    for(int i=1;i<=w;i++){
        cout<<a[i]<<" ";
    }
}
int main(){
    cin >> q;
    while(q--){
        k = 1;
        cin >> n;
        int flag = 0;
        for(int i = 1;i <= n;i++){
            cin >> t[i];
            if(t[i] != t[i-1] && i != 1){
                flag=1;
            }
        }
        if(flag == 0 || n == 1){
            cout << 1 << endl;
            for(int i = 1;i <= n;i++){
                cout << 1 <<" ";
            }
        }else{
            for(int i = 1;i <= n;i++)
            if(i % 2 == 1){
                a[i] = 1;
            }
            else{
                a[i] = 2;
            }
            if(n % 2 == 0){
                print(2,n);
            }
            else{
                if(t[n] != t[n-1] && t[n] != t[1]){
                    int P = 0;
                    for(int i = 2;i <= n-1;i++)
                    if(t[i] == t[i-1]){
                        P++;
                    }
                    if(P >= 1){
                        a[1] = 1;int num;
                        for(int i = 2;i <= n - 1;i++){
                            if(t[i] == t[i-1]){
                                a[i] = a[i-1],num = i + 1;
                                break;
                            }
                        }
                        for(int i = num;i <= n;i++)
                        if(a[i-1] == 1){
                            a[i]=2;
                        }else{
                            a[i]=1;
                        }
                        print(2,n);
                    }
                    else{
                        a[n] = 3;
                        print(3,n);
                    }
                }else if(t[n] != t[n-1]){
                        print(2,n);
                }else if(t[n] != t[1]){
                    a[n] = 2;
                    print(2,n);
                }
                else{print(2,n);
                }
            }
        }
        cout << endl;
    }
}

 

2020.6.1 习题练习四

原文：https://www.cnblogs.com/CCCCrack/p/13045584.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！