usaco 铜 第三题题解

· · 个人记录

这篇题解是备用的（等到洛谷有了这一题再提交）

其实这两个代码是我比赛时写的

题目链接：[USACO2020二月]交换

审题

这道题的题目要求是让我们反复交换两个区间的数字。

最先想到的方法应该就是模拟了

模拟实现

我这题全部用的是数组（先声明一下）

我们可以先写一个函数来交换区间的数字，具体思路是从区间两头开始一一交换，一直到中间。

代码：

void rever(int x,int y){
    int xianzaif=0;//先把要交换的数字区间复制到一个专门用于交换的数组（其实是方便调试）
    for(int i=x;i<=y;i++){
        fuz[xianzaif]=a[i];
        xianzaif++;
    }
    int temp = 0;
    int n =abs(y-x);
    for (int i = 0; i < n/2; ++i) {
        temp = fuz[n-i-1];//从两头开始互换位置
        fuz[n-i-1] = fuz[i];
        fuz[i] = temp;
    }
    xianzaif=0;
    for(int i=x;i<=y;i++){
        a[i]=fuz[xianzaif];//再把它复制回去
        xianzaif++;
    }
}

然后呢？

当然是按照题目要求一一交换啊！

主函数再加上一重for循环

搞定！

但是交上去之后，有一半的点却出现了TLE...

再回去看数据范围：(1≤K≤10^9)

这说明这道题其实还可以继续优化

标准TLE代码：

#include<bits/stdc++.h>
using namespace std;
int a[105]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101};
//这是牛的初始编号（最多一百只）
int fuz[105];
void rever(int x,int y){//上文说过原理啦，略过
    int xian=0;
    for(int i=x;i<=y;i++){
        fuz[xian]=a[i];
        xianzaif++;
    }
    int temp = 0;
    int n =abs(y-x);
    for (int i = 0; i < n/2; ++i) {
        temp = fuz[n-i-1];
        fuz[n-i-1] = fuz[i];
        fuz[i] = temp;
    }
    xian=0;
    for(int i=x;i<=y;i++){
        a[i]=fuz[xian];
        xian++;
    }
}
int main(){
    //温馨提醒：USACO比赛时一定要写文件读写哦~
    //freopen("swap.in","r",stdin);
    //freopen("swap.out","w",stdout);
    int n,k;
    cin>>n>>k;
    int c,d;
    int a1,a2,b1,b2;
    cin>>a1>>a2>>b1>>b2;
    for(int i=1;i<=k;i++){
        rever(a1,a2+1);//按照题目要求交换
        rever(b1,b2+1);
    }
    printf("%d",a[1]);
    for(int i=2;i<=n;i++){
        printf("\n%d",a[i]);//输出
    }
    return 0;
}

优化方案

其实我们总结一下就会发现： 每组数据在进行几次交换后都会回到原来的位置（有点像小学奥数）

所以我们可以去判断什么时候会回到原来的位置

具体代码：

bool pand(int z){//如果全部数字再次从小到大排列就说明重复了一次
    int ans=0;
    for(int i=1;i<=z;i++){
        if(a[i]==i)ans++;
    }
    if(ans==z)return true;
    else return false;
}

当重复点找到后，我们可以对k进行取模，然后再执行取模结果次就可以了！

正解

完整代码：

#include<bits/stdc++.h>
using namespace std;
int a[105]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101};
int fuz[105];
//和上文一样
bool pand(int z){解释过了
    int ans=0;
    for(int i=1;i<=z;i++){
        if(a[i]==i)ans++;
    }
    if(ans==z)return true;
    else return false;
}
void rever(int x,int y){//也和上文一样
    int xianzaif=0;
    for(int i=x;i<=y;i++){
        fuz[xianzaif]=a[i];
        xianzaif++;
    }
    int temp = 0;
    int n =abs(y-x);
    for (int i = 0; i < n/2; ++i) {
        temp = fuz[n-i-1];
        fuz[n-i-1] = fuz[i];
        fuz[i] = temp;
    }
    xianzaif=0;
    for(int i=x;i<=y;i++){
        a[i]=fuz[xianzaif];
        xianzaif++;
    }
}
int main(){
    //比赛时要写文件读写
    //freopen("swap.in","r",stdin);
    //freopen("swap.out","w",stdout);
    int n,k;
    cin>>n>>k;
    int c,d;//输入数据
    int a1,a2,b1,b2;
    cin>>a1>>a2>>b1>>b2;
    for(int i=1;i<=k;i++){
        rever(a1,a2+1);
        rever(b1,b2+1);//交换区间内的数
        if(pand(n)==true){//当完成了一个周期
            int sheng=k%i;//将k取模于i
            for(int j=1;j<=sheng;j++){//再循环交换几次
                rever(a1,a2+1);
                rever(b1,b2+1);
            }
            printf("%d",a[1]);
            for(int i=2;i<=n;i++){
                printf("\n%d",a[i]);//直接输出
            }
            return 0;//结束程序
        }
    }
    printf("%d",a[1]);//如果全部循环完毕后还没有出现周期
    for(int i=2;i<=n;i++){
        printf("\n%d",a[i]);
    }//再输出
    return 0;
}