首页 > 其他分享 >2024.7.20

2024.7.20

时间:2024-07-21 18:08:50浏览次数:14  
标签:20 2024.7 int res LL long ++ mod

模拟赛

昨天的题解还在咕。。。今天的又来了。。。

T1 Simple Math 2

签到题,推一推式子就好了。

\[\lfloor {\frac{a^b}{c}} \rfloor\mod c= x \]

\[\lfloor {\frac{a^b}{c}} \rfloor = k \times c + x \]

\[\frac{a^b-(a^b \mod c)}{c} = k \times c + x \]

\[a^b-(a^b \mod c)= k \times c^2 + x \times c \]

\[(a^b-(a^b \mod c)) \mod c^2=x \times c \]

\[\frac{(a^b-(a^b \mod c)) \mod c^2}{c}=x \]

\(c\) \(1e4\) 直接搞。

code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL b,c,C;

LL qpow(LL x,LL y)
{
	LL res=1;
	while(y)
	{
		if(y&1) res=(res*x)%C;
		x=(x*x)%C; y>>=1;
	}
	return res;
}

int main()
{
	scanf("%lld%lld",&b,&c);
	C=c*c;
	LL d=qpow(10,b),e=d%c;
	printf("%lld\n",(d-e)/c);
	return 0;
}

T2 Mister B and PR Shifts

线性做法。我们考虑每一位数的贡献,然后大力分讨。

  • 如果一开始 \(a[i] \le i\),那么随着这个数向右移,贡献越来越大。

  • 如果一开始 \(a[i] \gt i\),贡献会先变小再变大,会有一个转折点。
    我们可以开一个桶记录到转折点距离为 \(d\) 的数的个数为 \(cnt[d]\)。
    当我们移动 \(d\)时,就会有 \(cnt[d]\) 个数变为第一种。

  • 最后一个数会变成第一个,特判一下。

代码不太好打,这次呵题解对压行有了更深理解,最近好多题都是直接考虑每个数的贡献。

code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+6;
#define LL long long
int n,a[N],cnt[N<<1],cnt1,cnt2,k;
LL ans,s1,s2;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]>i?(s1+=a[i]-i,cnt[a[i]-i]++,cnt1++):(s2+=i-a[i],cnt2++);
	ans=s1+s2;
	for(int i=1;i<=n;i++) s1-=cnt1,s2+=cnt2,cnt1-=cnt[i],cnt2+=cnt[i],cnt2--,s2-=((n+1)-a[n-i+1]),
	a[n-i+1]>1?++cnt[a[n-i+1]-1+i],s1+=a[n-i+1]-1,cnt1++:++cnt2,s1+s2<ans&&(ans=s1+s2,k=i);
	printf("%lld %d\n",ans,k);
	return 0;
}

T3 Yazid 的新生舞会

咕咕咕。。。

T4 上帝造题的七分钟 2 / 花神游历各国

有一个很显然的性质,\(a=10^11\) 进行开方操作最多 \(6\) 次就会变成 \(1\)。

最多修改操作只有 \(6n\) 次,可以考虑爆修。

于是爆修线段树:

code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1e5+5;
int n,q;
LL a[N];
struct T
{
	int l,r;
	LL sum;
} tr[N<<2];
inline void pushup(int k)
{
	tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
}
inline void bui(int k,int l,int r)
{
	tr[k].l=l; tr[k].r=r;
	if(l==r) return tr[k].sum=a[l],void(0);
	int mid=l+r>>1;
	bui(k<<1,l,mid); bui(k<<1|1,mid+1,r);
	pushup(k);
}
inline void mdf(int k,int l,int r)
{
	if(tr[k].sum==tr[k].r-tr[k].l+1) return;//注意剪枝 
	if(tr[k].l==tr[k].r) return tr[k].sum=sqrt(tr[k].sum),void(0);
	int mid=tr[k].l+tr[k].r>>1;
	if(l<=mid) mdf(k<<1,l,r);
	if(r>mid) mdf(k<<1|1,l,r);
	pushup(k);
}
inline LL que(int k,int l,int r)
{
	if(l<=tr[k].l&&r>=tr[k].r)
		return tr[k].sum;
	int mid=tr[k].l+tr[k].r>>1; LL res=0;
	if(l<=mid) res+=que(k<<1,l,r);
	if(r>mid) res+=que(k<<1|1,l,r);
	return res;
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);//卡常 
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	bui(1,1,n);
	cin>>q;
	while(q--)
	{
		int x,y,z; cin>>x>>y>>z;
		if(y>z) swap(y,z);
		if(x==0) mdf(1,y,z);
		else cout<<que(1,y,z)<<'\n';
	}
	return 0;
}

优点是不用动脑子(如果想不到就没脑子了),缺点是大力卡常。

正解其实就是用树状数组维护,减小常数,至于已经变成 \(1\) 的数可以用并查集维护。

并查集的 trick?

码量友好:

code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
#define LL long long
int n,q,fa[N]; LL a[N],c[N];
int find(int x)
{
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
void add(int x,LL v)
{
	for(;x<=n;x+=(x&-x)) c[x]+=v;
}
LL que(int x)
{
	LL res=0;
	for(;x;x-=(x&-x)) res+=c[x];
	return res;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),add(i,a[i]),fa[i]=i; fa[n+1]=n+1;
	scanf("%d",&q);
	while(q--)
	{
		int c,l,r; scanf("%d%d%d",&c,&l,&r); 
		if(l>r) swap(l,r);
		if(c==1) printf("%lld\n",que(r)-que(l-1));
		else
		{
			for(int i=l;i<=r;)
			{
				int fi=find(i);
				if(fi!=i) i=fi;
				else
				{
					LL t=sqrt(a[i]);
					add(i,t-a[i]); a[i]=t;
					if(a[i]==1) fa[i]=i+1,i=find(i);
					else i++;
				}
			}
		}
	}
	return 0;
}

标签:20,2024.7,int,res,LL,long,++,mod
From: https://www.cnblogs.com/ppllxx-9G/p/18313852

相关文章

  • Python turtle 无图 20行代码写乌龟快跑
    上期在一小时内被我用流量券顶到了20后面就没啥亮点了 _____________________________________________________________________________老规矩先放代码(20行代码以下代码段为准):importturtle,random;turtle.tracer(0);bg2=turtle.Screen();bg=turtle.Turtle();dg=tur......
  • 【题解】P4648 [IOI2007] pairs 动物对数
    Problem给定模板\(B(1\leB\le3)\),代表\(B\)维空间。其中有\(n\)个点,给出坐标与坐标上限\(M\),求\(n\)个点中曼哈顿距离\(\leD\)的对数。Solve\(B=1\)考虑将问题化简成:求\(\sum\limits_{i=1}^n\sum\limits_{j=1}^{i-1}[dis(i,j)\leqD]\)。其中\(dis(i,j)\)......
  • 免费【2024】springboot宝鸡文理学院学生成绩动态追踪系统
     博主介绍:✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围:SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大......
  • 免费【2024】springboot宝鸡文理学院学生成绩动态追踪系统
     博主介绍:✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围:SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大......
  • 免费【2024】springboot宝鸡文理学院学生成绩动态追踪系统
     博主介绍:✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围:SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大......
  • 在实际应用中,systemverilog相比vefilog2000有哪些重大的提升
    SystemVerilog相较于Verilog-2000有多项重大提升,这些提升使得SystemVerilog成为更强大的硬件描述和验证语言。以下是一些关键的改进:数据类型扩展:SystemVerilog引入了 logic 数据类型,可以替代Verilog-2000中的 wire 和 reg 类型,提供更灵活的使用方式。支持更广......
  • P3522 [POI2011] TEM-Temperature
    原题链接题解尽量直观地理解单调队列的作用首先,对于合法的一段,有如下性质A满足:当前的最高温度大于等于前面的最大的最低温度该性质对于段内每一个数都满足,所以对于第\(i\)天,我们可以找其前面的第一天\(j\)的最低温度大于\(i\)的最高温度,同时还要满足\((j,i]\)内......
  • P3197 [HNOI2008] 越狱
    原题链接题解正难则反不可能发生越狱的清空:从左到右,第一个人有m种选择,第二个人为了和前面一个人不一样,有m-1种选择。。。code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constllmod=100003;llqpow(lla,lln){llres=1;while(n......
  • [NOIP2005 普及组] 采药
    题目描述辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值......
  • 2024夏令营提高1模考0721模拟赛(提高1)补题报告
    2024夏令营提高1模考0721模拟赛(提高1)补题报告\[07121模拟赛(提高1)\\\补题报告\\\\2024年7月21日\\\by\\\唐一潇\]一、做题情况第一题比赛\(100/100\),赛后通过第二题比赛\(0/100\),赛后通过第三题比赛\(0/100\),赛后通过第四题比赛\(0/100\)......