头像

洞玄娃娃




离线:2天前


最近来访(11)
用户头像
跟着光
用户头像
菜花籽
用户头像
触手wink
用户头像
听雨.
用户头像
缚苍龙
用户头像
Shabby_fish
用户头像
hitNB

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n, c;
vector<pair<int, int>> segs;

int main(){
    cin>>n;
    int l, r;
    for(int i=0;i<n;i++){
        cin>>l>>r;
        segs.push_back({l, r});
    }
    sort(segs.begin(), segs.end());
    l=segs[0].first;
    r=segs[0].second;
    for(int i=1;i<n;i++){
        int nl=segs[i].first;
        int nr=segs[i].second;
        if(nl>r)
            c++;
        r=max(r, nr);
    }
    cout<<++c;
    return 0;
}


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

离散化:此处指的是整数的离散化,将大范围的稀疏空间中的有序序列映射到小范围的稠密空间,首先将待离散化序列排序再去重,然后映射到[0, n]上,可以通过二分查找由待离散化序列中的下标得到[0, n]上的下标;

//vector a是待离散化序列
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a,end()), a.end());

上面的unique是c++的去重函数,返回去重后序列的尾端点,erase是擦除;

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
//待会a数组中要存离散化后的数还要存查询中的l和r
const int N=300000+10;
int a[N], s[N], n, m;
vector<pair<int, int>> adds, query;
vector<int> alls;
//给出待离散化序列的一个下标x,通过二分查找返回其在离散化后的序列的下标
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(){
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++){
        int x, c;
        scanf("%d%d", &x, &c);
        adds.push_back({x, c});
        alls.push_back(x);
    }
    for(int i=0;i<m;i++){
        int l, r;
        scanf("%d%d", &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());
    //处理n个“在x位置上的数加c操作”,结果存在离散化后的数组a中
    for(auto item: adds){
        int x=find(item.first);
        a[x]+=item.second;
    }
    //前缀和预处理
    for(int i=1;i<=alls.size();i++)
        s[i]=s[i-1]+a[i];
    //处理n次查询
    for(auto item: query){
        int l=find(item.first);
        int r=find(item.second);
        printf("%d\n", s[r]-s[l-1]);
    }
    return 0;
}



关于微操作有两个基本的操作要记住:
1. 获取一个数x的二进制位中第k位的值:x>>k&1
注:x的二进制位从第0位开始;
2. 获取x的二进制位中最后一个1及其后面的0——lowbit(x):x&-x
注:比如lowbit(10100)=100=4,lowbit(111010000)=10000=16;

#include <iostream>
using namespace std;

const int N=100000+10;
int n, a;

int lowbit(int x){
    return x&-x;
}

int main(){
    cin>>n;
    while(n--){
        cin>>a;
        int c=0;
        while(a)
            a-=lowbit(a),
            c++;
        cout<<c<<" ";
    }
    return 0;
}


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

#include <iostream>

using namespace std;

const int N=100000+10;
int a[N], b[N], n, m;

int main(){
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);
    for(int i=0;i<m;i++)
        scanf("%d", &b[i]);
    int i=0, j=-1;
    while(i<n&&++j<m)
        if(a[i]==b[j])
            i++;
    if(i>=n)
        printf("Yes");
    else
        printf("No");
    return 0;
}



#include <iostream>
using namespace std;

const int N=100000+10;
int A[N], B[N], n, m , x;
int main(){
    scanf("%d%d%d", &n, &m, &x);
    for(int i=0;i<n;i++)
        scanf("%d", &A[i]);
    for(int i=0;i<m;i++)
        scanf("%d", &B[i]);
    int i=0, j=m-1;
    while(i<n&&j>=0){
        if(A[i]+B[j]>x)
            j--;
        else if(A[i]+B[j]<x)
            i++;
        else{
            printf("%d %d", i, j);
            return 0;
        }
    }
    return 0;
}



#include <iostream>

using namespace std;

const int N=100000+10;
int a[N], s[N], n, res;

int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0, j=0;i<n;i++){
        s[a[i]]++;
        while(s[a[i]]>1)
            s[a[j++]]--;
        /*
        注:上面三行不可以写成如下方式:
        while(++s[a[i]]>1)
            s[a[j++]]--;
        原因是上面代码中的s[a[i]]++执行一次而下面的代码把累加写进while循环会导致s[a[i]]++执行多次
        因此要对代码执行的次数有意识,不然改代码的时候容易犯错误。
        */
        res=max(res, i-j+1);
    }
    cout<<res<<endl;
    return 0;
}



#include <iostream>

using namespace std;

const int N=100000+10;
int a[N], s[N], n, res;

int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0, j=0;i<n;i++){
        s[a[i]]++;
        while(s[a[i]]>1)
            s[a[j++]]--;
        res=max(res, i-j+1);
    }
    cout<<res<<endl;
    return 0;
}



题目描述

小 A 和小 B 在下五子棋。

五子棋是在一个由网格构成的棋盘内进行的。

网格有 15 行 15 列,共有 225 个交叉点。

小 A 先手执黑棋,小 B 后手执白棋。

两人轮流下棋,每次下棋都将一个自己的棋子放在棋盘上一个空白的交叉点上。

然而,由于小 A 和小 B 都不知道五子棋的胜利条件,所以即使有一方已经胜利了,他们仍然会继续下棋。

现在想请你帮忙分析一下,所下的棋局是在第几步结束的。

当然,也有可能他们最终仍然没有分出胜负,这时请判定他们平局。

五子棋的胜利条件是这样的:当同一行或同一列或同一斜线(即与网格线成 45° 角的直线)上连续的五个或五个以上交叉点放有同色棋子的时候,立即判定使用该颜色棋子的玩家获得胜利,游戏结束。


模拟

对于每一个当前下的棋子,对其使用双指针进行横向、纵向、左斜、右斜扫描(8个while循环);

  1. 首先棋盘数组a[16][16]用0表示空、1表示A下的、2表示B下的;
  2. check时给出参数k,k=1代表这个棋子是A下的,k=2代表这个棋子是B下的;
  3. 根据1、2的设定就可以利用a[x][y]^k的值来判定这个位置是否存在A或B之前下的棋子;如果这个值为0,则意味着该位置存在当前落子人之前下的棋子,否则不存在,则该位置可能是空的也可能是对手下的棋子;
  4. 注意,==比^优先级高,因此2^2==1的值为2而(2^2)==0的值为1,一定要注意这一点;

时间复杂度$O(n)$

对n个棋子进行判定,每个棋子的判定是O(1),因为每个棋子虽然最多要走8个while循环,但是每个while循环最多5次,因此最多不过40次,仍是O(1),所以总体时间复杂度就是O(n);

C++ 代码

#include <iostream>

using namespace std;

const int N=16;
int a[N][N];
int n;
//对于最新下的这一颗棋子,判定其是否和周围的棋子构成5个棋子的连线
//k=1代表A,k=2代表B
//a中元素1代表A的子,2代表B的子,0代表空
//则a[i][j]^k==0则代表当前位置有k的子
bool check(int x, int y, int k){
    //判断横着的棋子是否5个一线
    int l=x+1, r=x;
    //一下八个while语句我都忽略了^与==的优先级,如果不加括号会先算==得到0再进行^;就这里debug了好久;
    while(--l>0&&(a[l][y]^k)==0);
    while(++r<N&&(a[r][y]^k)==0);
    if(r-l-1>=5)
        return true;
    //判断竖着的
    l=y+1, r=y;
    while(--l>0&&(a[x][l]^k)==0);
    while(++r<N&&(a[x][r]^k)==0);
    if(r-l-1>=5)
        return true;
    //判断y=-x形的
    int l1=x+1, l2=y+1, r1=x, r2=y;
    while(--l1>0&&--l2>0&&(a[l1][l2]^k)==0);
    while(++r1<N&&++r2<N&&(a[r1][r2]^k)==0);
    if(r1-l1-1>=5)
        return true;
    //判断y=x形的
    l1=x-1, l2=y+1, r1=x, r2=y;
    while(++l1>0&&--l2<N&&(a[l1][l2]^k)==0);
    while(--r1<N&&++r2>0&&(a[r1][r2]^k)==0);
    if(l1-r1-1>=5)
        return true;
    return false;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int x, y;
        cin>>x>>y;
        if(i%2==0)
            a[x][y]=1;
        else
            a[x][y]=2;
        if(i%2==0&&check(x, y, 1)){
            printf("A %d", i+1);
            return 0;
        }
        else if(i%2!=0&&check(x, y, 2)){
            printf("B %d", i+1);
            return 0;
        }
    }
    printf("Tie");
    return 0;
}



活动打卡代码 AcWing 798. 差分矩阵

#include <iostream>

using namespace std;

const int N=1000+10;
int a[N][N], b[N][N];
int n, m, q;
void insert(int x1, int y1, int x2, int y2, int c){
    b[x1][y1]+=c;
    b[x1][y2+1]-=c;
    b[x2+1][y1]-=c;
    b[x2+1][y2+1]+=c;
}

int main(){
    scanf("%d%d%d", &n, &m, &q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            scanf("%d", &a[i][j]);
            insert(i, j, i, j, a[i][j]);
        }
    while(q--){
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
            printf("%d ", b[i][j]);
        }
        printf("\n");
    }
    return 0;
}


活动打卡代码 AcWing 797. 差分

#include <iostream>

using namespace std;
const int N=100000+10;
int n, m, a[N], b[N];
void insert(int l, int r, int c){
    b[l]+=c;
    b[r+1]-=c;
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)
        scanf("%d", &a[i]);
    for(int i=1;i<=n;i++)
        insert(i, i, a[i]);
    while(m--){
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }
    for(int i=1;i<=n;i++){
        b[i]+=b[i-1];
        printf("%d ", b[i]);
    }
    return 0;

}