头像

ZZDoctor




在线 



#include <iostream>

#include <iostream>
#include <vector>
#include <queue>


using namespace std;

int n, m;
vector<vector<int>> outvec(100010, vector<int>());
vector<int> invec(100010, 0);
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int start; int end;
        cin >> start >> end;
        invec[end]++;
        outvec[start].push_back(end);
    }
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        if (invec[i] == 0)
        {
            q.push(i);
        }
    }

    vector<int>  ret;
    while (!q.empty()) {
        int idx = q.front();
        q.pop();

        ret.push_back(idx);
        for (auto& e : outvec[idx]) {
            if (e != -1) {
                invec[e]--;
                if (invec[e] == 0) {
                    q.push(e);
                }
                e = -1;
            }
        }
    }

    if(ret.size() == n)
        for (auto& e : ret) {
            cout << e << " ";
        }
    else
        cout << -1;



    return 0;
}


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

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], d[N], idx, ne[N];
int n, m, q[N];

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

int bfs()
{
    int hh = 0, tt = 0;

    q[0] = 1;
    memset(d, -1, sizeof d);
    d[1] = 0;
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)
            {
                d[j] = d[t] + 1;
                q[++tt] = j;
            }
        }
    }
    return d[n];
}

int main(void)
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cout << bfs() << endl;
    return 0;
}



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

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
const int M = 2 * N;

int h[N];
int e[M];
int ne[M];
int idx;
int n;
int ans = 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;
    st[u] = true;
    int sum = 1;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            int s = dfs(j);
            res = max(res, s);
            sum += s;
        }
    }

    res = max(res, n - sum);
    ans = min(res, ans);
    return sum;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(1);
    cout << ans << endl;

    return 0;
}



POJ1160 Post Office

传送门

题目描述

在笔直的大道上建有$n$个大别墅,两个大别墅之间的距离是他们的横坐标之差的绝对值,保证大别墅之间的距离只能是整数,且没有别墅的位置是相同的。
现在需要建立$m$座大超市$(m \leq n)$,大超市只能建立在别墅所在的位置,现在需要你写个程序,给定了所有别墅的位置和大超市的数目,计算出每个别墅离最近的大超市的距离总和的最小值。

输入格式

第一行包括两个整数$n$和$m$
第二行包括n个整数,代表别墅的位置,以升序的形式列出。对于每一个整数$x$.

样例输入

10 5
1 2 4 6 7 10 11 25 44 70

样例输出

11

数据范围

$1 <= n <= 300$
$1 <= m <= 30$
$m <= n$
$1 <= X <= 10000$


我们先考虑这样一个问题:三个别墅分别在$(1, 7, 20)$中选一个超市,最小的距离和是多少。
Alt
答案是在中间那个超市,因为$(20-1+1) ÷ 2 = 10$,离$10$最近的超市是7,所以我们选中间这个别墅做超市,那么再来有5个别墅的情况:
在这里插入图片描述
答案还是离$(20-1+1) ÷ 2=10$的最近的别墅7,所以我们得出一个结论: 只有超市位于中间位置,距离和才最小

注意这个位置不是中间的那个别墅,而是离中间的那个地方最近的别墅。

设$dp[i][j]$表示考虑前$i$个别墅建$j$个超市的最小代价。

那么$dp[i][j]$可以从哪个地方转移过来呢?

$dp[k][j - 1]$,因为我们可以把$k$前面的别墅分成一块$k$到$i$的别墅另外分成一块,这一块只建一个超市。

所以状态转移方程是:$$dp[i][j]=min(dp[i][j],\text{ }\text{ }dp[k][j-1]+dis[k+1][i])$$
注:$dis[i][j]$表示第i个别墅到第j个别墅只建一个超市的最小代价

这个$dis[i][j]$是需要预处理的,因为如果不预处理,每次就需要枚举最优决策点,时间复杂度为$O(P^2 V^2)$是会超时的,但是我们可以用$V^2$预处理$dis[i][j]$,那么时间复杂度就降成$O(P^2V)$就不会超时了。

那现在来看看这个$dis[i][j]$怎么算:

我们先去掉$i$~$j$区间的最后一个,即只剩下了$i$ ~ $j-1$,这个区间只建一个超市的最小代价是$dis[i][j-1]$,最后加上新加的这个节点的与最优决策点的差就行了。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 305
#define INF 0x3f3f3f3f
int V, P;
int x[MAXN], dp[MAXN][MAXN], dis[MAXN][MAXN];
int main()
{
    scanf("%d %d", &V, &P);
    memset(dp, INF, sizeof(dp)); 
    for(int i = 1; i <= V; i++)
        scanf("%d", &x[i]);
    for(int i = 1; i <= V; i++)
        dis[i][i] = 0;
    for(int i = 1; i <= V; i++)
        for(int j = i + 1; j <= V; j++)
            dis[i][j] = dis[i][j - 1] + x[j] - x[(i + j) / 2];
    for(int i = 1; i <= V; i++)
        dp[i][1] = dis[1][i];
    for(int j = 1; j <= P; j++)
        for(int i = j + 1; i <= V; i++)
            for(int k = 1; k <= i; k++)
                dp[i][j] = min(dp[i][j], dp[k][j - 1] + dis[k + 1][i]);
    cout << dp[V][P] << endl;
    return 0;
}


活动打卡代码 AcWing 845. 八数码

#include<cstring>
#include<iostream>
#include<queue>
using namespace std;

int fact[9];
bool vis[362880];

int permutation_hash(char s[])
{
    int ans = 0;
    for(int i = 0; i < 9; i ++)
    {
        int d = 0;
        for(int j = 0; j < i; j ++)
            if(s[j] > s[i])  d ++;
        ans += d * fact[i];
    }
    return ans;
}

typedef struct{
    char s[10];
    int step;
    int k;
}Point;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = { 0,-1, 0, 1};
int bfs(Point p)
{
    vis[permutation_hash(p.s)] = true;
    queue<Point> q;
    q.push(p);
    while(!q.empty())
    {
        p = q.front();
        q.pop();
        if(!strcmp(p.s , "12345678x"))
            return p.step;
        int x = p.k / 3;
        int y = p.k % 3;
        Point next;
        next.step = p.step + 1;
        for(int i = 0; i < 4; i ++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && nx <= 2 && ny >= 0 && ny <= 2)
            {
                next.k = nx * 3 + ny;
                strcpy(next.s, p.s);
                next.s[9] = 0;
                next.s[p.k] = p.s[next.k];
                next.s[next.k] = 'x';
                int hash = permutation_hash(next.s);
                if(!vis[hash])
                {
                    vis[hash] = true;
                    q.push(next);
                }
            }
        }
    }
    return -1;
}

int main()
{
    fact[0] = 1;
    for(int i = 1; i < 9; i ++)  fact[i] = fact[i - 1] * i;
    char c[2],str[10];
    Point start;
    for(int i = 0; i < 9; i ++)
    {
        scanf("%s",&c);
        if(c[0] == 'x')
            start.k = i;
        start.s[i] = c[0];
    }
    start.s[9] = 0;
    start.step = 0;
    printf("%d",bfs(start));
    return 0;
}



活动打卡代码 AcWing 844. 走迷宫

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
int n, m;
#define MAXN 105
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int g[MAXN][MAXN], d[MAXN][MAXN];
int bfs()
{
    queue <PII> q;
    for(auto &v : d) 
        for(auto &x : v)
            x = - 1;
    d[0][0] = 0;
    q.push({0, 0});
    while (!q.empty())
    {
        auto t = q.front();
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }
    return d[n - 1][m - 1];
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];
    cout << bfs() << endl;
    return 0;
}


活动打卡代码 AcWing 843. n-皇后问题

#include <bits/stdc++.h>
using namespace std;
#define MAXN 25
int n;
char g[MAXN][MAXN];
bool col[MAXN], dg[MAXN], udg[MAXN];
void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
                printf("%c", g[i][j]);
            puts("");
        }
        puts("");
        return;
    }
    for(int i = 0; i < n; i++)
        if(!col[i] && !dg[u + i] && !udg[n - u + i])
        {
            g[u][i] = 'Q';
            col[i] = 1;
            dg[u + i] = 1;
            udg[n - u + i] = 1;
            dfs(u + 1);
            col[i] = 0;
            dg[u + i] = 0;
            udg[n - u + i] = false;
            g[u][i] = '.';
        }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            g[i][j] = '.';
    dfs(0);
    return 0;
}   



活动打卡代码 AcWing 842. 排列数字

#include <iostream>
using namespace std;
#define MAXN 15
int n;
int path[MAXN];
bool flag[MAXN];
void dfs(int u) 
{
    if(u == n)
    {
        for(int i = 0; i < n; i++)
            printf("%d ", path[i]);
        puts("");
        return;
    }
    else 
    {
        for(int i = 1; i <= n; i++)
        {
            if(!flag[i])
            {
                flag[i] = true;
                path[u] = i;
                dfs(u + 1);
                flag[i] = false;
                path[u] = 0;
            }
        }
    }
}
int main()
{
    scanf("%d", &n);
    dfs(0);
    return 0;
}



活动打卡代码 AcWing 35. 反转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head){
        ListNode *prev = nullptr;
        ListNode *cur = head;
        while (cur)
        {
            ListNode *next = cur->next;
            cur->next = prev;
            prev = cur, cur = next;
        }
        return prev;
    }
};




class Solution {
public:
    int strToInt(string str) {
        int k = 0; 
        while(k < str.size() && str[k] == ' ')
            k++;
        bool is_minus = false;
        long long num = 0;
        if(str[k] == '+') k++;
        else if(str[k] == '-') k++, is_minus = true;
        while(k < str.size() && str[k] >= '0' && str[k] <= '9')
        {
            num = num * 10 + str[k] - '0';
            k++;
        }
        if(is_minus)
            num *= -1;
        if(num > INT_MAX) num = INT_MAX;
        if(num < INT_MIN) num = INT_MIN;
        return (int) num;
    }
};