头像

acw_yxy




离线:22小时前



acw_yxy
1个月前

最长递增子序列

$O(nlogn)$

可以求出子序列

C++ 代码

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        // 简单的线性dp
        int n = arr.size();

        vector<int> f(n+1); // 记录对应长度对应的数
        vector<int> maxlen;
        int len = 0;
        for(int i = 0; i < n; i ++)
        {
            int l = 0, r = len;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(f[mid] < arr[i]) l = mid; // 可能就是这个数比他小
                else r = mid - 1;
            }
            len = max(len, r + 1);
            f[r+1] = arr[i];
            maxlen.push_back(r+1); // 加入一个长度
        }
        // 贪心的方法来确定最长序列
        int tem = len;
        for(int i = n - 1; len > 0; i --)
        {
            if(maxlen[i] == len)
                f[--len] = arr[i]; 
        }
        return vector<int>(f.begin(), f.begin()+tem);
    }
};



acw_yxy
1个月前
// 染色法判定二分图
#include <iostream>
#include <cstring>
using namespace std;
int n, m;
// n和m都比较大,邻接表
const int N = 1e5+10, M = 2e5+10;
int h[N], e[M], ne[M], idx = 0;
int color[N]; // 每个点的颜色

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

bool dfs(int l, int c)
{
    color[l] = c;
    for(int i = h[l]; ~i; i = ne[i])
    {
        int a = e[i];
        if(color[a])
        {
            if(color[a] == c) 
                return false;
        }
        else if(!dfs(a, 3 - c)) return false;
    }
    return true;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m --)
    {
        int a, b;
        cin >> a >> b;
        if(a == b) continue;
        add(a, b), add(b, a);
    }

    // 二分图可能是没有连着的图,所以这里每个点都可能从头开始,只要没有奇数环就行了
    bool flag = true;
    for(int i = 1; i <= n; i ++)
    {
        if(!color[i])
        {
            if(!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }
    }

    if(flag) cout << "Yes";
    else cout << "No";

    return 0;
}


活动打卡代码 AcWing 3227. 折点计数

acw_yxy
1个月前
#include <iostream>

using namespace std;
const int N = 1010; 
int f[N];

int main()
{
    int n, ans = 0;
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> f[i];

    for(int i = 1; i < n - 1; i ++)
    {
        if(f[i] - f[i-1] > 0 && f[i+1] - f[i] < 0) ans ++;
        if(f[i] - f[i-1] < 0 && f[i+1] - f[i] > 0) ans ++;
    }
    cout << ans;
    return 0;
}



acw_yxy
1个月前
// 染色法判定二分图
#include <iostream>
#include <cstring>
using namespace std;
int n, m;
// n和m都比较大,邻接表
const int N = 1e5+10, M = 2e5+10;
int h[N], e[M], ne[M], idx = 0;
int color[N]; // 每个点的颜色

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

bool dfs(int l, int c)
{
    color[l] = c;
    for(int i = h[l]; ~i; i = ne[i])
    {
        int a = e[i];
        if(color[a])
        {
            if(color[a] == c) 
                return false;
        }
        else if(!dfs(a, 3 - c)) return false;
    }
    return true;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m --)
    {
        int a, b;
        cin >> a >> b;
        if(a == b) continue;
        add(a, b), add(b, a);
    }

    // 二分图可能是没有连着的图,所以这里每个点都可能从头开始,只要没有奇数环就行了
    bool flag = true;
    for(int i = 1; i <= n; i ++)
    {
        if(!color[i])
        {
            if(!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }
    }

    if(flag) cout << "Yes";
    else cout << "No";

    return 0;
}

```



活动打卡代码 AcWing 3232. 最大波动

acw_yxy
1个月前
#include <iostream>

using namespace std;
const int N = 1010;
int f[N];

int main()
{
    int n, res = 0;
    cin >> n;

    for(int i = 0; i < n; i ++)
    {
        cin >> f[i];
        if(i) res = max(res, abs(f[i] - f[i-1]));
    }
    cout << res;
    return 0;
}




acw_yxy
1个月前
// 先排序在一条边一条边的加 并查集也可以用
// 不得不说vector是真的慢
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 2e5+10;
vector<vector<int>> edge; // 用来存边
int p[N / 2];
int n, m, sum;

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> m;

    for(int i = 1; i <= n; i ++)
        p[i] = i;

    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edge.push_back({c, a, b});
    }

    sort(edge.begin(), edge.end());

    int num = 1;
    for(int i = 0; i < edge.size(); i ++)
    {
        int a = edge[i][1], b = edge[i][2], c = edge[i][0];
        if(find(a) == find(b)) continue;
        sum += c;
        num ++;
        p[find(a)] = find(b);
    }
    if(num == n) cout << sum;
    else cout << "impossible";
    return 0;
}



acw_yxy
1个月前

克鲁斯卡尔

$O(nlogn)$

C++ 代码

// 先排序在一条边一条边的加 并查集也可以用
// 不得不说vector是真的慢
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 2e5+10;
vector<vector<int>> edge; // 用来存边
int p[N / 2];
int n, m, sum;

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> m;

    for(int i = 1; i <= n; i ++)
        p[i] = i;

    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edge.push_back({c, a, b});
    }

    sort(edge.begin(), edge.end());

    int num = 1;
    for(int i = 0; i < edge.size(); i ++)
    {
        int a = edge[i][1], b = edge[i][2], c = edge[i][0];
        if(find(a) == find(b)) continue;
        sum += c;
        num ++;
        p[find(a)] = find(b);
    }
    if(num == n) cout << sum;
    else cout << "impossible";
    return 0;
}



acw_yxy
1个月前
// 这个算法和dijkstra算法很像,只不过把距离最初点的距离变成了距离整个点集合的距离
#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, M = 200010, md = 0x3f3f3f3f;

int e[M], ne[M], h[N], idx = 0; // 邻接表
int w[N][N], dist[N]; // 边权重数组, 点距离集合的数组
int sum, n, m;
bool st[N];
// 插入邻接表头指针
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;     
}

bool prim()
{
    // n个点要进行n次
    for(int i = 1; i <= n; i ++)
    {
        int t = -1; // 此时没有任何节点被选中
        for(int j = 1; j <= n; j ++ )
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }

        if(t != 1 && dist[t] == md)
            return false;

        if(t != 1) sum += dist[t];
        st[t] = true; // 这个点已经加进来了
        // 用找到的最小的点去更新距离
        for(int j = h[t]; j != -1; j = ne[j])
        {
            int a = e[j]; // 头节点
            dist[a] = min(dist[a], w[t][a]);
        }
    }
    return true;
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);
    memset(dist, 0x3f, sizeof dist);
    memset(w, 0x3f, sizeof w);

    // 读取所有边
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if(w[a][b] == md) add(a, b), add(b, a);
        w[b][a] = w[a][b] = min(w[a][b], c);
    }

    if(prim()) cout << sum;
    else cout << "impossible";
    return 0;
}



acw_yxy
1个月前

prim邻接表做法

(prim) $O(n^2)$

C++ 代码

// 这个算法和dijkstra算法很像,只不过把距离最初点的距离变成了距离整个点集合的距离
#include <iostream>
#include <cstring>
using namespace std;

const int N = 510, M = 200010, md = 0x3f3f3f3f;

int e[M], ne[M], h[N], idx = 0; // 邻接表
int w[N][N], dist[N]; // 边权重数组, 点距离集合的数组
int sum, n, m;
bool st[N];
// 插入邻接表头指针
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;     
}

bool prim()
{
    // n个点要进行n次
    for(int i = 1; i <= n; i ++)
    {
        int t = -1; // 此时没有任何节点被选中
        for(int j = 1; j <= n; j ++ )
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }

        if(t != 1 && dist[t] == md)
            return false;

        if(t != 1) sum += dist[t];
        st[t] = true; // 这个点已经加进来了
        // 用找到的最小的点去更新距离
        for(int j = h[t]; j != -1; j = ne[j])
        {
            int a = e[j]; // 头节点
            dist[a] = min(dist[a], w[t][a]);
        }
    }
    return true;
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);
    memset(dist, 0x3f, sizeof dist);
    memset(w, 0x3f, sizeof w);

    // 读取所有边
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if(w[a][b] == md) add(a, b), add(b, a);
        w[b][a] = w[a][b] = min(w[a][b], c);
    }

    if(prim()) cout << sum;
    else cout << "impossible";
    return 0;
}


活动打卡代码 AcWing 458. 比例简化

acw_yxy
1个月前
#include <iostream>

using namespace std;

int main()
{
    int A, B, L;
    int a, b;

    double delta = 1e9;
    cin >> A >> B >> L;
    // A B 均不大于L,直接枚举一下就完事了 1e4的时间复杂度
    for (int i = 0; i <= L; i ++ )
        for (int j = 1; j <= L; j ++ )
        {
            double x = (double)i / j;
            double X = (double)A / B;
            if (x >= X && x - X < delta)
            {
                delta = x - X;
                a = i, b = j;
            }
        }

    cout << a << ' ' << b << endl;
    return 0;
}