2019 Multi-University Training Contest 7

1001 A + B = C

题目链接
题意：给出a，b，c，寻找x，y，z满足式子 ${a*10^{x}+b*10^{y}=c*10^{z}}$ 。
思路：将a，b，c三个数补位后继0至长度相同，可能满足情况为

b数字移位和 c-a的数字移位比较
a数字移位和 c-b的数字移位比较
b数字移位和 10*c-a的数字移位比较
a数字移位和 10*b-a的数字移位比较

模拟一个大数减法，四次比较

#include <bits/stdc++.h>

#define maxn 100005
using namespace std;

char a[maxn],b[maxn],c[maxn];
int numa[maxn],numb[maxn],numc[maxn];
int ans1,ans2,ans3;

void sub(char s1[],char s2[],int n,int m)
{
    int i,j;
    for(i=0; i<n; i++)
        numa[i]=s1[n-i-1]-'0';
    for(i=0; i<m; i++)
        numb[i]=s2[m-i-1]-'0';
    for(i=0; i<n; i++)
        numc[i]=numa[i]-numb[i];
    for(i=0;i<n;i++){
        if(numc[i]<0)
        {
            while(numc[i]<0)
            {
              numc[i+1]=numc[i+1]-1;
              numc[i]+=10;
            }
        }    
    }   
}

bool isbig(char s1[],char s2[],int n,int m)
{
    if(n>m)
        return 1;
    else if(n==m){
        int k=strcmp(s1,s2);
        if(k>0)
            return 1;
    }
    return 0;
}

void input(){
    scanf("%s%s%s",a,b,c);
    int lena=strlen(a);
    int lenb=strlen(b);
    int lenc=strlen(c);
    int len=max(lena,max(lenb,lenc));

    ans1=ans2=ans3=0;

    int tlen=strlen(a);
    while(len>tlen)
    {
        a[tlen]='0';
        a[++tlen]='\0';
        ans1++;
    }

    tlen=strlen(b);
    while(len>tlen)
    {
        b[tlen]='0';
        b[++tlen]='\0';
        ans2++;
    }

    tlen=strlen(c);
    while(len>tlen)
    {
        c[tlen]='0';
        c[++tlen]='\0';
        ans3++;
    }
}

void solve(){
    int lena=strlen(a);
    int lenb=strlen(b);
    int lenc=strlen(c);
    int i;
    if(isbig(c,a,lenc,lena)){
        sub(c,a,lenc,lena);
        int flag=0;
        int Flag=1;
        int cnt=0;
        for(i=lenc-1;i>=0;i--){
            if(!numc[i])
            {
                if(!flag)
                    continue;
                else
                {
                    if(numc[i]!=b[cnt]-'0')
                        Flag=0;
                    cnt++;
                }
            }else{
                flag=1;
                if(numc[i]!=b[cnt]-'0')
                    Flag=0;
                cnt++;
            }
            if(!Flag)break;
        }

        for(i=cnt+1;i<lenb;i++)
            if(b[i]-'0'!=0)
                Flag=0;

        if(Flag){
            ans2-=lenc-cnt;
            if(ans2<0)
            {
                ans1-=ans2;
                ans3-=ans2;
                ans2=0;
            }

            printf("%d %d %d\n",ans1,ans2,ans3);
            return ;
        }
    }

    if(isbig(c,b,lenc,lenb)){
        sub(c,b,lenc,lenb);
        int flag=0;
        int Flag=1;
        int cnt=0;
        for(i=lenc-1;i>=0;i--){
            if(!numc[i])
            {
                if(!flag)
                    continue;
                else
                {
                    if(numc[i]!=a[cnt]-'0')
                        Flag=0;
                    cnt++;
                }
            }else{
                flag=1;
                if(numc[i]!=a[cnt]-'0')
                    Flag=0;
                cnt++;
            }
            if(!Flag)break;
        }

        for(i=cnt+1;i<lena;i++)
            if(a[i]-'0'!=0)
                Flag=0;

        if(Flag){
            ans1-=lenc-cnt;
            if(ans1<0)
            {
                ans2-=ans1;
                ans3-=ans1;
                ans1=0;
            }

            printf("%d %d %d\n",ans1,ans2,ans3);
            return ;
        }
    }

//    cout<<"!";
    c[lenc]='0';
    c[++lenc]='\0';
    ans3++;

    if(isbig(c,a,lenc,lena)){
        sub(c,a,lenc,lena);
        int flag=0;
        int Flag=1;
        int cnt=0;
        for(i=lenc-1;i>=0;i--){
            if(!numc[i])
            {
                if(!flag)
                    continue;
                else
                {
                    if(numc[i]!=b[cnt]-'0')
                        Flag=0;
                    cnt++;
                }
            }else{
                flag=1;
                if(numc[i]!=b[cnt]-'0')
                    Flag=0;
                cnt++;
            }
            if(!Flag)break;
        }

        for(i=cnt+1;i<lenb;i++)
            if(b[i]-'0'!=0)
                Flag=0;

        if(Flag){
            ans2-=lenc-1-cnt;
            if(ans2<0)
            {
                ans1-=ans2;
                ans3-=ans2;
                ans2=0;
            }

            printf("%d %d %d\n",ans1,ans2,ans3);
            return ;
        }
    }

    if(isbig(c,b,lenc,lenb)){
        sub(c,b,lenc,lenb);
        int flag=0;
        int Flag=1;
        int cnt=0;
        for(i=lenc-1;i>=0;i--){
            if(!numc[i])
            {
                if(!flag)
                    continue;
                else
                {
                    if(numc[i]!=a[cnt]-'0')
                        Flag=0;
                    cnt++;
                }
            }else{
                flag=1;
                if(numc[i]!=a[cnt]-'0')
                    Flag=0;
                cnt++;
            }
            if(!Flag)break;
        }

        for(i=cnt+1;i<lena;i++)
            if(a[i]-'0'!=0)
                Flag=0;

        if(Flag){
            ans1-=lenc-1-cnt;
            if(ans1<0)
            {
                ans2-=ans1;
                ans3-=ans1;
                ans1=0;
            }

            printf("%d %d %d\n",ans1,ans2,ans3);
            return ;
        }
    }

    printf("-1\n");
    return;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        input();
        solve();
    }
}

1006 Final Exam

题目链接
题意：有n门课，课程总分是m，复习一门课程的时间为其分数x+1，要求保证有k门课程通过。求所需要的最少时间。

思路：考虑最糟糕情况，即最后n-k+1门课程平分了所有的m分数。对于前k-1门，我并不知道课程的具体顺序，所以每一门复习所需要的时间都是 $\lceil$ $\frac{(m+1)}{(n-k+1)}$ $\rceil$ ，对于后面总共n-k+1所需要的时间总和即为m+1。

#include <cstdio>
#include <cmath>
#include <iostream>

typedef long long ll;
using namespace std;

int n,m,k;
void input(){
    scanf("%d%d%d",&n,&m,&k);
}

void solve(){
    printf("%lld\n",(ll)ceil(1.0*(m+1)/(n-k+1))*(k-1)+m+1);
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        input();
        solve();
    }
}

1010 Just Repeat

题目链接
题意：两个人玩游戏，第一人有n张牌，第二个人有m张，每张牌有其花色用数字表示，当其中一人选择了某种花色的牌，另一人就不能选择此花色的牌。谁不能拿谁输，求最后胜者。

思路：贪心考虑，优先的牌一定是出现次数最多的。在我方出现多，代表能选择更多次，在对方出现多代表能封对方更多牌。将双方都出现过的牌进行统计次数，从大到小排序，双方轮流贪心选择。
最后记录每个人的牌数，即只出现在自己方的牌+被自己选择的出现在双方的牌在自己手上出现次数。比较大小，若前者大于后者则胜利，否则失败。

据题解说卡了map，通过排序后类似多项式合并的方式优化。

#include <bits/stdc++.h>

#define maxn 10000005
typedef unsigned long long ull;
using namespace std;

unsigned long long k1, k2;
ull a[maxn],b[maxn];
pair<ull,ull> res[maxn];

bool cmp(pair<ull,ull> p,pair<ull,ull> q){
    return p.first + p.second > q.first + q.second;
}

struct node{
    ull val;
    ull cnt;
};
node na[maxn],nb[maxn];
int n,m,p;
unsigned long long rng() {
    unsigned long long k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= k3 << 23;
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

void input(){
    int i;
    scanf("%d%d%d",&n,&m,&p);
    if(p==1){
        for(i=0;i<n;i++)
            scanf("%lld",&a[i]);
        for(i=0;i<m;i++)
            scanf("%lld",&b[i]);
    }else{
        ull mod;
        scanf("%lld%lld%lld",&k1,&k2,&mod);
        for (i = 0; i < n; ++i)
            a[i] = rng() % mod;

        scanf("%lld%lld%lld",&k1,&k2,&mod);
        for (i = 0; i < m; ++i)
            b[i] = rng() % mod;
    }

/*
    for(i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    for(int j=0;j<m;j++)
        cout<<b[j]<<" ";
    cout<<endl;
*/
}

void solve(){
    int i,j;
    sort(a,a+n);
    ull temp=a[0];
    int cnt=1;
    int cnta=0;
    for(i=1;i<n;i++){
        if(a[i]!=a[i-1]){
            na[cnta].val=temp;
            na[cnta].cnt=cnt;
            cnt=1;
            temp=a[i];
            cnta++;
        }else
            cnt++;
    }
    na[cnta].val=temp;
    na[cnta].cnt=cnt;
    cnta++;

    sort(b,b+m);
    temp=b[0];
    cnt=1;
    int cntb=0;
    for(i=1;i<m;i++){
        if(b[i]!=b[i-1]){
            nb[cntb].val=temp;
            nb[cntb].cnt=cnt;
            cnt=1;
            temp=b[i];
            cntb++;
        }else
            cnt++;
    }
    nb[cntb].val=temp;
    nb[cntb].cnt=cnt;
    cntb++;

    cnt=0;
    ull a=0,b=0;
    for(i=0,j=0;i<cnta&&j<cntb;)
    {
//        cout<<i<<' '<<cnta<<' '<<na[i].val<<' '<<na[i].cnt<<endl;
//        cout<<j<<' '<<cntb<<' '<<nb[j].val<<' '<<nb[j].cnt<<endl;
//        cout<<endl;
        if(na[i].val>nb[j].val){
            b+=nb[j].cnt;
            j++;
        }else if(na[i].val<nb[j].val){
            a+=na[i].cnt;
            i++;
        }else{
            res[cnt++]=make_pair(na[i].cnt,nb[j].cnt);
            i++;j++;
        }
    }

    while(i<cnta){
        a+=na[i].cnt;
        i++;
    }

    while(j<cntb){
        b+=nb[j].cnt;
        j++;
    }

    sort(res,res+cnt,cmp);

    for(i=0;i<cnt;i++)
    {
        if(i%2==0)
            a+=res[i].first;
        else
            b+=res[i].second;
    }
//    cout<<a<<" "<<b<<endl;

    if(a>b) printf("Cuber QQ\n");
    else printf("Quber CC\n");
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        input();
        solve();
    }
}

1011 Kejin Player

题目链接
题意：给出n行输入，第i行表示从第i级升级到第i+1级别需要花费ai费用。对于升级有pi的概率表示可以成功，对于1-pi的概率失败会导致等级返回至xi级。q个询问，求从第a级到第b级需要多少费用期望。

思路：期望dp，设dp[i]为升级到第i级别所需要的费用，其等级为xi=i时

$dp[i+1]-dp[i]={-\frac{ai}{pi}}$

否则，可推出公式

$dp[i+1]-dp[i]={\frac{{(1-pi)}*{(dp[i-1]-dp[xi-1])}-{ai}}{pi}}$

可以通过前缀和维护

#include <bits/stdc++.h>

#define maxn 500005
typedef long long ll;
using namespace std;
const ll mod = 1000000007;

int n, q;
ll predif;
ll dif[maxn];//dp[i+1]-dp[i]
ll presum[maxn];

ll power_mod(ll a, ll b, ll m) {
    ll ans = 1;
    a %= m;
    while (b)
    {
        if (b & 1)ans = (ans*a) % m;
        a = (a*a) % m;
        b >>= 1;
    }
    return ans;
}//power_mod(b,m-2,m)

void input() {
    scanf("%d%d", &n, &q);
    int i;
    ll ri, si, xi, ai;
    presum[0] = 0;
    for (i = 1; i <= n; i++) {
        scanf("%lld%lld%lld%lld", &ri, &si, &xi, &ai);
        ll pi = ri * power_mod(si, mod - 2, mod) % mod;
        ll fpi = power_mod(pi, mod - 2, mod) % mod;
        if (xi == i) {
            dif[i] = -1ll * ai%mod;
            dif[i] = ((dif[i] * fpi )%mod-mod)%mod;
        }
        else {
            dif[i] = (((1 - pi) % mod*(presum[i - 1] - presum[xi-1]) % mod - ai) % mod ) % mod;
            dif[i] = ((dif[i] * fpi )%mod-mod)%mod;
        }
        presum[i] = ((presum[i - 1] + dif[i]) % mod - mod) % mod;
    }
}

void solve() {
    int i;
    int u, v;
    //    for(i=1;i<=n;i++)
    //        cout<<i<<' '<<dif[i]<<endl;
    for (i = 1; i <= q; i++) {
        scanf("%d%d", &u, &v);
        printf("%lld\n", -1ll * (((presum[v - 1] - presum[u - 1]) % mod-mod)%mod));
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        input();
        solve();
    }
}

Multi-University Contest 7

2019 Multi-University Training Contest 7

1001 A + B = C

1006 Final Exam

1010 Just Repeat

1011 Kejin Player