首页 > 其他分享 >11月7日 NOIP模拟(难题math、矩阵游戏matrix、括号序列seq、道路road) - 模拟赛记录

11月7日 NOIP模拟(难题math、矩阵游戏matrix、括号序列seq、道路road) - 模拟赛记录

时间:2024-11-07 20:57:22浏览次数:4  
标签:11 lcm ch NOIP int ans include operatorname 模拟

Preface

T1 试图找规律失败,正经推反而几分钟就出来了。以后应该少想这些歪门邪道(除非实在闲的蛋疼或者没有一点头绪,且必须要打完所有能打的子任务比如暴力或特殊性质;而且必须在用常规方法思考过后,才能够用一些稍微不那么常规的方法)

至于 T2、T3、T4,因为知道 T1 浪费了太多时间,都是直接打暴力 + 特殊性质拿所有部分分,最后才来挨个挨个想正解。事实证明,这种方法十分有效,没有浪费任何时间暴力(超级模拟类型的暴力除外)和特殊性质绝对不是浪费时间)。

赛时主攻 T4 去了,但是因为 SPJ 的错漏之处(把错误的路径直接 continue 掉),导致我误解了我的代码错误位置,最后没有调出来,所以以后还得多多靠自己,好好核对草稿的结果和实际输出的结果是否一致

难题(math

设 \(c_i\) 表示 \(f(j)=i, j \le n\) 的 \(j\) 的个数,那么答案显然可以转化成 \(\sum i \times c_i\),问题在于怎么求 \(c_i\)。

容易发现 \(f(x)=y\) 当且仅当 \(1 \mid x, 2 \mid x, \cdots, y-1 \mid x\) 且 \(y \nmid x\),其中前一条条件可以转化成 \(\operatorname{lcm}(1,2,\dots,y-1) \mid x\)。

运用容斥,满足条件一的数有 \(\left\lfloor \frac{n}{\operatorname{lcm}(1,2,\dots,y-1)} \right\rfloor\) 个,而同时满足条件一和条件二的数有 \(\left\lfloor \frac{n}{\operatorname{lcm}(\operatorname{lcm}(1,2,\dots,y-1),y)} \right\rfloor = \left\lfloor \frac{n}{\operatorname{lcm}(1,2,\dots,y)} \right\rfloor\) 个,所以:

\[c_i = \left\lfloor \frac{n}{\operatorname{lcm}(1,2,\dots,y-1)} \right\rfloor - \left\lfloor \frac{n}{\operatorname{lcm}(1,2,\dots,y)} \right\rfloor \]

当 \(y=50\) 的时候,\(\operatorname{lcm}(1,2,\dots,y)\) 就远超 \(10^{16}\) 了,所以可能的最大 \(f\) 值也不会超过 \(50\)(实际上大概在 \(41\) 左右)

然后就做出来了,如果预处理一下 \(\operatorname{lcm}(1,2,\dots,i)\) 还可以加点速。

核心代码:

int T=IO::read();
g[1]=1;
for(int i=2;g[i-1]<=N;i++)
	g[i]=lcm(g[i-1],i);
while(T--)
{
	long long n=IO::read<long long>();
	long long ans=0;
	for(int i=2;g[i-1]<=n;i++)
		ans=(ans+1ll*i*(n/g[i-1]-n/g[i]))%P;
	IO::write(ans%P); putchar('\n');
}
完整代码
#include<cstdio>
using namespace std;

namespace IO{

template<typename TYPE=int>
TYPE read()
{
	TYPE x=0; bool neg=false;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') neg=true;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return neg?-x:x;
}

template<typename TYPE>
void write(TYPE x)
{
	if(!x)
	{
		putchar('0');
		return;
	}
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	static int sta[55];
	int statop=0;
	while(x)
	{
		sta[++statop]=x%10;
		x/=10;
	}
	while(statop)
		putchar('0'+sta[statop--]);
	return;
}

}

const long long N=1e16;
const int P=1e9+7;

long long gcd(long long x,long long y){return y?gcd(y,x%y):x;}
inline long long lcm(long long x,long long y){return x*y/gcd(x,y);}
long long g[1005];

int main()
{
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	
	int T=IO::read();
	g[1]=1;
	for(int i=2;g[i-1]<=N;i++)
		g[i]=lcm(g[i-1],i);
	while(T--)
	{
		long long n=IO::read<long long>();
		long long ans=0;
		for(int i=2;g[i-1]<=n;i++)
			ans=(ans+1ll*i*(n/g[i-1]-n/g[i]))%P;
		IO::write(ans%P); putchar('\n');
	}
	return 0;
}

矩阵游戏(matrix

因为每次删行的时候每一列都会收到同等的影响,所以每一列的相对大小不改变,选择优先级也不改变;删列时每行同理。

所以,删行或者删列都不影响对方的决策,删行和删列的顺序也就不重要了。那么我们就直接求出只删行 \(i\) 次的最大得分 \(fr_i\)(代码中为 Row::f[i]) 和只删列 \(i\) 次时的最优得分 \(fc_i\)(代码中为 Column::f[i]),规定先删行后删列,那么删了 \(i\) 次行时的答案就是 \(fr_i \times fc_{k-i}\),但是,因为删列时的矩形实际上已经不是完整的矩形了,而是已经有 \(i\) 行被减过了(不一定不重复),所以所删的每一列都应当已经少了 \(i \times p\),总共少了 \(i \times (k-i) \times p\),最终的答案就是 \(\max\{ fr_i \times fc{k-i} - t \times (k-i) \times p\}, 0 \le i \le k\)。

至于求只选行和直选列的具体过程,可以用优先队列维护行 / 列的总和,每次贪心地找最大总和来删,注意删完之后还要放回去。

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

namespace IO{

template<typename T=int>
T read()
{
	T x=0; bool neg=false;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') neg=true;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return neg?-x:x;
}

template<typename T>
void write(T x)
{
	if(!x)
	{
		putchar('0');
		return;
	}
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	static int sta[55];
	int statop=0;
	while(x)
	{
		sta[++statop]=x%10;
		x/=10;
	}
	while(statop)
		putchar('0'+sta[statop--]);
	return;
}

}

const int N=1005,M=1005,K=1e6+5;
int n,m,k,p;
int a[N][M];

namespace Row{

	long long f[K];
	priority_queue<long long> pq;
	void Solve()
	{
		for(int i=1;i<=n;i++)
		{
			long long sum=0;
			for(int j=1;j<=m;j++)
				sum+=a[i][j];
			pq.push(sum);
		}
		for(int i=1;i<=k;i++)
		{
			long long top=pq.top(); pq.pop();
			f[i]=f[i-1]+top; pq.push(top-1ll*m*p);
		}
		return;
	}

}

namespace Column{

	long long f[K];
	priority_queue<long long> pq;
	void Solve()
	{
		for(int i=1;i<=m;i++)
		{
			long long sum=0;
			for(int j=1;j<=n;j++)
				sum+=a[j][i];
			pq.push(sum);
		}
		for(int i=1;i<=k;i++)
		{
			long long top=pq.top(); pq.pop();
			f[i]=f[i-1]+top; pq.push(top-1ll*n*p);
		}
		return;
	}

}

void Solve()
{
	Row::Solve();
	Column::Solve();
	long long ans=-1e18; //注意初始化! 
	for(int i=0;i<=k;i++)
		ans=max(ans,Row::f[i]+Column::f[k-i]-1ll*i*(k-i)*p); //有i*(k-i)个位置要被删两次
	IO::write(ans);
	return;
}

int main()
{
	#ifndef JC_LOCAL
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	#endif
	
	n=IO::read(),m=IO::read(),k=IO::read(),p=IO::read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[i][j]=IO::read();
	Solve();
	return 0;
}

括号序列(seq

个人感觉最难的一道题,题解写的做法和代码写法好像有点问题,不过能 AC 就很奇怪,我的写法中的更新方式感觉更好理解也更符合逻辑,同样能 AC。

image

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=25,LEN=4e5+5;
int n; char str[LEN];

int sum[N],minsum[N],cnt[N][LEN];
int f[(1<<(N-5))+5],tot[(1<<(N-5))+5];
int main()
{
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",str+1);
		int len=(int)strlen(str+1);
		for(int j=1;j<=len;j++)
		{
			sum[i]+=str[j]=='(' ? 1 : -1;
			minsum[i]=min(minsum[i],sum[i]);
			if(minsum[i]>=sum[i]) cnt[i][-sum[i]]++;
		}
	}
	
	for(int i=0;i<(1<<n);i++)
		f[i]=-0x3f3f3f3f;
	f[0]=0;
	int ans=0;
	for(int z=0;z<(1<<n);z++)
	{
		for(int i=1;i<=n;i++)
			if(!((z>>(i-1))&1))
			{
				int nxt=z|(1<<(i-1));
				if(tot[z]+minsum[i]>=0)
				{
					if(f[z]+cnt[i][tot[z]]>f[nxt])
					{
						f[nxt]=f[z]+cnt[i][tot[z]];
						tot[nxt]=tot[z]+sum[i];
						ans=max(ans,f[nxt]);
					}
				}
				else ans=max(ans,f[z]+cnt[i][tot[z]]);
			}
		ans=max(ans,f[z]);
	}
	printf("%d\n",ans);
	return 0;
}

路程(road

为方便叙述,题面中的 \(n\) 在这里用 \(q\) 表示,而这里的 \(n,m\) 则分别表示点数,边数,最后一个点均指 \(114\) 号点(这仰慕前辈……)

首先看 \(q=2^k\) 的特殊性质。

首先有 \(n=k+1\) 个点,从点 \(i\) 向点 \(i+1\) 连一条边,边长为 \(2^{k-i}\),这样可以凑出 \([0,2^k-1]\) 的所有路径,最后再从 \(1\) 向末端点连接一条边长为 \(2^k\) 的边,这样就可以凑出 \([0,2^k]\) 了。

然后再考虑普适情况。

如果不连最后一条边,而是从 \(1\) 向 \(i\) 连一条长度为 \(2^k\) 的边,那么其和后面所有边组合,就可以瞬间多出 \(2^{n-i}\) 条路径,范围是 \([2^k,2^k+2^{n-i}-1]\);

再从 \(1\) 向 \(j\) 连一条长度为 \(2^k+2^{n-i}\) 的边,那么就可以多出 \(2^{n-j}\) 条路径,范围是 \([2^k+2^{n-i},2^k+2^{n-i}+2^{n-j}-1]\)。

重复上述过程,每次新连接的边权就是现在已有的最大路径长度加一,运用二进制分解可以将任意 \(q\) 转化成若干个上述形式的区间,然后像上面一样连接新边即可。

最大点数 \(\log_2 q +1\),最大边数 \(3 \log_2 q\),满足题意。

注意当 \(q=2^k-1\) 的时候可能出 BUG,可能需要特殊处理一下。

#include<cstdio>
using namespace std;

const int N=105,M=105;
int q;
struct rAllan{
	int x,y,z;
}edge[M];
int m=0;
int vertex[N];

int main()
{
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	
	scanf("%d",&q);
	int lg2=0,tq=q;
	while(tq) lg2++,tq>>=1;
	int n=lg2;
	for(int i=1;i<n;i++)
		vertex[i]=i;
	vertex[n]=114;
	for(int i=1;i<n;i++)
	{
		int x=i,y=vertex[i+1];
		int z=1<<(n-i-1);
		edge[++m]={x,y,z};
		edge[++m]={x,y,0};
	} //[0,2^lg2-1]
	
	int rest=q-((1<<(lg2-1))-1);
	int now=1<<(lg2-1);
	bool flag=false;
	for(int p=lg2;p>=0;p--)
	{
		if(rest-(1<<p)>=0)
		{
			if(n-p==1) flag=true;
			else
			{
				edge[++m]={1,vertex[n-p],now};
				rest-=(1<<p);
				now+=(1<<p);
			}
		}
	}
	if(flag) edge[++m]={1,114,q};
	
	printf("%d %d\n",n,m);
	for(int i=1;i<=m;i++)
		printf("%d %d %d\n",edge[i].x,edge[i].y,edge[i].z);
	return 0;
}

标签:11,lcm,ch,NOIP,int,ans,include,operatorname,模拟
From: https://www.cnblogs.com/jerrycyx/p/18533799

相关文章

  • 2024/11/5日工作总结
    学习JS基础知识:1.引入方式:点击查看代码<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>Title</title></head><body><!--内部脚本--><!--<script>alert(......
  • 11.7 HTML
    Html一、基本介绍1、定义:html是一种超文本标记语言,也是一种标识性语言(不是编程语言)标记:记号(绰号)超文本:就是页面内容可以包含图片、链接,音乐,视频等素材。2、为什么学习html?(1)测试页面元素,了解页面页面元素(页面是html语言编写的)(2)进行ui自动化需用到元素定位3、html有哪些特点......
  • 多校 A 层冲刺 NOIP2024 模拟赛 19
    题解还是得写,不能偷懒啊~多校A层冲刺NOIP2024模拟赛19图书管理签到题考虑最困难的部分是确定中位数,不妨钦定中位数,然后计算其贡献,然后考虑只枚举一个边界,另一个边界可以放桶里。时间复杂度\(O(n^2)\)。两棵树概率期望考虑拆贡献,有等式\[连通块个数=点数-边数\]证明考虑......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛19
    RankbydCSP之后就没场切过题......
  • 2024年11月随便做做
    十月太摆了没有随便做做环节。测试题目选集20241106-D.盼君勿忘题解等会写qwq。Miscellaneous[AGC022D]Shopping神秘题目,比较酷。首先发现对于\(t_i\ge2L\)的\(t_i\)可以直接将\(t_i\lfloor\frac{t_i}{2L}\rfloor\)加入答案并将\(t_i\)对\(2L\)取模。然后只......
  • 11.7日
    创建一个新的DynamicWebProject打开Eclipse。选择File->New->DynamicWebProject。在弹出的对话框中,输入项目名称,例如MyWebApp。确保Targetruntime设置为ApacheTomcatv9.0(或其他你安装的Tomcat版本)。如果没有配置,点击NewRuntime按钮进行配置。点击Finish......
  • LeetCode 1137[第N个泰波那契数]
    题目链接LeetCode1137[第N个泰波那契数]详情实例实例1实例2提示题解思路一[递归]当n为0,1,2时,直接返回对应的值当n大于2时,开始用f(n+3)=f(n)+f(n+1)+f(n+2)来递归求值代码一[此代码在力扣会超出时间限制]classSolution{public:inttrib......
  • 11.7
    通过PreparedStatement实现对数据库的插入和查询操作。importjava.sql.Connection;importjava.sql.DriverManager;importjava.sql.PreparedStatement;importjava.sql.ResultSet;publicclassPreparedStatementExample{publicstaticvoidmain(String[]args){Strin......
  • 2024年11月7号总结
    今天在课余又学了javaWeb的一些内容,把MySQL重新下好了DQL聚合函数聚合函数:将一列数据作为一个整体,进行纵向计算count 统计数量max/min 最值sum 求和avg 平均数selectcount(id)fromstu;括号内的列名不能为空,有空的项不算数count取值:或者主键selectmax(math)fromstu;......
  • 洛谷 P2113 看球泡妹子(DP)
    传送门https://www.luogu.com.cn/problem/P2113解题思路可以设  表示前  场比赛看了  场,小红的满足度为  的最大精彩度。然后可以枚举前面的一个比赛 ,可以得到转移方程:但是,我们发现数组空间有一点小大,可以优化一下。发现每一次转移都是 ,于是可以滚动数组优化空......