题目链接
由易到难为：IE，KFD，HG
I. Link with Gomoku
仿照样例构造即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <bits/stdc++.h>
using namespace std;
int t;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> t;
while(t--)
{
int n,m;
cin >> n >> m;
if(n == 1 && m == 1)
{
cout << 'x' << '\n';
}else
{
if(n & 1)
{
char temp = 'x';
for(int i = 1;i < n;++i)
{
if(i & 1)
{
temp = 'x';
}else
{
temp = 'o';
}
for(int j = 1;j <= m;++j)
{
if(j % 4 == 1)
{
if(temp == 'x')
temp = 'o';
else
temp = 'x';
}
cout << temp;
}
cout << '\n';
}
for(int i = 1;i <= m;++i)
{
if(i & 1)
cout << 'x';
else
cout << 'o';
}
cout << '\n';
}else
{
char temp = 'x';
for(int i = 1;i <= n;++i)
{
if(i & 1)
{
temp = 'x';
}else
{
temp = 'o';
}
for(int j = 1;j <= m;++j)
{
if(j % 4 == 1)
{
if(temp == 'x')
temp = 'o';
else
temp = 'x';
}
cout << temp;
}
cout << '\n';
}
}
}
}
}
|
E. Square
由于数据范围的限制，可以对
枚举所有可能的
，之后暴力查看对于给定的
是否有满足条件的 即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <bits/stdc++.h>
using namespace std;
int t;
typedef long long ll;
ll x;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> t;
while(t--)
{
cin >> x;
ll ans = -1,l = 10;
for(int i = 1;i <= 9 && ans == -1;++i)
{
if(i != 1)
{
l *= 10;
}
ll cur_ans = sqrt(x * l);
if(((cur_ans * cur_ans) / l < x) && (cur_ans + 1) * (cur_ans + 1) / l == x)
{
ans = cur_ans + 1;
}else if(cur_ans * cur_ans / l == x)
{
ans = cur_ans;
}
}
cout << ans << endl;
}
}
|
K. Box
线性dp， 分别表示
处 前移， 处 不移动， 处 后移的最大值，对于最初没有 的地方分类讨论即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll dp[N][3];
ll a[N],b[N];
int main()
{
ios::sync_with_stdio(0);
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];
}
dp[0][0] = 0,dp[0][1] = -1e18,dp[0][2] = -1e18;
for(int i = 1;i <= n;++i)
{
if(b[i])
{
dp[i][0] = a[i - 1] + dp[i - 1][0];
dp[i][1] = a[i] + max(dp[i - 1][0],dp[i - 1][1]);
dp[i][2] = a[i + 1] + max(max(dp[i - 1][0],dp[i - 1][1]),dp[i - 1][2]);
}else
{
dp[i][0] = max(dp[i - 1][1],dp[i - 1][0]);
dp[i][1] = dp[i - 1][2];
dp[i][2] = -1e18;
}
}
cout << max(dp[n][0],dp[n][1]) << endl;
}
|
F. Link with Chess Game
本题可看作在一个
的立方体内，从
开始移动，每次只能移动一格距离，最先到达先前到达过状态的人输，由于每次只能移动距离一，因此每次移动都会改变
中任意一维的奇偶性于是可以转化成类似二分图最大匹配的问题，当
为偶数时，所有点都位于最大匹配上，先手必胜；当
为奇数时，数量较少的一部分位于最大匹配，数量较多的另一部分去掉一个点后最大匹配不变，此时若
位于数量较多的部分则先手必输，否则先手必胜，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin >> t;
while(t--)
{
int n,r,g,b;
cin >> n >> r >> g >> b;
if(n % 2 == 0)
{
cout << "Alice\n";
}else
{
if((r + g + b) % 2 == 1)
{
cout << "Bob\n";
}else
{
cout << "Alice\n";
}
}
}
}
|
D. The Game of Eating
贪心题，假设当前是最后一个人，那么他一定会在剩下的所有菜中挑自己最爱吃的，那么前一个人为了不浪费，应该在除去这道菜的菜里选自己最爱吃的，以此类推，每次拿当前人最喜欢的菜，然后将这道菜对所有人的权重置0，从
模拟一遍即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[2010][2010];
bool cmp(ll x,ll y)
{
return x > y;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;
cin >> t;
while(t--)
{
int n,m,k;
cin >> n >> m >> k;
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= m;++j)
{
cin >> a[i][j];
}
}
vector<int>ans;
for(;k >= 1;--k)
{
int cur = k % n;
if(!cur)
cur = n;
int mx = 0,pos = 0;
for(int j = 1;j <= m;++j)
{
if(mx < a[cur][j])
{
mx = a[cur][j];
pos = j;
}
}
ans.push_back(pos);
for(int i = 1;i <= n;++i)
a[i][pos] = 0;
}
sort(ans.begin(),ans.end());
for(auto x:ans)
cout << x << " ";
cout << "\n";
}
}
|
H. 0 and 1 in BIT
操作在无符号整型中表示为 ，在有符号整型中表示为
，由于最终只保留 位没有超过
表示范围，可以考虑从有符号整型角度出发，最后保留 位即可。
对于 使得 ，当已经经历奇数次 操作时， 相当于 ， 偶数次时相当于 ；考虑能否用前缀和预处理使得每次可直接查询 区间内的等价操作 ，最终答案直接使 加上 即可。
手动操作几次后发现实际情况还到 为止
的奇偶性有关，因为我们开始操作时作用在 上的 数量为 ，而数组 记录的是 整个过程的操作。因此 为奇数时应减去 。同时，若 内 为奇数，最后答案还要取反。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll pre[N];
ll add[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n,q;
cin >> n >> q;
string s;
cin >> s;
for(int i = 1;i <= n;++i)
{
add[i] = add[i - 1];
pre[i] = pre[i - 1];
if(s[i - 1] == 'A')
{
add[i] ^= 1;
}
else
{
if(add[i])
{
pre[i]--;
}else
{
pre[i]++;
}
}
}
ll ans = 0;
for(int i = 1;i <= q;++i)
{
unsigned long long l,r;
string x;
cin >> l >> r >> x;
int L = min((l ^ ans) % n + 1,(r ^ ans) % n + 1);
int R = max((l ^ ans) % n + 1,(r ^ ans) % n + 1);
ll mx = 1ll << x.length();
ll cur = 0;
for(int i = 0;i < x.length();++i)
{
if(x[i] == '1')
{
cur += (1ll << ((ll)x.length() - i - 1));
}
}
if(!add[L - 1])
{
ans = (cur + pre[R] - pre[L - 1]) & (mx - 1);
}else
{
ans = (cur + pre[L - 1] - pre[R]) & (mx - 1);
}
if(add[L - 1] ^ add[R])
{
ans = (mx - 1) - ans;
}
ll temp = ans;
string out;
while(out.size() < x.size())
{
if(temp & 1)
{
out = out + "1";
}else
{
out = out + "0";
}
temp /= 2;
}
reverse(out.begin(), out.end());
cout << out << "\n";
}
}
|