- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
比赛链接 。
知识点:KMP,构造.
考虑构造全 \(0,1\) 串,至少有一个可行.
我们只需要考虑到 \(t\) 的border \(t'\) ,即 \(t'+s+t'\) :
因此,我们只需要构造两次检查一下即可,检查方式有KMP、Z函数、哈希等等.
时间复杂度 \(O(n)\) 。
空间复杂度 \(O(n)\) 。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
class KMP {
int m;
string p;
vector<int> nxt;
public:
KMP() {}
KMP(const string &_p) { init(_p); }
void init(const string &_p) {
m = _p.size() - 1;
p = _p;
nxt.assign(m + 1, 0);
for (int i = 2;i <= m;i++) {
nxt[i] = nxt[i - 1];
while (nxt[i] && p[i] != p[nxt[i] + 1]) nxt[i] = nxt[nxt[i]];
nxt[i] += p[i] == p[nxt[i] + 1];
}
}
vector<int> find(const string &s) {
int n = s.size() - 1;
vector<int> pos;
for (int i = 1, j = 0;i <= n;i++) {
while (j && s[i] != p[j + 1]) j = nxt[j];
j += s[i] == p[j + 1];
if (j == m) {
pos.push_back(i - j + 1);
j = nxt[j];
}
}
return pos;
}
vector<int> get_cycle_time() {
vector<int> res;
int pos = m;
while (pos) {
pos = nxt[pos];
res.push_back(m - pos);
}
return res;
}
vector<int> get_cycle_loop() {
vector<int> res;
for (auto val : get_cycle_time())
if (!(m % val)) res.push_back(val);
return res;
}
int min_cycle_loop() { return get_cycle_loop()[0]; }
void debug() {
for (int i = 1;i <= m;i++)
cout << nxt[i] << " \n"[i == m];
}
};
/// KMP,前缀函数O(|P|)、查找O(|S|+|P|)、循环相关O(|P|),维护字符串前缀函数
bool solve() {
int n;
cin >> n;
string t;
cin >> t;
KMP kmp("?" + t);
if (kmp.find("?" + t + string(n, '0') + t).size() <= 2) cout << string(n, '0') << '\n';
else cout << string(n, '1') << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
知识点:二分,贪心.
显然每次只有最小值和最大值会被票出.
具体来说,我们统计最大值和最小值中点左右两侧的人数,左侧一定给最大值票,右侧一定给最小值票。当左大于等于右时,最大值会被票出,否则最小值会被票出.
因此,我们排序后,用二分找到中点的位置,用双指针表示当前剩余区间.
时间复杂度 \(O(n\log n)\) 。
空间复杂度 \(O(n)\) 。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<pair<int, int>> a(n + 1);
for (int i = 1;i <= n;i++) {
int x;
cin >> x;
a[i] = { x,i };
}
sort(a.begin() + 1, a.end());
int l = 1, r = n;
for (int i = 1;i <= n - 1;i++) {
int mid = a[l].first + a[r].first >> 1;
int it = upper_bound(a.begin() + l, a.begin() + r + 1, pair<int, int>{ mid, 2e9 }) - a.begin();
int lval = it - l;
int rval = r - it + 1;
if (lval >= rval) r--;
else l++;
}
cout << a[l].second << '\n';
return 0;
}
知识点:构造.
尝试在正方形对角线上选择一点,将正方形分为左上正方形,右下正方形和两个对称的长方形.
然后,按照类似gcd的方式,对长方形进行划分正方形.
可以统计得到一定存在一点,使得长方形划分后的正方形数量不超过 \(24\) ,即总和不超过 \(50\) .
因此,我们递归执行两种操作即可.
时间复杂度 \(O(n^2)\) 。
空间复杂度 \(O(n^2)\) 。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int gcd(int a, int b, int &cnt) {
if (b) {
cnt += a / b;
return gcd(b, a % b, cnt);
}
else return a;
}
vector<tuple<int, int, int>> ans;
void dfs_rec(int x, int y, int a, int b);
void dfs_sqr(int x, int y, int a);
void dfs_rec(int x, int y, int a, int b) {
bool sw = a < b;
if (sw) swap(x, y), swap(a, b);
if (!b) return;
for (int i = b;i <= a;i += b) {
if (sw) dfs_sqr(y, x + i - b, b);
else dfs_sqr(x + i - b, y, b);
}
if (sw) dfs_rec(y, x + a / b * b, b, a % b);
else dfs_rec(x + a / b * b, y, a % b, b);
}
void dfs_sqr(int x, int y, int a) {
if (a == 1) return;
if (a <= 7) {
ans.push_back({ x,y,a });
return;
}
bool ok = 0;
for (int i = 1;i <= a - 1;i++) {
int cnt = 0;
gcd(i, a - i, cnt);
if (cnt >= 25) continue;
ok = 1;
dfs_sqr(x, y, i);
dfs_rec(x + i, y, a - i, i);
dfs_rec(x, y + i, i, a - i);
dfs_sqr(x + i, y + i, a - i);
break;
}
assert(ok);
ans.push_back({ x,y,a });
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
dfs_sqr(1, 1, n);
cout << ans.size() << '\n';
for (auto [x, y, a] : ans) cout << x << ' ' << y << ' ' << a << '\n';
return 0;
}
知识点:线性dp,前缀和.
考虑设 \(f_{i,j}\) 为考虑了前 \(i\) 个数的后缀(不可为空)最小值为 \(j\) 时的方案数。显然, \(j \in [-m,m]\) 中.
在 \(f_{i-1,j}\) 时, \([-j,m]\) 的数字可以被使用,进一步分类讨论转移方程:
当 \(j\geq 0\) 时,后缀最小值更新为 \(a_i\) 本身:
当 \(j < 0\) 时,后缀最小值更新为 \(a_i + j\) :
用前缀和优化转移即可.
时间复杂度 \(O(nm)\) 。
空间复杂度 \(O(m)\) 。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 998244353;
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> f(2 * m + 1);
f[2 * m] = 1;
for (int i = 0;i < n;i++) {
vector<int> g(2 * m + 1);
for (int j = -m;j <= m;j++) {
if (j >= 0) (g[-j + m] += f[j + m]) %= P;
else {
(g[0 + m] += f[j + m]) %= P;
(g[j + m + m + 1] -= f[j + m] - P) %= P;
}
}
for (int j = -m + 1;j <= m;j++) (g[j + m] += g[j - 1 + m]) %= P;
swap(f, g);
}
int ans = 0;
for (int i = -m;i <= m;i++) (ans += f[i + m]) %= P;
cout << ans << '\n';
return 0;
}
知识点:离线,枚举.
考虑离线后倒着操作,并统计行的个数.
显然每行每列只关心最后一次操作的类型,之后的操作不需要考虑.
记录列开、列关的列数分别为 \(cnt_{on},cnt_{off}\) 。若行操作为打开,答案增加 \(m - cnt_{off}\) ,否则增加 \(cnt_{on}\) .
最后统计没被操作的行,对于每行答案增加 \(cnt_{on}\) .
时间复杂度 \(O(n+q)\) 。
空间复杂度 \(O(n+m+q)\) 。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Query {
bool row;
int id;
bool on;
}Q[1000007];
bool row_vis[1000007];
bool col_vis[1000007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m, q;
cin >> n >> m >> q;
for (int i = 1;i <= q;i++) {
string row;
int id;
string on;
cin >> row >> id >> on;
Q[i] = { row == "row",id,on == "on" };
}
ll ans = 0;
int cnt_on = 0, cnt_off = 0;
for (int i = q;i >= 1;i--) {
if (Q[i].row) {
if (row_vis[Q[i].id]) continue;
ans += Q[i].on ? m - cnt_off : cnt_on;
row_vis[Q[i].id] = 1;
}
else {
if (col_vis[Q[i].id]) continue;
if (Q[i].on) cnt_on++;
else cnt_off++;
col_vis[Q[i].id] = 1;
}
}
for (int i = 1;i <= n;i++) if (!row_vis[i]) ans += cnt_on;
cout << ans << '\n';
return 0;
}
最后此篇关于2023牛客暑期多校训练营4AFHJL的文章就讲到这里了,如果你想了解更多关于2023牛客暑期多校训练营4AFHJL的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
real adaboost Logit boost discrete adaboost 和 gentle adaboost in train cascade parameter 有什么区别.. -bt
我想为 book crossing 构建训练数据矩阵和测试数据矩阵数据集。但作为 ISBN 代码的图书 ID 可能包含字符。因此,我无法应用此代码(来自 tutorial ): #Create two
我找到了 JavaANPR 库,我想对其进行自定义以读取我所在国家/地区的车牌。 似乎包含的字母表与我们使用的字母表不同 ( http://en.wikipedia.org/wiki/FE-Schri
我有一个信用卡数据集,其中 98% 的交易是非欺诈交易,2% 是欺诈交易。 我一直在尝试在训练和测试拆分之前对多数类别进行欠采样,并在测试集上获得非常好的召回率和精度。 当我仅在训练集上进行欠采样并在
我打算: 在数据集上从头开始训练 NASNet 只重新训练 NASNet 的最后一层(迁移学习) 并比较它们的相对性能。从文档中我看到: keras.applications.nasnet.NASNe
我正在训练用于分割的 uNet 模型。训练模型后,输出全为零,我不明白为什么。 我看到建议我应该使用特定的损失函数,所以我使用了 dice 损失函数。这是因为黑色区域 (0) 比白色区域 (1) 大得
我想为新角色训练我现有的 tesseract 模型。我已经尝试过 上的教程 https://github.com/tesseract-ocr/tesseract/wiki/TrainingTesser
我的机器中有两个 NVidia GPU,但我没有使用它们。 我的机器上运行了三个神经网络训练。当我尝试运行第四个时,脚本出现以下错误: my_user@my_machine:~/my_project/
我想在python的tensorflow中使用稀疏张量进行训练。我找到了很多代码如何做到这一点,但没有一个有效。 这里有一个示例代码来说明我的意思,它会抛出一个错误: import numpy as
我正在训练一个 keras 模型,它的最后一层是单个 sigmoid单元: output = Dense(units=1, activation='sigmoid') 我正在用一些训练数据训练这个模型
所以我需要使用我自己的数据集重新训练 Tiny YOLO。我正在使用的模型可以在这里找到:keras-yolo3 . 我开始训练并遇到多个优化器错误,添加了错误代码以防止混淆。 我注意到即使它应该使用
将 BERT 模型中的标记化范式更改为其他东西是否有意义?也许只是一个简单的单词标记化或字符级标记化? 最佳答案 这是论文“CharacterBERT: Reconciling ELMo and BE
假设我有一个非常简单的神经网络,比如多层感知器。对于每一层,激活函数都是 sigmoid 并且网络是全连接的。 在 TensorFlow 中,这可能是这样定义的: sess = tf.Inte
有没有办法在 PyBrain 中保存和恢复经过训练的神经网络,这样我每次运行脚本时都不必重新训练它? 最佳答案 PyBrain 的神经网络可以使用 python 内置的 pickle/cPickle
我尝试使用 Keras 训练一个对手写数字进行分类的 CNN 模型,但训练的准确度很低(低于 10%)并且误差很大。我尝试了一个简单的神经网络,但没有效果。 这是我的代码。 import tensor
我在 Windows 7 64 位上使用 tesseract 3.0.1。我用一种新语言训练图书馆。 我的示例数据间隔非常好。当我为每个角色的盒子定义坐标时,盒子紧贴角色有多重要?我使用其中一个插件,
如何对由 dropout 产生的许多变薄层进行平均?在测试阶段要使用哪些权重?我真的很困惑这个。因为每个变薄的层都会学习一组不同的权重。那么反向传播是为每个细化网络单独完成的吗?这些细化网络之间的权重
我尝试训练超正方语言。我正在使用 Tess4J 进行 OCR 处理。我使用jTessBoxEditor和SerakTesseractTrainer进行训练操作。准备好训练数据后,我将其放在 Tesse
我正在构建一个 Keras 模型,将数据分类为 3000 个不同的类别,我的训练数据由大量样本组成,因此在用一种热编码对训练输出进行编码后,数据非常大(item_count * 3000 * 的大小)
关闭。这个问题需要多问focused 。目前不接受答案。 想要改进此问题吗?更新问题,使其仅关注一个问题 editing this post . 已关闭 8 年前。 Improve this ques
我是一名优秀的程序员,十分优秀!