2024.08.24京东

1. 100的倍数

给你一个整数，请你判断0～N之间有多少个数是100的正整数倍。输入描述：输入的第一行给出一个整数N 输出描述：输出0~N之间有多少个数是100的整数倍。

int main() {
 string st;
 cin>>st;

 int n=strlen(st);

 if (n<=2 || st[0]=='-'){
    cout<<"0";
    return 0;
}
 for (int i=0; i<n-2; i++) cout<<st[i];
}

2. 网格操作

给定一个大小为n * m 的网格板，网格板是由n * m个1x1的单元格组成，最初所有的单元格是白色的;现在给出k个操作:
c x y将位置为(x,y)的单元格涂成黑色 l x y从位置为(x,y)的单元格向左寻找最先出现的白色单元格(不包含(x,y))，并输出其坐标;
r x y从位置为(x,y)的单元格向右寻找最先出现的白色单元格(不包含(x,y))，并输出其坐标
u x y从位置为(x,y)的单元格向上寻找最先出现的白色单元格(不包含(x,y))，并输出其坐标;
d x y从位置为(x,y)的单元格向下寻找最先出现的白色单元格(不包含(x,y))，并输出其坐标 注:网格板的左上角的单元格坐标为(1,1)

int main() {
    int m,n,k;
    cin>>m>>n>>k;
    vector<vector<bool>> board(m,vector<bool>(n));
    int dir[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};//右、下、左、上
    map<char,int> mp = {{'d', 0},{'l',1},{'u',2},{'r',3}};
    while(k--){
        char c; int x,y;
        cin>>c>>x>>y;
        x = x-1; y = y-1;
        if(c=='c'){
            board[x][y] = true;
            continue;
        }
        int nx = x;
        int ny = y;
        while(true){
            nx = nx + dir[mp[c]][0];
            ny = ny + dir[mp[c]][1];
            if(nx<0||ny<0||nx==m||ny==n){
                cout<<-1<<endl;
                break;
            }
            if(board[nx][ny]==false){
                cout<<nx+1<<" "<<ny+1<<endl;
                break;
            }
        }
    }
    return 0;
}

3. 木棍最长子区间

有n根木棍排成一列,请你从中选出一个最长的子区间，
使得区间内任意三根木棍都能构成三角形。只需要输出选出的区间端点即可。

一眼滑动窗口，不过需要维护前面区间的最小值，次小值，最大值，直接使用红黑树即可

int main() {
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0;i<n;i++)
        cin>>nums[i];
    //构成三角形的条件，两边之和大于第三边
    int l = 0; int r = 1;//滑动窗口
    int res = 2;//最长区间
    int resl = 0; int resr = 1;
    set<pair<int,int>> s;//记录对应值和位置，根据值排序
    s.insert({nums[0],0});
    s.insert({nums[1],1});
    while(++r<n){//滑动右边,需要判断这个值加入区间后是否还满足，快速判断，需要维护和淘汰区间最小值最大值，次小值
        //如果该值在区间内，必然满足，如果小于区间，需要和最小值求和，如果大于区间，需要最小的两个值求和判断
        while(s.size()>1){
            int mn = (*s.begin()).first;
            int semn  = (*next(s.begin())).first;
            int mx = (*(s.rbegin())).first;
            if(mn+semn>nums[r]&&mn+nums[r]>mx){//满足条件
                if(r-l+1>res){//记录更新结果
                    res = r-l+1;
                    resr = r;
                    resl = l;
                }
                break;//跳出循环
            }
            s.erase({nums[l],l});//缩小窗口
            l++;
        }
        s.insert({nums[r],r});
    }
    cout<<resl+1<<" "<<resr+1<<endl;
    return 0;
}