首页 > 其他分享 >NOIP 模拟 2

NOIP 模拟 2

时间:2024-11-07 17:22:42浏览次数:1  
标签:NOIP int sum it1 mod it2 模拟 size

T1 四舍五入

假设有 \(\frac{a}{b}\),向下取整和四舍五入结果相同当且仅当 \(a\bmod b<\frac{b}{2}\),然后这个东西枚举除数很好做,但是这题让正着做,所以就相当于倒着区间加,复杂度是调和级数。

T2 填算符

神秘东西。
先按位考虑,发现最终的答案与和或都是连续的,可能中间会分一下,再简单分析一下,发现把与全放前面的答案一定可以是最优的,证明就是最后的数决定有无,所以直接保证最后的数全有即可。
然后考虑有那些或和与可以交换位置,贪心的从后检查每一个或,指针为 \(i\),然后再检查贪心的检查最后一个与,指针为 \(j\),由于这个东西有单调性,所以 \(i\) 指针是单调递减的,它之后的符号都是确定的,考虑在这个过程中,处理出后面的东西,然后对于检查是否可行,就是到当前 \(j\) 位置的与或上一段或后,看看是否能满足答案的最低要求,如果交换成功,答案的要求不变,否则后面多或了一个数,可以降低答案的要求。
讲的什么东西,自己看了都蚌埠住,你还是看别人的去吧。

T3 道路修建

不是很清新的数据结构,有经典 trick:路径长度转化为边的经过次数。
考虑环边和树边,来一张图
image
环上的点都带一棵子树,所以环上每条边的经过次数是 \({n\choose 2}-\sum{size\choose 2}\)。
再考虑树边,首先有子树内的情况,然后还有向外的情况,向外的情况连向每一个点有两种方案,发现子树内的情况统计比较麻烦,但是这种情况在加边前就有了,而向外的情况有一半也在加边前有了,所以考虑只计算新的贡献。
环上的边的新贡献:在上一个基础上,每条边减去加边前的经过次数 \(sizet_u(n-sizet_u)\),所以总次数就是 \(m({n\choose 2}-\sum{size\choose 2})-\sum{sizet_u(n-sizet_u)}\)。
树边的新贡献:\(\sum sum_u(n-size_u)=n\sum sum_u-\sum sum_usize_u\)。
\(size_u,sum_u\) 分别表示子树大小,子树内节点到子树根的距离之和,由于这是一个环,所以除了 \(sizet_u\),其他信息都表示 \(u\) 的父亲除去儿子 \(u\) 的信息,端点信息特殊处理,\(LCA\) 处换根处理信息。倍增维护 \(size_u,sum_u,sum_usize_u,sizet_u(n-sizet_u)\) 即可。
两部分的和加上原来的贡献就是答案,原来的答案直接搜一遍得出。

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii std::pair<int,int>
#define eb emplace_back
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=3e5+10,mod=998244353,inf=1e9,ny=499122177;
inline void Min(int &x,int y){if(x>y)x=y;}
inline void Max(int &x,int y){if(x<y)x=y;}
inline void W(int &x,int y){x=(x+y)%mod;}
int n,Q,type,size[N],sum[N],ans,dfn[N],dn,lastans,de[N],rt[N];
int size_[20][N],sfa[20][N],sum_[20][N],mul[20][N],at[20][N],st[20][N];
std::vector<int> e[N];
inline void dfs(int x,int fa,int dep){
    de[x]=dep;size[x]=1;sfa[0][x]=fa;st[0][dfn[x]=++dn]=fa;
    for(int i=1;i<=std::__lg(dep);++i)sfa[i][x]=sfa[i-1][sfa[i-1][x]];
    for(int v:e[x]){
        if(v==fa)continue;
        dfs(v,x,dep+1);W(size[x],size[v]);W(ans,size[v]*(n-size[v]));W(sum[x],sum[v]+size[v]);
    }
    for(int v:e[x]){
        if(v==fa)continue;
        sum_[0][v]=sum[x]-sum[v]-size[v];
        size_[0][v]=(size[x]-size[v])*(size[x]-size[v])%mod;
        at[0][v]=size[v]*(n-size[v])%mod;
        mul[0][v]=sum_[0][v]*(size[x]-size[v])%mod;
    }
}
inline int get(int x,int y){return dfn[x]<dfn[y]?x:y;}
inline void init(){for(int i=1;i<=std::__lg(n);++i)for(int j=1;j+(1<<i)-1<=n;++j)st[i][j]=get(st[i-1][j],st[i-1][j+(1<<i-1)]);}
inline int LCA(int u,int v){
    if(u==v)return u;
    if((u=dfn[u])>(v=dfn[v]))std::swap(u,v);
    int d=std::__lg(v-u++);
    return get(st[d][u],st[d][v-(1<<d)+1]);
}
struct SOME{int fa,size,sum,at,mul;};
inline void dfs1(int x,int fa,int dep){
    W(rt[x],rt[fa]-size[x]+n-size[x]);if(x==1)rt[x]=sum[x];
    for(int i=1;i<=std::__lg(dep);++i){
        W(sum_[i][x],sum_[i-1][x]+sum_[i-1][sfa[i-1][x]]),
        W(size_[i][x],size_[i-1][x]+size_[i-1][sfa[i-1][x]]),
        W(at[i][x],at[i-1][x]+at[i-1][sfa[i-1][x]]),
        W(mul[i][x],mul[i-1][x]+mul[i-1][sfa[i-1][x]]);
    }
    for(int v:e[x])if(v!=fa)dfs1(v,x,dep+1);
}
inline SOME GET(int u,int k){
    if(k<0)return {0,0,0,0,0};
    if(k<=0)return {u,0,0,0,0};
    SOME res={0,0,0,0,0};
    for(int i=std::__lg(k);~i;--i){
        if((k>>i)&1){
            W(res.size,size_[i][u]);W(res.sum,sum_[i][u]);W(res.mul,mul[i][u]);W(res.at,at[i][u]);
            u=sfa[i][u];
        }
    }res.fa=u;
    return res;
}
inline SOME ROOT(int u,int v,int lca){
    int a=n-size[u]-size[v],b=rt[lca]-sum[u]-size[u]-sum[v]-size[v];
    return{0,a*a%mod,b,(size[v]*(n-size[v])+size[u]*(n-size[u]))%mod,a*b%mod};
}
inline void ask(int u,int v){
    int lca=LCA(u,v),L=1;
    int k=de[u]-de[lca]-1;L+=k+1;auto it1=GET(u,k);if(u!=lca)W(it1.size,size[u]*size[u]),W(it1.sum,sum[u]),W(it1.mul,size[u]*sum[u]);
    k=de[v]-de[lca]-1;L+=k+1;auto it2=GET(v,k);if(v!=lca)W(it2.size,size[v]*size[v]),W(it2.sum,sum[v]),W(it2.mul,size[v]*sum[v]);
    auto it3=ROOT(it1.fa,it2.fa,lca);
    int sizesum=it1.size+it2.size+it3.size,yuan=it1.at+it2.at+it3.at,ss=it1.sum+it2.sum+it3.sum,smul=it1.mul+it2.mul+it3.mul;
    lastans=(L*(n*n-sizesum)%mod*ny%mod-yuan+n*ss%mod-smul)%mod;lastans=(lastans+ans+mod)%mod;
    std::cout<<lastans<<'\n';lastans*=type;
}
signed main(){
    freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read(),Q=read(),type=read();
    for(int i=1;i<n;++i){int u=read(),v=read();e[u].eb(v);e[v].eb(u);}
    dfs(1,0,0);dfs1(1,0,0);init();
    while(Q--)ask(read()^lastans,read()^lastans);
}

T4 逆序图

计数,不会。

总结

打的退役分,T2 不会高分暴力,T3,T4 一点不会,菜逼。

标签:NOIP,int,sum,it1,mod,it2,模拟,size
From: https://www.cnblogs.com/Ishar-zdl/p/18533149

相关文章

  • NOIP 模拟 4
    T1玩游戏神秘贪心。先拆成两个序列\(a,b\),需要保证时刻有前缀和\(sum_i+sum_j\le0\),首先两边贡献如果能为非正数,先看能否往两边跳,如果都跳不了无解,其实就是贪心地跳到前缀和比当前小的地方。跳到贡献为正数时,来到了两个序列前缀和的最低点,考虑从两边往中间跳每次也是往低跳,......
  • NOIP 模拟 6
    T1新的阶乘(factorial)线性筛出质数和每个数的最小质因数,然后直接算即可。T2博弈树(tree)结论:当且仅当起点为直径中心时,后手必胜。证明:先考虑只在直径上的博弈,如果起点在直径的一端,先手必胜,设直径长为\(len\),如果在端点的下一个位置,先手可以移动\(len-2\)到对称位置,此时后手......
  • NOIP 模拟 5
    T1选彩笔(rgb)观察到值域较小,考虑静态值域三维偏序,人话:三维前缀和。三维前缀和的式子:get(i,j,k,x,y,z)=s[i][j][k]-s[i][j][z-1]-(s[i][y-1][k]-s[i][y-1][z-1])-(s[x-1][j][k]-s[x-1][y-1][k]-s[x-1][j][z-1]+s[x-1][y-1][k-1]);,直接几何意义推的,但是高维前缀和有通式。然后二分......
  • noip模拟8
    A图书管理之前考过。。。但是我忘了咋写了,然后随便胡了个动态开点权值数上去,\(O(n^2\logn)\)拿了\(80\)。。。维护一个桶,检测到进来的两个数在中位数同侧,则中位数移动,否则不移动,然后就好了?。。。点击查看代码#include<bits/stdc++.h>usingnamespacestd;intn;cons......
  • NOIP2024集训Day71 贪心
    NOIP2024集训Day71贪心B.[CCO2015]饥饿的狐狸显然的,要求出最大美味值,应该先交错吃温度最大的和最小的饼干。所以我们给所有饼干按照温度排序,交替选择左右端点吃,如果喝水能够达到更大那就先喝水再吃,反正水管够。分两种情况,即左右端点谁先开始,再取个\(\operatorname{max}\)。......
  • lanqiaoOJ 1110:小王子单链表 ← 数组模拟实现
     【题目来源】https://www.lanqiao.cn/problems/1110/learning/【题目描述】小王子有一天迷上了排队的游戏,桌子上有标号为1-10的10个玩具,现在小王子将他们排成一列,可小王子还是太小了,他不确定他到底想把哪个玩具摆在哪里,直到最后才能排成一条直线,求玩具的编号。已知他排......
  • 基于Arduino的数码管显示变阻器模拟量读取值
    题目要求采集变阻器模拟量信号在数码管中显示,要求有二位小数电路连接数码管连接:数码管的七个段(a-g)分别连接到Arduino的引脚2到8。数码管的小数点(dp)连接到Arduino的引脚9。数码管的4个控制引脚连接到Arduino的引脚10到11。变阻器连接:变阻器的模拟输出引脚连接到Arduin......
  • 多校A层冲刺NOIP2024模拟赛18
    多校A层冲刺NOIP2024模拟赛18T1选彩笔(rgb)签到题,但是没签上。。。没想到三维前缀和,直接上了个bitset。就是直接二分答案,然后枚举这三维每维的区间的起点,前缀和查数量是否大于等于$K$即可,也可以把二分答案改为第一维的双指针,少一个$log$。T2兵蚁排序(sort)比T1还签......
  • CSP2024 前集训:NOIP2024加赛 2
    前言T2开太晚了,没打完,别的没怎么挂。哦对,T1以为埃筛复杂度是\(nlog^2\),实际上是\(n\ln(\ln(n))\),结果以为复杂度是错的,然后本地不开O2都飞快,我甚至还在惊叹本地竟然能跑\(5e9\)……还有我之前不知道树的直径的中点时唯一的……T1新的阶乘直接埃筛做完了。点击查......
  • NOIP2024 模拟赛 #15 总结
    Larunatrecy:信心赛。赛时T1求中位数,想起前两天做过的[ABC203D]Pond,考虑了二分答案。看出二分答案后不会做了,罚坐\(20\)min。然后发现我傻逼了,选出一个区间翻转,可以通过钦定右端点,找到最优的左端点得到,神仙Heldivis就出过一道这样的题。写完后调了下二分边界过了大样......