ABC377

🕗 发布于 2024-11-08 14:58 算法 c++

C

有n个马放在棋盘上，求剩下不被马攻击到的位置个数。

用set

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

ll n;
int m;
set<pair<ll, ll>> s;


int main(){
    //freopen("in.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        ll a, b;
        cin >> a >> b;
        s.insert({ a, b });
        s.insert({ a + 2, b - 1 });
        s.insert({ a + 2, b + 1 });
        s.insert({ a + 1, b - 2 });
        s.insert({ a + 1, b + 2 });
        s.insert({ a - 1, b - 2 });
        s.insert({ a - 1, b + 2 });
        s.insert({ a - 2, b - 1 });
        s.insert({ a - 2, b + 1 });
    }
    ll sub = 0;
    for (auto [x, y] : s) {
        if (x >= 1 && x <= n && y >= 1 && y <= n)
            sub++;
    }
    ll ans = n * n - sub;
    printf("%lld\n", ans);
    return 0;
}

D

线段覆盖问题。
给了一系列线段 $L_i,R_i]$
求每个点l有多少点r组成的线段 $[l, r]$ 不会覆盖所有的线段，然后求和

双指针写崩了，后来发现不需要
我们可以遍历l，对每个l点来检查
如果l点是这一系列线段中的左端点，那么这一系列以l为左端点的线段其中的最小右端点-1就是r的取值上限。
但是我们从右往左遍历，如果之前的线段右端点的取值上限更小，那么也是取不到的。
比如线段有[4 6] [1 7] [1 9]
我们遍历4时r上限是5，
遍历1时r的上限不能取6，因为[1 6]会把[4 5]覆盖
维护这个上限即可。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;


int f[200020];
ll ans;
int n, m;


int main(){
    //freopen("in.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int l, r;
        cin >> l >> r;
        if (f[l] == 0) f[l] = r;
        else f[l] = min(f[l], r);
    }
    int rgt = m + 1;
    for (int i = m; i >= 1; -- i) {
        if (f[i] != 0) {
            rgt = min(rgt, f[i]);
        }
        ans += rgt - i;
    }
    printf("%lld\n", ans);
    return 0;
}

E

给一个数列 $A$
每次操作将 $A_i$ 同时转换为 $A_{A_i}$ ，求K次操作后的数列

第一反应是矩阵快速幂，但是N太大了
我们手动来看例子：5,6,3,1,2,4 -> 2,4,3,5,6,1 -> 4,5,3,6,1,2 -> 6,1,3,2,4,5
设第一次操作的变换为p0,第二次操作为p1
首先明确每个操作有循环性
把数列从上往下排
5 6 3 1 2 4
2 4 3 5 6 1
4 5 3 6 1 2
观察p1中的2，2转换为4的操作来源于p0中6->4
我们在p1中间插一行：
5 6 3 1 2 4
2 4 3 5 6 1
6 1 3 2 4 5
4 5 3 6 1 2
即每次 $p_i$ 操作都是两次 $p_{i-1}$ 操作
得出结论：找到循环节，然后对每个数进行 $2^K-1$ 次p0操作

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

ll n, k;
int a[200020];
bool vis[200020];
int f[200020];
int seq[200020];
vi lp[200020];


ll qpow(ll a, ll x, ll m) {
    if (x == 0)
        return 1;
    ll temp = qpow(a, x / 2, m);
    if (x & 1) {
        return temp * temp % m * a % m;
    }
    else {
        return temp * temp % m;
    }
}


int main(){
    //freopen("in.txt", "r", stdin);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        int t = a[i];
        while (!vis[t]) {
            f[t] = a[i];
            seq[t] = lp[a[i]].size();
            lp[a[i]].push_back(t);
            vis[t] = 1;
            t = a[t];
        }
    }
    for (int i = 1; i <= n; ++i) {
        int t = f[a[i]];
        ll m = lp[t].size();
        int r = seq[a[i]];
        int nr = (qpow(2, k, m) + (m - 1) + r) % m;
        int nt = lp[t][nr];
        printf("%d ", nt);
    }
    printf("\n");
    return 0;
}

F

棋盘里面放n(<1000)个皇后，问棋盘不被攻击到的位置和。

维护四个划去的线段。比较繁琐的一个题。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;


ll n;
int m;
ll ans;
unordered_map<ll, bool> row, col, dia0, dia1;
#define check(x) (x >= 1 && x <= n)


int main(){
    //freopen("in.txt", "r", stdin);
    cin >> n >> m;
    ll ans = 0;
    for (int i = 0; i < m; ++i) {
        ll x, y;
        cin >> x >> y;
        
        if (!row[y]) {
            set<pair<ll, ll>> dup;
            for (auto [c, _] : col) {
                dup.insert({ c, y });
            }
            for (auto [d, _] : dia0) {
                ll nx = d - y;
                if (check(nx))
                    dup.insert({ nx, y });
            }
            for (auto [d, _] : dia1) {
                ll nx = y - d;
                if (check(nx))
                    dup.insert({ nx, y });
            }
            row[y] = 1;
            ll add = n - dup.size();
            ans += add;
        }
        if (!col[x]) {
            set<pair<ll, ll>> dup;
            for (auto [r, _] : row) {
                dup.insert({ x, r });
            }
            for (auto [d, _] : dia0) {
                ll ny = d - x;
                if (check(ny))
                    dup.insert({ x, ny });
            }
            for (auto [d, _] : dia1) {
                ll ny = x + d;
                if (check(ny))
                    dup.insert({ x, ny });
            }
            col[x] = 1;
            ll add = n - dup.size();
            ans += add;
        }
        ll d = x + y;
        if (!dia0[d]) {
            set<pair<ll, ll>> dup;
            for (auto [r, _] : row) {
                ll nx = d - r;
                if (check(nx))
                    dup.insert({ nx, r });
            }
            for (auto [c, _] : col) {
                ll ny = d - c;
                if (check(ny))
                    dup.insert({ c, ny });
            }
            for (auto [d1, _] : dia1) {
                if ((d + d1) % 2 == 0) {
                    ll nx = (d - d1) / 2, ny = (d + d1) / 2;
                    if (check(nx) && check(ny)) {
                        dup.insert({ nx, ny });
                    }
                }
            }
            dia0[d] = 1;
            ll add = d <= 1 + n ? d - 1 : 2 * n - d + 1;
            ans += add - dup.size();
        }
        d = y - x;
        if (!dia1[d]) {
            set<pair<ll, ll>> dup;
            for (auto [r, _] : row) {
                ll nx = r - d;
                if (check(nx))
                    dup.insert({ nx, r });
            }
            for (auto [c, _] : col) {
                ll ny = d + c;
                if (check(ny))
                    dup.insert({ c, ny });
            }
            for (auto [d0, _] : dia0) {
                if ((d + d0) % 2 == 0) {
                    ll nx = (d0 - d) / 2, ny = (d0 + d) / 2;
                    if (check(nx) && check(ny)) {
                        dup.insert({ nx, ny });
                    }
                }
            }
            dia1[d] = 1;
            ll add = d >= 0 ? n - d : n + d;
            ans += add - dup.size();
        }
    }
    printf("%lld\n", n * n - ans);
    return 0;
}

G

n个string
依次对于k=1…n
$S_k$ 可以删除一个字符或增加一个字符记为1次操作
问： $S_k$ 修改为空或者 $S_1,S_2..S_{k-1}$ 的操作数最少为多少

在一堆字符串里做编辑，第一感觉就是字典树
按顺序插入，插入的时候去看每个位置到之前的叶子节点最短是多少，这就是先删除到插入位置再增加字符的最小代价
动态开树居然wa了好几次，建议静态开树（~~其实是我菜~~ ）

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int N = 200020;
int tr[N][26], d[N];
int n;


int main(){
    //freopen("in.txt", "r", stdin);
    cin >> n;
    int cnt = 0;
    int p = 0;
    memset(d, 0x3f, sizeof(d));
    for (int i = 0; i < n; ++i) {
        string s; 
        cin >> s;
        int m = s.length();
        int ans = m;
        p = 0;
        for (int j = 0; j < m; ++j) {
            int idx = s[j] - 'a';
            if (!tr[p][idx]) 
                tr[p][idx] = ++cnt;
            p = tr[p][idx];
            ans = min(ans, m - 1 - j + d[p]);
            d[p] = min(d[p], m - 1 - j);
        }
        printf("%d\n", ans);
    }
    return 0;
}

原文地址：https://blog.csdn.net/acrux1985/article/details/143615823

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Rust性能优化与调试之性能基准测试
下一篇：Linux文本操作三大利器总结：sed、awk、grep

imageio 图片转mp4
imageio 图片转mp4
阅读更多2024-11-08
RAG（检索增强生成）的实现流程；RAG怎么实现检索增强的
它通过将传统的检索技术与现代的生成式模型结合，在用户提出问题时，首先从海量数据中检索相关信息，再基于这些信息生成更精准的答案。：将加载的文档分割成更小的段落或部分，有助于提高检索的准确性和效率。RAG
阅读更多2024-11-08
刷新认知！国产大模型已超GPT-4
一个很重要的认知应该被刷新：中国的大模型已经超越了GPT-4在2023年的版本，并且与GPT-4在8月份的版本处于同一水平。这表明中国的大模型已经完全可用，中国AI正在赶上甚至超越国际领先水平！
阅读更多2024-11-08
ArcGIS Pro SDK （二十四）任务
【代码】ArcGIS Pro SDK （二十四）任务。
阅读更多2024-11-08
linux 下调试 mpu6050 三轴加速度
供自己备忘；
阅读更多2024-11-08
黑马程序员linux学习【持续更新】
Linux已经安装并且配置好了，接下来我们要来学习Linux的基本操作指令。而在学习之前，我们还需要做一件事情，由于我们企业开发时，Linux服务器一般都是在远程的机房部署的，我们要操作服务器，不会每
阅读更多2024-11-08
基于Java Web的传智播客crm企业管理系统的设计与实现
本文研究的是通过构建CRM企业管理系统的优势进行信息化管理，通过调查和分析现在企业业务的相关信息，综合对大部分企业的现状和未来发展趋势进行分析，进而提出比较好的管理策略和方针。5.1 在校学生管理（查
阅读更多2024-11-08
31-自定义地图：分层地图
carla教程
阅读更多2024-11-08
2024 信友队 noip 冲刺 10.8
考虑一个数字能被选择的条件。假设我们已经把 kkk 个数选进答案子序列中，那么对于没选择的数 iii，它能被选当且仅当 [i,n][i,n][i,n] 中有剩下没选的所有数字。我们考虑对于每个 iii
阅读更多2024-11-08
探索 Java 中 String 类的常用方法
String类的这些常用方法为处理字符串提供了极大的便利。掌握这些方法，可以帮助你更有效地编写代码，处理各种字符串相关的问题。在实际开发中，合理利用这些方法，可以提高代码的可读性和效率。
阅读更多2024-11-08

ABC377

C

D

E

F

G

相关文章