题目链接：https://vjudge.net/contest/147102#overview。
A题：给出一堆的点，要找出两条垂直的直线，一条与x轴呈45度。-->使得所有的点到任意一条直线的最短曼哈顿距离（具体见题意描述）的最大值最小。做法是先把坐标轴逆时针旋转45度，x'=(x-y)/sqrt2, y'=(x+y)/sqrt2。然后我们把最短曼哈顿距离和最短点到直线距离做个转化，求后者，然后乘sqrt2可以得到前者。因此最后的x'=x-y，y'=x+y。之后，二分答案mid，用一条竖着的线，管辖左右不超过mid距离的点，其他的点归横着的线管辖即可。具体做法见代码，用两条竖着的线去O(n)扫描即可。代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <set> 5 using namespace std; 6 const int N = 100000 + 5; 7 const int inf = 2e9; 8 typedef pair<int,int> pii; 9 10 int n; 11 pii p[N]; 12 int pre_min[N], aft_min[N], pre_max[N], aft_max[N]; 13 14 void init() 15 { 16 pre_min[1] = pre_max[1] = p[1].second; 17 for(int i=2;i<=n;i++) 18 { 19 pre_min[i] = min(pre_min[i-1], p[i].second); 20 pre_max[i] = max(pre_max[i-1], p[i].second); 21 } 22 aft_min[n] = aft_max[n] = p[n].second; 23 for(int i=n-1;i>=1;i--) 24 { 25 aft_min[i] = min(aft_min[i+1], p[i].second); 26 aft_max[i] = max(aft_max[i+1], p[i].second); 27 } 28 } 29 30 bool solve(double mid) 31 { 32 //if((double)(p[n].first-p[1].first) <= 2.0*mid) return 1; 33 int j = 1; 34 for(int i=1;i<=n;i++) 35 { 36 //int j = i + 1; 37 while(j <= n && 1.0*(p[j].first-p[i].first) <= 2.0*mid) j++; 38 if(i == 1 && j == n+1) return 1; 39 int maxx = -inf, minn = inf; 40 if(i > 1) 41 { 42 maxx = max(maxx, pre_max[i-1]); 43 minn = min(minn, pre_min[i-1]); 44 } 45 if(j <= n) 46 { 47 maxx = max(maxx, aft_max[j]); 48 minn = min(minn, aft_min[j]); 49 } 50 if(1.0*(maxx - minn) <= 2.0*mid) return 1; 51 //i = j; 52 } 53 return 0; 54 } 55 56 int main() 57 { 58 scanf("%d",&n); 59 for(int i=1;i<=n;i++) 60 { 61 int x,y; 62 scanf("%d%d",&x, &y); 63 p[i].first = x - y; 64 p[i].second = x + y; 65 } 66 sort(p+1,p+1+n); 67 init(); 68 double L = 0.0, R = inf; 69 int cnt = 100; 70 while(cnt--) 71 { 72 double mid = (L + R) / 2.0; 73 if(solve(mid)) R = mid; 74 else L = mid; 75 } 76 printf("%.15f ",R); 77 return 0; 78 }
B题，只要找出最高的不同的一位，从这一位到最低位全部变成1的对应的那个数字就是答案。
C题，矩阵快速幂，矩阵的（i，j）位置表示余数从i变成i变成j的方案数，然后对这个矩阵进行b的幂次即可。代码如下（下面的代码，因为我的矩阵模板不是从0开始的，然而余数有0的可能，因此全部位移加1）：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <math.h> 4 #include <vector> 5 #include <map> 6 #include <set> 7 #include <iostream> 8 #include <string.h> 9 using namespace std; 10 typedef long long ll; 11 typedef pair<int,int> pii; 12 const int mod = 1e9+7; 13 14 //int mod; 15 int n,b,k,x; 16 17 void add(int &a,int b) 18 { 19 a += b; 20 if(a < 0) a += mod; 21 //if(a >= mod) a -= mod; 22 a %= mod; 23 } 24 25 struct matrix 26 { 27 int e[100+5][100+5],n,m; 28 matrix() {} 29 matrix(int _n,int _m): n(_n),m(_m) {memset(e,0,sizeof(e));} 30 matrix operator * (const matrix &temp)const 31 { 32 matrix ret = matrix(n,temp.m); 33 for(int i=1;i<=ret.n;i++) 34 { 35 for(int j=1;j<=ret.m;j++) 36 { 37 for(int k=1;k<=m;k++) 38 { 39 add(ret.e[i][j],1LL*e[i][k]*temp.e[k][j]%mod); 40 } 41 } 42 } 43 return ret; 44 } 45 matrix operator + (const matrix &temp)const 46 { 47 matrix ret = matrix(n,m); 48 for(int i=1;i<=n;i++) 49 { 50 for(int j=1;j<=m;j++) 51 { 52 add(ret.e[i][j],(e[i][j]+temp.e[i][j])%mod); 53 } 54 } 55 return ret; 56 } 57 void getE() 58 { 59 for(int i=1;i<=n;i++) 60 { 61 for(int j=1;j<=m;j++) 62 { 63 e[i][j] = i==j?1:0; 64 } 65 } 66 } 67 }; 68 69 matrix qpow(matrix temp,int x) 70 { 71 int sz = temp.n; 72 matrix base = matrix(sz,sz); 73 base.getE(); 74 while(x) 75 { 76 if(x & 1) base = base * temp; 77 x >>= 1; 78 temp = temp * temp; 79 } 80 return base; 81 } 82 83 void print(matrix p) 84 { 85 int n = p.n; 86 int m = p.m; 87 for(int i=1;i<=n;i++) 88 { 89 for(int j=1;j<=m;j++) 90 { 91 printf("%d ",p.e[i][j]); 92 } 93 cout << endl; 94 } 95 } 96 97 int cnt[12]; 98 99 int main() 100 { 101 cin >> n >> b >> k >> x; 102 for(int i=1;i<=n;i++) {int t;scanf("%d",&t);cnt[t]++;} 103 matrix ans = matrix(x,x); 104 for(int i=1;i<=x;i++) 105 { 106 for(int j=1;j<=9;j++) 107 { 108 add(ans.e[i][((i-1)*10+j)%x+1], cnt[j]); 109 } 110 } 111 ans = qpow(ans,b); 112 cout << ans.e[1][k+1] << endl; 113 return 0; 114 }
D题，考虑到m<n/2，那么总会有一个点，不在不能建的边内，那么找出这个点，其他点全部连接它即可（即假边建图，找出度为0的点即可）。
E题，q次询问，每次找出[L, R]内，回文串的总个数。做法是区间dp。代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 const int N = 5000 + 5; 6 7 char s[N]; 8 int dp[N][N]; 9 int is[N][N]; 10 11 int main() 12 { 13 scanf("%s",s+1); 14 int n = strlen(s+1); 15 for(int i=1;i<=n;i++) {is[i][i] = dp[i][i] = 1;} 16 for(int len=2;len<=n;len++) 17 { 18 for(int i=1;i+len-1<=n;i++) 19 { 20 int j = i + len - 1; 21 is[i][j] = s[i] == s[j] && (i+1 <= j-1 ? is[i+1][j-1] : 1); 22 dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1] + is[i][j]; 23 } 24 } 25 int q; 26 scanf("%d",&q); 27 while(q--) 28 { 29 int l,r; 30 scanf("%d%d",&l,&r); 31 printf("%d ",dp[l][r]); 32 } 33 return 0; 34 }