T1 字符串
小X十分热爱学习。有一天，他刚学完“漂亮的k字符串”的概念：给定长度为n的字符串和整数k，k能整除n，如果该字符串满足以下两个条件：
- s是一个回文串，即对于任意1≤i≤n，Si=Sn+1-i（其中Si表示字符串中第i个字母）
- s以k为周期，即对于任意1≤i≤n-k, Si=Sk+i（其中Si表示字符串中第i个字母）
就称该字符串为“漂亮的k字符串“。
比如说“abaaba“就是一个漂亮的3字符串，而”abccba“则不是。
小Y是小X 的同学，她对“漂亮的K字符串”也很感兴趣，她有一些字符串，每个字符串都是由小写字母构成，并且对于每个字符串她都会给出一个k，想让小X帮自己把该字符串修改成“漂亮的k字符串”。小Y可以选择任意位置的字母并将他们改成任意其他小写字母。由于小Y的字符串又长又多，小X又想在小Y前表现自己，在1s内把每个字符串修改为“漂亮的k字符串”，于是就请你来帮忙求出每个字符串最少需要修改多少字符才能成为“漂亮的k字符串”。
分析该字符串的性质，我们可以发现要满足上述性质的字符串必须满足两点：
对于任意 \([n(k - 1) + 1, ~ nk + 1]\) 的子串 \(S\)，必须满足 \(S_{i} = S_{k - i + 1}\)。
对于所有的串 \(S_i(1 \le i \le \frac{n}{k})\)，第 \(t\) 个字符满足 \(S_{i,t} = S_{j,t}(i \ne j)\)。
综上，我们可以得出上述的字符可以划分为若干个不相交的集合，对于每个集合中的元素，我们考虑求出所有字符变为同一个字符需要的最少次数，累加即可。
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k, sum;
int cnt[26];
char s[N];
void solve()
{
cin >> n >> k;
cin >> s + 1;
int ans = 0;
for (int i = 1; i <= (k + 1) >> 1; i ++ )
{
int sum = 0, res = 1e9;
for (int j = 0; j < 26; j ++ ) cnt[j] = 0;
for (int j = i; j <= n; j += k) cnt[s[j] - 'a'] ++ , sum ++ ;
if (i != k / 2 + 1) for (int j = k - i + 1; j <= n; j += k) cnt[s[j] - 'a'] ++ , sum ++ ;
for (int j = 0; j < 26; j ++ ) res = min(sum - cnt[j], res);
ans += res;
}
cout << ans << endl;
}
int main()
{
int T;
cin >> T;
while (T -- ) solve();
return 0;
}
T2 抓
小X这天兴致勃勃的要跑去小Y家玩。在他向小Y家行走了t秒后，小Y这时得知小X要来他家玩，认为上周小X弄丢自己作业后没有道歉是非常不对的，于是怒火中烧，要抓住小X让他给自己道歉。小X也突然意识到上周自己刚把小Y的作业弄丢，于是放弃去往小Y家，开始逃跑。
小X和小Y居住的城市有n个小区，这些小区由n-1条双向道路连接起来，每两个小区之间都可以通过这n-1条道路中的某几条到达，并且每条道路的长度只有1m。小X住在1号小区，小Y住在n号小区。小X的跑步速度为1m/s（在小Y开始抓小X时，小X既可以选择跑向和当前小区有道路的小区，也可以选择原地不动），而小Y的跑步速度为2m/s。并且小Y对整个城市和小X都十分了解，每时每刻都在以最短的路径跑向小X。小X想要让小Y尽可能晚的抓到自己，因为时间越长小Y越不愤怒，这样他就能获得小Y的原谅了。你能帮小X计算出从小Y出发抓小X最长经过几秒后抓住小X吗？
第一行包括两个整数n(3≤n≤105)，t（1≤t≤n-1）,分别表示小区个数和最开始经过了t秒后小Y出发抓小X。
接下来n-1行每行包含两个整数x(1≤x≤n),y(1≤y≤n)表示第x和第y个小区之间有一条长度为1m的双向道路。
对于100%的数据， 3≤n≤10^5, 1≤t≤n-1且t小于1号小区到n号小区的距离。
我们需要先求出 \(t\) 秒后小X的位置，才能够进行下一步判断，考虑从 \(1\) 和 \(n\) 分别跑一次最短路，记小Y为起点的最短路为 \(dist1\)，小X为起点的最短路为 \(dist2\)，那么经过 \(t\) 秒后的节点 \(u\) 一定满足 \(dist1[i] + t = dist1[1]\) 且 \(dist2[i] - t = 0\)，因为 \(u\) 在 \(1 \to n\) 的路径上，所以两者需要都满足才可以。
我们求出 \(u\) 后，考虑重新求 \(u\) 为起点的最短路，替换原来的 \(dist2\)，考虑小X能达到的地方必定满足 \(dist1[i] \ge dist2[i] \times 2\)，否则小Y可以比小X先到达目的地，小X在途中就会被抓，对于合法的目的地，求出小Y到目的地的时间的最大值即可。
参考代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, t, ans;
int h[N], e[N << 1], ne[N << 1], idx;
int st[N], dist1[N], dist2[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra(int S, int dist[])
{
memset(st, 0, sizeof st);
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, S}), dist[S] = 0;
while (heap.size())
{
auto t = heap.top();
heap.pop();
int u = t.second, distance = t.first;
if (st[u]) continue;
st[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + 1)
{
dist[j] = distance + 1;
heap.push({dist[j], j});
}
}
}
}
int main()
{
cin >> n >> t;
memset(h, -1, sizeof h);
memset(dist1, 0x3f, sizeof dist1);
memset(dist2, 0x3f, sizeof dist2);
for (int i = 1; i < n; i ++ )
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dijkstra(n, dist1), dijkstra(1, dist2);
int now = 0;
for (int i = 1; i <= n; i ++ )
if (dist1[i] + t == dist1[1] && dist2[i] - t == 0)
now = i;
memset(dist2, 0x3f, sizeof dist2);
dijkstra(now, dist2);
for (int i = 1; i <= n; i ++ )
if (dist1[i] >> 1 >= dist2[i])
ans = max(ans, (dist1[i] + 1) >> 1);
cout << ans;
return 0;
}
T3 彩虹
多年以后，小X和小Y结婚了，他们搬到了一个新的城市。该城市有r条南北方向的街道，也有r条东西方向的街道。每一条南北街道中的都与每一条东西街道交叉；第x条南北街道和第y条东西街道之间的十字路口用（x，y）表示。为了从十字路口（x，y）移动到十字路口（x’，y’）,小需要|x - x‘|+|y - y’|分钟。
小X知道这座城市有n条美丽的彩虹会在十字路口出现。他想带领小Y尽可能多地观看这些彩虹。对于每一个i＝1，…，n，小X知道第i条彩虹将第ti分钟开始时在十字路口（x，y）出现并在很短的时间内消失。小X和小Y必须在第ti分钟开始时就出现（x，y）处才会看到彩虹，并且小X和小Y对于每条彩虹只观看一瞬间即可。
目前小X和小Y在第0分钟开始时在他们的新家，位于十字路口（1,1）。作为小X的好兄弟，小X希望你能帮他求出他最多可以带小Y参观多少条彩虹？
第一行两个整数r（1≤r≤500）,和n（1≤n≤100000），表示南北街道和东西街道的条数、彩虹出现的个数。
标签：彩虹,int,NZOJ,dist1,小区,dist2,字符串,模拟 From： https://www.cnblogs.com/YipChipqwq/p/18462567接下来r行数据，每行包括三个整数ti（1≤ti≤1000000），xi（1≤xi≤r），yi（1≤yi≤r），表示第ti分钟有一条彩虹出现在十字路口（xi，yi）处。