前言

（本套为研发A卷）

难度比较大，第二题可以巧妙地运用位运算技巧优化代码逻辑，第三题需要使用并查集配合反向思维求出答案，没做过类似的还真不好

小红的敌人

小红有几个精灵，精灵分布在 m 个房间中，第i个精灵可以施展ai次魔法，现在有k个敌人要攻击，每次攻击需要一个房间的精灵都消耗一次魔法，该次攻击可以击杀一个敌人。问小红最多可以消灭多少敌人。

输入描述

一行三个整数n,m,k，分别表示精灵数量，房间数量，敌人数量
接下来n行，每行两个整数，第i行表示第i个精灵的所在房间编号bi和可以施展的魔法次数 ai.
1<=n,m <=10^5
1<=bi<=m
1<=ai,k<=10^6

输出描述

输出一个整数，表示最多可以消灭的敌人数量。

示例1

输入

4 5 12
2 4
5 2
3 6
2 3

输出

11

说明

有12个敌人，第二个房间可以消灭3个敌人，第三个房间可以消灭6个敌人，第五个房间可以消灭2个敌人。总共可以消灭 11 个敌人。

思路与代码

代码的核心思想是找到一组物品中的某些物品，以最小化总成本，同时不超过给定的预算k。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
#define ll long long
int mod = 1e9 + 7;

void solve() {
    ll n, m, k;
    scanf("%lld %lld %lld",&n,&m,&k);
    int a[m+10];
    memset(a, 0x3f, sizeof a);
    for(int i = 0;i < n;++i) {
        int b, c;
        scanf("%d %d",&b,&c);
        a[b] = min(a[b], c);
    }
    ll ans = 0;
    for(int i = 1;i <= m;++i) {
        if(a[i] < 0x3f3f3f3f) ans += a[i];
    }
    cout << min(k, ans);
}

int main() {
    solve();
}

第二题

Linux文件的基本权限就有九个，分别是user/group/others(拥有者/组/其他)三种身份各有自己的 read/write/execute 权限。

变更权限的指令chmod的格式是chmod [ugoa...][+-=][rwx]...] 文件

[ugoa..]: u,g,o对应的是user/group/others，a 则代表 all，即全部的身份

[+-=]: + 表示增加权限，- 表示取消权限，= 表示唯一设定权限。

[rwx]:r表示可读取，w 表示可写入，x 表示可执行。

比如: chmod u=rw baidu txt表示将baiduxt的拥有者权限设置成可读、可写，所在组和其他用户的权限不变

chmod ug+rwx baidu.txt 表示将baidu.txt的拥有者和所在组权限增加可读、可写、可执行权限，其余不变

chmod a-x baidutxt 表示将baidutxt的全部身份取消可执行权限，其余不变

现在给定文件baidu.txt的初始权限和一些合法格式的chmod命令，输出经过这些命令修改后文件的权限。

输入描述

第一行文件的初始权限，格式为: wxrwxrwx

第二行一个整数N，表示有多少个chmod命令1<=N<=9

后面的N行，每行一个合法格式的chmod命令

输出描述

经过chmod命令修改后文件的权限

示例1

输入

rwxiw-r--
1
chmod g+x baidu.txt

输出

rwxrwxr--

思路与代码

这个代码模拟文件权限管理，接收初始权限和一系列命令，根据命令修改权限并输出。程序用数组表示文件权限，根据用户、操作符和权限位进行权限操作，然后输出新权限状态。需要运用位运算技巧优化代码逻辑。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
#define ll long long
int mod = 1e9 + 7;

void solve() {
    string s;
    cin >> s;
    int pow[3];
    memset(pow, 0, sizeof pow);
    for(int i = 0;i < 3;++i) {
        for(int j = 0;j < 3;++j) {
            if(j == 0 && s[i*3+j] == 'r') pow[i] |= (1<<j);
            if(j == 1 && s[i*3+j] == 'w') pow[i] |= (1<<j);
            if(j == 2 && s[i*3+j] == 'x') pow[i] |= (1<<j);
        }
    }
    int n;
    cin >> n;
    while(n--) {
        string chm;
        cin >> chm;
        cin >> chm;
        int curu = 0, op = 0, curp = 0;
        for(char c : chm) {
            if(c == 'u') curu |= 1;
            if(c == 'g') curu |= 2;
            if(c == 'o') curu |= 4;
            if(c == 'a') curu |= 7;
            if(c == '+') op = 0;
            if(c == '-') op = 1;
            if(c == '=') op = 2;
            if(c == 'r') curp |= 1;
            if(c == 'w') curp |= 2;
            if(c == 'x') curp |= 4;
        }
        for(int i = 0;i < 3;++i) {
            if((curu&(1<<i))) {
                if(op == 0) {
                    pow[i] |= curp;
                }
                else if(op == 1) {
                    pow[i] &= ~(curp);
                }
                else {
                    pow[i] = curp;
                }
            }
            if(pow[i]&1) cout << 'r';
            else cout << '-';
            if(pow[i]&2) cout << 'w';
            else cout << '-';
            if(pow[i]&4) cout << 'x';
            else cout << '-';
        }
        cin >> chm;
    }
}

int main() {
    solve();
}

第三题

小红有一棵n个节点的树，节点编号为1到n。每条边有一个权值，权值是 1 或者0。

对于一个长度为k的节点序列[a1,a2,...,ak]，按照顺序依次访问这些节点,从a;走到ai+1，会按照最短路径走。

小红想知道，对于所有长度为k 的节点序列中 (一共有n^k个长度为k的序列)，有多少个序列满足: 小红走完这个序列后，经过的所有边的权值之和不为0.

由于答案可能很大，你只需要输出答案对 10^9+ 7取模的结果。

注意，小红可以从一个节点走到它自己，也可以重复经过一条边.

输入描述

一行两个整数n和k，表示树的节点数和序列长度。
接下来n-1行，每行三个整数u,v,w，表示节点u和节点v
之间有一条边，权值为W.
1<=k<=n<=10^5
1<=u,v<=n,
0<=w<=1.

输出描述

输出一个整数，表示满足条件的序列个数对 10^9+7 取模的结果.

示例1

输入

3 2
1 2 1
2 3 0

输出

4

说明

四个序列分别为[1,2],[2, 1],[1, 3], [3,1]

思路与代码

需要使用并查集配合反向思维求出答案，以下是代码的主要思路和功能：

1. 初始化数组f和cnt，分别用于表示节点的父节点和节点的数量。

2. 实现了一个函数father，用于查找节点的根节点，实现了路径压缩。

3. 实现了一个函数modPow，用于计算快速幂运算，避免整数溢出。

4. 实现了一个函数connect，用于连接两个节点，并更新它们的父节点和数量。

5. 接受输入n和k，表示节点数和幂的指数。

6. 使用循环构建了一个图，根据输入的权值0或1来连接节点。

7. 计算了总的节点数目的幂，然后遍历节点，计算每个子图的幂并减去，最终输出结果。

这段代码解决了一个与图和数学有关的问题，使用了图的连接和数学的快速幂运算来计算最终结果。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
#define ll long long
int mod = 1e9 + 7;
int f[N];
int cnt[N];
int father(int i) {
    if(f[i] == i) return i;
    return f[i] = father(f[i]);
}
ll modPow(int a,int b) {
    if(b == 0) return 1;
    ll res = modPow(a,b / 2);
    res *= res;
    res %= mod;
    if(b % 2 == 1) {
        res *= a;
        res %= mod;
    }
    return res;
}
void connect(int i,int j) {
    int fi = father(i);
    int fj = father(j);
    if(fi != fj) {
        f[fi] = fj;
        cnt[fj] += cnt[fi];
    }
}
void solve() {
    int n,k;
    cin >> n >> k;
    for(int i = 0;i < n;i++) {
        cnt[i] = 1;
        f[i] = i;
    }
    for(int i = 0;i < n - 1;i++) {
        int u,v,w;
        cin >> u >> v >> w;
        u--,v--;
        if(w == 0) {
            connect(u,v);
        }
    }
    ll tot = modPow(n,k);
    for(int i = 0;i < n;i++) {
        if(f[i] == i) {
            ll res = modPow(cnt[i],k);
            tot = (tot - res + mod) % mod;
        }
    }
    cout << tot << endl;
}
int main() {
    solve();
}