A：https://codeforces.com/contest/1454/problem/A
题意：
输出1~n的一个排列，满足每个i!=pi
解析：
偶数直接倒叙
奇数不能倒叙，因为中间点不符合。所以随便调下位置即可。比如先输出n，然后正序输出1~n-1
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<stack> using namespace std; typedef long long ll; const int maxn=1e5+10; int main() { int t; cin>>t; while(t--) { int n; cin>>n; if(n%2) { cout<<n<<" "; for(int i=1;i<=n-1;i++) cout<<i<<" "; } else { for(int i=n;i>=1;i--) cout<<i<<" "; } cout<<endl; } }
B：https://codeforces.com/contest/1454/problem/B
题意：
给出n个数，是否某个数只出现了一次，而且在所有出现一次的数中最小。
解析：
俩memset hack掉了。
其实计坐标的那个数组压根不需要重置。每次都被覆盖了。。。
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> using namespace std; typedef long long ll; const int maxn=2e5+10; int a[maxn]; int v1[maxn],v2[maxn]; int main() { int t; cin>>t; while(t--) { memset(v1,0,sizeof(v1)); int n; cin>>n; for(int i=1;i<=n;i++) { int x; cin>>x; v1[x]++; v2[x]=i; } int ok=0,idx; for(int i=1;i<=n;i++) { if(v1[i]==1) { ok=1; idx=v2[i]; break; } } if(ok) cout<<idx<<endl; else cout<<"-1"<<endl; } }
C：https://codeforces.com/contest/1454/problem/C
题意：
给出n个数
只能选择一个数字x，然后每次都要消一个[L,R]，[L,R]中不能包含x
使得数列全相等的最少操作数
解析：
开始以为是贪心，但是光看样例就给否定了。原来是个模拟。
那么就考虑，对每个数字的出现位置进行记录，每次算一下如果选它需要的操作数，取个最小值就行了。
但是细节是颇多的。其实对比别人的话，我是写的有点太丑了。。。。。vector写的比较简单，看来还是太菜了。。。
具体注释看代码：
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> using namespace std; typedef long long ll; const int maxn=2e5+10; const int inf=99999999; int a[maxn]; int v1[maxn],v2[maxn]; int main() { int t; cin>>t; while(t--) { int n; cin>>n; for(int i=1;i<=n;i++) v1[i]=0; memset(v2,0,sizeof(v2));//记录每个数的操作数 map<int,int>mp;//记录出现次数 int minn=inf;int maxx=0; int sum=0; for(int i=1;i<=n;i++) { cin>>a[i]; int cnt=0; mp[a[i]]++; if(v1[a[i]]==0)//之前没出现过 { if(i==1)//目前处于开头，那么不需要操作 cnt=0; else cnt=1; } else { if(v1[a[i]]+1==i)//如果出现过，而且和上次出现位置相邻，不需操作 cnt=0; else cnt=1; } v1[a[i]]=i; v2[a[i]]+=cnt; } for(int i=1;i<=n;i++)//对最后出现不在末尾的，操作+1 { if(v1[i]<n&&mp[i]>0) { v2[i]++; } } // for(int i=1;i<=n;i++) // cout<<v2[i]<<" "; // cout<<"--"<<endl; int ok=0; for(int i=1;i<n;i++) { if(a[i]!=a[i+1]) { ok=1; break; } } if(ok==0) //全相等 cout<<"0"<<endl; else {for(int i=1;i<=n;i++) { if(v2[i]!=0) minn=min(minn,v2[i]); } cout<<minn<<endl; } } }
来个vector版的吧，vector<vector<int>>v(n+10);
#include<iostream> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<map> #include<stack> using namespace std; typedef long long ll; const int maxn=2e5+10; const int inf=99999999; int a[maxn]; int v1[maxn],v2[maxn]; int main() { int t; cin>>t; while(t--) { int n; cin>>n; int x; vector<vector<int>>v(n+10); for(int i=1;i<=n;i++) { cin>>x; v[x].push_back(i); } int minn=inf; for(int i=1;i<=n;i++) { if(v[i].empty()) continue; int md=2;//默认i的个出现位置，都处于2~n-1之间，所以默认操作2次 for(int j = 1 ; j < v[i].size();j++)//算的是所有数之间，不包括两边 { if(v[i][j]>v[i][j-1]+1)//不相邻 md++; } if(v[i][0]==1)//初始处于第一个位置，md-- md--; if(v[i][v[i].size()-1]==n)//同理 md--; minn=min(minn,md); } cout<<minn<<endl; } return 0; }
D：https://codeforces.com/contest/1454/problem/D
题意：
给出n
输出最长的一组数，它们的乘积能被n整除。而且ai能够整除ai-1
解析：
根据唯一分解定理：
找出出现次数最多的质因子，设出现次数x
那么先输出前x-1个，然后剩下那个乘到其他因数上变成一体就好了。
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> using namespace std; typedef long long ll; const int maxn=2e5+10; int a[maxn]; int v1[maxn],v2[maxn]; int main() { int t; cin>>t; while(t--) { ll n,nn; cin>>n; nn=n; int sum=0; map<ll,int>m; for(int i=2;i<=n/i;i++) { while(n%i==0) { n=n/i; m[i]++; sum++; } } if(n>1) { m[n]++; sum++; } ll maxx=0; ll md; for(int i=2;i<=nn/i;i++) { if(nn%i==0) { if(maxx<m[i]) { maxx=m[i]; md=i; } } } if(maxx==0) maxx=1; cout<<maxx<<endl; ll all=1; for(int i=1;i<=maxx-1;i++) { cout<<md<<" "; all*=md; m[md]--; } cout<<nn/all<<endl; } return 0; }