首页 > 其他分享 >CSP-S 2022 - 模拟赛记录

CSP-S 2022 - 模拟赛记录

时间:2024-10-31 19:46:59浏览次数:1  
标签:int 31 30 mid 2022 year CSP 模拟 lld

Preface

T1 调的太久了,应当先打够部分分就切题的,全分思维难度不高,代码难度超高。

可能是出题人知道把最简单题放 T2 有点过于恶心,所以后两道题的部分分都很好打,给的分也很多,一共 \(55\) 分可以轻松到手。

就是第二题卡了一个 unsigned long long,有点莫名其妙,而且 T1 放模拟也是头一次见。

儒略日(Julian

恶心透顶,大部分时间都在调这个,各种分类讨论神奇处理,做紫题都没这么恶心。还好最后对了。

这是我最初过掉的代码,因为过于恶臭就折叠了,想赤石的可以打开看一下,不想的就算了

点击赤石·大石
#include<cstdio>
#define int long long
using namespace std;

const int Julian=-4712; //儒略日起点为-4712年1月1日 
const int Zero=1721426; //公元元年1月1日(-0.1.1)的儒略日 
const int Gregorian=2299160; //公元1582.10.4的儒略日 
const int common_Month[20]={0,31,28,31,30,31,30,31,31,30,31,30,31};
const int leap_Month[20]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int Q,n;

signed main()
{
//	freopen("julian.in","r",stdin);
//	freopen("julian.out","w",stdout);
	 
	scanf("%lld",&Q);
	while(Q--)
	{
		scanf("%lld",&n);
		if(n<=Gregorian) //使用儒略历 
		{
			n++; //将儒略日起点转化为-4713年12月31日,次年1月1日为第一天 
			//先计算经过了多少年 
			int l=-1,r=6296;
			while(l+1<r) //二分经过的年份 
			{
				int mid=l+r>>1;
//				printf("year %lld: %lld\n",mid,365*mid+((mid-1)>>2)+1);
				if(n>365*mid+((mid-1)>>2)+1) l=mid; //这里必须是大于,而不能包括等于! 
				else r=mid;
			}
			int year=l;
//			printf("year %lld\n",year);
			n-=(365*year+((year-1)>>2)+1); //注意负数时右移和除法行为不同 
//			printf("%lld days left\n",n);
//			n-=(365*year+(year>>2)+1); //当年剩下的天数
			int month=0;
			if(year%4==0) //当年是闰年
			{
				for(month=1;month<=12;month++)
				{
					if(n<=leap_Month[month]) break;
					else n-=leap_Month[month];
				}
			}
			else
			{
				for(month=1;month<=12;month++)
				{
					if(n<=common_Month[month]) break;
					else n-=common_Month[month];
				}
			}
			int day=n;
			year+=Julian;
			if(year>0) printf("%lld %lld %lld\n",day,month,year);
			else printf("%lld %lld %lld BC\n",day,month,-year+1);
		}
		else //使用格里高利历 
		{
			n-=(Zero-1); //转化为公元元年后的天数,1月1日为第1天 
//			printf("%lld days left\n",n);
			int l=-1,r=1e9+1;
			while(l+1<r) //二分:公元纪年下年份与公元元年1月1日相差年数 
			{
				int mid=l+r>>1; //经过mid年 
				//公元元年1月1日与公元(mid+1)年1月1日相差天数(经过了mid年) 
				if(mid*365+(mid/4-mid/100+mid/400)<n) l=mid;
				else r=mid;
			}
//			printf("%lld leap years\n",(l/4-l/100+l/400));
			n-=(l*365+(l/4-l/100+l/400)); //当年剩下的天数
			int year=l+1; //当前实际年份
//			printf("year %lld\n",year);
//			printf("%lld days left\n",n);
			int month=0;
//			n+=2;
			if(year%400==0 || (year%4==0&&year%100!=0)) //闰年 
			{
				for(month=1;month<=12;month++)
				{
					if(n<=leap_Month[month]) break;
					else n-=leap_Month[month];
				}
			}
			else
			{
				for(month=1;month<=12;month++)
				{
					if(n<=common_Month[month]) break;
					else n-=common_Month[month];
				}
			}
			int day=n;
			printf("%lld %lld %lld\n",day,month,year);
		}
	}
	return 0;
}

//2h45min

/*
将公元前i年设成公元前(i-1)年,儒略日起点为4712年(闰年,所以这里可以看为0) 
这样公元前与公元后年份连续,且可以通过%4来简单判断闰年 
*/

/*
所谓儒略日,其定义为从公元前 4713 年 1 月 1 日正午 12 点到此后某一时刻间所经过的天数

公元 1582 年 10 月 15 日(含)以后:
适用格里高利历,每年一月 31 天、二月 28 天或 29 天、三月 31 天、
四月 30 天、五月 31 天、六月 30 天、七月 31 天、八月 31 天、
九月 30 天、十月 31 天、十一月 30 天、十二月 31 天。
其中,闰年的二月为 29 天,平年为 28 天。当年份是 400 的倍数,
或日期年份是 4 的倍数但不是 100 的倍数时,该年为闰年。

公元 1582 年 10 月 5 日(含)至 10 月 14 日(含):
不存在,这些日期被删除,该年 10 月 4 日之后为 10 月 15 日。

公元 1582 年 10 月 4 日(含)以前:
适用儒略历,每月天数与格里高利历相同,但只要年份是 4 的倍数就是闰年。
尽管儒略历于公元前 45 年才开始实行,且初期经过若干次调整,
但今天人类习惯于按照儒略历最终的规则反推一切 1582 年 10 月 4 日之前的时间。
注意,公元零年并不存在,即公元前 1 年的下一年是公元 1 年。
因此公元前 1 年、前 5 年、前 9 年、前 13 年……以此类推的年份应视为闰年。
*/ 

洛谷上的题解应当有很多写的比我简洁清晰明了得多的,所以我这里只简述一下我的恶臭做法

首先通过打表之类稀奇古怪的做法求出儒略日下公元元年、\(1582\) 年 \(10\) 月 \(4\) 日的儒略日,然后根据这个来判断 \(n\) 是在儒略历还是在格里高利历。

接着二分得到所经过的年份(最恶心的一步),算出这一年还剩下多少天。

最后按照月份挨个挨个减找到对应的月份,剩下的就是天数。

稍稍修改了一下,但是依然恶臭:

点击赤石·小石
/*
将公元前i年设成公元前(i-1)年,儒略日起点为4712年(闰年,所以这里可以看为0) 
这样公元前与公元后年份连续,且可以通过%4来简单判断闰年 
*/
#include<cstdio>
using namespace std;

const int Julian=-4712; //儒略日起点为-4712年1月1日 
const int Zero=1721426; //公元元年1月1日(-0.1.1)的儒略日 
const int Gregorian=2299160; //公元1582.10.4的儒略日 
const int common_Month[20]={0,31,28,31,30,31,30,31,31,30,31,30,31};
const int leap_Month[20]={0,31,29,31,30,31,30,31,31,30,31,30,31};

int Q;
long long n;

int main()
{
//	freopen("julian.in","r",stdin);
//	freopen("julian.out","w",stdout);
	 
	scanf("%d",&Q);
	while(Q--)
	{
		scanf("%lld",&n);
		if(n<=Gregorian) //使用儒略历 
		{
			n++; //将儒略日起点转化为-4713年12月31日,次年1月1日为第一天 
			//先计算经过了多少年 
			int l=-1,r=6296;
			while(l+1<r) //二分经过的年份 
			{
				int mid=l+r>>1;
				if(n>365ll*mid+((mid-1)>>2)+1) l=mid; //这里必须是大于,而不能包括等于! 
				else r=mid;
			}
			int year=l;
			n-=(365ll*year+((year-1)>>2)+1); //当年剩下的天数
			//注意负数时右移和除法行为不同 
			int month=0;
			if(year%4==0) //当年是闰年
			{
				for(month=1;month<=12;month++)
				{
					if(n<=leap_Month[month]) break;
					else n-=leap_Month[month];
				}
			}
			else //当年是平年 
			{
				for(month=1;month<=12;month++)
				{
					if(n<=common_Month[month]) break;
					else n-=common_Month[month];
				}
			}
			int day=n;
			year+=Julian;
			if(year>0) printf("%d %d %d\n",day,month,year);
			else printf("%d %d %d BC\n",day,month,-year+1);
		}
		else //使用格里高利历 
		{
			n-=(Zero-1); //转化为公元元年后的天数,1月1日为第1天 
			int l=-1,r=1e9+1;
			while(l+1<r) //二分:公元纪年下年份与公元元年1月1日相差年数 
			{
				int mid=l+r>>1; //经过mid年 
				//公元元年1月1日与公元(mid+1)年1月1日相差天数(经过了mid年) 
				if(365ll*mid+(mid/4-mid/100+mid/400)<n) l=mid;
				else r=mid;
			}
			n-=(365ll*l+(l/4-l/100+l/400)); //当年剩下的天数
			int year=l+1; //当前实际年份
			int month=0;
			if(year%400==0 || (year%4==0&&year%100!=0)) //当年是闰年 
			{
				for(month=1;month<=12;month++)
				{
					if(n<=leap_Month[month]) break;
					else n-=leap_Month[month];
				}
			}
			else //当年是平年 
			{
				for(month=1;month<=12;month++)
				{
					if(n<=common_Month[month]) break;
					else n-=common_Month[month];
				}
			}
			int day=n;
			printf("%d %d %d\n",day,month,year);
		}
	}
	return 0;
}

//2h45min

/*
以下内容摘自题面: 
 
所谓儒略日,其定义为从公元前 4713 年 1 月 1 日正午 12 点到此后某一时刻间所经过的天数

公元 1582 年 10 月 15 日(含)以后:
适用格里高利历,每年一月 31 天、二月 28 天或 29 天、三月 31 天、
四月 30 天、五月 31 天、六月 30 天、七月 31 天、八月 31 天、
九月 30 天、十月 31 天、十一月 30 天、十二月 31 天。
其中,闰年的二月为 29 天,平年为 28 天。当年份是 400 的倍数,
或日期年份是 4 的倍数但不是 100 的倍数时,该年为闰年。

公元 1582 年 10 月 5 日(含)至 10 月 14 日(含):
不存在,这些日期被删除,该年 10 月 4 日之后为 10 月 15 日。

公元 1582 年 10 月 4 日(含)以前:
适用儒略历,每月天数与格里高利历相同,但只要年份是 4 的倍数就是闰年。
尽管儒略历于公元前 45 年才开始实行,且初期经过若干次调整,
但今天人类习惯于按照儒略历最终的规则反推一切 1582 年 10 月 4 日之前的时间。
注意,公元零年并不存在,即公元前 1 年的下一年是公元 1 年。
因此公元前 1 年、前 5 年、前 9 年、前 13 年……以此类推的年份应视为闰年。
*/

动物园(zoo

这道题其实我做它的时候还算挺顺的,就是最后狠狠恶心了我一把。

首先,某些位是必须要买饲料的,无论买了多少饲料,总之买了必买的饲料后,这些位一定会被全覆盖,怎么选都不多买饲料;

其次,剩下的位无需买饲料,但这里又分两种:

  • 这一位有没有 \(1\) 没影响,因为没有饲料对这个位置做要求;

  • 这里一旦有 \(1\) 就要多买饲料,这时这里不能选。

问题就转化成了:有些位置可以随意选,而有些不能选。

那么这就简单了,设有 \(t\) 位可以任取 \(1\) 或 \(0\),那么一共就可以选 \(2^t\) 种动物,其中已经有 \(n\) 种在园子里了,还可以选的就有 \(2^t-n\) 种。

求 \(t\) 直接用状态压缩标记哪一位被动物占领了,以及哪一位不能选即可。

unsigned long long 也真的是服了。

#include<cstdio>
#define ULL unsigned long long
using namespace std;

const int N=1e6+5;
int n,m,c,k;
ULL a[N];
int p[N],q[N];
ULL anim,unable;

void print_int128(__int128 x)
{
	if(x>=10) print_int128(x/10);
	putchar('0'+x%10);
	return;
}
int main()
{
//	freopen("zoo.in","r",stdin);
//	freopen("zoo.out","w",stdout);
	
	scanf("%d%d%d%d",&n,&m,&c,&k);
	int tot=k;
	for(int i=1;i<=n;i++)
	{
		scanf("%llu",&a[i]);
		anim|=a[i];
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&p[i],&q[i]);
		if(!((anim>>p[i])&1) && !((unable>>p[i])&1))
		{ //这一位没有动物,且还没有被标记 
			tot--;
			unable|=(1ull<<p[i]); //标记这一位不能选 
			//左移要开ull!
		}
	}
	__int128 ans=((__int128)1<<tot)-n;
	print_int128(ans);
	return 0;
}

//1h20min

函数调用(call

直接打暴力,递归调用函数,洛谷上可以卡到 \(45\) 分,为什么在某些地方就只有 \(35\) 分?

#include<cstdio>
#include<vector>
using namespace std;

const int N=1e5+5,M=1e5+5;
const int P=998244353;
int n;
long long a[N];
int m,op[M];
vector<long long> c[M];
int q;

void Execute(int id)
{
	if(op[id]==1)
	{
		a[c[id][0]]=(a[c[id][0]]+c[id][1])%P;
	}
	if(op[id]==2)
	{
		for(int i=1;i<=n;i++)
			a[i]=a[i]*c[id][0]%P;
	}
	if(op[id]==3)
	{
		for(int i=0;i<(int)c[id].size();i++)
			Execute(c[id][i]);
	}
	return;
}

int main()
{
	freopen("call.in","r",stdin);
	freopen("call.out","w",stdout);
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&op[i]);
		if(op[i]==1)
		{
			long long x,y; scanf("%lld%lld",&x,&y);
			c[i].push_back(x),c[i].push_back(y);
		}
		if(op[i]==2)
		{
			long long x; scanf("%lld",&x);
			c[i].push_back(x);
		}
		if(op[i]==3)
		{
			long long t; scanf("%lld",&t);
			for(int j=1;j<=t;j++)
			{
				long long x; scanf("%lld",&x);
				c[i].push_back(x);
			}
		}
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		int x; scanf("%d",&x);
		Execute(x);
	}
	for(int i=1;i<=n;i++)
		printf("%lld ",a[i]);
	return 0;
}

//45min

贪吃蛇(snakes

这次连暴力都打不来了。

分析样例可知,当 \(n=3\) 时,只有两种情况:要么最大的那条蛇吃了最小蛇后还有余力吃中间蛇,那就全吃,只剩 \(1\) 条蛇;要么它吃了最小蛇后要被中间蛇偷家,那它就摆烂不吃,剩 \(3\) 条蛇。

这样居然有 \(20\) 分,有点爽,可惜随机数没骗到分

#include<cstdio>
#include<ctime>
#include<random>
#include<algorithm>
using namespace std;

const int N=1e6+5;
int n,a[N];

mt19937 engine;
void Solve()
{
	if(n==3)
	{
		if(a[3]-a[1]>=a[2]) printf("1\n");
		else printf("3\n");
	}
	else printf("%d\n",engine()%n+1);
	return;
}

int main()
{
	freopen("snakes.in","r",stdin);
	freopen("snakes.out","w",stdout);
	
	engine.seed((unsigned)time(nullptr));
	int T; scanf("%d",&T);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	Solve();
	for(int I=2;I<=T;I++)
	{
		int k; scanf("%d",&k);
		for(int i=1;i<=k;i++)
		{
			int x,y; scanf("%d%d",&x,&y);
			a[x]=y;
		}
		Solve();
	}
	return 0;
}

//30min

标签:int,31,30,mid,2022,year,CSP,模拟,lld
From: https://www.cnblogs.com/jerrycyx/p/18518658

相关文章

  • 「模拟赛」多校 A 层联训 15
    比赛链接A.追逐游戏(chase)没啥意义的水题,但赛时没调出来。分讨,LCA设\(S\)和\(T\)的LCA为\(lca\)\(S'\)为\(lca\)的祖先节点的时候,\(S'\)到达\(s->T\)这条链上的第一个点\(x\)一定是\(lca\)否则,用LCA求出来\(S'\)到\(s->T\)这条链上的第一个点......
  • 多校 A 层冲刺 NOIP2024 模拟赛 16
    多校A层冲刺NOIP2024模拟赛16T1四舍五入签到题注意到一个数是否会入上去只和其剩余系有关,即满足\(i\modj<\frac{1}{2}j\),会入上去,考虑枚举j的倍数,其贡献就成了一个区间,差分即可。时间复杂度是调和级数的,为\(O(n\lnn)\)。T2填算符贪心,特殊性质显然将所有\(\&\)放......
  • # 20222316 2024-2025-1 《网络与系统攻防技术》实验三实验报告
    一、实验内容1.学习总结1)免杀基本概念英文为Anti-AntiVirus(简写VirusAV),逐字翻译为“反-反病毒”,翻译为“反杀毒技术”。一般是对恶意软件做处理,让它不被杀毒软件所检测。也是渗透测试中需要使用到的技术。2)免杀技术修改特征码修改校验和花指令免杀花指令其实......
  • DVD管理系统 (连接数据库--项目模拟)
    本章主要是增加和查看功能,其他的删除和修改(借出/归还)只是写了工具类和接口DVD类属性----必须与数据库里面,我们所调用的表一一对应!!!!packagedvd.entry;/***实体类---一对一参照表*表名=类名(首字母大写)*字段名===属性名*字段类型==属性类型*/publicclas......
  • NOIP 模拟赛:2024-10-30
    T1:一场比赛一共有\(n\)位选手和\(m\)道题目,其中你是第\(1\)位选手。你现在知道了每位选手通过了哪些题目。你可以调整题目的顺序,然后给题目赋予一个分值,使得第\(i\)道题目的分值是\(2^i\)。你想知道能否通过调整题目的顺序,使得你的成绩恰好是第二高的。保证不存在两个选手的通......
  • NOIP 模拟赛 Day 1
    赛时很神秘,自己设定开始时间。开T1,发现了一些性质,但是对着题面盯了1h什么思路也没有。开T2,博弈论,打了个SG函数的表,发现是SG函数是\(a_i\bmod(j+1)\)这样子的,这样就有了\(O(n^2)\),拿到了\(30\)pts。此时2h。开T3,会了暴力枚举全排列,这个复杂度是\(O(n!)\)的,有......
  • 2024.10.31模拟赛
    一定要好好睡觉啊,不然打模拟赛的时候会困死的!!!非常非常困的7:50时就开始打模拟赛,还是打了四个小时。打了T1、T2的正解,T3的5分特殊样例、T3的10分特殊样例,预计总215分。然后经过漫长的三个小时的等待,出现了T1100分,T265分,T360分,T410分、总分235分的神奇成绩。虽然结果比预......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛16
    Rank依托,给我烂完了(A.四舍五入唐题,赛时被硬控3h。发现枚举\(i\)是一个很没前途的选择,分成三段后仍然需要\(\mathcal{O(n)}\)去跑\(\left[1,\lfloor{\frac{i}{2}}\rfloor\right]\)这一段,复杂度仍是\(\mathcal{O(n^2)}\)的,只有30pts。正难则反,我们换个角度考虑枚......
  • 20241031模拟赛题解
    T1题目描述给定一个圆形蛋糕,被\(n\)条切割线分成\(n\)个扇形蛋糕块,按照顺时针编号,第\(i\)块上有\(a_i\)个草莓,第\(i\)条切割线到第\(i+1\)条切割线之间的部分是第\(i\)块蛋糕。Alice和Bob流选择切割线,假设Alice选择了第\(i\)条切割线,Bob选择了第\(j\)条......
  • 模拟用户登录网站
    模拟用户登录网站requests模块Requests继承了urllib2的所有特性。Requests支持HTTP连接保持和连接池,支持使用cookie保持会话,支持文件上传,支持自动确定响应内容的编码,支持国际化的URL和POST数据自动编码。requests的底层实现其实就是urllib3Requests的文档非常完备,中文......