主题链接：

本场比赛他们拿出前两分钟后，C。

。

不是真的很有趣。

A：简单统计。时间复杂度：O(N)

#include
    
     #include
     
      #include
      
       using namespace std;const int N = 2010;int a[N];int main(){    int n, k;    scanf("%d%d", &n, &k);    int cnt = 0;    for(int i = 0; i < n; ++i){        int x;        scanf("%d", &x);        if(5 - x >= k) ++cnt;    }    printf("%d\n", cnt / 3);    return 0;}
      
     
    

#include
    
     #include
     
      #include
      
       using namespace std;const int N = 1e5 + 10;int a[N], b[N];int x[N];int main(){    int n, k;    scanf("%d", &n);    for(int i = 0; i < n; ++i){        scanf("%d%d", &a[i], &b[i]);        ++x[a[i]];    }    for(int i = 0; i < n; ++i){        int ans = n - 1 + x[b[i]];        if(a[i] == b[i]) ans -= 1;        printf("%d %d\n", ans, n*2 - 2 - ans);    }    return 0;}
      
     
    

YY了一个定理：随意一个数都能够由最多5个质数的和表示（原来是哥德巴赫猜想：囧）， 刚好最大操作个数<=5*n。

这样先预处理出全部的素数。 每次二分素数， 推断并进行交换。  时间复杂度：O(N*sqrt(N))

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int N = 1e6 + 1;bool isPrime[N];int a[N], prime[N];int p[N];int cnt;int x[N], y[N];void gao(){	int k = sqrt(N*1.0);	int i = 2;	while(i <= k){		for(int j = i*i; j < N; j += i) isPrime[j] = 1;		++i;		while(i <= k && isPrime[i]) ++i;	}	for(int i = 2; i < N; ++i){		if(!isPrime[i]) prime[cnt++] = i;	}}int foo(int k){	int l = 0, r = cnt - 1;	while(l < r){		int m = (l + r + 1) >> 1;	//	printf("m = %d\n", m);		if(prime[m] <= k) l = m;		else r = m - 1;	}	return l;}int main(){	int n;	scanf("%d", &n);	gao();//	for(int i = 0; i < 30; ++i) printf("%d  ", prime[i]);	for(int i = 1; i <= n; ++i){		scanf("%d", &a[i]);		p[a[i]] = i;	} //   foo(3);	int ans = 0;	for(int i = 1; i <= n; ++i){		int dif = abs(p[i] - i) + 1;		if(p[i] > i){			int tmp = dif;			int xx = p[i], yy = i;			while(tmp != 0){	//			printf("%d en\n", tmp);				int k = foo(tmp);		//		printf("%d\n",foo(tmp));				x[ans] = xx, y[ans] = xx - prime[k] + 1;				p[a[y[ans]]] = xx;				swap(a[xx], a[y[ans]]);			    tmp -= prime[k];				if(tmp != 0) tmp += 1;				xx = y[ans++];			}		}		else if(i > p[i]){			int tmp = dif;			int xx = p[i], yy = i;			while(tmp != 0){				int k = foo(tmp);				x[ans] = xx, y[ans] = xx + prime[k] - 1;				p[a[y[ans]]] = xx;				swap(a[xx], a[y[ans]]);			    tmp -= prime[k];				if(tmp) ++tmp;				xx = y[ans++];			}		}	}	printf("%d\n", ans);	for(int i = 0; i < ans; ++i){		if(x[i] < y[i]) printf("%d %d\n", x[i], y[i]);		else  printf("%d %d\n", y[i], x[i]);	}	return 0;}