A. Make Even

题目大意：

Polycarp有一个不包含数字0的整数n。他可以对他的数字进行多次（可能是零）的操作。

将n的长度为l的前缀（换句话说，最左边的l个数字）颠倒过来。因此，最左边的数字与左边的第l个数字互换，左边的第二个数字与左边的（l-1）个数字互换，等等。例如，如果n=123456789，l=5，那么n的新值将是543216789。
注意，对于不同的操作，l的值可以是不同的。数字l可以等于数字n的长度–在这种情况下，整数n被倒置。

波利卡普喜欢双数。因此，他想让自己的数字变成偶数。同时，波利卡普非常没有耐心。他想尽可能少做操作。

帮助波利卡普。确定他需要对数字n进行的最小操作数，以使其成为偶数，或者确定这是不可能的。

你需要回答t个独立的测试案例。

输入
第一行包含数字t（1≤t≤104）–测试案例的数量。

接下来的t行中的每一行包含一个整数n（1≤n<109）。保证给定的数字不包含数字0。

输出
打印t行。每行打印一个整数 - 相应测试案例的答案。如果不可能得到一个偶数，则打印-1。

做题思路：

分类讨论

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int maxn=1e6+5;
bool is(string s){
   
    for (int i = 0; i < s.size();i++){
   
        if((s[i]-'0')%2==0)
            return true;
    }
    return false;
}
void solve(){
   
    string s;
    cin >> s;
    int n = s[0] - '0';
    int m = s[s.size() - 1] - '0';
    if(m%2==0)
        cout << "0" << endl;
    else if(n%2==0){
   
        cout << '1' << endl;
    }
    else{
   
        if(s.size()!=1&&is(s))
            cout << "2" << endl;
        else{
   
            cout << "-1" << endl;
        }
    }
}

int main(){
   
    ios::sync_with_stdio(0);
    int t;
    cin >> t ;
    while(t--){
   
         solve();
    }
    return 0;
}

B. Team Composition: Programmers and Mathematicians

题目大意：

全柏林团队编程竞赛将很快举行。今年，允许四人团队参加。

在Berland州立大学有a名程序员和b名数学家。最多可以组成多少个团队，如果。

每队必须正好由4名学生组成。
由4名数学家或4名程序员组成的队伍不太可能有好的表现，所以决定不组成这样的队伍。
因此，每个团队必须至少有一个程序员和至少一个数学家。

打印出所需的最大团队数量。每个人可以是不超过一个团队的成员。

输入
第一行包含一个整数t（1≤t≤104）–测试案例的数量。

接下来是对t组的描述，每行一个。每组由两个整数a和b给出（0≤a,b≤109）。

输出
打印t行。每行必须包含对应的输入数据集的答案–所需的最大团队数量。

做题思路

思维+贪心

code:


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int maxn=1e6+5;
void solve(){
   
    ll a, b;
    cin >> a >> b;
    ll m = (a + b) / 4;
    cout << min(min(a, b), m) << endl;
}

int main(){
   
    ios::sync_with_stdio(0);
    int t;
    cin >> t ;
    while(t--){
   
         solve();
    }
    return 0;
}

C. Polycarp Recovers the Permutation

题目大意:

波利卡普在白板上写了一个长度为n的数组p，这是一个从1到n的数字的排列组合。

他还准备了一个结果数组a，它最初是空的（也就是说，它的长度为0）。

之后，他正好做了n个步骤。每一步都是这样的。

看一下p的最左边和最右边的元素，然后挑选其中较小的一个。
如果你选了p的最左边的元素，就把它附加到a的左边；否则，如果你选了p的最右边的元素，就把它附加到a的右边。
被选中的元素将从p中删除。
注意，在最后一步，p的长度为1，它的最小元素既是最左边也是最右边。在这种情况下，Polycarp可以选择最小元素扮演什么角色。换句话说，这个元素既可以加在a的左边，也可以加在右边（由Polycarp决定）。

让我们看一个例子。让n=4，p=[3,1,4,2]。最初a=[]。然后。

在第一步中，最小值在右边（数值为2），所以在这一步之后，p=[3,1,4]，a=[2]（他把数值2加在右边）。
在第二步中，最小值在左边（值为3），所以在这一步之后，p=[1,4]，a=[3,2]（他在左边增加了值3）。
在第三步中，最小值在左边（值为1），所以在这一步之后，p=[4]，a=[1,3,2]（他在左边加了值1）。
在第四步中，最小值既是左边又是右边（这个值是4）。假设波利卡普选择了右边的选项。在这一步之后，p=[]，a=[1,3,2,4]（他在右边加了值4）。
因此，n步之后a的可能值可能是a=[1,3,2,4]。

找到任何可能的p的初始值，从而得到给定的a，或者确定没有解决方案。

输入
输入的第一行包含一个整数t（1≤t≤104）–测试中测试案例的数量。

做题思路：

模拟题意

注意“-1”的判断条件：给定数组的开头和结尾都不是数组所有元素的最大值，则无法构成此数组。

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
void solve(){
   
    stack<int> st;
    queue<int> q;
    int n;
    cin >> n;
    int a[maxn];
    for (int i = 0; i < n; i++){
   
        cin >> a[i];
    }
    if(max(a[0],a[n-1])!=n){
   
        cout << "-1\n";
    }
    else{
   
        for (int i = 0, j = n - 1; i != j+1; ){
   
            if(a[i]>=a[j]){
   
                //左大
                st.push(a[i]);
                i++;
            }else{
   
                q.push(a[j]);
                j--;
            }
        }
        while(!st.empty()){
   
            cout << st.top() << " ";
            st.pop();
        }while(!q.empty()){
   
            cout << q.front() << " ";
            q.pop();
        }
        cout<<endl;
    }
}

int main(){
   
    int t;
    cin >> t ;
    while(t--){
   
         solve();
    }
    return 0;
}

2021-11-26【Codeforces Round #756 (Div. 3)】【A-C题解】

A. Make Even

题目大意：

做题思路：

code:

B. Team Composition: Programmers and Mathematicians

题目大意：

做题思路

code:

C. Polycarp Recovers the Permutation

题目大意:

做题思路：

code: