注意题目中 字符串中只有a，b两个字符
因此只要找到左右两端点字符相同的子串，这个子串一定回文，这里不在证明
求长为偶数回文串数量，就等于求相同的两个字符，而下标奇偶性不同的数对数量，比如0， 1 两个下标都是‘a’，这是偶数回文
同理 求长度为奇数回文，等于求下标奇偶性相同的数对数量
求奇数时需要注意，因为奇偶性相同是同类，求数对数量即求组合数n*(n - 1)/ 2 最后加上每个单个的字符
偶数不需要除以2是因为奇偶性不同，不会重复
#include <iostream>
#include <cstring>
using namespace std;
#define int long long
signed main()
{
string s; cin >> s;
int a1 = 0, a2 = 0, b1 = 0, b2 = 0;
for(int i = 0; i < s.size(); i ++)
{
a1 += (s[i] == 'a' && (i & 1));
a2 += (s[i] == 'a' && !(i & 1));
b1 += (s[i] == 'b' && (i & 1));
b2 += (s[i] == 'b' && !(i & 1));
}
int res = a1 * a2 + b1 * b2;
cout << res << ' ';
res = (a1 - 1) * a1 / 2 + (a2 - 1) * a2 / 2 + (b1 - 1) * b1 / 2 + (b2 - 1) * b2 / 2;
cout << res + s.size() << '\n';
}
对于给定的下界 k k k，可以发现如下性质.
以 k = 8 k=8 k=8为例，一个二进制数的二进制位可以分为k的最高位(1000)前的和k的最高位后的.例如，16是最高位前的二进制位、4和8是最高位后的二进制位。
对于两组二进制数，可以证明，如果当前的二进制位数 u u u比k的最高位靠前，那么这两个二进制数在 u u u上的取值对答案不构成影响. 证明如下：
设其一组 A A A在 u u u的下一位上取0，另一组 B B B在 u u u的下一位上取1. 那么任意 a ∈ A , b ∈ B , a x o r b > = k . a \in A, b\in B, a \space xor \space b >= k. a∈A,b∈B,a xor b>=k. 同时，由于任两个元素的异或也要 > = k >=k >=k，这就要求 A A A组内两两异或也要符合要求. 实际上，答案的个数就是 A A A组内合法的个数+ B B B组内合法的个数.
实际上，上面的性质可以转化成如下做法.
维护一棵字典树，对于比k的最高位高的位数，它的答案等于:
左子树的答案+右子树的答案. [ 1 ] ^{[1]} [1]
这样问题就转化为，对于一棵任意位都比k的最高位低的字典树，如何维护它的答案，使得结果 > = k >=k >=k?
[ 1 ] [1] [1]如果某一棵子树没有答案，由于左右子树异或之后的答案也合法，此时如果这棵子树有儿子，就可以强行使这棵树的答案取1.
对于上述的一棵低位字典树，其对答案的贡献只能是0或2.
证明如下.
对于任意二元组，要使它们的答案大于 k k k，就一定要有k的最高位上的结果是1，也就是说，这两个数在二进制的那一位上一个是0、一个是1.
这样答案就不可能>=3. 因为这样就一定会有两个元素在k的最高位上取得相同的结果，异或值也就不可能 > = k >=k >=k.
如果找不到这样的元组，答案为0.
问题就转化为，对于给定树根的字典树，是否存在二元组的异或值 > = k >=k >=k?
这是一个比较熟悉的问题. 我们可以转化问题为，求异或的最大值是否比 k k k大. 利用字典树即可解决.
总之，对于字典树内的每个节点我们都访问了一次，最终的复杂度为 O ( n ∗ l o g ( 2 30 ) ) O(n*log(2^{30})) O(n∗log(230))
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
const int N = 300010;
int n, m, tr[N * 30][2], idx;
void add(int c)
{
int root = 0;
for (int i = 29; i >= 0; i --)
{
int cur = ((c >> i) & 1);
if (!tr[root][cur]) tr[root][cur] = ++ idx;
root = tr[root][cur];
}
}
int tot;
vector<int> res;
void dfs2(int u, int cur)
{
if (!tr[cur][0] && !tr[cur][1])
{
int root = u; int ans = 0;
for (auto c: res)
{
ans = ans * 2;
if (tr[root][!c]) ans += 1, root = tr[root][!c];
else root = tr[root][c];
}
tot = max(tot, ans);
return;
}
if (tr[cur][0])
{
res.push_back(0);
dfs2(u, tr[cur][0]);
res.pop_back();
}
if (tr[cur][1])
{
res.push_back(1);
dfs2(u, tr[cur][1]);
res.pop_back();
}
}
int dfs(int u, int k)
{
int next = (1LL << (k - 1));
if (next > m)
{
int p1 = 0, p2 = 0;
if (tr[u][0]) p1 = dfs(tr[u][0], k - 1);
if (tr[u][1]) p2 = dfs(tr[u][1], k - 1);
if (tr[u][0] && tr[u][1])
return max(1LL, p1) + max(1LL, p2);
else return p1 + p2;
}
else
{
tot = 0;
dfs2(u, u);
return (tot >= m)? 2: 0;
}
}
signed main() {
cin >> n >> m;
while (n --)
{
int x; cin >> x;
add(x);
}
int p = dfs(0, 30);
cout << (p == 0? -1: p);
}
需要记录上一步处在哪个位置
然后判断如果是同一侧移动距离就是abs（x1 - x2）
如果不同就是x1 + x2
#include <iostream>
#include <cmath>
using namespace std;
#define int long long
signed main()
{
int n; cin >> n;
char s, pres;
int x, prex;
cin >> pres >> prex;
int res = prex;
for(int i = 2; i <= n; i ++)
{
cin >> s >> x;
if(pres != s) res += x + prex;
else res += abs(prex - x);
pres = s, prex = x;
}
res += prex;
cout << res << '\n';
}
倒着思考，从终点往周围扩展，判断能否到达，把能到达的点放入队列，接着扩展
这里判断时需要注意从能到达的点往外扩展时 方向是反着的，判断能否到达需要反着判断
#include <iostream>
#include <queue>
using namespace std;
const int N = 1010;
char g[N][N];
bool st[N][N];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};
signed main()
{
int n, m; cin >> n >> m;
for(int i = 0; i < n; i ++) cin >> g[i];
int sx, sy;
// 找到终点位置
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
if(g[i][j] == 'O')
sx = i, sy = j;
queue<pair<int,int>> q;
q.push({sx, sy});
st[sx][sy] = true;
int res = 1;
while(q.size())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i = 0; i < 4; i ++)
{
int ax = x + dx[i];
int ay = y + dy[i];
if(ax < 0 || ax >= n || ay < 0 || ay >= m || st[ax][ay]) continue;
if((i == 0 && g[ax][ay] == 'D') || (i == 1 && g[ax][ay] == 'U') || (i == 2 && g[ax][ay] == 'L') || (i == 3 && g[ax][ay] == 'R'))
{
q.push({ax, ay});
st[ax][ay] = true;
res ++;
}
}
}
cout << res << '\n';
}
先按照每个人的最低分加入到总成绩，用两个数组记录，一个原始数组，一个按总成绩从大到小排序的数组
遍历每一个人，用二分在在已经排序的数组里找到比它的数的数量就是排名
这里不需要考虑原来加入的自己，因为按最高分加入一定比最低分加入高
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Node
{
int l, r;
int sum;
};
bool cmp(Node a, Node b)
{
return a.sum > b.sum;
}
signed main()
{
int n; scanf("%d", &n);
vector<Node> vec, pre;
for(int i = 0, l, r, x, sum; i < n; i ++)
{
scanf("%d %d", &l, &r);
sum = 0;
for(int j = 0; j < 5; j ++)
{
scanf("%d", &x);
sum += x;
}
sum += l;
vec.push_back({l, r, sum});
pre.push_back({l, r, sum});
}
sort(vec.begin(), vec.end(), cmp);
vector<int> res;
for(int i = 0; i < n; i ++)
{
int sum = pre[i].sum + pre[i].r - pre[i].l;
int l = 0, r = n;
while(l < r)
{
int mid = l + r >> 1;
if(vec[mid].sum <= sum) r = mid;
else l = mid + 1;
}
cout << l + 1 << '\n';
}
}
最小的天鹅数黑白配对
剩下的相同2只配对
如果剩下的是奇数 减去c
#include <iostream>
using namespace std;
#define int long long
signed main()
{
int n, m, a, b, c;
cin >> n >> m >> a >> b >> c;
if(n > m) swap(n, m);
int res = n * a;
m -= n;
res += (m / 2) * b;
if(m & 1) res -= c;
cout << res << '\n';
}
这是一个很经典虚拟源点的模板题
需要将问题转化为单源最短路问题
因为最后还需要返回，因此路程距离直接乘2
对于每个答案，相当于求虚拟源点0 到点 i 的最短距离
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define int long long
const int N = 200010;
vector<pair<int, int>> g[N];
int d[N];
bool vis[N];
signed main()
{
int n, m;
cin >> n >> m;
for(int i = 1, a, b, w; i <= m; i ++)
{
cin >> a >> b >> w;
g[a].push_back({b, w * 2});
g[b].push_back({a, w * 2});
}
for(int i = 1, x; i <= n; i ++)
{
cin >> x;
g[0].push_back({i, x});
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
for(int i = 1; i <= n; i ++) d[i] = 1e18;
d[0] = 0;
q.push({0, 0});
while(q.size())
{
int u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = true;
for(auto [v, w] : g[u])
{
if(d[v] > d[u] + w)
{
d[v] = d[u] + w;
q.push({d[v], v});
}
}
}
for(int i = 1; i <= n; i ++)
cout << d[i] << " ";
}
先把处理好的全加起来
用hh记录长度为k窗口的左端点，遍历右端点每次求出长度为k的区间中的没处理好的调料数量
每次更新res
#include <iostream>
using namespace std;
const int N = 100010;
#define int long long
int a[N], b[N];
signed main()
{
int n, k; cin >> n >> k;
for(int i = 0; i < n; i ++) cin >> a[i];
for(int i = 0; i < n; i ++) cin >> b[i];
int hh = 0, sum = 0;
for(int i = 0; i < n; i ++)
if(b[i]) sum += a[i];
// 先处理第一个窗口
for(int i = 0; i < k; i ++)
if(!b[i]) sum += a[i];
int res = sum;
for(int i = k; i < n; i ++)
{
if(!b[i - k]) sum -= a[i - k];
if(!b[i]) sum += a[i];
res = max(sum, res);
}
cout << res << '\n';
}
k和ai很大，但是数只有1e5个，很容易想到离散化
因为每次影响的只有最大值和最小值，就可以直接看 最大值 和 最小值分别对应的数量哪个小
每次用k减去 那个小的，维护一个双指针，直到k小于0，或者双指针相遇
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define int long long
map<int,int> mp;
signed main()
{
int n, k, x; scanf("%lld %lld",&n, &k);
vector<int> vec;
for(int i = 0; i < n; i ++)
{
scanf("%lld", &x);
if(!mp.count(x)) vec.push_back(x);
mp[x] ++;
}
sort(vec.begin(), vec.end());
int hh = 0, tt = vec.size() - 1;
while(hh < tt)
{
int l = mp[vec[hh]];
int r = mp[vec[tt]];
if(l < r)
{
int num = vec[hh + 1] - vec[hh];
int cnt = l;
if(k >= cnt * num)
{
k -= cnt * num;
mp[vec[hh + 1]] += mp[vec[hh]];
hh ++;
}
else
{
int t = k / cnt;
k -= t * cnt;
int res = vec[tt] - vec[hh] - t;
cout << res << '\n';
return 0;
}
}
else
{
int num = vec[tt] - vec[tt - 1];
int cnt = r;
if(k >= cnt * num)
{
k -= cnt * num;
mp[vec[tt - 1]] += mp[vec[tt]];
tt --;
}
else
{
int t = k / cnt;
k -= t * cnt;
int res = vec[tt] - t - vec[hh];
cout << res << '\n';
return 0;
}
}
}
cout << 0 << '\n';
}
#include <iostream>
using namespace std;
#define int long long
int val[] = {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 4};
signed main()
{
int n;cin >> n;
// kong ge
int res = n - 1;
while(n --)
{
string s; cin >> s;
for(int i = 0; i < s.size(); i ++) res += val[s[i] - 'a'];
}
cout << res << '\n';
}
有点极限，洛谷需要开O2优化
如果问题缩减到1e6，由于y是单调不减的，dp跑一遍就好
但是现在问题是1e9的，可以考虑离散化，对于每个机关(x, y)，维护y, y+1, y+2，即把这三项加入要离散化的序列中，随后跑一遍dp即可.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e6 + 5;
const int mod = 998244353;
int n, m, k;
int dp[N][4], f[N][4];
map<int, int> rev;
int main() {
//freopen("parkour3.in", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m >> k;
vector<pair<int, int>> res;
rev[m] = 1, rev[1] = 1;
for (int i = 0; i < k; i ++) {
int u, v; cin >> u >> v;
res.push_back({u, v});
for (int j = v; j <= v + 2; j ++)
rev[j] = 1;
}
int cnt = 0;
for (auto [a, b]: rev) {
rev[a] = ++ cnt;
}
for (auto c: res) {
int a = c.first, b = c.second;
f[rev[b]][a] = true;
}
dp[1][1] = true;
int du = rev[m];
for (int i = 1; i <= du; i ++) {
for (int j = 1; j <= n; j ++) {
if (!f[i][j])
dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;
else {
dp[i + 1][max(1, j - 1)] = (dp[i + 1][max(1, j - 1)] + dp[i][j]) % mod;
dp[min(du, i + 2)][j] = (dp[min(du, i + 2)][j] + dp[i][j]) % mod;
dp[i + 1][min(n, j + 1)] = (dp[i + 1][min(n, j + 1)] + dp[i][j]) % mod;
}
}
}
for (int i = 1; i <= n; i ++)
cout << dp[du][i] << '\n';
return 0;
}
/*
all right,
but m8 tle?
*/
华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o
所有题目均有五种语言实现。C实现目录、C++实现目录、Python实现目录、Java实现目录、JavaScript实现目录题目n行m列的矩阵，每个位置上有一个元素你可以上下左右行走，代价是前后两个位置元素值差的绝对值.另外，你最多可以使用一次传送阵(只能从一个数跳到另外一个相同的数)求从走上角走到右下角最少需要多少时间。输入描述：第一行两个整数n,m，分别代表矩阵的行和列。后面n行，每行m个整数，分别代表矩阵中的元素。输出描述：一个整数，表示最少需要多少时间。
昨晚看到IDEA官推宣布IntelliJIDEA2023.1正式发布了。简单看了一下，发现这次的新版本包含了许多改进，进一步优化了用户体验，提高了便捷性。至于是否升级最新版本完全是个人意愿，如果觉得新版本没有让自己感兴趣的改进，完全就不用升级，影响不大。软件的版本迭代非常正常，正确看待即可，不持续改进就会慢慢被淘汰！根据官方介绍：IntelliJIDEA2023.1针对新的用户界面进行了大量重构，这些改进都是基于收到的宝贵反馈而实现的。官方还实施了性能增强措施，使得Maven导入更快，并且在打开项目时IDE功能更早地可用。由于后台提交检查，新版本提供了简化的提交流程。IntelliJIDEA
目录1. 研究范围定义2. 流程中台市场分析3. 厂商评估：微宏科技4. 入选证书 1. 研究范围定义近年来，随着外部市场环境快速变化、客户需求愈发多样，企业逐渐意识到，自身业务需要更加敏捷、高效，具备根据市场需求快速迭代的能力。业务流程的自动化能够帮助企业实现业务的敏捷高效，因此受到越来越多企业的关注。企业的“自动化武器库”品类丰富，包括低/零代码平台、RPA、BPM、AI等。企业可以使用多项自动化工具，但结果往往是各项自动化工具处于各自的“自动化烟囱”之中，仅能实现碎片式自动化。例如，某企业的IT团队可能在使用低代码平台、财务团队可能在使用RPA、呼叫中心则可能在使用聊天机器人。自动
自从2019年OpenApplicationModel诞生以来，KubeVela已经经历了几十个版本的变化，并向现代应用程序交付先进功能的方向不断发展。最近，KubeVela完成了向CNCF孵化项目的晋升，标志着社区的发展来到一个新的里程碑。今天，KubeVela社区内活跃着大量来自全球的开发者，共同推动KubeVela项目的落地和发展。在即将开幕的KubeCon+CloudNatvieConEurope2023上，我们惊喜地发现，连续3天，KubeVela项目的贡献者、企业用户和来自阿里云的核心维护者，将从不同角度展对KubeVela项目的分享。让我们先睹为快！🎙️BuildingaPlat
最近更新的博客华为OD机试-卡片组成的最大数字（Python）|机试题算法思路华为OD机试-网上商城优惠活动（一）（Python）|机试题算法思路华为OD机试-统计匹配的二元组个数（Python）|机试题算法思路华为OD机试-找到它（Python）|机试题算法思路华为OD机试-九宫格按键输入（Python）|机试算法备考思路华为OD机试-身高排序（Python）|备考思路使用说明参加华为od机试，一定要注意不要完全背诵代码，需要理解之后模仿写出，通过率才会高。华为OD清单查看地址：blog.csdn.net/hihell/catego
目前6月DAMA-CDGP数据治理认证考试开放报名地区有：北京、上海、广州、深圳、长沙、呼和浩特。目前南京、济南、西安、杭州等地区还在接近开考人数中，打算参加6月考试的朋友们可以抓紧时间报名啦！！！5月初，DAMA-CDGA/CDGP数据治理认证考前班也即将开班啦！报名从速！！！DAMA认证为数据管理专业人士提供职业目标晋升规划，彰显了职业发展里程碑及发展阶梯定义，帮助数据管理从业人士获得企业数字化转型战略下的必备职业能力，促进开展工作实践应用及实际问题解决，形成企业所需的新数字经济下的核心职业竞争能力。DAMA是数据管理方面的认证，帮助数据从业者提升数据管理能力。CDGP数据治理专家认证属于
最近更新的博客【华为OD机试模拟题】用C++实现-最多获得的短信条数（2023.Q1））文章目录最近更新的博客使用说明删除指定目录题目输入输出示例一输入输出说明Code使用说明参加华为od机试，一定要注意不要完全背诵代码，需要理解之后模仿写出，通过率才会高。华为OD清单查看地址：https://blog.csdn.net/hihell/catego
这是一道简单题题目来自：https://leetcode.cn/problems/two-sum/题目给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。提示：22nums.length104−109−109nums[i]109−109−109target109只会存在一个有效答案进阶：你可以想出一个时间复杂度小于O(n2)O(n^2)O(n2)的算法吗？示例1：输入：nums=[2,7,11,15],targe
InternetDownloadManager介绍2023最佳下载利器。InternetDownloadManager(简称IDM)是一款Windows平台功能强大的多线程下载工具，国外非常受欢迎。支持断点续传，支持嗅探视频音频，接管所有浏览器，具有站点抓取、批量下载队列、计划任务下载，自动识别文件名、静默下载、网盘下载支持等功能。一款下载器软件，也可以叫它网页嗅探下载工具可以理解为和迅雷差不多，但是没有迅雷那么多广告，而且功能也更加强大（ps：我也是不久前知道迅雷可以下载网页的视频了）。这是一款互联网下载管理器，看着名字挺长的，但它还有一个简称，你一定知道：IDM，在很多论坛技术贴中被称为H