给你两个二进制字符串
您的任务是确定最大可能的数字
如果
输入
第一行包含一个整数
每个测试用例的第一行包含两个整数
每个测试用例的第二行包含长度为
每个测试用例的第三行包含长度为
保证所有测试用例的值
赛时写的有点慢。这里主要讨论
暴力线性围护的时候,需记录对应位置字符下一次出现的地方方便跳转。
讨论
则有转移方程
#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
#define IOS \
ios::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr);
#define int long long
const int INF = 1e18;
const int mod = 998244353;
void solve()
{
int n, m;
cin >> m >> n;
string a, b;
cin >> a >> b;
vector<int> nxt0(b.size() + 2);
vector<int> nxt1(b.size() + 2);
nxt0[b.size()] = nxt1[b.size()] = INF;
int pre0 = INF, pre1 = INF;
for (int i = n; i >= 0; i--)
{
nxt0[i] = pre0;
nxt1[i] = pre1;
if (i)
{
if ((b[i - 1] & 15) == 0)
{
pre0 = i;
}
else
{
pre1 = i;
}
}
}
int k = 0;
int pos = 0;
for (auto c : a)
{
if (c == '0')
{
if (nxt0[pos] == INF)
break;
pos = nxt0[pos];
k++;
}
else
{
if (nxt1[pos] == INF)
break;
pos = nxt1[pos];
k++;
}
}
cout << k << endl;
return;
}
signed main()
{
IOS;
int t;
cin >> t;
while (t--)
{
solve();
}
system("pause");
return 0;
}
Bodya 和 Sasha 发现了一个排列
长度为
它们都在排列中选择了一个起始位置。
对局持续了
在整整
知道了博迪娅的起始位置
很快能想到最终的结果不会和博弈相关,因为两人的选择互不干扰。
所以两人都玩命想更大就行了。
最优解是从当前位置走到能到达的范围内某个分数较高的格子里面不动。注意到不一定是最大的,因为到达最大格子可能付出更沉重的代价。
但是,停留行为是一定的。
所以我们枚举停留点就行了,计算从初始点一路走到停留点停下所能得到的分数,比较出最大值就可以。
#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
#define IOS \
ios::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr);
#define int long long
const int INF = 1e18;
const int mod = 998244353;
void solve()
{
int n, k, posb, poss;
cin >> n >> k >> posb >> poss;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int j = 1; j <= n; j++)
cin >> b[j];
int anss, ansb;
vector<int> maxnb(1), maxns(1);
vector<int> dpb(n + 1), dps(n + 1);
vector<int> rb(1), rs(1);
vector<int> vis(n + 1, 0);
int _posb = posb, _poss = poss;
int maxx = -1;
while (!vis[_posb])
{
rb.push_back(b[_posb]);
vis[_posb] = 1;
maxx = max(maxx, b[_posb]);
_posb = a[_posb];
maxnb.push_back(maxx);
}
maxx = -1;
vis = vector<int>(n + 1, 0);
while (!vis[_poss])
{
rs.push_back(b[_poss]);
vis[_poss] = 1;
maxx = max(maxx, b[_poss]);
_poss = a[_poss];
maxns.push_back(maxx);
}
int pre = 0;
for (int i = 1; i < rb.size(); i++)
{
pre += rb[i];
dpb[i] = max(dpb[i - 1], k - i >= 0 ? (pre + (k - i) * maxnb[i]) : 0);
}
pre = 0;
for (int i = 1; i < rs.size(); i++)
{
pre += rs[i];
dps[i] = max(dps[i - 1], k - i >= 0 ? (pre + (k - i) * maxns[i]) : 0);
}
ansb = dpb[rb.size() - 1], anss = dps[rs.size() - 1];
if (anss > ansb)
{
cout << "Sasha" << endl;
return;
}
if (anss < ansb)
{
cout << "Bodya" << endl;
return;
}
cout << "Draw" << endl;
return;
}
signed main()
{
IOS;
int t;
cin >> t;
while (t--)
{
solve();
}
system("pause");
return 0;
}
给你一个整数
假设
如果存在多个解,你可以输出任意一个。
单元格
纯
还不如
显然这种题看样例看多了就是给自己找麻烦。
观察情况数最少的
注意考虑下面样例都有对角线,构造题一定是递推的关系,不同情况之间一定有联系。
然后逆天小题就结束了。
如果可以将数组分成
更正式地说,你必须把数组
例如,如果是
给你一个数组
输入
第一行包含一个整数
每个测试用例的第一行包含两个整数
下一行包含
接下来的每行
保证所有测试用例中
保证所有测试用例中
异或区间想前缀和已经基本属于是
考虑分片的问题。赛场上就有想到,如果区间异或
显然易证——如果区间
那么我们只需要专注区间异或结果不为
更近一步的,说明如果存在可能的分片,那么其必然可以分成三片。
设可能的分片方式为
则必然有
故问题转化成找区间
预处理前缀和时map<int,set<int>>
然后执行set::lower_bound()
就行。
auto judge = [&](int l, int r, int tar) -> bool
{
auto s1 = mp[sum[r]].lower_bound(l);
auto s2 = mp[sum[l - 1]].lower_bound(r);
if (s1 == mp[sum[r]].end() || s2 == mp[sum[l - 1]].begin())
return false;
s2--;
if (*s1 < *s2)
return true;
return false;
};
#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
#define IOS \
ios::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr);
#define int long long
const int INF = 1e18;
const int mod = 998244353;
void solve()
{
int n;
cin >> n;
int q;
cin >> q;
vector<int> a(n + 1);
vector<int> sum(n + 1);
map<int, set<int>> mp;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum[i] = sum[i - 1] ^ a[i];
mp[sum[i]].insert(i);
}
auto judge = [&](int l, int r, int tar) -> bool
{
auto s1 = mp[sum[r]].lower_bound(l);
auto s2 = mp[sum[l - 1]].lower_bound(r);
if (s1 == mp[sum[r]].end() || s2 == mp[sum[l - 1]].begin())
return false;
s2--;
if (*s1 < *s2)
return true;
return false;
};
while (q--)
{
int l, r;
cin >> l >> r;
int res = sum[l - 1] ^ sum[r];
if (!res)
{
cout << "YES" << endl;
}
else
{
if (judge(l, r, res))
{
cout << "YES" << endl;
}
else
cout << "NO" << endl;
}
}
return;
}
signed main()
{
IOS;
int t;
cin >> t;
while (t--)
{
solve();
}
system("pause");
return 0;
}
扩展
咕咕
请我喝杯咖啡吧~