期望得分：100+100+100=300

实际得分：100+10+0=110

T2 思路有漏洞

T3 求到lca的什么什么值，指跳了一个点，没管另一个，丢100

T1 转圈游戏

题目描述

n 个小伙伴（编号从 0 到 n-1）围坐一圈玩游戏。按照顺时针方向给 n 个位置编号，从0 到 n-1。最初，第 0 号小伙伴在第 0 号位置，第 1 号小伙伴在第 1 号位置，……，依此类推。游戏规则如下：每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置，第 1 号位置小伙伴走到第 m+1 号位置，……，依此类推，第n − m号位置上的小伙伴走到第 0 号位置，第n-m+1 号位置上的小伙伴走到第 1 号位置，……，第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。

现在，一共进行了 10^k轮，请问 x 号小伙伴最后走到了第几号位置。

输入输出格式

输入格式：

 

输入文件名为 circle.in。

输入共 1 行，包含 4 个整数 n、m、k、x，每两个整数之间用一个空格隔开。

 

输出格式：

 

输出文件名为 circle.out。

输出共 1 行，包含 1 个整数，表示 10

k 轮后 x 号小伙伴所在的位置编号。

 

输入输出样例

输入样例#1：

10 3 4 5

输出样例#1：

5

说明

对于 30%的数据，0 < k < 7；

对于 80%的数据，0 < k < 10^7；

对于 100%的数据，1 <n < 1,000,000，0 < m < n，1 ≤ x ≤ n，0 < k < 10^9

每次移动m个位置，共移动10^k次，

用快速幂算出移动的总步数，加上x再%n

#include
      
       #include
       
        using namespace std;int n,m,k,x;long long tmp=1;void mul(long long a,long long b){    for(;b;b>>=1,a=a*a%n)      if(b&1) tmp=tmp*a%n;    tmp=m*tmp%n;}int main(){    scanf("%d%d%d%d",&n,&m,&k,&x);    mul(10,k);    printf("%d",(x+tmp)%n);}
       
      

 

T2 火柴排队

题目描述

涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为： ∑(ai-bi)^2

其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

输入输出格式

输入格式：

 

输入文件为 match.in。

共三行，第一行包含一个整数 n，表示每盒中火柴的数目。

第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

 

输出格式：

 

输出文件为 match.out。

输出共一行，包含一个整数，表示最少交换次数对 99,999,997 取模的结果。

 

输入输出样例

输入样例#1：

【输入输出样例 1】42 3 1 43 2 1 4【输入输出样例 2】41 3 4 21 7 2 4

输出样例#1：

【输入输出样例 1】1【输入输出样例 2】2

说明

【输入输出样例说明1】

最小距离是 0，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。

【输入输出样例说明2】

最小距离是 10，最少需要交换 2 次，比如：交换第 1 列的中间 2 根火柴的位置，再交换第 2 列中后 2 根火柴的位置。

【数据范围】

对于 10%的数据， 1 ≤ n ≤ 10；

对于 30%的数据，1 ≤ n ≤ 100；

对于 60%的数据，1 ≤ n ≤ 1,000；

对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤火柴高度≤ maxlongint

 ∑(ai-bi)^2=Σ ai² + Σ bi² - 2 Σ ai * bi

ai² ，b²是固定的

所以要最大化 ai * bi

下意识觉得 将a、b排序后对应顺序相乘的结果最大，正确

证明如下： 

由排序不等式：

设有两组数 a1 , a2 ,…… an; b1 , b2 ,…… bn 满足 a1 ≤ a2 ≤……≤ an, b1 ≤ b2 ≤……≤ bn ，

其中c1,c2,……,cn是b1,b2,……，bn的任一排列，则有 　　

   a1* bn + a2 *b{n-1}+ ... + an *b1 　　

≤ a1 *c1 + a2* c2 +……+ an *cn 　　

≤ a1 *b1 + a2 *b2 + ……+an* bn.

即 逆序和<=乱序和<=顺序和

所以最大化ai * bi，就要顺序相乘

所以问题就转化为

在b数组中，交换最少的次数，

使得 若a[i]在a数组中排名为j，b[i]也在b数组中排名为j

设一个数组s，s[i]=j表示 b原序列中第i个元素，应该在位置j

然后问题转化为了求s[]的逆序对个数

AC代码：

#include
      
       #include
       
        #define N 100001#define mod 99999997using namespace std;int n,ans,tmp[N],s[N];struct node{    int w,id;}a[N],b[N]; bool cmp(node p,node q){    return p.w
        
         >1;    solve(l,mid);    solve(mid+1,r);    int i=l,j=mid+1,k=l;    while(i<=mid&&j<=r)    {        if(s[i]<=s[j]) tmp[k++]=s[i++];        else         {            ans=(ans+mid-i+1)%mod;            tmp[k++]=s[j++];        }    }    while(i<=mid) tmp[k++]=s[i++];    while(j<=r) tmp[k++]=s[j++];    for(int i=l;i<=r;i++) s[i]=tmp[i];}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d",&a[i].w),a[i].id=i;    for(int i=1;i<=n;i++) scanf("%d",&b[i].w),b[i].id=i;    sort(a+1,a+n+1,cmp);    sort(b+1,b+n+1,cmp);    for(int i=1;i<=n;i++) s[b[i].id]=a[i].id;    solve(1,n);    printf("%d",ans);}
        
       
      

自己做的错误思路:

将a数组从大到小排序，对应的b随之排序，求b中 i>j,b[i]<b[j]的个数

错误1：

逆序对定义：i<j，a[i]>a[j]，归并排序求逆序对模版是按i<j来的

错误2：

重排a数组，b数组随之排，这样归并排序完后得到b的循序序列

但改变了a数组，即改变了原序列

WA 10分代码：

#include
      
       #include
       
        #define N 100001#define mod 99999997using namespace std;int n,ans,tmp[N],s[N];struct node{    int a,b;}e[N];bool cmp(node p,node q){    return p.a
        
         >1;    solve(l,mid);    solve(mid+1,r);    int i=l,j=mid+1,k=l;    while(i<=mid&&j<=r)    {        if(s[i]<=s[j]) tmp[k++]=s[i++];        else         {            ans=(ans+mid-i+1)%mod;            tmp[k++]=s[j++];        }    }    while(i<=mid) tmp[k++]=s[i++];    while(j<=r) tmp[k++]=s[j++];    for(int i=l;i<=r;i++) s[i]=tmp[i];}int main(){    /*freopen("data","r",stdin);    freopen("my.out","w",stdout);*/    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d",&e[i].a);    for(int i=1;i<=n;i++) scanf("%d",&e[i].b);    sort(e+1,e+n+1,cmp);    for(int i=1;i<=n;i++) s[i]=e[i].b;    solve(1,n);    printf("%d",ans);}
        
       
      

T3 货车运输

题目描述

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入输出格式

输入格式：

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道

路。 接下来 m 行每行 3 个整数 x、 y、 z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意： x 不等于 y，两座城市之间可能有多条道路 。

接下来一行有一个整数 q，表示有 q 辆货车需要运货。

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。

 

输出格式：

输出文件名为 truck.out。

输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货

车不能到达目的地，输出-1。

 

输入输出样例

输入样例#1：

4 31 2 42 3 33 1 131 31 41 3

输出样例#1：

3-13

说明

对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q< 1,000；

对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q< 1,000；

对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q< 30,000，0 ≤ z ≤ 100,000。

题意：若点x、y连通，求x、y路径上限重的最小值；若不连通，输出-1

注：数据有重边、有环

重边肯定保留限重最大的那一条，所选的道路限重越大越好

所以 是最大生成树

在最大生成树上倍增，同时维护倍增区域的最小值

答案就是两点到其lca路径上，所有倍增区域的最小值

#include

考试时的错误：

1、跳了x没跳y

2、跳y之前没有判断y是否就是lca