1001 Alice Game
题意：
起初有n个物品，玩家可以有如下操作：
①若该堆物品数量小于等于k，全部拿走。
②若该堆物品数量大于k，则只能选择拿走k个物品，并将剩余物品分成不为空的两堆。
Alice先手，问谁必胜。
分析：
打表可知当n % (4 * k + 2) == k + 1时Alice必败，其他时候必胜。
打表代码：
#include
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
LL f[N];
int sg(int x, int k)
{
if (f[x] != -1)
return f[x];
set S;
if (x 0)
S.insert(sg(0, k));
else
{
for (int i = 2; i 代码：
#include
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n, k;
cin >> k >> n;
if ((n % (4 * k + 2)) == k + 1)
cout 1002 Binary Number
题意:
给定一个01串，有k次操作，每次选择一个区间将其翻转，求k次操作后的最大结果。
分析:
最高位一定是1。
①n = 1：k为奇数则输出0，k为偶数则输出1
②n > 1：设连续0的段数为m。显然要让结果最大，要尽可能将高位的0翻转。
k
k ≥ m：特别的当m = 0，k = 1时将最后一位变为0。其他情况，我们先将m段0翻转为1，然后考虑对较低的位去操作，若k – m是偶数则翻转最后一位k – m次，因此不影响结果；若k – m是奇数可以先翻转最低位一次，再翻转次低位一次，然后将次低位和最低位一起翻转，剩下的操作为偶数不影响结果。综上除了特殊情况其他均输出n个1。
代码:
#include
using namespace std;
typedef long long LL;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
LL k;
cin >> n >> k;
string s;
cin >> s;
if (n == 1)
{
if (k & 1)
cout 1004 Card Game
题意:
给你n个堆,起初第一个堆放了k个东西,下面大上面小,其它堆都是空的,需要通过其它空堆的中转作用将k个东西从第一个堆全部放到第二个堆上(也是下面大上面小),问最多可以成功转移的k的个数是多少。
分析：
找规律。发现f[n] = f[n – 1] * 2 + 1 => f[n] = (2^{n – 1}) – 1。
代码:
#include
using namespace std;
typedef long long LL;
int mod = 998244353;
LL qmi(LL m, LL k)
{
LL res = 1, t = m;
while (k)
{
if (k & 1)
res = res * t % mod;
t = t * t % mod;
k >>= 1;
}
return res;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
cout 1007 foreverlasting and fried-chicken
题意：
给你一个无向图，求出如下图形的数量。
分析：
枚举度大于等于6的点和度大于等于4的点，分别设为u，v。设与u相连的结点数为cnt，u和v均相连的结点数为cnt2，则u，v能组成的目标图形数为(C_{cnt2}^4·C_{cnt – cnt2}^2)。倘若暴力枚举cnt2会是(O^3)的复杂度，因此考虑用bitset优化。可以用bitset维护一个邻接矩阵g，cnt = g[u].count(),cnt2 = (g[u] & g[v]).count()。
代码:
#include
using namespace std;
typedef long long LL;
const int N = 1010, mod = 1e9 + 7;
bitset g[N];
LL f[N], f2[N];
LL qmi(LL m, LL k)
{
LL res = 1, t = m;
while (k)
{
if (k & 1)
res = res * t % mod;
t = t * t % mod;
k >>= 1;
}
return res;
}
void init()
{
f[0] = f2[0] = 1;
for (int i = 1; i > t;
init();
while (t --)
{
int n, m;
cin >> n >> m;
for (int i = 1; i > a >> b;
g[a][b] = g[b][a] = 1;
}
LL res = 0;
for (int i = 1; i 1009 String Problem
题意：
取k个子串，每个子串只包含一种字母，问子串长度之和减去k的最大值是多少。
分析：
双指针枚举满足条件的子串的最长长度，其对答案的贡献为子串长度减1。
代码：
#include
using namespace std;
const int N = 27;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
string s;
cin >> s;
int res = 0;
for (int i = 0; i 1010 Klee likes making friends
题意：
给定n个元素，每个元素有一个权值，要求每连续m个元素至少要有两个元素被选，求所选元素权值之和的最小值。
分析：
考虑dp。
f[i][j]表示所选方案中最后一个在i倒数第二个在j的权值之和的最小值，且i – j
但这样定义状态i×j最大有1e8级别，会MLE。考虑优化，首先很容易想到j可以用相对距离i – j来描述。其次，由于我们每次考虑一个长度为m的区间，因此第一维可以用i % m表示。新的状态可以定义为：f[k][l]表示所选方案中最后一个元素所在位置为k（k = i % m）倒数第二个元素与倒数第一个元素的相对距离为l（l = i – j）的权值之和的最小值。
代码：
#include
using namespace std;
const int N = 2010, M = 20010;
int f[N][N], Min[N][N], pos[M];
int a[M];
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;
for (int i = 1; i > a[i];
pos[i] = i % m;
}
for (int i = 0; i = 1; j --)
{
f[pos[i]][i - j] = a[i] + a[j];
Min[pos[i]][i - j] = min(Min[pos[i]][i - j - 1], f[pos[i]][i - j]);
}
}
for (int i = m + 1; i = i - m + 1; j --)
{
f[pos[i]][i - j] = a[i] + Min[pos[j]][j - (i - m)];
Min[pos[i]][i - j] = min(Min[pos[i]][i - j - 1], f[pos[i]][i - j]);
}
}
int res = 0x3f3f3f3f;
for (int i = n - m + 2; i = n - m + 1; j --)
{
res = min(res, f[pos[i]][i - j]);
}
}
cout 1011 SPY finding NPY
题意：
n个人，IQ值为n的全排列，先取前k个人的最大IQ值m，之后从[k + 1, n – 1]位置内去选第一个大于m的人否则选第n个人，问选到IQ为n的概率最大时k的最小值。
分析：
设选到的人在位置a，且在[1, a – 1]内，IQ最大的人在[1, k]的概率：(frac{k}{n(a – 1)})。则选到IQ为n的概率为：(frac{1}{n}sum_{i=k+1}^{n}{frac{k}{(i – 1)}} = frac{k}{n}sum_{i=k}^{n-1}{frac{1}{i}})。可以用前缀和预处理出(sum{frac{1}{i}})，然后枚举k取个min即可。
代码：
#include
using namespace std;
const int N = 1e4 + 5;
double f[N];
struct Ans
{
int k;
double p;
};
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
memset(f, 0, sizeof f);
for (int i = 1; i 机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net
