牛客多校2
D.The Game of Eating
题意:
有\(n\)个人，\(m\)种菜，从\(1\)开始轮流点菜，一共点\(k\)道，\(n\)点完轮到\(1\)，直到点完，点过的菜其他人不能再点。第\(i\)个人对第\(j\)道菜有\(A_{i,j}\)的喜好度，每个人都想让自己对所有已选的菜的喜好度总和最大，他们能彼此看到对菜的喜好度，问最后点了的菜有什么？
思路：
假设第一个人有一道菜是他喜欢的菜里面最大的，这道菜也是别人菜里面最大的，那么他肯定不选这个，选一个次大的。这样，我们不仿从第\(k\)个人开始选，这样前面的人的最大就会被选走了，倒序模拟一遍即可。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e3 + 5, M = 2e3 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--) {
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> a(n + 1, vector<int>(m + 1));
vector<priority_queue<pair<int, int>>> q(n + 1);
vector<bool> c(m + 1);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> a[i][j];
q[i].emplace(a[i][j], j);
}
}
int now = (k - 1) % n + 1;
vector<int> ans;
for(int i = 1; i <= k; i++) {
while(c[q[now].top().second]) q[now].pop();
ans.emplace_back(q[now].top().second);
c[q[now].top().second] = true;
now--;
if(now == 0) {
now = n;
}
}
sort(ans.begin(), ans.end());
for(int i = 0; i < ans.size(); i++) {
cout << ans[i] << " \n"[i + 1 == ans.size()];
}
}
return 0;
}
E.Square
题意：
给出一个\(x(1\leq x\leq10^9)\)，在\(x\)的数位后拼接数字，使得他存在一个\(y\)满足\(0\leq y\leq 10^9\)且\(y^2=x\)
思路：
由于\(y\)的范围，这就限定了\(x\leq10^{18}\)，这样我们只需要枚举拼接的数位个数即可，假设\(x=123\)，拼接了四位，那么结果的范围就是\([1230000, 1239999]\)，可能的\(y\)就在\([\sqrt{1230000}, \sqrt{1239999}]\)对这一部分二分，二分数的检查头\(3\)位即可，\(x\)有多少位就检查多少位即可。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;
using mint = ll;
mint cal(int x, int y) {
mint ret = 1;
for(int i = 1; i <= y; i++) {
ret *= x;
}
return ret;
}
mint geth(int len) {
mint ret = 0;
while(len--) {
ret = ret * 10 + 9;
}
return ret;
}
void work() {
mint x;
cin >> x;
if(x == 0) {
cout << 0 << "\n";
return;
}
int d = (int)log10(x) + 1;
for(int i = 0; i <= 19 - d; i++) {
mint b = cal(10, i);
if(x > (mint)1e18 / b) {
break;
}
mint l = x * b, r = l == (mint)1e18 ? l : l + geth(i);
mint lsq = ceil(sqrt(l)), rsq = (int)sqrt(r);
while(lsq <= rsq) {
mint mid = (lsq + rsq) / 2;
mint v = mid * mid;
while((int)log10(v) + 1 > d) {
v /= 10;
}
if(v == x) {
cout << mid << "\n";
return;
}
if(v > x) {
rsq = mid - 1;
} else {
lsq = mid + 1;
}
}
}
cout << -1 << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--) {
work();
}
return 0;
}
G.Link with Centrally Symmetric Strings
题意：
字符\(s,o,x,z\)是自我中心对称的，字符\(\{u, n \},\{q, b\},\{d,p\}\)是对应中心对称的。给出一个字符串， 确定是否是由若干个中心对称的串首尾拼接起来的。
思路：
从头找，每找到一个中心对称串，就把他删去，这样操作下去，可以删空原串就是符合题意的。
判断是否是中心对称串可以把字符看成对应对称字符，然后就是求回文串，可以用哈希解决，也可以用manacher算法
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e6 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;
string strs = "bqdpunosxz#";
string strt = "qbpdnuosxz#";
map<char, char> inv;
set<char> set1;
string trans(const string &s) {
string ret;
ret += '#';
for(char c : s) {
ret += c;
ret += '#';
}
return ret;
}
string s;
int p[N];
void work() {
cin >> s;
for(char c : s) {
if(!set1.count(c)) {
cout << "NO" << "\n";
return;
}
}
s = " " + trans(s);
int mid = 0, mr = 0, l = 1, n = (int)s.size() - 1;
for(int i = 1; i <= n; i++) {
p[i] = mr >= i ? min(mr - i + 1, p[2 * mid - i]) : s[i] == inv[s[i]];
while(s[i - p[i]] == inv[s[i + p[i]]]) p[i]++;
if(l <= i && i - p[i] + 1 <= l) {
l = 2 * i - l + 1;
}
if(i + p[i] - 1 > mr) {
mr = i + p[i] - 1;
mid = i;
}
}
if(l == n + 1) cout << "YES" << "\n";
else cout << "NO" << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for(int i = 0; i < strs.size(); i++) {
inv[strs[i]] = strt[i];
inv[strt[i]] = strs[i];
set1.emplace(strs[i]);
set1.emplace(strt[i]);
}
int tt;
cin >> tt;
while(tt--) {
work();
}
return 0;
}
H.0 and 1 in BIT
给定一个对二进制数的操作序列，其中\(A\)代表然这个二进制数取反，\(B\)代表让这个数\(+1\)
给出若干操作，每个操作给出\(L,R,X\)，问对\(X\)顺序做\([L,R]\)的结果是什么？
取反操作可以看成补码的操作，有~x == -x - 1
这么一来只需要快速查询区间操作和，可以用倍增实现，也可以用前缀和
下面是一个前缀和的实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
const int N = 1e6 + 5;
int n, q;
string s;
struct ele {
int fu, val;
ele operator+(const ele &x) const {
ele ret;
if(x.fu) {
ret.fu = fu ^ x.fu;
ret.val = -val + x.val;
} else {
ret.fu = fu;
ret.val = val + x.val;
}
return ret;
}
ele operator-(const ele &x) const {
ele ret;
ret.fu = fu ^ x.fu;
ret.val = val - (ret.fu ? -x.val : x.val);
return ret;
}
}sum[N];
signed main() {
#ifdef stdjugde
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q >> s;
s = "?" + s;
//ele(fu, value)
for(int i = 1; i <= n; i++) {
if(s[i] == 'A') sum[i] = sum[i - 1] + (ele){1, -1};
else sum[i] = sum[i - 1] + (ele){0, 1};
}
auto trans = [&](int l, int r, ll ans) -> tuple<int, int> {
int x = (ans ^ l) % n + 1ll;
int y = (ans ^ r) % n + 1ll;
return {min(x, y), max(x, y)};
};
auto _2to10 = [&](string str) -> ll {
ll ret = 0;
reverse(str.begin(), str.end());
for(int i = 0; i < str.size(); i++) {
if(str[i] == '1') {
ret += 1ll << i;
}
}
return ret;
};
auto _10to2 = [&](ll x, int len) {
string ret;
for(int i = 0; i < len; i++) {
ret += '0' + (x & 1ll);
x >>= 1ll;
}
reverse(ret.begin(), ret.end());
return ret;
};
ll ans = 0;
while(q--) {
int l, r;
cin >> l >> r;
tie(l, r) = trans(l, r, ans);
string str;
cin >> str;
ans = _2to10(str);
ele res = sum[r] - sum[l - 1];
if(res.fu) ans = -ans;
ans += res.val;
string anss = _10to2(ans, str.size());
cout << anss << "\n";
ans = _2to10(anss);
}
return 0;
}
K.Box
题意：
有\(n\)个盒子，一开始每个盒子上面可能有盖子，对于每个盖子可以将他左移一格或右移一格或原地不动，每个盒子有权值\(a_{i}\)，有盖子的盒子可以获得其权值，问最多可以获得多少权值？
思路：
每个位置有\(4\)个状态：取左边位置的盖子，取当前位置的盖子，取后一个位置的盖子，没有盖子
每个盖子有\(3\)个状态：到左边去，原地不动，到右边去
对盖子dp是比较好实现的，因为有一个重要的性质：盖子的相对顺序不改变一定可以获得最优的结果
所以对于第\(i\)个盖子只需要放的比第\(i - 1\)个后就可以了
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5, M = 2e5 + 5, inf = 0x3fffffff;
const long long INF = 0x3fffffffffffffff, mod = 998244353;
int n, a[N], b[N];
ll dp[N][3];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
vector<int> vec;
for (int i = 1; i <= n; i++) {
cin >> b[i];
if(b[i]) vec.emplace_back(i);
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j < 3; j++) {
dp[i][j] = -INF;
}
}
if (vec[0] > 1) {
dp[0][0] = a[vec[0] - 1];
}
dp[0][1] = a[vec[0]];
if (vec[0] < n) {
dp[0][2] = a[vec[0] + 1];
}
for (int i = 1; i < vec.size(); i++) {
for (int j = 0; j < 3; j++) {
if (1 <= vec[i] + j - 1 && vec[i] + j - 1 <= n) {
for (int k = 0; k < min(vec[i] - vec[i - 1] + j, 3); k++) {
if (1 <= vec[i - 1] + k - 1 && vec[i - 1] + k - 1 <= n) {
dp[i][j] = max(dp[i][j], dp[i - 1][k] + a[vec[i] + j - 1]);
}
}
}
}
}
ll ans = 0;
for (int i = 0; i < 3; i++) {
ans = max(ans, dp[(int)vec.size() - 1][i]);
}
cout << ans << endl;
return 0;
}