首页 > 其他分享 >noip模拟8

noip模拟8

时间:2024-11-07 16:19:15浏览次数:1  
标签:log noip int freopen ans now 模拟 Mod

A 图书管理

之前考过。。。

但是我忘了咋写了,然后随便胡了个动态开点权值数上去,\(O(n^2\log n)\) 拿了 \(80\)。。。

维护一个桶,检测到进来的两个数在中位数同侧,则中位数移动,否则不移动,然后就好了?。。。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1e4+4;
int mx=1e4;
int a[N];
bitset<N>vis;
signed main()
{
	freopen("book.in","r",stdin);
	freopen("book.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;long long ans=0;
	for(int i=1;i<=n;i++)cin>>a[i],ans+=(1ll*i*i*a[i]);
	for(int i=1;i<=n;i++)
	{
		int now=a[i];
		vis.reset();
		vis[a[i]]=1;
		for(int j=i+2;j<=n;j+=2)
		{
			int a1=a[j-1],a2=a[j];
			if(a1>a2)swap(a1,a2);
			vis[a1]=1,vis[a2]=1;
			if(a1<now&&a2>now);
			else if(a1<now&&a2<now) 
			{
				--now;
				while(!vis[now])now--;
			}
			else if(a1>now&&a2>now)
			{
				++now;
				while(!vis[now])now++;
			}
			ans+=(1ll*i*j*now);
		}
	}
	cout<<ans;
	return 0;
}

哎呀我是真唐,这都忘了。。

B 两棵树

连通块数 = 剩余的点数 − 剩余的边数

贡献被拆成四个部分:点 × 点 − 边 × 点 − 点 × 边 + 边 × 边

这里以 边 × 边 为例,对于树 \(T\) 的边 \((u,v)\) 假设它被保留(概率 \(\frac 1 4\))

则树 \(U\) 中 \(u,v\) 必定被删除

计算树 \(u\) 中有多少边 \((x,y)\) 不以 \(u\) 或 \(v\) 为端点

每条边 \((x,y)\) 都有 \(\frac 1 4\) 概率被保留

用 set 维护每个点的边,时间复杂度 \(O(n\log n)\)

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int Mod(int x)
{
	if(x<0)
	{
		if(x<=-mod) x%=mod;
		if(x==0) return 0;
		return x+mod;
	}
	return x>=mod?x%mod:x;
}
const int inv2=499122177,inv4=748683265,inv8=873463809,inv16=935854081;
const int maxn=2e5;
set<pair<int,int> >se;
int deg[maxn+5];
signed main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n;cin>>n;
	int ans=Mod(Mod(n*Mod((n-1)*inv4))-Mod((n-2)*Mod((n-1)*inv4)));
	for(int i=1;i<n;i++)
	{
		int u,v;cin>>u>>v;
		if(u>v)swap(u,v);
		se.insert({u,v});
		deg[u]++,deg[v]++;
	}
	for(int i=1;i<n;i++)
	{
		int u,v;cin>>u>>v;
		if(u>v)swap(u,v);
		ans=Mod(ans+Mod((n-1-deg[u]-deg[v]+se.count({u,v}))*inv16));
	}
	cout<<ans;
	return 0;
}

C 函数(fun)

实际上 \(O(n^2)\) 可以过百万。。。

然后有一个优化可以直接干过标算,就是我们知道异或有一个性质是 \(A\text{ xor }B\text{ xor }A=B\),那我们可以开 \(map\) 存每个 \(x_i\),然后枚举 \(j=a\text{ xor }x\),找到 \(j\in{[0,B]}\) 的所有,去反过来找 \(j\text{ xor }a=x\) 在 \(map\) 里面有没有,如果有,那看它的上一位或者下一位有没有大于 \(B\) 的,因为这样找到的 \(j\) 一定小于 \(B\),那两个函数就是异号,乘起来小于等于 \(0\)。

否则如果 \(B>n\),直接跑暴力得了,因为枚举次数小于 \(B\) 的。

然后就过了,如果手写哈希表能更快。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
const int N=1e6+5;
int x[N];
int a,b;
inline int f(int i)
{
	return (i^a)-b;
}
unordered_map<int,int>mp;
signed main()
{
//	freopen("C.in","r",stdin);
//	freopen("C1.out","w",stdout);
	freopen("fun.in","r",stdin);
	freopen("fun.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>x[i],mp[x[i]]=i;
	while(q--)
	{
		cin>>a>>b;
		int ans=0;
		if(b>n)
		{
			for(int i=n-1;i>=1;i--)
			{
				if(f(x[i])*f(x[i+1])<=0){ans=i;break;}
			}
		}
		else
		{
			for(int i=b;i>=0;i--)
			{
				int now=mp[i^a];
				if(!now)continue;
				if(now<n&&(x[now+1]^a)>=b)
				{
					ans=now;break;
				}
				if(now>1&&(x[now-1]^a)>=b)
				{
					ans=now-1;break;
				}
			}
		}
		ans=ans>0?ans:-1;
		cout<<ans<<"\n";
	}
	return 0;
}

正解是这样的:

30pts

\(O(n^2)\) 枚举所有情况。

60pts

通过整体二分,判定 \([1,mid]\) 内是否有解的方式找到第一组解,或利用离线数据结构技巧进行求解,复杂度为 \(O(n \log n \log C)\),与正解关联性不大。

100pts

求解 \(x_i \oplus a\) 最小和最大的两个位置 \(c_1,c_2\),如果 \(f(c_1) \times f(c_2) > 0\) 显然无解。

否则每次取 \(c_1,c_2\) 中点 \(mid\),因为 \(f(c_1),f(c_2)\) 异号,所以 \(f(c_1),f(mid)\) 和 \(f(mid),f(c_2)\) 必然有一对异号,每次区间长度减半,因此重复 \(\log\) 次即可。

求解 \(x_i \oplus a\) 最小和最大的两个位置 \(c_1,c_2\) 可以利用 trie 快速求解,时间复杂度为 \(((n+q) (\log n + \log V))\)。

D 编辑(edit.cpp)

全输出零有 60,望周知。

30pts

枚举 \(T\) 的某一子串进行编辑距离求解的DP,具体状态为让 \(A\) 变成 \(B\),现在只考虑 \(A[1:i]\) 变成 \(B[1:j]\) 的编辑距离为 \(f[i][j]\),转移时考虑删除,添加,修改第 \(i+1\) 个位置即可,时间复杂度为 \(O(n^4)\)​。

100pts

枚举每个后缀,\(f_{i,j}\) 表示最大的 \(x\),使得 \(S[1:x]\) 和 \(T[1:x+j]\) 可以在 \(i\) 次编辑内得到,显然若 \(x\) 可以,所有\(x_0 \leq x\), \(S[1:x_0]\) 和 \(T[1:x_0+j]\) 都可以在 \(i\) 次编辑内得到。

考虑如何转移,先考虑做完第 \(j\) 次编辑操作后往外延申,可以延申的即为 \(S\) 的一个后缀和 \(T\) 的一个后缀的最长公共前缀,即\(f_{i,j} = f_{i,j} + \text{LCP}(S[f_{i,j + 1}:|S|],T [f_{i,j} + j + 1 . .: |T|])\),随后我们可以通过对\(f_{i+1,j-1},f_{i+1,j},f_{i+1,j+1}\) 三项进行转移,即考虑下一次的编辑的具体操作是删除添加还是修改。

每次要算的两个后缀的前缀下标不会差超过 \(k\),因此一共至多求 \(O(nk)\) 次 LCP,可以利用二分+ hash 的方式解决。

记录每个后缀中 \(f_{i,j}=|S|\) 的那些状态,即可计算出最终答案,时间复杂度为 \(O(nk^2+nk \log n)\)。

标签:log,noip,int,freopen,ans,now,模拟,Mod
From: https://www.cnblogs.com/ccjjxx/p/18533001

相关文章

  • 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就出过一道这样的题。写完后调了下二分边界过了大样......
  • CSP2024 前集训:多校A层冲刺NOIP2024模拟赛18
    前言不知道咋回事儿?脑子里一直放歌。然后T3空间给了256,开了256.23死了。T1选彩笔显然可以二分答案,所以现在有了\(O(nv^3\logv)\)的做法,去重后可以拿到\(80pts\),发现直接三维前缀和就可以做到\(O(v^3\logv)\)。点击查看代码#include<bits/stdc++.h>#definell......
  • 『模拟赛』NOIP2024加赛2
    Rank一直烂,什么时候触底反弹(A.新的阶乘赛时觉得线筛一遍同时统计每个质数的指数就做完了,然后本机怎么跑不进1s,卡常卡了半个小时,最后没T,但是vector炸了,70pts。可以换思路考虑,赛时一直没转换过来。对于每个质数枚举其倍数统计贡献。复杂度不知道多少,跑得中等速度。点......
  • 「模拟赛」NOIP2024 模拟 2
    Rank14,190pts比赛链接新的阶乘容易发现只需要处理1~n的质因子分解即可,每个数\(i\)本来有\(n-i+1\)个我们在欧拉筛的过程中同时维护每个数的一个质因子\(pri\)每次从\(n\)到1把遇到的非质数\(i\)现有的个数加到他的质因子\(pri_i\)和\(\frac{i}{pri_i......
  • [NOIP2022] 比赛 随机排列 部分分
    看到最大值,考虑使用单调栈搞出\([la_i,ra_i],[lb_i,rb_i]\)表示这一段区间\(i\)是\(a,b\)的最大值。预处理是简单的。inlinevoidinit(){staticautof=[](inta[],intl[],intr[])->void{staticintstack[N],top;top=0,a[n+......