问题标题: 包河区初中组区赛

这是包河区初中组区赛AK的方法：（第一题数据有误，全包河区都是0分）

 

包河区2021年初中组区赛

第一题：permutation

题目大意：
输入一个n和一个长度为n的整数序列a1 a2 ... an，判断序列a是否为n的全排列

输入描述：
n
a1 a2 a3 ... an

输出描述：
如果a为n的全排列，输出Yes，否则输出No

数据范围：n<=1000，ai<=n

自己的解：
用一个桶存储a，然后遍历桶下标1~n，如果某一个数的数量不为1，则直接一票否决，输出No；否则输出Yes

难度：简单题

第二题：swappable

题目大意：
输入一个n和一个长度为n的整数序列a1 a2 ... an，求出所有的整数对(ai,aj)使得i<j且ai≠aj。

输入描述：
n
a1 a2 a3 ... an

输出描述：
输出所有满足条件的整数对的数量

数据范围：n<=300000，ai<=10^9

自己的解：
用桶存储序列a，b[a[i]]表示a[i]的数量，最后答案是对于1<=i<=n，求n-b[a[i]]的和再除以2
但是桶需要用map，防止内存不够

朋友的解：
对序列a进行排序，求出sum=n(n-1)/2
然后，进行如下操作：（伪代码）
定义变量l
for i from 1 to n
    if a[i]!=a[i-1] then
        sum-=l(l-1)/2
        l=1
    else
        l++
最后输出sum即可

难度：一般题

第三题：water

题目大意：
给出一个01矩阵，表示一个地图，其中1表示窨井，0表示道路
从矩阵的左上角走，每次只能向右或向下走一步，问一次最多能**多少个窨井

输入描述：
第一行输入n和m
接下来输入一个n*m的01矩阵，如题所示

输出描述：
输出一次最多能**的窨井数量

范围：n<=100，m<=100

自己的解：
定义f[i][j]表示走到(i,j)最多能**多少个窨井
状态转移方程：f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
边界：f[1][1]=a[1][1];
解：f[n][m]

难度：**题，但如果没学过DP的话……

第四题：palindrome

题目大意：
输入一个n和一个长度为n的整数序列a1 a2 ... an，现对a进行若干次操作，使得a为回文序列
一次操作的定义为：将序列中所有的x换成y
问最少需要多少次操作，使得a为回文序列

输入描述：
n
a1 a2 a3 ... an

输出描述：
最少操作的次数

数据范围：n<=200000，ai<=200000

自己的解：

回文，即对于1<=i<=n，满足a[i]=a[n-i+1]
那么我们可以用一个头指针l和一个尾指针r
若a[l]==a[r] 则直接pass
否则，必须要执行一次操作
    将a[r]替换成a[l]和将a[l]替换成a[r]是等价的，因为替换后相当于它们变成了一个相同的数，就不用管了
核心代码：
int l=1,r=n;
while l<r
    if a[l]!=a[r]
        ans++
        for i from l to r
            if a[i]==a[r]
                a[i]=a[l]
    l++,r--
此解法时间复杂度为O(n^2)，无法AC
发现：我们没有必要把整个序列换来换去，只需要把一些数建立等价关系即可，当a[l]和a[r]满足等价关系时，应视为相等
最简单、最直接的办法就是映射，把关系建立在一个映射表上
但是，这种方法写过后，连样例都过不了。这是因为，虽然2和3是等价，3和5是等价，但是2和5并没有设置等价，所以样例过不了
那么，既然是等价，那有什么好办法呢？
可以建立一个并查集，将所有等价的数放在一个集合里面，这样，形成一个个等价的区块。核心代码如下：
int l=1,r=n;
while l<r
    if a[l]!=a[r] && !same(a[l],a[r])
        ans++
        unite(a[l],a[r]);
    l++,r--
此解法时间复杂度为O(kn)，其中k的平均值取1
最后输出ans即可

难度：魔鬼题