首页 > 代码库 > Codeforces Round #246 (Div. 2)

Codeforces Round #246 (Div. 2)

2024-07-05 12:01:31   239人阅读

C 这题说的是给了一个数列然后通过交换得到有序的数组 数列中的数只有满足距离j-i+1 为素数的时候才可以交换然后 根据哥德巴赫猜想就可以知道数之间的关系 然后通过交换得到他们的值，这里犯了一个严重的错误就是在计算的时候L[a[i]] 与 L[i] 的地址交换了 但是是 a[i] 与a[L[i]] 的值却没有发生交换导致了 一直wa 要知道是通过值得下标值去访问地址的然后就可以得到要的地址 只交换了地址却没有交换值  记住这个错误

#include <iostream>
#include<string.h>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn = 100005;
int a[maxn+5],L[maxn+5],prime[maxn+5],numPrime,X[maxn*5+5],Y[maxn*5+5],n,num;
bool vis[maxn*10];
void inti(){
   int m = (int)sqrt(maxn + 0.5);
    memset(vis,false,sizeof(vis));
    vis[1]=true;
     for(int i = 2; i <= m; ++ i)
        if(vis[i] == false)
            for(int j = i * i; j <= maxn+100; j += i)
                vis[j] = true;

}
void look(int &a,int &b,int G){
      int t1;
      t1=G/2;
      while(true){
        if(vis[t1]==0&&vis[G-t1]==0) break;
        t1--;
      }
      a=t1;
      b=G-t1;
}
void jud(int a,int b){

   if(a<b){
      X[num]=a; Y[num]=b;
   }
   else{
      X[num]=b; Y[num]=a;
   }
   num++;
}
int main()
{


    inti();
   while( scanf("%d",&n)==1){
         num=0;
    for(int i=1;i<=n; ++i){
        scanf("%d",&a[i]);
        L[a[i]]=i;
    }
    for(int i =1 ;i<= n ; ++i){
        if(L[i]==i) continue;
        int L1 = L[i];
        int L2 = i;

        L[a[i]]=L[i];
        L[L2] =L2;
        int tt=a[i];
        a[i]=i;
        a[L1]=tt;
        if(vis[L1-L2+1]==0){
            jud(L2,L1);
            continue;
        }
        if((L1-L2)&1){
           int aa,bb;
           look(aa,bb,L1-L2+1);
           int L3=L2+1;
           int L4=L3-1+aa;
            jud(L2,L3);
            jud(L3,L4);
            jud(L4,L1);
            jud(L3,L4);
            jud(L2,L3);
        }
        else{
            int aa,bb;
            look(aa,bb,L1-L2+2);
            int L3=L2+aa-1;
            jud(L2,L3);
            jud(L3,L1);
            jud(L2,L3);
        }
     }
      printf("%d\n",num);
      for(int i=0;i<num; ++i)
        printf("%d %d\n",X[i],Y[i]);
    }
    return 0;
}
Viewdfdf　　　　　　　　　　


联系
我们