个人空间 - AcWing

馄炖大稀粥

hust

阅读量

190

+关注发消息

离线：11分钟前

最近来访(12)

一万小时定律

铁锅炖大鹅

gAg

你好流星

Bigwave

Airon

KAI11_EVEN

分享有关滑动窗口的暴力解法

馄炖大稀粥
4小时前

                #include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N];
int n,k,tt,hh;
//核心窗口长度并没有改变，代表了i之前的k个数，但是并不是把这k个元素都拿来比较
int main(){
    cin >> n >> k;

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

    tt = -1, hh = 0;
    for(int i = 0 ; i < n ; i ++)
    {
        tt++;
        q[tt] = i;
        if(tt >= hh && i - q[hh] + 1 > k)
            hh++;

        int min1 = a[q[hh]];    
        for(int j = hh ; j <= tt ; j++ )
        {
            min1 = min(min1,a[q[j]]) ;
        }

        if( i >= k - 1)
            cout<<min1<<" ";
    }

    cout << endl;

    tt = -1, hh = 0;
    for(int i = 0 ; i < n ; i ++)
    {
        tt++;
        q[tt] = i;
        if(tt >= hh && i - q[hh] + 1 > k)
            hh++;

        int max1 = a[q[hh]];    
        for(int j = hh ; j <= tt ; j++ )
        {
            max1 = max(max1,a[q[j]]) ;
        }

        if( i >= k - 1)
            cout<<min1<<" ";
    }
}

            

题目讨论 AcWing 838. 关于down函数

馄炖大稀粥
1天前

y总的down函数

void down(int u)
{
    //注意 这里不能先判断 节点是不是有子节点  再比较三者大小关系
    //否则结果里会在前面多一个0，不知道为什么
    int t = u;
    if (2 * u <= size1 && h[t] > h[2 * u])
        t = 2 * u;
    if (2 * u + 1 <= size1 && h[t] > h[2 * u + 1])
        t = 2 * u + 1;
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}

我修改后的down函数

void down(int u){
    //先判断节点有没有儿子 有右儿子必有左儿子 ，只用看有没有左儿子
    if( u * 2 <= size1)
    {
        //这三条语句选出了值最小的节点的序号
        int t = u;
        if( h[u*2 + 1] < h[t] ) t = u*2 + 1  ;
        if( h[u*2] < h[t]  )    t = u*2;

        if(u != t)
        {
            swap(h[u], h[t]);
            down(temp);
        }

    }
}

不知道为什么我的会在堆排序的结果最前方是0
比如下图

1 评论

铁锅炖大鹅 1小时前回复

//交换数据
void swap(int &a,int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

//建立大顶堆
void Adjust_down(int a[], int k, int len)
{
    int dad = k;
    int son = 2 * dad + 1;//找到自己的左儿子
    while (son < len)
    {
        if (son+1<len && a[son + 1]>a[son])//判断有右儿子，并且右儿子更大
        {
            son++;
        }
        if (a[son] > a[dad])
        {
            swap(a[son], a[dad]);
            dad = son;
            son = 2 * dad + 1;
        }
        else {
            break;
        }
    }
}

//堆排序
void Heap_sort(int a[],int len)
{
    //首先建立大顶堆，从最后一个父亲节点开始,依次向头建立所有父亲节点
    int i;
    for (i = len / 2-1 ; i >= 0; i--)
    {
        Adjust_down(a,i,len);//建立单个节点的大顶堆
    }
    swap(a[0],a[len-1]);//交换第一个节点和最后一个节点
    //再从第一个节点开始建立大顶堆，每次循环需要减少最后一个元素
    len--;
    for (i = len; i > 0; i--)
    {
        Adjust_down(a, 0, i);
        swap(a[0], a[i-1]);
    }
}

int main () {
    int n,m;
    int arr[N];
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n ;i++) {
        scanf("%d",&arr[i]);
    }
    Heap_sort(arr,n);
    for(int i = 0;i < m;i++)  {
        printf("%d ",arr[i]);
    }
    printf("\n");
    return 0;
}

查看更多评论

活动打卡代码 AcWing 801. 二进制中1的个数

馄炖大稀粥
4天前

求整数n的二进制表达式的从低往高第k位 (k从0开始)
bit_k = (n>>k) & 1;

求整数n的二进制表达式最低的1   m = n & ~n;
   原：1011000 1000000
   反：0100111 0111111
   补：0100111 1000000
原&补; 0000000 1000000

#include <iostream>
using namespace std;
const int N = 100010;
int a[N],cnt[N];

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

    for(int i = 0 ; i < n ; i ++){
        temp = a[i];
        while(temp != 0){
        //每次与1相位与 ， 相当于取出二进制的最低位
            lowbit = temp & 1;
            if(lowbit == 1)
                cnt[i] ++;
            temp = temp >> 1;  //temp = temp/2; 要习惯这么写
        }
    }

    for(int i = 0 ; i < n ; i ++)    cout << cnt[i]<<" ";
}

题目讨论 AcWing 837. 求助，明明没有错，却报wrong answer

馄炖大稀粥
4天前

会报wrong answer
但是我的输出与他给出的正确输出没有差别
不知道问题在哪里。。。。请教各位dd

#include <iostream>
using namespace std;
const int N = 100010;
int fa[N],cnt[N];
int n,m;

int find(int x){
    if(x != fa[x])

    fa[x] = find(fa[x]);

    return fa[x];
}
int main(){
    cin >> n >> m;
    for(int i = 0 ; i < n ; i ++){
        fa[i] = i;
        cnt[i]++;
    }

    while(m--){
        string op;
        cin >> op;
        int a, b;
        if(op == "C"){
            cin >> a>> b;
            int x = find(a);
            int y = find(b);
            //先求顶点的数量和，再合并集合
            cnt[y] += cnt[x];
            fa[x]   =  y;
        }
        else if(op == "Q1"){
            cin >> a >> b;
            if(find(a) == find(b))
                cout << "Yes" <<endl;
            else
                cout << "No"  <<endl;
        }
        else if(op == "Q2"){
            cin >> a;
            cout<<cnt[find(a)]<<endl;
        }
    }
}

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

馄炖大稀粥
4天前

                #include <iostream>
using namespace std;
const  int N = 100020;
int p[N];//每个节点所指向的父节点
//int e[N];  可以用来存储节点需要保存的数据

//将节点所在树的根节点找到 ，并且路径压缩
int find(int x){
    if( x != p[x])
        p[x] = find(p[x]);//递归 直到找到祖宗节点，然后一条路上的p[x] = 祖宗节点 = 

    else
        return p[x];//返回祖宗节点、根节点
}

//将两个数所在的集合合并
void merge(int a, int b){
    int x = find(a);
    int y = find(b);
    //把含有a的集合x合并到含有b的集合y中去 x指向的父节点为y
    p[x] = y;
}
void query(int a, int b){
    if(find(a) == find(b))
        cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
int main(){
    int n, m;
    cin >> n >> m;

    //初始化，每个节点都指向自己
    for(int i = 0; i < n ; i++){
        p[i] = i;
    }

    while(m--){
        int a,b;
        string op;
        cin >> op;
        int x,y;
        if(op == "M")  
        {
            cin>>a>>b;
            merge(a,b);
        }
        else if(op == "Q")
        {
            cin>>a>>b;
            query(a,b);
        }
    }
}


            

分享 154 滑动窗口的暴力求法

馄炖大稀粥
4天前

                #include <iostream>
using namespace std;
const int N = 100010;
int q[N],a[N];
int tt,hh;
int minx,maxx;
int main(){
    int n,k;
    cin >> n >>k;
    for(int i = 0 ; i < n ; i++)  cin >> a[i];

    tt = -1 , hh = 0;
    for(int i = 0 ; i < n ; i ++){
        q[++tt] = a[i];

        if(tt-hh+1 > k)  hh++;

        minx = q[hh];
        for(int j = hh ; j <= tt ; j++)
            minx  = min(minx , q[j]);

        if( i >= k -1 )
            cout << minx <<" ";

    }

    cout << endl;

    tt = -1 , hh = 0;
    for(int i = 0 ; i < n ; i ++){
        q[++tt] = a[i];

        if(tt-hh+1 > k)  hh++;

        minx = q[hh];
        for(int j = hh ; j <= tt ; j++)
            maxx  = max(maxx , q[j]);

        if( i >= k -1 )
            cout << maxx <<" ";

    }
}

            

活动打卡代码 AcWing 829. 模拟队列

馄炖大稀粥
4天前

这里使用的是 q[hh] 对应装入的第一个元素的形式
即为 tt 落后于 hh
hh = 0
tt = -1

#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
int hh = 0, tt = -1;
int main(){
    int m;
    cin >> m;
    while(m--){
        string op;
        cin >> op;
        int x;
        if(op=="push") 
        {
            cin >>x;
            tt++;
            q[tt] = x;
        }
        else if(op == "pop")
        {
            hh++;
        }
        else if(op == "empty")
        {
            if(tt >= hh)    cout<<"NO"<<endl;
            else            cout<<"YES"<<endl;
        }
        else if(op =="query")
        {
            cout<<q[hh]<<endl;
        }
    }
}

活动打卡代码 AcWing 828. 模拟栈

馄炖大稀粥
4天前

没啥好说的

#include <iostream>
using namespace std;
const int N = 100010;
int s[N];
int top = 0 ;

int main(){
    int m ;
    cin >> m;
    while(m--){
        string op;
        cin >> op;
        int x;
        if(op == "push")
        {
            cin >> x;
            top++;
            s[top] = x;
        }
        else if(op == "pop")
        {
            top--;
        }
        else if(op == "empty")
        {
            if(top == 0) cout<<"YES"<<endl;
            else     cout<<"NO"<<endl;
        }
        else if(op =="query")
        {
            cout<<s[top]<<endl;
        }
    }
}

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

馄炖大稀粥
5天前

                #include <iostream>
using namespace std;
const int N = 100010;
int son[N][26];
int cnt[N];
int idx;
char input[N];

void insert(char s[]){
    int p = 0;
    for(int i = 0 ; s[i] != '\0' ; i++){
        int u = s[i] - 'a';


        //不可以偷懒写成 if(!son[p][u]) son[p][u] = ++idx; if 后面不打括号只循环一条语句
        if(!son[p][u]){
            idx++;
            son[p][u] = idx;  //以插入的次序作为新生成节点的名字
        }

        p = son[p][u];
    }
    cnt[p]++;   //这里写 cnt[ son[p][u]  ] 的话更易懂                          最后一个生成的新节点对应的计数器++。
}

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

        p = son[p][u];
    }
    return cnt[p];
}
int main(){

    idx = 0;

    int n;
    cin >> n;
    while(n--)
    {
        string op;
        cin >> op;
        if(op == "I")
        {
            cin >> input;
            insert(input);
        }
        else if( op == "Q")
        {
            cin >> input ;
            cout << query(input)<<endl;
        }
    }
}

            

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

馄炖大稀粥
5天前

                #include <iostream>
using namespace std;
const int N = 1000010;
int a[N] , q[N];
int n,k;
int hh = 0 , tt = -1;

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

    for(int i = 0 ; i < n ; i ++)
    {   
       //如果 i 到 q[hh] 大于窗口长度，窗口中第一个数的 下标出队
       if(i - q[hh] + 1 > k)  hh++;

       //如果窗口中有比a[i] 大的数，这些数对应的下标出队，队列是单调递增的，尾部数更容易出
       //并且窗口缩短对应的长度      
       while(tt >= hh && a[i] < a[q[tt]]) tt--;

       //将a[i] 对应的下标加入队尾 a[i]进入滑动窗口
       tt++;
       q[tt]  =  i;

       //如果窗口还没有满，不显示  窗口即使没有满 也会输出
       if( i + 1 >= k)  cout<<a[q[hh]]<<" ";
    }

    cout << endl;
    //还原滑动窗口到初始情况
    tt = -1 , hh = 0;

    for(int i = 0 ; i < n ; i ++)
    {   
       //如果 i 到 q[hh] 大于窗口长度，第一个下标出队
       if(i - q[hh] + 1 > k)  hh++;

       //如果窗口中有比a[i] 小的数，这些数对应的下标出队，由于队列具有单调递增性，所以尾部的元素最大
       // 尾部最容易被踢出  从尾部开始踢
       //并且窗口缩短对应的长度      
       while(tt >= hh && a[i] > a[q[tt]]) tt--;

       //将a[i] 对应的下标加入到队尾
       tt++;
       q[tt]  =  i;

       //如果窗口还没有满，不显示
       if(  i + 1 >= k)  cout<<a[q[hh]]<<" ";
    }



}

            