题目大意

给定一个数$num$，求去掉$k$位后的最小值。

解题思路

分情况讨论各种删数的情况

一、数列单调不递减

例如：

122345
3

根据数据我们可以画出图形：

我们每删掉一个数，后面的数就会向前移动一格。
那很明显，我们这个数据的最优答案应该是$122$（将$3,4,5$删去）
* 那为什么要删$3,4,5$呢？

假设我们在第次删除时不删去$3$，而删去$2$
那我们的数字就会变成$123$
就会比我们的最优答案少1
其实这个例子不是很好，但是应该挺好看懂的

所以当数字单调不递减时，我们删去末尾的$k$位数字。

二、数组没有规律（一般情况）

例如：
（其实用样例也是可以的，就是画图麻烦了点）

143221
3

根据数据画出的图形:

那这种情况怎么考虑呢？

• 首先假设现在已经输入了$1$和$4$，那么这两个数单调递增，所以我们可以先不用处理
• 接下来读入$3$，那么$1,4,3$并不是单调递增的数列了，那么我们现在应该删去哪一个数呢？，如图

很明显13开头的数字小于14开头的数字，所以删去4是优秀的

可以发现这种操作类似单调栈操作，所以……

参考代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,k;
string num,res;
// num为输入数字，res为答案（这里将res用作单调栈保存答案）
int main(){
    cin>>num>>k; // 读入
    res = "0"; // 设为0，使res从下表1开始记录答案
    for(auto c : num){ // 遍历num
        while(k && c < res.back()){ // 如果找到更优数字
            res.pop_back(); // 删除
            k --; // 已删去一个数
        }
        res += c; // 将当前数字压入单调栈
    }
    while(k --) res.pop_back(); // 如果还没有把数字删去k位，继续删除末尾的数字
    int i = 0;
    while(i + 1 < res.size() && res[i] == '0') i ++; // 记录前导0数量
    cout<<res.substr(i)<<endl; // 输出
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 110;
const double eps = 1e-6;
int n;
double a[N][N];
int gauss(){
    int c = 1,r = 1;
    for(;c <= n;c ++){
        int t = r;
        for(int i = r;i <= n;i ++){
            if(fabs(a[t][c]) < fabs(a[i][c])) t = i;
        }
        if(fabs(a[t][c]) < eps) continue;
        for(int i = c;i <= n + 1;i ++) swap(a[t][i],a[r][i]);
        for(int i = n + 1;i >= c;i --) a[r][i] /= a[r][c];
        for(int i = r + 1;i <= n;i ++){
            if(fabs(a[i][c]) > eps){
                for(int j = n + 1;j >= c;j --){
                    a[i][j] -= a[r][j] * a[i][c];
                }
            }
        }
        r ++;
    }
    if(r <= n){
        for(int i = r;i <= n;i ++){
            if(fabs(a[i][n + 1]) > eps) return 2;
        }
        return 1;
    }
    for(int i = n;i >= 1;i --){
        for(int j = i + 1;j <= n;j ++){
            a[i][n + 1] -= a[j][n + 1] * a[i][j];
        }
    }
    return 0;
}
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= n + 1;j ++){
            scanf("%lf",&a[i][j]);
        }
    }
    int t = gauss();
    if(t == 0){
        for(int i = 1;i <= n;i ++) printf("%.2lf\n",a[i][n + 1] + eps - eps);
    }
    else if (t == 1) puts("Infinite group solutions");
    else puts("No solution");
    return 0;
}

题目描述

给定 $2n$ 个整数 $a_1,a_2,…,a_n$ 和 $m_1,m_2,…,m_n$，求一个最小的非负整数 $x$，满足 $∀i∈[1,n],x≡m_i(mod a_i)$。

输入格式

第 $1$ 行包含整数 $n$。

第 $2…n+1$ 行：每 $i+1$ 行包含两个整数 $a_i$ 和 $m_i$，数之间用空格隔开。

输出格式

输出最小非负整数 $x$，如果 $x$ 不存在，则输出 −1。
如果存在 $x$，则数据保证 $x$ 一定在 $64$ 位整数范围内。

数据范围

$1≤a_i≤2^{31}−1$,
$0≤m_i<a_i$
$1≤n≤25$

输入样例：

2
8 7
11 9

输出样例：

31

算法1

(中国剩余定理) $O(n^2)$

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int n;
long long exgcd(long long a,long long b,long long &x,long long &y){ // 扩展欧几里得算法
    if(!b){ // b为0时
        x = 1;
        y = 0;
        return a;
    }
    long long d = exgcd(b,a % b,y,x);
    y -= (a / b) * x;
    return d;
}
int main(){
    scanf("%d",&n); // 输入
    long long a1,m1;
    scanf("%d%d",&a1,&m1); // 先读入第一个式子，方便合并
    n --; // 少了一个式子
    while(n --){ // 读入剩下的式子
        long long a2,m2;
        scanf("%d%d",&a2,&m2);
        long long k1,k2; // 按照前面说过的方法合并
        long long d = exgcd(a1,a2,k1,k2);
        if((m2 - m1) % d){
            puts("-1");
            return 0;
        }
        k1 *= (m2 - m1) / d;
        long long t = abs(a2 / d);
        k1 = (k1 % t + t) % t;
        m1 = k1 * a1 + m1;
        a1 = abs(a1 * t);
    }
    printf("%lld\n",m1);
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int n;
long long exgcd(long long a,long long b,long long &x,long long &y){
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    long long d = exgcd(b,a % b,y,x);
    y -= (a / b) * x;
    return d;
}
int main(){
    scanf("%d",&n);
    long long a1,m1;
    scanf("%d%d",&a1,&m1);
    n --;
    while(n --){
        long long a2,m2;
        scanf("%d%d",&a2,&m2);
        long long k1,k2;
        long long d = exgcd(a1,a2,k1,k2);
        if((m2 - m1) % d){
            puts("-1");
            return 0;
        }
        k1 *= (m2 - m1) / d;
        long long t = abs(a2 / d);
        k1 = (k1 % t + t) % t;
        m1 = k1 * a1 + m1;
        a1 = abs(a1 * t);
    }
    printf("%lld\n",m1);
    return 0;
}

题目描述

给定 $n$ 组数据 $a_i$,$b_i$,$m_i$，对于每组数求出一个 $x_i$，使其满足 $a_i×x_i≡b_i(\mod m_i)$，如果无解则输出 impossible。

输入格式

第一行包含整数 $n$。

接下来 $n$ 行，每行包含一组数据 $a_i$,$b_i$,$m_i$。

输出格式

输出共 $n$ 行，每组数据输出一个整数表示一个满足条件的 $x_i$，如果无解则输出 impossible。

每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。

输出答案必须在 $int$ 范围之内。

数据范围

$1≤n≤10^5$,
$1≤a_i,b_i,m_i≤2×10^9$

输入样例：

2
2 3 6
4 3 5

输出样例：

impossible
-3

算法1

(扩展欧几里得算法) $O(n^2)$

推导：

时间复杂度

参考文献

C++ 代码

#include <iostream>
using namespace std;
int n;
int exgcd(int a,int b,int &x,int &y){ // 扩展欧几里得算法
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b,a % b,y,x);
    y -= (a / b) * x;
    return d;
}
int main(){
    scanf("%d",&n);
    while(n --){
        int a,b,m;
        scanf("%d%d%d",&a,&b,&m); // 读入三个数
        int x,y;
        int d = exgcd(a,m,x,y);
        if(b % d) puts("impossible");
        else printf("%d\n",(long long) x * (b / d) % m); // 这里输出的答案解析见解析①
    }
    return 0;
}

解析①

#include <iostream>
using namespace std;
int n;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b,a % b,y,x);
    y -= (a / b) * x;
    return d;
}
int main(){
    scanf("%d",&n);
    while(n --){
        int a,b,m;
        scanf("%d%d%d",&a,&b,&m);
        int x,y;
        int d = exgcd(a,m,x,y);
        if(b % d) puts("impossible");
        else printf("%d\n",(long long) x * (b / d) % m);
    }
    return 0;
}

题目描述

给定 $n$ 对正整数 $a_i$,$b_i$，对于每对数，求出一组 $x_i$,$y_i$，使其满足 $a_i×x_i+b_i×y_i=gcd(a_i,b_i)$。

输入格式

第一行包含整数 $n$。

接下来 $n$ 行，每行包含两个整数 $a_i$,$b_i$。

输出格式

输出共 $n$ 行，对于每组 $a_i$,$b_i$，求出一组满足条件的 $x_i$,$y_i$，每组结果占一行。

本题答案不唯一，输出任意满足条件的 $x_i$,$y_i$ 均可。

数据范围

$1≤n≤10^5$,
$1≤a_i,b_i≤2×10^9$

输入样例：

2
4 6
8 18

输出样例：

-1 1
-2 1

算法1

(扩展欧几里得算法) $O(\log n)$

欧几里得算法

时间复杂度

参考文献

C++ 代码

#include <iostream>
using namespace std;
int n;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b,a % b,y,x);
    y -= (a / b) * x;
    return d;
}
int main(){
    scanf("%d",&n);
    while(n --){
        int a,b,x,y;
        scanf("%d%d",&a,&b);
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}

#include <iostream>
using namespace std;
int n;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b,a % b,y,x);
    y -= (a / b) * x;
    return d;
}
int main(){
    scanf("%d",&n);
    while(n --){
        int a,b,x,y;
        scanf("%d%d",&a,&b);
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}

题目描述

题目描述

小蓝最近正在玩一款 $RPG$ 游戏。

他的角色一共有 $N$ 个可以加攻击力的技能。

其中第 $i$ 个技能首次升级可以提升 $A_i$ 点攻击力，以后每次升级增加的点数都会减少 $B_i$。

$\left\lceil\frac{A_{i}}{B_{i}}\right\rceil$（上取整）次之后，再升级该技能将会改变攻击力。

现在小蓝可以总计升级 $M$ 次技能，他可以任意选择升级的技能和次数。

请你计算小蓝最多可以提高多少点攻击力？

输入格式

输入第一行包含两个整数 $N$ 和 $M$。

以下 $N$ 行每行包含两个整数 $A_i$ 和 $B_i$ 。

算法1

(暴力枚举) $O(n^2)$

首先我们可以发现每个技能提升的攻击力可以合起来变为一个等差数列

那如果要求最多能提升的攻击力
那么我们可以选前$m$个数（按从大到小排序）
那为什么前$m$个数是正确的，且不会取到没有升级过但却升级更多次的方式呢
那肯定是不会的
如果一种升级方式的第$n$次升级已经被选（$n>1$且$n$为正整数）
那么它前面升级过的一定会被选
因为这个技能升级的攻击力是一个等差数列
是下降的
所以在这个技能升级时，它的第一个技能一定已经被选过了

时间复杂度

然后这个暴力肯定是不能过的啊
就是写个思路，后面来做优化

参考文献

C++ 代码

暴力的代码以后有空再写吧

思路说一下

大概就是建一个堆
然后读一个往堆里放一个
然后最后选出前$m$个求和就可以了

也可以读入后再排序，最后求和

算法2

(贪心+多路归并+二分) $O(n^2)$

那现在来考虑优化
因为是要选前$m$个数，所以考虑二分
那我们假设选到的第$m$个数为$x$，那么可以得出
大于等于$x$的数的个数，要$≥m$个
大于等于$x + 1$的数的个数，要$<m$个

那就可以发现这里的数组是具有两段性的，所以可以用二分

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int a[N],b[N];
bool check(int mid){ // 二分判断条件
    long long res = 0;
    for(int i = 1;i <= n;i ++){
        if(a[i] >= mid) res += (a[i] - mid) / b[i] + 1;
    }
    return res >= m;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++) scanf("%d%d",&a[i],&b[i]);
    int l = 0,r = 1e6;
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    long long res = 0,cnt = 0;
    for(int i = 1;i <= n;i ++){
        if(a[i] >= r){
            int c = (a[i] - r) / b[i] + 1;
            int end = a[i] - (c - 1) * b[i];
            cnt += c;
            res += (long long)(a[i] + end) * c / 2;
        }
    }
    printf("%lld",res - (cnt - m) * r);
    return 0;
}

题目描述

农夫约翰计划建造 $N$ 个农场，用 $N−1$ 条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。

每个农场有一头奶牛，品种为更赛牛或荷斯坦牛之一。

约翰的 $M$ 个朋友经常前来拜访他。

在朋友 $i$ 拜访之时，约翰会与他的朋友沿着从农场 $A_i$ 到农场 $B_i$ 之间的唯一路径行走（可能有 $A_i=B_i$）。

除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。

由于约翰的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。

他的有些朋友只喝更赛牛的牛奶，其余的只喝荷斯坦牛的牛奶。

任何约翰的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。

请求出每个朋友在拜访过后是否会高兴。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$。

第二行包含一个长为 $N$ 的字符串。如果第 $i$ 个农场中的奶牛是更赛牛，则字符串中第 $i$ 个字符为 ‘G’，如果第 i 个农场中的奶牛是荷斯坦牛则为 ‘H’。

以下 $N−1$ 行，每行包含两个不同的整数 $X$ 和 $Y$，表示农场 $X$ 与 $Y$ 之间有一条道路。

以下 $M$ 行，每行包含整数 $A_i$,$B_i$，以及一个字符 $C_i$。$A_i$ 和 $B_i$ 表示朋友 $i$ 拜访时行走的路径的端点，$C_i$ 是 G 或 H 之一，表示第 $i$ 个朋友喜欢更赛牛的牛奶或是荷斯坦牛的牛奶。

输出格式

输出一个长为 $M$ 的二进制字符串。如果第 $i$ 个朋友会感到高兴，则字符串的第 $i$ 个字符为 1，否则为 0。

数据范围

$1≤N,M≤10^5$,
$1≤X,Y≤N$

输入样例：

5 5
HHGHG
1 2
2 3
2 4
1 5
1 4 H
1 4 G
1 3 G
1 3 H
5 5 H

输出样例：

10110

样例解释

在这里，从农场 $1$ 到农场 $4$ 的路径包括农场 $1、2$ 和 $4$。所有这些农场里都是荷斯坦牛，所以第一个朋友会感到满意，而第二个朋友不会。

算法1

($LCA$) $O(n log n)$

一、样例

根据样例可以画出题目中的树。

二、与$LCA$的关系

（1） 判断朋友是否满意的条件

题目中说每个朋友需要在访问时喝到自己偏好的牛奶才会满意
那很明显，就是从题目中的$A_i$点到$B_i$点的路径中需要有第$i$个朋友所偏好的牛奶

（2） 路径

找到了题目中朋友满意的条件
那我们现在就应该思考一下路径是怎么走的
我们找到题目中说的

在朋友 $i$ 拜访之时，约翰会与他的朋友沿着从农场 $A_i$ 到农场 $B_i$ 之间的唯一路径行走（可能有 $A_i=B_i$）。

所以排除最短路等算法

那唯一的路径怎么求出来呢

我们可以发现

这个唯一的路径其实就是从$A_i$开始，到$A_i$和$B_i$的最近公共祖先（$LCA$）为中转点，最后到达$B_i$的路径。

三、如何求出路径中是否有朋友偏好的牛奶

根据上面我们推导出来的路径的表示方法，那我们可以发现
这个路径中的点我们在做$LCA$时都会遍历到
所以，我们可以边做$LCA$边判断是否有朋友所偏好的牛奶

实现方法$1$

我们可以开一个$st[N][K][3]$的数组

用法：

• 设$j$为一个点
• 设$k$为要往上走$2^k$步

那么

$st[j][k][1]$ 表示从$j$往上走$2^k$步中所有的点是否含有$G$种牛奶
$st[j][k][2]$ 表示从$j$往上走$2^k$步中所有的点是否含有$H$种牛奶

到做$LCA$的时候就可以用这个判断是否有朋友所偏好的牛奶了

实现方法$2$

这个方法其实是比上面的方法$1$省一点空间的
我们可以把原来二维的$fa$数组改成三维

用法：

• 设$j$为一个点
• 设$k$为要往上走$2^k$步
• 设$i$为$fa$数组第三维

那么

$fa[j][k][0]$ 表示原本二维的$fa$数组表示的数
$fa[j][k][1]$ 表示从$j$往上走$2^k$步中所有的点是否含有$G$种牛奶
$fa[j][k][2]$ 表示从$j$往上走$2^k$步中所有的点是否含有$H$种牛奶

时间复杂度

倍增算法版的$LCA$算法是$O(n log n)$的
而且也没做多余的需要时间的处理
所以这道题的时间复杂度就为$O(n log n)$

参考文献

然后这里的代码用的是上面说的实现方法$2$

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10,M = 2 * N,K = 19; // N为点数，M为边数，K为最多要跳2^K步
int n,m;
int depth[N],fa[N][K][3]; // depth 表示深度；fa上面有讲解
int h[N],e[M],ne[M],idx; // 邻接表存图
char type[N]; // 牛奶的种类
int q[N]; // 队列
void add(int a,int b){ // 邻接表加边函数
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
void bfs(int root){ // bfs预处理深度和fa
    memset(depth,0x3f,sizeof depth);
    depth[0] = 0;
    depth[root] = 1;
    fa[root][0][0] = 0;
    int hh = 0,tt = 0;
    q[0] = root; // 以上和LCA模板几乎一样，不解释
    while(hh <= tt){
        int t = q[hh ++];
        for(int i = h[t];~i;i = ne[i]){
            int j = e[i];
            if(depth[j] > depth[t] + 1){
                depth[j] = depth[t] + 1;
                q[++ tt] = j;
                fa[j][0][0] = t;
                if(type[t] == 'G') fa[j][0][1] = 1;
                else if(type[t] == 'H') fa[j][0][2] = 1; // 更新从j跳到t的路径上的牛奶
                for(int k = 1;k < K;k ++){
                    fa[j][k][0] = fa[fa[j][k - 1][0]][k - 1][0]; // 与LCA模板相似，多了第三维
                    fa[j][k][1] = (fa[j][k - 1][1]) || (fa[fa[j][k - 1][0]][k - 1][1]);
                    fa[j][k][2] = (fa[j][k - 1][2]) || (fa[fa[j][k - 1][0]][k - 1][2]); // 更新fa数组中出现的牛奶
                }
            }
        }
    }
}
bool lca(int a,int b,char c){ // LCA
    int cow;
    if(c == 'G') cow = 1; // 把char换成int
    else cow = 2;
    if(type[a] == c || type[b] == c) return true; // 如果出现这种牛奶了，返回true
    if(depth[a] < depth[b]) swap(a,b); // 如果a在b的上面，交换a，b
    for(int i = K - 1;i >= 0;i --){ // 将a移到与b的深度一样的地方
        if(depth[fa[a][i][0]] >= depth[b]){
            if(fa[a][i][cow]) return true; // 判断是否跳到了有合适牛奶的地方
            a = fa[a][i][0];
            if(type[a] == c) return true; // 判断的其实都差不多
        }
    }
    if(a == b) return false;
    for(int i = K - 1;i >= 0;i --){ // 一起往上跳，如果出现朋友想要的牛奶，返回true
        if(fa[a][i][0] != fa[b][i][0]){
            if(fa[a][i][cow]) return true;
            if(fa[b][i][cow]) return true;
            a = fa[a][i][0];
            b = fa[b][i][0];
            if(type[a] == c || type[b] == c) return true;
        }
    }
    if(type[fa[a][0][0]] == c) return true; // 如果a，b的公共祖先是朋友想要的牛奶，返回true
    return false; // 没有找到朋友想要的牛奶，返回false
}
int main(){
    memset(h,-1,sizeof h); // 邻接表初始化
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++){
        char x;
        cin>>x;
        type[i] = x;
    }
    for(int i = 1;i < n;i ++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a); // 加双向边
    } // 以上为输入部分
    bfs(1); // 预处理
    for(int i = 1;i <= m;i ++){ // 处理m个询问
        int a,b;
        char x;
        scanf("%d%d",&a,&b);
        cin>>x;
        if(lca(a,b,x)) printf("1");
        else printf("0");
    }
    return 0;
}