头像

FandouHututu




离线:1天前


最近来访(464)
用户头像
落拓Leisure
用户头像
哦呼_2
用户头像
吟风
用户头像
浩哥哥
用户头像
纪念曾经的信念
用户头像
无名小卒x
用户头像
2162826114
用户头像
被自己菜醒
用户头像
Pedestrian
用户头像
种花家的虎式坦克
用户头像
Present.
用户头像
Cvemix9
用户头像
小郭冲冲冲
用户头像
Weirdo_3
用户头像
Goku74
用户头像
瓜_9
用户头像
做些荼蘼绮丽的梦
用户头像
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()


活动打卡代码 AcWing 854. Floyd求最短路

#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;
        add(x, y, z);
    }
    cout << djs();
    return 0;
}


活动打卡代码 AcWing 847. 图中点的层次

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;
        add(a, b);
    }
    cout << bfs();
    return 0;
}


活动打卡代码 AcWing 846. 树的重心

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];

void add(int a, int b)
{
    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;
        add(a, b);
        add(b, a);
    }
    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()


活动打卡代码 AcWing 3371. 舒适的奶牛

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()