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.tpcf.cn/bicheng/89994.html

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【INT四则优先算式】2022-9-22

【INT四则优先算式】2022-9-22

缘由ccf201903-2二十四点我用暴力破解做的&#xff0c;但是两个程序一个拿到了满分&#xff0c;一个拿到了50分&#xff0c;看了很长时间也没看出问题在哪里&#xff0c;希望有英雄慧眼帮我看一下-编程语言-CSDN问答 void INT四则优先算式() {//缘由https://ask.csdn.net/ques…
阅读更多...
本地k8s集群的搭建

本地k8s集群的搭建

windows机器&#xff0c;考虑如果使用云服务器&#xff0c;每年的开销还是太大&#xff0c;不值得&#xff0c;自己只是做demo&#xff0c;了解各种配置和使用即可&#xff0c;使用VMware的虚拟机来搭建k8s集群 使用docker安装rancher和k8s yum -y install chronycat > /et…
阅读更多...
B树、B+树的区别及MySQL为何选择B+树

B树、B+树的区别及MySQL为何选择B+树

B树与B树 B树和B树都是自平衡的多路搜索树&#xff0c;广泛应用于数据库和文件系统中&#xff0c;用于高效管理大量数据。它们的设计目标是在磁盘存储环境下减少I/O操作次数&#xff0c;提高数据访问效率。下面我将逐步解释两者的定义、特性、比较以及应用场景&#xff0c;确保…
阅读更多...
Unity之可视化编程VisualScripting快速入门

Unity之可视化编程VisualScripting快速入门

文章目录 前言 脚本机和状态机 脚本图ScriptGraph 脚本图 子图 自定义事件 状态图StateGraph 状态图 Start状态 创建新状态 过渡连接 常用功能 射线检测 补间动画 按钮点击 前言 可视化脚本使您无需编写代码即可为游戏或应用程序创建逻辑。可视化脚本使用基于节点的可视化图形…
阅读更多...
2025三掌柜赠书活动第二十五期 网络安全应急响应实战

2025三掌柜赠书活动第二十五期 网络安全应急响应实战

目录 前言 网络安全的重要性 关于《网络安全应急响应实战》 编辑推荐 内容简介 作者简介 图书目录 《网络安全应急响应实战》全书速览 结束语 前言 在当今数字化时代&#xff0c;网络安全已经成为企业和个人都无法忽视的重要问题。随着网络技术的飞速发展&#xff0c;…
阅读更多...
车载软件架构 --- 软件开发面临的问题

车载软件架构 --- 软件开发面临的问题

我是穿拖鞋的汉子，魔都中坚持长期主义的汽车电子工程师。 老规矩，分享一段喜欢的文字，避免自己成为高知识低文化的工程师： 周末洗了一个澡，换了一身衣服，出了门却不知道去哪儿，不知道去找谁，漫无目的走着，大概这就是成年人最深的孤独吧! 旧人不知我近况，新人不知我过…
阅读更多...
MySQL 8.0 OCP 1Z0-908 题目解析(31)

MySQL 8.0 OCP 1Z0-908 题目解析(31)

题目121 Choose two. Examine this command, which executes successfully on InnoDB Cluster: dba.dropMetadataSchema() Which two statements are true? □ A) The mysql_innodb_cluster_metadata schema is dropped from the instance where the connection was establish…
阅读更多...
本地生活服务 app 同城信息发布系统搭建

本地生活服务 app 同城信息发布系统搭建

一、逻辑分析用户需求层面&#xff1a;对于发布者来说&#xff0c;需要一个便捷的界面来输入同城信息&#xff0c;包括但不限于房屋租售、招聘求职、二手交易、活动推广等各类信息。发布者要能够上传相关图片、详细描述信息内容、设置价格&#xff08;如果有需要&#xff09;、…
阅读更多...
[Python] -项目实战4- 利用Python进行Excel批量处理

[Python] -项目实战4- 利用Python进行Excel批量处理

一、为什么要批量处理Excel文件？ 节省时间：人工对数十、数百个 Excel 文件重复操作不现实，Python 批量处理一次搞定。 保证一致性：统一格式、统一操作，避免手动误差。 易于集成：可嵌入日常自动化流程，支持定时和触发执行。 二、常用库及选型建议 库 作用 优势 局限 p…
阅读更多...
社区搜索离线回溯系统设计：架构、挑战与性能优化｜得物技术

社区搜索离线回溯系统设计：架构、挑战与性能优化｜得物技术

一、项目背景在社区场景中&#xff0c;我们积累了丰富的用户互动数据。这些历史互动信息对CTR/CVR预估建模具有重要参考价值&#xff0c;用户的每次互动都反映了其特定维度的偏好特征。当前&#xff0c;已在多个业务实践中验证&#xff0c;基于用户历史互动特征进行未来行为预测…
阅读更多...
WPF——自定义ListBox

WPF——自定义ListBox

在阅读本文前&#xff0c;最好先看看WPF——自定义RadioButton 背景 WPF中实现单选功能通常有两种方案&#xff1a; - RadioButton组&#xff1a;传统方案&#xff0c;但代码冗余 - ListBox定制&#xff1a;通过样式改造&#xff0c;兼顾数据绑定和UI灵活性 需求 一组选项中…
阅读更多...
rancher上使用rke在华为云多网卡的服务器上安装k8s集群问题处理了

rancher上使用rke在华为云多网卡的服务器上安装k8s集群问题处理了

报错:问题&#xff1a;[[network] Host [192.168.0.213] is not able to connect to the following ports: [192.168.0.213:2379]. Please check network policies and firewall rules]问题&#xff1a; roothwy-isms-210-66:~# gotelnet 172.17.210.66 2379 map[2379:failed] …
阅读更多...
xformers包介绍及代码示例

xformers包介绍及代码示例

文章目录主要特性安装方式主要优势使用场景注意事项代码示例xFormers是由Meta开发的一个高性能深度学习库&#xff0c;专门用于优化Transformer架构中的注意力机制和其他组件。它提供了内存高效和计算高效的实现&#xff0c;特别适用于处理长序列和大规模模型。github地址&…
阅读更多...
CityEngine自动化建模

CityEngine自动化建模

CityEngine学习记录 学习网址&#xff1a; 百度安全验证 CityEngine-CityEngine_Rule-based_Modeling-基于规则建模和输出模型 - 豆丁网 CityEngine 初探-CSDN博客 City Engine CGA 规则包_cga规则-CSDN博客 CityEngine学习记录 学习网址&#xff1a;百度安全验证 CityE…
阅读更多...
Nacos+LoadBalancer实现服务注册与发现

Nacos+LoadBalancer实现服务注册与发现

目录 一、相关文章 二、兼容说明 三、服务注册到Nacos 四、服务发现 五、服务分级存储模型 六、查看集群服务 七、LoadBalancer负载均衡 一、相关文章 基础工程&#xff1a;gradle7.6.1springboot3.2.4创建微服务工程-CSDN博客 Nacos服务端安装&#xff1a;Nacos服务端…
阅读更多...
事务并发-封锁协议

事务并发-封锁协议

事务并发数据库里面操作的是事务。事务特性&#xff1a;原子性&#xff1a;要么全做&#xff0c;要么不做。一致性&#xff1a;事务发生后数据是一致的。隔离性&#xff1a;任一事务的更新操作直到其成功提交的整个过程对其他事务都是不可见的&#xff0c;不同事务之间是隔离的…
阅读更多...
大气波导数值预报方法全解析：理论基础、预报模型与误差来源

大气波导数值预报方法全解析：理论基础、预报模型与误差来源

我们希望能够像天气预报一样&#xff0c;准确预测何时、何地会出现大气波导&#xff0c;其覆盖范围有多大、持续时间有多长&#xff0c;以便为通信、雷达等应用提供可靠的环境保障。 目录 &#xff08;一&#xff09;气象预报 1.1 气象预报的分类 1.2 大气数值预报基础 1.2…
阅读更多...
关于JavaWeb的总结笔记

关于JavaWeb的总结笔记

JavaWeb基础描述Web服务器的作用是接受客户端的请求&#xff0c;给客户端响应服务器的使用Tomcat&#xff08;最常用的&#xff09;JBossWeblogicWebsphereJavaWeb的三大组件Servlet主要负责接收并处理来自客户端的请求&#xff0c;随后生成响应结果。例如&#xff0c;在处理用…
阅读更多...
生成式引擎优化（GEO）核心解析：下一代搜索技术的演进与落地策略

生成式引擎优化（GEO）核心解析：下一代搜索技术的演进与落地策略

最新统计数据声称&#xff0c;今天的 Google 搜索量是 ChatGPT 搜索的 373 倍&#xff0c;但我们大多数人都觉得情况恰恰相反。 那是因为很多人不再点击了。他们在问。 他们不是浏览搜索结果&#xff0c;而是从 ChatGPT、Claude 和 Perfasciity 等工具获得即时的对话式答案。这…
阅读更多...
网编数据库小练习

网编数据库小练习

搭建服务器客户端&#xff0c;要求 服务器使用 epoll 模型 客户端使用多线程 服务器打开数据库&#xff0c;表单格式如下 name text primary key pswd text not null 客户端做一个简单的界面&#xff1a;1&#xff1a;注册2&#xff1a;登录无论注册还是登录&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023