传送门
A Omkar and Completion
题意：构造序列，ax+ay!=az
思路：全输出1
int main()
{int T,n;scanf("%d",&T);while(T){T--;scanf("%d",&n);for(int i=1;i<=n;i++)printf("1 ");printf("\n");}return 0;
}
B Omkar and Last Class of Math
题意：给定n，求a, b满足a+b=n且LCM(a, b)最小
思路：
设x=gcd(a, b)，a=px, b=qx, 则有(p+q) * x=n。对于给定x，LCM= p * q * x, 由于p,q互质，显然
最优。那么
所以x越大越好，所以找到能整除n的最大的数，可以转化为找整除n的最小的质数，以减少运算次数。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int N=1e5+10;
LL mn=1e5;
int flag[N],prim[N];
int cnt=0;
void get_prim()
{for(LL i=2;i<=mn;i++){if(flag[(int)i]==0)prim[++cnt]=i;for(int j=1;j<=cnt;j++){if(prim[j]*i>mn)break;flag[(int)(prim[j]*i)]=1;if(i%prim[j]==0)break;}}
}
int main()
{get_prim();int T,n;scanf("%d",&T);while(T){T--;scanf("%d",&n);int i;for(i=1;i<=cnt;i++)if(n%prim[i]==0)break;if(i==cnt+1)printf("1 %d\n",n-1);elseprintf("%d %d\n",n/prim[i],n-n/prim[i]);} return 0;
}C Omkar and Baseball
题意：定义一次区间换序为：任意交换区间内任意多个数，使得每一个数都不在原来的位置上。求下列长度为n排列经过几次换序才可以变成升序。
思路：
0次：本身就是升序
1次：除了前缀和后缀，中间每一个数都不在原位
2次：其他
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2e5+10;
int a[N];
int main()
{int T;scanf("%d",&T);while(T){T--;int n,cnt1=0,cnt2=0,l,r;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++)if(a[i]!=i)cnt1++;if(cnt1==0) printf("0\n");else{for(l=1;l<=n;l++)if(l!=a[l])break;for(r=n;r>0;r--)if(r!=a[r])break;for(int i=l;i<=r;i++)if(a[i]==i)cnt2++;if(cnt2) printf("2\n");else printf("1\n");}} return 0;
}
D Omkar and Circle
题意：一串珠子（首尾相接），每个珠子有一个价值。每次操作，取走一个珠子，并将该珠子相邻的两个珠子合成一个。求最后一颗珠子的最大值。（N为奇数）
思路：可以看成选择一些珠子求和，选出的珠子中至多有一对是相邻的，其他的都相隔1, 3, 5……个。相隔3，5……个肯定比相隔1个答案要少，没有相邻的肯定比有相邻的方案答案要少。所以，最优的选择珠子的方案必然是某两个相邻，然后其他的珠子两两之间相隔一个（比如取出2，4，5，7，9这样的方案）。枚举相邻的位置，前缀和统计就可以了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2e5+10;
long long a[N],suma[N],sumb[N];
int main()
{int n;long long ans=0;scanf("%d",&n);for(int i=1;i<=n;i++){cin>>a[i];if(i&1) suma[i]+=a[i];else sumb[i]+=a[i];suma[i]+=suma[i-1];sumb[i]+=sumb[i-1];}for(int i=1;i<=n-2;i+=2) ans+=a[i];for(int i=1;i<=n;i++){if(i&1) ans=max(ans,suma[i]+sumb[n]-sumb[i]);else ans=max(ans,sumb[i]+suma[n]-suma[i]);}cout<<ans;return 0;}
F Omkar and Modes
题意：交互题。猜一个长度为n（n
）的不下降序列。询问l, r, 返回[l, r]内的众数x和出现次数f。序列中最多有k个互不相同的数，k
2500，要求询问不超过4k。
思路：
如果已知[l. r]内众数为x, 个数为f, 且x的一个位置为pos, 那么就可以求出x所在区间。x必然是[pos-f+1, pos]或[pos,pos+f-1]的众数，对这两个区间询问，可以求出x在其中一个区间内出现的次数，得到x的一个边界，由此推出另一个边界。
那么如何求出x的一个位置呢？在[l, r]区间内，每间隔f个数取一个，必然能取到x的一个位置。但是，这样一来询问次数就会变多，如何降低询问次数呢？记录被访问过的数的一个位置，存入map中，查找的时候从map中找出第一个比x小的数的位置，从这个位置开始找就可以了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
map<int,int>mp;
map<int,int>::iterator it;
const int N=2e5+10;
int ans[N];
void ask(int l,int r,int &x,int &f)
{printf("? %d %d\n",l,r);fflush(stdout);scanf("%d%d",&x,&f);
}
void get_ans(int l,int r,int x)
{for(int i=l;i<=r;i++)ans[i]=x;
}
void solve(int l,int r)
{if(l>r)return;int x,f;ask(l,r,x,f);if(f==r-l+1){get_ans(l,r,x);return;}it=mp.lower_bound(x);int pos;if(it != mp.end() && it->first == x) pos=it->second;else{--it;for(int i=max(l,it->second);i<=r;i+=f){int a,b;ask(i,i,a,b);mp[a]=i;if(a==x){pos=i;break;}}}int ll,rr,a;ask(max(l,pos-f+1),pos,a,ll);if(a==x){ll=pos-ll+1;rr=ll+f-1;}else{ask(pos,min(pos+f-1,r),a,rr);rr=pos+rr-1;ll=rr-f+1;}get_ans(ll,rr,x);solve(l,ll-1);solve(rr+1,r);
}
int main()
{int n;scanf("%d",&n);mp[0]=0;solve(1,n);printf("! ");for(int i=1;i<=n;i++)printf("%d ",ans[i]);printf("\n");fflush(stdout); return 0;
}