20250721

P5357 【模板】AC 自动机 - 洛谷

主要是构建fail树

/*

我们可以知道的是，当访问一个点x时，接下来需要跳转其fail[x]，以此类推，如果在某个fail[x]上出现了一个字符串，那么相应的统计次数应该加1，然后当访问到fail[x]时，又要继续访问fail[fail[x]]造成了一个点多次访问的情况

那么我们可以看出如果我们访问到了一个点x,那么接下来他的fail点都会继续访问到，那么我们其实可以构造一个fail树，当匹配主串的时候仅让siz[u]++,而不跳转他的fail[u],然后再遍历完主串的时候我们得到了每个点访问的次数，构建fail树，根据树的特性遍历求出哪些点访问过了多少次，这样就能把时间控制在O(S + T + n)内，S是模式串的总长度，T是主串长度，n是模式串个数

*/

#include<bits/stdc++.h>
using namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int> TUP;const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n;
int cnt[N], ne[N], ch[N][30], idx;
string s[N], t;
int match[N]; // 统计第几个字符串出现在哪个idx上
int siz[N];  // 每个点访问过的次数
vector<int> vec[N];  // 构建fail树void insert(string x, int id)
{int p = 0;rep(0, x.size() - 1){int j = x[i] - 'a';if(!ch[p][j]) ch[p][j] = ++idx;p = ch[p][j];}cnt[p]++;match[id] = p;
}void built()
{queue<int> q;rep(0, 25)if(ch[0][i])q.push(ch[0][i]);while(!q.empty()){auto u = q.front();q.pop();for(int i = 0; i <= 25; i++){int v = ch[u][i];if(v) ne[v] = ch[ne[u]][i], q.push(v);elsech[u][i] = ch[ne[u]][i];}}
}void dfs(int u)
{for(auto it : vec[u]){dfs(it);siz[u] += siz[it];}
}void query(string x)
{for (int k = 0, i = 0; k < x.size(); k++){i = ch[i][x[k] - 'a'];++siz[i];}rep(1, idx)vec[ne[i]].pb(i);dfs(0);rep(1, n)cout << siz[match[i]] << '\n';
}void solve()
{cin >> n;rep(1, n){cin >> s[i];insert(s[i], i);}built();cin >> t;query(t);
}signed main()
{IOS;int T = 1;// cin >> T;while(T --)solve();return 0;
}

https://codeforces.com/problemset/problem/2109/B

#include<bits/stdc++.h>
using namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int> TUP;const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, m, a, b;void solve()
{cin >> n >> m >> a >> b;if(n == 2 && m == 2){cout << 2 << '\n';return;}int t1 = ceil(log2(n)), t2 = ceil(log2(m));int c1 = ceil(log2(min(a, n - a + 1))), c2 = ceil(log2(min(b, m - b + 1)));cout << min(t1 + c2, c1 + t2) + 1 << '\n';
}signed main()
{IOS;int T = 1;cin >> T;while(T --)solve();return 0;
}

https://codeforces.com/problemset/problem/2108/B

#include<bits/stdc++.h>
using namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int> TUP;const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, x;void solve()
{cin >> n >> x;int cnt = 0;int tx = x;if(n == 1 && x == 0){cout << -1 << '\n';return;}while(tx){if(tx & 1) cnt++;tx /= 2;}if(n <= cnt){cout << x << '\n';return;}else{if((n - cnt) % 2 == 0)cout << x + (n - cnt) << '\n';else{if(x > 1) cout << x + (n - cnt) + 1 << '\n';elsecout << n + 3 << '\n';}}
}signed main()
{IOS;int T = 1;cin >> T;while(T --)solve();return 0;
}

Contest Login
 

#include<bits/stdc++.h>
using namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int> TUP;const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, x, y;int count(int a)
{int ans = 0;while(a){if(a & 1) ans ++;a /= 2;}return ans;
}void solve()
{cin >> n >> x >> y;if(x == y){cout <<  0 << '\n';return;}if(count(x) == count(y) || lowbit(x) == lowbit(y)){cout << 1 << "\n";return;}cout << 2 << '\n';
}signed main()
{IOS;int T = 1;cin >> T;while(T --)solve();return 0;
}


Contest Login

#include<bits/stdc++.h>
using namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int> TUP;const int N = 2e5 + 10, INF = 0x3f3f3f3f;void solve()
{int n;scanf("%d", &n);printf("%.4f\n", 1.0 * 3 * n / 2);
}signed main()
{// IOS;int T = 1;cin >> T;while(T --)solve();return 0;
}

二维偏序问题

Contest Login

/*
题目的意思就是对于一个数在a[]数组中的位置为i,在b[]数组中的位置为j，那么我们的结果就是(i - 1) + (j - 1) + 前面重复的部分
主要就是重复的部分怎么求呢？如果有重复的部分，那么是不是一个数x在a[]和b[]中的下标分别小于i, j。这就是一个典型的二维偏序问题。经典的做法就是树状数组
我们对于a[]原封不动，对于b[]数组，记录下b[]元素所在b[]数组中的位置。我们开始遍历a[]数组，得到a[]数组的(i - 1) + (j - 1)这个值。根据遍历a[]数组的顺序就可以知道，a[]数组后面的元素所要加的值肯定有a[]数组前面的元素，那么我们在把a[i]在b[]数组中出现的位置用BIT统计上，这样如果我们访问a[]的下一个元素的时候，如果这个元素在b[]中的位置在j之后，那么因为我们刚才更新了BIT就能直接通过BIT减去重复的，如果在j之前的话，那么就没有影响。。。以此类推
*/


#include<bits/stdc++.h>
using namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int> TUP;const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n;
int a[N], b[N], p[N], ans[N];struct BIT
{int s[N];BIT(){init();}void init(){memset(s, 0, sizeof s);}void update(int poi, int val){for (int i = poi; i <= n; i += lowbit(i))s[i] += val;}int query(int poi){int ans = 0;for (int i = poi; i > 0; i -= lowbit(i))ans += s[i];return ans;}
};BIT bit;void solve()
{cin >> n;bit.init();rep(1, n) cin >> a[i];rep(1, n){cin >> b[i];p[b[i]] = i;}rep(1, n){int res = (i - 1) + (p[a[i]] - 1);res -= bit.query(p[a[i]]);// cout << ans << " \n"[i == n];ans[a[i]] = res;bit.update(p[a[i]], 1);}rep(1, n) cout << ans[i] << " \n"[i == n];
}signed main()
{IOS;int T = 1;cin >> T;while(T --)solve();return 0;
}

 P2163 [SHOI2007] 园丁的烦恼 - 洛谷

核心思想就是因为我们统计的是每一个矩形框内的点的个数，那么难免会用到二维前缀和，但是有时候我们的二维前缀和的数组需要开太大题目不支持。我们在计算二维前缀和的时候会用到一个公式，那么我们就就可以根据扫描线的原理，先将所有的点按照x从大到小的顺序排序，然后将满足x条件的点全加进BIT中，但是加进来的是这个点的纵坐标，然后因为我们将访问一个矩阵变成了4个矩阵的而访问和，那么我们在对每一个访问矩阵的操作的时候就可以直接计算满足其y的点的个数，本质还是通过BIT的离线处理

#include<bits/stdc++.h>
using namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int, int> TUP;const int N = 1e7 + 5, INF = 0x3f3f3f3f;
int n, m;struct BIT
{int s[N];BIT(){init();}void init(){memset(s, 0, sizeof s);}void update(int poi, int val){for (int i = poi; i < N; i += lowbit(i))s[i] += val;}int query(int poi){int ans = 0;for (int i = poi; i > 0; i -= lowbit(i))ans += s[i];return ans;}
} bit;vector<PII> vec;
vector<TUP> qu;
int ans[(int)5e5 + 10];void solve()
{cin >> n >> m;rep(1, n){int a, b;cin >> a >> b;++a, ++b;vec.pb({a, b});}rep(1, m){int x1, x2, y1, y2;cin >> x1 >> y1 >> x2 >> y2;++x1, ++y1, ++x2, ++y2;qu.pb({x2, y2, 1, i});qu.pb({x1 - 1, y2, -1, i});qu.pb({x2, y1 - 1, -1, i});qu.pb({x1 - 1, y1 - 1, 1, i});}sort(vec.begin(), vec.end());sort(qu.begin(), qu.end());int cur = 0;for(auto [x, y, c, id] : qu){while(cur < n && vec[cur].first <= x)bit.update(vec[cur].second, 1), cur++;ans[id] += bit.query(y) * c;}rep(1, m) cout << ans[i] << '\n';
}signed main()
{IOS;int T = 1;// cin >> T;while(T --)solve();return 0;
}

P3755 [CQOI2017] 老C的任务 - 洛谷

加了离散化的，就是关键是一定要注意树状数组的大小问题。

#include<bits/stdc++.h>
using namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define lowbit(x) (x & (-x))
#define int long long
#define rep(l, r) for(int i = l; i <= r; i++)
#define pb push_backtypedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, double> PID;
typedef tuple<int, int, int, int> TUP;const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m;
int maxlen;
vector<array<int, 3>> vec;
vector<TUP> que;vector<int> vy;
map<int, int> mp;
int ans[N];struct BIT
{int s[N * 10];BIT(){init();}void init(){memset(s, 0, sizeof s);}void update(int poi, int val){for (int i = poi; i <= maxlen; i += lowbit(i))s[i] += val;}int query(int poi){int ans = 0;for (int i = poi; i > 0; i -= lowbit(i))ans += s[i];return ans;}
} bit;void solve()
{cin >> n >> m;rep(1, n){int a, b, c;cin >> a >> b >> c;vec.pb({a, b, c});vy.pb(b);}rep(1, m){int x1, x2, y1, y2;cin >> x1 >> y1 >> x2 >> y2;que.pb({x1 - 1, y1 - 1, 1, i});que.pb({x2, y2, 1, i});que.pb({x1 - 1, y2, -1, i});que.pb({x2, y1 - 1, -1, i});vy.pb(y2), vy.pb(y1 - 1);}sort(vec.begin(), vec.end());sort(vy.begin(), vy.end());sort(que.begin(), que.end());vy.erase(unique(vy.begin(), vy.end()), vy.end());maxlen = vy.size();rep(0, vy.size() - 1)mp[vy[i]] = i + 1;int cur = 0;for(auto [x, y, c, id] : que){while(cur < n && vec[cur][0] <= x){bit.update(mp[vec[cur][1]], vec[cur][2]);cur++;}ans[id] += c * bit.query(mp[y]);}rep(1, m) cout << ans[i] << '\n';
}signed main()
{IOS;int T = 1;// cin >> T;while(T --)solve();return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/2628.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Maven

Maven

目录 1 什么是 Maven 2 Maven 核心功能 项目构建 依赖管理 Maven Help 插件 3 Maven 仓库 本地仓库 中央仓库 私有服务器&#xff08;简称私服&#xff09; 4 Maven 设置国内源 配置当前项目 setting 设置新项目的 setting 1 什么是 Maven Maven 是一个项目管理工…
阅读更多...
RabbitMQ核心组件浅析：从Producer到Consumer

RabbitMQ核心组件浅析：从Producer到Consumer

作为分布式系统中异步通信的扛把子&#xff0c;RabbitMQ 凭借其高可靠、灵活路由的特性&#xff0c;几乎是每个后端开发者的"必备技能"。但很多新手刚接触时&#xff0c;常被各种组件名称绕晕——Broker、Exchange、Queue、vhost…这些"术语炸弹"到底啥关系…
阅读更多...
c#转python第四天：生态系统与常用库

c#转python第四天：生态系统与常用库

作为系列文章的第 4 篇，本文将聚焦 Python 生态中最具代表性的技术栈，通过与 C# 对应技术的横向对比，帮助开发者快速掌握 Python 在数据处理、Web 开发和异步编程领域的核心优势。无论是有 C# 基础想转 Python 的开发者，还是需要在两种语言间做技术选型的团队，都能从本文的…
阅读更多...
nginx定期清理日志

nginx定期清理日志

原创作者&#xff1a;运维工程师 谢晋 nginx定期清理日志 创建脚本clean_nginx_logs.sh # vi clean_nginx_logs.sh#!/bin/bash# 定义日志文件路径 LOG_DIR"/var/log/nginx" ACCESS_LOG"access.log" ERROR_LOG"error.log"# 定义保留日志的天数…
阅读更多...
【Go语言-Day 22】解耦与多态的基石：深入理解 Go 接口 (Interface) 的核心概念

【Go语言-Day 22】解耦与多态的基石：深入理解 Go 接口 (Interface) 的核心概念

Langchain系列文章目录 01-玩转LangChain&#xff1a;从模型调用到Prompt模板与输出解析的完整指南 02-玩转 LangChain Memory 模块&#xff1a;四种记忆类型详解及应用场景全覆盖 03-全面掌握 LangChain&#xff1a;从核心链条构建到动态任务分配的实战指南 04-玩转 LangChai…
阅读更多...
YOLO多模态融合 | 从 DEA 到 DEFA：动态卷积＋交叉注意力的创新融合

YOLO多模态融合 | 从 DEA 到 DEFA：动态卷积＋交叉注意力的创新融合

本教程基线代码为开源项目 YOLOFuse 请注意&#xff1a;并非在所有数据集上都能带来性能提升。DEFA 模块是我基于自身思路改进的——在您的数据集上是否有效&#xff0c;还需您自行实验验证&#xff0c;无法保证一定会有所增益。 一、背景与动机 在多模态目标检测场景中&#…
阅读更多...
基于SEP3203微处理器的嵌入式最小硬件系统设计

基于SEP3203微处理器的嵌入式最小硬件系统设计

目录 1 引言 2 嵌入式最小硬件系统 3 SEP3202简述 4 最小系统硬件的选择和单元电路的设计 4.1 电源电路 4.2 晶振电路 4.3 复位及唤醒电路 4.5 存储器 4.5.1 FLASH存储 4.5.2 SDRAM 4.6 串行接口电路设计 4.7 JTAG模块 4.8 扩展功能&#xff08;LED&#xff09; …
阅读更多...
PCIe RAS学习专题（3）：AER内核处理流程梳理

PCIe RAS学习专题（3）：AER内核处理流程梳理

目录 一、AER内核处理整体流程梳理 二、AER代码重要部分梳理 1、AER初始化阶段 2、中断上半部 aer_irq 3、中断下半部 aer_isr 3.1、aer_isr_one_error 3.2、find_source_device 3.3、aer_process_err_devices 3.4、handle_error_source 3.5、pcie_do_recovery 整体逻…
阅读更多...
Window延迟更新10000天配置方案

Window延迟更新10000天配置方案

1.点击"开始"菜单&#xff0c;搜索"注册表编辑器"&#xff0c;点击"打开"。2.找到"\HKEY LOCAL MACHINE\SOFTWARE\Microsoft\WindowsUpdate\Ux\Settings"路径。3.右面空白处右键新建一个32位值&#xff0c;命名为FlightSettingsMaxPau…
阅读更多...
TCP/IP 哲学：端到端的 Postel 定律

TCP/IP 哲学：端到端的 Postel 定律

实际上这是互联网哲学&#xff0c;但 TCP/IP 是互联网的事实标准&#xff0c;也是互联网的唯一实例&#xff0c;因此 TCP/IP 等同于互联网。 我写过很多 TCP/IP 发展史的随笔&#xff0c;于宏观&#xff0c;我希望理解互联网何以至此&#xff0c;于微观&#xff0c;希望理解 TC…
阅读更多...
Linux下使用原始socket收发数据包

Linux下使用原始socket收发数据包

在Linux系统中&#xff0c;使用非原始的socket&#xff0c;可以收发TCP或者UDP等网络层数据包。如果要处理网络层以下的数据包&#xff0c;比如ICMP、ARP等&#xff0c;或者更底层&#xff0c;比如链路层数据包&#xff0c;就得使用原始socket了。 创建socket 创建socket要使用…
阅读更多...
cocosCreator2.4 Android 输入法遮挡

cocosCreator2.4 Android 输入法遮挡

这里是 调用显示系统的输入法&#xff0c;然后在 Cocos2dxEditBox.java 创建UI,用于处理输入&#xff0c;这里可以看到会ui 会被系统的输入法遮挡&#xff0c;无法点击&#xff0c;是因为 计算ui位置时没有算上刘海区域&#xff0c;需要处理一下&#xff1a; private int getTo…
阅读更多...
最新文章

Copyright @ 2022~2023