题目大意：
有一个n*m的棋盘，开局时棋子在左下角，两个玩家轮流移动，每次只能向上或向右移动奇数个格子，最后不能移动的玩家就输了。
思路：
由于每个人每次只能移动奇数个格子，我们可以直接移动最大奇数格子数，所以第一个玩家Burenka想赢的话，一定是在第三轮赢得比赛。
当n和m同为偶数时，最少2轮结束游戏，Tonya赢
当n和m同为奇数时，最少4轮结束游戏，Tonya赢
当n和m奇偶性不同时，最少3轮结束游戏，Burenka赢
AC Code
1
2
3
4
5
6
7
8
9
10
11
| void solve()
{
int n,m;
cin >> n >> m;
string a = "Burenka";
string b = "Tonya";
if ((n % 2 == 0 && m % 2 == 0) || (n % 2 == 1 && m % 2 == 1))
cout << b << endl;
else cout << a << endl;
}
|
题目大意：
给定两个数n,k，是否能用1~n所有的数组成2n个数对{a,b}，满足(a+k)*b能被4整除。
如果满足条件则输出YES后输出全部结果，如果不满足条件则输出NO。
思路1：
要想满足条件，则一定要有2n个数对。
分类讨论：
-
k为奇数时，(a+k) * b为偶数*偶数，则能被4整除。
-
k为偶数时
1). k能被4整除：只要a和b其中一个有一个奇数，就不能满足(a + k) * b能被4整除，所以输出NO
2). k不能被4整数：则只要给每个奇数分配一个偶数就可以，b能被4整除时，a为奇数；a+k能被4整除时，b为奇数。
AC Code
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
| void solve()
{
int n,k;
cin >> n >> k;
if (n == 2 && k == 0)
{
puts("NO");
return;
}
if (k % 4 == 0)
{
puts("NO");
return;
}
if (k & 1)
{
puts("YES");
for (int i = 1;i <= n;i += 2)
printf("%lld %lld\n",i,i + 1);
}
else
{
puts("YES");
for (int i = 2;i <= n;i += 4)
printf("%lld %lld\n",i,i - 1);
for (int i = 3;i <= n;i += 4)
printf("%lld %lld\n",i,i + 1);
}
}
|
思路2：
要想满足条件，则一定要有2n个数对。
直接枚举相邻数对{1,2}、{3,4}…{n - 1,n}。
对于每个数对{x,y}，如果(x + k) * y能被4整除，则添加进答案，否则如果(y + k) * x能被4整除，则添加进答案，如果都不能则不添加。
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void solve()
{
int n,k;
cin >> n >> k;
vector<PII> ans;
for (int i = 1;i <= n;i += 2)
{
int a = i,b = i + 1;
int x = (a + k) * b,y = (b + k) * a;
if (x % 4 == 0) ans.push_back({a,b});
else if (y % 4 == 0) ans.push_back({b,a});
}
if (ans.size() == n / 2)
{
puts("YES");
for (auto it:ans)
cout << it.first << ' ' << it.second << '\n';
}
else
puts("NO");
}
|
题目大意：
有n名运动员参加比赛，标号为1~n。第i名运动员的实力是a[i] (1 <= a[i] <= n)。每个运动员的实力都是不同的。
一开始，运动员按标号从小到大排成一列，第一位为1号运动员。
每一轮比赛，队头的两个人记性格斗，赢的人变成队头，输的人排到队尾。
q次询问，每次询问给出i和k，问i号运动员在前k次比赛中赢了几场。
思路：
当某个人的能量为n时，则无人能赢他，所以我们先找到能量最大的人，记为max。
所以出现在max后面的人，都没有赢的机会。
先初始化每个人第一次能赢的场次和最后一次能赢的场次。
对于每次询问，可以分类讨论：
选手i在max后面，则能赢的场次为0
- 如果k小于选手i第一次赢需要耗费的场次，则能赢的场次为0
- 如果选手i第一次赢需要耗费的场次为0，则说明他没赢过，最后赢的场次为0
- 如果k大于选手i最后一次赢得场次，则他能赢的场次为 最后一次赢-第一次赢 + 1
- 如果k小于选手i最后一次硬的场次，则他能赢的场次为 k - 第一次赢 +1
- 如果选手i为max，则他能赢的场次为 k - 第一次赢 + 1
AC Code
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
| void solve()
{
int n,q,k;
int maxx = -INF;
cin >> n >> q;
vector<int> a(n + 1);
vector<PII> res(n + 1);
for (int i = 1;i <= n;i ++)
{
cin >> a[i];
if (a[i] == n) maxx = i;
}
int mx = a[1],idx = 1,cnt = 1;
for (int i = 2;i <= n;i ++)
{
if (a[i] < mx)
{
if (res[idx].second == 0) res[idx].first = cnt;
res[idx].second = cnt;
}
else
{
mx = a[i];
idx = i;
res[idx].first = cnt;
res[idx].second = cnt;
}
cnt ++;
}
while(q --)
{
cin >> idx >> k;
int ans = 0;
bool can = idx > maxx || idx > k + 1 || res[idx].first > k || res[idx].first == 0;
if (!can && idx == maxx) ans = k - res[maxx].first + 1;
else if (!can)
{
if (k >= res[idx].second) ans = res[idx].second - res[idx].first + 1;
else ans = k - res[idx].first + 1;
}
cout << ans << endl;
}
}
|
