头像

CYa想要速通

UCL统计


访客:5712

离线:1小时前


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

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

const int N=1e5+10;

//用链表结构存储每个点的边

int h[N];   //h[]用于存储每个点的头节点
int e[2*N];   //用于存储元素    因为是无向图 所以是双向边 应该乘2
int ne[2*N];    //存储链表的next值
int idx=0;
int n;
int ans=N;  //记录重心子树的最小值

bool st[N];  //记录该点是否已经查找过

void add(int a,int b)       //将b插入a中 a作为根 所以处在链表的最后
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int dfs(int u)       //dfs过程寻找根的连通的点
{
    int size=0;    //存放连通块中点的个数的最大值

   st[u]=true;  //  该点已经走过

   int sum=0;       //sum用于记录根子树的个数

   for(int i=h[u];i!=-1;i=ne[i])
   {
       int j=e[i];
       if(!st[j])
       { 
            int s=dfs(j);
            size=max(size,s);
            sum+=s;
       }
   }
   size=max(size,n-sum-1);  //通过画图可得n-m 即总的节点-根的子树 即为剩余的连通节点值
                            //而size为当前为根的子树的个数 通过比较确认连通块中点的最大数
    ans=min(ans,size); 
   return sum+1;        //return sum+1 是因为sum初始化为0 而当前这个点即根也算是该连通块内的一点

}

int main()
{   
    memset(h,-1,sizeof h);  //初始化h[]表 -1表示空

    scanf("%d",&n);



    for(int i=0;i<n-1;i++)  //注意这里应该n-1,
    {               //有些奇怪但是 仔细想想就明白 n是表示点的个数 而每行是输入两个点之间的边所以只需输入n-1行即可
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs(1);


    cout<<ans<<endl;


    return 0;
}


新鲜事 原文

试一下iPadOs笔写输入效果
今日一读:贾扬清的故事也有点太顶了。(Caffe创始人tensor flor贡献者等)
清华出来的学霸都是上帝派来的指引者么



#include<bits/stdc++.h>
using namespace std;
int dp[1000050];
int main()
{
    int n,a[1000050];
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>a[i];
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<=i;++j){
            if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);
        }
    }
    int ans=-1;
    for(int i=0;i<n;++i)ans=max(ans,dp[i]);
    cout<<ans+1;
    return 0;
}



111.PNG




题目描述

只能进行一次交易(买+卖),要求使利润最大。输出这个最大利润

样例

[7,1,5,3,6,4]
Output: 5

算法1

(DP 贪心) $O(n)$

C++ 代码

int maxProfit(vector<int> &prices) {
    int maxPro = 0;
    int minPrice = INT_MAX;
    for(int i = 0; i < prices.size(); i++){
        minPrice = min(minPrice, prices[i]);
        maxPro = max(maxPro, prices[i] - minPrice);
    }
    return maxPro;
}

Kadane’s Algorithm

更通用版本
计算prices[i] - prices[i-1] 然后找到一个连续含利润最大值的子数列,
如果maxCur 小于0,重置到0。
1. calculate the difference (maxCur += prices[i] - prices[i-1]) of the original array,
2. and find a contiguous subarray giving maximum profit.
3. If the difference falls below 0, reset it to zero.

int maxProfit(vector<int> &prices) {
        int maxCur = 0, maxSoFar = 0;
        for(int i = 1; i < prices.size(); i++) {
            maxCur = max(0, maxCur += prices[i] - prices[i-1]);
            maxSoFar = max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }



题目描述

只能进行一次交易(买+卖),要求使利润最大。输出这个最大利润

样例

[7,1,5,3,6,4]
Output: 5

算法1

(DP 贪心) $O(n)$

C++ 代码

int maxProfit(vector<int> &prices) {
    int maxPro = 0;
    int minPrice = INT_MAX;
    for(int i = 0; i < prices.size(); i++){
        minPrice = min(minPrice, prices[i]);
        maxPro = max(maxPro, prices[i] - minPrice);
    }
    return maxPro;
}

Kadane’s Algorithm

更通用版本
计算prices[i] - prices[i-1] 然后找到一个连续含利润最大值的子数列,
如果maxCur 小于0,重置到0。
1. calculate the difference (maxCur += prices[i] - prices[i-1]) of the original array,
2. and find a contiguous subarray giving maximum profit.
3. If the difference falls below 0, reset it to zero.

int maxProfit(vector<int> &prices) {
        int maxCur = 0, maxSoFar = 0;
        for(int i = 1; i < prices.size(); i++) {
            maxCur = max(0, maxCur += prices[i] - prices[i-1]);
            maxSoFar = max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }


活动打卡代码 AcWing 839. 模拟堆

指针定义

堆排序-指代.PNG

交换过程演示

堆排序-交换.PNG

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

const int N = 100010;
int h[N], ph[N], hp[N], Size;
//详见图解,就是指针和堆里面对应的互换,
void heap_swap(int a, int b){
    swap(ph[hp[a]], ph[hp[b]]); // ph 第一是 p指针 指向 h堆。
    swap(hp[a], hp[b]); //注: hp 意思是h堆 指向 p 指针,
    swap(h[a], h[b]); //之前写错了不小心写成swap(a,b)了 实际应是换堆里的元素,h[a]与h[b]
}

void down(int u){
    int Min = u;
    if (u * 2 <= Size && h[u * 2] < h[Min]) Min = u * 2; 
    //判断有左二子 2x比总大小小,并且判断左二子小于t,那么t等于左二子
    if (u * 2 + 1 <= Size && h[u * 2 + 1] < h[Min]) Min = u * 2 + 1;
    if (u != Min){ //跟根节点比一下谁是最小值
        heap_swap(u, Min);
        down(Min);
    }
}

void up(int u){
    while (u / 2 && h[u / 2] > h[u]){
        heap_swap(u / 2, u);
        u /= 2;
    }
}


int main(){
    int n, m = 0;
    scanf("%d", &n);
    while (n--){
        char op[10];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I")){
            scanf("%d", &x);
            h[++Size] = x;
            m++;
            ph[m] = Size, hp[Size] = m;
            up(Size);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if(!strcmp(op, "DM")){
            heap_swap(1, Size);
            Size --;
            down(1);
        }
        else if(!strcmp(op, "D")) {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, Size--);
            down(k), up(k);
        }
        else{
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }


        /*for (int i = n / 2; i > 0; i--) down(i); //O(n) 递推。从n/2 down到1 
        printf("%d ", h[1]);
        h[1] = h[Size];
        Size --;
        down(1); 上一题输出的最小值 */
    }
    return 0;
}


新鲜事 原文

记录一下键盘上 `INS` 即 `DEL`键上面那个,是切换`|`光标和`_`光标,前者输入时插入,后者输入时修改_所对应的(即当前)数


活动打卡代码 AcWing 838. 堆排序

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], Size;

void down(int u){
    int Min = u;
    if (u * 2 <= Size && h[u * 2] < h[Min]) Min = u * 2; 
    //判断有左二子 2x比总大小小,并且判断左二子小于t,那么t等于左二子
    if (u * 2 + 1 <= Size && h[u * 2 + 1] < h[Min]) Min = u * 2 + 1;
    if (u != Min){ //跟根节点比一下谁是最小值
        swap(h[u], h[Min]);
        down(Min);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    Size = n;
    for (int i = n / 2; i > 0; i--) down(i); //O(n) 递推。从n/2 down到1 
    while (m--){
        printf("%d ", h[1]);
        h[1] = h[Size];
        Size --;
        down(1);
    }
    return 0;
}



题目描述

在无限的平面上,机器人最初位于 (0, 0) 处,面朝北方。机器人可以接受下列三条指令之一:

“G”:直走 1 个单位
“L”:左转 90 度
“R”:右转 90 度
机器人按顺序执行指令 instructions,并一直重复它们。

只有在平面中存在环使得机器人永远无法离开时,返回 true。否则,返回 false。

样例

输入:"GGLLGG"
输出:true
解释:
机器人从 (0,0) 移动到 (0,2),转 180 度,然后回到 (0,0)。

算法1

(模拟) $O(N)$

Starting at the origin and face north (0,1),
after one sequence of instructions,

执行一次后的两种情况

  1. if chopper return to the origin, he is obvious in an circle.
  2. if chopper finishes with face not towards north, it will get back to the initial status in another one or three sequences.

Explanation

(x,y) is the location of chopper.
d[i] is the direction he is facing. 注意这里指的是他朝的方向而不是坐标
i = (i + 1) % 4 will turn right
i = (i + 3) % 4 will turn left
Check the final status after instructions.

Python 代码

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        x, y, dx, dy = 0, 0, 0, 1
        for i in instructions:
            if i == 'R': dx, dy = dy, -dx
            if i == 'L': dx, dy = -dy, dx
            if i == 'G': x, y = x + dx, y + dy
        return (x, y) == (0, 0) or (dx, dy) != (0,1)

算法2

C++ 代码

bool isRobotBounded(string instructions) {
        int x = 0, y = 0, i = 0;
        vector<vector<int>> d = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}};
        for (char & ins : instructions)
            if (ins == 'R')
                i = (i + 1) % 4;
            else if (ins == 'L')
                i = (i + 3) % 4;
            else
                x += d[i][0], y += d[i][1];
        return x == 0 && y == 0 || i > 0;
    }