A题：
又是一道送分题。。
快速幂一下就秒杀了，
5分钟A掉比较理想
比没有什么需要分析的东西
代码（。。。）：
#include<bits/stdc++.h>
using namespace std;
int ksm(int a,int b,int P){//博主英文不好。。
int res=;
while(b){
if(b&)res=ll*res*a%P;
a=ll*a*a%P;
b/=;
}return res%P;
}
int main(){
int n,m,k,x;
scanf("%d %d %d %d",&n,&m,&k,&x);
int tmp=ksm(,k,n)*m%n;
x=(x+tmp)%n;
printf("%d\n",x);
return ;
}
B题：
想要做这题，
首先你要有一点常识或是数学知识的储备
如果你有二者其一的话
你在看到这一题的第一眼就会明白
额。。。
这个不太好描述。。
好吧，我们还是先来看一道数学题目，
现在给出一个序列是 ai 是单调递增的
另有一个序列 bi ，现在你可以改变 bi 中各个数的位置，
使得他们的距离最小（即本题中的距离： ∑ni=1(ai−bi) ）
我们知道，但 bi 也为单调递增的时候，距离是最小的
但是怎么证明呢？
我们先考虑n=2的情况
设 a1<a2、b1<b2
那么这个时候
(a1−b1)2+(a2−b2)2=a21+a22+b21+b22−2a1b1−2a2b2;
(a1−b2)2+(a2−b1)2=a21+a22+b21+b22−2a1b2−2a2b1;
于是乎~~
(a1−b1)2+(a2−b2)2<(a1−b2)2+(a2−b1)2
-> 2a1(b2−b1)<2a2(b2−b1)
-> a1<a2
于是这是条件，于是n=2的情况得到了证明
于是n>2的情况先由无数个n=2的情况构成，显然成立
于是乎，我们回到原题
这下我们明白了最后两下标相同的火柴在自己那一列的相对高度应该是相同的【都同样是第几大、第几小等等】
于是这题就很轻松了，
为了解题方便我们可以将 ai 假设为第i大
而后映射到 b 数组就行了
于是乎我们绕来绕出终于明白了这题是求逆序对。。。
有两种方法，
1.线段树、树状数组单点更新，区间查询
2.归并排序求逆序对
最后别忘了mod99999997
这里给出线段树解法的代码：
#include<bits/stdc++.h>
using namespace std;
#define M 100005
const int P=;
void Rd(int &res){
char c;res=;
while(c=getchar(),!isdigit(c));
do res=(res<<)+(res<<)+(c^);
while(c=getchar(),isdigit(c));
}
int a[M],b[M],A[M],B[M],ID[M];
struct node{
int l,r,cnt;
}tree[M<<];
void build(int l,int r,int p){
tree[p].l=l;tree[p].r=r;
tree[p].cnt=;
if(l==r)return;
int mid=l+r>>;
build(l,mid,*p);build(mid+,r,*p+);
}
void up(int p){//Up
tree[p].cnt=tree[*p].cnt+tree[*p+].cnt;
}
int query(int l,int r,int p){
if(tree[p].l==l&&tree[p].r==r)return tree[p].cnt;
int mid=tree[p].l+tree[p].r>>;
if(r<=mid)return query(l,r,*p);
if(l>mid)return query(l,r,*p+);
return query(l,mid,*p)+query(mid+,r,*p+);
}
void update(int p,int c){
if(tree[p].l==tree[p].r){
tree[p].cnt=;
return;
}int mid=tree[p].l+tree[p].r>>;
if(c<=mid)update(*p,c);
else update(*p+,c);
up(p);
}
int main(){
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
Rd(a[i]);
A[i]=a[i];
}for(int i=;i<=n;i++){
Rd(b[i]);
B[i]=b[i];
}sort(A+,A+n+);sort(B+,B+n+);
for(int i=;i<=n;i++)a[i]=lower_bound(A+,A+n+,a[i])-A;
for(int i=;i<=n;i++)b[i]=lower_bound(B+,B+n+,b[i])-B;
for(int i=;i<=n;i++)ID[a[i]]=i;
for(int i=;i<=n;i++)b[i]=ID[b[i]];
int ans=;
build(,n,);//建树
for(int i=;i<=n;i++){
ans=(ans+query(b[i],n,))%P;//查询
update(,b[i]);//更新
}printf("%d\n",ans);
return ;
}
C题：
这题刚开始的时候一秒想到二分，
自信满满的敲出来
以为暴力60分到手了。。
结果仔细一看数据才发现，Y的30分都没有。。O（m2logm）
考试完以后老师讲了三种方法。。
发现有一种就是二分
把我的代码经过一个神奇的变化就能神奇的A掉了。。。
而后我又自信满满的去敲了最短路，
认为这下子30分应该有了，
60分并查集的写法认为有点小问题，没去敲。。。
（其实一切的一切只是因为博主是蒟蒻）
好了，我们来研究正解。。。
首先是第一种解法：
最大生成树+倍增
其实这个倍增改成树链剖分什么其他的，也是可以的
但是倍增这种已经烂大街的东西显然更好写
（这几年下来几乎每年NOIP的3题都能用倍增做）
反正，博主是敲倍增敲到手残了。。
其实有点智商的人都能发现最终的答案一定是在最大生成树上的【好吧，图不一定联通，所以可能是最大生成树林】
你问为什么？
这不是废话吗？
自己度娘一下最大生成树的定义（好吧，应该。或许、可能是搜不到的，去搜最小生成树吧。。）
因为树的性质五花八门，而图的性质我们却并不了解多少，
所以当我们迈出了这关键的一步将树转化为图的时候，一切就简单多了，
于是我们知道，在树上，如果在两点之间走一条欧拉路径（不走重边）的话，
只有一条路可走，
把起点和终点到达他们的LCA路径拼接起来就可以了
然而重边走了并无软用
于是乎我们只用用倍增预处理出每个点到他的祖先时经过的边的最小权值就行了
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define M 10005
#define N 50005
#define S 16
#define oo 2000000000
void Rd(int &res){
char c;res=;
while(c=getchar(),!isdigit(c));
do res=(res<<)+(res<<)+(c^);
while(c=getchar(),isdigit(c));
}
struct LI{
int a,b,c;
bool operator <(const LI &A)const{
return c>A.c;
}
}s[N];
struct node{
int to,v;
};
vector<node>edge[M];
int fa[M],tfa[S][M],dep[M],falen[S][M];
//fa是克鲁斯卡尔算法中用到的，其实并无实际意义,只是用来判断两个节点是否已经属于同一棵树
//tfa[x]代表x在树上的父亲节点
//dep[x]代表结点x在树上的深度
//falen[s][x]代表结点x向根节点走(1<<s)步中经过的边的最小权值
int n,m,k;
void init(){//刚开始每个点相互独立
for(int i=;i<=n;i++)
fa[i]=i;
}
int getfa(int x){
if(fa[x]==x)return x;
return fa[x]=getfa(fa[x]);//路径压缩
}
void Kruskral(){//求最小生成树，注意，由于这个图可能不是联通的，所以可能会求出一片森林
sort(s+,s+m+);//边权从大到小加边
init();
for(int i=;i<=m;i++){
int a=getfa(s[i].a),b=getfa(s[i].b);
if(a!=b){//不在同一棵树
fa[b]=a;
node tmp;
tmp.to=s[i].b;tmp.v=s[i].c;
edge[s[i].a].push_back(tmp);//你可以写链表，但是STL的vector多方便啊，虽然慢了点
tmp.to=s[i].a;
edge[s[i].b].push_back(tmp);
}
}
}
void dfs(int x,int pre,int d){//求结点x的深度，到x的父亲以及到父亲的距离
if(dep[x])return;
dep[x]=d;
for(int i=;i<edge[x].size();i++){
int y=edge[x][i].to;
if(y==pre)continue;
dfs(y,x,d+);
tfa[][y]=x;falen[][y]=edge[x][i].v;
}
}
int solve(int x,int y){
int res=oo;
if(dep[y]>dep[x])swap(x,y);
if(dep[x]>dep[y])//一直走到深度相同
for(int i=S-;i>=;i--)
if(dep[tfa[i][x]]>=dep[y]){
if(res>falen[i][x])res=falen[i][x];
x=tfa[i][x];
}
if(x!=y){//一直走到LCA，停下来
for(int i=S-;i>=;i--)
if(tfa[i][x]!=tfa[i][y]){//往上倍增跳，一旦跳过了LCA或是刚好在LCA上就不跳
if(res>falen[i][x])res=falen[i][x];
if(res>falen[i][y])res=falen[i][y];
x=tfa[i][x];y=tfa[i][y];
}
if(res>falen[][x])res=falen[][x];
if(res>falen[][y])res=falen[][y];
x=tfa[][x];y=tfa[][y];//最后正好差一步就能到达LCA
}return res;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=;i<=m;i++){Rd(s[i].a);Rd(s[i].b);Rd(s[i].c);}
Kruskral();
for(int i=;i<=n;i++)dfs(getfa(i),,);
for(int i=;i<S;i++)//倍增求出falen
for(int j=;j<=n;j++)
if(tfa[i-][j]&&tfa[i-][tfa[i-][j]]){
tfa[i][j]=tfa[i-][tfa[i-][j]];
falen[i][j]=min(falen[i-][j],falen[i-][tfa[i-][j]]);
}
scanf("%d",&k);
while(k--){
int x,y;
Rd(x);Rd(y);
if(getfa(x)!=getfa(y))puts("-1");
else printf("%d\n",solve(x,y));
}return ;
}
于是225分再度崩盘
好吧，还有两种解法没讲。。。
第二种，并查集+启发式合并，
然而吾并不会，
于是开始第三种
并查集+二分+二分+二分+二分 ………………
这个方法碉堡了
首先我们知道一个暴力的二分是这样的：
void solve(){
while(q--){//询问数量
int l=,r=m;//二分边，最终结果一定是边权
while(l<=r){
int mid=(l+r)/;
if(check(mid)){//check的复杂度为O（m）【加边，getfa判断】
res=mid;
l=mid+;
}else r=mid-;
}
}
}
复杂度为O( qm⋅logm )
然而这个神奇的方法硬生生的吧那个二分调到了外面
然后把里面的 qm 完美变成了 q+m
所以这是个复杂度为O（ (q+m)logm ）的代码
这个时候对于每个询问，mid的大小是不相同的
于是按照mid从小到大排序就可以O( m )加边
每条边判断一次总共是O（q）
这里提供部分代码：
void solve(){
sort(s+,s+m+);//将边按边权大小排序
memset(ans,-,sizeof(ans));
for(int w=;w<=;w++){
init();
sort(res+,res+k+);//res代表每个询问的l，r和mid
for(int i=,q=;i<=m&&q<=k;q++){
if(res[q].L>res[q].R)continue;
while(i<=res[q].mid){
int a=getfa(s[i].a),b=getfa(s[i].b);
if(a!=b){//加边
fa[b]=a;
}if(res[q].mid==i){//判断是否联通
int X=getfa(res[q].x),Y=getfa(res[q].y);
if(X==Y){
ans[res[q].id]=s[res[q].mid].c;
res[q].R=res[q].mid-;
}else res[q].L=res[q].mid+;
res[q].mid=res[q].L+res[q].R>>;
break;
}i++;
}
}
}
}
于是225分再次爆炸
![tarjan算法介绍与分析[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)