Educational Codeforces Round 86 (Rated for Div. 2)

A. Road To Zero

题意：题目要求给定两个数字，x,y。要求通过将其中一个数字或两个数字同时进行加一或减一操作，但这个过程需要支付a或b元，问将两个数都变为0，最少需要支付的钱数。

题解：本题属于简单题，分情况讨论即可，两个数都变为0，有三种方式：

　　两个数各自进行加一或减一操作；当两个数不相等时可将最小的一个数的那个部分进行第二种操作(两个数同时进行加一或减一操作);将两个数变为一样，然后一起进行第二种操作。取三种情况的最小值。

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#define ll long long 
using namespace std;
int main() {
    ll t;
    cin>>t;
    ll x,y,a,b;
    for(ll i=0;i<t;i++){
        cin>>x>>y;
        cin>>a>>b;
        if(x==0||y==0){
            if(x==0&&y==0){
                cout<<0<<endl;
            }else if(x==0&&y!=0){
                cout<<y*a<<endl;
            }else if(x!=0&&y==0){
                cout<<x*a<<endl;
            }
        }else {// x y 都不等于 0 
            ll t1=(x+y)*a;
            ll t2=-1;
            if(x!=y){
                t2=min(x,y)*b+(max(x,y)-min(x,y))*a;
            }
            ll t3=-1;
            if(x==y){
                t3=x*b;
            }else{
                ll tt=(max(x,y)-min(x,y));
                t3=tt*a;
                t3=t3+max(x,y)*b;    
            }
            ll min_n=t1;
            if(t2!=-1){
                min_n=min(min_n,t2);
            }
            if(t3!=-1){
                min_n=min(min_n,t3);
            }
            cout<<min_n<<endl;
        }
    }
    return 0;
}

B. Binary Period

题意：这一题的的题意也比较有意思，让你根据题目给定的字符串t构造一个字符串s。并且s要满足一下三个条件：

　　　1、字符串仅由'0'or'1'构成；

　　　2、s的长度小于等于t的长度的两倍；

　　　3、s是t的字串;

　　　4、在满足1、2、3的条件下使s的字符串周期最短(想要理解“周期”这一概念可以去原题看)。

题解：这一题比较简单的题，主要可以分三类情况讨论：当只有'0'or'1'的时候直接将原串输出即可，当两者的数量不相等时，可向两个数字中间插入字符('0'or'1'),具体插入什么可以根据插入位置两边字符的种类判断，最后保证'1','0'交替出现即可。

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int main() {
    int T;
    string t;
    cin>>T;
    while(T--) {
        cin>>t;/*输入字符串*/
        int num0=0,num1=0;
        for(int i=0; i<t.length(); i++) {
            if(t[i]=='0') {
                num0++;
            } else {
                num1++;
            }
        }
        if(num0==0||num1==0) { // 有一个的数量为 0
            cout<<t<<endl;
        } else { //两者的数量都不为  0
            for(int i=0; i<t.length(); i++) {
                cout<<t[i];
                if(i+1<t.length()) {
                    if(t[i]!=t[i+1]) { //相邻两个不同
                    } else { //相邻两个相同
                        if(t[i]=='0') {
                            cout<<'1';
                        } else {
                            cout<<'0';
                        }
                    }
                }
            }
            cout<<endl;
        }
    }
    return 0;
}

C. Yet Another Counting Problem

题意：这是一个计数问题,题目给出a,b,q.要求你在区间[l,r]中找到符合等式：((x%a)%b)!=((x%b)%a)中x的个数。

题解：这一题一看数据范围就知道直接写肯定会tle，应该是有某种规律在里面，我们注意到：(x%a)=(x+a)%a,(x%b)=(x+b)%b(这是一个非常重要的特点)，那么原式子可以转变为：(x+a)%a%b!=(x+b)%b%a(这是恒等变形)，那么我们想如果把他们的所加的数字变为同一个数，那么这就不是有了周期的性质了吗？而在这个前提下又要保证原式子成立，通过打表可以发现，这里的最小周期就是a,b的最小公倍数。于是我们只要统计一个周期里面的数就可以了。

代码：

#include<iostream>
#include<algorithm>
#include<math.h>
#define ll long long
using namespace std;
const int maxn = 505;
ll ans[maxn]={0} , pre[40005]={0};
ll cnt,gc;
ll app(ll x){
    ll y=x/gc;
    ll t=x%gc;
    ll sum=cnt*y+pre[t];
    return sum;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        ll a,b,q,l,r;
        scanf("%lld %lld %lld",&a,&b,&q);
        cnt=0;
        gc=a*b/__gcd(a,b);
        for(ll i=1;i<=gc;i++){
            if(i%a%b!=i%b%a){
                cnt++;
            }
            pre[i]=cnt;
        }
        for(ll i=1;i<=q;i++){
            scanf("%lld %lld",&l,&r);
            ans[i]=app(r)-app(l-1);
        }
        for(int i=1;i<=q;i++){
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}