头像

J_blake




离线:5小时前


活动打卡代码 AcWing 842. 排列数字

J_blake
15小时前
#include <iostream>

using namespace std;
const int N = 100010;
int h[N], n;
bool st[N];

void dfs(int u){                                                // h[]是结点,存储一位数,dfs将从该结点顺序往下搜索
    if (u == n + 1){
        for (int i = 1; i <= n; i ++)   printf("%d ",h[i]);
        puts("");
        return;
    }

    for (int i = 1; i <= n ; i ++){                                 //  st[]用来表示哪些数被用过
        if (!st[i]){
            h[u] = i;
            st[i] = true;
            dfs(u+1);
            st[i] = false;
        }
    }
}

int main(){
    cin >> n;
    dfs(1);
    return 0;
}


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

J_blake
7天前
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 100010;
int h[N], ph[N], hp[N], cnt;         // ph表示第k个插入的数对应的下标; hp表示下标idx存储的数是第几个插入的; cnt表示
                                        // 当前结点个数(下标);m表示已经插入了多少个数

void head_swap(int k1,int k2){              //head_swap传入的参数是数组的下标!
    swap(ph[hp[k1]], ph[hp[k2]]);
    swap(hp[k1], hp[k2]);
    swap(h[k1],h[k2]);
}

/*void up(int t){
      if (t/2 && h[t] < h[t/2]){                //可以用while 也可以用 递归
        head_swap(t/2,t);
        up(t >> 1);
    }
}*/


void up(int t){
    while (t/2 && h[t/2] > h[t]){
        head_swap(t/2,t);
        t >>= 1;
    }
}


void down(int t){
    int u = t;
    if (2*t <= cnt && h[2*t] < h[u])    u = 2*t;
    if (2*t+1 <= cnt && h[2*t+1] < h[u])    u = 2*t+1;
    if (u!=t)  {
        head_swap(u,t);
        down(u);
    }
}


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

    while(n--) {
        char op[5];
        int k,x;
        scanf ("%s",op);

        if (!strcmp(op,"I")){           //第I个插入的数下标是cnt,建立hp 和 ph的相互映射;
            scanf("%d",&x);
            m ++, cnt ++;
            ph[m] = cnt; hp[cnt] = m;
            h[cnt] = x;
            up(cnt);  
        }   
        else if (!strcmp(op,"PM"))      printf("%d\n",h[1]);
        else if (!strcmp(op,"DM")){
            head_swap(cnt,1);
            cnt --;
            down(1);
        }
        else if (!strcmp(op,"D")){
            scanf("%d",&k);
            k = ph[k];
            head_swap(cnt,k);
            cnt --;
            up(k);  
            down(k);
        }
        else{
            scanf ("%d%d",&k,&x);
            h[ph[k]] = x;
            up(ph[k]);
            down(ph[k]);
        }
    }
    return 0;
}



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

J_blake
8天前

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010;
int h[N], cnt;

void down(int t){
    int u = t;
    if (2*t <= cnt && h[2*t] < h[u])    u = 2*t;
    if (2*t+1 <= cnt && h[2*t+1] < h[u])     u = 2*t + 1;
    if (u != t){
        swap(h[u],h[t]);
        down(u);
    }
}

int main(){
    int n ,m;
    cin >> n >> m;
    for (int i = 1; i<= n ; i ++)    scanf("%d",&h[i]);

    cnt = n;

    for (int i = n/2; i; i--)   down(i);


    while (m--){
        printf("%d ",h[1]);
        h[1] = h[cnt--];
        down(1);
    }
    return 0;
}



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

J_blake
9天前

include [HTML_REMOVED]

using namespace std;
const int N = 50010;
int p[N], d[N], cnt;

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

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

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

int t, x ,y;
while ( m--){
    scanf("%d%d%d",&t,&x,&y);
    int px = find(x), py = find(y);

    if (x > n || y > n)
    cnt ++;

    else {
        if ( t == 1){
        if (px == py && ( d[x] - d[y] )% 3 )     cnt ++;
        else if (px != py){
            p[px] = py;
            d[px] = d[y] - d[x];
             }
        }

    else {
        if ( px == py && (d[x] - d[y] - 1) % 3)     cnt ++;
        else if (px != py){
            p[px] = py;
            d[px] = d[y] - d[x] + 1;
             }
        }
    }
}
printf("%d",cnt);
return 0;

}
```




J_blake
9天前
#include <iostream>
using namespace std;
const int N = 100010;
int p[N], cnt[N];

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

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

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

    while (m--){
        char op[2];
        int a,b;
        scanf("%s",op);
        if (*op == 'C'){
            cin >> a >> b;
            if ( find(a) != find(b) ){
                cnt[find(b)] += cnt[find(a)];
                p[find(a)] = find(b);
            }
        }

        else if( op[1] == '1'){
            cin >> a >> b;
            if (find(a) == find(b))     puts("Yes");
            else puts("No");
        }

        else {
            cin >> a;
            printf("%d\n",cnt[find(a)]);
        }
    }
    return 0;
}


活动打卡代码 AcWing 836. 合并集合

J_blake
11天前
#include <iostream>

using namespace std;

const int N = 100010;
int p[N];                            //p[N]存储数的父亲节点

int find(int x){                    //  find函数: 返回x的祖宗结点 + 路径压缩
    if (p[x] != x)      p[x] = find(p[x]);
    return p[x];
}

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

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

    while (m --){
        char op[2];
        int a, b;
        scanf("%s%d%d",op,&a,&b);
        if (*op == 'M')     p[find(a)] = find(b);
        else
        {
        if (find(a) == find(b))    puts("Yes");
        else puts("No");
        }
    }
    return 0;
}


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

J_blake
11天前
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010, M = 3000000;
int a[N], son[M][2], idx;

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

        /*int &s = son[p][x >> i & 1];
        if (!s) s = ++ idx;
        p = s;*/
    }
}

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

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++){
        scanf("%d",&a[i]);
        insert(a[i]);
    }
    int Max_ = 0;
    for (int i = 0; i < n; i ++){
       // printf("%d",search(a[i]));
        Max_ = max(search(a[i]), Max_);
    }
    cout << Max_;
    return 0;
}



J_blake
12天前

题目链接 LeetCode XXX

为什么输入字符串的语句放在初始化h[]和p[]语句之后结果会不对,放在之前就对了?

错误的代码:

#include <iostream>

using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;
ULL h[N], p[N];
char str[N];

ULL get(int l,int r){
    return h[r] - h[l-1]*p[r-l+1];
}

int main(){
    int n,m;
    cin >> n >> m;
    scanf("%s",str + 1);  //正确
    p[0] = 1;
    for (int i = 1; i <= n; i ++){
        p[i] = p[i-1] * P;
        h[i] = h[i-1] * P + str[i];
    }
    scanf("%s",str + 1);    //错误

    while (m--){
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if (get(l1,r1) == get(l2,r2))    puts("Yes");
        else puts("No");
   }
    return 0;
}


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

J_blake
13天前
#include <iostream>

using namespace std;
const int N = 100010;
int son[N][26],cnt[N],idx;              //son存储下一个节点的位置,每个结点(字符)都有唯一的标识(idx)通过son[idx][]寻找下一个字符的标识。
//每遍历完一个字符串时p指向一个新标识,cnt[p]标识该字符串出现的次数

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

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

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

    while (n--){
        char op[2],str[N];
        scanf("%s%s",op,str);
        if ( *op == 'I')    insert(str);
        else printf("%d\n",query(str));
    }
    return 0;
}


活动打卡代码 AcWing 841. 字符串哈希

J_blake
14天前
#include <iostream>

using namespace std;
const int N = 100010, P = 131;              //P取131或13331冲突概率最小
typedef unsigned long long  ULL;            //unsigned long long会将溢出的数自动取模
ULL p[N], h[N];                             
char str[N];                                

ULL get(int l,int r){
    return h[r] - h[l-1] * p[r-l+1];      //平移位数为r-l-1,从l - 1位开始平移
}

int main(){
    int n,m;
    cin >> n >> m;
    scanf("%s",str + 1);

    p[0] = 1;
    for (int i = 1; i <= n; i++){
        p[i] = p[i -1] * P;
        h[i] = h[i -1] * P + str[i];
    }

    while (m--){
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if (get(l1,r1) == get(l2,r2))   puts("Yes");
        else puts("No");
    }
    return 0;
}