题目描述

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

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

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

⌈AiBi⌉（上取整）次之后，再升级该技能将不会改变攻击力。

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

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

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

以下 N 行每行包含两个整数 Ai 和 Bi。

输出格式
输出一行包含一个整数表示答案。

数据范围
对于 40% 的评测用例，1≤N,M≤1000；
对于 60% 的评测用例，1≤N≤104，1≤M≤107；
对于所有评测用例，1≤N≤105，1≤M≤2×109，1≤Ai,Bi≤106。

输入样例：
3 6
10 5
9 2
8 1
输出样例：
47

算法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;
}

#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;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int t,m;
long long n,a,b;
int main(){
    scanf("%d",&t);
    while(t --){
        scanf("%lld%lld%lld",&n,&a,&b),m = n - a * b + 2;
        int l = 1,r = m >> 1;
        while(l < r){
            int mid = l + r >> 1;
            if((long long) mid * (m - mid) >= n) r = mid;
            else l = mid + 1;
        }
        if((long long) l * (m - l) == n){
            printf ("%d %d\n",l,m - l);
        }
        else{
            puts ("NO");
        }
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main(){
    int a, b;
    scanf("%d%d",&a,&b);
    long long res = 1;
    while(a > 1 && b --){
        res *= a;
        if(res > 1e9){
            res = -1;
            break;
        }
    }
    printf("%lld\n",res);
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n;
int h[N],e[N],ne[N],idx;
void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++ ;
}
int dfs(int u){
    int hmax = 0,cnt = 0;
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        hmax = max(hmax,dfs(j));
        cnt ++;
    }
    return hmax + cnt;
}
int main(){
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i = 2;i <= n;i ++){
        int p;
        scanf("%d",&p);
        add(p,i);
    }
    printf("%d\n",dfs(1));
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair <int,int> PII;
const int N = 1010,M = 60;
int n,m,k;
PII tree[N];
int b[M][M];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 0;i < n;i ++){
        scanf("%d%d",&tree[i].x,&tree[i].y);
    }
    int tc = 0;
    for(int i = k;i >= 0;i --){
        for(int j = 0;j <= k;j ++){
            scanf("%d",&b[i][j]);
            tc += b[i][j];
        }
    }
    int res = 0;
    for(int i = 0;i < n;i ++){
        int sx = tree[i].x,sy = tree[i].y;
        if(sx + k > m || sy + k > m) continue;
        int cnt = 0;
        for(int j = 0;j < n;j ++){
            int x = tree[j].x, y = tree[j].y;
            if(x >= sx && x - sx <= k && y >= sy && y - sy <= k){
                if(!b[x - sx][y - sy]) cnt = -1e8;
                else cnt ++;
            }
        }
        if(cnt == tc) res ++;
    }
    printf("%d\n",res);
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
int n,m,k;
int b[N];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1;i <= n;i ++){
        int t,c;
        scanf("%d%d",&t,&c);
        int l = t - k - c + 1,r = t - k;
        if(r > 0) b[max(1,l)] ++,b[r + 1] --;
    }
    for(int i = 1;i < N;i ++) b[i] += b[i - 1];
    for(int i = 1;i <= m;i ++){
        int q;
        scanf("%d",&q);
        printf("%d\n",b[q]);
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 40,M = 300010;
int n,x;
int w[N],f[M];
int main(){
    scanf("%d%d",&n,&x);
    int sum = 0;
    for(int i = 1;i <= n;i ++){
        scanf("%d",&w[i]);
        sum += w[i];
    }
    int m = sum - x;
    for(int i = 1;i <= n;i ++){
        for(int j = m;j >= w[i];j --){
            f[j] = max(f[j],f[j - w[i]] + w[i]);
        }
    }
    printf("%d\n",sum - f[m]);
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510,M = 1e5 + 10;
int n1,n2,m;
int match[N];
int h[N],e[M],ne[M],idx;
bool st[N];
void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
bool find(int x){
    for(int i = h[x];~i;i = ne[i]){
        int j = e[i];
        if(!st[j]){
            st[j] = true;
            if(match[j] == 0 || find(match[j])){
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    memset(h,-1,sizeof h);
    scanf("%d%d%d",&n1,&n2,&m);
    for(int i = 1;i <= m;i ++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    int res = 0;
    for(int i = 1;i <= n1;i ++){
        memset(st,false,sizeof st);
        if(find(i)) res ++;
    }
    printf("%d\n",res);
    return 0;
}