头像

奥特汪打小怪喵




离线:4小时前


最近来访(12)
用户头像
_N
用户头像
沙漠之狐
用户头像
不到130不改名
用户头像
ESP
用户头像
ZQCa
用户头像
L.妍ab
用户头像
Algorithm没有冬眠
用户头像
123go
用户头像
忆の風
用户头像
itdef
用户头像
小熊饼干吃QQ

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

#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

const int N = 100010;

int h[N],ph[N],hp[N],s;

void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
    swap(h[a],h[b]);
}

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

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

int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n -- )
    {
        char op[5];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            scanf("%d", &x);
            s ++ ;
            m ++ ;
            ph[m] = s, hp[s] = m;
            h[s] = x;
            up(s);
        }

        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, s);
            s -- ;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, s);
            s -- ;
            up(k);
            down(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }

    return 0;
}


新鲜事 原文

AcWing《算法提高课》拼团优惠!https://www.acwing.com/activity/content/introduction/16/group_buy/34327/ 
还差一个


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

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int n,m;
int a[N],s;

void down(int x)
{
    int t =x;
    if(x * 2 <= s && a[x * 2] < a[t])
    {
        t = x * 2;
    }
    if(x * 2 + 1 <= s && a[x * 2 + 1] < a[t])
    {
        t = x * 2 + 1;
    }
    if( x != t)
    {
        swap(a[x],a[t]);
        down(t);
    }
}

int main()
{
    scanf("%d%d", &n,&m);
    for (int i= 1; i <=n; i++) scanf("%d",&a[i]);
    s = n;
    for (int i= n/2; i; i --)
    {
       down(i);
    }

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


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

#include<iostream>

using namespace std;

const int N = 50010;

int n,m;
int p[N],d[N];

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()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)
    {
        p[i]=i;
    }
    int res = 0;
    while(m--)
    {
        int t,x,y;
        scanf("%d%d%d",&t,&x,&y);
        if(x > n || y > n) res++;
        else
        {
            int px = find(x),py = find(y);
            if( t == 1)
            {
                if(px == py && (d[x]-d[y]) % 3) res++;
                else if(px != py)
                {
                    p[px]=py;
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
                if (px == py && (d[x] - d[y] -1) % 3) res++;
                else if(px != py)
                {
                    p[px]=py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    printf("%d\n",res);
    return 0;
}



#include<iostream>

using namespace std;

const int N = 100010;

int n,m;
int p[N],s[N];

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

int main()
{
    scanf("%d%d",&n,&m);

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

    while(m--)
    {
        char op[5];
        int a,b;
        scanf("%s",op);

        if(op[0] == 'C') 
        {
            scanf("%d%d",&a,&b);
            if(find(a) == find(b)) continue;
            s[find(b)] += s[find(a)];
            p[find(a)] = find(b);
        }
        else if(op[1] == '1')
        {
            scanf("%d%d",&a,&b);
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
        }
        else if(op[1] == '2')
        {
            scanf("%d",&a);
            printf("%d\n", s[find(a)]);
        }

    }
    return 0;
}


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

#include<iostream>

using namespace std;

const int N = 100010;

int n,m;
int p[N];

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

int main()
{
    scanf("%d%d",&n,&m);

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

    while(m--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);

        if(op[0] == 'M') 
        {
            p[find(a)] = find(b);
        }
        else if(op[0] == 'Q')
        {
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
        }

    }
    return 0;
}


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

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010, M = 3000000;

int n;
int son[M][2],a[N],idx;

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

int query(int x)
{
    int res = 0, p = 0;
    for(int i=30;i>=0;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()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        insert(a[i]);
    }

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


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

#include<iostream>
#include<algorithm>

using namespace std;

const int N=100010;

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

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];
}

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


活动打卡代码 AcWing 831. KMP字符串

#include<iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n,m;
char p[N],s[M];
int ne[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }

    return 0;
}



题目链接 (https://www.nowcoder.com/test/question/3897c2bcc87943ed98d8e0b9e18c4666?pid=260145&tid=50149544)

不知道为啥,输出为空,明明是有输出的。

错误的代码:

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int n,m;
int q[N];

int maxquery( int A, int B){

   int ans = q[A];
    for(int i=A;i<= B;i++) ans = max(ans,q[i]);
    return ans;
}

void update(int A, int B){
    q[A]=B;
}

int main(){
   while(cin>>n>>m)
   {
       for(int i=1;i<=n;i++) cin>>q[i];
       int A,B;
       char C;
       cin>>A>>B;
       cin>>C;
       while(m--)
       {
           if(C=='U') update(A,B);
           else if(C == 'Q')
               {
                if(A>B) swap(A,B);
               cout<<maxquery(A,B)<<endl;
           }
       }
   }
    return 0;
}

编译器报了什么错误?输出为空