题目链接：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)扫描即可。代码如下：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <set>
using namespace std;
const int N = + ;
const int inf = 2e9;
typedef pair<int,int> pii; int n;
pii p[N];
int pre_min[N], aft_min[N], pre_max[N], aft_max[N]; void init()
{
pre_min[] = pre_max[] = p[].second;
for(int i=;i<=n;i++)
{
pre_min[i] = min(pre_min[i-], p[i].second);
pre_max[i] = max(pre_max[i-], p[i].second);
}
aft_min[n] = aft_max[n] = p[n].second;
for(int i=n-;i>=;i--)
{
aft_min[i] = min(aft_min[i+], p[i].second);
aft_max[i] = max(aft_max[i+], p[i].second);
}
} bool solve(double mid)
{
//if((double)(p[n].first-p[1].first) <= 2.0*mid) return 1;
int j = ;
for(int i=;i<=n;i++)
{
//int j = i + 1;
while(j <= n && 1.0*(p[j].first-p[i].first) <= 2.0*mid) j++;
if(i == && j == n+) return ;
int maxx = -inf, minn = inf;
if(i > )
{
maxx = max(maxx, pre_max[i-]);
minn = min(minn, pre_min[i-]);
}
if(j <= n)
{
maxx = max(maxx, aft_max[j]);
minn = min(minn, aft_min[j]);
}
if(1.0*(maxx - minn) <= 2.0*mid) return ;
//i = j;
}
return ;
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
int x,y;
scanf("%d%d",&x, &y);
p[i].first = x - y;
p[i].second = x + y;
}
sort(p+,p++n);
init();
double L = 0.0, R = inf;
int cnt = ;
while(cnt--)
{
double mid = (L + R) / 2.0;
if(solve(mid)) R = mid;
else L = mid;
}
printf("%.15f\n",R);
return ;
}
B题，只要找出最高的不同的一位，从这一位到最低位全部变成1的对应的那个数字就是答案。
C题，矩阵快速幂，矩阵的（i，j）位置表示余数从i变成i变成j的方案数，然后对这个矩阵进行b的幂次即可。代码如下（下面的代码，因为我的矩阵模板不是从0开始的，然而余数有0的可能，因此全部位移加1）：
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
#include <set>
#include <iostream>
#include <string.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod = 1e9+; //int mod;
int n,b,k,x; void add(int &a,int b)
{
a += b;
if(a < ) a += mod;
//if(a >= mod) a -= mod;
a %= mod;
} struct matrix
{
int e[+][+],n,m;
matrix() {}
matrix(int _n,int _m): n(_n),m(_m) {memset(e,,sizeof(e));}
matrix operator * (const matrix &temp)const
{
matrix ret = matrix(n,temp.m);
for(int i=;i<=ret.n;i++)
{
for(int j=;j<=ret.m;j++)
{
for(int k=;k<=m;k++)
{
add(ret.e[i][j],1LL*e[i][k]*temp.e[k][j]%mod);
}
}
}
return ret;
}
matrix operator + (const matrix &temp)const
{
matrix ret = matrix(n,m);
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
add(ret.e[i][j],(e[i][j]+temp.e[i][j])%mod);
}
}
return ret;
}
void getE()
{
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
e[i][j] = i==j?:;
}
}
}
}; matrix qpow(matrix temp,int x)
{
int sz = temp.n;
matrix base = matrix(sz,sz);
base.getE();
while(x)
{
if(x & ) base = base * temp;
x >>= ;
temp = temp * temp;
}
return base;
} void print(matrix p)
{
int n = p.n;
int m = p.m;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
printf("%d ",p.e[i][j]);
}
cout << endl;
}
} int cnt[]; int main()
{
cin >> n >> b >> k >> x;
for(int i=;i<=n;i++) {int t;scanf("%d",&t);cnt[t]++;}
matrix ans = matrix(x,x);
for(int i=;i<=x;i++)
{
for(int j=;j<=;j++)
{
add(ans.e[i][((i-)*+j)%x+], cnt[j]);
}
}
ans = qpow(ans,b);
cout << ans.e[][k+] << endl;
return ;
}
D题，考虑到m<n/2，那么总会有一个点，不在不能建的边内，那么找出这个点，其他点全部连接它即可（即假边建图，找出度为0的点即可）。
E题，q次询问，每次找出[L, R]内，回文串的总个数。做法是区间dp。代码如下：
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = + ; char s[N];
int dp[N][N];
int is[N][N]; int main()
{
scanf("%s",s+);
int n = strlen(s+);
for(int i=;i<=n;i++) {is[i][i] = dp[i][i] = ;}
for(int len=;len<=n;len++)
{
for(int i=;i+len-<=n;i++)
{
int j = i + len - ;
is[i][j] = s[i] == s[j] && (i+ <= j- ? is[i+][j-] : );
dp[i][j] = dp[i][j-] + dp[i+][j] - dp[i+][j-] + is[i][j];
}
}
int q;
scanf("%d",&q);
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",dp[l][r]);
}
return ;
}