当前位置：网站首页>2022牛客寒假补题记录 2

2022牛客寒假补题记录 2

2022-04-21 06:21:00 【Bzdhxs_nt】

A.小沙的炉石

数学结论/二分
感觉考虑区间合并会更好做一些,不过不好想
考虑在有限次的攻击中能造成伤害的最大和最小值
攻击最大次数 $m a x n = m i n (n, m + 1)$ ;
设攻击 $a$ 次,回蓝 $b$ 次,易想到

一次攻击一次回蓝造成的伤害是最低的,伤害序列为 $1, 3, 5, 7 . . . .$ ,伤害为 $a^2$
先使用完法术牌再使用攻击牌伤害是最高的,伤害序列为 $1 + b, 2 + b, 3 + b . . . .$ ,伤害为 $a b + (a + 1) * a / 2$

可以证明通过交换回蓝和攻击的顺序,来实现伤害是连续的,介于最大最小值之间
那么 $a$ 次攻击, $b$ 次回蓝的伤害区间就是 $a^2,ab+(a+1)*a/2]$
那么两个伤害区间可以合并满足 $a-1)*b + a(a-1)/2 >= a^2-1$
隐藏的条件 $a < = b + 1$ 移项可得 $b > = a - 1$
带入上式可得 $a > = 4$
即当 $a > = 4$ 时,答案可以取到 $[1, m a x n * b + (m a x n + 1) * m a x n / 2]$
现在只需要特判 $b = 1$ 和 $b = 2$ 两种情况
可得 $b = 1$ 时伤害区间为 $[1, 2]$ $[4, 5]$ , $b = 2$ 时伤害区间为 $[1, 3] [4, 7] [9, 12]$

int n,m;
signed main()
{
    
    cin>>n>>m;
    n = min(n,m+1);
    int maxn = n*m+n*(n+1)/2;
    int q;cin>>q;
    while(q--){
    
        int x;cin>>x;
        if((m == 1 && x == 3)||(m == 2 && x==8)) puts("NO");
        else if(x > maxn) puts("NO");
        else puts("YES");
    }
    return 0;
}

B.小沙的魔法

并查集/ Kruskal算法 + 思维

容易想到倒着考虑
发现一条边对答案的贡献,让答案最小只与这条边最大点权有关
并且当连通分量为 $1$ 时,肯定是一个生成树
那么我们就可以利用 $K r u s k a l$ 算法的思想,把一条边最小点权为边权然后从大到小排序
不断加入生成树集合中
计算答案 $r e s$ 前先把所有边的边权加上,然后当一条边还未加入生成树集合中时把这条边的边权给减去,最后剩下的 $r e s$ 就是答案
为什么这样呢?
当加入集合中集合中的点同时减少,所以只需要加上一个最小边权就行,故 $r e s$ 要减去一个边的最小点权

int n,m;
int a[500005];
struct edge{
    
    int l,r,v;
    bool operator<(const edge&t)const{
    
        return v >t.v;
    }
}e[5000005];

int pre[500005];
int find(int x){
    
    return x==pre[x]?x:pre[x] = find(pre[x]);
}

signed main()
{
    
    cin>>n>>m;
    int res = 0;
    forr(i,1,n) cin >> a[i], res += a[i],pre[i] = i;
    forr(i,1,m){
    
        int u,v;cin>>u>>v;
        e[i].l = u,e[i].r = v;
        e[i].v = min(a[u],a[v]);
    }
    int x = min(m,5*n);
    sort(e+1,e+1+m);
    forr(i,1,m){
    
        if(!x) break;
        int l = e[i].l,r = e[i].r;
        int val = e[i].v;
        int pl = find(e[i].l),pr = find(e[i].r);
        if(pl != pr){
    
            res -= min(a[l],a[r]);
            x--;
            pre[pl] = pr;
        }
    }
    cout << res << endl;
    return 0;
}

E.小沙的长路

知识点: 欧拉路径
留下了不学无术的眼泪 $Q u Q$
一眼考查欧拉路径
一张完全图的最短路径就是每个点都会走一遍就是 $n - 1$
最大值对于奇数顶点的完全图来说每个点的度都是偶数,存在一条欧拉路经过所有的边,答案为 $n * (n - 1) / 2$ ;
对于偶数顶点的完全图来说只需要把奇数度的点变为2个就可以存在一条欧拉路遍历到剩下的边
所以为 $n * (n - 1) / 2$ 减去 $(n - 2) / 2$ 条边

signed main()
{
    
    int n;cin>>n;
    int maxn = n*(n-1LL)/2 + ((n&1)?0:-n/2+1);
    int minn = n-1;
    cout << minn <<" " << maxn << endl;
    return 0;
}

F.小沙的算数

逆元数学

根据＋号分块,计算就可以了,记录每个位置在第几个块,以及每个块的值
修改的时候先出后乘,取模需要用到逆元

int n,q;
char s[N];
int a[N];
int pos[N];
int va[N];


int qmi(int a,int b){
    
    int res = 1;
    while(b){
    
        if(b&1) res = res*a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return res;
}
int inv(int x){
    
    return qmi(x,mod-2);
}

signed main()
{
    
    _orz;
    cin>>n>>q;
    cin>>s+1;
    s[n] = '+';
    forr(i,1,n) cin>>a[i];
    int val = 1;
    int p = 1;
    forr(i,1,n){
    
        val = val*a[i]%mod;
        if(s[i]=='+'){
    
            pos[i] = p;
            va[p++] = val;
            val = 1;
        }
        else  pos[i] = p;
    }
    p--;
    int res = 0;
    forr(i,1,p) res = (res + va[i])%mod;
    while(q--){
    
        int x,y; cin>> x >> y;
        int t = pos[x];
        int cur = va[t];
        va[t] = va[t]*inv(a[x])%mod*y%mod;
        res = (res + (va[t] - cur+mod)%mod)%mod;
        a[x] = y;
        cout << res << endl;
    }
    return 0;
}

G.小沙的身法

树上差分思想, LCA
重要点在如何计算树上两点见的值呢?
这里用
$s u m [u] [0]$ 表示从 $u$ 结点跳到 $f a$ 结点用的体力
$s u m [u] [1]$ 表示从 $f a$ 结点跳到 $u$ 结点用的体力
那么查询 $< u, v >$ 结果为
$a n s = a [u] + s u m [u] [0] - s u m [l c a (u, v)] [0] + s u m [v] [1] - s u m [l c a (u, v)] [1]$
在这里插入图片描述
类似这样 $s u m [] []$ 求的都是到根节点的相关值

int d[N];
int f[N][20];
int a[N],h[N];
int sum[N][2];

int cnt = 1;
struct node{
    
    int to,ne;
}e[N<<1];

void add(int u,int v){
    
    e[++cnt] = {
    v,h[u]};
    h[u] = cnt;
}
void dfs(int cur,int fa){
    
    d[cur] = d[fa]+1;
    sum[cur][0] = sum[fa][0] + max(0LL,a[fa]-a[cur]);
    sum[cur][1] = sum[fa][1] + max(0LL,a[cur]-a[fa]);
    for(int i = h[cur];i;i = e[i].ne){
    
        int v = e[i].to;
        if(v == fa) continue;
        f[v][0] = cur;
        forr(k,1,18)
            if(f[v][k-1])
                f[v][k] = f[f[v][k-1]][k-1];
            else
                break;
        dfs(v,cur);
    }
}

int lca(int a,int b){
    
    if(d[a] > d[b]) swap(a,b);
    for(int i = 18;i>=0;i--)
        if(d[f[b][i]] >= d[a]) b = f[b][i];
    if(a == b) return a;
    for(int i = 18;i >=0;i--)
        if(f[a][i] != f[b][i]) a = f[a][i],b = f[b][i];
    return f[a][0];
}
int n,m;

signed main()
{
    
    cin >> n >> m;
    forr(i,1,n) cin>>a[i];
    forr(i,1,n-1){
    
        int u,v;
        cin>>u>>v;
        add(u,v);add(v,u);
    }
    dfs(1,0);
    while(m--){
    
        int u,v;
        cin>>u>>v;
        int res = a[u] + sum[u][0]+sum[v][1]-sum[lca(u,v)][0] - sum[lca(u,v)][1];
        cout << res << endl;
    }
    return 0;
}

H.小沙的数数

差不多这个题意
在这里插入图片描述
每个球均不相同且可以放在任何一个盒子里面且允许有空盒 ans = $m^n$ ;
注意一个点 当进行快速幂的时候若底数大于了模数要先取模!!!

int qmi(int a,int b){
    
    int res = 1;
    a %= mod;
    while(b){
    
        if(b&1) res = res*a%mod;
        a = a *a %mod;
        b >>= 1;
    }
    return res;
}

signed main()
{
    
    int n,m;
    cin>>n>>m;
    int t = __builtin_popcountll(m);
    //cout << t << endl;
    cout << qmi(n,t);
    return 0;
}

I.小沙的构造

构造题
代码能力太弱了 $Q w Q$ 哭死~
大佬写的确实好 %%%

string s = "\"!'*+-.08:=^_WTYUIOAHXVM|",  l = "<\\[{(" ,  r = ">/]})", ans;
// "!'*+-.08:=^_WTYUIOAHXVM| <>\/[]{}()
signed main()
{
    
    int n,m;cin>>n>>m;
    if(n==m && n == 1) cout << s[24];
    for(int i = 0; i < 5;i++,m-=2){
    
        if(m <= 2 && (n&1 || m <=1)) break;
        ans = l[i]+ans+r[i];
    }
    for(int i = 0; i < 24;i++,m--){
    
        if(m <= 1) break;
        ans = s[i] + ans +s[i];
    }

    if(ans.size() >= n || m > 1) cout <<-1;
    else{
     // m == 1, m == 0
        while(ans.size()+2 <= n){
    
            if(m==1) ans = s[24]+ans+s[24];
            else ans = r[0]+ans+l[0];
        }
        if(n&1){
    
            for(int i = 0 ; i < n-1;i++){
    
                if(i == n/2) cout << s[24];
                cout << ans[i];
            }
        }
        else cout << ans << endl;
    }
    return 0;
}

L&M 小沙的remake

树状数组优化 $d p$

考虑 dp[i] 表示以a[i]结尾的方案数
转移方式类似于最长上升子序列,子状态的范围在 $[i - b [i], i)$

for(int i = 1; i <= n;i++)
	for(int j = 1; j<= b[i];j++)
		if(a[i] > a[i-j])
			dp[i] += dp[i-j];

即是说对于 $i$ 考虑在 $[i - b [i], i)$ 内且比a[i]权值小的位置
那么对 $a$ 记录初始下标,进行从小到大排序,依次插入到树状数组中,插入前查询下标 $[i - b [i], i)$ 的值 $x$ ,然后把 $x$ 插入到当前下标里
注意,插到下标而不是值;

#include<bits/stdc++.h>
namespace GenHelper
{
    
    int z1,z2,z3,z4,z5,u,res;
    int get()
    {
    
        z5=((z1<<6)^z1)>>13;
        z1=((int)(z1&4294967)<<18)^z5;
        z5=((z2<<2)^z2)>>27;
        z2=((z2&4294968)<<2)^z5;
        z5=((z3<<13)^z3)>>21;
        z3=((z3&4294967)<<7)^z5;
        z5=((z4<<3)^z4)>>12;
        z4=((z4&4294967)<<13)^z5;
        return (z1^z2^z3^z4);
    }
    int read(int m) {
    
        u=get();
        u>>=1;
        if(m==0)res=u;
        else res=(u/2345+1000054321)%m;
        return res;
    }
     void srand(int x)
    {
    
        z1=x;
        z2=(~x)^(0x23333333);
        z3=x^(0x12345798);
        z4=(~x)+51;
      	u = 0;
    }
}
using namespace GenHelper;
using namespace std;
const int N=2e6+7,mod=1e9+7;
int a[N],b[N];
int t[N];
int n,seed;
int lowbit(int x){
    
    return x&-x;
}
void add(int p,int x){
    
    for(int i = p;i<=n;i+=lowbit(i))
        (t[i] += x)%=mod;
}

int ask(int x){
    
    int res = 0;
    for(int i = x;i;i-=lowbit(i))
        (res += t[i]) %= mod;
    return res;
}
struct node{
    
    int id,v;
    bool operator<(const node&t)const{
    
        return v == t.v? id<t.id:v < t.v;
    }
}s[N];
int main(){
    
    scanf("%d %d",&n,&seed);
	srand(seed);
	for(int i=1;i<=n;i++){
    
		a[i]=read(0),b[i]=read(i);
        s[i].id = i,s[i].v = a[i];
	}

    sort(s+1,s+1+n);
    for(int i = 1;i <=n;i++){
    
        int id = s[i].id;
        int x = (ask(id-1) - ask(id-b[id]-1)+1+mod)%mod; // 加一是考虑到可以第一个选自己
        add(id,x);
    }
    cout << ask(n) << endl;
    return 0;
}

总结

这套下来给我的感觉

离散中图论的基础知识掌握的非常差劲,例如: 判是否有欧拉路径的条件,极大联通子图定义等
想出题人所说的铜牌题都是我已经掌握并且多次使用的算法,我不会做是因为不知道如何利用算法去解决这个问题,也就是说思维和代码能力过于薄弱,如果给出思路的话可以利用自己手中的算法给轻松解决
数学能力, 多练确实可以让自己思考的更多

版权声明
本文为[Bzdhxs_nt]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_51687628/article/details/123876107