You are given one integer n (n>1).
Recall that a permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation of length 5, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).
Your task is to find a permutation p of length n that there is no index i (1≤i≤n) such that pi=i (so, for all i from 1 to n the condition pi≠i should be satisfied).
You have to answer t independent test cases.
If there are several answers, you can print any. It can be proven that the answer exists for each n>1.
Input
The first line of the input contains one integer t (1≤t≤100) — the number of test cases. Then t test cases follow.
The only line of the test case contains one integer n (2≤n≤100) — the length of the permutation you have to find.
Output
For each test case, print n distinct integers p1,p2,…,pn — a permutation that there is no index i (1≤i≤n) such that pi=i (so, for all i from 1 to n the condition pi≠i should be satisfied).
If there are several answers, you can print any. It can be proven that the answer exists for each n>1.
输入：
2
2
5
输出：
2 1
2 1 5 3 4
AC代码：
#include<iostream>
using namespace std;
int a[105];
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
for(int i=1;i<n;i++)
a[i]=i+1;
a[n]=1;
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
}
There is a game called “Unique Bid Auction”. You can read more about it here: https://en.wikipedia.org/wiki/Unique_bid_auction (though you don’t have to do it to solve this problem).
Let’s simplify this game a bit. Formally, there are n participants, the i-th participant chose the number ai. The winner of the game is such a participant that the number he chose is unique (i. e. nobody else chose this number except him) and is minimal (i. e. among all unique values of a the minimum one is the winning one).
Your task is to find the index of the participant who won the game (or -1 if there is no winner). Indexing is 1-based, i. e. the participants are numbered from 1 to n.
You have to answer t independent test cases.
Input
The first line of the input contains one integer t (1≤t≤2e4) — the number of test cases. Then t test cases follow.
The first line of the test case contains one integer n (1≤n≤2e5) — the number of participants. The second line of the test case contains n integers a1,a2,…,an (1≤ai≤n), where ai is the i-th participant chosen number.
It is guaranteed that the sum of n does not exceed 2e5 (∑n≤2e5).
Output
For each test case, print the answer — the index of the participant who won the game (or -1 if there is no winner). Note that the answer is always unique.
输入：
6
2
1 1
3
2 1 3
4
2 2 2 3
1
1
5
2 3 2 4 2
6
1 1 5 5 4 4
输出：
-1
2
4
1
2
-1
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> cnt(n + 1), idx(n + 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++cnt[x];
idx[x] = i + 1;
}
int ans = -1;
for (int i = 0; i <= n; ++i) {
if (cnt[i] == 1) {
ans = idx[i];
break;
}
}
cout << ans << endl;
}
return 0;
}
C. Sequence Transformation
You are given a sequence a, initially consisting of n integers.
You want to transform this sequence so that all elements in it are equal (i. e. it contains several occurrences of the same element).
To achieve this, you choose some integer x that occurs at least once in a, and then perform the following operation any number of times (possibly zero): choose some segment [l,r] of the sequence and remove it. But there is one exception: you are not allowed to choose a segment that contains x. More formally, you choose some contiguous subsequence [al,al+1,…,ar] such that ai≠x if l≤i≤r, and remove it. After removal, the numbering of elements to the right of the removed segment changes: the element that was the (r+1)-th is now l-th, the element that was (r+2)-th is now (l+1)-th, and so on (i. e. the remaining sequence just collapses).
Note that you can not change x after you chose it.
For example, suppose n=6, a=[1,3,2,4,1,2]. Then one of the ways to transform it in two operations is to choose x=1, then:
choose l=2, r=4, so the resulting sequence is a=[1,1,2];
choose l=3, r=3, so the resulting sequence is a=[1,1].
Note that choosing x is not an operation. Also, note that you can not remove any occurrence of x.
Your task is to find the minimum number of operations required to transform the sequence in a way described above.
You have to answer t independent test cases.
Input
The first line of the input contains one integer t (1≤t≤2e4) — the number of test cases. Then t test cases follow.
The first line of the test case contains one integer n (1≤n≤2e5) — the number of elements in a. The second line of the test case contains n integers a1,a2,…,an (1≤ai≤n), where ai is the i-th element of a.
It is guaranteed that the sum of n does not exceed 2e5 (∑n≤2e5).
Output
For each test case, print the answer — the minimum number of operations required to transform the given sequence in a way described in the problem statement. It can be proven that it is always possible to perform a finite sequence of operations so the sequence is transformed in the required way.
输入：
5
3
1 1 1
5
1 2 3 4 5
5
1 2 3 2 1
7
1 2 3 1 2 3 1
11
2 2 1 2 3 2 1 2 3 1 2
输出：
0
1
1
2
3
AC代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
int a[n+4],b[n+4];
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
int minn=inf;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]!=a[i-1]) b[a[i]]++;
}
b[a[1]]--;b[a[n]]--;
for(int i=1;i<=n;i++) minn=min(minn,b[a[i]]);
cout<<minn+1<<endl;
}
return 0;
}
You are given an integer n (n>1).
Your task is to find a sequence of integers a1,a2,…,ak such that:
each ai is strictly greater than 1;
a1⋅a2⋅…⋅ak=n (i. e. the product of this sequence is n);
ai+1 is divisible by ai for each i from 1 to k−1;
k is the maximum possible (i. e. the length of this sequence is the maximum possible).
If there are several such sequences, any of them is acceptable. It can be proven that at least one valid sequence always exists for any integer n>1.
You have to answer t independent test cases.
Input
The first line of the input contains one integer t (1≤t≤5000) — the number of test cases. Then t test cases follow.
The only line of the test case contains one integer n (2≤n≤1e10).
It is guaranteed that the sum of n does not exceed 1010 (∑n≤1e10).
输入：
4
2
360
4999999937
4998207083
输出：
1
2
3
2 2 90
1
4999999937
1
4998207083
AC代码：
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
ll t,n,cnt,ans;
pair<ll,ll>p; //记录质因数的个数以及数值
int main(){
scanf("%d",&t);
while(t--){
p.first=p.second=0;
cin>>n;
ans=n;
for(ll i=2;i*i<=n;i++){
int cnt=0;
while(n%i==0) {
cnt++;
n/=i;
}
if(cnt>p.first){
p.first=cnt;
p.second=i;
cnt=0;
}
}
if(p.first==0) cout<<1<<"\n"<<n<<endl;
else{
cout<<p.first<<endl;
for(ll i=1;i<p.first;i++)
{
ans/=p.second;
cout<<p.second<<" ";
}
cout<<ans<<endl;
}
}
return 0;
}
You are given an undirected graph consisting of n vertices and n edges. It is guaranteed that the given graph is connected (i. e. it is possible to reach any vertex from any other vertex) and there are no self-loops and multiple edges in the graph.
Your task is to calculate the number of simple paths of length at least 1 in the given graph. Note that paths that differ only by their direction are considered the same (i. e. you have to calculate the number of undirected paths). For example, paths [1,2,3] and [3,2,1] are considered the same.
You have to answer t independent test cases.
Recall that a path in the graph is a sequence of vertices v1,v2,…,vk such that each pair of adjacent (consecutive) vertices in this sequence is connected by an edge. The length of the path is the number of edges in it. A simple path is such a path that all vertices in it are distinct.
Input
The first line of the input contains one integer t (1≤t≤2e4) — the number of test cases. Then t test cases follow.
The first line of the test case contains one integer n (3≤n≤2e5) — the number of vertices (and the number of edges) in the graph.
The next n lines of the test case describe edges: edge i is given as a pair of vertices ui, vi (1≤ui,vi≤n, ui≠vi), where ui and vi are vertices the i-th edge connects. For each pair of vertices (u,v), there is at most one edge between u and v. There are no edges from the vertex to itself. So, there are no self-loops and multiple edges in the graph. The graph is undirected, i. e. all its edges are bidirectional. The graph is connected, i. e. it is possible to reach any vertex from any other vertex by moving along the edges of the graph.
It is guaranteed that the sum of n does not exceed 2⋅105 (∑n≤2e5).
Output
For each test case, print one integer: the number of simple paths of length at least 1 in the given graph. Note that paths that differ only by their direction are considered the same (i. e. you have to calculate the number of undirected paths).
输入：
3
3
1 2
2 3
1 3
4
1 2
2 3
3 4
4 2
5
1 2
2 3
1 3
2 5
4 3
输出：
6
11
18
AC代码：
include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int n,fa[maxn],t[maxn],tot;
bool vis[maxn],loop[maxn]; //k用来记录以环上的点为树根建的小树的顶点数
vector<int>g[maxn];
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
void Init(){
memset(loop,0,sizeof(loop));
memset(vis,0,sizeof(vis));
memset(t,0,sizeof(t));
tot=0;
for(int i=1;i<=n;i++) {fa[i]=i;g[i].clear();}
}
void get_loop(int u){
t[u]=++tot;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(fa[u]==v) continue;
if(t[v]){
if(t[v]<t[u]) continue;
loop[v]=1;
for(;v!=u;v=fa[v]) loop[fa[v]]=1;
}
else {fa[v]=u;get_loop(v);}
}
}
int dfs(int u){
int result=1;
vis[u]=1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(loop[v]||vis[v]) continue;
result+=dfs(v);
}
return result;
}
int main(){
int T;
T=read();
while(T--){
n=read();
Init();
for(int i=1;i<=n;i++){
int u,v;
u=read();v=read();
g[u].push_back(v);
g[v].push_back(u);
}ll ans=0;
get_loop(1);
for(int i=1;i<=n;i++){
if(loop[i]){
ll k=dfs(i);
ans+=k*(n-k)+k*(k-1)/2;
}
}
cout<<ans<<endl;
}
return 0;
}
You are given an array a consisting of n integers.
Let min(l,r) be the minimum value among al,al+1,…,ar and max(l,r) be
the maximum value among al,al+1,…,ar.Your task is to choose three positive (greater than 0) integers x, y
and z such that:x+y+z=n; max(1,x)=min(x+1,x+y)=max(x+y+1,n). In other words, you have
to split the array a into three consecutive non-empty parts that cover
the whole array and the maximum in the first part equals the minimum
in the second part and equals the maximum in the third part (or
determine it is impossible to find such a partition).Among all such triples (partitions), you can choose any.
You have to answer t independent test cases.
Input The first line of the input contains one integer t (1≤t≤2e4) —
the number of test cases. Then t test cases follow.The first line of the test case contains one integer n (3≤n≤2e5) —
the length of a.The second line of the test case contains n integers a1,a2,…,an
(1≤ai≤1e9), where ai is the i-th element of a.It is guaranteed that the sum of n does not exceed 2e5(∑n≤2e5).
Output For each test case, print the answer: NO in the only line if
there is no such partition of a that satisfies the conditions from the
problem statement. Otherwise, print YES in the first line and three
integers x, y and z (x+y+z=n) in the second line.If there are several answers, you can print any.
输入：
6
11
1 2 3 3 3 4 4 3 4 2 1
8
2 9 1 7 3 9 4 1
9
2 1 4 2 4 3 3 1 2
7
4 2 1 1 4 1 4
5
1 1 1 1 1
7
4 3 4 3 3 3 4
输出：
YES
6 1 4
NO
YES
2 5 2
YES
4 1 2
YES
1 1 3
YES
2 1 4
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=2e5+10;
const int maxx=100;
int a[maxn],Log[maxn],b[40],dmin[maxx][maxn],dmax[maxx][maxn];
int n;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
void Init(){
b[0]=1;
for(int i=1;i<=20;i++) b[i]=b[i-1]*2;
Log[0]=-1;
for(int i=1;i<=n;i++) Log[i]=Log[i/2]+1;
for(int i=1;i<=n;i++) dmin[0][i]=dmax[0][i]=a[i];
for(int i=1;i<=Log[n];i++)
for(int j=1;j<=n;j++)
if(j+b[i]-1<=n) dmin[i][j]=min(dmin[i-1][j],dmin[i-1][j+b[i-1]]),dmax[i][j]=max(dmax[i-1][j],dmax[i-1][j+b[i-1]]);
}
inline int getmax(int l,int r){
int k=Log[r-l+1];
return max(dmax[k][l],dmax[k][r-b[k]+1]);
}
inline int getmin(int l,int r){
int k=Log[r-l+1];
return min(dmin[k][l],dmin[k][r-b[k]+1]);
}
int main(){
int t;t=read();
while(t--){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
Init();
bool flag=0;
for(int i=1;i<=n-2;i++){
int ans1=getmax(1,i);
int l=i+1,r=n-1,mid,vis=0;
while(l<=r){
mid=(l+r)/2;
int ans2=getmin(i+1,mid),ans3=getmax(mid+1,n);
if(ans1<ans2||ans1<ans3) l=mid+1;
else if(ans1>ans2||ans1>ans3) r=mid-1;
else {
cout<<"YES\n"<<i<<" "<<mid-i<<" "<<n-mid<<endl;
vis=flag=1;
break;
}
}
if(vis) break;
}
if(!flag) cout<<"NO"<<endl;
}
return 0;
}