A题

题目链接

题意及思路

  • 题意：大致要求的是，问我们围成一个圈的n个学生能否起舞，哈哈哈。起舞的标准是，顺时针学生的编号按升序排列，或者逆时针学生的编号按升序排列。当然了，学生的编号由1到n，各不相同。
  • 思路：首先，读入数据的时候，先找到下标为1的最小位的位置。然后，从该位开始，从左右两边顺次比较学生的编号，如若两者皆不满足可起舞的条件，则输出false，反之输出true。

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 205;
int qt[N];
vector<int> tp,tq;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int q,n;
    cin >> q;
    while(q--){
        cin >> n;
        int flag = 0;
        for(int i=0;i<n;i++) {
            cin >> qt[i];
            if(qt[i]==1)
                flag = i;
        }

        tp.clear();
        int cnt = 0;
        int i = flag;
        for( ;cnt<n;i=(i+1)%n){
            tp.push_back(qt[i]);
            cnt++;
        }

        tq.clear();
        i = flag;
        cnt = 0;
        for( ;cnt<n;i=i==0?n-1:i-1){
            tq.push_back(qt[i]);
            cnt++;
        }
//        cout << "tq : " << endl;
//        for(int i=0;i<n;i++){
//            cout << tq[i] << " ";
//        }
//        cout << endl;

        bool f = true;
        for(int i=1;i<n;i++){
            if(tp[i]!=tp[i-1]+1 && tq[i]!=tq[i-1]+1){
                f = false;
                break;
            }
        }
        if(f) cout << "YES" << endl;
        else cout <<"NO" << endl;
    }
    return 0;
}

B题

题目链接

题意及思路

  • 题意：给出4n条边，问能否构成面积相等的n个矩形。
  • 思路：想法是，先将边不降排序；然后双指针i、j，分别从头尾遍历元素；每一个矩形需要至少需要两个等长的边，故每次判断i、j指针所指的下一顺次位上的边长是否与当前边等长，如若不满足，这组数组将无法构成题意的矩形；反之，将i*j，意即矩形面积存入s（set对象）中。最后判断s中元素个数即可（显而易见，若满足题意等面积的矩形的话，s中必定只有一个元素）。

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 405;
int qt[N];
set<int> s;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int q,n;
    cin >> q;
    while(q--){
        cin >> n;
        for(int i=0;i<4*n;i++){
            cin >> qt[i];
        }
        sort(qt,qt+4*n);
        s.clear();

        bool f = true;
        int i=0,j=4*n-1;
        for( ;i<j;i+=2,j-=2){
            if(qt[i+1]!=qt[i] || qt[j-1]!=qt[j]){
                f = false;
                break;
            }
//            cout << "s : " << qt[i]*qt[j] << endl;
            s.insert(qt[i]*qt[j]);
        }
        if(f && s.size()==1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

C题

题目链接

题意及思路

  • 题意：给定n个数，求能被 所有n个数整除的 数的个数。
  • 思路：直接暴力法会TLE，因为该题n个数上限是10的12次方。所以我们第一步，先将n个数的最大公约数求出来。第二步，在图片说明 范围内，找能被g整除的即可被所有n个数 整除，ans++。
  • 收获：知道了c++中，有个__gcd内置函数，并且所有能被n个整数共同整除的数的个数该怎么做的方法。

代码

#include<bits/stdc++.h>

using namespace std;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    long long g = 0;
    for(int i=0;i<n;i++){
        long long x;
        cin >> x;
        g = __gcd(g,x);
    }

    int ans = 0;
    for(int i=1;i*1ll*i<=g;i++){
        if(g%i==0){
            ans++;
            if(i!=g/i){
                ans++;
            }
        }
    }
    cout << ans << endl;

    return 0;
}

D题

题目链接

题意及思路

  • 题意：给定s和t字符串，t必定能从s中找出。求最大可删除多长的子串，保留后的s仍然是t的父串。
  • 思路：枚举。删除i到j这一段子串。从j+1开始遍历到s尾部，遍历一遍后，如果找到了t，则更新ans。
  • 题意模糊处：这题解法子串的定义似乎是，只需要s中有t中的每一个字符，并且字符的相对位置不变即t是s的子串。我很纳闷这种含义，做题时，我没有看懂题目，英文阅读能力和文字阅读能力欠缺。

代码

#include<bits/stdc++.h>

using namespace std;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    string s,t;
    cin >> s >> t;

    int ans = 0;
    int ls = s.size(),lt = t.size();
    for(int i=0; i<ls; i++){
        for(int j=i; j<ls; j++){
            int pos = 0;
            for(int p=0; p<ls; p++){
                if(i<=p && p<=j) continue; //从后面那个下标j后面开始搜索子串中是否包含子串t 
                if(pos<lt && t[pos]==s[p]) pos++; 
            }
            if(pos==lt) ans = max(ans,j-i+1);
        }
    }
    cout << ans << endl;

    return 0;
}