作为一个算法小白也是被打击惨了，今天就来补题了
PS:是和小红做朋友的一天
A、小红的不动点
A题比较简单，输入一个数组，检查有多少个不动点（下标和元素值相等的点）。下标从1开始
#include <bits/stdc++.h>
using namespace std;
int a[5];
int main()
{int ans=0;for(int i=1;i<=4;i++){cin>>a[i];if(a[i]==i) ans++;}cout<<ans;return 0;
}
B、小红的不动点构造
B题小红想要得到一个长度为n的排列，其中恰好有k个不动点。
这里介绍了排列的知识：从1~n的数，按任意顺序组成的数组。不能有重复的数字，也不能有超出范围的数字。
不动点定义同A。
输入n,k
如果无法构造输出-1，否则就输出符合条件的排列(随机输出一个)。
这里可以模拟一下
比如有五个数字 1 2 3 4 5如果要得到1个不动点就可以把剩下的四个数字，两两交换
1 3 2 4 5 ->1 3 4 2 5 -> 1 3 4 5 2;
如果要得到2个不动点就可以从第三个数字开始把剩下三个数字两两交换
1 2 4 3 5 -> 1 2 4 5 3；
如果要得到3个不动点可以从第四个开始两两交换
1 2 3 5 4
如果要得到4个不动点，我们可以发现无法实现，所以当k=n-1时，无解输出-1；
如果要得到5个不动点，则原数组不变
#include <bits/stdc++.h>
using namespace std;
int a[11];
int main()
{int n,k;cin>>n>>k;for(int i=1;i<=n;i++){a[i]=i;//数据范围比较小，这里我们进行数组读入}if(k==n-1) cout<<"-1";//如果k=n-1时，无解输出-1；else //否则交换剩余数组{for(int i=k+1;i<n;i++){swap(a[i],a[i+1]);}for(int i=1;i<=n;i++)//然后输出数组{cout<<a[i]<<" ";}}return 0;
}
C、小红的不动点分配
这个题是贪心+计数的思想
对于一个数字，我们假设它出现了k次，那么它对不动点的贡献就是min(k,2)，最多贡献两个不动点，如果一个数大于n，那么这个元素永远无法作为不动点。所以我们只需要统计每个x出现的次数。累加后即可得出答案
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
vector<int> cnt(N);//
int main()
{//输入比较多，优化一下ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int n;cin>>n;for(int i=1;i<=2*n;i++){int x;cin>>x;cnt[x]++;}int ans=0;for(int i=1;i<=n;i++){ans+=min(2,cnt[i]);}cout<<ans;return 0;
}
D、小红的矩阵不动点
这个题最多只能进行一次交换，那么答案只有三种
- 不交换
- 交换后增加一个不动点
- 交换后增加两个不动点
感觉这个题难度超大/(ㄒoㄒ)/~~
#include <bits/stdc++.h>
using namespace std;
const int N=550;
int a[N][N];
vector<pair<int,int>> bad;
bool inCV[N], inDV[N], hasPair[N][N];
int main()
{int n,m;cin>>n>>m;bad.reserve(n * m);int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]==min(i,j))ans++;else {int u=a[i][j];//这里存一下不是不动点的值和理想值int v=min(i,j);bad.push_back({u,v});inCV[u] = true;//这里单方面存一下当前位置的值inDV[v] = true;//这里单方面存一下当前位置需要的理想值}}}if(ans==n*m)//超理想情况，输入的都是不动点{cout<<ans;return 0;}// 检查是否可以增加两个不动点，是否存在(u,v)和(v,u)for(auto &p:bad){ //遍历bad中的每个(u,v)对int u=p.first,v=p.second; // 获取当前值u和目标值vif(hasPair[v][u]){//如果存在(v,u)对cout<<ans+2;return 0;}hasPair[u][v] = true;//标记(u,v)对已检查}for(int x=1;x<=n+m;x++){ //遍历所有可能的值if(inCV[x]&&inDV[x]){ //如果x同时在CV和DV中cout<<ans+1;//这里遍历元素 如果当前值存在，并且其理想值也存在就可以进行交换return 0;}}cout<<ans;return 0;
}
E、小红的不动点权值
这个题当时做的TLE了，也是很惨了
这里我们反过来想：对于原排列中的值为k的那个位置，只要一个子数组同时包含了所有比k小的元素和k，那么排序后就会产生一个不动点k
也就是每个值k能在多少个子数组里成为不动点？
- 设p[x]为原排列中值为x的下标
L_k=min{p[1],p[2],...,p[k]}R_k=max(p[1],p[2],...,p[k])- 只有当子数组的左右端点区间[l,r]同时覆盖[L_k,R_k]时，子数组中才包含1~k，
- 可选的l有L_k种，可选的r有(n-R_k+1)种
- 所以K的贡献为L_k*(n-R_k+1)
- 最后求和就行
代码基本上和思路一致
#include <bits/stdc++.h>
using namespace std;
int main(){int n;cin >> n;vector<int> p(n+1);for(int i=1;i<=n;i++){int x;cin>>x;p[x]=i;}long long ans=0;int L=n+1,R=0;for(int k=1;k<=n;k++){L=min(L,p[k]);R=max(R,p[k]);ans+=(long long)L * (n - R + 1);}cout<<ans;return 0;
}
没劲儿了，明天接着写