头像

会飞的泡泡

云南民族大学->考研人




离线:13小时前


活动打卡代码 AcWing 788. 逆序对的数量

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int a[N], tmp[N];

LL merge_sort(int q[], int l, int r)
{
    if (l >= r) return 0;

    int mid = l + r >> 1;

    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else
        {
            res += mid - i + 1;
            tmp[k ++ ] = q[j ++ ];
        }
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];

    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    cout << merge_sort(a, 0, n - 1) << endl;

    return 0;
}


活动打卡代码 AcWing 803. 区间合并

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
void merge(vector<PII> &segs)
{
    vector<PII> res;
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}
int main()
{
    int n;
    scanf("%d", &n);

    vector<PII> segs;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back({l, r});
    }
    merge(segs);
    cout << segs.size() << endl;
    return 0;
}


活动打卡代码 AcWing 802. 区间和

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls;
vector<PII> add, query;
int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});

        alls.push_back(x);
    }
    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});

        alls.push_back(l);
        alls.push_back(r);
    }
    // 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    // 处理插入
    for (auto item : add)
    {
        int x = find(item.first);
        a[x] += item.second;
    }
    // 预处理前缀和
    for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];
    // 处理询问
    for (auto item : query)
    {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}




#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    while(n--){
        int a;
        scanf("%d",&a);
        int ans=0;
        for(int i=a; i; i-=i&-i){
            ans++;
        }
        cout<<ans<<' ';
    }
}


活动打卡代码 AcWing 2816. 判断子序列

#include <iostream>
using namespace std;
const int maxn=100010;
int x[maxn],y[maxn];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>x[i];
    }
    for(int j=0; j<m; j++){
        cin>>y[j];
    }
    int aa=0;
    for(int i=0,j=0; j<m; j++){
        if(x[i]==y[j])i++;
        if(i>=n){
            cout<<"Yes";
            aa=1;
            break;
        }
    }
    if(!aa)cout<<"No";
    return 0;
}



BFS,DFS的题写不出来,但看其他人代码能看懂!!写不出来啊啊啊,崩溃!!!




BFS,DFS的题写不出来,但看其他人代码能看懂!!写不出来啊啊啊,崩溃!!!




每次for循环直接填完一条边,填完一圈后,更新四角的值

注意细节!

#include <iostream>

using namespace std;
const int N = 105;

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

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

    int left = 0, right = m - 1, top = 0, bottom = n - 1;
    int k = 1;
    while (left <= right && top <= bottom) {
        for (int i = left ; i <= right; i ++) {
            a[top][i] = k ++;
        }
        for (int i = top + 1; i <= bottom; i ++) {
           a[i][right] = k ++;
        }
        for (int i = right - 1; i >= left && top < bottom; i --) {
            a[bottom][i] = k ++;
        }
        for (int i = bottom - 1; i > top && left < right; i --) {
            a[i][left] = k ++;
        }
        left ++, right --, top ++, bottom --;
    }
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int maxn = 150;
int a[maxn][maxn];

方法二

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

    memset(a, 0, sizeof(a));
    int x = 0, y = 0;       //初始坐标坐标,(0,0) 
    int cnt = 1;            //初始化第一个数 
    a[x][y] = cnt;

    while (cnt < n * m ) 
    {   
        //用下一笔的位置来判断
        //向右, 符合条件,则填入下一笔。____提前预判  
        while (y + 1 < m && !a[x][y + 1]) a[x][ ++ y] = ++ cnt;
        //向下 
        while (x + 1 < n && !a[x + 1][y]) a[ ++ x][y] = ++ cnt;
        //向左
        while (y - 1 >= 0 && !a[x][y - 1]) a[x][ -- y] = ++ cnt;
        //向上
        while (x - 1 >= 0 && !a[x - 1][y]) a[ -- x][y] = ++ cnt;    
    }
    for (int i = 0; i < n; i ++ ) 
    {
        for (int j = 0; j < m; j ++ )
        {
            cout << a[i][j] << " ";
            // printf("%-5d", a[i][j]);
        }   
        cout << endl;
    } 

    return 0;
}



活动打卡代码 AcWing 2065. 整除序列

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long  n;
    cin>>n;
    cout<<n<<' ';
    while(n>1){
        n/=2;
        cout<<n<<' ';
    }

    return 0;
}


活动打卡代码 AcWing 2066. 解码

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str,ss,sss;
    getline(cin,str);
    for(int i=str.size()-1; i>=0; i--){
        if(str[i]>='0'&&str[i]<='9'){
            for(int j=0; j<str[i]-'0'-1; j++){
                ss+=str[i-1];
            }
        }else ss+=str[i];
    }
    for(int i=ss.size()-1; i>=0; i--){
        sss+=ss[i];
    }
    cout<<sss;
}