A. Shape Perimeter

题意

在一个无限大的纸张上，有一个边长为 $m$ 的正方形印章。初始时，正方形印章的左下角与纸张的左下角对>齐。给定两个长度为 $n$ 的整数序列 $x$ 和 $y$。对于从 $1$ 到 $n$ 的每一步 $i$，会发生以下操作：

• 将印章向右移动 $x_i$ 个单位，并向上移动 $y_i$ 个单位。
• 将印章按压在纸张上，在其当前位置留下一个边长为 $m$ 的彩色正方形。

注意，序列 $x$ 和 $y$ 的元素有一个特殊的约束条件：$1 \le x_i, y_i \le m - 1$。

请注意，你不会在纸张的左下角按压印章。为了更好地理解，请参考注释部分。

可以证明，在所有操作完成后，纸张上由印章形成的彩色形状是一个单一的连通区域。请找出这个彩色形状的周长。

分析

由约束条件可以知道，每次印章移动都会保证移动后一定有一部分与移动前重叠，且不会完全重叠。
故计算周长可以将总的正方形个数的周长的和减去叠加部分的周长即可。

代码

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 1e5 + 5;


void solve() {
    int n, m;
    cin >> n >> m;
    int ans = n * m * 4;
    int a,b;
    cin>>a>>b;//第一个不算
    for (int i = 0; i < n-1; ++i) {
        cin >> a >> b;
        int i1 = m - a;
        int i2 = m - b;
        ans -= (i1 + i2) * 2;
    }
    cout<<ans<<endl;

}

signed main() {
    int _;
    cin >> _;
    while (_--)solve();
}

B. Find the Permutation

题意

给你一个无向图，它有 $n$ 个顶点，标记范围从 $1$ 到 $n$ 。这个图编码了一个隐藏的排列 $p$ ，大小为 $n$ 。图的构造如下

对于每一对整数 $1 \le i < j \le n$ ，当且仅当 $p_i < p_j$ 时，在顶点 $p_i$ 和顶点 $p_j$ 之间添加一条无向边。

您的任务是重建并输出排列 $p$ 。可以证明排列 $p$ 是唯一确定的

分析

考虑某个节点$i$

• 比$i$小的点与$i$之间有边，则说明这些点应该在$i$的左边
• 同理，若比$i$大的点与$i$之间没有边，则这些点应该在$i$的右边。
  当左右个数确定，则$i$的位置也就确定了。

• 代码

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 1e3 + 5;
int n;
char a[N][N];
int ans[N];

int getl(int u) {
    int s = 0;
    for (int i = 1; i <= u - 1; ++i) {
        s += a[u][i] == '1';
    }
    return s;
}

int getr(int u) {
    int s = 0;
    for (int i = u + 1; i <= n; ++i) {
        s += a[u][i] == '0';
    }
    return s;
}

void solve() {

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> a[i][j];
        }
    }
    for (int i = n; i >= 1; --i) {
        ans[getl(i) + getr(i) + 1] = i;
    }
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << ' ';
        assert(ans[i] != 0);
    }
    cout << endl;

}

signed main() {
    int _;
    cin >> _;
    while (_--)solve();
}

C. Palindromic Subsequences

题意

给定$n$，构造一个序列$a$，要求

• $a$中的每一个元素都在1到n之间
• $a$的 最长的回文串个数大于n

分析

观察第一个样例1 1 2 3 1 2，最长回文串长度为3，个数为7，满足要求。

当长度增加时，我们能不能添加一个数字进去，能满足最长回文串的长度不变，而且长度还能增加呢？

分析所有的最长回文串

1. [1, 2, 1]
2. [1, 1, 1]
3. [1, 3, 1]
4. [1, 2, 1]
5. [1, 3, 1]
6. [2, 3, 2]
7. [2, 1, 2]

可以注意到，加在最后两位的1和2之间可以与前一个和后一个2组成长度为3的回文串。

代码

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 1e3 + 5;


void solve() {
    int n;
    cin >> n;
    cout << "1 1 2 3 1 ";
    for (int i = 0, t = 4; i < n - 6; ++i, ++t) {
        cout << t << ' ';
    }
    cout << "2\n";


}

signed main() {
    int _;
    cin >> _;
    while (_--)solve();
}