头像

故人倾




离线:1小时前


最近来访(123)
用户头像
情断青丝
用户头像
苏丕谟
用户头像
AOHY
用户头像
吊车尾92
用户头像
77777777777
用户头像
林带王子
用户头像
@cxd
用户头像
rzybzzzz
用户头像
Pokestar
用户头像
耐心
用户头像
烟火流沙
用户头像
Anohgy
用户头像
石不转
用户头像
有机物
用户头像
改了吧
用户头像
yxc的小迷妹
用户头像
AlexZhang
用户头像
.yxc.
用户头像
a_pig_of_banana
用户头像
算法练习生

活动打卡代码 工程课 Linux-5.0. homework_0

初始化
git init

git add .

git commit -m '干了什么事'

git push

查看commit了几次,可以看到序列号
git log 

将文件回退到某个版本,此时log也会回退
git reset --hard xx序列号

//查看所有log和版本号
git reflog

强制推送
git push -f



能否找到一个关键点,使得所有从左上走到右下的点都必须经过该点
两次DFS,如果满足,第一次dfs能到达终点,然后把第一次经过的所有路径全都置为0,然后再dfs一次却不能到终点了,说明其中某个关键点被消除了。说明有存在关键点

class Solution {
public:

    int n,m;
    bool dfs(vector<vector<int>>& g,int x,int y)
    {
        if(x == n-1 && y == m-1)
        {
           return true;
        }
        g[x][y] = 0;
        if(x + 1 < n && g[x+1][y] && dfs(g,x + 1,y))return true;
        if(y + 1 < m && g[x][y + 1] && dfs(g,x,y + 1))return true;
        return false;
    }
    bool isPossibleToCutPath(vector<vector<int>>& g) {
         n = g.size();
         m = g[0].size();

       dfs(g,0,0);
        if(dfs(g,0,0) == false)  return true;
        return false;  

    }
};



固定第二个seg,然后枚举前面那个seg

class Solution {
public:
    int maximizeWin(vector<int>& prizePositions, int k) {
        int n = prizePositions.size();
        int l = 0,pre[n + 1],ans = 0;
        pre[0] = 0;
        for(int r = 0; r < n; r ++)
        {
            while(prizePositions[r] - prizePositions[l] > k)l ++;


            int t = 0;
            if(l == 0)
            {
                t = 0;
            }
            else t = pre[l-1];
            ans = max(ans, r - l + 1 + t);
            if(r == 0)
            {
                t = 0;
            }
            else t = pre[ r-1];
            pre[r] = max(r - l + 1,t);
        }
        return ans;
    }
};


活动打卡代码 LeetCode 2560. 打家劫舍 IV

二分答案
然后判断n个数中在满足条件的情况下是否存在至少k个小于等于target

class Solution {
public:
    bool check(vector<int> nums,int mid,int k)
    {
        int n = nums.size(),cnt = 0;
        vector<bool> st(n,false);
        for(int i  = 0; i < n; i ++)
            if(nums[i] <= mid)st[i] = true;
        for(int i = 0; i < n; i ++)
        {
            if(st[i])
            {
                cnt ++;
                i ++;
            }
        }
        return cnt >= k;
    }
    int minCapability(vector<int>& nums, int k) {
        int l = 0, r = 1e9;
        while(l < r)
        {
            int mid = (l + r ) >> 1;
            if(check(nums,mid,k))r = mid;
            else l = mid + 1;
        }
        return r;
    }
};


活动打卡代码 AcWing 4281. 序列查询新解

这个分段考验耐心
mid = i * R,这个mid为什么是最小的横坐标,因为 y = x / R,—>求x—》= y * R

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL n,m,a[N],R;
LL get(LL l,LL r)
{
    LL res = 0;
    if(l / R == r / R)return (r - l + 1) * (r / R);
    LL a = l / R + 1, b = r / R - 1;
    res += R * (a + b) * (b - a + 1) / 2; // 中间
    res += (a-1) * (a * R - l);         //左边
    res += (b + 1) * (r - (b + 1) * R + 1); //右边
    return res;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)cin >> a[i];
    a[n + 1] = m;
    R = m / (n + 1);
    LL res = 0;
    for(LL i = 0; i <= n; i ++)
    {
        LL l = a[i], r = a[i + 1] - 1;
        LL x = l / R, y = r / R;
        if(x >= i || y <= i)
        {
            res += abs(i * (r - l + 1) - get(l,r));
        }
        else 
        {
            LL mid = i * R;
            res += abs( i * (mid - l + 1) - get(l, mid));
            res += abs(get(mid + 1,r) - i * (r - mid) );
        }
    }
    cout << res;
}


新鲜事 原文

故人倾
12天前
AcWing《Unity3D应用课》拼团优惠!https://www.acwing.com/activity/content/introduction/2487/group_buy/119074/


活动打卡代码 AcWing 176. 装满的油箱

故人倾
12天前

每个点有两个属性,u,c。当前点u和当前的还剩下的油量c。
dist[u][c]代表的是当前点的花费
还有一点,当前点可以更新两类问题:
加1L油(u,c+1),
或者通过当前边,消耗一定量的油更新别的点
问,为为什么只更新加1L油,明明可以加1,2,3,4..这么多的。
是的,当然没问题,但是这样的话,加边会很多,会产生很多点重复入队。因为是按照当前花费的小根堆,后续加油也会加进来的。

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

using namespace std;
const int N = 1e3 + 10, M = 2e4 + 10;
int h[N], e[M], w[M], ne[M], idx;
int dist[N][N],price[N],m,n;
bool st[N][N];
struct node
{
    int d,u,c;//d代表从起点到当前点u的花费,c代表当前还剩余的油量
    bool operator> (const node &t)const
    {
        return t.d < d;
    }
};
void add(int a, int b, int c)  // 添加一条边a->b,边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra(int C,int S,int E)
{
    priority_queue<node,vector<node>,greater<node> > q;
    memset(st, 0, sizeof st);
    memset(dist,0x3f,sizeof dist);
    q.push({0,S,0});
    dist[S][0] = 0;
    while(q.size())
    {
        node t = q.top();
        q.pop();
        if(t.u == E)return t.d;
        if(st[t.u][t.c])continue;
        st[t.u][t.c] = true;
        if(t.c < C)
        {
            if(dist[t.u][t.c] + price[t.u] < dist[t.u][t.c + 1])
            {
                dist[t.u][t.c + 1] = dist[t.u][t.c] + price[t.u];
                q.push({dist[t.u][t.c + 1],t.u,t.c + 1});
            }
        }
        for(int i = h[t.u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(t.c - w[i] >= 0)
            {
                dist[j][t.c-w[i]] = min(dist[j][t.c-w[i]], t.d);
                q.push({t.d,j,t.c - w[i]});
            }
        }
    }
    return -1;
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)cin >> price[i];
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a, b,c);
        add(b,a,c);
    }
    int k;
    cin >> k;
    while(k --)
    {
        int C,S,E;
        cin >> C >> S >> E;
        int t = dijkstra(C,S ,E);
        if(t == -1)puts("impossible");
        else cout << t << endl;
    }
}


活动打卡代码 AcWing 456. 车站分级

故人倾
13天前

本质上也是差分约束,最后求个最大值,但是这题建图会爆掉
所以我们优化一下,对于每次建图找一个虚拟中间点,因为你最终的目的就是要a->b连接一条边,现在有了拓扑排序,跑最长路比较快,所以建立一个中间点,虽然跑最长路浪费了点时间,但是建图省了很多空间

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e3 + 10, M = 1e6 + 10;
int n,m,q[N],hh = 0, tt = -1,d[N],dist[N];
int h[N], e[M],w[M], ne[M], idx;
bool st[N];
void add(int a, int b,int c)  // 添加一条边a->b
{
    e[idx] = b,w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    d[b] ++;
}
void topsort()
{
    for(int i = 1; i <= n + m; i ++)
    {
        if(!d[i])q[++tt] = i;
    }
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(--d[j] == 0)q[++tt] = j;
        }
    }
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i ++ )
    {
        int cnt,start = n, end = 1;
        cin >> cnt;
        memset(st, 0, sizeof st);
        while(cnt --)
        {

            int x;
            cin >> x;
            start = min(start,x);
            end = max(end,x);
            st[x] = true;
        }
        int ver = n + i;
        for(int j = start; j <= end; j ++)
        {
            if(!st[j])add(j,ver,0);
            else add(ver,j,1);
        }
    }
    topsort();

    for(int i = 1; i <= n ; i ++)dist[i] = 1;
    for(int t  = 0; t <= tt; t ++)
    {
        int u = q[t];
        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            dist[j] = max(dist[j],dist[u] + w[i]);
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i ++)res = max(res,dist[i]);
    cout << res;
}



活动打卡代码 AcWing 1192. 奖金

故人倾
13天前

本题本质是差分约束,但是跑spfa需要n*m复杂度,但是这个图是DAG,如果存在拓扑排序,那么就不用spfa了,直接bfs就可以,复杂度n + m

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10, M = 2e4 + 10;
int n,m,q[N],hh = 0, tt = -1,d[N],dist[N];
int h[N], e[M], ne[M], idx;

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool topsort()
{
    for(int i = 1; i <= n; i ++)
    {
        if(!d[i])q[++tt] = i;
    }
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(--d[j] == 0)q[++tt] = j;
        }
    }

    return n == tt + 1;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i ++ )
    {
        int a,b;
        cin >> a >> b;
        add(b,a);
        d[a] ++;
    }
    if(!topsort())
    {
        puts("Poor Xed");
        return 0;
    }
    for(int i = 1; i <= n; i ++)dist[i] = 100;
    for(int t  = 0; t <= tt; t ++)
    {
        int u = q[t];
        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            dist[j] = max(dist[j],dist[u] + 1);
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i ++)res += dist[i];
    cout << res;
}


活动打卡代码 AcWing 1191. 家谱树

故人倾
13天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200, M = 202;
int n,q[N],hh = 0, tt = -1,d[N];
int h[N], e[M], ne[M], idx;

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void topsort()
{
    for(int i = 1; i <= n; i ++)
    {
        if(!d[i])q[++tt] = i;
    }
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(--d[j] == 0)q[++tt] = j;
        }
    }
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {

        int x;
        while(cin >> x,x)
        {
            add(i,x);
            d[x] ++;
        }
    }
    topsort();

    for(int i = 0; i <= tt; i ++)cout << q[i] <<" ";
}