首页 > 其他分享 >【比赛】高一小学期2

【比赛】高一小学期2

时间：2024-07-08 11:41:44浏览次数：9  
标签：bd qr 比赛 rs int 一小 zb 学期 ch

挺唐的比赛，一道数位 dp 原题一道平衡树，然后 T1 数据范围还整错了。。

没图了呜呜

【比赛】高一小学期2

$Rank$
赛时

image

日前赛后

image
image

T1 同类分布

思路

印象里为数不多搞懂了的数位 dp，但过太久忘了，只能赛时打暴力

后来发现跟正解很接近了，只是在 dfs 前的预处理上出了点问题。

用记搜做，记搜前循环遍历所有可能的数字和 \(s\) 作为模数，\(len\) 为当前搜到的位数，\(sum\) 为当前所有数字和，\(logos\) 存当前数对 \(s\) 取模的结果，\(lmt\) 判断当前是否达到上限。

由于每次模数 \(s\) 不同，所以 dp 数组需要每轮清空，多次用到 memset，所以数组大小要开适量。

Code：

#include<bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch=getchar();lx 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;
}
#undef lx
#define qr qr()
const int Ratio=0;
ll a,b,cnt,s;
ll num[20],f[20][163][163];
// 最多19位数，sum 最大值为 1+18*9=162
namespace Wisadel
{
	inline ll Wdfs(int len,int sum,int logos,int lmt)
	{
		if(sum+9*len<s) return 0;// 小剪枝 
		if(!lmt&&f[len][sum][logos]!=-1) return f[len][sum][logos];// 记录过 
		if(!len) return logos==0&&sum==s;// 搜到末尾 
		ll res=0,maxx=lmt?num[len]:9;
		fo(i,0,maxx)
			res+=Wdfs(len-1,(sum+i),(logos*10+i)%s,lmt&&i==maxx);
		if(!lmt) f[len][sum][logos]=res;// 记忆 
		return res;
	}
	inline ll Ws(ll x)
	{
		cnt=0;ll ans=0;
		while(x) num[++cnt]=x%10,x/=10;
		for(s=1;s<=cnt*9;s++)
		{
			memset(f,-1,sizeof f);
			ans+=Wdfs(cnt,0,0,1);
		}
		return ans;
	}
	short main()
	{
		freopen("a.in","r",stdin),freopen("a.out","w",stdout);
		a=qr,b=qr;
		printf("%lld\n",Ws(b)-Ws(a-1));
		return Ratio;
	}
}
int main(){return Wisadel::main();}

T2 千山鸟飞绝

思路

首先（才不是只会）考虑暴力的思路，开一个结构体存每只鸟的有关信息，用 map 将坐标离散成点，\(num_i\) 存每个点实时鸟数量，\(pre_{i,j}\) 表示 \(i\) 点第 \(j\) 只鸟的下标。

注意到有鸟会飞走，静态数组不能很好地进行删除替换，所以我们令飞走的第 \(j\) 只鸟下标为 \(-1\)，然后还要一个 \(ttot_i\) 记录 \(i\) 点一共来过多少只鸟。

写一个 pushup 操作，每当鸟变化后 \(num_i>1\) 时运行，更新该点每个鸟的信息。

暴力本来期望的分 \(50pts\)，但我只拿了 \(40pts\)，怎么绘世呢？

考虑鸟的数量最多为 \(30000\)，为了防止 MLE，我只把 \(pre\) 数组开到了 \(30000\times 150\)，然而那个测试点中显然有个点来了超过 \(150\) 只鸟，然后就 GG 了。

暴力 $50pts's\,code$： 
#include<bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx int
inline lx qr()
{
	char ch=getchar();lx 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;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=30005;
int n,t,tot;
struct rmm
{
	int id,xx,yy,ww,zb;
	int sq=0,tj=0;
}bd[N];
map<pair<int,int>,int>mp;
int num[N*2],pre[N*2][308],ttot[N*4];
namespace Wisadel
{
	void Wpushup(int zbb)
	{
		fo(i,1,ttot[zbb])
		{
			if(pre[zbb][i]==-1) continue;
			int maxsq=-2147483647,k=pre[zbb][i];
			bd[k].tj=max(bd[k].tj,num[zbb]-1);
			fo(j,1,ttot[zbb])
			{
				if(i==j) continue;
				int kk=pre[zbb][j];
				maxsq=max(maxsq,bd[kk].ww);
			}
			bd[k].sq=max(bd[k].sq,maxsq);
		}
	}
	void Wfin(int v)
	{
		fo(i,1,ttot[bd[v].zb])
			if(pre[bd[v].zb][i]==v)
			{
				pre[bd[v].zb][i]=-1;
				break;
			}
		num[bd[v].zb]--;
	}
	short main()
	{
		freopen("a.in","r",stdin),freopen("a.out","w",stdout);
		n=qr;
		fo(i,1,n)
		{
			bd[i].id=i,bd[i].ww=qr,bd[i].xx=qr,bd[i].yy=qr;
			if(!mp[{bd[i].xx,bd[i].yy}]) mp[{bd[i].xx,bd[i].yy}]=++tot;
			bd[i].zb=mp[{bd[i].xx,bd[i].yy}];
			num[bd[i].zb]++,ttot[bd[i].zb]++,pre[bd[i].zb][ttot[bd[i].zb]]=i;
			if(num[bd[i].zb]>1) Wpushup(bd[i].zb);
		}
		t=qr;
		while(t--)
		{
			int a=qr,b=qr,c=qr;int i=a;
			Wfin(a);
			if(!mp[{b,c}]) mp[{b,c}]=++tot;
			bd[i].xx=b,bd[i].yy=c;
			bd[i].zb=mp[{b,c}];
			num[bd[i].zb]++,ttot[bd[i].zb]++,pre[bd[i].zb][ttot[bd[i].zb]]=i;
			if(num[bd[i].zb]>1) Wpushup(bd[i].zb);
		}
		fo(i,1,n) printf("%lld\n",1ll*bd[i].sq*bd[i].tj);
		return Ratio;
	}
}
int main(){return Wisadel::main();}

然后考虑平衡树做法。打出暴力能加深对题目的理解(确信)，现在我们知道可以用 Splay 维护每个点的有关信息，每秒进行以下操作：

  • 将该鸟从原树中删除；
  • 将该鸟的武力值更新到前往的树中，用标记记录树上士气值和团结值；
  • 将该树中的士气值更新给该鸟；
  • 将该鸟插入前往的树对应的 Splay 中。

之后下放标记，输出答案即可。

Code：

#include<bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx int
inline lx qr()
{
	char ch=getchar();lx 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;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=30005;
int n,t,tot;
pair<int,int>zb[N];
int rt[N<<2],fa[N],son[N][2],siz[N];// Splay 
int maxv[N],v[N],sq[N],tj[N];// 每个鸟的信息 
int sqbj[N],tjbj[N];// 标记 
map<pair<int,int>,int>mp;// 离散化 
namespace Wisadel
{
	#define ls(x) son[x][0]
	#define rs(x) son[x][1]
	void Wcler(int x)
	{//飞走 清除数据 
		fa[x]=ls(x)=rs(x)=0;siz[x]=1;maxv[x]=v[x];sqbj[x]=tjbj[x]=0; 
	}
	void Wpushup(int x)
	{
		siz[x]=siz[ls(x)]+siz[rs(x)]+1;
		maxv[x]=max(v[x],max(maxv[ls(x)],maxv[rs(x)]));
	}
	//传递标记 
	void Wmark(int x,int a,int b)
	{
		sqbj[x]=max(sqbj[x],a),sq[x]=max(sq[x],sqbj[x]);
		tjbj[x]=max(tjbj[x],b),tj[x]=max(tj[x],tjbj[x]);
	}
	void Wpushdown(int x)
	{
		if(sqbj[x]) Wmark(ls(x),sqbj[x],0),Wmark(rs(x),sqbj[x],0),sqbj[x]=0;
		if(tjbj[x]) Wmark(ls(x),0,tjbj[x]),Wmark(rs(x),0,tjbj[x]),tjbj[x]=0;
	}
	void Wrotate(int x)
	{
		int y=fa[x],z=fa[y],fla=rs(y)==x;
		fa[x]=z;if(z) son[z][rs(z)==y]=x;
		son[y][fla]=son[x][!fla],fa[son[y][fla]]=y;
		son[x][!fla]=y,fa[son[x][!fla]]=x;
		Wpushup(y),Wpushup(x);
	}
	void Wpdrt(int x)
	{// 从该 Splay 的根开始下放 
		if(fa[x]) Wpdrt(fa[x]);
		Wpushdown(x);
	}
	void Wsplay(int x)
	{
		Wpdrt(x);
		for(int y=fa[x];y;Wrotate(x),y=fa[x])
			if(fa[y])
				((rs(y)==x)^(rs(fa[y])==y))?Wrotate(x):Wrotate(y);
		rt[mp[zb[x]]]=x;
	}
	void Wins(pair<int,int> c,int x)
	{// 飞来 
		zb[x]=c;
		if(!mp[c])
		{
			mp[c]=++tot,rt[mp[c]]=x;
			return;
		}
		int y=rt[mp[c]];
		sq[x]=max(sq[x],maxv[y]);
		tj[x]=max(tj[x],siz[y]);
		Wmark(y,v[x],siz[y]);
		ls(x)=y,fa[ls(x)]=x;
		rt[mp[c]]=x;
		Wpushup(x);
	}
	void Wdel(int x)
	{// 飞走 处理原树 
		pair<int,int> c=zb[x];
		Wsplay(x);
		if(!ls(x))
		{
			rt[mp[c]]=rs(x),fa[rt[mp[c]]]=0;
			return;
		}
		int y=ls(x);
		while(rs(y)) y=rs(y);
		Wsplay(y);
		rs(y)=rs(x),fa[rs(y)]=y;
		Wpushup(y);
	}
	void Wpdall(int x)
	{// 下放所有标记 
		if(!x) return;
		Wpushdown(x);
		Wpdall(ls(x)),Wpdall(rs(x));
	}
	short main()
	{
		freopen("a.in","r",stdin),freopen("a.out","w",stdout);
		n=qr;
		fo(i,1,n)
		{
			siz[i]=1;maxv[i]=v[i]=qr;
			int a=qr,b=qr;
			Wins({a,b},i);
		}
		t=qr;
		while(t--)
		{
			int a=qr,b=qr,c=qr;
			Wdel(a),Wcler(a);
			Wins({b,c},a);
		}
		fo(i,1,tot) Wpdall(rt[i]);
		fo(i,1,n) printf("%lld\n",1ll*sq[i]*tj[i]);
		return Ratio;
	}
}
int main(){return Wisadel::main();}

完结撒花~

标签：bd,qr,比赛,rs,int,一小,zb,学期,ch
From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18289505

相关文章

  • 高一小学期2
    A.同类分布本来看着挺像月之迷的（其实就是一模一样），但是鉴于我自己不是非常会打月之迷（其实应该自信点的，虽然当时是贺的题解但是大体思路还是会的），而且数据范围只有\(2^{31}\)，所以就去分块打表了.赛时爆搜#include<bits/stdc++.h>usingnamespacestd;constintN=100000;//int......
  • 小学期第一周（7.1-7.7）
    7.1 周一为啥被人学校都放假了我们还有小学期【微笑]开玩笑其实我高兴得很，毕竟我是如此热爱学习今天小学期一人分了四道题我把每道题都看了看答案最后选了四道代码比较少的，这样验收的时候还简单点什么？问我为什么从网上找答案不自己写？那我也得会写才行啊，我的基础真的不敢恭......
  • 数据结构小学期第七天
    今天继续学习Springboot的项目实战今天了解了一下，如何在自己登陆后，还能让界面知道是谁在进行操作，这个功能的实现需要JWT令牌的作用我们需要先引入一个JWT依赖1<!--java-JWT坐标-->2<dependency>3<groupId>com.auth0</groupId>4<artifa......
  • 小学期第一次博客
    一、配置虚拟机环境首先，安装和配置虚拟机是整个项目的基础。选择适当的虚拟机管理软件（如VirtualBox或VMware）并安装Linux操作系统（如Ubuntu或CentOS）。配置好虚拟机后，需要确保虚拟机的网络设置为桥接模式，以便能够与外部网络通信。二、安装和配置Hadoop下载和安装Hadoop：从Hadoop的......
  • 20240706比赛总结
    题外话：IOI赛制的一大好处是可以猜解法，密码已改，不要试图jc我T1公式求值根据样例解释，显然在不进位的情况下，倒数第一位是所有位上数字的总和，倒数第二位是所有位上数字的总和减去最后一位的数字以此类推，显然前缀和，在处理一下进位即可代码：#include<cstdio>#include<string>#inc......
  • 比赛获奖的武林秘籍：03 好的创意选取-获得国奖的最必要前提
    比赛获奖的武林秘籍：03好的创意选取-获得国奖的最必要前提摘要本文主要介绍了大学生电子计算机类比赛和创新创业类比赛创意选取的重要性，并列举了好的创意选取和坏的创意选取的例子，同时说明了好的创意选取具有哪些特点，同时对常见的创意选取途径与来源进行了基本介绍。正文好的......
  • 比赛获奖的武林秘籍：03 好的创意选取-获得国奖的最必要前提
    比赛获奖的武林秘籍：03好的创意选取-获得国奖的最必要前提摘要本文主要介绍了大学生电子计算机类比赛和创新创业类比赛创意选取的重要性，并列举了好的创意选取和坏的创意选取的例子，同时说明了好的创意选取具有哪些特点，同时对常见的创意选取途径与来源进行了基本介绍。正文......
  • 数据结构小学期第六天
    今天完全实现了九宫格拼图游戏，具备一键通关功能按下W键，查看原图功能按住A键不松，移动图片按上下左右键，如果你自己想要实现这个功能，需要自己的图片，图片格式要求。每个小图片是105*105，完整图片是315*315.有人想要做一下，可以试一试。代码如下启动类1importcom.itheima.ui.GameJ......
  • 【2023-2024第二学期】助教工作学期总结——数字电路与逻辑设计助教
    一、助教工作的具体职责和任务协助教师引导大一转专业学生如何学习本门课程，收集学生问题、定期答疑、协助教师批改作业并跟踪作业完成情况，实验指导，改进课程建设。指导学生学习《数字电路与逻辑设计》。并指导学生完成《数字电路与逻辑设计实验》。二、助教工作的每周时长和具体......
  • 助教工作学期总结
    一、助教工作的具体职责和任务老师的配合：    协助老师完成作业的批改、作业的评分、登记成绩二、助教工作的每周时长和具体安排    没有固定的工作时间和具体安排，在布置的作业截至后对作业进行批改、评分；大作业答辩前安排好答辩名单，课程结课后按照老师要求完成成绩录......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99