头像

馄炖大稀粥

hust




离线:11分钟前


最近来访(12)
用户头像
一万小时定律
用户头像
铁锅炖大鹅
用户头像
gAg
用户头像
你好流星
用户头像
Bigwave
用户头像
Airon
用户头像
KAI11_EVEN


#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<<" ";
    }
}



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.png




求整数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]<<" ";
}



会报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. 合并集合

#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);
        }
    }
}




#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. 模拟队列

这里使用的是 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. 模拟栈

没啥好说的

#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字符串统计

#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. 滑动窗口

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



}