标题

Educational Codeforces Round 89 (Rated for Div. 2)

A Shovels and Swords

题意

制造一铲子需要2棍子1钻石，制造一把剑需要2钻石1棍子。它们都可以卖一翡翠，有a棍子b钻石，问可以卖多少钻石？

题解

#include <bits/stdc++.h>
using namespace  std;
const int maxn=2e5+10;
int main()
{
    int t,a,b;
    cin >> t;
    while(t--)
    {
        cin >> a >> b;
        if(a>2*b)
            printf("%d\n",b);
        else if(2*a<b)
            printf("%d\n",a);
        else
            printf("%d\n",(a+b)/3);
    }
}

B Shuffle

题意

给你一个长度为n的数组a，其中第x位为1其他为0，你可以操作m次，每次可以交换下标为li至ri之间的任意两个元素。问最后1可以在几个位置？

题解

当1在操作过程之中可以到达位置p，那么最后1就可以在位置p

#include <bits/stdc++.h>
using namespace  std;
const int maxn=2e5+10;
int main()
{
    int t,i,j,n,m,x,l,r;
    cin >> t;
    while(t--)
    {
        cin >> n >> x >> m;
        int nowl=x,nowr=x;
        for(i=1;i<=m;i++)
        {
            scanf("%d %d",&l,&r);
            if(nowl>=l && nowl<=r || nowr>=l && nowr<=r)
            {
                nowr=max(nowr,r);
                nowl=min(nowl,l);
            }
        }
        printf("%d\n",nowr-nowl+1);
    }
}

C Palindromic Paths

题意

给定一个n*mn∗m的0101矩阵，一个人从(1,1)出发到达(n,m)，只能向右或者向下。现在要他走过的路径会形成一个01串，求最少改变多少个位置的值，使得这个人走过的所有路径形成的串都是回文串。

题解

算出每一个位置离（1，1），（n,m)哪个近，num[近的距离][a[i][j]]++。遍历距离，距离i对答案的贡献为min(num[i][0],num[i][1])

#include <bits/stdc++.h>
using namespace  std;
const int maxn=2e5+10;
int main()
{
    int t,i,j,n,m,a[50][50],num[100][2];
    cin >> t;
    while(t--)
    {
        cin >> n >> m;
        memset(num,0,sizeof(num));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
                if(i+j-2>n-i+m-j)
                    num[n-i+m-j][a[i][j]]++;
                else if(i+j-2<n-i+m-j)
                    num[i+j-2][a[i][j]]++;
            }
        }
        int res=0;
        for(i=0;i<=(n+m-2)/2;i++)
        {
            res+=min(num[i][0],num[i][1]);
        }
        cout << res << endl;
    }
}

D Two Divisors

题意

给你一个数n，让你给出两个n的因子，要求他们的和与n的gcd=1，如果不存在则输出-1 -1

题解

找两个大于1且互质的因子即可

#include <bits/stdc++.h>
using namespace  std;
const int maxn=1e7+10;
bool prime[maxn];
int mp[maxn],res[maxn][3];
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int main()
{
    int n,i,j;
    for(i=1;i<=maxn;i++)
        prime[i]=true;
    prime[1]=false;
    for(i=2;i<=maxn;i++)
        mp[i]=i;
    for(i=2;i<=sqrt(maxn);i++)
    {
        if(prime[i]==true)
        {
            for(j=2*i;j<=maxn;j+=i)
            {
                prime[j]=false;
                mp[j]=min(mp[j],i);
            }
        }
    }
    cin >> n;
    for(i=1;i<=n;i++)
    {
        int x,d1=1,d2;
        scanf("%d",&x);
        int temp=x;
        int tmp=mp[x];
        while(x%tmp==0)
        {
            d1=d1*tmp;
            x/=tmp;
            if(x==0)break;
        }
        d2=temp/d1;
        if(d1>1 && d2 >1)
            res[i][1]=d1,res[i][2]=d2;
        else
            res[i][1]=-1,res[i][2]=-1;
    }
    for(i=1;i<=n;i++)
        printf("%d ",res[i][1]);
    printf("\n");
    for(i=1;i<=n;i++)
        printf("%d ",res[i][2]);
    return 0;
}