首页 > 其他分享 >多校A层冲刺NOIP2024模拟赛03

多校A层冲刺NOIP2024模拟赛03

时间:2024-10-07 21:23:09浏览次数:7  
标签:03 const int 多校 ++ maxn freopen NOIP2024 501

A. 五彩斑斓

没办法,不会统计四个点相同的,赛时没想到,写了一个神秘算法骗了80

考虑倒着计算,总子矩阵有 \(\frac{n(n+1)*m(m+1)}{4}\) 个,减去四个角相同的矩阵数量就是答案,枚举矩阵的上下边界两条线

再枚举每一列,会有两个交点,统计每种颜色的上下交点颜色一样的个数,就可以计算了

点击查看代码
#include<bits/stdc++.h>
const int maxn=410;
using namespace std;
int n,m,c[maxn][maxn],cnt[1000001];
long long ans; 

int main()
{
	freopen("colorful.in","r",stdin);
	freopen("colorful.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m; 
	for(register int i=1;i<=n;i++)
	{
		for(register int j=1;j<=m;j++)
		{
			cin>>c[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			for(int k=1;k<=m;k++)
			{
				if(c[i][k]==c[j][k])
				{
					cnt[c[i][k]]++;
					ans+=cnt[c[i][k]];
				}
			}
			for(int k=1;k<=m;k++) cnt[c[i][k]]=0; 
		}
	} 
	cout<<1ll*(n+1)*n/2*m*(m+1)/2-ans;

	return 0;
}
/*
3 4
1 2 3 1
1 3 1 2
1 2 1 1
 
*/

B. 错峰旅行

确实没想到怎么维护,直接找的每一天有多少城市可走,正解实际上就是再简化一下,因为区间很少,所以有很多天他们

的城市拥堵情况是一样的,这样就可以直接合并,这样就去除了很多重复的情况,因为不拥堵时城市数是 \(n\) ,所以直接

对每一个限制的 \(l,r\) 记一个在 \(l\) 处 -1,在 \(r+1\) 处 +1,把每一个有限制的时间点记录下来,按时间先后跑一边就行

点击查看代码
#include<bits/stdc++.h>
#define int long long 
const int mod=1e9+7;
const int maxn=2e6+10;
using namespace std;
int n,m,s,t,p[maxn],ans,cnt;
struct lsx
{
	int id,x,k;
	bool operator < (const lsx &a) const
	{
		return x==a.x?k<a.k:x<a.x; 
	}
}a[maxn<<1];

int qpow(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1) ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}

signed main()
{
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>s>>t;
	p[++p[0]]=s,p[++p[0]]=t+1;
	for(int i=1;i<=m;i++)
	{
		int x,l,r;
		cin>>x>>l>>r;
		p[++p[0]]=l,p[++p[0]]=r+1;
		a[++cnt]={x,l,-1};
		a[++cnt]={x,r+1,1};
	}
	sort(a+1,a+1+cnt);
	sort(p+1,p+1+p[0]);
	p[0]=unique(p+1,p+p[0]+1)-p-1;
	int num=n;
	ans=1; 
	for(int i=1,j=0;i<p[0];i++)
	{
		while(j<cnt&&a[j+1].x<=p[i])
		{
//			cout<<a[j].x<<" "<<a[j].k<<endl; 
			j++;
			int x=a[j].k;
			num+=x;	
		}
//		cout<<i<<" "<<p[0]<<endl; 
//		cout<<p[i]<<" "<<ans<<" "<<num<<endl; 
		ans=ans*qpow(num,p[i+1]-p[i])%mod;
	}
	cout<<ans;

	return 0;
}
/*

*/

C. 线段树

没想到是 \(dp\) 啊,由于一个区间至少需要一次,所以答案的下届是 \(q\) ,我们考虑对一个区间 \(l-r\) 查询次数增加需要达到

的条件,即为你划分出来的区间 \(x-y\) 满足与 \(l-r\) 有交集,但是不包含,这样当划分完之后,\(l-r\) 有一部分在区间外

一部分在区间内,它就需要进入子树内从而至少多花费1的代价

区间 \(dp\) ,设 \(f_{l,r}\) 表示将 \(l-r\) 划分区间对询问造成的最小代价,\(f_{l,r}=\min_{k=l}^{r-1}\limits(f_{l,k}+f_{k+1,r}+cost(l,r,k))\)

\(cost(l,r,k)\) 表示有多少询问区间与 \(l-r\) 有交且包含 \(k+0.5\)

点击查看代码
#include<bits/stdc++.h>
const int maxn=1e5+10;
using namespace std;
int n,q,x[maxn],y[maxn],w[501],a[501][501],ans,k,f[501][501],sum[501][501]; 

int main()
{
	freopen("segment.in","r",stdin);
	freopen("segment.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>x[i]>>y[i];
		a[x[i]][y[i]]++;
		for(int j=x[i];j<y[i];j++) w[j]++;
	}
	for(int l=1;l<=n;l++)
		for(int r=n;r>=l;r--) 
			sum[l][r]+=sum[l-1][r]+sum[l][r+1]-sum[l-1][r+1]+a[l][r];
	for(int len=2;len<=n;len++)
	{
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			f[i][j]=0x7f7f7f;
			for(int k=i;k<j;k++)
			{
				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+w[k]-sum[i][j]);
//				cout<<w[k]-sum[i][j]<<endl; 
			}
//			cout<<i<<" "<<j<<" "<<f[i][j]<<endl; 
		}
	}
	cout<<f[1][n]+q;
	
	return 0;
}
/*

*/

你们怎么都往博客塞点私货啊。。。

我们终会在星辰里相遇

image

标签:03,const,int,多校,++,maxn,freopen,NOIP2024,501
From: https://www.cnblogs.com/oceansofstars/p/18450659

相关文章

  • [42] (多校联训) A层冲刺NOIP2024模拟赛03
    今天的乐子今天的乐子2昨天晚上做梦梦见自己被关进戒网瘾学校里面的老师全和疯子一样然后我和这帮疯子老师比疯疯子老师发现他们没我疯所以就把我放了今天的乐子3lhx罗曼蒂克的辟谷A.五彩斑斓赛时的想法\(n^4\)的做法,设\(f_{i,j,k,l}\)表示以\((i,j)......
  • P8531 [Ynoi2003] 戌亥彗星
    特殊性质实际上就是保证了所有环外点度数都\(\le2\),这样就只需要考虑前两个条件。注意到对于一个\(i\),假设\(i\)为区间左端点,那么所有满足条件\(2\)的右端点构成一个区间,记为\(l_i,r_i\),且满足\(l_i\lel_{i+1},r_i\ler_{i+1}\)。而且这些区间有更强的性质:如果\(l_i<l_......
  • 多校A层冲刺NOIP2024模拟赛03 -- T4 量子隧穿问题
    多校A层冲刺NOIP2024模拟赛03--T4量子隧穿问题$$HZOI$$感觉是这两天最有意义的题吧。\(n\)句话题意我是巴甫洛夫的狗,我又重生了,重生在薛定谔的家里。薛定谔是抖S,于是给我铃声。我开始狂跑不止。为什么没流口水没删除我给定\(n\)个点,对于\(i\)存在一条外向连的单向......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛03
    Rank炸了,触底反弹A.五彩斑斓(colorful)签,又没签上。考虑如何一步步优化暴力。最暴力的思想\(\mathcal{O(n^4)}\)枚举每个矩形,判断四个顶点颜色。稍微优化些,两次\(\mathcal{O(n^2)}\)跑出对于行/列每个点下一个与之颜色相同的坐标,利用容斥全部减去不合法的方案数,然后再枚......
  • CSP2024 前集训:多校A层冲刺NOIP2024模拟赛03
    前言T1没想到正难则反,脑瘫了没敢用bitset(复杂度擦边但卡常能过),T2空间开大了挂了\(100pts\),\(T3\)是原。T1五彩斑斓部分分\(20pts\):\(O(n^4)\)暴力。部分分\(20+?pts\):进行一些优化,极限数据下仍是\(O(n^4)\)。部分分\(60\sim100pts\):bitset优化一下,\(O(\f......
  • 多校A层冲刺NOIP2024模拟赛03
    多校A层冲刺NOIP2024模拟赛03还有一个半小时结束才来,题基本没打,全口胡。T1五彩斑斓(colorful)直接统计答案难做,考虑统计四个顶点都一样的。知道\(n\)行\(m\)列的矩阵有\(\frac{n\times(n+1)\timesm\times(m+1)}{4}\)个子矩阵,这个想成选择矩阵的边界就可以证明。如何统计四......
  • 多校 A 层冲刺 NOIP2024 模拟赛 03
    多校A层冲刺NOIP2024模拟赛03T1五彩斑斓(colorful)签到题直接暴力枚举是\(O(n^4)\),考虑使用\(bitset\)优化,对每个点开个\(bitset\),预处理它所在一行它及它之前相同颜色的位置,这样就只用枚举另一个点所在列,时间复杂度为\(O(n^3+\frac{n^4}{w})\)。T2错峰旅行(travel)......
  • 网站403forbidden怎么解决
    遇到“403Forbidden”错误通常表示服务器拒绝了请求访问某个资源。解决这个问题可以从以下几个方面入手:1.检查权限设置服务器文件权限:确认服务器上的文件和目录权限是否正确。通常文件权限应为 644,目录权限应为 755。使用命令 chmod 和 chown 调整权限:sudochm......
  • 信息学奥赛复赛复习14-CSP-J2021-03网络连接-字符串处理、数据类型溢出、数据结构Map
    PDF文档公众号回复关键字:202410071P7911[CSP-J2021]网络连接[题目描述]TCP/IP协议是网络通信领域的一项重要协议。今天你的任务,就是尝试利用这个协议,还原一个简化后的网络连接场景。在本问题中,计算机分为两大类:服务机(Server)和客户机(Client)。服务机负责建立连接,客户机......
  • 多校A层冲刺NOIP2024模拟赛02 & csp-s模拟9
    多校A层冲刺NOIP2024模拟赛02四道题因为暑假被拉去当模拟赛暑假集训CSP提高模拟22了,遂直接把赛后代码交了上去,然后就被通知换题了。原\(100+100+100+20\)被在accodersNOI上被卡成了\(100+100+90+10\),更改longlong和int后达到了\(100+100+100+30\)。\(T1\)P318......