【牛客小白月赛24】

B.
题意：选若干个人满足最大值和最小值差不超过k 求人数最大是多少
思路：排序后二分去找当前值+k 更新最大值即可

LL a[N];

int main()
{
    int t ;

    scanf("%d",&t);

    while(t --)
    {
        LL n,k;

        scanf("%lld%lld",&n,&k);

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

        sort(a,a + n);

        int res = 0;

        for(int i = 0;i < n;i ++)
        {
            int r = lower_bound(a,a + n,a[i] + k) - a;

            if(r == n)
            {
                res = max(res,r - i);
                continue;
            }

            if(a[r] != a[i] + k)
                r -- ;

            res = max(res,r - i + 1);
        }

        printf("%d\n",res);
    }

    return 0;
}

C.
题意：包围一个联通块 使得方块的数量最少且与联通块紧密接触
思路：先用dfs把非联通块部分标记 然后遍历地图判断当前标记是否和连通块相连 如果是改成* 最后把没用的标记还原成‘.’即可

#include <bits/stdc++.h>

using namespace std;

char s[505][505];

int n, m;

void dfs(int x,int y)
{
    s[x][y] = 'a';

    if(x > 0 && s[x - 1][y] == '.')
        dfs(x - 1,y);
    if(x < n - 1 && s[x + 1][y] == '.')
        dfs(x + 1,y);
    if(y > 0 && s[x][y - 1]== '.')
        dfs(x,y - 1);
    if(y < m - 1 && s[x][y + 1] == '.')
        dfs(x,y + 1);
}

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

    cin >> n >> m ;

    for(int i = 0; i < n; i ++)
        cin >> s[i];

    dfs(0,0);

    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            if(s[i][j] == 'a')
            {
                if(s[i - 1][j] == '#')
                    s[i][j] = '*';
                if(s[i + 1][j] == '#')
                    s[i][j] = '*';
                if(s[i][j - 1] == '#')
                    s[i][j] = '*';
                if(s[i][j + 1] == '#')
                    s[i][j] = '*';
            }
        }
    }

      for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            if(s[i][j] == 'a')
            {
                s[i][j] = '.';
            }
        }
    }
    for(int i = 0; i < n; i ++)
        cout << s[i] << '\n';

    return 0;
}

D.
题意：给x1 y1 x2 y2 内区间点放置豆子 求任意x1 y1 x2 y2 区间的数量
思路：二维前缀和 先对各个点标记 然后对各个点求前缀得到原数组 再求一次得到前缀和数组

LL sum[N][N];

int main()
{
    int n ,m ,k , q;

    scanf("%d%d%d%d",&n,&m,&k,&q);

    int x1,y1,x2,y2;

    while(k --)
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

        sum[x1][y1] ++;
        sum[x2 + 1][y2 + 1] ++ ;

        sum[x1][y2 + 1] -- ;
        sum[x2 + 1][y1] -- ;
    }

    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1]  - sum[i - 1][j - 1] + sum[i][j];
    }

     for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + sum[i][j] ;
    }

    while(q --)
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

        printf("%lld\n",sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]);
    }

    return 0;
}

F.签到

G.
题意：每道题消耗不同时间 最多能做多少道
思路：贪心 m记得开long long

int a[N];

int main()
{
    int n;
    LL m;

    scanf("%d%lld",&n,&m);

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

    sort(a,a + n);

    int res = 0;

    for(int i = 0;i < n;i ++)
    {
        if(m >= a[i])
        {
            m -= a[i];
            res ++ ;
        }
        else
            break;
    }

    printf("%d\n",res);

    return 0;
}

H.
题意：有多对人 每对有不同的关系 判断关系网中是否存在矛盾
思路：并查集先将为朋友关系的合并 然后根据敌人的关系判断父节点是不是为同一个 如果是的话则矛盾 数据范围大需要离散化

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define mes(x,a) memset(x,a,sizeof(x));
#define sca(a) scanf("%d",&a)
#define lowbit(x)  x & (-x)
#define mk make_pair
#define pb(x) push_back(x)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define pii pair<int, int>

inline int read()
{
    int x=0,flag_read=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            flag_read=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*flag_read;
}

const double eps=1e-9;
const double pi=acos(-1);
const int N = 1e6+5;
const int M = 1e7+5;
const int INF = 0x3f3f3f3f;
const int mod=2e6+5;

int a[N],b[N],c[N];
int fa[N << 1];

vector <int> v;

int findx(int x)
{
    if(fa[x] == x)
        return x;
    return fa[x] = findx(fa[x]);
}

void join(int x,int y)
{
    int xx = findx(x);
    int yy = findx(y);

    if(xx != yy)
        fa[xx] = yy;
}

int main()
{
    int t;

    scanf("%d",&t);

    while(t--)
    {
        v.clear() ;

        int n;

        scanf("%d",&n);

        for(int i = 1;i <= n;i ++)
        {
            scanf("%d%d%d",&a[i],&b[i],&c[i]);
            v.pb(a[i]);
            v.pb(b[i]);
        }

        sort(all(v));
        v.erase(unique(all(v)),v.end());

        for(int i = 1;i <= n;i ++)
        {
            a[i] = lower_bound(all(v),a[i]) - v.begin() + 1;
            b[i] = lower_bound(all(v),b[i]) - v.begin() + 1;
        }

         for(int i = 1;i <= (n << 1);i ++)
            fa[i] = i;

        for(int i = 1;i <= n;i ++)
        {
            if(c[i] == 1)
                join(a[i],b[i]);
        }

        bool flag = 1;

        for(int i = 1;i <= n;i ++)
        {
            if(c[i] == 0)
            {
                int xx = findx(a[i]);
                int yy = findx(b[i]);

                if(xx == yy)
                {
                    flag = 0;
                    break;
                }
            }
        }

        if(flag)
            puts("YES");
        else
            puts("NO");
    }

    return 0;
}

I.
题意：给出一颗树 两种操作：1.给结点x加上y 2.查询结点x的子树大小值
思路：dfs序 + 树状数组 这两个操作分别是单点更新 + 区间查询 用dfs序更新将树形结构转变成线性结构 然后根据in和out 来建立和更新查询

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define mes(x,a) memset(x,a,sizeof(x));
#define sca(a) scanf("%d",&a)
#define lowbit(x)  x & (-x)
#define mk make_pair
#define pb(x) push_back(x)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define pii pair<int, int>


const double eps=1e-9;
const double pi=acos(-1);
const int N = 1e6+5;
const int M = 1e7+5;
const int INF = 0x3f3f3f3f;
const int mod=2e6+5;

vector <int> e[N];

int n, m, k;
int in[N],out[N],num[N],dfn = 0;
int sz[N],c[N];

void dfs(int x,int fa)
{
    in[x] = ++ dfn;
    num[dfn] = x;

    for(int i = 0; i < e[x].size(); i ++)
    {
        int to = e[x][i];

        if(to == fa)
            continue;

        dfs(to,x);
    }

    out[x] = dfn;
}

void update(int x,int y)
{
    for(; x <= n; x += lowbit(x))
        c[x] += y;
}

LL query(int x)
{
    LL res = 0;

    for(; x ; x -= lowbit(x))
        res += c[x];

    return res;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);

    for(int i = 1; i <= n; i ++)
        scanf("%d",&sz[i]);

    for(int i = 0; i < n - 1; i ++)
    {
        int u,v;

        scanf("%d%d",&u,&v);

        e[u].pb(v);
        e[v].pb(u);
    }

    dfs(k, 0);


    for(int i = 1; i <= n; i ++)
        update(in[i],sz[i]);

    int op,x,y;

    while(m --)
    {
        scanf("%d",&op);

        if(op == 1)
        {
            scanf("%d%d",&x,&y);
            update(in[x],y);
        }

        else
        {
            scanf("%d",&x);

            printf("%lld\n",query(out[x]) - query(in[x] - 1));
        }
    }
    return 0;
}

J.
题意：求
思路：

通过最终的式子 前半部分O(n)就可以解决 而对于后半部分我们只要枚举i 然后通过前缀和O(1)得到 n~i也就是j那个部分的区间和是多少 相乘即可 复杂度也是O(n) 注意减法取模会+mod避免答案错误

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define mes(x,a) memset(x,a,sizeof(x));
#define sca(a) scanf("%d",&a)
#define lowbit(x)  x & (-x)
#define mk make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define pii pair<int, int>

inline int read()
{
    int x=0,flag_read=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            flag_read=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*flag_read;
}

const double eps=1e-9;
const double pi=acos(-1);
const int N = 5e5+5;
const int M = 1e7+5;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9+ 7;

LL a[N],sum[N];

int main()
{
    int n;

    scanf("%d",&n);

    for(int i = 1; i <= n; i ++)
        scanf("%lld",&a[i]),sum[i] = (sum[i - 1] + a[i])%mod;

    LL res = 0;

    for(int i = 1; i <= n - 1; i ++)
    {
        LL x = (((a[i]*a[i])%mod)*((n - 1)+mod%mod)%mod)%mod;


        LL y = (((2*a[i])%mod)*((sum[n] - sum[i]+mod%mod)+mod%mod)%mod)%mod;


        res = (res + x- y+mod)%mod;
    }

    res = (res%mod + (((a[n]%mod*a[n]%mod)%mod)*((n - 1)+mod%mod))%mod)%mod;

    printf("%lld\n",res);

    return 0;
}