链接： http://acm.hdu.edu.cn/showproblem.php?pid=6229
题意： 给一个矩阵上面有一些坏点，坏点不能走，起点是
(
0
,
0
)
(0, 0)
(0,0) ，保证所有可行点联通。在每个点走向其他可走方向（上下左右）和待在原地的概率是相同的。问无限次后，在位置
{
(
x
,
y
)
∣
x
+
y
≥
N
−
1
}
\{(x, y)|x + y ≥ N - 1 \}
{(x,y)∣x+y≥N−1} 的部分的概率总和是多少。
思路： 完全没思路，看完题解并没有理解，并不知道是怎么想出来…。现在开始搬运，每个点给一个权值，权值是到达当前位置的方案数，比如四个角就是
3
3
3，矩阵边沿就是
4
4
4，内部是
5
5
5。坏点是
0
0
0（不可达），并且坏点周围的点要减
1
1
1，因为坏点周围的点不能从坏点到达。 结果是 下三角的权值 / 总权值。对于此我有三种解法。
-
二分
先算出没有坏点的下三角权值和、权值总和。按照先
x
x
x 后
y
y
y 排序所有坏点。遍历所有坏点，二分找四个方向上是否有坏点，如果有，不做任何操作（因为坏点周围的那个点是坏点，没有影响）；如果没有坏点，权值总和减一，如果位置在下三角，下三角权值和减一（就是坏点对周围的点的贡献是
−
1
-1
−1）。最后别忘了也要减去所有坏点的权值。
-
set
和二分思路一样，多了一步把所有坏点插入
s
e
t
set
set ，然后查找的时候直接
c
o
u
n
t
count
count 找点，
1
1
1 就找到了，
0
0
0 就没有。其实好像比二分好写多了。也不会出现
k
k
k 写成
n
n
n 的智障情况。其实就是因为我二分写毒了，把
k
k
k 写成
n
n
n 了，导致一直
W
A
WA
WA，才写的
s
e
t
set
set ，没想到一下就过了，很无奈，不过也告诉了我二分没错，才浪费了我几个小时
d
e
b
u
g
debug
debug 二分。
-
map
其实这才是最好写的。遍历所有坏点，坏点存入
m
a
p
map
map 他的值是当前点的权值。坏点周围的点的值就是 当前值 加一，然后取点的权值 和 加一后的值的最小值。这是在算有负贡献的点的负贡献值，取最小值是因为一个点只能有权值这么多的负贡献。最后遍历
m
a
p
map
map 减去所有负贡献即可。
1.
二
分
1. 二分
1.二分
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 11000;
struct node {
int x, y;
bool operator < (const node &d) const {
return (x == d.x)?(y < d.y):(x < d.x);
}
};
int t, cas;
LL n, k;
std::map<int, int> m[MAXN];
node bad[MAXN];
set<node > se;
int dir[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool check(int x, int y) {
if(x < 0 || x > n-1 || y < 0 || y > n-1) return true;
return false;
}
int where(int x, int y) {
if((x == 0 && y == 0) || (x == 0 && y == n-1) || (x == n-1 && y == 0) || (x == n-1 && y == n-1))
return 3;
if(x == 0 || x == n-1 || y == 0 || y == n-1)
return 4;
return 5;
}
int main(int argc, char const *argv[])
{
scanf("%d", &t);
while(t--) {
scanf("%lld%lld", &n, &k);
if(n == 1) {
printf("Case #%d: 1/1\n", ++cas);
continue;
}
se.clear();
for (int i = 0; i < k; ++i) {
scanf("%d%d", &bad[i].x, &bad[i].y);
}
LL sum = 4*3 + 4*(n-2)*4 + (n-2)*(n-2)*5;
LL part = 3*3 + 2*(n-2)*4 + ((n-1)*(n-2)/2)*5;
sort(bad, bad+k);
for (int i = 0; i < k; ++i) {
int x = bad[i].x;
int y = bad[i].y;
int cnt = 0, cnt2 = 0, num = 0, num2 = 0;
for (int d = 0; d < 4; ++d) {
if(check(x+dir[d][0], y+dir[d][1])) continue;
node tm;
tm.x = x+dir[d][0];
tm.y = y+dir[d][1];
bool flag = 0;
int pos = lower_bound(bad, bad+k, tm) - bad;
if((pos != k) && (bad[pos].x == x+dir[d][0] && bad[pos].y == y+dir[d][1])) {
continue;
}
sum--;
if(x+dir[d][0] + y+dir[d][1] >= n-1) part--;
}
int tmp = where(x, y);
if(x+y >= n-1) {
part -= tmp;
}
sum -= tmp;
}
LL g = __gcd(part, sum);
printf("Case #%d: %lld/%lld\n", ++cas, part/g, sum/g);
}
return 0;
}
看我的调试代码就知道我
d
e
b
u
g
debug
debug 多久了，简直崩溃。
2.
s
e
t
2. set
2.set
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 11000;
struct node {
int x, y;
bool operator < (const node &d) const {
return (x == d.x)?(y < d.y):(x < d.x);
}
};
int t, cas;
LL n, k;
std::map<int, int> m[MAXN];
node bad[MAXN];
set<node > se;
int dir[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool check(int x, int y) {
if(x < 0 || x > n-1 || y < 0 || y > n-1) return true;
return false;
}
int where(int x, int y) {
if((x == 0 && y == 0) || (x == 0 && y == n-1) || (x == n-1 && y == 0) || (x == n-1 && y == n-1))
return 3;
if(x == 0 || x == n-1 || y == 0 || y == n-1)
return 4;
return 5;
}
int main(int argc, char const *argv[])
{
scanf("%d", &t);
while(t--) {
scanf("%lld%lld", &n, &k);
if(n == 1) {
printf("Case #%d: 1/1\n", ++cas);
continue;
}
se.clear();
for (int i = 0; i < k; ++i) {
scanf("%d%d", &bad[i].x, &bad[i].y);
se.insert(bad[i]);
}
LL sum = 4*3 + 4*(n-2)*4 + (n-2)*(n-2)*5;
LL part = 3*3 + 2*(n-2)*4 + ((n-1)*(n-2)/2)*5;
for (int i = 0; i < k; ++i) {
int x = bad[i].x;
int y = bad[i].y;
int cnt = 0, cnt2 = 0, num = 0, num2 = 0;
for (int d = 0; d < 4; ++d) {
if(check(x+dir[d][0], y+dir[d][1])) continue;
node tm;
tm.x = x+dir[d][0];
tm.y = y+dir[d][1];
bool flag = 0;
if(se.count(tm)) {
continue;
}
sum--;
if(x+dir[d][0] + y+dir[d][1] >= n-1) part--;
}
int tmp = where(x, y);
if(x+y >= n-1) {
part -= tmp;
}
sum -= tmp;
}
LL g = __gcd(part, sum);
printf("Case #%d: %lld/%lld\n", ++cas, part/g, sum/g);
}
return 0;
}
这里是一次过的，调试代码是和二分对拍的时候写的。
3.
m
a
p
3. map
3.map
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
const int MAXN = 11000;
struct node {
int x, y;
bool operator < (const node &d) const {
return (x == d.x)?(y < d.y):(x < d.x);
}
};
int t, cas;
LL n, k;
std::map<node, int> mp;
node bad[MAXN];
set<node > se;
int dir[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool check(int x, int y) {
if(x < 0 || x > n-1 || y < 0 || y > n-1) return true;
return false;
}
int where(int x, int y) {
if((x == 0 && y == 0) || (x == 0 && y == n-1) || (x == n-1 && y == 0) || (x == n-1 && y == n-1))
return 3;
if(x == 0 || x == n-1 || y == 0 || y == n-1)
return 4;
return 5;
}
int main(int argc, char const *argv[])
{
scanf("%d", &t);
while(t--) {
scanf("%lld%lld", &n, &k);
if(n == 1) {
printf("Case #%d: 1/1\n", ++cas);
continue;
}
mp.clear();
for (int i = 0; i < k; ++i) {
scanf("%d%d", &bad[i].x, &bad[i].y);
}
LL sum = 4*3 + 4*(n-2)*4 + (n-2)*(n-2)*5;
LL part = 3*3 + 2*(n-2)*4 + ((n-1)*(n-2)/2)*5;
for (int i = 0; i < k; ++i) {
int x = bad[i].x;
int y = bad[i].y;
mp[(node){x, y}] = where(x, y);
for (int d = 0; d < 4; ++d) {
if(check(x+dir[d][0], y+dir[d][1])) continue;
node tm;
tm.x = x+dir[d][0];
tm.y = y+dir[d][1];
++mp[tm];
mp[tm] = min(mp[tm], where(tm.x, tm.y));
}
}
for (std::map<node, int>::iterator it = mp.begin(); it != mp.end(); ++it) {
int x = (it->fi).x;
int y = (it->fi).y;
int tmp = it->se;
sum -= tmp;
if(x + y >= n-1) part -= tmp;
}
LL g = __gcd(part, sum);
printf("Case #%d: %lld/%lld\n", ++cas, part/g, sum/g);
}
return 0;
}
m
a
p
map
map 其实是可以用auto类型遍历的，但是必须用
c
+
+
11
c++11
c++11 的标准编译，
g
+
+
g++
g++ 的命令是 g++ -g -Wall -std=c++11 M(map).cpp
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
