D.The Game of Eating
题意:
一共有m道菜，n个人轮流点，一共点k道。
第i个人对第j道菜的喜爱程度(A_i)公开, 一个人点了菜所有人都可以吃到。
每个人都希望最大化自己的喜爱程度之和，求最终的点菜集合。
分析：
倒着贪心，如果最后一个人最喜欢吃的菜没被选那么他一定会选择这道菜，则其他人不会浪费机会选这道菜，他们会选择从剩下的菜中选择自己最喜欢的，以此类推，可以保证最大化每个人的收益。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 2007;
int a[N][N];
bool vis[N];
vector<int> S;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t --)
{
int n, m, k;
cin >> n >> m >> k;
S.clear();
memset(vis,0,sizeof(vis));
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
cin >> a[i][j];
for (int i = k; i >= 1; i --)
{
int x = (i - 1) % n + 1, idx = 0, fav = 0;
for (int j = 1; j <= m; j ++)
if (!vis[j] && a[x][j] > fav)
{
fav = a[x][j];
idx = j;
}
vis[idx] = 1;
S.push_back(idx);
}
sort(S.begin(), S.end());
for (auto x : S)
cout << x << " ";
cout << endl;
}
return 0;
}
E.Square
题意：
在[0,(10^9)]范围内找一个y，使得(lfloorfrac{y^2}{10^k}rfloor=x)。
分析：
枚举k，然后二分查找第一个满足 y · y >= x · (10^k)的y，然后判断x是否是(y^2)的前缀。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
LL qmi(LL m, LL k)
{
LL res = 1, t = m;
while (k)
{
if (k & 1)
res = res * t;
t = t * t;
k >>= 1;
}
return res;
}
bool check(LL mid, LL x)
{
for (int i = 0; i <= 18; i ++)
{
LL a = qmi(10, i);
LL res = mid * mid / a;
if (res == x) //判断是否是前缀
return true;
}
return false;
}
int main()
{
int t;
scanf("%d", &t);
while (t --)
{
LL x;
scanf("%lld", &x);
bool flag = false;
LL y = 0;
for (int i = 0; i <= 18; i ++)
{
LL a = qmi(10, i);
LL x2 = x * a;
LL l = 0, r = 1e9;
while (l < r)
{
LL mid = (l + r) / 2;
if (mid * mid >= x2)
r = mid;
else
l = mid + 1;
}
if (check(r, x))
{
y = r;
flag = true;
break;
}
}
if (flag)
printf("%lldn", y);
else
printf("-1n");
}
return 0;
}
F.Link with Chess Game
题意:
n个单元格，有3个不同棋子，3个棋子各有一个初始位置，Alice和Bob可轮流将一枚棋子移动到相邻的位置，若移动过后三枚棋子所在位置组成的三元组(a, b, c)之前出现过，则做出此操作的玩家输，Alice先手，问谁赢。
分析：
赛时猜的结论，二分图博弈交给队友了...不想补。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
LL t, n, r, g, b;
cin >> t;
while(t--)
{
cin >> n >> r >> g >> b;
if (((r + g + b) * n - 1) & 1)
cout << "Alice" << endl;
else
cout << "Bob" << endl;
}
return 0;
}
G.Link with Centrally Symmetric Strings
题意:
给你一个字符串，问它是否能由若干个中心对称字符串组成
S是中心对称字符串应满足：
1.S为空字符串
2.S由“o,s,x,z”组成。
3.S由两对中心对称字符夹一个中心对称字符串组成。例如：bSq∣dSp∣pSd∣qSb∣nSu∣uSn∣oSo∣sSs∣xSx∣zSz都是中心对称字符串。
分析：
可以借助manacher算法维护一个满足要求的最大前缀，更新时看以当前字母为中心的对称半径能否覆盖到维护的前缀，同时需注意剔除掉不能做对称中心的字母。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, M = 2 * N + 5;
char s[N], s2[M];
int r[M], n, m;
unordered_map<char, char> mp;
void init()
{
for (int i = 'a'; i <= 'z'; i ++)
mp[i] = 1;
mp['$'] = mp['^'] = 1;
mp['b'] = 'q';
mp['d'] = 'p';
mp['p'] = 'd';
mp['q'] = 'b';
mp['n'] = 'u';
mp['u'] = 'n';
mp['o'] = 'o';
mp['s'] = 's';
mp['x'] = 'x';
mp['z'] = 'z';
mp['#'] = '#';
}
bool check(char c)
{
return c == '#' || c == 'o' || c == 's' || c == 'x' || c == 'z';
}
bool manacher()
{
m = 0;
n = strlen(s);
s2[m ++] = '$', s2[m ++] = '#';
for (int i = 0; i < n; i ++)
s2[m ++] = s[i], s2[m ++] = '#';
s2[m ++] = '^';
for (int i = 0; i < m; i ++)
r[i] = 0;
int mid = 0, mr = 0, idx = 1;
for (int i = 1; i < m - 1; i ++)
{
if (!check(s2[i]))
{
r[i] = 0;
continue;
}
r[i] = i < mr ? min(r[2 * mid - i], mr - i) : 1;
while (s2[i - r[i]] == mp[s2[i + r[i]]])
r[i] ++;
if (i + r[i] > mr)
{
mr = i + r[i];
mid = i;
}
if (i - r[i] <= idx)
{
int r2 = i - idx;
s2[i + r2 - 1] = '$';
idx = i + r2;
i = i + r2;
}
}
return idx == m - 2;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
init();
while (t --)
{
cin >> s;
if (manacher())
cout << "Yes" << "n";
else
cout << "No" << "n";
}
return 0;
}
H.0 and 1 in BIT
题意:
给定一个长为n的只含A, B两种字符的字符串,给定Q次询问(l, r, x)表示二进制字符串x经过字符串(l, r)这段区间后变成什么。其中，A操作反转该二进制字符串（0->1,1->0），B操作将
该二进制字符串视为数字计算x = x + 1 (溢出的位舍弃)。
分析:
A操作：由于-x是x的补码，补码是原码取反加一，因此，x取反即为x = -x - 1
B操作：x = x + 1
观察上面两个操作,可以发现对于x，经过一个区间的操作过后，x = -x + a或者x = x + b。x前是是否是-1取决于是否进行奇数次A操作。至于后面的常数我们通过预处理求出来。
设我们要求的常数为f[l][r]。可以对0做一遍操作，代入上面的结论，有：
当[l， r]内A的数量为奇数时，-f[1][l - 1] + f[l][r] = f[1][r];否则，f[1][l - 1] + f[l][r] = f[1][r]。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
LL sum[N], op[N];
char s[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, t;
cin >> n >> t;
cin >> s + 1;
for (int i = 1; i <= n; i ++)
{
if (s[i] == 'A')
{
op[i] = -op[i - 1] - 1;
sum[i] = sum[i - 1] + 1;
}
else
{
op[i] = op[i - 1] + 1;
sum[i] = sum[i - 1];
}
}
LL ans = 0;
while (t --)
{
int L, R, l, r;
LL x = 0, mod = 0;
string s2;
cin >> L >> R >> s2;
for (int i = 0, j = s2.size() - 1; i < s2.size(); i ++, j --)
{
if (s2[i] == '1')
{
x += (LL)1 << j;
}
}
mod = (LL)1 << s2.size();
l = min((ans ^ L) % n + 1, (ans ^ R) % n + 1);
r = max((ans ^ L) % n + 1, (ans ^ R) % n + 1);
int d = sum[r] - sum[l - 1];
LL num = 0;
if (d & 1)
{
num = op[r] + op[l - 1];
x = -x;
}
else
num = op[r] - op[l - 1];
ans = ((x + num) % mod + mod) % mod;
for (int i = s2.size() - 1; i >= 0; i --)
{
if (ans >> i & 1)
cout << 1;
else
cout << 0;
}
cout << endl;
}
return 0;
}
I.Link with Gomoku
题意：
对一个n×m的五子棋棋盘，构造一个平局棋面。
分析：
若n为偶数，则按：
xxxxooooxxxx..
ooooxxxxoooo..
....
的形式构造，这样可以保证4个方向都不会出现连续5个相同项。
若n为奇数，则前n - 1行按前面讨论的构造，最后一行按如下形式构造：
xoxoxox...
代码:
#include <bits/stdc++.h>
using namespace std;
void output1(int n, int m)
{
for (int i = 1; i <= n; i ++)
{
char a, b;
if (i & 1)
a = 'x', b = 'o';
else
a = 'o', b = 'x';
bool flag = true;
for (int j = 1; j <= m; j ++)
{
if (flag)
cout << a;
else
cout << b;
if ((j % 4) == 0)
flag ^= 1;
}
cout << endl;
}
}
void output2(int m)
{
for (int i = 1; i <= m; i ++)
{
if (i & 1)
cout << "x";
else
cout << "o";
}
cout << endl;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n, m;
cin >> n >> m;
if (n & 1)
{
output1(n - 1, m);
output2(m);
}
else
{
output1(n, m);
}
}
return 0;
}
K.Box
题意:
有n个盒子，有的盒子上有盖子，盖子可以左右移动一位，若盒子上有盖子可以获得一定分数，求能获得的最大分数值。
分析:
首先要保证最优，无论怎么移动，盒子间的相对方向是不变的（a永远在b的左边相对的b永远在a的右边）。然后考虑dp，考虑枚举盖子的放置情况：
f[i][3]表示考虑前i个盖子，且第i个盖子的状态是0（左移）、1（不动）、2（右移）时所能获得的最大分数值。
状态的转移要考虑第i个盖子和第i - 1个盖子的位置关系，具体参考代码。
设盖子的数量为m，答案即max(f[m][0], f[m][1], f[m][2])。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
LL a[N], b[N], f[N][3];
int idx[N], m;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
if (b[i])
idx[++ m] = i;
}
if (idx[1] > 1)
f[1][0] = a[idx[1] - 1];
f[1][1] = a[idx[1]];
f[1][2] = a[idx[1] + 1];
for (int i = 1; i <= m; i ++)
{
if (idx[i] - idx[i - 1] == 1) // 相邻
{
f[i][0] = f[i - 1][0] + a[idx[i] - 1];
f[i][1] = max(f[i - 1][0], f[i - 1][1]) + a[idx[i]];
f[i][2] = max(max(f[i - 1][0], f[i - 1][1]), f[i - 1][2]) + a[idx[i] + 1];
}
else if (idx[i] - idx[i - 1] == 2) // 相隔1个
{
f[i][0] = max(f[i - 1][0], f[i - 1][1]) + a[idx[i] - 1];
f[i][1] = max(max(f[i - 1][0], f[i - 1][1]), f[i - 1][2]) + a[idx[i]];
f[i][2] = max(max(f[i - 1][0], f[i - 1][1]), f[i - 1][2]) + a[idx[i] + 1];
}
else // 相隔多个
{
LL tmp = max(max(f[i - 1][0], f[i - 1][1]), f[i - 1][2]);
f[i][0] = tmp + a[idx[i] - 1];
f[i][1] = tmp + a[idx[i]];
f[i][2] = tmp + a[idx[i] + 1];
}
}
cout << max(max(f[m][0], f[m][1]), f[m][2]);
return 0;
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
