AtCoder Beginner Contest 275(C，E 补)

C - Counting Squares

给出一个9 * 9的字符矩阵找所有的由“#”组成的正方形
思路 ， 以一个顶点开始 ， 通过枚举偏移量找到其余四个顶点

枚举 x , y , m , n 然后用 set 去重即可

#include
using namespace std;
 
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e6+10;
const int NN = 1e6+100;
const int p = 1e5 + 3;
typedef pair<int,int>PII;
const int inf = 1e9 + 10;
const ll linf = 1e18 + 10;
 
inline int read() {
	bool sym = 0; int res = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}
 
char c[19][19];
 
bool judge(int x,int y){
	return x >= 1 && y >= 1 && x <= 9 && y <= 9;
}
 
set<set<PII>>st;
 
int main(){
	
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			cin >> c[i][j];
		}
	}
	
	int ans = 0;
	
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			for(int k=-9;k<=9;k++){
				for(int m=-9;m<=9;m++){
					if(judge(i,j) && c[i][j] == '#' && judge(i+k,j+m) && c[i+k][j+m] == '#' && judge(i-m,j+k) && c[i-m][j+k] == '#' && judge(i-m+k,j+k+m) && c[i-m+k][j+k+m] == '#'){
						set<PII>s;
						s.insert({i,j});
						s.insert({i+k,j+m});
						s.insert({i-m,j+k});
						s.insert({i-m+k,j+k+m});
						if(s.size() == 4) st.insert(s);//这里是防止 k = m = 0 的情况
					}
				}
			}
		}
	}
	
	cout << st.size() << "\n" ;

	return 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
51
52
53
54
55
56
57
58
59
60
61

E - Sugoroku 4(概率 dp + 刷表法)

首先说刷表法和填表法

刷表法是指 当前已知去推未知
填表法是指 当前未知要用已知来推

一般概率题用刷表法

dp[i] [j] 表示 第 i 次投掷 到达位置为 j 的概率
s 是走的步数

j + s <= n 时
dp[i+1][j+s] +=  dp[i][j] / m 
else
dp[i+1][2*n-j-s] += dp[i][j] / m 
1
2
3
4

一定要注意除法取模要用逆元
还要注意因为是用已知去推未知，一定要注意范围
还有就是一个状态有可能是多个状态转移来的，一定要加上去

#include
using namespace std;

#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e6+10;
const int NN = 1e6+100;
const ll p = 998244353;
typedef pair<int,int>PII;
const int inf = 1e9 + 10;
const ll linf = 1e18 + 10;

inline int read() {
	bool sym = 0; int res = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

int n , m , k;
ll dp[1010][1010];


ll qsm(ll a,ll b)
{
	ll res=1;
	
	while(b){
		if(b % 2 != 0) res = res * a % p;
		a = a * a % p;
		b /= 2;
	}
	
	return res;
}


//dp[i][j] 表示转盘转动 i 次 到达 j 点的概率
//dp[i+1][j+s] += dp[i][j] * 1/M = dp[i][j] * inv(M)
//刷表法  已知推未知
int main(){
	
	dp[0][0] = 1;

	cin >> n >> m >> k;
	
	ll inv = qsm(m , p-2);
	
	for(int i=0;i<k;i++){
		for(int j=0;j<n;j++){
			for(int s=1;s<=m;s++){
				if(j + s <= n){
					dp[i+1][j+s] = (dp[i+1][j+s] + dp[i][j] * inv) % p;
				}else{
					dp[i+1][2*n-j-s] = (dp[i+1][2*n-j-s] + dp[i][j] * inv) % p;
				}
			}
		}
	}
	
	ll ans = 0;
	
	for(int i=1;i<=k;i++){
		ans = (ans + dp[i][n]) % p;
	}
	
	cout << ans ;
	
	return 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74