FandouHututu

1.7万

2162826114

Pedestrian

Present.
Cvemix9

Weirdo_3
Goku74

1402864132
yu_yu
incra

#### python3 代码

def main():
n = int(input())
h = list(map(int, input().split()))
a, ans = sorted(list(set(h))), [-1] * n
m = len(a)
tree = [-1] * (m+5)

def getId(x: int) -> int:
left, right = 0, m-1
while left < right:
mid = left+right >> 1
if a[mid] >= x: right = mid
else: left = mid+1
return left+2

def query(u: int) -> int:
res = -1
while u:
res = max(res, tree[u])
u -= u & -u
return res

def update(u: int, v: int) -> int:
while u < len(tree):
tree[u] = max(tree[u], v)
u += u & -u

for i in range(n-1, -1, -1):
q = query(getId(h[i])-1)
if q != -1:
ans[i] = q-i-1
update(getId(h[i]), i)
for e in ans:
print(e, end = " ")

if __name__ == '__main__':
main()


#include <iostream>
#include <cstring>

using namespace std;

const int N = 205, INF = 0x3f3f3f3f;
int n, m, t, x, y, z;
int dis[N][N];

int main()
{
memset(dis, 0x3f, sizeof dis);
cin >> n >> m >> t;
for (int i = 1; i <= n; ++ i) dis[i][i] = 0;
for (int i = 0; i < m; ++ i)
{
cin >> x >> y >> z;
dis[x][y] = min(dis[x][y], z);
}
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
for (int k = 1; k <= n; ++ k)
dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
for (int i = 0; i < t; ++ i)
{
cin >> x >> y;
if (dis[x][y] * 2 > INF) cout << "impossible" << endl;
else cout << dis[x][y] << endl;
}
return 0;
}


#### C++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 1e3 + 10;
int t, n, m, bx, by, gx, gy, cnt;
char grid[N][N];
bool stb[N][N], stg[N][N];
PII ghost[2];
int dir[5] = {0, 1, 0, -1, 0};
struct node{
int x, y, step;
};

int check_dis(const int& x, const int& y, const int& step)
{
for (int i = 0; i < 2; ++ i)
{
if (abs(ghost[i].first - x) + abs(ghost[i].second - y) <= 2 * (step + 1))
return false;
}
return true;
}

bool check(const int& x, const int& y, const int& step, const int& u)
{
if (x < 0 || x >= n || y < 0 || y >= m) return false;
if (u && stb[x][y]) return false;
if (!u && stg[x][y]) return false;
if (grid[x][y] == 'X') return false;
return check_dis(x, y, step);
}

int bfs()
{
queue<node> qb, qg;
qb.push({bx, by, 0});
qg.push({gx, gy, 0});
stb[bx][by] = true, stg[gx][gy] = true;
while (qb.size() && qg.size())
{
int temp = qb.front().step;
for (int k = 0; k < 3; ++ k)
{
while (qb.size() && qb.front().step == temp + k)
{
auto tnode = qb.front();
qb.pop();
int x = tnode.x, y = tnode.y, step = tnode.step;
if (!check_dis(x, y, temp)) continue;
for (int i = 0; i < 4; ++ i)
{
int tx = x + dir[i], ty = y + dir[i + 1];
if (check(tx, ty, temp, 1))
{
stb[tx][ty] = true;
if (k != 2) qb.push({tx, ty, step + 1});
else qb.push({tx, ty, temp + 1});
}
}
}
}
while (qg.size() && qg.front().step == temp)
{
auto tnode = qg.front();
qg.pop();
int x = tnode.x, y = tnode.y, step = tnode.step;
if (!check_dis(x, y, step)) continue;
for (int i = 0; i < 4; ++ i)
{
int tx = x + dir[i], ty = y + dir[i + 1];
if (check(tx, ty, step, 0))
{
if (stb[tx][ty]) return step + 1;
stg[tx][ty] = true;
qg.push({tx, ty, step + 1});
}
}
}
}
return -1;
}

int main()
{
cin >> t;
while (t --)
{
cnt = 0;
memset(stb, false, sizeof stb);
memset(stg, false, sizeof stg);
cin >> n >> m;
for (int i = 0; i < n; ++ i)
{
for (int j = 0; j < m; ++ j)
{
cin >> grid[i][j];
if (grid[i][j] == 'M') bx = i, by = j;
else if (grid[i][j] == 'G') gx = i, gy = j;
else if (grid[i][j] == 'Z') ghost[cnt ++] = {i, j};
}
}
cout << bfs() << endl;
}
return 0;
}


FandouHututu
1个月前
def main():
N = 505
g, dis = [], [0x3f3f3f3f] * N
n, m, k = map(int, input().split())
while m:
g.append(list(map(int, input().split())))
m -= 1

def bellman_ford(u: int, v: int) -> int:
dis[u] = 0
for i in range(k):
back = dis[:]
for e in g:
dis[e[1]] = min(dis[e[1]], back[e[0]] + e[2])
return dis[v]

ans = bellman_ford(1, n)
if ans >= 0x3f3f3f3f // 2:
print("impossible")
else:
print(ans)

if __name__ == '__main__':
main()


FandouHututu
1个月前
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 1e5 + 5e4 + 10;
int n, m, x, y, z, idx;
int e[N], ne[N], h[N], dis[N], w[N];
bool st[N];
priority_queue<PII, vector<PII>, greater<PII>> pq;

void add(const int& a, const int& b, const int& c)
{
w[idx] = c;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}

int djs()
{
dis[1] = 1;
pq.push({0, 1});
while (!pq.empty())
{
auto t = pq.top();
pq.pop();
int tdis = t.first, tidx = t.second;
if (st[tidx]) continue;
st[tidx] = true;
for (int i = h[tidx]; i != -1; i = ne[i])
{
int j = e[i];
if (dis[j] > tdis + w[i])
{
dis[j] = tdis + w[i];
pq.push({dis[j], j});
}
}
}
if (dis[n] != 0x3f3f3f3f) return dis[n];
return -1;
}

int main()
{
memset(h, -1, sizeof h);
memset(dis, 0x3f, sizeof dis);
cin >> n >> m;
while (m --)
{
cin >> x >> y >> z;
}
cout << djs();
return 0;
}


FandouHututu
1个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n, m, a, b;
int e[N], ne[N], h[N], idx;
bool st[N];

void add(const int& a, const int& b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}

int bfs()
{
queue<pair<int, int>> q;
q.push({1, 0});
st[1] = true;
while (!q.empty())
{
int t = q.front().first;
int step = q.front().second;
if (t == n) return step;
for (int i = h[t]; i != -1; i = ne[i])
if (!st[e[i]])
{
st[e[i]] = true;
q.push({e[i], step + 1});
}
q.pop();
}
return -1;
}

int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m --)
{
cin >> a >> b;
}
cout << bfs();
return 0;
}


FandouHututu
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = 2 * N;
int n, ans = N, idx;
int ne[M], e[M], h[N];
bool st[N];

{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}

int dfs(int u)
{
int res = 0, sum = 1;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(!st[j])
{
st[j] = true;
int temp = dfs(j);
res = max(res, temp);
sum += temp;
}
}
res = max(res, n - sum);
ans = min(ans, res);
return sum;
}

int main()
{
memset(h, -1, sizeof h);
cin >> n;
int t = n - 1;
while(t --)
{
int a, b;
cin >> a >> b;
}
st[1] = true;
dfs(1);
cout << ans;
return 0;
}


FandouHututu
1个月前

#### Python3 代码

def main():
N = 1010
g = [[0] * N for i in range(N)]
st = [[False] * N for i in range(N)]
dr = [0, -1, 0, 1, 0]

def check(x: int, y: int) -> bool:
if x < 0 or x >= N or y < 0 or y >= N or not g[x][y]:
return False
cnt = 0
for i in range(4):
tx, ty = x + dr[i], y + dr[i + 1]
if tx >= 0 and ty < N and g[tx][ty]:
cnt += 1
return cnt == 3

n, ans = int(input()), 0
for i in range(n):
x, y = map(int, input().split())
g[x][y] = 1
if check(x, y):
st[x][y] = True
ans += 1
for i in range(4):
tx, ty = x + dr[i], y + dr[i + 1]
if tx < 0 or tx >= N or ty < 0 or ty >= N or not g[tx][ty]:
continue
if st[tx][ty]:
if not check(tx, ty):
ans -= 1
st[tx][ty] = False
elif check(tx, ty):
st[tx][ty] = True
ans += 1
print(ans)

if __name__ == '__main__':
main()


FandouHututu
1个月前
def main():
N = 1010
g = [[0] * N for i in range(N)]
st = [[False] * N for i in range(N)]
dr = [0, -1, 0, 1, 0]

def check(x: int, y: int) -> bool:
if x < 0 or x >= N or y < 0 or y >= N or not g[x][y]:
return False
cnt = 0
for i in range(4):
tx, ty = x + dr[i], y + dr[i + 1]
if tx >= 0 and ty < N and g[tx][ty]:
cnt += 1
return cnt == 3

n, ans = int(input()), 0
for i in range(n):
x, y = map(int, input().split())
g[x][y] = 1
if check(x, y):
st[x][y] = True
ans += 1
for i in range(4):
tx, ty = x + dr[i], y + dr[i + 1]
if tx < 0 or tx >= N or ty < 0 or ty >= N or not g[tx][ty]:
continue
if st[tx][ty]:
if not check(tx, ty):
ans -= 1
st[tx][ty] = False
elif check(tx, ty):
st[tx][ty] = True
ans += 1
print(ans)

if __name__ == '__main__':
main()


FandouHututu
1个月前
def main():

def cal(n: int, nums: list) -> int:
x, y, ans = 0, 0, 0
for e in nums:
if e & 1:
x += 1
else:
y += 1
for i in range(n):
if i & 1:
if x:
x -= 1
ans += 1
else:
break
else:
if y:
y -= 1
ans += 1
elif x >= 2:
x -= 2
ans += 1
else:
break
if x % 2:
ans -= 1
return ans

n = int(input())
nums = list(map(int, input().split()))
ans = cal(n, nums)
print(ans)

if __name__ == '__main__':
main()