首页 > 其他分享 >CSP-S 2023 题解

CSP-S 2023 题解

时间：2023-10-24 16:15:54浏览次数：34  
标签：nxt ch int 题解 ll 2023 fsy CSP nw

CSP-S 2023 题解

游记

打得非常烂。。。也是一个经验的总结吧：

image

T1.密码锁(lock)

似乎也没什么好讲的，直接模拟枚举每一种情况即可。

放上我的考场代码。

#include <bits/stdc++.h>
using namespace std;

int n,a[10][8],b[2][90][8],ans=0,len,l;

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

int build(int *p,int op){
  int cnt=0;
  for(int i=1;i<=5;i++){
  	for(int j=1;j<=5;j++){
  	  if(i==j) continue;
  	  for(int k=1;k<=9;k++) b[op][cnt+k][j]=p[j];
	} 
	for(int k=0;k<=9;k++){
	  if(p[i]==k) continue;
	  b[op][++cnt][i]=k;
	}
  }
  for(int i=1;i<=4;i++){
  	for(int j=1;j<=5;j++){
  	  if(i==j||j==i+1) continue;
  	  for(int k=1;k<=9;k++) b[op][cnt+k][j]=p[j];
	} 
	for(int k=0;k<=9;k++){
	  if(p[i]==k) continue;
	  b[op][++cnt][i]=k;b[op][cnt][i+1]=(k+(p[i+1]-p[i])+10)%10;
	}
  }
  return cnt;
} 

bool cmp(int *a,int *p){
  for(int i=1;i<=5;i++)
    if(a[i]!=p[i]) return false;
  return true;
}

bool chk(){
  for(int i=1;i<=n;i++){
    bool flag=false;
  	for(int j=1;j<=l;j++){
  	  if(cmp(a[i],b[1][j])){flag=true;break;}	
	}
	if(!flag) return false;
  }
  return true;
}

int main(){
  freopen("lock.in","r",stdin);
  freopen("lock.out","w",stdout);
  n=read();
  for(int i=1;i<=n;i++){
  	for(int j=1;j<=5;j++)
  	  a[i][j]=read();
  }
  len=build(a[1],0);
//  for(int i=1;i<=len;i++,cout<<'\n')
//    for(int j=1;j<=5;j++) cout<<b[0][i][j]<<' ';
  for(int i=1;i<=len;i++){
  	l=build(b[0][i],1);
  	if(chk()) ans++;
  } 
  printf("%d\n",ans);
  return 0;
}

最后没时间把 T1 放到 NOI Linux 下面去测了，还好它没挂。。。

T2.消消乐

一眼看很想之前的一道联考题：20230718-T4，基本上本质相同，于是不少同学按照之前的思路往矩阵上面想了。

也不是不行，但是我用的另一种方法（矩阵直接维护前缀积即可）。

很明显可以用字符串哈希做，但我用的 dp，时间复杂度 \(O(26n)\)

思路也非常简单。

我们希望找到从每个点开始的下一个匹配的位置，

很容易发现这个位置唯一，求出来之后我们就可以知道单个的回文串的数量。

而多个回文串拼起来也是可以的，

所以最后从后往前扫一遍枚举当前这个回文串作为结尾的方案数即可。

所以现在的问题就是在于怎么找到以 \(i\) 开头的回文串结尾？

不妨记为 \(nxt[i]\)。

首先我们可以想到单调栈，

用单调栈从 \(1\) 开始做一遍就可以得到 \(\gt \frac{n}{2}\) 的点的匹配位置，

而那些剩下的就是和别人匹配的那些位置，怎么求呢？

我们考虑从后往前枚举，

发现当枚举到位置 \(i\) 时，有解当且仅当 \(i+1\) 是有解的。

也就是说在 \(i+1 \sim nxt[i+1]\) 中间一定是不会出现 \(nxt[i]\) 的，

这个应该很好想到。

所以下一个可能成为 \(nxt[i]\) 的点一定是 \(i+1,nxt[i+1]+1,nxt[nxt[i+1]+1]+1,\dots\)

只有这样才能保证中间的都可以消完。

于是我们就可以对于每一个位置，

去维护每一个字母在它后面的下一个出现的位置即可。

于是可以用 \(O(26n)\) 的时间算出所有答案。

这道题就做完了——放上考场代码：

/*f[i]表示以i开头往后面的区间得到的方案数，
ans=\sum f[i]，首先需要维护从i出发第一次栈中清空的位置，
第一次从1遍历可以得到 n/2 个元素的 nxt[i] ， 
*/ 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=2e6+3;
int n,st[N],tp=0;
ll ans=0,cnt=0,f[N],nxt[N];
vector<pair<int,int> > dp[N];
bool vis[N];
char s[N];

int read(){
  int x=0,F=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') F=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*F;
}

void print(ll x){
  int p[25],tmp=0;
  if(x==0) putchar('0');
  if(x<0) putchar('-'),x=-x;
  while(x){
  	p[++tmp]=x%10;
  	x/=10;
  }
  for(int i=tmp;i>=1;i--) putchar(p[i]+'0');
  putchar('\n');
}

int main(){
  freopen("game.in","r",stdin);
  freopen("game.out","w",stdout);
  n=read();tp=cnt=ans=0;
  for(int i=1;i<=n;i++){
  	s[i]=getchar();
  	while(!(s[i]>='a'&&s[i]<='z')) s[i]=getchar();
	if(tp){
  	  if(s[i]==s[st[tp]]) vis[st[tp]]=true,nxt[st[tp]]=i,tp--;
  	  else st[++tp]=i;
	}
	else st[++tp]=i;
  }
  for(int i=1;i<=tp;i++) vis[st[i]]=true,nxt[st[i]]=n+1;
  memset(dp,0,sizeof(dp));
  f[n+1]=f[n+2]=0;
  for(int i=n;i>=1;i--){
  	if(!vis[i]){
  	  int tmp=(int)(s[i]-'a');	
	  bool flag=false;
	  for(auto j:dp[i+1]){
	  	if(j.first==tmp){
	  	  nxt[i]=j.second;
	  	  flag=true;
		  break;	
		}
	  }	
	  if(!flag) nxt[i]=n+1;
	}
    dp[i].pb({(s[i]-'a'),i});
  	int tmp=(int)(s[i]-'a');
  	for(auto j:dp[nxt[i]+1]){
  	  if(j.first==tmp) continue;
	  else dp[i].pb(j);	
	}
	//cout<<"pipei:"<<i<<endl;
	//for(auto j:dp[i]) cout<<j.second<<' ';
	//cout<<endl;
  }
  for(int i=n;i>=1;i--){
	if(nxt[i]!=n+1) f[i]=f[nxt[i]+1]+1;
	else f[i]=0;
	//cout<<i<<":"<<nxt[i]<<' '<<f[i]<<endl;
	ans+=f[i];  	
  }
  print(ans);
  return 0;
}

字符串哈希的做法要注意用双哈希！单哈希在 \(n=1e6\) 的时候错误极高！

T3.结构体(struct)

我居然把题意理解错了！！！

image

注意只要每一个元素的起始位置能是 这个元素 的对齐的倍数即可。

所以直接模拟即可。

具体来说就是用两个数组分别存结构体和元素，

查询的时候直接用 while 查询即可（不需要任何优化，暴力枚举）

场下用了大概一个小时写完然后一发过了。。。

还是写了好久！我太菜了。

image

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N=105;
int n,op,c=0,d=0;
ll sum[N];
string str;
struct Str{
  string s,t;//s是结构名称，t为元素名称 
  ll l,r,len,fsy;
}y[N];
struct node{
  int c=0;
  Str nw,a[N];
}f[N];

ll read(){
  ll x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
} 

void print(ll x,char ch){
  int p[25],tmp=0;
  if(x==0) putchar('0');
  if(x<0) putchar('-'),x=-x;
  while(x){
  	p[++tmp]=x%10;
  	x/=10;
  }
  for(int i=tmp;i>=1;i--) putchar(p[i]+'0');
  putchar(ch);
}

map<string,int > mp;
void init(){
  c=4;
  f[1].c=0;f[1].nw={"byte","",0,0,1,1};mp.insert({"byte",1});
  f[2].c=0;f[2].nw={"short","",0,1,2,2};mp.insert({"short",2});
  f[3].c=0;f[3].nw={"int","",0,3,4,4};mp.insert({"int",3});
  f[4].c=0;f[4].nw={"long","",0,7,8,8};mp.insert({"long",4});
}

void sol1(){
  cin>>f[++c].nw.s;
  f[c].c=read();
  mp.insert({f[c].nw.s,c});
  for(int i=1;i<=f[c].c;i++){
  	cin>>f[c].a[i].s>>f[c].a[i].t;
  	
  	int it=mp[f[c].a[i].s];
  	ll fsy=f[it].nw.fsy;
  	
  	f[c].a[i].len=f[it].nw.len;f[c].a[i].fsy=fsy;
  	f[c].nw.fsy=max(f[c].nw.fsy,fsy);
  	
  	if(i==1) f[c].a[i].l=0;
  	else f[c].a[i].l=f[c].a[i-1].r+1;
  	if(f[c].a[i].l%fsy!=0) f[c].a[i].l=((f[c].a[i].l-1)/fsy+1)*fsy;
  	f[c].a[i].r=f[c].a[i].l+f[it].nw.len-1;
  }
  f[c].nw.l=0;
  f[c].nw.len=((f[c].a[f[c].c].r)/f[c].nw.fsy+1)*f[c].nw.fsy;
  print(f[c].nw.len,' ');print(f[c].nw.fsy,'\n');
}

void sol2(){
  d++; 
  cin>>y[d].s>>y[d].t;
  int it=mp[y[d].s];
  if(d==1) y[d].l=0;
  else y[d].l=y[d-1].r+1;
  if(y[d].l%f[it].nw.fsy!=0) y[d].l=((y[d].l-1)/f[it].nw.fsy+1)*f[it].nw.fsy;
  y[d].len=f[it].nw.len;
  y[d].r=y[d].l+y[d].len-1;
  y[d].fsy=f[it].nw.fsy;
  print(y[d].l,'\n');
}

void sol3(){
  cin>>str;string s="";
  ll ans=0,it;bool flag=false;
  int len=(int)str.size();
  for(int i=0;i<len;i++){
  	s="";
  	while(str[i]!='.'&&i<len){
  	  s=s+str[i];
	  i++;	
	}
	if(!flag){
	  for(int j=1;j<=d;j++)
	    if(y[j].t==s){
	      ans+=y[j].l;
	      it=mp[y[j].s];
	      break;
		}	
	  flag=true;
	}
	else{
	  int tmp=it;
	  for(int j=1;j<=f[tmp].c;j++){
	  	if(f[tmp].a[j].t==s){
	  	  ans+=f[tmp].a[j].l;
	  	  it=mp[f[tmp].a[j].s];
		  break;  
		}
	  }
	}
  }
  print(ans,'\n');
}

void sol4(){
  int it=0;ll k=read();
  string ans="";
  for(int i=1;i<=d;i++){
  	if(k>y[i-1].r&&k<y[i].l){puts("ERR");return;}
  	if(y[i].l<=k&&y[i].r>=k){
  	  it=mp[y[i].s];k-=y[i].l;
  	  ans=ans+y[i].t; 
  	  break;
	}
  }
  if(it==0){puts("ERR");return;}
  while(it>4){
  	int tmp=it;bool flag=false;
  	for(int i=1;i<=f[tmp].c;i++){
  	  if(k>f[tmp-1].a[i].r&&k<f[tmp].a[i].l){puts("ERR");return;}
	  if(f[tmp].a[i].l<=k&&f[tmp].a[i].r>=k){
	  	ans=ans+".";ans=ans+f[tmp].a[i].t;
	  	k-=f[tmp].a[i].l;
	  	it=mp[f[tmp].a[i].s];
	  	flag=true;
	  	break;
	  }	
	}
	if(!flag){puts("ERR");return;}
  }
  cout<<ans<<'\n';
}

int main(){
  freopen("struct.in","r",stdin);
  freopen("struct.out","w",stdout);
  n=read();init();
  for(int i=1;i<=n;i++){
  	op=read(); 
  	if(op==1) sol1();
  	if(op==2) sol2();
  	if(op==3) sol3();
  	if(op==4) sol4();
  }
  return 0;
}

T4.种树(tree)

今天改题时才发现其实主要错在精度！！！

为什么我场上加了 __int128 又把它删了，呜呜呜。。。

还是一些细节问题，

注意变量在枚举的过程中是否会改变，

对于区间求和问题可以采用前缀和！！！

具体思路：

考虑二分答案，

这样可以算出每一个点最晚的种树时间（这里可以二分也可以手解一元二次方程）

于是我们从小到大枚举，

对于每一个枚举到的点，我们就不断往上跳到一个已经被种树的点，

把这条路打通即可。

注意判断一下打到这里的时间是否合法。

在考场代码上面进行了修改——还是比较丑。

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N=1e5+5;
int n,head[N],tot=0,fa[N];
struct node{
  ll a,b,c,d;
}a[N];
ll tim[N];
struct edge{
  int v,nxt;
}e[N<<1];

ll read(){
  ll x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

void add(int u,int v){
  e[++tot]=(edge){v,head[u]};
  head[u]=tot;
  e[++tot]=(edge){u,head[v]};
  head[v]=tot;
}

void dfs(int u,int pre){
  fa[u]=pre;
  for(int i=head[u];i;i=e[i].nxt){
  	int v=e[i].v;
  	if(v==pre) continue;
  	dfs(v,u);
  }
}

void print(ll x){
  int p[25],tmp=0;
  if(x==0) putchar('0');
  if(x<0) putchar('-'),x=-x;
  while(x){
  	p[++tmp]=x%10;
  	x/=10;
  }
  for(int i=tmp;i>=1;i--) putchar(p[i]+'0');
  putchar('\n');
}

#define i128 __int128 

i128 calc(int i,ll x){
  if(a[i].c>=0||x<=a[i].d) return (i128)(x+1)*x/2ll*a[i].c+(i128)x*a[i].b;
  return (i128)(a[i].d+1ll)*a[i].d/2ll*a[i].c+(i128)a[i].d*a[i].b+(i128)(x-a[i].d);
}

ll find(int i,ll x){
  
  i128 tmp=calc(i,x);
  if(tmp<a[i].a) return -1;
  ll l=1,r=x;
  while(l<r){
  	ll m=(l+r+1)/2;
  	if(tmp>=(i128)a[i].a+calc(i,m-1)) l=m;
  	else r=m-1;
  }
  return l;
}
#define pii pair<ll,int>
bool vis[N];
bool chk(ll x){
  for(int i=1;i<=n;i++){
  	tim[i]=find(i,x);
  	if(tim[i]==-1) return false;
  }
  priority_queue<pii,vector<pii>,greater<pii> > q;
  for(int i=1;i<=n;i++) vis[i]=false,q.push({tim[i],i});
  vis[0]=true;ll t=0;
  while(!q.empty()){
  	int u=q.top().second;q.pop();
  	if(vis[u]) continue;
  	vis[u]=true;int len=0,v=u;
  	while(!vis[fa[v]]&&fa[v]!=0) len++,v=fa[v],vis[v]=true;
  	len++;t+=len;
  	if(t>tim[u]||t>x) return false;
  }
  return true;
}

int main(){
  freopen("tree.in","r",stdin);
  freopen("tree.out","w",stdout);
  n=(int)read();
  for(int i=1;i<=n;i++){
  	a[i].a=read(),a[i].b=read(),a[i].c=read();
  	if(a[i].c<0) a[i].d=(1-a[i].b)/a[i].c;
  }
  for(int i=1,u,v;i<n;i++) u=(int)read(),v=(int)read(),add(u,v);
  dfs(1,0);
  ll L=n,R=1e9;
  while(L<R){
  	ll mid=(L+R)/2;
  	if(chk(mid)) R=mid;
  	else L=mid+1;
  }
  print(L);
  return 0;
}

Conclusion

  1. 注意变量在枚举的过程中是否会改变。

  2. 对于区间求和问题可以采用前缀和！！！

标签：nxt,ch,int,题解,ll,2023,fsy,CSP,nw
From： https://www.cnblogs.com/hwy0622/p/csps2023.html

相关文章

  • CSP2023冬眠记
    书接上回day-16吃饭睡觉拜bot。day-15吃饭睡觉拜bot。day-14吃饭睡觉拜bot。day-13吃饭睡觉拜bot。day-12吃饭睡觉拜bot。day-11吃饭睡觉拜bot。day-10吃饭睡觉拜bot。day-9在学校OJ打上榜首。day-8被HB模拟赛偷袭，不会T1，掉下榜首。并获得成就【你不......
  • FSCTF 2023（公开赛道）WP
    FSCTF2023ID：Mar10Rank：6总结：下次看到不正常报错一定重新安装一遍工具~~web源码！启动!就在源码注释里<!--师傅们，欢迎来到CTF的世界~NSSCTF{59a1d387-6eb8-40d0-828d-99ce32b3feb8}--->webshell是啥捏哭脸是passthru，那直接命令执行Hello,you源码有注释......
  • 每日总结20231024
    代码时间（包括上课）6h代码量（行）：100行博客数量（篇）：1篇相关事项：1、今天是周二，今天上午上的是大型数据库应用技术和习概，大型数据库应用技术讲的是spark的相关知识，习概课讲的是党的领导的种种优势。2、今天下午上的是软件需求案例分析，这节课还是上机课，然后写的是大作业，农作物籽粒的进......
  • Codeforces 1862G 题解
    传送门题解因为有这个操作：将序列\(a\)加上\(\{n,n-1,\cdots,1\}\)，考虑差分。那么显然每次操作会将差分数组中的每个元素减去\(1\)，如果差分数组中有\(0\)，就会把\(0\)删除。所以可以发现差分数组中剩下的一定是操作前的最大值。由于操作后最大值还是最大值，最小值仍......
  • 2023NOIP A层联测16 T3 货物运输
    2023NOIPA层联测16T3货物运输题目描述说这是一个仙人掌图，通常将问题转换为环和树的问题在使用圆方树来解决。树解法令\(a_i=s_i-\frac{\sums_i}{n}\)，最终令\(a_i=0\)。通过树形dp，从叶子节点向上转移，叶子节点要么向父亲拿资源，要么向父亲传资源，所以转移为：\[a_{fa}+=a_i......
  • CF1777A题解
    分析发现操作2不会改变数的奇偶性，故无视。那么操作就是单纯删一个数。对于一个连续出现\(x\)个奇偶性相同的数的序列，需要删\(x-1\)个数（因为只剩下一个数就不会和相邻的数奇偶性相同了）。觉得找序列太麻烦，观察到连续出现\(x\)个奇偶性相同的数的序列有\(x-1\)个不......
  • CF1523D Love-Hate 题解
    抽象化题意：一共有\(m\)个元素，给定\(n\)个集合，每个集合的元素不超过\(15\)个，求出一个元素个数最多的集合\(S\)是至少\(\lceil\dfrac{n}{2}\rceil\)个集合的子集。其中$p$$(1\len\le2\cdot10^5,1\lep\lem\le60)$我们先假设\(limit=\lceil\dfrac......
  • 2023-10-24 Too many re-renders. React limits the number of renders to prevent an
    React报错：Toomanyre-renders.Reactlimitsthenumberofrenderstopreventaninfiniteloop. 重新渲染过多。React限制渲染次数，以防止出现无限循环。解决方案：查看你最近写的代码，比如我写了一个函数组件，我在函数组件里面写了直接执行的任务，这将导致状态变化，react会重新渲......
  • CSP-S2023游寄
    补个游记。day0前往秦皇岛，路上颓废，打半天地灵殿N打不过，一直卡在小五。不过顺便打通了非想天则N。day1上午复习了一些板子。下午考试。T1一看范围，爆搜题。但一开始读错题了，开场大概40分钟才做完。然后开始做T2，嗯？范围\(2\times10^6\)，CCF应该不会出什么卡常题吧，感觉正解应......
  • 2023级HAUT新生周赛题解汇总
    2023级HAUT新生周赛（零）熟悉周赛规则专场：2023级HAUT新生周赛（一）@21级学长专场（张子豪，张鑫，李昊阳）：2023级HAUT新生周赛（二）@曹瑞峰专场：2023级HAUT新生周赛（三）@22级学姐专场（杨焱，刘振歌，周欣滢）：2023级HAUT新生周赛（四）@牛浩然专场：2023级HAUT新生周赛（五）@陈兰锴专场：......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99