CSP-S 2020 游记 - 洛谷保存站

## Day -1

待更

## Day 0

待更

## Day 1

待更

### T1

这个题是一个我相对擅长的模拟题，可能是大家做思维题做多了，这种非常考察细节的题目似乎发挥都不太好

我把时间轴分为了三个部分：  
公元前 | 公元 1.1.1 到 公元 1582.10.4 | 公元 1582.10.15 之后

简单做了数学题之后，把时间轴分割为三个部分，中间还是算错了一次  
查了十多分钟吧

个人感觉难度还算友好，不知道为什么这么多人喷 T1

代码进行了一些类工程化的修改，可读性提升了

```
#include<bits/stdc++.h>
#define int long long 
#define reg register
#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);
using namespace std;
int read(){
	int x=0,f=0;
	char ch=0;
	while(!isdigit(ch))f|=(ch=='-'),ch=getchar();
	while(isdigit(ch))(x*=10)+=(ch^48),ch=getchar();
	return f?-x:x;
}
int Day;
const int 
	_DaysForMonth[]={-1,31,-1,31,30,31,30,31,31,30,31,30,31},
	_DaysEveryFourYear=1461,
	_FirstYearBCE=4713,
	_FirstYearCE=1,
	_FirstYearGregorian=1582,
	_FirstMonth=1,
	_FirstDay=1,
	_DaysLeapYear=366,
	_DaysCommonYear=365,
	_MonthsEveryYear=12,
	_DaysBeforeCE=1721423,
	_DaysBeforeGregorian=2299160,
	_DaysForFebInLeapYear=29,
	_DaysForFebInCommonYear=28,
	_DaysEveryFourHundredsYear=146097;
	
namespace BCE{
	bool isLeapYear(const int _Year){
		return (_Year-1)%4==0;
	}
	void Main(const int _Day){
		
		int Days_Untreated=_Day;
		int Year_Now=_FirstYearBCE,Month_Now=_FirstMonth,Day_Now=_FirstDay;
	
		Year_Now-=Days_Untreated/_DaysEveryFourYear*4;
		Days_Untreated%=_DaysEveryFourYear;
		
		int Days_To_Year=_DaysLeapYear;
		
		while(Days_Untreated>Days_To_Year){
			
			Days_Untreated-=Days_To_Year;
			Year_Now--;
			
			if(isLeapYear(Year_Now)){
				Days_To_Year=_DaysLeapYear;
			}
			else{
				Days_To_Year=_DaysCommonYear;
			}
				
		}
		
		int Days_To_Month=_DaysForMonth[Month_Now];
		
		while(Days_Untreated>=Days_To_Month){
			
			Days_Untreated-=Days_To_Month;
			Month_Now++;
			
			if(Month_Now>_MonthsEveryYear){
			
				Month_Now=_FirstDay;
				Year_Now--;
				
				if(isLeapYear(Year_Now)){
					Days_To_Year=_DaysLeapYear;
				}
				else{
					Days_To_Year=_DaysCommonYear;
				}
				
			}
			
			if(Month_Now==2){
				if(isLeapYear(Year_Now)){
					Days_To_Month=_DaysForFebInLeapYear;
				}
				else {
					Days_To_Month=_DaysForFebInCommonYear;
				}
			}
			else{
				Days_To_Month=_DaysForMonth[Month_Now];
			}
			
		}
		
		Day_Now+=Days_Untreated;
		
		printf("%lld %lld %lld BC\n",Day_Now,Month_Now,Year_Now);
	}
}
namespace CEBeforeGregorian{
	bool isLeapYear(const int _Year){
		return _Year%4==0;
	}
	void Main(const int _Day){
		
		int Days_Untreated=_Day-_DaysBeforeCE-1;
		int Year_Now=_FirstYearCE,Month_Now=_FirstMonth,Day_Now=_FirstDay;
		
		Year_Now+=Days_Untreated/_DaysEveryFourYear*4;
		Days_Untreated%=_DaysEveryFourYear;
		
		int Days_To_Year=_DaysCommonYear;
		
		while(Days_Untreated>Days_To_Year){
			
			Days_Untreated-=Days_To_Year;
			Year_Now++;
			
			if(isLeapYear(Year_Now)){
				Days_To_Year=_DaysLeapYear;
			}
			else{
				Days_To_Year=_DaysCommonYear;
			}
			
		}
		
		int Days_To_Month=_DaysForMonth[1];
		
		while(Days_Untreated>=Days_To_Month){
			
			Days_Untreated-=Days_To_Month;
			Month_Now++;
			
			if(Month_Now>_MonthsEveryYear){
				
				Month_Now=_FirstMonth;
				Year_Now++;
				
				if(isLeapYear(Year_Now)){
					Days_To_Year=_DaysLeapYear;
				}
				else{
					Days_To_Year=_DaysCommonYear;
				}
				
			}
			
			if(Month_Now==2){
				if(isLeapYear(Year_Now)){
					Days_To_Month=_DaysForFebInLeapYear;
				}
				else {
					Days_To_Month=_DaysForFebInCommonYear;
				}
			}
			else{
				Days_To_Month=_DaysForMonth[Month_Now];
			}
			
		}
		
		Day_Now=Day_Now+Days_Untreated;
		
		printf("%lld %lld %lld\n",Day_Now,Month_Now,Year_Now);
	}
}
namespace CEAfterGregorian{
	bool isLeapYear(const int _Year){
		return (_Year%4==0&&_Year%100!=0)||(_Year%400==0);
	}
	void Main(const int _Day){
		
		const int _DaysCompensated=287;
		int Days_Untreated=_Day-_DaysBeforeGregorian-1+_DaysCompensated;
		//Return 287 days so we can solve the problem in 1582.1.1
		//Because we know the date must be later than 1582.10.15
		//Although the 1582.10.5-1582.10.14 is nonexistent
		//But we can compensate the date 287 days to make our problem easier
		
		int Year_Now=_FirstYearGregorian,Month_Now=_FirstMonth,Day_Now=_FirstDay;
		
		Year_Now+=Days_Untreated/_DaysEveryFourHundredsYear*400;
		Days_Untreated=Days_Untreated%_DaysEveryFourHundredsYear;
				
		int Days_To_Year=_DaysCommonYear;
		
		while(Days_Untreated>Days_To_Year){
			
			Days_Untreated-=Days_To_Year;
			Year_Now++;
			
			if(isLeapYear(Year_Now)){
					Days_To_Year=_DaysLeapYear;
			}
			else{
				Days_To_Year=_DaysCommonYear;
			}
			
		}
		
		int Days_To_Month=_DaysForMonth[Month_Now];
		
		while(Days_Untreated>=Days_To_Month){
			
			Days_Untreated-=Days_To_Month;
			Month_Now++;
			
			if(Month_Now>_MonthsEveryYear){
				
				Month_Now=_FirstMonth;
				Year_Now++;
				
				if(isLeapYear(Year_Now)){
					Days_To_Year=_DaysLeapYear;
				}
				else{
					Days_To_Year=_DaysCommonYear;
				}
				
			}
			
			if(Month_Now==2){
				if(isLeapYear(Year_Now)){
					Days_To_Month=_DaysForFebInLeapYear;
				}
				else {
					Days_To_Month=_DaysForFebInCommonYear;
				}
			}
			else{
				Days_To_Month=_DaysForMonth[Month_Now];
			}
			
		}
		
		Day_Now=Day_Now+Days_Untreated;
		
		printf("%lld %lld %lld\n",Day_Now,Month_Now,Year_Now);
	}
}
signed main(){
	for(reg int T=read();T;T--){
		Day=read();
		if(Day<=_DaysBeforeCE) {
			BCE::Main(Day);
		}
		else{
			if(Day<=_DaysBeforeGregorian) {
				CEBeforeGregorian::Main(Day);
			}
			else {
				CEAfterGregorian::Main(Day);
			}
		}
	}
	return 0;
}
```

### T2

个人感觉这次比赛做的最可惜的一道题目，输入格式中有一行

> 数据保证所有 ai 互不相同，所有的 qi 互不相同。

赛时根本完全没有看到这句话，自己YY了 $q_i$ 相同时的情况，荣获TLE

这道题目放到提高似乎显得过于简单，唯一恶心人的估计就是传统艺能卡 ull 了，可是看边上的人得分也不是很理想=-=

有部分人歪打正着没看到这句话也没考虑 $q_i$ 相同时的情况

具体一点的解法的话，直接考虑二进制下每一位是否有约束，如果有约束是否已经被原来就有的数满足了

一位上如果没有约束或者约束已经被满足则总动物数可以 $\times 2$

最终答案就是 总动物数 - 现有动物数

```
#include<bits/stdc++.h>
#define int unsigned long long 
#define reg register
#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);
using namespace std;
int read(){
	int x=0,f=0;
	char ch=0;
	while(!isdigit(ch))f|=(ch=='-'),ch=getchar();
	while(isdigit(ch))(x*=10)+=(ch^48),ch=getchar();
	return f?-x:x;
}
const int MAXN=1020200;
bool lim[MAXN];
int a[MAXN];
int n,m,c,k;
int p[MAXN],q[MAXN];
signed main(){
	Open("zoo");
	n=read(),m=read(),c=read(),k=read();
	for(reg int i=1;i<=n;i++)
		a[i]=read();
	for(reg int i=1;i<=m;i++){
		p[i]=read(),q[i]=read();
		lim[p[i]]=1;
	}
	int allb=0;
	for(reg int i=1;i<=n;i++)
		allb|=a[i];
	int et=1;
	for(reg int i=0;i<k;i++)
		if(allb&(1ull<<i))
			lim[i]=0;
	for(reg int i=0;i<k;i++)
		if(lim[i])continue;
		else et=et*2;
	if(et==0){
		if(n==0)printf("18446744073709551616");
		else {
			et=18446744073709551615;
			n--;
			printf("%llu\n",et-n);
		}
	}
	else printf("%llu\n",et-n);
	return 0;
}
```

### T3

待更

### T4

待更

正在渲染内容...