头像

GALA




离线:11小时前


最近来访(9)
用户头像
BILL01
用户头像
烟雨_8
用户头像
Skuy
用户头像
白之月
用户头像
scx
用户头像
奈落_8
用户头像
故人倾
用户头像
Femnop


GALA
16小时前

给定三个整数数组

A=[A1,A2,…AN]
,
B=[B1,B2,…BN]
,
C=[C1,C2,…CN]
,

请你统计有多少个三元组 (i,j,k)
满足:

1≤i,j,k≤N
Ai<Bj<Ck
输入格式
第一行包含一个整数 N

第二行包含 N
个整数 A1,A2,…AN

第三行包含 N
个整数 B1,B2,…BN

第四行包含 N
个整数 C1,C2,…CN

输出格式
一个整数表示答案。

数据范围
1≤N≤105
,
0≤Ai,Bi,Ci≤105
输入样例:
3
1 1 1
2 2 2
3 3 3
输出样例:
27


//二分(之前提交的)
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n;
int a[N], b[N], c[N];

//在A中找到最后一个小于B的数的位置
//在C中找到第一个大于B的数的位置
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &c[i]);

    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    sort(c + 1, c + 1 + n);

    long long res = 0;  //long long --最坏情况下要用long long
    for(int i = 1, IndexA = 1, IndexC = 1; i <= n; i++){  //IndexA--指针 IndexC同理
        int B = b[i];
        while(IndexA <= n && a[IndexA] < B){  //在A中找到最后一个小于B的数的位置
            IndexA++;
        }
        while(IndexC <= n && c[IndexC] <= B){  //在C中找到第一个大于B的数的位置
            IndexC++;
        }
        res += (long long)(IndexA - 1) * (n - IndexC + 1);   //强转成long long
    }
    printf("%lld\n", res);
    return 0;
}



GALA
5天前

A-B 数对

题目背景

出题是一件痛苦的事情!

相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的 A+B Problem,改用 A-B 了哈哈!

题目描述

给出一串正整数数列以及一个正整数 $C$,要求计算出所有满足 $A - B = C$ 的数对的个数(不同位置的数字一样的数对算不同的数对)。

输入格式

输入共两行。

第一行,两个正整数 $N,C$。

第二行,$N$ 个正整数,作为要求处理的那串数。

输出格式

一行,表示该串正整数中包含的满足 $A - B = C$ 的数对的个数。

样例 #1

样例输入 #1

4 1
1 1 2 3

样例输出 #1

3

提示

对于 $75\%$ 的数据,$1 \leq N \leq 2000$。

对于 $100\%$ 的数据,$1 \leq N \leq 2 \times 10^5$,$0 \leq a_i <2^{30}$,$1 \leq C < 2^{30}$。

2017/4/29 新添数据两组




//b指针中又分了两个指针—-b1和b2
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 200010;

int n, C;
int q[N];

int main()
{
    scanf("%d %d", &n, &C);
    for(int i = 1; i <= n; i++){
        scanf("%d", &q[i]);
    }

    sort(q + 1, q + 1 + n);

    long long res = 0;
    for(int a = 1, b1 = 1, b2 = 1; a <= n; a++){
        while(b1 <= a && q[a] - q[b1] >= C){
            b1++;
        }
        while(b2 <= a && q[a] - q[b2] > C){
            b2++;
        }
        res += b1 - b2;
    }

    printf("%lld\n", res);
    return 0;
}



GALA
5天前

一、题目描述
给定两个升序排序的有序数组 A AA 和 B BB,以及一个目标值 x xx。

数组下标从 0 00 开始。

请你求出满足 A [ i ] + B [ j ] = x A[i]+B[j]=xA[i]+B[j]=x 的数对 ( i , j ) (i,j)(i,j)。

数据保证有唯一解。

输入格式
第一行包含三个整数 n , m , x n,m,xn,m,x,分别表示 A 的长度,B 的长度以及目标值 x。

第二行包含 n nn 个整数,表示数组 A。

第三行包含 m mm 个整数,表示数组 B。

输出格式
共一行,包含两个整数 i ii 和 j jj。

数据范围
数组长度不超过 1 0 5 10^510
5

同一数组内元素各不相同。
1 ≤ 1≤1≤ 数组元素 ≤ 1 0 9 ≤10^9≤10
9

输入样例:

4 5 6
1 2 4 7
3 4 6 8 9
1
2
3
输出样例:

1 1
————————————————



#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

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

int main()
{
    scanf("%d %d %d", &n, &m, &x);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++){
        scanf("%d", &b[i]);
    }

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



GALA
6天前

输入一个 n
行 m
列的整数矩阵,再输入 q
个询问,每个询问包含四个整数 x1,y1,x2,y2
,表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式
第一行包含三个整数 n,m,q

接下来 n
行,每行包含 m
个整数,表示整数矩阵。

接下来 q
行,每行包含四个整数 x1,y1,x2,y2
,表示一组询问。

输出格式
共 q
行,每行输出一个询问的结果。

数据范围
1≤n,m≤1000
,
1≤q≤200000
,
1≤x1≤x2≤n
,
1≤y1≤y2≤m
,
−1000≤矩阵内元素的值≤1000
输入样例:
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例:
17
27
21



#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m, k;
int q[N][N];
int s[N][N];  //前缀和数组的和

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
             scanf("%d", &q[i][j]);
        s[i][j] = q[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    while(k--){
        int x1, x2, y1, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x2][y1 -1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
        //**printf("%d\n", s[x2][y2] - s[x2][y1 -1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);**
    }
    return 0;
}




GALA
6天前
  1. 前缀和

输入一个长度为 n
的整数序列。

接下来再输入 m
个询问,每个询问输入一对 l,r。

对于每个询问,输出原序列中从第 l
个数到第 r
个数的和。

输入格式
第一行包含两个整数 n
和 m。

第二行包含 n
个整数,表示整数数列。

接下来 m
行,每行包含两个整数 l
和 r
,表示一个询问的区间范围。

输出格式
共 m
行,每行输出一个询问的结果。

数据范围
1≤l≤r≤n
,
1≤n,m≤100000
,
−1000≤数列中元素的值≤1000
输入样例:
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例:
3
6
10


暴力的方

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 10001;

int n, m;
int q[N];

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &q[i]);
    }

    while(m--){
        int l, r;
        scanf("%d %d", &l, &r);
        int sum = 0;
        for(int i = 1; i <= n; i++){
            sum += q[i];
        }
        printf("%d\n", sum);
    }
    return 0;
}

前缀和(优化)

//前缀和作用——快速求出数组中一段区间的和
//省去了一个for循环
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;

int n, m;
int q[N];
int sum[N];

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &q[i]);
        sum[i] = sum[i - 1] + q[i];
    }

    while(m--){
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", sum[r] - sum[l - 1]);
    }
    return 0;
}



GALA
6天前

一、题目描述
给 定 一 个 长 度 为 n 的 整 数 序 列 , 请 找 出 最 长 的 不 包 含 重 复 的 数 的 连 续 区 间 , 输 出 它 的 长 度 。 给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。给定一个长度为n的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。

输入格式
第 一 行 包 含 整 数 n 。 第一行包含整数 n。第一行包含整数n。
第 二 行 包 含 n 个 整 数 ( 均 在 0 ∼ 1 0 5 范 围 内 ) , 表 示 整 数 序 列 。 第二行包含 n 个整数(均在 0∼10^5 范围内),表示整数序列。第二行包含n个整数(均在0∼10
5
范围内),表示整数序列。

输出格式
共 一 行 , 包 含 一 个 整 数 , 表 示 最 长 的 不 包 含 重 复 的 数 的 连 续 区 间 的 长 度 。 共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。

数据范围
1 ≤ n ≤ 1 0 5 1≤n≤10^51≤n≤10
5

输入样例:

5
1 2 2 3 5
1
2
输出样例:

3
————————————————


双指针方法

//会超时,要优化
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;

int n;
int q[N];

//check——是否有重复的2个数, 有返回false,无返回true
bool check(int left, int right)
{
    for(int i = left; i <= right; i++){
        for(int j = i; j <= right; j++){
            if(i != j && q[i] == q[j]){
                return false;
            }
        }
    }
    return true;
}

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

    int res = 1;
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            if(check(i, j)){
                res = max(res, j - i + 1);
            }
        }
    }
    printf("%d\n",res);
    return 0;
}

__在双指针基础上优化____

//节省一层for循环(for(j)),可以不循环
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n;
int q[N];
int cnt[N];  //记录每个数字出现的次数

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

    int res = 1;
    for(int i = 1, j = 1; i <= n; i++){
        cnt[q[i]]++;
        while(cnt[q[i]] > 1){
            cnt[q[j]]--;  //如果有一个数出现2次及以上,就把前面的“数删掉”(把前面不符合的数的出现次数也减去)(重置数组),再把j的指针移到和i指针同一个数上,重新开始循环
            j++;
        }
        res = max(res, i - j + 1);
    }
    printf("%d\n", res);
    return 0;
}

整 数 序 列——单调不减的(有平有增) (—/----/)




GALA
8天前

汽车拉力比赛

题目描述

博艾市将要举行一场汽车拉力比赛。

赛场凹凸不平,所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500),每个单元格的海拔范围在0到10^9之间。

其中一些单元格被定义为路标。组织者希望给整个路线指定一个难度系数D,这样参赛选手从任一路标到达别的路标所经过的路径上相邻单元格的海拔高度差不会大于D。也就是说这个难度系数D指的是保证所有路标相互可达的最小值。任一单元格和其东西南北四个方向上的单元格都是相邻的。

输入格式

第一行两个整数M和N。第2行到第M+1行,每行N个整数描述海拔高度。第2+M行到第1+2M

行,每行N个整数,每个数非0即1,1表示该单元格是一个路标。

输出格式

一个整数,即赛道的难度系数D。

样例 #1

样例输入 #1

3 5 
20 21 18 99 5  
19 22 20 16 26
18 17 40 60 80
1 0 0 0 1
0 0 0 0 0
0 0 0 0 1

样例输出 #1

21
//带点二分的味道,但实际还是bfs的方法
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510;

int n, m;
int high[N][N];  //存海拔高度
int flag[N][N];  //路标
int cnt_flag = 0;

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            scanf("%d", &high[i][j]);
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            scanf("%d", flag[i][j]);
        }
    }

    //int cnt_flag = 0;  //统计路标总数  //放到全局变量中,使得bfs可以少传一个参数
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            scanf("%d", &flag[i][j]);
            if(flag[i][j] == 1){
                cnt_flag++;
            }
        }
    }

    int x1, y1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(flag[i][j] == 1){
               x1 = i, y1 = j;
               break;  //找到一个“1”路标就行,就可以开始bfs
            }
        }
    }

    //二分思路
    int l = -1,r = 1e9 + 10;
    while(l + 1 < r){

    }
}



GALA
9天前

奇怪的电梯

题目描述

呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第 $i$ 层楼($1 \le i \le N$)上有一个数字 $K_i$($0 \le K_i \le N$)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如: $3, 3, 1, 2, 5$ 代表了 $K_i$($K_1=3$,$K_2=3$,……),从 $1$ 楼开始。在 $1$ 楼,按“上”可以到 $4$ 楼,按“下”是不起作用的,因为没有 $-2$ 楼。那么,从 $A$ 楼到 $B$ 楼至少要按几次按钮呢?

输入格式

共二行。

第一行为三个用空格隔开的正整数,表示 $N, A, B$($1 \le N \le 200$,$1 \le A, B \le N$)。

第二行为 $N$ 个用空格隔开的非负整数,表示 $K_i$。

输出格式

一行,即最少按键次数,若无法到达,则输出 -1

样例 #1

样例输入 #1

5 1 5
3 3 1 2 5

样例输出 #1

3

提示

对于 $100 \%$ 的数据,$1 \le N \le 200$,$1 \le A, B \le N$,$0 \le K_i \le N$。

//暴力的方法,会被卡,完美AC要用bfs
//指数型枚举——选上或者下,两种情况
//优化一下 //每层楼最多走一次取到的方案 一定比 某层楼走过两次以上的方案 要好  //运用全排列思想—选过就不能再选了
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 10010;

int n, A, B;
int evlt[N];  //存当前电梯楼层允许上或者下的楼数
int res = 1e9;  //答案
bool st[N];  //存每层楼走没走过

//x表示当前在几楼
void dfs(int x, int cnt){
    if(cnt >= res) return ;
    if(x < 0 || x > n) return ;

    if(x == B){
        res = min(res, cnt);  //去最优解
        return ;
    }

    st[x] = true;

    //上楼
    if(x + evlt[x] <= n && !st[x + evlt[x]]){
        st[x + evlt[x]] = true;
        //printf("x + evlt[x] = %d\n", x + evlt[x]);
        dfs(x + evlt[x], cnt + 1);
        st[x + evlt[x]] = false;  //恢复现场
    }

    //下楼c
    if(x - evlt[x] > 0 && !st[x - evlt[x]]){
        st[x - evlt[x]] = true;
        //printf("x - evlt[x] = %d\n", x - evlt[x]);
        dfs(x - evlt[x], cnt + 1);
        st[x - evlt[x]] = false;  //恢复现场
    }
}

int main()
{
    scanf("%d%d%d", &n, &A, &B);
    for(int i = 1; i <= n; i++){
        scanf("%d", &evlt[i]);
    }

    dfs(A, 0);
     if(res == 1e9){
        printf("-1\n");
        return 0;
    }
    printf("%d\n", res);
    return 0;


}


分享 pP2895

GALA
10天前

[USACO08FEB]Meteor Shower S

题面翻译

题目描述

贝茜听说一场特别的流星雨即将到来:这些流星会撞向地球,并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑,发誓要找到一个安全的地方(一个永远不会被流星摧毁的地方)。

如果将牧场放入一个直角坐标系中,贝茜现在的位置是原点,并且,贝茜不能踏上一块被流星砸过的土地。

根据预报,一共有 $M$ 颗流星 $(1\leq M\leq 50,000)$ 会坠落在农场上,其中第 $i$ 颗流星会在时刻 $T_i$ 砸在坐标为 $(X_i,Y_i)(0\leq X_i\leq 300$,$0\leq Y_i\leq 300)$ 的格子里。流星的力量会将它所在的格子,以及周围 $4$ 个相邻的格子都化为焦土,当然贝茜也无法再在这些格子上行走。

贝茜在时刻 $0$ 开始行动,它只能在第一象限中,平行于坐标轴行动,每 $1$ 个时刻中,她能移动到相邻的(一般是 $4$ 个)格子中的任意一个,当然目标格子要没有被烧焦才行。如果一个格子在时刻 $t$ 被流星撞击或烧焦,那么贝茜只能在 $t$ 之前的时刻在这个格子里出现。 贝西一开始在 $(0,0)$。

请你计算一下,贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 $−1$。

输入格式

共 $M+1$ 行,第 $1$ 行输入一个整数 $M$,接下来的 $M$ 行每行输入三个整数分别为 $X_i, Y_i, T_i$。

输出格式

贝西到达安全地点所需的最短时间,如果不可能,则为 $-1$。

题目描述

Bessie hears that an extraordinary meteor shower is coming; reports say that these meteors will crash into earth and destroy anything they hit. Anxious for her safety, she vows to find her way to a safe location (one that is never destroyed by a meteor) . She is currently grazing at the origin in the coordinate plane and wants to move to a new, safer location while avoiding being destroyed by meteors along her way.

The reports say that M meteors (1 ≤ M ≤ 50,000) will strike, with meteor i will striking point (Xi, Yi) (0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300) at time Ti (0 ≤ Ti  ≤ 1,000). Each meteor destroys the point that it strikes and also the four rectilinearly adjacent lattice points.

Bessie leaves the origin at time 0 and can travel in the first quadrant and parallel to the axes at the rate of one distance unit per second to any of the (often 4) adjacent rectilinear points that are not yet destroyed by a meteor. She cannot be located on a point at any time greater than or equal to the time it is destroyed).

Determine the minimum time it takes Bessie to get to a safe place.

输入格式

* Line 1: A single integer: M

* Lines 2..M+1: Line i+1 contains three space-separated integers: Xi, Yi, and Ti

输出格式

* Line 1: The minimum time it takes Bessie to get to a safe place or -1 if it is impossible.

样例 #1

样例输入 #1

4
0 0 2
2 1 2
1 1 2
0 3 5

样例输出 #1

5
#include<iostream>
#include<cstring>
#include<algorithm>

#define x first
#define y second


using namespace std;
typedef pair<int, int> PII;

const int N = 310;

int m;
int dist[N][N];
int fire[N][N];  //记录流星砸到(i,j)的时间
PII q[N * N];

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; 

int bfs(){ //知道起点为0 0, 不赋初始值
    q[0] = {0, 0};
    dist[0][0] = 0;
    int hh = 0, tt = 0;

    while(hh <= tt){
        auto t = q[hh++];

        for(int i = 0; i < 4; i++){
            int a = t.x + dx[i], b = t.y + dy[i];

            if(a < 0 || b < 0) continue;
            if(dist[a][b]) continue;
            if(dist[t.x][t.y] + 1 >= fire[a][b]) continue; //流星砸下来了就不能走了

            dist[a][b] = dist[t.x][t.y] + 1;
            q[++tt] = {a, b};

            if(fire[a][b] > 1e9) return dist[a][b];
        }
    }
    return -1;
}

int main()
{   //预处理
    scanf("%d", &m);
    memset(fire, 0x3f, sizeof fire);  //初始化成无穷大
    while(m--){
        int x1, y1, t;
        scanf("%d %d %d", &x1, &y1, &t);
        fire[x1][y1] = min(t, fire[x1][y1]);  //理解这句话
        for(int i = 0; i < 4; i++){
            int a = x1 + dx[i], b = y1 + dy[i];
            if(a < 0 || a > 301 || b  < 0 || b > 301) continue;
            fire[a][b] = min(t, fire[a][b]);  //取最早降落再(x,y)流星的时间  //理解这句话
        }
    }
    //bfs
    int res = bfs();
    printf("%d\n", res);
    return 0;
}



GALA
11天前

tt = -1 和 tt = 0; 初始化的区别,用双指针模拟