头像

RealDish


访客:151

离线:2小时前


活动打卡代码 AcWing 240. 食物链

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

const int N = 200010;

int food[N], n, k, d, x, y;

void init_set(){
    for(int i = 0; i <= 3 * n; i++)
        food[i] = i;
}

int find_set(int x){
    return x == food[x] ? x : food[x] = find_set(food[x]);
}

void merge_set(int x, int y){
    x = find_set(x);
    y = find_set(y);
    if( x == y )return ;
    food[x] = y;
}

int main(){
    cin >> n >> k;
    int ans = 0;
    init_set();
    for(int i = 1; i <= k; i++){
        cin >> d >> x >> y;
        if(x > n || y > n || x < 1 || y < 1)ans++;
        else if(d == 1){
            if( find_set(x) == find_set(y + n) || find_set(x) == find_set(y + 2 * n) )ans++;
            else{
                merge_set(x, y);
                merge_set(x + n, y + n);
                merge_set(x + 2 * n , y + 2 * n);
            }
        }else{
            if( x == y || find_set(x) == find_set(y) || find_set(x) == find_set(y + n)){
                ans++;
            }else{
                merge_set(x, y + 2 * n);
                merge_set(x + n, y);
                merge_set(x + 2 * n , y + n);
            }
        }
    }
    cout << ans << endl;
    return 0 ;
}


活动打卡代码 AcWing 238. 银河英雄传说

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

const int N = 30010;
int uset[N], b[N],usize[N];

void init_set(){
    for(int i = 0 ; i <= N; i++)
    {
        uset[i] = i;
        b[i] = 0;
        usize[i] = 1;
    }
}

int find_set(int x){
    if( x == uset[x] )return x;
    int root = find_set(uset[x]);
    b[x] += b[uset[x]];
    return uset[x] = root;
}

void merge_set(int x, int y){
    x = find_set(x);
    y = find_set(y);
    if(x == y)return;
    uset[x] = y;
    b[x] = usize[y];
    usize[y] += usize[x];
}

int main(){
    int t;
    scanf("%d\n", &t);
    char op; int x, y;
    init_set();
    while(t--){
        op = getchar();
        scanf("%d %d\n",&x, &y);
        if(op == 'M'){
            merge_set(x, y);
        }else if(op == 'C'){
            int a = find_set(x), c = find_set(y);
            if( a == c )cout << abs(b[x] - b[y]) - 1 << endl;
            else cout << "-1" << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 237. 程序自动分析

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

const int N = 2e6 + 10;

int b[N], t, n, c[N],sizec,sizeb,uset[N];
bool flag;
struct node{
    int x, y, e;
}a[N];

void discrete(){
    sort(c + 1,c + sizec + 1);
    for(int i = 1; i <= sizec;i++){
        if(i == 1 || c[i] != c[i - 1])
            b[++sizeb] = c[i]; 
    }
}

void init_set(){
    for(int i = 0 ; i <= sizeb ;i ++)
        uset[i] = i;
}

int find_set(int x)
{
    return (x == uset[x])? x : uset[x] = find_set(uset[x]);
}

void merge_set(int x, int y){
    x = find_set(x);
    y = find_set(y);
    if( x != y ){
        uset[x] = y;
    }
}

int query(int x){
    return lower_bound(b + 1,b + 1 + sizeb,x) - b;
}

bool cmp(node a, node b){
    return a.e > b.e;
}

int main(){
    cin >> t;
    while(t--){
        cin >> n;
        sizec = 0, sizeb = 0 ,flag = true;
        memset(b, 0,sizeof(b));
        memset(c, 0,sizeof(c));
        memset(uset,0,sizeof(uset));
        memset(a, 0, sizeof(a));
        for(int i = 1 ;i <= n;i++){
            cin >> a[i].x >> a[i].y >> a[i].e;
            c[++sizec] = a[i].x;
            c[++sizec] = a[i].y;
        }
        discrete();
        for (int i = 1; i <= n; ++i) {
            a[i].x = query(a[i].x);
            a[i].y = query(a[i].y);
        }
        init_set();
        sort(a + 1, a + 1 + n, cmp);
        for(int i = 1 ;i <= n;i++){
            int u = find_set(a[i].x), v = find_set(a[i].y);
            if(a[i].e == 1)merge_set(u, v);
            else if(u == v){
                printf("NO\n");
                flag = 0;
                break;
            }
        }
        if(flag)printf("YES\n");
    }
    return 0;
}




/*
滑动窗口——经典利用单调队列解决,用一个dequeue双端队列维护一个单调队列,队列中存储数组的索引
存储索引便于判断滑动窗口是否超出滑过而弹出队头元素
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int N = 1000010;
int a[N];
deque<int>windowslide;
int n, k;

void findMin(){
    //维护一个单调递减队列, 使得队头始终为滑动窗口的最小值
    windowslide.clear();
    for(int i = 0; i < n; i++){
        while( !windowslide.empty() && a[windowslide.back()] > a[i] )windowslide.pop_back();
        //若windowslide不满足单调递增,则弹出队尾元素
        while( !windowslide.empty() && i - windowslide.front() >= k )windowslide.pop_front();
        //若windowslide已滑过,则弹出队头一个元素
        windowslide.push_back(i);//添加元素
        if(i >= k - 1)cout << a[windowslide.front()] << ' ' ;//输出
    }
}

void findMax(){
    //维护一个单调递减队列, 使得队头始终为滑动窗口的最大值
    windowslide.clear();
    for(int i = 0; i < n; i++){
        while( !windowslide.empty() && a[windowslide.back()] < a[i])windowslide.pop_back();
        //若windowslide不满足单调递减,则弹出队尾元素
        while( !windowslide.empty() && i - windowslide.front() >= k)windowslide.pop_front();
        //若windowslide已滑过,则弹出队头一个元素
        windowslide.push_back(i);//add
        if(i >= k - 1)cout << a[windowslide.front()] << ' ';//output
    }
}

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    findMin();//找出滑动窗口的最小值
    cout << endl;
    findMax();//找出滑动窗口的最大值
}


活动打卡代码 AcWing 154. 滑动窗口

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int N = 1000010;
int a[N];
deque<int>windowslide;
int n, k;

void findMax(){
    windowslide.clear();
    for(int i = 0; i < n; i++){
        while( !windowslide.empty() && a[windowslide.back()] > a[i] )windowslide.pop_back();
        while( !windowslide.empty() && i - windowslide.front() >= k )windowslide.pop_front();
        windowslide.push_back(i);
        if(i >= k - 1)cout << a[windowslide.front()] << ' ' ;
    }
}

void findMin(){
    windowslide.clear();
    for(int i = 0; i < n; i++){
        while( !windowslide.empty() && a[windowslide.back()] < a[i])windowslide.pop_back();
        while( !windowslide.empty() && i - windowslide.front() >= k)windowslide.pop_front();
        windowslide.push_back(i);
        if(i >= k - 1)cout << a[windowslide.front()] << ' ';
    }
}

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    findMax();
    cout << endl;
    findMin();
}


活动打卡代码 AcWing 149. 荷马史诗

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 100010;
struct node{
    LL val;
    int dept;
    node(){
        val = 0; dept = 0;
    }
};
struct cmp{
    bool operator()(const node a, const node b){
        return a.val >  b.val || (a.val == b.val && a.dept > b.dept);
    }
};
priority_queue<node, vector<node>, cmp> huffman;
node a[N];
LL ans;
int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i].val;
        huffman.push(a[i]);
    }
    while((n - 1)%(k - 1)!=0){
        node b;
        huffman.push(b);
        n++;
    }
    while(huffman.size() > 1){
        node mid; int dp;
        for(int i = 0; i < k; i++){
            mid.val += huffman.top().val;
            dp = max(dp, huffman.top().dept);
            huffman.pop();
        }
        mid.dept = dp + 1;
        huffman.push(mid);
        ans += mid.val;
    }
    cout << ans << '\n' << huffman.top().dept << endl;
    return 0;
}


活动打卡代码 AcWing 145. 超市

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int N = 10010;
typedef pair<int, int> PII;

int main(){
    int n;
    while(cin >> n){
        vector<PII> products(n);
        for(int i = 0; i < n; i++){
            cin >> products[i].second >> products[i].first;
        }
        sort(products.begin(), products.end());
        priority_queue<int,vector<int>, greater<int> > heap;
        for(auto goods : products){
            heap.push(goods.second);
            if(heap.size() > goods.first)heap.pop();
        }
        int ans = 0;
        while(!heap.empty()){
            ans += heap.top();
            heap.pop();
        }
        cout << ans << endl;
    }
}



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

const int N = 100010, M = 4e6 + 50;
int son[M][2], a[N], idx;
int u, v, w;

void insert(int x){
    int p = 0;
    for(int i = 30; ~i; i--){
        int &s = son[p][x >> i & 1];
        if(!s) s = ++idx;
        p = s;
    }
}

int query(int x){
    int p = 0, cnt = 0;
    for(int i = 30; ~i; i--){
        int s = x >> i & 1;
        if(son[p][!s]){
            cnt += 1 << i;
            p = son[p][!s];
        }else p = son[p][s];
    }
    return cnt;
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> u >> v >> w ;
        a[v] = a[u] ^ w;
    }
    for(int i = 0; i < n; i++){
        insert(a[i]);
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        ans = max(ans, query(a[i]));
    }
    cout << ans << endl;
}


活动打卡代码 AcWing 143. 最大异或对

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

const int N = 100010, M = 4000050;
int pos;
int son[M][2], a[N];

void insert(int x){
    int p = 0;
    for(int i = 30; ~i; i--){
        int &s = son[p][x >> i & 1];
        if(!s)s = ++pos;
        p = s;
    }
}

int query(int x){
    int p = 0, res = 0;
    for(int i = 30; ~i; i--){
        int s = x >> i & 1;
        if(son[p][!s]){
            res += 1 << i;
            p = son[p][!s];
        }else p = son[p][s];
    }
    return res;
}

int main(){
    int n, ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        insert(a[i]);
    }
    for(int i = 1; i <= n; i++){
        ans = max(ans, query(a[i]));
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 101. 最高的牛

/*

因为这题中除最高的牛已知身高,其余的身高均未知。所以可以假设所有的牛与最高的牛身高相同。假设均为 h 
1、朴素方法:
开一个数组并初始化全为身高为h的牛。给出一对关系(i , j)表示牛i与牛j可以相互看到,即中间的牛严格比i和j小。
若此前未给出(i, j)的关系对,即将(i , j)中间的牛[i + 1 ~ j - 1] - 1
复杂度分析:若给出 M 个关系对,平均处理长度为 N。处理牛的复杂度O(N), O(N * M)

2、差分序列:
使用一个差分数组处理, 在朴素方法上处理中间牛的方法简化,只需要在c[i + 1]上加1,c[j]减一。
则可以达到(i , j)中间的牛[i + 1 ~ j - 1] - 1 的同样效果。
复杂度分析:若给出 M 个关系对,平均处理长度为 N 。处理牛的复杂度O(1), O(M)

*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;

const int N = 10010;//牛的最多多少个
int c[N];//牛的差分序列
map<pair<int,int>, bool>existed;//判断关系对是否存在重复

int main(){
    int n, p, h, m;
    cin >> n >> p >> h >> m;
    memset(c, 0, sizeof(c));
    for(int i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        if(a > b)swap(a , b);//保证a比b小,即(a, b)是有效的
        if(existed[make_pair(a, b)])continue;//若关系对之前已判断则不需要再处理
        c[a + 1]--, c[b]++;//处理c[i + 1 ~ j - 1]的牛
        existed[make_pair(a, b)] = true;
    }
    for(int i = 1; i <= n; i++){
        c[i] += c[i - 1];
        cout << h + c[i] << endl;
    }
    return 0;
}