Problem B
题面
In Omkar's last class of math, he learned about the least common multiple, or LCM. LCM(a,b) is the smallest positive integer x which is divisible by both a and b.
Omkar, having a laudably curious mind, immediately thought of a problem involving the LCM operation: given an integer n, find positive integers a and b such that a+b=n and LCM(a,b) is the minimum value possible.
Can you help Omkar solve his ludicrously challenging math problem?
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤10). Description of the test cases follows.
Each test case consists of a single integer n (2≤n≤109).
Output
For each test case, output two positive integers a and b, such that a+b=n and LCM(a,b) is the minimum possible.
思路
数学题，当a和b的gcd不等于1时，gcd(a,b)=gcd (a,n-a)=gcd(n/i,n-n/i)=gcd (a,a(i-1)),得到此时的gcd（a,b）就等于a，所以我们去求最小可以被n整除的数，就是答案，否则输出1和n-1，保证lcm相对小。
代码实现
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=start;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define exp 1e-8
#define N 1000005
#define fi first
#define se second
#define pb push_back
const int mod=1e9+7;
typedef long long ll;
typedef vector <int> VI;
typedef pair<int ,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<int ,PII> PIII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
char ch=getchar(); int x=0, f=1;
while(ch<'0'||ch>'9') {
if(ch=='-') f=-1;
ch=getchar();
} while('0'<=ch&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
} return x*f;
}
int main () {
int t;
cin>>t;
while (t--) {
int n;
cin>>n;
int flag=0;
rep (i,2,sqrt (n)) {
if (n%i==0) {
int x=n/i;
cout<<x<<" "<<n-x<<endl;
flag=1;
break;
}
}
if (!flag) cout<<1<<" "<<n-1<<endl;
}
return 0;
}
Problem C
题面
Patrick likes to play baseball, but sometimes he will spend so many hours hitting home runs that his mind starts to get foggy! Patrick is sure that his scores across n sessions follow the identity permutation (ie. in the first game he scores 1 point, in the second game he scores 2 points and so on). However, when he checks back to his record, he sees that all the numbers are mixed up!
Define a special exchange as the following: choose any subarray of the scores and permute elements such that no element of subarray gets to the same position as it was before the exchange. For example, performing a special exchange on [1,2,3] can yield [3,1,2] but it cannot yield [3,2,1] since the 2 is in the same position.
Given a permutation of n integers, please help Patrick find the minimum number of special exchanges needed to make the permutation sorted! It can be proved that under given constraints this number doesn't exceed 1018.
An array a is a subarray of an array b if a can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). Description of the test cases follows.
The first line of each test case contains integer n (1≤n≤2⋅105) — the length of the given permutation.
The second line of each test case contains n integers a1,a2,...,an (1≤ai≤n) — the initial permutation.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
Output
For each test case, output one integer: the minimum number of special exchanges needed to sort the permutation.
思路
可以发现，最多两次就可以搞定，那么我们对比原序列和排序完成的序列，如果一样，就输出0，如果只有1那么输出1,。
代码实现
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=start;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define exp 1e-8
#define N 1000005
#define fi first
#define se second
#define pb push_back
const int mod=1e9+7;
typedef long long ll;
typedef vector <int> VI;
typedef pair<int ,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<int ,PII> PIII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
char ch=getchar(); int x=0, f=1;
while(ch<'0'||ch>'9') {
if(ch=='-') f=-1;
ch=getchar();
} while('0'<=ch&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
} return x*f;
}
const int maxn=2e6+10;
int a[maxn],b[maxn];
int main () {
int t;
cin>>t;
while (t--) {
int n;
cin>>n;
rep (i,1,n) cin>>a[i];
int flag=0,cnt=0,x=1;
rep (i,1,n) {
if (a[i]!=i) {
flag=1;
if (x) {
cnt++;
x=0;
}
}
if (a[i]==i) x=1;
}
if (flag==0) cout<<0<<endl;
else if (cnt==1) cout<<1<<endl;
else cout<<2<<endl;
}
return 0;
}
Problem D
题面
Danny, the local Math Maniac, is fascinated by circles, Omkar's most recent creation. Help him solve this circle problem!
You are given n nonnegative integers a1,a2,…,an arranged in a circle, where n must be odd (ie. n−1 is divisible by 2). Formally, for all i such that 2≤i≤n, the elements ai−1 and ai are considered to be adjacent, and an and a1 are also considered to be adjacent. In one operation, you pick a number on the circle, replace it with the sum of the two elements adjacent to it, and then delete the two adjacent elements from the circle. This is repeated until only one number remains in the circle, which we call the circular value.
Help Danny find the maximum possible circular value after some sequences of operations.
Input
The first line contains one odd integer n (1≤n<2⋅105, n is odd) — the initial size of the circle.
The second line contains n integers a1,a2,…,an (0≤ai≤109) — the initial numbers in the circle.
Output
Output the maximum possible circular value after applying some sequence of operations to the given circle.
思路
说有一个序列，我排成环形，每次操作可以把一个元素用相邻元素的和代替，问最后得到的可以最大值是多少。环形的话直接破开，然后我们可以发现取得的值都是相隔一定的距离，只是开始和结束的点不一样，我们直接累加前缀和暴力枚举就好了，不过这个前缀和要分一下奇偶。
代码实现
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=start;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define exp 1e-8
#define N 1000005
#define fi first
#define se second
#define pb push_back
const int mod=1e9+7;
typedef long long ll;
typedef vector <int> VI;
typedef pair<int ,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<int ,PII> PIII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
char ch=getchar(); int x=0, f=1;
while(ch<'0'||ch>'9') {
if(ch=='-') f=-1;
ch=getchar();
} while('0'<=ch&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
} return x*f;
}
const int maxn=4e5+10;
ll a[maxn],sum[maxn];
int main () {
int n;
cin>>n;
rep (i,1,n) {
cin>>a[i];
a[i+n]=a[i];
}
sum[1]=a[1];
rep (i,2,2*n) sum[i]=sum[i-2]+a[i];
ll ans=0;
rep (i,n+1,2*n) ans=max (ans,sum[i]-sum[i-n-1]);
cout<<ans<<endl;
return 0;
}