头像

Yoh




在线 


最近来访(3)
用户头像
xiaoling
用户头像
Kenshin


Yoh
2天前

include[HTML_REMOVED]

using namespace std;

const int N = 1e6+10;

int q[N];

int n;

void quick_sort(int q[],int l,int r){

if(l>=r) return;

int x=q[l] ,i=l-1,j=r+1;

while(i<j){

    do i++; while(q[i]<x);
    do j--; while(q[j]>x);
    if(i<j) swap(q[i],q[j]);
}

quick_sort(q,l,j);
quick_sort(q,j+1,r);

}

int main(){
cin>>n;

for(int i=0;i<n;i++){
    cin>>q[i];
}

quick_sort(q,0,n-1);

for(int i=0;i<n;i++){
    cout<<q[i];
}

return 0;

}



活动打卡代码 AcWing 901. 滑雪

Yoh
5个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 1000;
int mp[N][N];
int a[N][N];
int m, n;
int dir[4][2] = {0,1,1,0,-1,0,0,-1};
int dfs(int x, int y){
    if(mp[x][y] != -1) return mp[x][y];
    mp[x][y] = 1;
    for(int i = 0; i < 4; i ++){
        int nx = x + dir[i][0], ny = y + dir[i][1];
        if(nx > 0 && nx <= m && ny > 0 && ny <= n){
            if(a[nx][ny] < a[x][y]) mp[x][y] = max(dfs(nx, ny) + 1, mp[x][y]);
        } 
    }

    return mp[x][y];
}
int main(){
    memset(mp, -1, sizeof(mp));
    cin >> m >> n;
    for(int i = 1; i <= m; i ++){
        for(int j = 1; j <= n; j ++){
            cin >> a[i][j];
        }
    }

    int res = 0;
    for(int i = 1; i <= m; i ++){
        for(int j = 1; j <= n; j ++){
            res = max(res, dfs(i, j));
            //cout << mp[i][j] << " ";
        }
        //cout << endl;
    }
    cout << res << endl;
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;

int ne[N], e[N], h[N], idx;
int hp[N];
int dp[N][2];
bool fat[N];

void init(){
    memset(fat, false, sizeof(fat));
    idx = 0;
    memset(h, -1, sizeof(h));
}

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

void dfs(int u){
    dp[u][1] = hp[u];

    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        dfs(j);

        dp[u][1] += dp[j][0];
        dp[u][0] += max(dp[j][0], dp[j][1]);
    }
}

int main(){
    init();
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> hp[i];
        //cout << i << hp[i] << endl;
    }
    int a, b;
    for(int i = 0; i < n - 1; i ++){
        cin >> a >> b;
        add(b, a);
        fat[a] = true;
    }

    int root = 1;
    while(fat[root]) root ++;
    //cout << root << endl;
    dfs(root);

    cout << max(dp[root][0], dp[root][1]);

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int e[2 * N], ne[2 * N], h[N], idx, n;
int ans = N;
bool st[N];
void init(){
    idx = 0;
    memset(h, -1, sizeof(h));
    memset(st, false, sizeof(st));
}

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

int dfs(int u){
    st[u] = true;
    int sum = 0, res = 0;
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(st[j]) continue;

        int s = dfs(j);
        res = max(s, res);
        sum += s;
    }

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

    return (sum + 1);
}

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

    int a, b;
    for(int i = 0; i < n - 1; i ++){
        scanf("%d %d", &a, &b);
        add(a, b);
        add(b, a);
    }

    dfs(1);

    cout << ans << endl;

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 826. 单链表

Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int ne[N], e[N], head, idx;
void init(){
    head = -1;
    idx = 0;
}
void add(int x){
    ne[idx] = head;
    e[idx] = x;
    head = idx;
    idx ++;
}

void insert(int k, int x){
    ne[idx] = ne[k];
    ne[k] = idx;
    e[idx] = x;
    idx ++;
}

void remove(int k){
    ne[k] = ne[ne[k]];
}
int main(){
    int n;
    cin >> n;
    init();

    while(n --){
        char ch;
        cin >> ch;
        if(ch == 'H'){
            int x;
            cin >> x;
            add(x);
        }
        else if(ch == 'I'){
            int k, x;
            cin >> k >> x;
            insert(k - 1, x);
        }
        else{
            int k;
            cin >> k;
            if(k == 0) head = ne[head];
            else remove(k - 1);
        }
    }

    for(int i = head; i != -1; i = ne[i]) cout << e[i] << " ";

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int son[31 * N][2], idx, a[N];

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

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

    return res;
}

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

    int res = 0;
    for(int i = 0; i < n; i ++){
        res = max(res, query(a[i]));
        insert(a[i]);
    }

    cout << res << endl;
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;

int a[1000010], b[1000010], mp[1000010];
int main(){
    int n;
    cin >> n;

    for(int i = 1; i <= n; i ++){
        scanf("%d", &a[i]);
        mp[a[i]] = i;
    }
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &b[i]);
        if(mp[b[i]]) b[i] = mp[b[i]];
        else b[i] = 0;
        //cout << b[i] << " ";
    }

    vector<int> aa;
    for(int i = 1; i <= n; i++){
        if(b[i] == 0) continue;
        if(aa.size() == 0 || b[i] > aa.back()) aa.push_back(b[i]);
        int idx = lower_bound(aa.begin(), aa.end(), b[i]) - aa.begin();
        aa[idx] = b[i];
    }

    cout << aa.size() << endl;
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 802. 区间和

Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int x[400010],c[400010];
int r[400010],l[400010];
int sum[400010];

int find(int num){
    return lower_bound(v.begin(), v.end(), num) - v.begin();
}

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n ; i ++){
        cin >> x[i] >> c[i];
        v.push_back(x[i]);
    }
    for(int i = 0; i < m; i ++){
        cin >> l[i] >> r[i];
        v.push_back(l[i]);
        v.push_back(r[i]);
    }
    v.push_back(-2e9);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for(int i = 0; i < n ; i++) sum[find(x[i])] += c[i];

    int len = v.size();
    for(int i = 1; i <= len; i ++) sum[i] += sum[i - 1];

    for(int i = 0; i < m; i ++) cout << sum[find(r[i])] - sum[find(l[i]) - 1] << endl;

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 282. 石子合并

Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;

int a[310], s[310], dp[310][310];
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }

    for(int len = 2; len <= n ; len ++){
        for(int i = 1; i + len - 1 <= n; i ++){
            int j = i + len - 1;
            dp[i][j] = 1e8;
            for(int k = i; k <= j; k ++){
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }

    cout << dp[1][n] << endl;

    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 835. Trie字符串统计

Yoh
6个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;

int son[N][26], cnt[N], idx;

void insert(char str[]){
    int p = 0;
    for(int i = 0; str[i]; i ++){
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }

    cnt[p] ++;
}

int query(char str[]){
    int p = 0;
    for(int i = 0; str[i]; i ++){
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }

    return cnt[p];
}

char str[N];
int main(){
    int qnum;
    cin >> qnum;
    while(qnum --){
        char ch[2];
        scanf("%s%s",ch,str);
        if(ch[0] == 'I'){
            insert(str);
        }
        else cout << query(str) << endl;
    }

    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~