Fork me on GitHub

Atcoder Regular Contest arc 091-092 切(W)题(A)记

发表于 | 分类于
字数统计: 1,086字 | 阅读时长 ≈ 5分钟

概述

上午闲着没事就找了点Atcoder的（水）题切切, 顺便过一下博弈和SG函数。

Atcoder Regular Contest 091 C Flip,Flip,and Flip

ARC 091C

問題文

縦横に無限に広がるマス目があり、そのうちの連続する N 行 M 列の領域のすべてのマスに表裏の区別できるカードが置かれています。 最初はすべてのカードが表を向いています。

以下の操作を、カードが置かれている全てのマスについて 1 度ずつ行います。

  • そのマスと辺または点で接する 8 つのマスと、そのマスの合計 9 マスについて、カードが存在するなら裏返す。

すべての操作を行った後の各カードの状態は操作を行う順番に依らないことが証明できます。 すべての操作を行った後、裏を向いているカードの枚数を求めてください。

大意

问题陈述有无限长度和宽度的正方形展开，并且可以区分正面和背面的牌被放置在连续的n行和m列中的所有单元中。最初所有牌都面朝桌子。对于放置卡的每个方块执行一次以下操作。如果有8个方格邻接那个正方形和边或者点，并且如果有一张卡，则总共9个方格。您可以证明执行所有操作后每张卡的状态不取决于操作顺序。完成所有操作后，请找到背面的卡片数量。

注意细节特判1,1的情况.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(void)
{
	int x = 0,f = 1; char ch = getchar();
	while(!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
	while(isdigit(ch)){x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return x * f;
}
signed main(signed argc, char *argv[])
{
	int n = read(), m = read();
	if (n == 1 && m == 1) printf("1\n");
 	else if (n == 1)
		printf("%lld\n",m-2);
	else if (m == 1) printf("%lld\n",n-2);
	else printf("%lld\n",n*m-(n+m)*2+4);
	return 0;
}

Atcoder Regular Contest 091 D Remainder Reminder

ARC 091D

問題文

高橋君は、N 以下の正の整数の 2 つ組 (a,b) を持っていましたが、忘れてしまいました。 高橋君は、a を b で割ったあまりが K 以上であったことを覚えています。 高橋君が持っていた組としてあるうるものの個数を求めてください。

制約

  • 1≤N≤105
  • 0≤K≤N−1
  • 入力は全て整数である

大意

给出限制$N,K$,求满足

考虑b的范围为$[K+1,N]$

直接枚举b,然后算出对应范围下的$x$个数，但是注意xmax后有一部分剩余.

注意细节。（我特么WA了两次啊真彩笔）

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(void)
{
	int x = 0,f = 1; char ch = getchar();
	while(!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
	while(isdigit(ch)){x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return x * f;
}
signed main(signed argc, char *argv[])
{
	int ans = 0;
	int N = read(),K = read();
	if (K == 0)
	{
		N *= N;
		cout << N;
		return 0;
	}
	for (int b = K+1; b <= N; b++)
	{
		int xmax = (N)/(b);
		//cout << xmax << " # " << "\n"; 
		ans += xmax * (b-K);
		ans += max(0LL,(N - b * xmax) - K + 1);
		//cout << ans << endl;
	}
	cout << ans;
	return 0;
}

Atcoder Regular Contest 091 F Strange Nim

ARC 091F

問題文

高橋君と青木君は、石取りゲームをしています。最初、山が N 個あり、i 個目の山には A**i 個の石があり、整数 K**i が定まっています。

高橋君と青木君は、高橋君から始めて、交互に以下の操作を繰り返します。

  • 山を 1 つ選ぶ。i 個目の山を選び、その山に X 個の石が残っている場合、1 個以上 floor(X⁄K**i) 個以下の任意の個数の石を i 個目の山から取り除く。

先に操作ができなくなったプレイヤーが負けです。両者最善を尽くしたとき、どちらのプレイヤーが勝つか判定してください。 ただし、floor(x) で x 以下の最大の整数を表します。

大意:

给n堆石子，每堆有一开始有ai个和一个常数ki。两个人轮流操作，每个人每轮可以选一堆石子，然后在其中取走1到$\large\frac{a_i}{k_i}$,谁不能操作就算输，问先手必胜还是后手必胜。

SG函数+暴力

不难发现SG函数递推式$SG(x) = SG(x-x/k-1)$

因为每一次k都是恒等的，考虑直接一步用取模跳到就行，不然T飞。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 210;
string s1 = "Takahashi",s2 = "Aoki";
inline int read(void)
{
	int x = 0,f = 1; char ch = cin.get();
	while(!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = cin.get();}
	while(isdigit(ch)){x = (x << 3) + (x << 1) + ch - '0'; ch = cin.get();}
	return x * f;
}
int main(int argc, char *argv[])
{
	ios::sync_with_stdio(false);
	int n = read();
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		int x = read() , k = read();
		while((x%k)) x -= ((x%k-1)/(x/k+1)+1) * (x/k+1);
		ans ^= x/k; 
	}
	if (ans) cout << s1;
	else cout << s2;
	return 0;
}