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

题目来源：Atcoder-abc297; Atcoder-arc156;

题目考点：

AT-10 V

Problem Statement

题目大意：

翻转所有中间有连续标签的序列

题目解析

当时比赛时想的是将所有的连续标签转换成序列的左右端点然后再全程倒序输出，写的时候挺费劲的，模拟的判断条件也多，左右端标签检查等等……结果30分钟第一发还WA了。

后来看官方题解是这么说的

大意就是将没有标签的数当成长度为1的倒序序列压入，因为长度为n的倒序序列需要n-1个标签标记出来。这样就可以让倒序区间连续起来。

vector<int> ans;
for (int i = 1, j = 1; i <= N; i = ++j)
    {
        while (re[j]) j++;//当前该数字j身后有标签，继续判断j+1身后有没有标签
        //数字j身后没有标签的时候,j即作为该段翻转序列的右端点处
        for (int k = j; k >= i; k--) ans.push_back(k);//压入区间[i,j]的倒序
        //接下来是for循环最为精巧的部分，区间左端点指针直接挪到j++，
    }
  for (int i = 0; i < N; i++) cout << ans[i] << " \n"[i + 1 == N];

这样就很精巧，也可行。

比赛当时我第二发的答案和这个代码挺像的，但是我当时思考的时候没有考虑到两个标签之间的序列正序输出，也就是其实我默认了两个倒序区间必须是紧紧挨着的（这个和官方题解中的0标记视为1序列碰巧撞上了，也就稀里糊涂的就过去了）

当时思考的是补一个前序0作为上一个倒序区间的右端点，这样统一了区间的更改过程。

设rem是上一个倒序区间的右端点，那么下一个倒序区间的起点就是rem+1，当遍历检查到某个check[i]!=1的时候，说明i后面没有了标记，是当前一个倒序序列的右端点，然后倒序将[rem+1,i]区间的数输出。

提交的时候我就发现我这么写是默认了没有两个倒序区间之间存在一个没有标记的正序区间，但是交了却AC了，当时有所疑惑但暂时没有细究原因，现在才想明白精髓——将多种可能的情况化归成同一个角度下的不同看法，进而化成了单种可能。将连续的k个数组成的无标签正向序列看做是k个单个数的倒序序列拼成的，就是这个思维。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[101],check[101];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        a[i]=i;
    }
    for(int i=1;i<=k;i++)
    {
        int t;cin>>t;
        check[t]=true;
    }
    int rem=0;
    for(int i=1;i<=n;i++)
    {
        if(!check[i])
        {
            for(int j=i;j>=rem+1;j--)cout<<j<<" ";
            rem=i;
        }
        
    }
    cout<<endl;
    system("pause");
    return 0;
}

AT-11 Swap Places

Problem Statement

题目大意：

给定一个个点条边的无向图，点有点权，值可以为或。两个人分别在点和，每次他们同时向自己这个结点的任意一个邻居移动，任意时刻，他们所在的结点的权值不得相同。最后要使得他们互相交换位置。输出最小次数或输出-1。

题目分析：

又是一道好题，每次都是只会记得那个死模版，更改更改思路挺好。

上来不难判断这是一个，无权图，最短路径，小数据，首先考虑的就必定是。

但是问题在于，这个最短路是有限制的，两个人不能同时出现在同一个权的点上。

我一开始是这么想的，如果能存在合法的最短路径，那么肯定A能走到，B直接走重复的反向路程也必定能走到，所以只对A跑一次，然后记录沿线个点点权后判断。

这么想有两个问题。第一，B未必非得走和A重复的路线也能到达，而且可能还不会判重；第二，就算满足第一点，广搜的单点时也会产生一个严重的问题，就像样例1，最短的过不去，却不会去往走(不好消除非法最短路径的影响)

所以，广搜的时候同时枚举两个人的状态（但是这貌似也不算双向广搜？），符合要求的将两个人的节点组合加入队列，不符合的直接排掉就行。

void bfs()
{
    queue<PP> q;
    q.push({ {1,n},0 });//两个连续的花括号需要中间加空格，否则解析错误
    while (!q.empty())
    {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int step=q.front().second;
        q.pop();
        if (x == n && y == 1)
        {
            cout << step << endl;
            return;
        }
        if (visited[x][y])
            continue;
        visited[x][y] = true;
        int sx = connects[x].size(), sy = connects[y].size();
        for (int i = 0; i < sx; i++)
        {
            int poserx = connects[x][i];
            for (int j = 0; j < sy; j++)
            {
                int posery = connects[y][j];
                if (tag[poserx] != tag[posery])
                {
                    q.push(PP(P(poserx, posery),step+1));
                }
            }
        }
    }
    cout << "-1" << endl;
    return;
}

话外附议一个问题。

通常bfs的时候bfs的步长是跟随队列记录的，这样的话走板子的判重位置是没有问题的

void bfs()
{
    queue<type> q;
    q.push();
    while(!q.empty())
    {
        type top=q.front();
        q.pop();
        if(visit[top])continue;
        /*Opetations*/
        q.push();
    }
}

而如果你的步长没有随队列而在局外记录，那就要小心一个问题，判重需要放到修改局外步长之前，也就是上面板子的中，否则可能产生意外的非法重复修改。 WA代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
bool tag[2001];
bool visited[2001][2001];
vector<int> connects[2001];
int n, m;
int step[2001][2001];
void init()
{
    memset(visited, 0, sizeof(visited));
    memset(tag, 0, sizeof(tag));
    memset(step, 0, sizeof(step));
    for (int i = 1; i <= 2000; i++)
    {
        connects[i].clear();
    }
}
void bfs()
{
    queue<pair<int, int>> q;
    q.push({1, n});
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (x == n && y == 1)
        {
            cout << step[x][y] << endl;
            return;
        }
        if (visited[x][y])
            continue;
        visited[x][y] = true;
        int sx = connects[x].size(), sy = connects[y].size();
        for (int i = 0; i < sx; i++)
        {
            int poserx = connects[x][i];
            for (int j = 0; j < sy; j++)
            {
                int posery = connects[y][j];
                if (tag[poserx] != tag[posery])
                {
                    q.push({poserx, posery});
                    step[poserx][posery] = step[x][y] + 1;
                }
            }
        }
    }
    cout << "-1" << endl;
    return;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        init();
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            cin >> tag[i];
        }
        for (int i = 1, u, v; i <= m; i++)
        {
            cin >> u >> v;
            connects[u].push_back(v);
            connects[v].push_back(u);
        }
        bfs();
    }
    system("pause");
    return 0;
}

//对上文的修改后AC：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
bool tag[2001];
bool visited[2001][2001];
vector<int> connects[2001];
int n, m;
int step[2001][2001];
void init()
{
    memset(visited, 0, sizeof(visited));
    memset(tag, 0, sizeof(tag));
    memset(step, 0, sizeof(step));
    for (int i = 1; i <= 2000; i++)
    {
        connects[i].clear();
    }
}
void bfs()
{
    queue<pair<int, int>> q;
    q.push({1, n});
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (x == n && y == 1)
        {
            cout << step[x][y] << endl;
            return;
        }
        int sx = connects[x].size(), sy = connects[y].size();
        for (int i = 0; i < sx; i++)
        {
            int poserx = connects[x][i];
            for (int j = 0; j < sy; j++)
            {
                int posery = connects[y][j];
                if (!visited[poserx][posery]&&tag[poserx] != tag[posery])
                {
                    visited[poserx][posery]=1;
                    q.push({poserx, posery});
                    step[poserx][posery] = step[x][y] + 1;
                }
            }
        }
    }
    cout << "-1" << endl;
    return;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        init();
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            cin >> tag[i];
        }
        for (int i = 1, u, v; i <= m; i++)
        {
            cin >> u >> v;
            connects[u].push_back(v);
            connects[v].push_back(u);
        }
        bfs();
    }
    system("pause");
    return 0;
}

随队列代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
typedef pair<P,int> PP;
bool tag[2001];
bool visited[2001][2001];
vector<int> connects[2001];
int n, m;
void init()
{
    memset(visited, 0, sizeof(visited));
    memset(tag, 0, sizeof(tag));
    for (int i = 1; i <= 2000; i++)
    {
        connects[i].clear();
    }
}
void bfs()
{
    queue<PP> q;
    q.push(PP(P(1,n),0));
    while (!q.empty())
    {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int step=q.front().second;
        q.pop();
        if (x == n && y == 1)
        {
            cout << step << endl;
            return;
        }
        if (visited[x][y])
            continue;
        visited[x][y] = true;
        int sx = connects[x].size(), sy = connects[y].size();
        for (int i = 0; i < sx; i++)
        {
            int poserx = connects[x][i];
            for (int j = 0; j < sy; j++)
            {
                int posery = connects[y][j];
                if (tag[poserx] != tag[posery])
                {
                    q.push(PP(P(poserx, posery),step+1));
                }
            }
        }
    }
    cout << "-1" << endl;
    return;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        init();
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            cin >> tag[i];
        }
        for (int i = 1, u, v; i <= m; i++)
        {
            cin >> u >> v;
            connects[u].push_back(v);
            connects[v].push_back(u);
        }
        bfs();
    }
    system("pause");
    return 0;
}

AT-12 Non-Adjacent Flip

Problem Statement

题目大意：

给一堆01串，要求每次翻转1的时候不能翻转两个相邻的1，求能不能全部翻转。若不能，则-1；能，则输出最小次数

题目分析

当时非常脑残的把问题复杂化成为了题，结果死磕也没找出来方程，结果没想到是个模拟

其实当时在对样例的尝试的时候已经发现当硬币达到一定数量的时候翻转次数就是1的数量的一半。但是这个大数量也不知道什么时候会被打破，加上以为是然后就寄了。

其实也是不知道模拟的方法，这个题从小到大找找规律其实就出来了。

首先开始就能明确的，这个1的数量不能是奇数，否则必然是不能够满足条件的。

其次，只有两个1的序列也是不可能完成的，因为两个1挨着不能翻。

再次，对于三个数字的序列，只有101是可以翻过来的，其余的都不行。

对于4个数的序列，是一定可以翻过来的。因为可以借道：0110变成1001再变成0000，恰好是三次，但是它不是2的一半，而是2的一半加2（因为借了两次道）。

但是1111的话就是2的一半。

对于5个数的序列，如果两个有011000这样的也是可以，但是2的一半再加1（由于借道1次）

多处理几组后发现，后面的只要1的数量是偶数就一定可以实现。如果1的数量大于等于4，交换的次数一定是1的数量的一半；对于只有两个1的时候；如果出现序列里面只有两个1挨着，那就是2（2的一半再加上借道产生的1）；如果是0110则是3次。

然后就……就没了……

鬼知道当时咋就当成了，这叫做新手的中阶算法恐惧症？？？

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int a[N];
void slove()
{
    int n;
    string st;
    cin>>n>>st;
    int ans=0;
    for(int i=0;i<st.size();i++)
        if(st[i]=='1')ans++,a[ans]=i+1;
    if(ans&1||st=="110"||st=="011")
        cout<<-1<<endl;
    else if(st=="0110")
        cout<<3<<endl;
    else if(ans==2&&a[1]+1==a[2])
        cout<<2<<endl;
    else 
        cout<<ans/2<<endl;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    slove();
    system("pause");
    return 0;
}

AT-13 Mex on Blackboard

Problem Statement

题目大意：

有一个多重集合（允许重复元素）,接下来你将进行如下次操作：

取出一个子集，将加入集合

问次操作之后你可以得到几种不同的多重集合,答案对998244353取模。

题目分析：

首先明确的定义是返回中最小的未出现非负元素。

先试试看呗，就对样例来说。

对于样例1集合，假设要插入7次且暂时保证插入的元素不重复，那么每次插入的时候都需要把这个集合完整的选上（也就不是选真子集而是子集），插入7次的话就会得到一个单增序列{}

但是如果一旦这个时候不选子集而选真子集的话，集合的上限不会扩展，反而插入的是集合已有的元素。

那么说，如果,就必然有集合包含连续的~ 的所有元素，否则必然不会返回而是返回那个缺失的元素。

如果选一个连续的组成的集合的真子集作为自变量，返回的一定是

然后就变成了对这个集合插入次能组成多少个多重集合。

然后就变成了个苹果被个人分，每个人不一定能分到一个，求分的方法总数。

显然，给每个人借一个苹果，然后按照每个人至少一个分配，然后再收回来,这样就可以用插板法排列组合了。

一共是种分配方法。（个人插个隔板）

然后需要做的就是知道我返回的时候已经消耗了几次插入，那么

枚举的可能就行了，枚举的过程相当于在扩展集合，计算组合数的过程相当于在选取子集。

这个题着实是很巧妙的。

至于说求模……逆元呗。

同样，想把元素插全，也就是求的时候，你这个集合到缺几个数，就需要取几次完整的集合来补齐。

挺新奇的一道题，上来的时候是没有思路的

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, mod = 998244353;
int T, n, k, a[N], vis[N], p[N], res,inv[N];
char s[N];
int quickpow(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

int C(int a, int b) {
    return p[a] * inv[b] % mod * inv[a-b] % mod;
}

signed main() {
    cin >> n >> k;

    for (int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        vis[a[i]]++;
    }
    p[0] = 1,inv[0]=1;
    for (int i = 1; i <= N - 5; i++)
        {
            p[i] = p[i - 1] * i % mod;
            inv[i] = inv[i-1] * quickpow(i,mod - 2)%mod;
        }
    int cnt = 0;
    for (int i = 0; i <= N - 5; i++) 
    {
        if (vis[i] == 0) 
            cnt++;
        if (vis[i + 1]) 
            continue;
        if (cnt > k) 
            break;
        (res += C(k - cnt + i, i)) %=mod;
    }
    cout << res << endl;
}

AT-S-4 Teleporter Takahashi

Problem Statement

大模拟，还没做明白

AT-S-5 Shopping in AtCoder store

Problem Statement

计算几何的凸包，暂时不碰

AT-S-6 Trio

Problem Statement

大概率题，还没顾上思考。