Codeforces Round 8 (Div. 2)题解

A. Dalton the Teacher

题目大意

Dalton是一个班级的老师，这个班级有$n$个学生，分别使用1~n来代表这些学生。课室包含$n$张椅子，编号也是对应1 ~ n，一开始学生$i$坐在凳子$pi$,我们保证$p1$,$p2$,…,$pn$，是一个长度为$n$排列组合序列。
如果他/她的号码与他/她的椅子号码不同，学生就会感到高兴。为了让他所有的学生都高兴，道尔顿可以反复执行以下操作:选择两个不同的学生，交换他们的椅子。让所有学生满意的最少动作数是多少?我们可以证明，在这个问题的约束下，有可能用有限的移动次数让所有的学生都满意。
长度为n的排列是由n个不同的整数以任意顺序从1到n组成的数组。例如，[2,3,1,5,4]是一个排列，但[1,2,2]不是一个排列(2在数组中出现两次)，[1,3,4]也不是一个排列(n=3，但数组中有4)。

题解思路

代码

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<#x<<" = "<<x<<endl

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int ans=0;
        for(int i=1;i<=n;++i)
        {
            int shuru;
            scanf("%d",&shuru);
            if(shuru==i)ans++;
        }
        printf("%d\n",ans/2+ans%2);
    }
    return 0;
}

B. Longest Divisors Interval

题目大意

给定一个正整数n，求一个正整数区间[l,r]的最大值，使得对于区间内的每一个i(即l≤i≤r)， n是i的倍数。
给定两个整数l≤r，区间[l,r]的大小为r−l+1(即与属于该区间的整数个数重合)。

题解思路

如果一个数是区间[k+1,k+y]里面任意一个数的倍数，那么这个数一定是区间[1,y]里面任意一个数的倍数

代码

#include<bits/stdc++.h>
#include<math.h>
using namespace std;
#define debug(x) cout<<#x<<" = "<<x<<endl

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long n;
        scanf("%lld",&n);
        long long ans=0;
        //int m=(int)sqrt(n);
        for(long long i=1;i<=n;++i)
        {
            if(n%i==0)ans++;
            else break;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

C1. Dual (Easy Version)

题目大意

给定一个数组a1,a2，…，anof整数(正，负或0)。您可以对该数组执行多个操作(可能为0操作)。
在一个操作中，你选择i,j(1≤i,j≤n，它们可以相等)，并设置ai:=ai+aj(即(在ai后面加上aj)。
在最多50次操作中使数组不递减(即当1≤i≤n - 1时，ai≤ai+1)。您不需要最小化操作的数量。

题解思路

这道题目给的次数比较大，我们可以分类来进行处理，如果这里面的数字存在正整数，那么肯定可以把这些数字转化为正整数，那么我们只需要后面的数加前面的数就肯定能够符合条件，如果所有的数字都是负数，那我们只需要前面的数字加上后面的数字也肯定能够满足条件。还有一种情况全部都是0，那就直接输出0即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<#x<<" = "<<x<<endl

int main()
{
    int t;
    cin>>t;
    int cnt;
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int arr[30]{0};
        int maxzhi=-30,maxweizhi;
        int minzhi=+30,minweizhi;
        cnt=0;
        int a[50]{0};
        int b[50]{0};
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&arr[i]);
            if(arr[i]>maxzhi)
            {
                maxzhi=arr[i];
                maxweizhi=i;
            }
            if(arr[i]<minzhi)
            {
                minzhi=arr[i];
                minweizhi=i;
            }
        }
        if(maxzhi>0)
        {
            while(maxzhi<20)
            {
                maxzhi=2*maxzhi;
                arr[maxweizhi]*=2;
                a[cnt]=maxweizhi;
                b[cnt]=a[cnt];
                cnt++;
            }
            for(int i=1;i<=n;++i)
            {
                if(arr[i]<0)
                {
                    arr[i]+=maxzhi;
                    a[cnt]=i;
                    b[cnt]=maxweizhi;
                    cnt++;
                }
            }
            for(int i=2;i<=n;++i)
            {
                if(arr[i]<arr[i-1])
                {
                    arr[i]+=arr[i-1];
                    //printf("%d %d\n",i,i-1);
                    a[cnt]=i;
                    b[cnt]=i-1;
                    cnt++;
                }
            }
        }
        else if(minzhi<0)
        {
            while(minzhi>-20)
            {
                minzhi+=minzhi;
                a[cnt]=minweizhi;
                b[cnt]=minweizhi;
                cnt++;
            }
            for(int i=n-1;i>=1;--i)
            {
                if(arr[i]>arr[i+1])
                {
                    while(arr[i]>arr[i+1])
                    {
                        arr[i]+=arr[i+1];
                        a[cnt]=i;
                        b[cnt]=i+1;
                        cnt++;
                    }
                }
            }
        }
        printf("%d\n",cnt);
        for(int i=0;i<cnt;++i)
        {
            printf("%d %d\n",a[i],b[i]);
        }
    }
    return 0;
}