头像

Heisenberg_

zzu




离线:7小时前


新鲜事 原文

acwing推动了整个计算机相关就业升学的内卷啊 如果acwing某天真的家喻户晓人人注册刷题。。可能必须要进阶课滚瓜烂熟 + codeforces每次div1都补题才能卷过别人了= =



Heisenberg_
1个月前
//method 1
class Solution {
public:

    int findPairs(vector<int>& nums, int k) {
         int res = 0;
         sort(nums.begin(),nums.end());
         int n = nums.size();

         for(int i = 0, j = 0; i < n;i++)
         {
             while(i > 0 && i < n - 1 && nums[i + 1] == nums[i]) i++;

             while(j < i && nums[i] - nums[j] > k) j++;
             if(j < i && nums[i] - nums[j] == k) res++;
         }
        return res;
    }  
};\
//method 2 

class Solution {
public:
      unordered_map<int,int> less;
      unordered_map<int,int> greater;
    int findPairs(vector<int>& nums, int k) {
             int n = nums.size();
             int res = 0;
          for(int i = 0; i < n;i++)
          {
              if(less.count(nums[i] - k))
              {
                  if(!greater.count(nums[i])) greater[nums[i]]++;
              }
                if(less.count(nums[i] + k))
              {
                  if(!greater.count(nums[i] + k)) greater[nums[i]+k]++;
              }
              if(!less.count(nums[i])) less[nums[i]]++;



          }

          res = greater.size();

          return res;
    } 
};


活动打卡代码 AcWing 756. 蛇形矩阵

Heisenberg_
1个月前
#include<bits/stdc++.h>

using namespace std;

const int N = 110;
int n,k;
int g[N][N];
bool st[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
    int a = 0, b = 0, m = 0;
    for(int i = 0; i < n * k; i++ )
    {
         g[a][b] = i + 1;
          st[a][b] = true;
         int ta = a, tb = b;
         a = a + dx[m], b = b + dy[m];
         if(a < 0 || a > n - 1 || b < 0 || b >  k - 1 || st[a][b])
         {

              m = (m + 1) % 4;
              a = ta + dx[m], b = tb + dy[m];
         }


    }

    for(int i = 0; i < n;i++)
    {

              for(int j = 0; j < k;j++)
          {

             cout << g[i][j] << " " ;
          }  


          cout <<  endl;
    }


    return 0;
}



Heisenberg_
4个月前

排序算法的稳定性

九大排序

计数排序 基数排序 桶排序
选择排序 插入排序 冒泡排序
堆排序 归并排序 快速排序

什么是排序的稳定性
如果元素大小相同
排序后的相对位置不变

不稳定
堆排序 快速排序 选择排序 不是稳定的
稳定
基数排序 冒泡排序 插入排序 归并排序 计数排序 桶排序

选择排序
在每次将最小的元素拿到最前面和未排序的序列的第一个元素进行交换的时候发生了对原序列的破坏 失去了稳定性

快速排序
Swap的时候有可能让两个本来相等的元素交换位置 破坏了原序列的稳定性

堆排序
比如:3 27 36 27,
如果堆顶3先输出,则,第三层的27(最后一个27)跑到堆顶,然后堆稳定,继续输出堆顶,是刚才那个27,这样说明后面的27先于第二个位置的27输出,不稳定。

基数排序 计数排序 桶排序
基数 进入每个桶的顺序和一开始相对位置相同
计数 下标映射偏移和相对位置相同
桶 和基数同理

冒泡排序 基于比较换到一侧 相等的话不会交换位置 保证相对的有序
插入排序 因为如果两个元素相等不会发生交换 先插入的放在前面 保证相对位置不变
归并排序 相等则不发生交换 保证相对位置不变




Heisenberg_
4个月前
#include<bits/stdc++.h>

using namespace std;
int n;
vector<int> chosen;
void calc(int x)
{

    if(x == n + 1)
    {
        for(int i = 0; i < chosen.size();i++) cout << chosen[i] << ' ';
        cout << endl;
        return;
    }
    calc(x+1); // not choose

    chosen.push_back(x);
    calc(x+1);
    chosen.pop_back();
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    calc(1);

    return 0;
}


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

Heisenberg_
4个月前
#include<bits/stdc++.h>

using namespace std;

const int N = 1000010;
int q[N],a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k; 
    for(int i = 0; i < n; i++) cin >> a[i];
    int hh = 0, tt = -1;
    for(int i = 0; i < n;i++)
    {
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++ tt] = i;
        if(i >= k - 1) cout << a[q[hh]] << ' ';

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

    }

    return 0;
}


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

Heisenberg_
4个月前
#include<bits/stdc++.h>

using namespace std;

const int N = 1000010;
int q[N],a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k; 
    for(int i = 0; i < n; i++) cin >> a[i];
    int hh = 0, tt = -1;
    for(int i = 0; i < n;i++)
    {
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++ tt] = i;
        if(i >= k - 1) cout << a[q[hh]] << ' ';

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

    }

    return 0;
}


活动打卡代码 AcWing 830. 单调栈

Heisenberg_
4个月前
#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
int stk[N],tt;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n;i++) 
    {
        int x;
        cin >> x;
        while(tt && stk[tt] >= x) tt--;
        if(tt) cout << stk[tt] << ' ';
        else cout << "-1" << ' ';
        stk[++tt] = x;
    }
    return 0;
}


活动打卡代码 AcWing 105. 七夕祭

Heisenberg_
4个月前
#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
long long a[N],b[N],f[N],avr;

long long calc(long long nums[],int t)
{


    for(int i = 1; i <= t;i++)
    {
        nums[i] -= nums[0] / t;
        nums[i] += nums[i-1];
    }
    sort(nums+1,nums+t+1);
    long long ans = 0;
    for(int i = 1; i <= t;i++)
    {
        ans += abs(nums[i] - nums[t+1>>1]);
    }
    return ans;
}



int main()
{
    ios::sync_with_stdio(false);

    long long n,m,t;
    cin >> n >> m >> t;
    while(t--)
    {
        int x,y;
        cin >> x >> y;
        a[x]++; b[y]++;

    }
    long long res = 0;

    for(int i = 1; i <= n;i++) a[0] += a[i];
    for(int i = 1; i <= n;i++) b[0] += b[i];
     if(a[0]%n==0&&b[0]%m==0)
        printf("both %lld\n",calc(a,n)+calc(b,m));
    else if(a[0]%n==0)
        printf("row %lld\n",calc(a,n));
    else if(b[0]%m==0)
        printf("column %lld\n",calc(b,m));
    else puts("impossible");

    return 0;
}




活动打卡代码 AcWing 122. 糖果传递

Heisenberg_
4个月前
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n,a[1000001],c[1000001],ave;ll sum;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    ave=sum/n;

    for(int i=2;i<=n;i++)
       c[i]=c[i-1]+a[i]-ave;
    sort(c+1,c+n+1);



    ll ans=0;
    int mid=c[(n>>1)+1];
    for(int i=1;i<=n;i++)
       ans+=abs(c[i]-mid);
    printf("%lld",ans); 
    return 0;
}