测试原链接：TJU暑期训练 个人排位赛（一）

题目来源：Atcoder-abc307;

题目考点：模拟，图论（最短路+队列优化），动态规划

AT-1 B-racecar

Problem Statement

题目大意

给定个字符串序列，从中随机取两个 按先后顺序 组成完整字符串，判断这个字符串有没有可能组成回文序列。

解析

为什么把这个题也列出来就是单纯的为了强调 按先后顺序 这个事儿。需要注意，按照的顺序取字符串合并和的顺序合成的字符大串很可能回文性质不一样，单纯的按这样就会漏情况（人家也没说前后俩字符串必定长度一样，长度一样也不一定回文性质一样啊）

还有就是函数针对的是类型，对于要函数函数。

#include <bits/stdc++.h>
using namespace std;
string s[1001];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
    }
    for (int i = 1; i <= n ; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if(i==j)continue;
            string f = s[i] + s[j];
            reverse(f.begin(), f.end());
            if (f == s[i] + s[j])
            {
                cout << "Yes" << endl;
                system("pause");
                return 0;
            }
        }
    }
    cout << "No" << endl;
    system("pause");
    return 0;
}

AT-2 C-Ideal Sheet

Problem Statement

题目大意

高桥有两张不大于的长方形透明方格纸，两个方格纸上都有一些方格被涂黑了。现在他有一张无限大的全透明方格纸，他要将和粘在这个无限大的方格纸上。和可以重叠粘贴，重叠区域的方块只有全为透明的时候才透明，否则就是黑的方块。他想在粘完和的这张无限大纸上割下来一块他需要的不大于的目标长方形方格纸，他能不能做到这一点。

解析

格纸和的分布一共有以下几种情况：

1. 格纸和为交集非包含放置关系
2. 格纸和为包含关系
3. 格纸和互斥关系（无重叠）

但是要注意，目标格纸的大小最大也不超过,这就意味着和的粘贴区域最大不超过，否则裁剪区域必定无法将所有的黑色方块减掉。 （举个例子，假设和的粘贴区域为，大小均为最大。设放置在的区域，B放置在,此时无论怎么分割都不可能做到将所有的黑色方块全部纳入。即如果 ,就必定有;反之若,就必有）

所以设无限大方格纸就是,和如果粘贴位置超出了就抛弃(不参与判定)。

枚举模拟和的粘贴位置(起始点位置可能在内的任何一个点)来模拟每一次粘贴情况，然后和期望部分比较。

但是还有一个问题，期望矩形可能出现粘好表部分的任何一个位置。怎么确定某一种情况是能够完成任务所需要的？

一种方法是模拟在该情况的大矩阵中的各个可能的位置来找，但是这样频繁的移动并不好实现而且有所浪费时间。将这个方法变通一下，将目标固定在大矩阵的正中间(即固定在处来比较)。因为和可能放置在大矩阵中的任何一个位置，如果能裁出来的话，根据平移原理，必然存在一种情况使得和可以将裁剪的目标区域恰好集中在处，与判定矩阵重合。

代码

#include <bits/stdc++.h>
using namespace std;
int a[40][40], b[40][40], c[40][40], anss[40][40];
int ax, ay, bx, by, cx, cy;
int main()
{
    string s;
    cin >> ax >> ay;
    for (int i = 1; i <= ax; i++)
    {

        cin >> s;
        for (int j = 0; j < s.size(); j++)
            a[i][j + 1] = (s[j] == '#');
    }
    cin >> bx >> by;
    for (int i = 1; i <= bx; i++)
    {
        cin >> s;
        for (int j = 0; j < s.size(); j++)
            b[i][j + 1] = (s[j] == '#');
    }

    cin >> cx >> cy;
    for (int i = 1; i <= cx; i++)
    {
        cin >> s;
        for (int j = 0; j < s.size(); j++)
            c[10 + i][11 + j] = (s[j] == '#');//放在大矩阵的中间
    }
    for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= 20; j++)//A矩阵启动位置
            for (int m = 1; m <= 20; m++)
                for (int k = 1; k <= 20; k++)//B矩阵启动位置
                {
                    bool tag = 1;
                    memset(anss, 0, sizeof(anss));
                    for (int i_ = 1; i_ <= ax; i_++)
                        for (int j_ = 1; j_ <= ay; j_++)
                        {
                            if (a[i_][j_])
                                anss[i_ - 1 + i][j_ - 1 + j] = 1;
                        }
                    for (int i_ = 1; i_ <= bx; i_++)
                        for (int j_ = 1; j_ <= by; j_++)
                        {
                            if (b[i_][j_])
                                anss[i_ - 1 + m][j_ - 1 + k] = 1;
                        }
                    for (int x = 1; x <= 30; x++)//判断合法区域就只为30x30
                        for (int y = 1; y <= 30; y++)
                        {
                            if (anss[x][y] != c[x][y])
                                tag = 0;
                        }
                    if (tag)
                    {
                        cout << "Yes" << endl;
                        system("pause");
                        return 0;
                    }
                }
    cout << "No" << endl;
    system("pause");
    return 0;
}

AT-3 E-Distinct Adjacent

Problem Statement

题目大意

环形的涂色问题，有一个有个节点的环，有种颜色，求涂色方法总数，使得两两相邻的节点颜色不同。输出结果对998244353取模。

解析

设数列表示个节点的环用种颜色涂最多有的情况数，表示个节点的无环线段用种颜色涂最多有的情况数。

易有

而将首尾拼接成环的话，有两种情况：

1. 首尾颜色相同，这样的话必然保证第一个和倒数第二个节点首尾不同，即首尾相同的情况数为.
2. 首尾颜色不同，总计种情况.

所以

等比数列待定系数法，设特别的，认为.

解有

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ull;
const ull MOD = 998244353;
ull as[10000001];
int main()
{
    int n, m;
    cin >> n >> m;
    ull ans = 1;
    as[1] = m - 1;
    for (int i = 2; i <= n; i++)
        as[i] = ((as[i - 1]) * (m - 1)) % MOD;
    if (n & 1)
        cout << (as[n] + MOD - (m - 1)) % MOD << endl;
    else
        cout << (as[n] + (m - 1) ) % MOD << endl;

    system("pause");
    return 0;
}

AT-4 F-Virus2

Problem Statement

题目大意

一张有个节点，条边的无向图；初始时第天有个节点被病毒污染。每天病毒的传染能力有限。如果第天的传染能力为,传染源点为P，那么若点到点存在通路并且其最短路径小于等于,就认为第天时节点将被病毒污染并且在之后的天数将和其他被污染节点一样具有同样的传染能力。按顺序输出天之后，各节点被污染的时间。如果天之后该节点仍旧没有被污染，那么则输出。

解析

一开始的时候想法很简单，就是以第天的最初始感染原点为总点集跑一遍最短路径，然后将前天的感染能力求前缀和，按照这个来比较节点相对于最初始源点点集的最短路径，如果够了就证明在第天被感染，但是这个思路不正确，原因很简单，样例中的样例2就过不了，因为这样会造成一个越界的问题：第一天没有感染节点A,但是第二天计算的时候如果按前缀和来计算，就是暗中默认了A点在第一天被感染的情况下来分析A后面的联通节点的。

意识到这个问题之后，就换了第二种方式，对每一次节点都重新跑一次最短路径算法；但是这会产生一个新的问题：首先是存在第天的所有感染源点无法感染任何点但是第天可以继续感染的问题，其次就是大量的跑最短路造成了严重的超时。

错误代码1

#include <bits/stdc++.h>
using namespace std;
struct nexts // 邻接表
{
    int pos;
    int w;
};
int n, m, d, k; // 房间数，走廊数，总传染天数，初始感染者人数
struct node     // 最短路径队列维护
{
    long long dist;
    int pos;
    int infectday;
    bool operator<(const node &x) const
    {
        return x.dist < dist;
    }
};
vector<nexts> connects[300001];
priority_queue<node> q;
long long dist[300001];   // 最短路径
bool visited[300001];       // 最短路径
bool infectcheck[300001]; // 是否感染
int A[300001];            // 初始感染者位置
long long D[300001];      // 第i天传染力距离
int infectdays[300001];
void initdist()
{
    for (int i = 1; i <= 300001; i++)
    {
        dist[i] = 1e10;
    }
}
void initvisited()
{
    memset(visited, false, sizeof(visited));
}
void Dijkstra_queue(int start)
{
    dist[start] = 0;
    q.push((node){0, start});
    while (!q.empty())
    {
        int location = q.top().pos;
        q.pop();
        if (visited[location])
            continue;
        visited[location] = true;
        for (int i = 0; i < connects[location].size(); i++)
        {
            int v = connects[location][i].pos;
            int w = connects[location][i].w;
            if (dist[v] > dist[location] + w)
            {
                dist[v] = dist[location] + w;
                if (!visited[v])
                    q.push((node){dist[v], v});
            }
        }
    }
    return;
}
void Final_queue(int k)
{
    initdist();
    cin >> d;
    for (int i = 1; i <= d; i++)
        cin >> D[i];
    queue<node> q;
    for (int i = 1; i <= k; i++)
        q.push((node){0, A[i], 0});
    int start = 0;
    int infectday = 0;
    while (!q.empty()) // 存在一种可能，当某一天可感染成员队列为空（第i天无法感染任何人）
    {
        start = q.front().pos;
        infectday = q.front().infectday;
        q.pop();
        infectcheck[start] = true;
        infectdays[start] = infectday;
        if (infectday >= d)
            continue;
        initvisited();
        Dijkstra_queue(start);
        for (int i = 1; i <= n; i++)
        {
            if (!infectcheck[i] && D[infectday + 1] >= dist[i])
            {
                q.push({dist[i], i, infectday + 1});
                infectcheck[i] = true;
                infectdays[i] = infectday + 1;
            }
        }
        if (q.empty() && infectday < d - 1) 
        // 感染队列为空的原因有两种，一是第i天无法感染任何人，需要下一步if；二是天数已满，统计结束，直接跳出.
        // 而当第d-1天的感染者无法感染任何人时，直接跳出；否则要进行手动跨天。
        {
            for (int i = 1; i <= n; i++) // 如果不是第d-1天
            {
                if (!infectcheck[i] && D[infectday + 2] >= dist[i])
                {
                    q.push({dist[i], i, infectday + 2});
                    infectcheck[i] = true;
                    infectdays[i] = infectday + 2;
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; i++)
    {
        cin >> u >> v >> w;
        connects[u].push_back((nexts){v, w});
        connects[v].push_back((nexts){u, w}); // 邻接表双向图
    }
    cin >> k;
    memset(infectdays, -1, sizeof(infectdays));
    for (int i = 1; i <= k; i++)
        cin >> A[i], infectdays[A[i]]++;
    Final_queue(k);
    for (int i = 1; i <= n; i++)
        cout << infectdays[i] << endl;
    system("pause");
    return 0;
}

后来意识到按照点的传染能力计算天数可行性不高（关于中间无感染天数的计算难度过大且浪费大量时间复杂度），最后决定更换思路，按照每一天计算传染情况。这其实也就是对求最短路的时候更深层次的拆分理解——将合并的两次步骤拆开来写。

对于第天，感染源对周边某一密接节点（与感染源节点直接相连）感染情况只存在如下两种可能：

1. 感染源点无法感染该密接节点。
2. 感染源点可能感染该密接节点并且可能威胁后续非密接节点。

这样按照一个节点一个节点的跑最短路径相当于将拆成了一步一步的，只要某一条路径的总长度超过了当天的最大传染能力，就停止后续的最短路计算————因为不可能在必然通过该路径的前提下继续感染其他节点。

同时还涉及到的问题是，由于是多源点最短路径，所以存到队列的时候的时候会有一步局限性，需要这句话：

if(dis>dist[v])continue;

代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> nexts;
vector<nexts> connects[300001];
priority_queue<nexts, vector<nexts>, greater<nexts>> qfirst, qothers;
// qfirst的含义是在第i-1天的感染者辐射下的密接圈内的人，qothers含义是指在第i-1天感染者辐射下次密接及次次密接
// 等非密接但是能被感染距离污染的人
int dist[300001], infectdays[300001];
int n, m, k, d;
void cin_graph(int &n, int &m) // 全部初始化
{
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; i++)
    {
        cin >> u >> v >> w;
        connects[u].push_back(nexts(v /*pos*/, w /*w*/));
        connects[v].push_back(nexts(u, w));
    }
    for (int i = 1; i <= n; i++)
    {
        dist[i] = 2147483647;
        infectdays[i] = -1;
    }
    return;
}
int main()
{
    cin_graph(n, m);
    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        int location; // 初始感染者坐标；
        cin >> location;
        dist[location] = 0;
        infectdays[location] = 0;
        for (int j = 0; j < connects[location].size(); j++)
        {
            int u = connects[location][j].first;
            int w = connects[location][j].second;
            if (dist[u] > dist[location] + w)
            {
                dist[u] = dist[location] + w;   // 第i-1天的感染者在第i天可能的密接圈路径
                qfirst.push(nexts(dist[u], u)); // 单对起点，由于第i-1天的感染者并不唯一，所以存入临时密接圈
                // 的dist数值只是说明当前location下的距离而非最短距离（可能两个点能够同时到一个点但距离不一）
                // ，但是一直在全局的dist数组却是能保证第i-1天感染者组成的集合针对其他密接圈内人的最短距离
            }
        }
    }
    cin >> d;
    for (int i = 1; i <= d; i++) // 彻底转变思路，以病毒爆发第i天来进行规划。
    // 病毒爆发的第i天，由第i-1天及以前的所有人组成的集合向外辐射最大距离为Di的病毒污染人群。而污染分成了两大类情况。
    /*1.感染者距离不够感染任何人（感染距离小于密接圈最短距离）。
      2.感染者距离恰好能够感染密接圈内的某人(密接圈外距离够不到）。
      3.感染者距离能够辐射到密接圈之外的人。
      如果单纯以密接圈内所有人为基准进行最短路径规划会有非常恐怖的时间复杂度（大约是n^2,这还是不计算队列优化的
      Dijkstra的nlogn的前提下，面对3e5的数据绝对超时，所以我们优化计算的时候，仅对可能辐射到次密接的部分进行
      Dijkstra_queue计算，减少大面积的无必要的计算。
    */
    {
        int ability;
        cin >> ability; // 第i天的最大感染辐射范围。
        vector<nexts> infectedperson;
        while (!qfirst.empty())
        {
            nexts node = qfirst.top();
            qfirst.pop();
            int dis = node.first, location = node.second;
            if (dis > dist[location])
                continue; // 这就是涉及到上文注释过的点集合到目标位置的最短距离筛选，只有两者
            // 相等的时候才是最短距离，符合题目要求。
            if (ability < dis)
            {
                qfirst.push(node);
                break;
            } // 1.密接圈内该人不能被感染，此时由于优先队列特性，node后面所有的节点都不可能被感染，所以直接打破
              // 密接圈排查，密接圈内剩余人将在第二天继续排查。
              /*
              这里同时涉及到了一个greater<pair<int,int>>的特性，该函数的含义如下：
              template<typename T> struct greater
              {
                  constexpr bool operator()(T const& a, T const& b) const
                  {
                      return a.first>b.first || ( (a.first<b.first) && (a.second>b.second));
                  }
               };
              */
            qothers.push(nexts(dis, location));
        }
        while (!qothers.empty())
        {
            nexts node = qothers.top();
            qothers.pop();
            int dis = node.first, location = node.second;
            if (dis > dist[location])
                continue; // 同理，多源起点取最短距离必须有部分。
            infectedperson.push_back(node);
            for (int j = 0; j < connects[location].size(); j++) // 既然目标人已经进入感染的辐射范围，
            // 那么探查其是否可能存在辐射到次密接的可能性，进行最短路径。
            {
                int v = connects[location][j].first;
                int w = connects[location][j].second;
                if (dist[v] > dist[location] + w)
                {
                    dist[v] = dist[location] + w;
                    if (dist[v] <= ability) // 从该路径仍存在继续辐射的可能性
                        qothers.push(nexts(dist[v], v));
                }
            }
        } // qothers变为空的时候，infectperson即保存了全部在第i天被感染的人。
        for (int j = 0; j < infectedperson.size(); j++)
        {
            int location = infectedperson[j].second;
            infectdays[location] = i;
            dist[location] = 0; // 作为第i批被感染的人去初始化感染第i+1天的人。
            for (int p = 0; p < connects[location].size(); p++)
            {
                int u = connects[location][p].first;
                int w = connects[location][p].second;
                if (dist[u] > dist[location] + w)
                {
                    dist[u] = dist[location] + w;
                    qfirst.push(nexts(dist[u], u));
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << infectdays[i] << endl;
    system("pause");
    return 0;
}

AT-5 G-Approximate Equalization

Problem Statement

题目大意

给定一串数列，对数列的每一次操作有以下两种选择：

1. 对任意使得,操作.
2. 对任意使得,操作.

求使得数列各项之间绝对值差小于等于1的最少操作次数。

解析

设数列的总和为,各项操作不会改变总和。操作顺序为从左到右依次使各项变为目标最终状态。

最终状态的数列一定是由个和个组成,顺序未知。其中,，数学意义上的取余( ).

设数列初始时每一项的移动为的次数为 ,则 ，因为调整每一个数时都会对后面的下一个数产生多余的负担（减1必在后面一个数加1，反之亦然），而这些多余的负担会利滚利的传递到后面，所以是求前缀和。

所以，最终序列的各项排列顺序决定了数列的操作次数，故进行.

设 表示前 个数字组成的子数列有 项,则有动态规划方程：

对于的解释是这样的：

前缀和的计算是将所有项全部调整成为了.对于前i个数的复原时，本来应该有个数是 但却复原成为了 。那么，第一个应该被复原为 的数多产生了一次复原的负担并且使下一个数的复原过程时多了一步，下下个数的复原过程又多了一步……同理，这 个特殊的数字将会对 后面的每一个数多产生 个数字的负担，而我们现在需要 ，所以也就需要对后面的每一个数字抵消次的额外操作负担。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=0x7fffffffffffff;//无穷大初始化
ll a[5001],b[5001],sum,ave,rem;
ll dp[5001][5001];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    ave=sum/n;
    if(ave<=0)ave--;
    rem=sum-ave*n;
    for(int i=1;i<=n;i++)
    {
        b[i]=b[i-1]+a[i]-ave;//假设全变为ave需要调整的次数
    }
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            dp[i][j]=INF;
        }
    }
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i&&j<=rem;j++)
        {
            if(j==0)dp[i][j]=dp[i-1][j];
            else
            dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]);
            dp[i][j]+=abs(b[i]-j);
            //解释一下为什么要b[i]-j
            /*
            本题的最少次数就是一个一个的复位匹配。那么我们在复原的时候，复原每一个数时所产生的副作用
            都会被下一个数所负担，这样就会有负担次数的利滚利。
            而对于前i个数的复原时，本来应该有j个数是ave+1但却复原成为了ave。那么，第一个应该被复原为ave+1
            的数多产生了一次复原的负担并且使下一个数的复原过程时多了一步，下下个数的复原过程又多了一步……
            同理，这j个特殊的数字将会对i后面的每一个数多产生j个数字的负担，而我们现在需要ave+1，
            所以也就需要对后面的每一个数字抵消j次的额外操作负担。
            */
        }
    }
    cout<<dp[n][rem]<<endl;
    system("pause");
    return 0;

}

AT-S-1 Marquee

Problem Statement

考点：快速傅里叶变换（能力范围之外，暂留）