头像

做题必ac

北京大学




离线:8小时前


最近来访(53)
用户头像
Eurus_
用户头像
NULL_DrakKing
用户头像
weige1015
用户头像
目标大佬的大学生
用户头像
SmiLeeeee
用户头像
取什么名字好呢
用户头像
白之月
用户头像
呐呐呐呐
用户头像
人生如戏ba
用户头像
1357649762
用户头像
rushhhhh
用户头像
爱算法爱生活
用户头像
lzoolloozl
用户头像
一切皆有解
用户头像
chengxi
用户头像
solo起来
用户头像
vendestine
用户头像
SUPERDOGE
用户头像
糕小芝
用户头像
俄罗斯刺沙蓬


做题必ac
8小时前

一份详细的题解,傻瓜都能看懂~

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

using namespace std;

const int N = 100010, M = N * 2;

int n;
int h[N], e[M], ne[M], idx;
int ans = N;
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs(int u) //dfs(u)表示以u号点为根节点,返回u号点的各个子树的结点个数
{
    st[u] = true;

    int res = 0, sum = 0;//sum = 1;    sum用来纪录u的子树中的所有结点
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            int s = dfs(j) + 1; //表示以u号点为根节点的其中一个子树的所有结点个数
            res = max(res, s);
            sum += s;
        }
    }

    res = max(res, n - sum - 1);//需要减去一个u号结点后再和之前的res做比较,看是否能更新res的值
    ans = min(ans, res);  //每个更新一个根节点就选出最小的ans值

    return sum;
}

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

    memset(h, -1, sizeof h);

    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dfs(1);

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

    return 0;
}


活动打卡代码 AcWing 4615. 相遇问题

一道简单的思维题

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    cin >> T;

    while (T -- )
    {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        int d = y - x;
        if (d % (a + b) == 0) cout << d / (a + b) << endl;
        else puts("-1");
    }

    return 0;
}



先纪录题目,防止复习时忘记~

树形dp加邻接表

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 300010, M = N * 2;

int n;
int v[N];
int h[N], e[M], w[M], ne[M], idx;
LL f[N];
LL ans;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int fa)
{
    LL max1 = 0, max2 = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
        if (f[j] - w[i] >= max1)
        {
            max2 = max1;
            max1 = f[j] - w[i];
        }
        else if (f[j] - w[i] > max2)
        {
            max2 = f[j] - w[i];
        }
    }

    ans = max(ans, v[u] + max1 + max2);
    f[u] = v[u] + max1;
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &v[i]);

    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }

    dfs(1, -1);

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


活动打卡代码 AcWing 4619. 减法操作

简单的思维题 应该能作为省赛的签到难度

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n;
int w[N];
bool check()
{
    for (int i = 0; i < n - 1; i ++ )
        if (w[i] % 2)
            w[i] --, w[i + 1] -- ;

    for (int i = 0; i < n; i ++ )
        if (w[i] < 0 || w[i] % 2)  //①判断处理后的数中是否存在负数②判断最后一个数是否为奇数
            return false;
    return true;
}

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

    if (check()) puts("YES");
    else puts("NO");

    return 0;
}



题目描述

Alice and Bob like playing games.

The game is played on a sequence of length n. Alice and Bob take turns performing the operation, with Alice going first.

In each operation, the player can remove an element from the beginning or the end of the sequence.

If this operation is not the first operation of the game, the removed element must be strictly greater than all the previously removed elements.

The player who cannot perform the operation loses.

Please determine who will win the game if both Alice and Bob play the game optimally.

输入格式

The first line contains a single integers n(1≤n≤10^5),representing the length of the sequence.
The second line contains n integers a1,a2,…,an(1≤a≤10^5),representing the sequence.

输出格式

For each test case, print “Alice” if Alice will win the game, otherwise print “Bob”.

样例

输入
3
1 3 2
输出
Bob

时间复杂度

观察下,每次dfs 只会有一个出口,且经过一个dfs后,L,R的大小会减一。所以总共的状态为O(n)个。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
list<int> pre,suf;
int n,a[N];
int dfs(list<int>& L, list<int>& R) 
{
    if (L.size() == 0)return R.size() % 2;
    if (R.size() == 0)return L.size() % 2;
    if (L.front() > R.front()) 
    {
        if (L.size() % 2)return 1;
        else 
        {
            R.pop_front();
            if (dfs(L, R) == 0)return 1;
            else return 0;
        }
    }
    else if (L.front() == R.front()) 
    {
        if (L.size() % 2 || R.size() % 2)return 1;
        else return 0;
    }
    else
    {
        if (R.size() % 2)return 1;
        else 
        {
            L.pop_front();
            if (dfs(L, R) == 0)return 1;
            else return 0;
        }
    }
}
int main() 
{
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    int p = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] > p)pre.push_back(a[i]), p = a[i];
        else break;
    }
    p = 0;
    for (int i = n; i >= 1; i--) 
    {
        if (a[i] > p)suf.push_back(a[i]), p = a[i];
        else break;
    }
    if (dfs(pre,suf))cout << "Alice" << endl;
    else cout << "Bob" << endl;
    return 0;
}




问题链接 点击此处




题目描述

HH有一串由各种漂亮的贝壳组成的项链。
HH相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一 段贝壳,思考它们所表达的含义。
HH不断地收集新的贝壳,因此他的项链变得越来越长。
有一天,他突然提出了一 个问题:某一段贝壳中,包含了多少种不同的贝壳?
这个问题很难回答。。。因为项链实在是太长了。于是,他只 好求助睿智的你,来解决这个问题。

输入描述

第一行:一个整数N,表示项链的长度。
第二行:N个整数,表示依次表示项链中贝壳的编号(编号为0到1000000之间的整数)。
第三行:一个整数M,表示HH询问的个数。
接下来M行:每行两个整数,L和R(1 ≤ L ≤ R ≤ N),表示询问的区间。
N ≤ 50000,M ≤ 200000。

输出描述

M行,每行一个整数,依次表示询问对应的答案。

输出示例

输入
6
1 2 3 4 3 5
3
1 2 
3 5
2 6

输出
2
2
4

算法

(树状数组+前缀和) $O(nlgn)$

C++ 代码

#include<bits/stdc++.h>
const int maxn = 1000010;
using namespace std;
int n,m;
int a[maxn],ans[maxn];
int st[maxn],tree[maxn]; //st[i]表示第i种贝壳在目前询问到的区间中最后出现的位置(也就是最右端

struct QUE  //重载,利用右边界
{
    int l;
    int r;
    int id;
    bool operator < (QUE a ) 
    {
        return r < a.r; 
    }
}q[maxn];

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

void modify(int p,int v)  //构建和修改树状形数组
{
    for(int i = p;i<=n;i+=lowbit(i))
        tree[i]+=v;
}

int query(int p)
{
    int res=0;
    for(int i = p ; i; i-=lowbit(i))
        res+=tree[i];
    return res;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id = i;
    }
    sort(q+1,q+m+1);
    int pow=1;
    for(int i=1;i<=m;++i)
    {
        for(int j=pow;j<=q[i].r;++j)
        {
            if(st[a[j]]) modify(st[a[j]],-1);  //如果第a[j]种贝壳之前已经出现过,则将前缀和减一
            modify(j,1);  //然后在加一,这样就避免了重复
            st[a[j]]=j;  //更新第a[j]种贝壳最后出现的位置
        }
        pow=q[i].r+1;
        ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
    }

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

希望大佬能帮忙解决的问题:

这个树状数组是怎么建起来的?树状数组是怎么维护的?我虽然在解题思路上明白应该按照下图的方法进行操作
屏幕截图 2022-09-23 002643.png

也就是把询问存下来,按照右端点从小到大排序
##但为什么modify能够实现:
第一次碰到一个数,直接在这个位置加1
若非第一次,将这个数上一次出现的位置减1,在当前位置加1?
###树状数组的每一个元素tree[i]本来就是前缀和,不就已经表示了前i个序列中的贝壳种类吗?为什么ans不是tree[R]-tree[L-1]?
###反而还需要再对每一个tree[i]求一次前缀和,对于询问[L,R],ans=sum(R)-sum(L-1)?
######以上这两个疑问,我实在是没有想太明白,看了一些树状数组的相关知识,但还是搞不太明白
希望能有大佬可以帮帮忙解答


问题 牛客

题目链接 牛客挑战赛63

😭身为弱鸡的我,实在是看不懂这个状态是怎么转移的。还有,为什么题解里面是j<=m?f[i][j][]表示在前i个原料里选择j个,不应该是j<=i吗?希望大佬能帮忙解答

希望某个大佬能写一下注释,帮忙理解一下d题😭

题解代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1100, M = 13;
int n, k, m, f[N][M + 1][1 << M]; //设f_{i, j, R}表示在前i个物品中选择了j个放入集合中,元素的并集为R的最大的S的贡献。
//转移时,如果选择放入集合,则直接转移到f_{i + 1, j + 1, R | col_{i + 1}} 
//如果选择不放入集合,那尽可能选择后面的物品,使集合中物品的数量恰好达到上界,容易发现这样的贪心是对的。
pair <int, int> a[N]; //a[i]第一位表示原材料的质量和第二位表示由哪几种元素构成
int main () 
{

    scanf("%d%d%d", &n, &k, &m);
    for (int num, idx, i = 1; i <= n; i++) 
    {
        scanf("%d%d", &a[i].first, &num);
        while (num--) scanf("%d", &idx), a[i].second |= (1 << idx - 1);
    }
    sort(a + 1, a + n + 1);
    int lim = (1 << m) - 1; //每一种元素都选
    memset(f, 128, sizeof f), f[0][0][0] = 0;

    for (int i = 0; i < n; i++)
        for (int j = 0; j <= m; j++)
            for (int S = 0; S <= lim; S++)
            {
                if (j < m) f[i + 1][j + 1][S | a[i + 1].second] = max(f[i + 1][j + 1][S | a[i + 1].second], f[i][j][S]);
                if (n - i <= k - j) f[i + 1][j][S] = max(f[i + 1][j][S], f[i][j][S] + a[i + 1].first);
                f[i + 1][j][S] = max(f[i + 1][j][S], f[i][j][S]);
            }
    long long ans =0 ;
    for (int j = 0; j <= m; j++)
        for (int S = 0; S <= lim; S++)
            ans = max(ans, 1ll * __builtin_popcount(S) * f[n][j][S]);
    printf("%lld\n", ans);

    return 0;
}

代码中部分注释是我写的,但不明白实现的原理。希望有大佬能帮忙分析状态是如何压缩的


新鲜事 原文

有没有大佬分享一下今天刚打完的ccpc网络赛题解啊,想学习下各位大佬的代码。 身为弱鸡的我被打哭了......



#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];

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

    int len = 0;
    for (int i = 0; i < n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }

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

    return 0;
}