转圈游戏

题目

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 号小伙伴所在的位置编号。

样例

样例输入

10 3 4 5

样例输出

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

思路

1. 先通过草稿手动模拟，可以得到规律，最后的位置为（x+m*10^k)%n
2. 很明显，算m*10^k需要用到快速幂
3. 数据范围：为了防止爆long long要不断%n

代码

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
long long n;
long long pow(int root, int time) {
    int  ans=1;
    while(time) {
        if(time & 1) ans=(root*ans)%n;
        root=(root*root)%n;
        time>>=1;
    }
    return ans%n;
}
int main() {
    long long m,k,x;
    long long t,r;
    cin>>n>>m>>k>>x;
    r=0;
    t=pow(10,k);
    t*=m;
    t%=n;
    r=(x+t)%n;
    cout<<r<<endl;
    return 0;
}

火柴排队

题目

涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为： ∑(ai-bi)^2
其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

输入输出

输入：
输入文件为 match.in。
共三行，第一行包含一个整数 n，表示每盒中火柴的数目。
第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

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

思路

1. 先来证明一个公式：
   若a1>a2且b1>b2，则有(a1-b1)^2 +(a2-b2)^2 < (a2-b1)^2 + (a1-b2)^2
   当然这个公式很容易证，拆开就好了
2. 然后运用这个公式，发现为保证火柴距离最小，两列火柴对应的两根火柴在各列中高度的排名应该相同
3. 再来定义一个r数组，使得r[a[i].num]=b[i].num,则可以很惊奇地发现，交换次数即为r数组中逆序对的个数，此题得解

现在考虑求逆序对

用归并排序求：
实际上归并排序的交换次数就是这个数组的逆序对个数，为什么呢？

1. 归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序，然后再将这两半合并起来。
2. 在合并的过程中（设l<=i<=mid，mid+1<=j<=h），当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时，在
3. 前半部分中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。因此，可以在归并排序中的合并过程中计算逆序数.

用树状数组求：

1. 每输入一个b[i],就用a[b[i]+1]++去标记总共输入多少次了（因为输入的数据是0~n-1，所以输入的b[i]就相当于a[i]的下标i，而且有0，树状数组无法对下标为0进行操作，所以要a[b[i]+1]）;
2. 对于一个b[i],要想查询它前面有多少大于它的，只需将a[b[i]+1]到a[n]加起来，也就是求一段数组的和，那么树状数组就上场加速了

代码

归并排序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct n{
    int num,ord;
}node;
node first_team[100010],second_team[100010];
int a[100010],b[100010],ans;
int compare(node x,node y)
{
    return x.num<y.num;
}
void Merge(int l,int r)
{
    if(l>=r) return ;
    int mid=(l+r)/2;
    Merge(l,mid);
    Merge(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
    {
        if(a[i]>a[j])
        {
            b[k++]=a[j++];
            ans+=mid-i+1;
            ans%=99999997;
        }
        else b[k++]=a[i++];
    }
    while(i<=mid) b[k++]=a[i++];
    while(j<=r) b[k++]=a[j++];
    for(int i=l;i<=r;i++)
        a[i]=b[i];
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&first_team[i].num);
        first_team[i].ord=i;
    }
    for(int i=1;i<=n;i++)`
    {
        scanf("%d",&second_team[i].num);
        second_team[i].ord=i;
    }
    sort(first_team+1,first_team+n+1,compare);
    sort(second_team+1,second_team+n+1,compare);
    for(int i=1;i<=n;i++)
        a[first_team[i].ord]=second_team[i].ord;
    Merge(1,n);
    printf("%d",ans);
    return 0;
}

树状数组

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 100010;
const int maxm = 99999997;
struct MyStruct
{
    int data;
    int loc;
}a[maxn],b[maxn];
int e[maxn], n, c[maxn];
int inline readint()
{
    int x = 0;
    char c = getchar();
    while (c<'0' || c>'9') c = getchar();
    while (c >= '0'&&c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}
int lowbit(int x)
{
    return x&-x;//树状数组实现 
}
void add(int x,int t)
{
    while (x <= n)
    {
        e[x] += t;
        e[x] %= maxm;
        x += lowbit(x);//每次往后加，可以改变后面对应的和 
    }
}
int sum(int x)
{
    int s = 0;
    while(x)
    {
        s += e[x];
        s %= maxm;
        x -= lowbit(x);//得到所求的和 
    }
    return s;
}
bool cmp(MyStruct x, MyStruct y)
{
    return x.data < y.data;
}
int main()
{
    n = readint();
    for (int i = 1; i <= n; i++)
    {
        a[i].data = readint();
        a[i].loc = i;//记录位置 
    }
    for (int i = 1; i <= n; i++)
    {
        b[i].data = readint();
        b[i].loc = i;
    }
    sort(a + 1, a + n + 1, cmp);
    sort(b + 1, b + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        c[a[i].loc] = b[i].loc;//离散优化 
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        add(c[i], 1);//离散优化后大小就是正确顺序的位置 
        ans += i - sum(c[i]);//当前位置，减去之前比他大的数的个数  
        ans %= maxm;
    }
    printf("%d", ans);
    return 0;
}

积木大赛

题目

春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦，大厦可以看成由n块宽度为1的积木组成，第i块积木的最终高度需要是hi。

在搭建开始之前，没有任何积木（可以看成n块高度为 0 的积木）。接下来每次操作，小朋友们可以选择一段连续区间[l, r]，然后将第第 L 块到第 R 块之间（含第 L 块和第 R 块）所有积木的高度分别增加1。

小 M 是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。

输入输出格式

输入格式：
输入文件为 block.in
输入包含两行，第一行包含一个整数n，表示大厦的宽度。
第二行包含n个整数，第i个整数为hi 。

输出格式：
输出文件为 block.out
仅一行，即建造所需的最少操作数。

输入输出样例

样例输入

5
2 3 4 1 2

样例输出

5

思路

其实就是简单的贪心，观察样例；

a[1]=2 所以位置1一定被操作了两次 ans+=2
a[2]-a[1]=1 位置2比位置1多操作一次 ans+=1
但a[i]<a[i-1]时，跳过。因为对于a[i]<a[i-1]的情况，a[i]和a[i-1]一定不在一次操作内
以此类推，就得到最后的答案

代码

/*很简短*/
#include<iostream>
#include<cstdio>
#define MAXX 100000+5
using namespace std;
int a[MAXX],n;
long long ans=0;
int main() {
    scanf("%d",&n);
    for (int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
        if (a[i]>a[i-1]) ans+=a[i]-a[i-1];
    }
    printf("%lld",ans);
    return 0;
}

货车运输

题目描述

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。

输入输出样例

输入样例：

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

输出样例#1：

3
-1
3

说明

数据范围
对于 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。

思路

• 求一条路径的最小边的最大值，符合该条件的路径一定在最大生成树上
• 在最大生成树上跑LCA倍增。即求起点到LCA上最小边和终点到LCA上最小边的最小值

代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
const int inf = 100001;
const int maxn = 10010;
const int maxm = 50050;
int n, m, q, tot;
int st[maxn], vis[maxn], deep[maxn], fa[maxn][17], g[maxn][17], f[maxn];

struct node{
    int v, w, next;
} edge[maxm];

struct node1{
    int u, v, w;
} a[maxm];

bool cmp(node1 x, node1 y){
    return x.w > y.w;
}

void in(int x, int y, int z){
    edge[++tot].v = y;
    edge[tot].w = z;
    edge[tot].next = st[x];
    st[x] = tot;
}

void init(){
    for(int i = 1; i <= n; i++) f[i] = i;
    memset(fa, 0, sizeof(fa));
    memset(g, 0, sizeof(g));
}

int find(int x){
    if(f[x] == x)   return x;
    return f[x] = find(f[x]);
}

void kruskal(){
    init();
    for(int i = 1, from, to, ff, ft; i <= m; i++){
        from = a[i].u, to = a[i].v;
        ff = find(from), ft = find(to);
        if(ff != ft){
            f[ff] = ft;
            in(from, to, a[i].w);
            in(to, from, a[i].w);
        }
    }
}

void dfs(int rt){//建树
    vis[rt] = 1;
    for(int i = 1; i <= 16; i++){
        if(deep[rt] < (1<<i))   break;
        fa[rt][i] = fa[fa[rt][i-1]][i-1];
        g[rt][i] = min(g[rt][i-1], g[fa[rt][i-1]][i-1]);
    }
    for(int i = st[rt]; i; i = edge[i].next){
        int to = edge[i].v;
        if(vis[to]) continue;
        fa[to][0] = rt;
        g[to][0] = edge[i].w;
        deep[to] = deep[rt] + 1;
        dfs(to);
    }
}

int lca(int x, int y){//倍增往上跳，返回最近公共祖先 
    if(deep[x] < deep[y])   swap(x, y);
    int delta = deep[x] - deep[y];
    for(int i = 0; i <= 16; i++)//2^16正好过50000 
        if(delta & (1<<i))  x = fa[x][i];
    for(int i = 16; i >= 0; i--)
        if(fa[x][i] != fa[y][i]){
            x = fa[x][i];
            y = fa[y][i];
        }
    if(x == y)  return x;
    else return fa[x][0];
}

int ask(int x, int y){//询问路上满足条件的边 
    int mn = inf;
    int delta = deep[x] - deep[y];
    for(int i = 0; i <= 16; i++)
        if(delta & (1<<i)){
            mn = min(mn, g[x][i]);
            x = fa[x][i];
        }
    return mn;
}

int main(){
    cin >> n >> m;
    for(int i = 1, x, y, z; i <= m; i++)
        cin >> a[i].u >> a[i].v >> a[i].w;
    sort(a+1, a+m+1, cmp);
    kruskal();
    for(int i = 1; i <= n; i++)
        if(!vis[i]) dfs(i);
    cin >> q;
    while(q--){
        int op, ed;
        cin >> op >> ed;
        if(find(op) != find(ed)){
            cout << "-1" << endl;
            continue;
        }
        else{
            int baba = lca(op, ed);
            cout << min(ask(op, baba), ask(ed, baba)) << endl;
        }
    }
    return 0;
}

花匠

题目

花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。
具体而言，栋栋的花的高度可以看成一列整数h1,h2..hn。设当一部分花被移走后，剩下的花的高度依次为g1,g2..gn，则栋栋希望下面两个条件中至少有一个满足：
条件 A：对于所有g(2i)>g(2i-1),g(2i)>g(2i+1)
条件 B：对于所有g(2i)<g(2i-1),g(2i)<g(2i+1)
注意上面两个条件在m = 1时同时满足，当m > 1时最多有一个能满足。
请问，栋栋最多能将多少株花留在原地。

输入输出格式

输入格式：
输入文件为 flower .in。
输入的第一行包含一个整数n，表示开始时花的株数。
第二行包含n个整数，依次为h1,h2..hn,表示每株花的高度。。
输出格式：
输出文件为 flower .out。
输出一行，包含一个整数m，表示最多能留在原地的花的株数。

输入输出样例

样例输入

5
5 3 2 1 2

样例输出

3

说明

样例解释
有多种方法可以正好保留 3 株花，例如，留下第 1、4、5 株，高度分别为 5、1、2，满足条件 B。
数据范围
对于 20%的数据，n ≤ 10；
对于 30%的数据，n ≤ 25；
对于 70%的数据，n ≤ 1000，0 ≤ ℎi≤ 1000；
对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤ hi≤ 1,000,000，所有的hi 随机生成，所有随机数服从某区间内的均匀分布。

思路

意思就是让你找转折点的数量即g(i-1)<gi>g(i+1)或g(i-1)>gi<g(i+1)，gi即是转折点。首先可以肯定的是，当花的数目为1的时候，可以直接输出1。首尾两株花都肯定是可以留下的，因此，当花的数目大于等于2时，我们可以将答案初始化为2，然后加上转折点的数目即可

代码

#include<iostream>
#include<cstdio>
using namespace std;
int a[100005];
int w,n,ans;
int main(){
    scanf("%d",&n);
    a[0]=-147258963;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[++w]);
        if(a[w]==a[w-1]) --w;
    } 
    if(w==1) {
        printf("1");
        return 0; 
    }
    ans=2;
    for(int i=2;i<=w-1;i++){
        if (((a[i]>a[i-1])&&(a[i]>a[i+1]))||((a[i]<a[i-1])&&(a[i]<a[i+1]))){
            ans++;
        }
    }
    printf("%d",ans);
    return 0;
}