D.The Game of Eating
题意:
一共有m道菜，n个人轮流点，一共点k道。
第i个人对第j道菜的喜爱程度(A_i)公开, 一个人点了菜所有人都可以吃到。
每个人都希望最大化自己的喜爱程度之和，求最终的点菜集合。
分析：
倒着贪心，如果最后一个人最喜欢吃的菜没被选那么他一定会选择这道菜，则其他人不会浪费机会选这道菜，他们会选择从剩下的菜中选择自己最喜欢的，以此类推，可以保证最大化每个人的收益。
代码:
#include
using namespace std;
const int N = 2007;
int a[N][N];
bool vis[N];
vector 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 > 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 fav)
{
fav = a[x][j];
idx = j;
}
vis[idx] = 1;
S.push_back(idx);
}
sort(S.begin(), S.end());
for (auto x : S)
cout E.Square
题意：
在[0,(10^9)]范围内找一个y，使得(lfloorfrac{y^2}{10^k}rfloor=x)。
分析：
枚举k，然后二分查找第一个满足 y · y >= x · (10^k)的y，然后判断x是否是(y^2)的前缀。
代码：
#include
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 = 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
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 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
using namespace std;
const int N = 1e6 + 5, M = 2 * N + 5;
char s[N], s2[M];
int r[M], n, m;
unordered_map mp;
void init()
{
for (int i = 'a'; i mr)
{
mr = i + r[i];
mid = i;
}
if (i - r[i] > t;
init();
while (t --)
{
cin >> s;
if (manacher())
cout 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
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 > L >> R >> s2;
for (int i = 0, j = s2.size() - 1; i = 0; i --)
{
if (ans >> i & 1)
cout I.Link with Gomoku
题意：
对一个n×m的五子棋棋盘，构造一个平局棋面。
分析：
若n为偶数，则按：
xxxxooooxxxx..
ooooxxxxoooo..
….
的形式构造，这样可以保证4个方向都不会出现连续5个相同项。
若n为奇数，则前n – 1行按前面讨论的构造，最后一行按如下形式构造：
xoxoxox…
代码:
#include
using namespace std;
void output1(int n, int m)
{
for (int i = 1; i > 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
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 > a[i];
}
for (int i = 1; i > 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 机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net
