快速竞技#4

A–Duff and Meat588A

= =这题不知道怎么写题解了。。

直接上code……….

#include<bits/stdc++.h>

#include<string.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

const double eps=1e-5;

const double pi=acos(-1.0);

const int mod=1e8+7;

const LL INF=0x3f3f3f3f;

const int N=1e3+10;

int main()

{

    int n;

    int x,a,b;

    x=INF;

    scanf("%d",&n);

    int ans=0;

    for(int i=0;i<n;i++)

    {

        scanf("%d%d",&a,&b);

        if(b<x)

            x=b;

        ans+=a*x;

    }

    printf("%d\n",ans);

    return 0;

}

B——-Duff in Love588A

lovely number.:不能整除一个a^2(a>1)。

给出一个N(<=10^12)，在他的因子里，求一个最大的lovely number.

思路:

不含平方因子就是说一种因子只能存在一个，所以说分解质因子然后一种因子取一个就好了。

学到一波：分解质因数；可以求所有质因数哟~~~

for(LL i=2;i*i<=n;i++)

{

if(n%i==0){

ans*=i;

while(n%i==0)

n/=i;

}

if(n==1)

break;

}

code………..

#include<bits/stdc++.h>

#include<string.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

const double eps=1e-5;

const double pi=acos(-1.0);

const int mod=1e8+7;

const LL INF=0x3f3f3f3f;

const int N=1e6+10;

int d[N];

int main()

{

    int u,v;

    LL n;

    LL ans=1;

    scanf("%I64d",&n);

    for(LL i=2;i*i<=n;i++)

    {

        if(n%i==0){

            ans*=i;

            while(n%i==0)

                n/=i;

        }

        if(n==1)

            break;

    }

    if(n>1)

        ans*=n;

    printf("%I64d\n",ans);

    return 0;

}

F： 584C - Marina and Vasya

题意：

求一个字符串和s1，s2有t个不同；

思路：

直接搞；还是蛮清楚的构造。

code…………..

#include<bits/stdc++.h>

#include<string.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

const double eps=1e-5;

const double pi=acos(-1.0);

const int mod=1e8+7;

const LL INF=0x3f3f3f3f;

const int N=1e5+10;

char s1[N],s2[N],ans[N];

bool status[N];

char kill(char a,char b)

{

    for(int i='a';i<='z';i++)

    {

        if(i!=a&&i!=b)

            return i;

    }

}

int main()

{

    int n,t,sum;

    scanf("%d%d",&n,&t);

    scanf("%s%s",s1,s2);

    sum=0;

    memset(status,0,sizeof(status));

    for(int i=0;i<n;i++)

    {

        if(s1[i]!=s2[i])

            sum++;

        else

            status[i]=1;

    }

    if(sum==t)

    {

        for(int i=0;i<n;i++)

        {

            if(status[i])

                ans[i]=s1[i];

            else

                ans[i]=kill(s1[i],s2[i]);

        }

    }

    else if(sum<t){     //补齐t-sum;

        int cnt=0;

        for(int i=0;i<n;i++)

        {

            if(status[i])

            {

                if(cnt<(t-sum))

                {

                    ans[i]=kill(s1[i],s2[i]);

                    cnt++;

                }

                else

                    ans[i]=s1[i];

            }

            else

                ans[i]=kill(s1[i],s2[i]);

        }

    }

    else{                       //不同的多了t-sum

        int cnt1=0,cnt2=0;      //把两个串都补齐，可能补不齐，所以最后还要判断。

        for(int i=0;i<n;i++)

        {

            if(status[i])

                ans[i]=s1[i];

            else

            {

                if(cnt1<(sum-t))

                {

                    ans[i]=s1[i];

                    cnt1++;

                }

                else if(cnt2<(sum-t))

                {

                    ans[i]=s2[i];

                    cnt2++;

                }

                else

                    ans[i]=kill(s1[i],s2[i]);

            }

        }

    }

    int sum1=0,sum2=0;

    for(int i=0;i<n;i++)

    {

        if(s1[i]!=ans[i])

            sum1++;

        if(s2[i]!=ans[i])

            sum2++;

    }

    if(sum1!=t||sum2!=t)

    {

        puts("-1");

        return 0;

    }

    ans[n]='\0';

    printf("%s",ans);

    return 0;

}