T1
傻逼快速幂，敲敲就过了。
我跟你们讲个笑话当时我以为这个数据范围过不了于是想出了求GCD再推规律什么的magic方法中途还咨询了某个学长。
然后怎么想都是不可做。
……直到我发现我昨年的代码一个傻逼快速幂就过了=A=
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
int n=,m=,k=,x=;
long long quick(int x,int y);
int main(void)
{
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&k,&x);
long long ans=quick(,k);
ans=ans*m%n;
ans=(ans+x)%n;
printf("%lld",ans);
return ;
} long long quick(int x,int y)
{
if(y==)return x;
int ins=y/;
long long tot=0ll;
tot=quick(x,ins)%n;
tot=tot*tot%n;
if(y%)tot=tot*x%n;
return tot;
}
T2
排个序，离散化之后找逆序对即可。
这里要注意的是，我们先把两个数列离散化+排序之后，是找第二个数列里的数在第一个数列里出现的位置，然后对这个序列求逆序对。
我为了这个映射卖了很多蠢就不说了。
我会说因为我不想写归并于是用了树状数组求逆序对？
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
struct line
{
int sum;
int num;
};
line xl_a[],xl_b[];
int n=,stack[]={},top=;
int mark[]={},tree[]={};
const int mod=;
bool cmp(line a,line b);
bool kp(line a,line b);
int lowbit(int x);
int red(int x);
void add(int x);
int main(void)
{
freopen("match.in","r",stdin);
freopen("match.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&xl_a[i].sum),xl_a[i].num=i;
sort(xl_a+,xl_a+n+,cmp);
for(int i=;i<=n;i++)xl_a[i].sum=i; for(int i=;i<=n;i++)scanf("%d",&xl_b[i].sum),xl_b[i].num=i;
sort(xl_b+,xl_b+n+,cmp);
for(int i=;i<=n;i++)xl_b[i].sum=i; sort(xl_b+,xl_b+n+,kp);
for(int i=;i<=n;i++)mark[i]=xl_a[xl_b[i].sum].num; long long ans=; for(int i=;i<=n;i++)
{
ans+=red(n)-red(mark[i]);
ans%=mod;
add(mark[i]);
}
printf("%d",ans);
return ;
} bool cmp(line a,line b)
{
if(a.sum<b.sum)return ;
return ;
} bool kp(line a,line b)
{
if(a.num<b.num)return ;
return ;
} int lowbit(int x){return x&-x;} int red(int x)
{
int tot=;
while(x)
{
tot+=tree[x];
tot%=mod;
x-=lowbit(x);
}
return tot;
} void add(int x)
{
while(x<=n)
{
tree[x]++;
tree[x]%=mod;
x+=lowbit(x);
}
}
T3
最大生成树+树上倍增标准模板
调了半小时发现我预处理写错了。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
struct bian
{
int x;
int y;
int v;
};
bian a[];//因为我们是存储双向边所以边数量x2
struct lb
{
int u;
int to;
int val;
};
lb line[];
int head[]={},fa[]={},n=,m=,q=;
int cnt_1=,cnt_2=,deep[]={};
int beiz[][]={},value[][]={};
//最大生成树函数x3
void kruskal();
int fid(int x);
void heb(int x,int y);
//树上倍增
void dfs(int nw);//确定树
void pre(int x);//倍增预处理
int ask(int x,int y);//查询两点之间的公共祖先
//乱七八糟的函数
void add(int f,int t,int val);
bool cmp(bian A,bian B);
int main(void)
{
freopen("truck.in","r",stdin);
freopen("truck.out","w",stdout);
scanf("%d%d",&n,&m);
int b=,c=,d=;
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&b,&c,&d);
cnt_1++;
a[cnt_1].x=b,a[cnt_1].y=c,a[cnt_1].v=d;
swap(b,c);
cnt_1++;
a[cnt_1].x=b,a[cnt_1].y=c,a[cnt_1].v=d;
}
sort(a+,a+cnt_1+,cmp);
for(int i=;i<=n;i++)fa[i]=i;
kruskal();
memset(beiz,-,sizeof(beiz));
beiz[][]=,value[][]=0x7ffffff,deep[]=;
dfs();
pre();
scanf("%d",&q);//我觉得是根节点的问题……
for(int i=;i<=q;i++)
{
scanf("%d%d",&b,&c);
if(beiz[b][]==-||beiz[c][]==-)
{
printf("-1\n");
continue;
}
printf("%d\n",ask(b,c));
}
return ;
}
bool cmp(bian A,bian B)
{
if(A.v>B.v)return ;
return ;
} int fid(int x)
{
if(fa[x]==x)return x;
fa[x]=fid(fa[x]);
return fa[x];
} void heb(int x,int y)
{
fa[x]=y;
return;
} void kruskal()
{
int cho=,f_x=,f_y=;
for(int i=;i<=cnt_1;i++)
{
if(cho==n-)break;
f_x=fid(a[i].x);
f_y=fid(a[i].y);
if(f_x==f_y)continue;
cho++;
add(a[i].x,a[i].y,a[i].v);
add(a[i].y,a[i].x,a[i].v);
heb(f_x,f_y);
}
return;
} void add(int f,int t,int val)
{
line[++cnt_2].u=t;
line[cnt_2].to=head[f];
line[cnt_2].val=val;
head[f]=cnt_2;
return;
} void dfs(int nw)
{
if(nw>n)return;
int next=;
for(int i=head[nw];i>;i=line[i].to)
{
next=line[i].u;
if(next==beiz[nw][])continue;
beiz[next][]=nw;
value[next][]=line[i].val;
deep[next]=deep[nw]+;
dfs(next);
}
return;
} void pre(int nw)
{
if(nw>=)return;
for(int i=;i<=n;i++)
{
beiz[i][nw]=beiz[beiz[i][nw-]][nw-];
value[i][nw]=min(value[i][nw-],value[beiz[i][nw-]][nw-]);
}
pre(nw+);
return;
} int ask(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
int ans=0x7fffffff;
for(int i=;i>=;i--)if(deep[x]-(<<i)>=deep[y])ans=min(ans,value[x][i]),x=beiz[x][i];
if(x==y)return ans;
for(int i=;i>=;i--)
{
if(beiz[x][i]!=beiz[y][i])
{
ans=min(ans,value[x][i]);
x=beiz[x][i];
ans=min(ans,value[y][i]);
y=beiz[y][i];
}
}
ans=min(ans,value[x][]);
ans=min(ans,value[y][]);
return ans;
}