A，水题不多说。
#include<bits/stdc++.h> using namespace std; //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif int n,t; scanf("%d%d",&n,&t); if(t<10){ for(int i = n; i--;) putchar('0'+t); }else{ if(n == 1) puts("-1"); else{ putchar('1'); for(int i = n; --i;) putchar('0'); } } return 0; }
B，用补集算一下。
#include<bits/stdc++.h> using namespace std; const int mod = 1e9+7; typedef long long ll; int qpow(int a,int q) { int re = 1; while(q){ if(q&1) re = (ll)re*a%mod; a = (ll)a*a%mod; q >>= 1; } return re; } //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif int n; scanf("%d",&n); int ans = (qpow(27,n)-qpow(7,n)+mod)%mod; printf("%d",ans); return 0; }
C，当s1[i] != s2[i]的时候至少其中f值+1，效果记为10，01，11（与s1[i]和s2[i]都不同）
s1[i] == s2[i]的时候效果记为11 00。
记s[i] != s[i]有ct1个，为了保证两个f相等如果ct是奇数，单出来那个只有使得f1,f2同时加1，所以下界为low = (ct+1)/2。
其中有ct/2个对10，01 。当t<low的时候无解。
记s1[i]==s2[i]有ct2 = n-ct1个，当t>=low && t <= low+ct2的时候，只要在s1[i]==s2[i]时取相应个数个的ch，ch !=s1[i]。(11)
当t>=low+ct2的时候，需要从ct/2对中选出一些来变成 11，11
#include<bits/stdc++.h> using namespace std; const int LEN = 1e5+5; char s[2][LEN]; //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif int n,t; scanf("%d%d ",&n,&t); gets(s[0]); gets(s[1]); int ct1 = 0; for(int i = 0; i < n; i++){ ct1 += s[0][i] == s[1][i]; } int ct2 = n-ct1; int low = (ct2+1)/2; if(t < low){ puts("-1"); }else { int pir = low - (ct2&1); int del = t - low - ct1; int swc = 0, ct, ex; if(del > 0) { ex = ct1; ct = (pir - del)*2; }else { ct = (pir)*2; ex = t - low; } for(int i = 0; i < n; i++){ if(s[0][i] != s[1][i]){ if(ct){ //控制 01 ct--; putchar(s[swc ^= 1][i]); }else { for(char c = 'a'; c <= 'z'; c++){ if(c != s[0][i] && c != s[1][i]) { putchar(c); break; } } } }else { if(ex){ //控制11 ex--; for(char c = 'a'; c <= 'z'; c++){ if(c != s[0][i] && c != s[1][i]) { putchar(c); break; } } }else { putchar(s[0][i]); } } } } return 0; }
D，暴力，有个事实是1e9以内的的素数间隔不超过282，sqrt（N）判断一下就好了。
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5+5; int Prim[maxn], sz ; bool vis[maxn]; void seive(int n = maxn-5) { int m = (int)sqrt(n+0.5); for(int i = 2; i <= m; i++){ if(!vis[i]) for(int j = i*i; j <= n; j += i){ vis[j] = true; } } for(int i = 2; i <= n; i++){ if(!vis[i]) Prim[sz++] = i; } } bool chkPrime(int x) { int m = (int)sqrt(x+0.5); for(int i = 0; Prim[i] <= m; i++){ if(x%Prim[i] == 0) return false; } return true; } //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif seive(); int n; scanf("%d",&n); if(chkPrime(n)){ puts("1"); printf("%d",n); }else if(chkPrime(n-2)){ puts("2"); printf("%d %d",2,n-2); }else { puts("3"); for(int i = 4; ; i += 2){ if(chkPrime(n-i)){ printf("%d ",n-i); n = i; break; } } for(int i = 0; Prim[i] <= n; i++){ if(chkPrime(n-Prim[i])){ printf("%d %d",Prim[i],n-Prim[i]); break; } } } return 0; }
E，问交换的最小花费。看成一个置换环，最优的交换就是不断消去端点，但是这样不太好写。
一般两个排列问相对关系都可以把其中一个做映射会方便处理。把序列b映射成1...n，把a按照相同规则映射，并记录映射后元素x的位置。
从小的元素枚举，找到它在序列中的位置p[x]，小的要往左边走，判断一下左边的元素是不是要往大于p[x]的位置走。如果是就交换。
p[x]的位置前面一定会有一个不小于p[x]的元素。
#include<bits/stdc++.h> using namespace std; const int maxn = 2001; int mp[maxn]; int a[maxn],p[maxn]; #define PB push_back #define MP make_pair #define fi first #define se second //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif int n; scanf("%d",&n); for(int i = 1; i <= n; i++){ scanf("%d",a+i); } for(int i = 1; i <= n; i++){ int x; scanf("%d",&x); mp[x] = i; } for(int i = 1; i <= n; i++){ p[ a[i] = mp[a[i]] ] = i; } int c = 0; for(int x = 1; x <= n; x++){ for(int j = p[x]; --j>=x ; ){ if(a[j] >= p[x]){ c += p[x] - j; swap(a[j],a[p[x]]); ans.PB(MP(j,p[x])); p[a[j]] = p[x]; p[x] = j; } } } printf("%d ",c); printf("%d ",(int)ans.size()); for(auto i: ans){ printf("%d %d ",i.fi,i.se); } return 0; }