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

CSP-S 2023 题解

时间：2024-03-25 13:56:34浏览次数：34  
标签：ch int 题解 LL py 2023 ly CSP define

T1

听说有歧义？希卓没看懂。

不过真的水。

你看能把它拧成什么正确密码。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,sum,a[10][6],p,b[10][6];
LL f[100010];
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=5;j++)
		{
			scanf("%lld",&a[i][j]);
			b[i][j]=a[i][j];
		}
		for(int j=1;j<=9;j++)
		{
			for(int k=1;k<=5;k++)
			{
				b[i][k]+=j;
				b[i][k]%=10;
				p=0;
				for(int o=1;o<=5;o++)p=p*10+b[i][o];
				f[p]++;
				b[i][k]=a[i][k];
			}
		}
		for(int j=1;j<=9;j++)
		{
			for(int k=1;k<5;k++)
			{
				b[i][k]+=j;
				b[i][k+1]+=j;
				b[i][k]%=10;
				b[i][k+1]%=10;
				p=0;
				for(int o=1;o<=5;o++)p=p*10+b[i][o];
				f[p]++;
				b[i][k]=a[i][k];
				b[i][k+1]=a[i][k+1];
			}
		}
	}
	for(int i=0;i<=99999;i++)
	{
		if(f[i]==n)sum++;
	}
	printf("%lld",sum);
	return 0;
}

T2

CCF=Copy CodeForces。

CF1223F原题。

说句闲话：研究珂学的最好方法是我不这么认为。

一共就那么多算法，重了正常吧。

我从小喝到大选择DP。

我认为，这题用DP，比起哈希真的就是华为Mate 60——遥遥领先！

求出 \(ne_i\)，让 \(ne_i\) 是让\([i,ne_i]\)为序列的最左边的那一个。

然后，DP，启动！

\(f[i]\)表示以\(i\)为开头的序列数目。

所以，

\[ f[i]=f[nxt[i]]+1 \]

\[ ans=\sum\limits_{i=1}^nf[i] \]

\(ne_i\) 求法：说不太清楚啊，看代码你们能看懂吧QWQ。

当然，这样不能满屏草地AC。

所以优化:

对每一个位置开一个 \(map\)，\(map_{i,j}\) 记录了 \(i\) 右边的一个位置 \(pos\)，且 \([i,pos−1]\) 是合法的，所以 \(ne_i=map_{i+1,a_i}\)。

就是这样。

赛时根本没做。

代码：

#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 99824420520
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void write(i128 x)
{
	if(x>=10)write(x/10);
	putchar(x%10+'0');
}
LL q,n;
char a[2000010];
LL nxt[2000010],f[2000010];
map<LL,LL>mp[2000010];
int main()
{
	q=1;
	while(q--)
	{
		cin>>n;
		rep(i,1,n,1)cin>>a[i];
		for(LL i=1;i<=n+1;i++)mp[i].clear(),f[i]=0,nxt[i]=-1;
		for(LL i=n;i;i--)
		{
			if(mp[i+1].count(a[i]))
			{
				LL pos=mp[i+1][a[i]];
				nxt[i]=pos;
				swap(mp[i],mp[pos+1]);
				if(pos<n)mp[i][a[pos+1]]=pos+1;
			}
			mp[i][a[i]]=i;
		}
		LL res=0;
		for(LL i=n;i;i--)
		{
			if(nxt[i]==-1)continue;
			f[i]=f[nxt[i]+1]+1;
			res+=f[i];
		}
		cout<<res<<endl;
	}
	return 0;
}

T3

赛时没做。

作者没有hand和肝写所以放一个链接：link

代码：

#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void write(i128 x)
{
	if(x>=10)write(x/10);
	putchar(x%10+'0');
}
struct ly
{
	string nam,ty;
	LL l,d,py;
	vector<ly *>s;
	ly()
	{
		py=l=d=0;
		nam=ty="";
	}
	ly(LL l,string ty)
	{
		this->py=0;
		this->l=l;
		this->d=l;
		this->ty=ty;
	}
};
map<string,ly>CGMP;
LL cei(LL a,LL b)
{
	return a/b+(LL)(a%b>0);
}
void bui(string x,LL k)
{
	ly t;
	t.ty=x;
	LL py=0;
	ly *l;
	rep(i,1,k,1)
	{
		string ty,a;
		cin>>ty>>a;
		ly *t1=new ly(CGMP[ty]);
		t1->nam=a;
		t.d=max(t1->d,t.d);
		if(i!=1)
		{
			t1->py=t1->d*cei(l->py+l->l,t1->d);
		}
		t.s.push_back(t1);
		l=t1;
	}
	t.l=t.d*cei(l->l+l->py,t.d);
	CGMP[x]=t;
	cout<<t.l<<' '<<t.d<<endl;
}
ly *tt=new ly();
void ad(string ty,string nam)
{
	ly *t=new ly(CGMP[ty]);
	t->nam=nam;
	LL x,y,s=0;
	vector<ly *>v=tt->s;
	if(v.empty())
	{
		x=0,y=0;
	}
	else
	{
		x=(*--v.end())->py;
		y=(*--v.end())->l;
	}
	s=cei(x+y,t->d)*t->d;
	t->py=s;
	tt->s.push_back(t);
	cout<<s<<endl;
}
LL fi(string x)
{
	vector<string>v;
	LL ls=0,l=x.size();
	rep(i,1,l,1)if(x[i-1]=='.')v.push_back(x.substr(ls,i-ls-1)),ls=i;
	v.push_back(x.substr(ls,l-ls));
	ly *nw=tt;
	LL s=0,py;
	rep(i,1,v.size(),1)
	{
		py=s;
		rep(j,1,nw->s.size(),1)
		{
			ly *k=nw->s[j-1];
			py=s+k->py;
			if(k->nam==v[i-1])
			{
				s=py;
				nw=k;
				break;
			}
		}
	}
	return py;
}
string CG(ly *nw,LL s,LL t)
{
	string ans="";
	rep(i,1,nw->s.size(),1)
	{
		ly *k=nw->s[i-1];
        if(s+(k->py)<=t&&t<s+(k->py)+(k->l))
		{
            ans=k->nam;
            if(k->s.size())ans+="."+CG(k,s+(k->py),t);
            break;
        }
	}
	if(ans.empty())return "ERR";
	else return ans;
}
LL n;
int main()
{
	cin>>n;
	CGMP["long"]=ly(8LL,"long");
	CGMP["int"]=ly(4LL,"int");
	CGMP["short"]=ly(2LL,"short");
	CGMP["byte"]=ly(1LL,"byte");
	rep(i,1,n,1)
	{
		LL op;
		cin>>op;
		if(op==1)
		{
			string x;
			LL y;
			cin>>x>>y;
			bui(x,y);
		}
		if(op==2)
		{
			string x,y;
			cin>>x>>y;
			ad(x,y);
		}
		if(op==3)
		{
			string x;
			cin>>x;
			cout<<fi(x)<<endl;
		}
		if(op==4)
		{
			LL adr;
			cin>>adr;
			string t=CG(tt,0,adr);
			if(t.find("ERR")!=-1)cout<<"ERR"<<endl;
			else cout<<t<<endl;
		}
	}
	return 0;
}

T4

赛时没做。

woc崧维nb！口胡解法！

思路就是二分套二分。

众所周知我 \(\LaTeX\) 超级差所以放个链接：link

哦对了特别卡常所以要优化一下。

代码：

#include<bits/stdc++.h>
#define LL long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define i128 __int128
#define min(a,b) (a)<(b)?(a):(b)
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;
const int N=1e5+5;
int h[N],len;
struct nod
{
	int to,ne;
}ed[N<<1];
void add(int u,int v)
{
	ed[++len]={v,h[u]};
	h[u]=len;
}
int f[N];
void dfs(int u,int fa)
{
	f[u]=fa;
	for(int i=h[u];i;i=ed[i].ne)
	{
		int v=ed[i].to;
		if(v!=fa)dfs(v,u);
	}
}
i128 ca(i128 x)
{
	return x*(x+1)/2;
}
const i128 ly=1;
inline i128 ca(i128 a,i128 b,i128 c)
{
	i128 x=max(ly,min(a+1,(i128)ceil(1.0*(1-b)/c)));
	if(c<0)return (x-1)*b+ca(x-1)*c+(a-x+1);
	if(c==0)return a*b;
	return (x-1)+(a-x+1)*b+(ca(a)-ca(x-1))*c;
}
LL a[N],b[N],c[N];
int p[N],t[N],n;
bool usd[N];
int upd(int u)
{
	if(usd[u])return 0;
	usd[u]=1;
	if(f[u])return upd(f[u])+1;
	return 1;
}
bool cmp(int x,int y)
{
	return t[x]<t[y];
}
bool sw(int x)
{
	rep(i,1,n)
	{
		usd[i]=0;
		i128 va=ca(x,b[i],c[i]);
		if(va<a[i])return 0;
		int l=1,r=n,ans=-1;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(va-ca(mid-1,b[i],c[i])>=a[i])
			{
				ans=mid,l=mid+1;
			}
			else r=mid-1;
		}
		t[i]=ans;
	}
    sort(p+1,p+n+1,[](const int &x,const int &y){
        return t[x]<t[y];
    });
	int res=0;
	rep(i,1,n)
	{
		res+=upd(p[i]);
		if(res>t[p[i]])return 0;
	}
	return 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*10+ch-48,ch=getchar();
    return x*f;
}
int main()
{
	n=read();
	rep(i,1,n)
	{
		a[i]=read(),b[i]=read(),c[i]=read(),p[i]=i;
	}
	rep(i,2,n)
	{
		int u=read(),v=read();
		add(u,v);
		add(v,u);
	}
	dfs(1,0);
	int l=n,r=1e9,ans=1e9;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(sw(mid))
		{
			r=mid-1,ans=mid;
		}
		else l=mid+1;
	}
	printf("%d\n",ans);
	return 0;
}

标签：ch,int,题解,LL,py,2023,ly,CSP,define
From： https://www.cnblogs.com/cppom/p/-/CSP2023Stijie

相关文章

  • CSP-J 2023 题解
    T1这么水？！赛时AC。思路：小学数学题，我孙子都会做认真点。就是余数和商，小学二年级的知识（毕导：亻尔女子）代码：#include<bits/stdc++.h>#defineLLlonglongusingnamespacestd;LLn,sum;LLt(LLa){ if(a!=1)return1+t(a-((a-1)/3+1)); elsereturn1;}intmain(){......
  • AT_arc175_a [ARC175A] Spoon Taking Problem 题解
    题目翻译link有\(N\)人围坐在一张圆桌旁，按逆时针顺序编号为\(1\)至\(N\)。每个人都有一个惯用手圆桌上有\(N\)把勺子，编号为\(1\)到\(N\)，每对相邻的人之间放一把勺子给你一个\((1,\dots,N)\)的排列组合\((P_1,\dots,P_N)\)。在\(i=1,\dots,N\)的顺序中，人......
  • 题解：AT_abc345_c [ABC345C] One Time Swap
    求过审题面翻译给定一个字符串$s$，求执行以下操作一次可以产生的字符串的个数设$N$为$s$的长度。选择一对整数$(i,j)$，使$1≤i<j≤N$，交换$s$的第$i$个和第$j$个字符可以证明，在这个问题的约束条件下，你总是可以得到它思路暴力做法我们可以......
  • JavaScript:void(0) 用法及常见问题解析
    JavaScript:void(0)用法及常见问题解析javascript:void(0);是一种在JavaScript和网页开发中经常使用的技术，尤其在处理链接的行为时。本文将深入探讨javascript:void(0);的用法，以及在使用过程中可能遇到的常见问题和解决方法。什么是javascript:void(0);？javascript:v......
  • LeetCode第390场周赛题解（c++）
    真的无语了，早上怎么都提交不了，显示未知错误。。。结果晚上就可以提交了。唉100245.每个字符最多出现两次的最长子字符串给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的 最大 长度。示例1：输入： s="bcbbbcba"输出： 4解释：以......
  • [题解]HDU1024 Max Sum Plus Plus
    HDU1024这道题是一道很巧妙的\(dp\)题（虽然优化成一维，可是究其本质算不算二维\(dp\)？如果有明白的麻烦在评论说一下多谢），在上一篇文章——线性\(dp\)模型中也提到过，因为其前身其实就是上一篇写到的「最大连续子段和」。只不过这一题问的不是一段，而是\(m\)段，所以较上一题我们的选择......
  • AtCoder Beginner Contest 346 题解
    A-AdjacentProductQuestion给你\(N\)个整数\(A_1,A_2,\dots,A_N\)。同时，定义\(B_i=A_i\timesA_{i+1}\(1\leqi\leqN-1)\)按此顺序打印\(B_1,B_2,\dots,B_{N-1}\)Solution按照题意模拟Code#include<bits/stdc++.h>usingnamespacestd;intmain......
  • AT_abc344_D-String Bags 题解
    明显是DP。然后就开始分析：状态：\(dp_{ij}=\)有\(i\)个袋子且匹配\(T\)的前缀的长度为\(j\)时所需的最少钱数。匹配\(T\)的前缀的长度为\(j\)就是前\(j\)个字符与\(T\)的前\(j\)个字符相同。相对简单。然后看转移。为了方便，咱不妨令\(|S|\)为字符串\(S......
  • P10111 [GESP202312 七级] 纸牌游戏 题解
    看标签知道要用DP。于是开始分析。状态：$dp(i,j,k)=$前\(i\)轮中，第\(i\)轮出\(j\)，一共换了\(k\)次牌的最大钱数。很好理解。转移也不难，不就是不换和换两种吗！所以，转移就是：\[dp(i,j,k)=\max\begin{cases}dp(i-1,j,k)+\operatorname{pk}(j,c_i)\times......
  • [暴力题解系列]2023年蓝桥杯-整数删除（30分）
    这题暴力最多30分，但是30分也是分，做暴力的人不能贪心，拿到分就是赚了。​ 这题核心烦人点在于他数据分层断崖，就只有前3个点能做到稳过。用的思路就是链表，但不是用指针存的，而是用数组下标为标记存的，只是我觉得因为这样好写一些。链表方便修改左右连接位置，所以越到后面就越能省下查询......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99