A
A 题只需要求出最小的字符，然后把其余的字符按顺序输出即可，没有什么难度。
代码：
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N number
#define M number
using namespace std;
const int INF=0x3f3f3f3f;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int t;
string s;
int main(){
read(t);
while(t--){
cin>>s;
int len=s.length();
int Minc=INF;
for(int i=0;i<len;i++){
Minc=min(Minc,(int)s[i]);
}
putchar((char)Minc);
putchar(' ');
for(int i=0;i<len;i++){
if(s[i]==Minc) Minc=0;
else putchar(s[i]);
}
puts("");
}
return 0;
}
B
容易发现这个序列的变化次数不会超过 (2000) 次，这个事实不难证明，或者说，这个东西看起来就是对的。所以这个题就相当于模拟。
模拟即可。
代码：
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 2010
#define M number
using namespace std;
const int INF=0x3f3f3f3f;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int cnt[N];
int a[N][N],n,t,q;
inline void Init(){
read(n);
for(int i=1;i<=n;i++) read(a[0][i]);
}
inline void Change(int id){
for(int i=1;i<=n;i++) cnt[i]=0;
for(int i=1;i<=n;i++) cnt[a[id-1][i]]++;
for(int i=1;i<=n;i++) a[id][i]=cnt[a[id-1][i]];
}
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(t);
while(t--){
Init();
for(int i=1;i<=2000;i++) Change(i);
read(q);
for(int i=1;i<=q;i++){
int x,k;read(x);read(k);
if(k>2000) k=2000;
printf("%d
",a[k][x]);
}
}
}
C
注意到答案就是所有非零的二进制位，把每一位出现次数加起来，然后直接做 (gcd) 就可以，注意判断全是 (0) 的情况。
代码：
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 200010
#define M number
using namespace std;
const int INF=0x3f3f3f3f;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int t,n,a[N],cnt[N],ans[N],tail;
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
inline void Init(){
read(n);
for(int i=1;i<=n;i++) read(a[i]);
}
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(t);
while(t--){
tail=0;
for(int i=0;i<=30;i++) cnt[i]=0;
Init();
bool op=1;
for(int i=1;i<=n;i++) if(a[i]!=0) op=0;
if(op){
for(int i=1;i<=n;i++) printf("%d ",i);puts("");continue;
}
for(int i=1;i<=n;i++){
for(int j=30;j>=0;j--){
if((a[i]>>j)&1) cnt[j]++;
}
}
int g=-1;
for(int i=30;i>=0;i--){
if(!cnt[i]) continue;
if(g==-1) g=cnt[i];
else g=gcd(g,cnt[i]);
}
int i;
for(i=1;i*i<g;i++){
if(g%i==0){
ans[++tail]=i;ans[++tail]=g/i;
}
}
if(g==i*i) ans[++tail]=i;
sort(ans+1,ans+tail+1);
for(int i=1;i<=tail;i++) printf("%d ",ans[i]);
puts("");
}
}
D
D 题一开始没有想到图论建模，然后在 dalao nyy 的秒杀之下才发现这个东西其实直接硬上线段树优化建图就行。
发现这个东西我们可以建两列点，左边一列向右边一列连边表示掉下去，右边向左边表示向上走，容易发现右边向左边连边其实连的是一段区间，可以用线段树优化建图，然后建完图直接跑最短路就可以。
代码：
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 300010
#define M number
using namespace std;
const int INF=0x3f3f3f3f;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
struct edge{
int to,next,w;
inline void Init(int to_,int ne_,int w_){
to=to_;next=ne_;w=w_;
}
}li[20*N];
int head[5*N],tail,tot,rt,rk[N*5];
int id[N],n,a[N],b[N],ID[N],at,flag;
int d[N*5],s,nowtot;
bool vis[N*5];
pair<int,int> Pre[N*5];
typedef pair<int,int> P;
pair<int,P> ans[N*5];
inline void Add(int from,int to,int w){
li[++tail].Init(to,head[from],w);
head[from]=tail;
}
#define ls(k) p[k].ls
#define rs(k) p[k].rs
struct Node{
int ls,rs;
}p[N<<2];
inline int Build(int l,int r){
if(l==r){
++tot;id[l]=tot;rk[tot]=l;
if(l==0) flag=tot;
return tot;
}
tot++;int k=tot;
int mid=(l+r)>>1;
ls(k)=Build(l,mid);rs(k)=Build(mid+1,r);
Add(k,ls(k),0);Add(k,rs(k),0);
return k;
}
inline void Find(int k,int now,int l,int r,int z,int y){
if(l==z&&r==y){Add(now,k,1);return;}
int mid=(l+r)>>1;
if(y<=mid) Find(ls(k),now,l,mid,z,y);
else if(z>mid) Find(rs(k),now,mid+1,r,z,y);
else{Find(ls(k),now,l,mid,z,mid);Find(rs(k),now,mid+1,r,mid+1,y);}
}
inline void Init(){
read(n);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n;i++) read(b[i]);
}
inline void Mapping(){
nowtot=tot;
for(int i=1;i<=n;i++){
ID[i]=++tot;
}
// for(int i=1;i<=n;i++) printf("id[%d]=%d
",i,id[i]);
for(int i=1;i<=n;i++) Add(id[i],ID[i+b[i]],0);
for(int i=1;i<=n;i++){
Find(rt,ID[i],0,n,i-a[i],i);
}
}
deque<int> q;
inline void bfs(){
memset(d,INF,sizeof(d));
d[s]=0;
q.push_back(s);
while(q.size()){
int top=q.front();q.pop_front();
if(vis[top]) continue;
vis[top]=1;
for(int x=head[top];x;x=li[x].next){
int to=li[x].to,w=li[x].w;
if(d[to]<=d[top]+w) continue;
d[to]=d[top]+w;Pre[to]=make_pair(top,w);
if(w) q.push_back(to);
else q.push_front(to);
}
}
}
inline void Print(){
if(d[id[0]]==INF){puts("-1");return;}
printf("%d
",d[id[0]]);
int now=id[0];
while(now){
P pre=Pre[now];
ans[++at]=make_pair(pre.first,make_pair(pre.second,now));
now=pre.first;
}
reverse(ans+1,ans+at+1);
// printf("flag=%d
",flag);printf("id[0]=%d
",id[0]);
bool op=0;
for(int i=1;i<=at;i++){
if(ans[i].second.first) op=1;
if(rk[ans[i].second.second]||ans[i].second.second==flag){
op=0;printf("%d ",rk[ans[i].second.second]);
}
}
}
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
// printf("Complete Initing
");
Init();rt=Build(0,n);Mapping();
s=ID[n];bfs();Print();
}
E
这个题其实并不是很难，但是看了题解才恍然大悟。我们发现，(b) 一定是一个升序的数组，所以逆序对个数一定出自 (a,b) 两个序列之间以及 (a) 序列内部。(a) 序列内部的逆序对已经确定了，我们考虑两个序列之间的怎么算。
我们考虑 (b) 中的每个元素放进 (a) 中时是独立的，且位置是递增的，所以我们可以直接扫一遍，然后用树状数组维护逆序对，但这样实现难度较大。
我们考虑用分治，先解决中间，然后再做两边，同时维护值域，这样就可以做完了，复杂度 ((n+m)log n)，最后用树状数组统计答案。
代码：
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define int long long
#define uint unsigned int
#define ull unsigned long long
#define N 1000100
#define M number
using namespace std;
const int INF=0x3f3f3f3f;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int posi[N],a[N],b[N],n,m,c[N<<1],tail,t,Pre[N],Suf[N];
struct BIT{
int p[N<<1];
inline int lowbit(int x){return x&(-x);}
inline void PreAdd(int w,int x){
for(int i=w;i<=tail;i+=lowbit(i)) p[i]+=x;
}
inline int PreAsk(int w){
int res=0;for(int i=w;i>=1;i-=lowbit(i)) res+=p[i];return res;
}
inline void SufAdd(int w,int x){
for(int i=w;i>=1;i-=lowbit(i)) p[i]+=x;
}
inline int AskSuf(int w){
int res=0;for(int i=w;i<=tail;i+=lowbit(i)) res+=p[i];return res;
}
inline void Clear(int n){
for(int i=1;i<=n;i++) p[i]=0;
}
}bit;
inline void Init(){
read(n);read(m);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=m;i++) read(b[i]);
for(int i=1;i<=n;i++) c[++tail]=a[i];
for(int i=1;i<=m;i++) c[++tail]=b[i];
sort(c+1,c+tail+1);int len=unique(c+1,c+tail+1)-c-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(c+1,c+len+1,a[i])-c;
for(int i=1;i<=m;i++) b[i]=lower_bound(c+1,c+len+1,b[i])-c;
sort(b+1,b+m+1);a[n+1]=INF;
}
inline void Solve(int l,int r,int Rl,int Rr){
if(r<l) return;
int mid=(l+r)>>1;
Pre[Rl]=0;
for(int i=Rl+1;i<=Rr;i++){
Pre[i]=Pre[i-1];
if(a[i-1]>b[mid]) Pre[i]++;
}
Suf[Rr]=0;
for(int i=Rr-1;i>=Rl;i--){
Suf[i]=Suf[i+1];
if(b[mid]>a[i]) Suf[i]++;
}
int minn=INF,minp=-1;
for(int i=Rl;i<=Rr;i++){
if(minn>Pre[i]+Suf[i]){
minn=Pre[i]+Suf[i];
minp=i;
}
}
posi[mid]=minp;
Solve(l,mid-1,Rl,minp);
Solve(mid+1,r,minp,Rr);
}
inline int GetAns(){
// for(int i=1;i<=m;i++) printf("%d ",posi[i]);puts("");
int now=0,ans=0;
for(int i=1;i<=m;i++){
while(now<posi[i]-1){
now++;
bit.SufAdd(a[now],1);
}
ans+=bit.AskSuf(b[i]+1);
}
// printf("ans=%d
",ans);
bit.Clear(tail);
now=n+1;
for(int i=m;i>=1;i--){
while(now>posi[i]){
now--;
bit.PreAdd(a[now],1);
}
ans+=bit.PreAsk(b[i]-1);
}
// printf("ans=%d
",ans);
bit.Clear(tail);
for(int i=n;i>=1;i--){
ans+=bit.PreAsk(a[i]-1);
bit.PreAdd(a[i],1);
}
// printf("ans=%d
",ans);
bit.Clear(tail);
tail=0;
return ans;
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(t);
while(t--){
Init();Solve(1,m,1,n+1);
printf("%lld
",GetAns());
}
return 0;
}
F
这个题贪心非常妙，这个题其实我如果一个贪心策略与两个元素的大小都有关系，不妨考虑其最小值或最大值，或者加减乘除运算。这个题就是一个典型的考虑最大值的贪心。
先说贪心策略：按照 (max(s,a)) 排序，从小到大；然后再按照 (s) 从小到大排序，最后按照 (a)。
我们考虑上面贪心策略的正确性：设 (max(s_i,a_i)<max(s_j,a_j))
-
(s_ige a_i,s_jge a_j)
这种情况不难发现，如果我们先让 (i) 爬，(j) 一定可以爬，但是如果我们先让 (j) 爬，(i) 可能不能爬，所以我们先让 (i) 爬，不会使答案变劣。
-
(s_ige a_i,s_j<a_j)
如果我们先让 (i) 爬，然后 (j) 一定可以爬，如果我们先让 (j) 爬，(i) 一定不能爬。我们先让 (i) 爬，会使答案变优。
-
(s_i< a_i,s_jge a_j)
如果我们先让 (i) 爬，然后 (j) 一定可以爬，但是如果我们先让 (j) 爬，(i) 可能不能爬，所以我们先让 (i) 爬不会使答案变劣。
-
(s_i<a_i,s_j<a_j)
如果我们先让 (i) 爬，(j) 可能能爬，如果 (j) 先爬，则 (i) 一定不能爬，让 (i) 先爬，不会是答案变劣。
同理，经过同样的分析，我们可以得到当最值相等时我们让 (s) 小的先爬不会使答案变劣。
排序直接跑就可以。
代码：
#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define int long long
#define uint unsigned int
#define ull unsigned long long
#define N 1000100
#define M number
using namespace std;
const int INF=0x3f3f3f3f;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int posi[N],a[N],b[N],n,m,c[N<<1],tail,t,Pre[N],Suf[N];
struct BIT{
int p[N<<1];
inline int lowbit(int x){return x&(-x);}
inline void PreAdd(int w,int x){
for(int i=w;i<=tail;i+=lowbit(i)) p[i]+=x;
}
inline int PreAsk(int w){
int res=0;for(int i=w;i>=1;i-=lowbit(i)) res+=p[i];return res;
}
inline void SufAdd(int w,int x){
for(int i=w;i>=1;i-=lowbit(i)) p[i]+=x;
}
inline int AskSuf(int w){
int res=0;for(int i=w;i<=tail;i+=lowbit(i)) res+=p[i];return res;
}
inline void Clear(int n){
for(int i=1;i<=n;i++) p[i]=0;
}
}bit;
inline void Init(){
read(n);read(m);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=m;i++) read(b[i]);
for(int i=1;i<=n;i++) c[++tail]=a[i];
for(int i=1;i<=m;i++) c[++tail]=b[i];
sort(c+1,c+tail+1);int len=unique(c+1,c+tail+1)-c-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(c+1,c+len+1,a[i])-c;
for(int i=1;i<=m;i++) b[i]=lower_bound(c+1,c+len+1,b[i])-c;
sort(b+1,b+m+1);a[n+1]=INF;
}
inline void Solve(int l,int r,int Rl,int Rr){
if(r<l) return;
int mid=(l+r)>>1;
Pre[Rl]=0;
for(int i=Rl+1;i<=Rr;i++){
Pre[i]=Pre[i-1];
if(a[i-1]>b[mid]) Pre[i]++;
}
Suf[Rr]=0;
for(int i=Rr-1;i>=Rl;i--){
Suf[i]=Suf[i+1];
if(b[mid]>a[i]) Suf[i]++;
}
int minn=INF,minp=-1;
for(int i=Rl;i<=Rr;i++){
if(minn>Pre[i]+Suf[i]){
minn=Pre[i]+Suf[i];
minp=i;
}
}
posi[mid]=minp;
Solve(l,mid-1,Rl,minp);
Solve(mid+1,r,minp,Rr);
}
inline int GetAns(){
// for(int i=1;i<=m;i++) printf("%d ",posi[i]);puts("");
int now=0,ans=0;
for(int i=1;i<=m;i++){
while(now<posi[i]-1){
now++;
bit.SufAdd(a[now],1);
}
ans+=bit.AskSuf(b[i]+1);
}
// printf("ans=%d
",ans);
bit.Clear(tail);
now=n+1;
for(int i=m;i>=1;i--){
while(now>posi[i]){
now--;
bit.PreAdd(a[now],1);
}
ans+=bit.PreAsk(b[i]-1);
}
// printf("ans=%d
",ans);
bit.Clear(tail);
for(int i=n;i>=1;i--){
ans+=bit.PreAsk(a[i]-1);
bit.PreAdd(a[i],1);
}
// printf("ans=%d
",ans);
bit.Clear(tail);
tail=0;
return ans;
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(t);
while(t--){
Init();Solve(1,m,1,n+1);
printf("%lld
",GetAns());
}
return 0;
}