题解-20200207

A-String Transformation

https://vjudge.net/problem/CodeForces-946C

本题的题意：给你一个字符串，要你判断从这个字符串中通过将字符串的字符进行变化（从小往大变）能否得到a-z这26个字母，如果能，则将变化后的字符串输出，否则就输出-1.

解题思路：可以通过for循环遍历所给字符串的每一个字符。定义一个初始字符c=‘a’，假如当ptr[i]<=c,就说明ptr[i]可以通过该种变化变为c，同时将ptr[i]更新为c,进行完该操作后，c进行c++，即将c更新为下一个字母，当c>'z'时，即表明26个字母群都可以通过改变化获得，即可将该变化后的字符串输出，假如当循环结束，c<'z'，即表明该字符串不符合题意，即可输出-1.

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#define ll long long
using namespace std;
int cmp(int a,int b){
	return a>b;
}
ll read(){
	ll x=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return w*x;
}//快读算法
bool IsPrimeNumber(int n){//判断该数是不是素数
    if (n==2){
        return true;
    }
    if (n%2==0||n==1){
        return false;
    }
    int sqrtn=(int)sqrt((double)n);
    bool flag=true;
    for (int i=3;i<=sqrtn;i+=2){
        if (n%i==0){
            flag=false;
        }
    }
    return flag;
}//快速判断某个数是不是素数的算法
void reversea(int t[],int n){
    int temp[n];
    for(int i=0;i<n;i++){
        temp[i]=t[i];
    }
    int r=0;
    for(int i=n-1;i>=0;i--){
        t[r++]=temp[i];
    }
}//数组逆序函数
int main(){
    string ptr;
    int f=0;//标记 
    string ans;
    cin>>ptr;
    int t=0;
	char c= 'a';
	int num=0;
	for(int i=0;i<ptr.length();i++){
		if(ptr[i]<=c){
			ptr[i]=c;
			c++;
			num++;
		}
		if(num==26){
			f=1;
			break;
		}
	}
	if(f==0){
		cout<<-1<<endl;
	}else{
		cout<<ptr<<endl;
	}
    return 0;
}

B-Weird Subtraction Process

https://vjudge.net/problem/CodeForces-946B

本题的题意：题目给处两个数a,b，要你判断当a,b经过一下两个步骤后，输出a,b的值。

1、当a=0或者b=0，结束这个程序，否则执行第二步。

2、当a>=2*b时，就令a=a-2*b，返回第一步继续执行，否则执行第三步。

3、当b>=2*a时，就令b=b-2*a，返回第一步继续执行，否则跳出循环，输出a,b。

解题思路：本题是一个题意简单的模拟题，但由于输入的数据范围太大，简单的进行过程模拟肯定会超时，所以，这里就需要利用技巧--“取余运算替换减法运算”，我们注意到，如果单纯的执行a=a-2*b，该步骤可能会执行很多次，但如果我们执行a=a%(2*b)，即该步骤只会执行一次，这就大大的提高了执行的效率，而最终的运算结果是一样的。同理，用b=b%(2*a)替换步骤3中的运算。

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#define ll long long
using namespace std;
int cmp(int a,int b){
	return a>b;
}
ll read(){
	ll x=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return w*x;
}//快读算法
bool IsPrimeNumber(int n){//判断该数是不是素数
    if (n==2){
        return true;
    }
    if (n%2==0||n==1){
        return false;
    }
    int sqrtn=(int)sqrt((double)n);
    bool flag=true;
    for (int i=3;i<=sqrtn;i+=2){
        if (n%i==0){
            flag=false;
        }
    }
    return flag;
}//快速判断某个数是不是素数的算法
void reversea(int t[],int n){
    int temp[n];
    for(int i=0;i<n;i++){
        temp[i]=t[i];
    }
    int r=0;
    for(int i=n-1;i>=0;i--){
        t[r++]=temp[i];
    }
}//数组逆序函数
int main(){
    ll a,b;
    cin>>a>>b;
    int f=1;
    while(1){
    	if(a==0||b==0){
    		break;
		}
		if(a>=2*b){
			a=a%(2*b);
		}else if(b>=2*a){
			b=b%(2*a);
		}else{
			break;
		}
	}
	cout<<a<<" "<<b<<endl;
    return 0;
}

C-Partition

https://vjudge.net/contest/355841#problem/C

本题题意：本题比较简单，题目给你一个数字序列，从中抽出若干个组成集合A,剩下的组成集合B,当然，也可以一个数字也不算抽，要你求 $sum_{A}-sum_{B}$ 的最大值。（如果该集合中元素个数为0，则它的和为0）

解题思路：遍历该数字序列，正数放到集合A，其余的放到集合B，这样求出来的结果是最大的。

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#define ll long long
using namespace std;
int cmp(int a,int b){
	return a>b;
}
ll read(){
	ll x=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return w*x;
}//快读算法
bool IsPrimeNumber(int n){//判断该数是不是素数
    if (n==2){
        return true;
    }
    if (n%2==0||n==1){
        return false;
    }
    int sqrtn=(int)sqrt((double)n);
    bool flag=true;
    for (int i=3;i<=sqrtn;i+=2){
        if (n%i==0){
            flag=false;
        }
    }
    return flag;
}//快速判断某个数是不是素数的算法
void reversea(int t[],int n){
    int temp[n];
    for(int i=0;i<n;i++){
        temp[i]=t[i];
    }
    int r=0;
    for(int i=n-1;i>=0;i--){
        t[r++]=temp[i];
    }
}//数组逆序函数
int main(){
    int n;
    cin>>n;
    int num[10000]={0};
    for(int i=0;i<n;i++){
        cin>>num[i];
    }//输入数据
    sort(num,num+n);//从小到大
    int suma=0;
    int sumb=0;
    int cmax=-1;
    for(int i=0;i<n;i++){//以 i 为基础
        //取  i  个值
        if(num[i]>0){
            suma=suma+num[i];
        }else{
            sumb=sumb+num[i];
        }
    }
    //suma大于0  sumb小于0
    cout<<suma-sumb<<endl;
    return 0;
}

F-Zebras

https://vjudge.net/problem/CodeForces-950C

本题题意：给你一串“01”串，要你判断可以组成多少个“正确的序列”---“以0开头和以0结尾，并且其中0和1交替出现”，要注意的是串中每一个字符都必须要用到，假如不能构成正确的序列或者是有字符没有被用到则输出-1，否则输出总的数量以及每个字符的长度及坐标。

本题思路：利用二维vector,利用for循环遍历，当遇到‘0’时，放到vector中，当遇到‘1’时，放到上一个‘0’的后面，（注意放进去的该字符的坐标）

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#define ll long long
using namespace std;
int cmp(int a,int b){
    return a>b;
}
ll read(){
    ll x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return w*x;
}//快读算法
bool IsPrimeNumber(int n){//判断该数是不是素数
    if (n==2){
        return true;
    }
    if (n%2==0||n==1){
        return false;
    }
    int sqrtn=(int)sqrt((double)n);
    bool flag=true;
    for (int i=3;i<=sqrtn;i+=2){
        if (n%i==0){
            flag=false;
        }
    }
    return flag;
}//快速判断某个数是不是素数的算法
//==================================
const int maxn=2e5+7;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int EPS=1e-6;
ll binarymod(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)
        res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
//利用二进制来算a的b次方的模板
//===================================
char s[maxn];
vector<int> a[maxn];
int main(){
    scanf("%s",s+1);
    int len=strlen(s+1);
    int Max=-1,ans=0,flag=1;
    for(int i=1;i<=len&&flag;i++){
        if(s[i]=='0'){
        	a[++ans].push_back(i);
		}else{
            if(ans==0){
            	flag=0;
			}    
            a[ans--].push_back(i);
        }
        Max=max(Max,ans);
    }
	if(Max!=ans){
		flag=0;
	}
	if(flag==0){
		cout<<-1<<endl;
	}else{
		cout<<Max<<endl;
		for(int i=1;i<=Max;i++){
			cout<<a[i].size();
			for(int j=0;j<a[i].size();j++){
				cout<<" "<<a[i][j];
			}
			cout<<endl;
		}
	}
    return 0;
}

G-Left-handers, Right-handers and Ambidexters

https://vjudge.net/problem/CodeForces-950A

本题的题意：给你三种人：习惯用左手的（l）、习惯用右手（r）的以及左右手（a）都习惯用的，要你将这三种人分为两组，要求组中，使用左手和右手的人数一样，要你计算该组人数最多的人数。

解题思路：本题主要在于对数字a的处理上，我们可以先将a分给a、b两种情况（谁少分给谁），最后ans等于a、b中人数少的那一种的两倍。

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#define ll long long
using namespace std;
int cmp(int a,int b){
	return a>b;
}
ll read(){
	ll x=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return w*x;
}//快读算法
bool IsPrimeNumber(int n){//判断该数是不是素数
    if (n==2){
        return true;
    }
    if (n%2==0||n==1){
        return false;
    }
    int sqrtn=(int)sqrt((double)n);
    bool flag=true;
    for (int i=3;i<=sqrtn;i+=2){
        if (n%i==0){
            flag=false;
        }
    }
    return flag;
}//快速判断某个数是不是素数的算法
void reversea(int t[],int n){
    int temp[n];
    for(int i=0;i<n;i++){
        temp[i]=t[i];
    }
    int r=0;
    for(int i=n-1;i>=0;i--){
        t[r++]=temp[i];
    }
}//数组逆序函数
int main(){
    int r,l,a;
    cin>>l>>r>>a;
    int ans=0;
    while(a){
        if(l>r){
            r++;
        }else{
            l++;
        }
        a--;
    }
    if(l>r){
        ans=2*r;
    }else{
        ans=2*l;
    }
    cout<<ans<<endl;
    return 0;
}