首页 > 其他分享 >NOIP 2021 游记

NOIP 2021 游记

时间：2022-10-30 11:55:46浏览次数：78  
标签：templateinl const NOIP int void 2021 游记 rep define

Day 0

对着大纲找了点很板子的题做，主要找的dcc和scc缩点、树形DP和DP优化、KMP之类的。睡前祈祷不要失眠，结果在即将睡着后外面传来钢琴声，直接失眠........emmmmmmm。

Day 1

精神不是很好，早饭感觉吃得有点油，一直到考时候十几分钟都有呕吐感，考前还拉了肚子。状态肯定没有CSP时好，但硬着头皮直接冲进考场。

那道题目，第一眼感觉题目名字比较正常，但看到T4的chess的时候下意识想到了 奆佬PG 昨天押的博弈论，有点害怕，就快速看了一下题目。看完题目我就大概知道我今年NOIP的结果了.......今年T1、T4题目较长，但都很好理解，T1看到 \(x\leq 10^7\) 就知道感觉可以类似线筛直接预处理答案，想了十几秒发现线筛不现实，但感觉合法的数不多，拿埃筛稍微剪剪枝或许能卡过，然后就看T2。T2不长，但我还是理解了一会儿题目意思，感觉到是一个DP，但并没有很好的思路，主要是那个二进制下 \(1\) 的个数不超过 \(K\) 带来了进位等一系列难处理的问题，于是觉得今年要稳就必须把T2想出来。T3的意思很简单，但完全没有思路，但爆搜应该很好写。T4太长了，各种走法，于是我决定先回去把T1写了。

大概犹豫了一会儿有没有更优的做法，没想到就直接把代码冲上去。中途因为 \(10^7\) 只枚举了六个数位等低级错误耽搁了一小会儿时间，\(9:00\) 过完所有样例。

然后想T2,。不夸张的说，想T2的时间是整场考试最痛苦的时间，不仅有难处理的各种问题，还有见到数据范围就知道是自己很不熟练的多维DP。硬着头皮去设计一个DP状态，但还是处理不了进位，以及一些组合的问题，想了一会儿，忘了时间，就又去想了会儿T3。

手玩那个操作的时候，发现对相邻两个数操作之后，得到的数有点规律，但没太看得出来（考完了才知道是交换差分数组），又推了一下方差的公式，以为有用，结果啥用都没有，浪费时间.......

有点慌了，只写了 \(100pts\) ，加上没打的T2的暴力 \(50pts\) 和T3的暴力 \(10pts\) （一开始以为只有 \(10pts\) ） ，还没

上 \(200pts\) 。于是决定看一下 T4 看暴力分有多少。发现题目意思不是很复杂，每种道路可以分开算，暴力就直接模拟即可，有 \(32pts\) ，就决定拿了就跑路。中途又调试了一会儿，复杂度写假了一个小地方，花了一个小时才稳过暴力的样例。

打完T2T3的暴力后，剩下的一段时间就一直在想T2了，各种DP的方法都尝试过，等绕不卡那几个圈子，唯一一次感觉是对的算法我又认为复杂度会多一点，而且很难写，就放弃了。之后又尝试了另一种思路，写上去感觉很有道理，但还是算漏了一些组合情况，而这时，我已经能确定这场NOIP的结果了。于是我开始边检查代码，边思考如何面对考场外面的世界.......苛责是绝不会少的，至少对于某来说。同学和老师会来问我考得怎么样，我该如何回答。一堆whk蜂拥而至，而oi自然是要停一会儿了。

当保持安静的几个大字出现在所有人的屏幕上时，一切都结束了，一切又都开始了。

出门，先看到PG，看脸知道也考得不好，下楼统计了一下，PG、green_orange、ycz都做出来了（但洛谷测了后ycz挂了），T4PG想出了平衡树启发式合并的做法，但没打出来，暴力也没调出来。感觉高二学长要集体退役了，而我们也还只剩最后一次机会了。

下午在洛谷上测了一下，T4暴力挂了 \(8pts\) ，清空把时间复杂度清假了，但貌似不是很重要了，这个分数段1=应该是稳的，省队就做梦吧。

心情不太好，游记都是第二天才写的，中间还有很多细节懒得回忆，大概记录一下，准备回去补whk了。

附录

期望得分：

\[100pts+50pts+20pts+24pts=194pts \]

考场代码：
T1:

#include<bits/stdc++.h>
#define inl inline 
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
#define pii pair<int,int>
#define vi vector<int>
#define mp make_pair
#define fi first
#define se second
#define eb emplace_back
using namespace std;

template<typename T>inl void exg(T &x,T &y){ x^=y^=x^=y; }
template<typename T>inl void chkmn(T &x,const T &y){ (x>y) && (x=y); }
template<typename T>inl void chkmx(T &x,const T &y){ (x<y) && (x=y); }

const int maxn=1e7+10,N=1e7;
int T,x;
int nxt[maxn];
bool ban[maxn];

int main(){
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
	scanf("%d",&T);
	rep(a,0,9) rep(b,0,9) rep(c,0,9) rep(d,0,9) rep(e,0,9) rep(f,0,9) rep(g,0,9)
	    if(!((a ^ 7) && (b ^ 7) && (c ^ 7) && (d ^ 7) && (e ^ 7) && (f ^ 7) && (g ^ 7))){
	    	const int x=a*1000000+b*100000+c*10000+d*1000+e*100+f*10+g;
	    	if(!ban[x] && x) rep(i,1,N/x) ban[x*i]=1;
		}
	per(i,N+5,1) if(!ban[i]) nxt[i-1]=i;
	per(i,N+5,1) if(!nxt[i]) nxt[i]=nxt[i+1];
	while(T--){
		scanf("%d",&x);
		if(ban[x]) puts("-1");
		else printf("%d\n",nxt[x]);
	}
	return 0;
}

T2:

#include<bits/stdc++.h>
#define inl inline 
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define repp(i,x,y,d) for(int i=(x);i<=(y);i+=(d))
#define per(i,x,y) for(int i=(x);i>=(y);--i)
#define pii pair<int,int>
#define vi vector<int>
#define mp make_pair
#define fi first
#define se second
#define eb emplace_back
using namespace std;
typedef long long LL;

template<typename T>inl void exg(T &x,T &y){ x^=y^=x^=y; }
template<typename T>inl void chkmn(T &x,const T &y){ (x>y) && (x=y); }
template<typename T>inl void chkmx(T &x,const T &y){ (x<y) && (x=y); }

const int MOD=998244353;

inl int inc(int a,int b){ return (a+b>=MOD) ? a+b-MOD : a+b; }
inl int mul(int a,int b){ return 1LL*a*b%MOD; }
inl void Inc(int &a,int b){ ((a+=b)>=MOD) && (a-=MOD); }
inl void Mul(int &a,int b){ a=1LL*a*b%MOD; }
inl void Sqr(int &a){ a=1LL*a*a%MOD; }
int KSM(int a,int x=MOD-2){
	int res=1;
	while(x){
		if(x & 1) Mul(res,a);
		Sqr(a),x>>=1;
	}return res;
}

const int maxn=110;
int n,m,k;
int v[maxn];

namespace case_1{
	int f[32][1<<17];
	void Work(){
		f[0][0]=1;
		rep(i,0,n-1) rep(j,0,(1<<17)-1) if(f[i][j]) rep(l,0,m){
			const int x=j+(1<<l);
			Inc(f[i+1][x],mul(f[i][j],v[l]));
		}int ans=0;
		rep(i,0,(1<<17)-1) if(__builtin_popcount(i)<=k) Inc(ans,f[n][i]);
		printf("%d\n",ans);
	}
}
//namespace case_2{
//	int g[maxn][35],f[maxn][35][35],fac[35],fiv[35];
//	inl int Binom(int x,int y){ return mul(fac[x],mul(fiv[y],fiv[x-y])); }
//	void Work(){
//		fac[0]=1;
//		rep(i,1,n) fac[i]=mul(fac[i-1],i);
//		fiv[n]=KSM(fac[n]);
//		per(i,n-1,0) fiv[i]=mul(fiv[i+1],i+1);
//		
//		rep(i,0,m+5){
//			g[i][1]=v[i];
//			rep(j,2,n) rep(l,0,i) if(j>=(1<<(i-l))) Inc(g[i][j],mul(g[l][j-(1<<(i-l))],Binom(i,l))); 
//			
////			Inc(g[i][j],mul(g[i-1][k],g[i-1][j-k]));
//		}
//		
////		rep(i,0,m+5){
////			rep(j,1,n) printf("%d ",g[i][j]);
////			puts("");
////		}
//		
//		f[0][1][1]=v[0],f[0][0][0]=1;
//		rep(i,1,m+5) rep(j,0,n) rep(l,0,k){
//			f[i][j][l]=f[i-1][j][l];
//			rep(x,1,j) Inc(f[i][j][l],mul(f[i-1][j-x][l-1],g[i][x])); 
////			printf("%d %d %d %d\n",i,j,l,f[i][j][l]);
//		}int ans=0;
//		rep(i,1,k) Inc(ans,f[m+5][n][i]);
//		printf("%d\n",ans);
//	}
//}

int main(){
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	rep(i,0,m) scanf("%d",&v[i]);
	case_1::Work();
	return 0;
}

T3:

#include<bits/stdc++.h>
#define inl inline 
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
#define pii pair<int,int>
#define vi vector<int>
#define mp make_pair
#define fi first
#define se second
#define eb emplace_back
using namespace std;
typedef long long LL;

template<typename T>inl void exg(T &x,T &y){ x^=y^=x^=y; }
template<typename T>inl void chkmn(T &x,const T &y){ (x>y) && (x=y); }
template<typename T>inl void chkmx(T &x,const T &y){ (x<y) && (x=y); }

const int maxn=1e4+5;
int n;
LL ans=1e18;
vi a;
set<LL>st;

LL Trans(vi x){
	LL ans=0;
	rep(i,0,n-1) ans=ans*40+x[i];
	return ans;
}
void DFS(const vi &a){
	LL tmp1=0,tmp2=0;
	rep(i,0,n-1) tmp1+=a[i]*a[i],tmp2+=a[i];
	chkmn(ans,n*tmp1-tmp2*tmp2);
	rep(i,1,n-2){
		vi b=a;
		b[i]=b[i+1]+b[i-1]-b[i];
		const LL y=Trans(b);
		if(!st.count(y)) st.insert(y),DFS(b);
	}
}

int main(){
	freopen("variance.in","r",stdin);
	freopen("variance.out","w",stdout);
	scanf("%d",&n);
	a.resize(n);
	rep(i,0,n-1) scanf("%d",&a[i]);
	st.insert(Trans(a));
	DFS(a);
	printf("%lld\n",ans);
	return 0;
}

T4:

#include<bits/stdc++.h>
#define inl inline 
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mp make_pair
#define fi first
#define se second
#define eb emplace_back
using namespace std;

template<typename T>inl void exg(T &x,T &y){ x^=y^=x^=y; }
template<typename T>inl void chkmn(T &x,const T &y){ (x>y) && (x=y); }
template<typename T>inl void chkmx(T &x,const T &y){ (x<y) && (x=y); }

const int maxn=2e5+5;
int _T,n,m,q;
vii c[maxn];
vector<bool> b1[maxn],b2[maxn],b3[maxn],vis[maxn];
string S[maxn],T[maxn];
pii _q[maxn<<4];

int main(){
	freopen("chess.in","r",stdin);
	freopen("chess.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>_T;
	while(_T--){
		cin>>n>>m>>q;
		rep(i,1,n){
			cin>>S[i],c[i].resize(m+1),b1[i].resize(m+1),b2[i].resize(m+1),b3[i].resize(m+1),vis[i].resize(m+1);
			rep(j,1,m) c[i][j]=mp(0,0);
		}rep(i,1,n-1) cin>>T[i];
		int col,lv,x,y;
		while(q--){
			cin>>col>>lv>>x>>y;
			if((x ^ 1) && T[x-1][y-1]=='1'){ if(!c[x-1][y].se || ((c[x-1][y].fi ^ col) && c[x-1][y].se<=lv)) b1[x-1][y]=1; }
			if((x ^ n) && T[x][y-1]=='1'){ if(!c[x+1][y].se || ((c[x+1][y].fi ^ col) && c[x+1][y].se<=lv)) b1[x+1][y]=1; }
			if((y ^ 1) && S[x][y-2]=='1'){ if(!c[x][y-1].se || ((c[x][y-1].fi ^ col) && c[x][y-1].se<=lv)) b1[x][y-1]=1; }
			if((y ^ m) && S[x][y-1]=='1'){ if(!c[x][y+1].se || ((c[x][y+1].fi ^ col) && c[x][y+1].se<=lv)) b1[x][y+1]=1; }
			int xx=x,yy=y;
			while(xx ^ 1){
				if(T[xx-1][yy-1]=='2'){
					--xx;
					if(c[xx][yy].se){
						if((c[xx][yy].fi ^ col) && c[xx][yy].se<=lv) b2[xx][yy]=1;
						break;
					}b2[xx][yy]=1;
				}else break;
			}xx=x,yy=y;
			while(xx ^ n){
				if(T[xx][yy-1]=='2'){
					++xx;
					if(c[xx][yy].se){
						if((c[xx][yy].fi ^ col) && c[xx][yy].se<=lv) b2[xx][yy]=1;
						break;
					}b2[xx][yy]=1;
				}else break;
			}xx=x,yy=y;
			while(yy ^ 1){
				if(S[xx][yy-2]=='2'){
					--yy;
					if(c[xx][yy].se){
						if((c[xx][yy].fi ^ col) && c[xx][yy].se<=lv) b2[xx][yy]=1;
						break;
					}b2[xx][yy]=1;
				}else break;
			}xx=x,yy=y;
			while(yy ^ m){
				if(S[xx][yy-1]=='2'){
					++yy;
					if(c[xx][yy].se){
						if((c[xx][yy].fi ^ col) && c[xx][yy].se<=lv) b2[xx][yy]=1;
						break;
					}b2[xx][yy]=1;
				}else break;
			}int head=1,tail=1;
			_q[tail++]=mp(x,y);
			while(head<tail){
				pii p=_q[head++];
				if(c[p.fi][p.se].se){
					if((c[p.fi][p.se].fi ^ col) && c[p.fi][p.se].se<=lv) b3[p.fi][p.se]=1;
					continue;
				}else b3[p.fi][p.se]=1;
				if(p.fi ^ 1){ if(T[p.fi-1][p.se-1]=='3' && !vis[p.fi-1][p.se]) _q[tail++]=mp(p.fi-1,p.se),vis[p.fi-1][p.se]=1; }
				if(p.fi ^ n){ if(T[p.fi][p.se-1]=='3' && !vis[p.fi+1][p.se]) _q[tail++]=mp(p.fi+1,p.se),vis[p.fi+1][p.se]=1; }
				if(p.se ^ 1){ if(S[p.fi][p.se-2]=='3' && !vis[p.fi][p.se-1]) _q[tail++]=mp(p.fi,p.se-1),vis[p.fi][p.se-1]=1; }
				if(p.se ^ m){ if(S[p.fi][p.se-1]=='3' && !vis[p.fi][p.se+1]) _q[tail++]=mp(p.fi,p.se+1),vis[p.fi][p.se+1]=1; }
			}int ans=0;
			rep(i,1,n) rep(j,1,m){
				if(b1[i][j] || b2[i][j] || b3[i][j]){
					b1[i][j]=b2[i][j]=b3[i][j]=0;
					if((i ^ x) || (j ^ y)) ++ans;
				}vis[i][j]=0;
			}cout<<ans<<endl;
			c[x][y]=mp(col,lv);
		}
	}
	return 0;
}

Update 12.4

emmmmmmmmmmmmmmm，有被卷到，荣登榜首，超第二二十多分，CQ真强！

1=没了，下一年的压力更大了。

whk补得差不多了，卷！

标签：templateinl,const,NOIP,int,void,2021,游记,rep,define
From： https://www.cnblogs.com/Sword-K/p/16840878.html

相关文章

  • CSP-S 2021 游记
    Day0下午试机，打了一下板子，发现编译都过不了人都傻了，结果是32位机。于是就以为整个机房都是32位机，考试的时候发现自己的机子是64位的，运气真好。试了一下对拍器，看来库里的......
  • CSP 2022 游记
    上午先去打了一场J组，一是为下午的S组练练手感，二是想要弥补一下自己J组还没AK过的遗憾吧J组题目不难,T1,T2都是签到题，加上文件操作大概15min左右写完吧。T3看了一眼发现......
  • CSP-S 2022游记
    本蒟蒻第一次考\(CSP\)，有点紧张QAQ其实好像没啥必须写的，但为了做个纪念就把这天的活动记一下吧。今年好多地方都寄了（该死的疫情），\(SC\)万幸没有取消，恰好我们团队的同学......
  • 【游记】重生之 CSP 2022 卷土重来
    CSP2022游记\(\text{Day}1\)前面到底是\(\text{Day}0\)还是\(\text{Day}-1\)？？\(\text{Day}-2\)打了场模拟赛，感觉状态不错。总和之前的模拟赛经验，发现只要不被......
  • CSP-S 2022 游记
    坐标ZJ，每部分游记都会在后面标注时间。CSP-S1游记（writtenon2022/9/18）：Day-inf~Day0：9.11时做了套初赛模拟还行，后面自己又做了一份也不错就直接没管。Day1：今......
  • CSP-S2022 游记
    上午到学校休息了一会，没有干什么活，为下午考试留足精力。在学校附近吃过午饭就去华山饭店了。大概十二点五十到考场，发现没有座位，全是上午J组同学的吃着午饭继续考S。所......
  • CSP - S 2022 游记
    零虽然同样参加了CSP-S2021和CSP-J2020，但是实在是打的太烂了，感觉是没有写游记的脸面。这次的分数就比较正常。这是最后一次了，感觉如果不留下写什么的话，以后就会......
  • CSP-S 2022 游记
    考前准备本来这次考前准备做的挺差的，然后想着反正是寄了，那考多少其实也无所谓，考前也没有太紧张，心态还算好开考前14:20带了几块巧克力进去，结果开考前由于太无聊几乎全吃......
  • CSP2022 游记。
    作为第一次以高中生身份参加csp，虽然有了一定的经验，但还是有点小慌。14:20基本进完场了，考场内回忆了一下tarjan，然后眯眼休息。14:27开考，解压。T1一道图论题，找几个最......
  • [游记]CSP-S第二场
    现役划水？不知道为什么半夜会醒，但既然醒了，就把它写完吧。如果这是NOIP的话，如果NOIP真的没了的话，大概我真的要AFO了。我真的有好好考啊，4个小时没有喝一口水，没有任何走思，没......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99