首页 > 其他分享 >CSP-S 模拟赛 #2 题解

CSP-S 模拟赛 #2 题解

时间:2022-10-05 15:45:31浏览次数:83  
标签:10 ch int 题解 nx ny while CSP 模拟

300 rk3。题面是本校 OJ 的,链接挂了找我。

upd: T1 被 xiaopanda 的 hack 数据卡了。

T1-A-B

Problem

出题是一件痛苦的事情!

题目看多了也有审美疲劳,于是我舍弃了大家所熟悉的 A+B Problem,改用 A-B 了哈哈!

好吧,题目是这样的:给出一串数以及一个数字 \(C\) ,要求计算出所有 \(A-B=C\) 的数对的个数。(不同位置的数字一样的数对算不同的数对)。

输入格式

第一行包括2个非负整数 \(N\) 和 \(C\),中间用空格隔开。
第二行有 \(N\) 个整数,中间用空格隔开,作为要求处理的那串数。

输出格式

输出一行,表示该串数中包含的所有满足 \(A-B=C\) 的数对的个数。

Input

4 1
1 1 2 3

Output

3

\(1\le N\le 2\times 10^5\)。

Solution

签到,用个 map 瞎几把乱搞就可以了。
hack: \(c=0\),算答案会被加两遍,减掉即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline void read(int &x)
{
	char ch=getchar();
	int r=0,w=1;
	while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
	while(isdigit(ch))r=(r<<3)+(r<<1)+(ch^48),ch=getchar();
	x=r*w;
}
map<int,int>mp;
const int N=1e6+7;
int a[N];
main()
{
	freopen("a-b.in","r",stdin);
	freopen("a-b.out","w",stdout);
	int n,c,ans=0;
	read(n);read(c);
	for(int i=1;i<=n;i++)
		read(a[i]),mp[a[i]]++;
	for(int i=1;i<=n;i++)
		ans+=mp[a[i]+c]-(c==0);
	cout<<ans;
	return 0;
}

T2-吉波那契数列

题面

Solution

先表示 \(G_i\):
\(G_0=1,G_1=t,G_2=t+1,G_3=2t+1,G_4=3t+2,G_5=5t+3\)。

那么对于斐波那契 \(F={0,1,1,2,3,5...}\) (下标从 \(0\) 开始),有
\(G_i=F_it+F_{i-1}(i>0)\),所以只要预处理出斐波那契数列,直接解方程看是否满足条件。

#include<bits/stdc++.h>
#define int long long
using namespace std;
void read(int &x)
{
	char ch=getchar();
	int r=0,w=1;
	while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
	while(isdigit(ch))r=(r<<3)+(r<<1)+(ch^48),ch=getchar();
	x=r*w;
}
const int N=5e6+7,mod=19960515;
int f[N];
void solve(){
	int x,k,y;
	read(x);read(k);read(y);
	int t=(k-f[x-1])/f[x];
	if(t*f[x]!=k-f[x-1]||t<=0){puts("-1");return;}
	printf("%lld\n",(f[y]*t%mod+f[y-1])%mod);
}
main()
{
	freopen("gibonacci.in","r",stdin);
	freopen("gibonacci.out","w",stdout);
	f[0]=0;f[1]=1;
	for(int i=2;i<=5e6;i++)
		f[i]=f[i-1]+f[i-2],f[i]%=mod;
	int T;
	read(T);
	while(T--)solve();
	return 0;
}

T3-魔塔

题面

Solution

测试时因不明原因写挂而爆0。

考虑到数据规模较小,设 \(f(x,y,h,ans)\) 表示在 \((x,y)\) 剩余 \(h\) 体力,打过 \(ans\) 个怪,直接记忆化搜索即可,注意合理剪枝。

std 超级压行版:

#include<cstdio>
int h,n,m,tim,ans,x,y,i,j;char a[10][10],v[10][10][10][10];
int dx[]={-1,0,0,1},dy[]={0,-1,1,0};
int check(int x,int y){return x>=0&&x<n&&y>=0&&y<m;}
void dfs(int x,int y,int h,int k){
	if(v[x][y][h][k]==tim)return;v[x][y][h][k]=tim;
	for(int nx,ny,i=0;i<4;i++)
	if(check(nx=x+dx[i],ny=y+dy[i]))
	if(a[nx][ny]=='.')dfs(nx,ny,h,k);
	else if(a[nx][ny]=='E'){if(ans>k)ans=k;return;}
	else if(a[nx][ny]=='C')a[nx][ny]='.',dfs(nx,ny,h+5,k),a[nx][ny]='C';
	else if(a[nx][ny]=='M'&&h>0)a[nx][ny]='.',dfs(nx,ny,h-1,k+1),a[nx][ny]='M';
}
int main(){
	freopen("tower.in","r",stdin);
	freopen("tower.out","w",stdout);
	while(~scanf("%d%d%d\n",&h,&n,&m)){
		for(i=0,++tim;i<n;i++)scanf("%s",a[i]);
		for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		if(a[i][j]=='S')x=i,y=j,a[i][j]=0;
		ans=233,dfs(x,y,h,0);
		if(ans==233)puts("Poor Warrior");
		else printf("%d\n",ans);
	}
}

return 0 CCF 那里会爆0的(。

T4-对战

题面

Solution

题目要求裁判水平要在两人之间,那个什么路程条件就是说选的裁判的下标也要在两人之间,即选择 \(i<k<j\) 满足 \(a_i<a_k<a_j\) 或 \(a_i>a_k>a_j\)。

考虑枚举裁判,如果我们知道他左边有几个比他小,右边有几个比他大,根据乘法原理即可求出答案,这个用树状数组维护值域即可(逆序对都会叭)。最后把两种情况相加。

代码的变量应该都看得懂。

#include<bits/stdc++.h>
#define int long long
using namespace std;
void read(int &x)
{
	char ch=getchar();
	int r=0,w=1;
	while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
	while(isdigit(ch))r=(r<<3)+(r<<1)+(ch^48),ch=getchar();
	x=r*w;
}
const int N=1e6+7;
int a[N],n,lmx[N],rmx[N],lmn[N],rmn[N],c[N],mx;
int lowbit(int x){return x&-x;}
void add(int x,int k){
	while(x<=mx){
		c[x]+=k;
		x+=lowbit(x);
	}
}
int query(int x){
	int sum=0;
	while(x>=1){
		sum+=c[x];
		x-=lowbit(x);
	}
	return sum;
}
void clear(){memset(c,0,sizeof c);}
void solve(){
	read(n);mx=-1;
	for(int i=1;i<=n;i++)read(a[i]),mx=max(mx,a[i]);
	clear();
	for(int i=1;i<=n;i++){
		lmn[i]=query(a[i]-1);
		lmx[i]=i-1-lmn[i];
		add(a[i],1);
	}
	clear();
	for(int i=n;i>=1;i--){
		rmn[i]=query(a[i]-1);
		rmx[i]=n-i-rmn[i];
		add(a[i],1);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		ans+=lmn[i]*rmx[i]+lmx[i]*rmn[i];
	printf("%lld\n",ans);
}
main()
{
	freopen("inhouse.in","r",stdin);
	freopen("inhouse.out","w",stdout);
	int T;
	read(T);
	while(T--)solve();
	return 0;
}

标签:10,ch,int,题解,nx,ny,while,CSP,模拟
From: https://www.cnblogs.com/LAK666/p/16755631.html

相关文章

  • texlive编译中发现字体有问题解决
    这里可以用tlmgrinfo命令搜索需要下载的字体并从CTAN官网下载。一般这个时候也会有对应的路径,比如texmf-dist/fonts/。把下载的字体解压放在这些路径下,然后分别运行mktexl......
  • 2022.10.5 模拟赛
    T1签到题题面Description给定\(n\)个数,求出这\(n\)个数的一个非空子集,使得这个子集中的数的和能被\(n\)整除,无解输出\(-1\).Input第一行为数据组数\(T\)接下来\(T\)......
  • 【LGR-122】T1 & T2 题解
    T1下面所说的做法来自于dty(%%%%%%%%%)注意到每一个数的绝对值是大于等于\(2\)的,那么就可以发现一个性质:当一个区间长度为\(len\)时,如果\(len\ge62\),那么这个区间的......
  • 组态软件报警问题解决
    作为工业自动化领域的从业者,经常会使用各种组态软件,近期作者在使用业界鼎鼎大名的组态软件IFix过程中就遇到了一个小case,现在分享给大家。众所周知,IFix在运行过程中报警会......
  • 【题解】P3583 [POI2015] KWA
    模拟赛出这道题???还好赛时乱搞做出来了(/hanxlinkDescription定义一个数\(n\)的拆分为:将\(n\)表示为若干个不同的正整数的平方和。令\(k(n)\)为\(n\)的拆分中最......
  • CF 547D. Mike and Fish 题解
    Solution1二分图染色显然这题是构造染色方案,于是我们考虑将矩阵转化成图进行染色。结论:将同一行的点两两配对,将同一列的点两两配对,形成的一定是二分图。证明:由于每......
  • P4572 题解
    前言题目传送门!更好的阅读体验?双倍经验:P3554(数据坑一点)。简要题意可以看P3554。思路:二分答案+树形DP。思路答案显然具有单调性,所以考虑二分答案。\(\operatorna......
  • P3226 [HNOI2012]集合选数 题解
    纪念一下30紫and500AC首先先膜拜一下神仙出题人,这题太神仙了。题意:要构造一个集合,使得$x\inA$,满足$2x\notinA$且$3x\notinA$,求\(\{1,2,\ldots,n\}\)......
  • 2022 CSP-J/S 游寄
    \(\color{blue}{\texttt{FirstRound}}\)Day-x报名了CSP-J/S.Day-6切掉了P7426体育成绩统计,自我感觉良好。Day-2把初赛知识硬生生看了一遍,一个字没被进去,是死......
  • 原始递归函数及模拟运行的优化
    看到网上一个题目,证明x开y次方是原始递归函数(primitiverecursivefunction)。这个问题并不难,只要把x开y次方实现出来即可。于是,正好把《递归论》相关内容补一补。【......