首页 > 其他分享 >CSP-J模拟赛一补题报告

CSP-J模拟赛一补题报告

时间：2024-10-03 21:47:11浏览次数：7  
标签：cnt return int 样例 long step 赛一 补题 CSP

IAKIOI！！！

前言

考的最好的一回：240pts
首先开T1，45min干掉了
然后T2，45min挂了
然后T3，40min又挂了
然后发呆了一会把T4 骗分打了 ，此时已过去一坤时
40minT2切了，最后20min打了T3骗分又发呆了一会
T1：100pts
T2：100pts
T3：30pts
T4：10pts

《正文》

0101101010100101001010101101010001101010101000110010101011001010010101001100101010101101100101010101010101010101011010101010101001101010010101010101010010101001010011010010101010010110010101000101010100101010110100101011001101001101101010010101010101001010101001010101100101010101010101100101010100101010100000010101001010100101101010010011000101001010101010101010101010101010101010101001010101010101
0101101010100101001010101101010001101010101000110010101011001010010101001100101010101101100101010101010101010101011010101010101001101010010101010101010010101001010011010010101010010110010101000101010100101010110100101011001101001101101010010101010101001010101001010101100101010101010101100101010100101010100000010101001010100101101010010011000101001010101010101010101010101010101010101001010101010101
1010101010010110010101010101010101101100101010101010101010101010101010101010101010110101010101010100101010010101101010101010011010101010101010100111000110010101
0101101010100101001010101101010001101010101000110010101011001010010101001100101010101101100101010101010101010101011010101010101001101010010101010101010010101001010011010010101010010110010101000101010100101010110100101011001101001101101010010101010101001010101001010101100101010101010101100101010100101010100000010101001010100101101010010011000101001010101010101010101010101010101010101001010101010101
0101101010100101001010101101010001101010101000110010101011001010010101001100101010101101100101010101010101010101011010101010101001101010010101010101010010101001010011010010101010010110010101000101010100101010110100101011001101001101101010010101010101001010101001010101100101010101010101100101010100101010100000010101001010100101101010010011000101001010101010101010101010101010101010101001010101010101
1010101010010110010101010101010101101100101010101010101010101010101010101010101010110101010101010100101010010101101010101010011010101010101010100111000110010101
01010011001010101011010100110001010101011001001010101010111001010101010101010100

T1 交替出场(alter)

简单，秒了

题面

时间限制：1秒 内存限制：256M

题目描述

给定一个字符串，仅包含字符 0 或 1，求字符串中的 01 交替子串个数。

01 交替串的定义是，前一位必须不同于后一位的字符串。

特殊的，任意的长度为 1 的字符串也被定义为 01 交替串。

输入描述

一行，一个字符串 s s s，保证仅包含字符 0 或 1。

输出描述

一行一个整数，表示 s s s 中的 01 交替子串个数。

输入样例

0101

输出样例

10

样例解释

显然的，任意一个子串都是 01 交替子串。

数据范围

定义 n n n 为字符串 s s s 的长度。
对于 20% 数据：

1 ≤ n ≤ 3 1≤n≤3 1≤n≤3

对于另外 60% 数据：

1 ≤ n ≤ 100 1≤n≤100 1≤n≤100
1 ≤ n ≤ 100 1≤n≤100 1≤n≤100

对于全部数据：

1 ≤ n ≤ 1000 1≤n≤1000 1≤n≤1000

解析

c n t cnt cnt为找到的01交替子串长度， s i z siz siz为字符串长度
枚举子串的开头 i i i，结尾 j j j
j j j一定要从 i i i按顺序枚举到 s i z e size size
如果子串 [ i , j − 1 ] [i,j-1] [i,j−1]不是01交替子串，子串 [ i , j ] [i,j] [i,j]必定也不是，此时直接break。
否则发现了一个新的01交替子串， c n t + + cnt++ cnt++。
秒了
s = s= s=" " + s +s +s是为了从一开始扫。

AC Code

#include<bits/stdc++.h>
using namespace std;
string s;
/* 
bool check(long long l,long long r)
{
	for(int i=l+1;i<=r;i++)
	{
		if(s[i]==s[i-1])
		{
			return 0;
		}
	}
	return 1;
}
*/
int main()
{
	freopen("alter.in","r",stdin);
	freopen("alter.out","w",stdout);
	cin>>s;
	long long ans=0,siz=s.size();
	s=" "+s;
	/*
	for(int len=1;len<=siz;len++)
	{
		for(int l=1;l<=siz-len+1;l++)
		{
			long long r=l+len;
			if(check(l,r));
			{
				ans++;
			}
		}
	}
	*/
	//暴力代码保留备用 
	int cnt=0; 
	for(int i=1;i<=siz;i++)
	{
		cnt++;
		for(int j=i+1;j<=siz;j++)
		{
			if(s[j-1]==s[j])
			{
				break;
			}
			cnt++;	
		}
	}
	printf("%d",cnt);
	return 0;
}

T2 翻翻转转(filp)

有难度

题面

时间限制：1秒 内存限制：256M

题目描述

gza 有一系列的字符串，第 i i i个名为 s ​ i s_​i s​​i。

s 0 = 1 s_0=1 s0​=1
s 1 = 10 s_1=10 s1​=10
s 2 = 1001 s_2=1001 s2​=1001
s 3 = 10010110 s_3=10010110 s3​=10010110

⋯⋯
s ​ i s_​i s​​i是 s ​ i − 1 s_{​i−1} s​i−1​
​​ 逐位取反后拼接在 s ​ i − 1 s_{​i−1} s​i−1​
​​ 后的串。

你需要求 s 114514 s_{114514} s114514​的第 x x x 个字符是什么。

多测。

输入描述

第一行一个整数 T T T，表示数据组数。

接下来
T T T 行，一行一个整数，表示 x x x，含义见题目描述。

输出描述

一共 T T T 行，一行一个字符，表示答案。

输入样例

1
3

输出样例

0

数据范围

对于 10%的数据：

x ≤ 100 x≤100 x≤100。

对于另外 50% 的数据：

x ≤ 1 0 7 x≤10^7 x≤107​​ 。

对于全部数据：

x ≤ 1 0 9 x≤10^9 x≤109。

思路

类似倍增
用 x x x依次尝试减去 2 32 2^{32} 232到 2 0 2^0 20
每次操作后， x x x将被取反
如果操作偶数次，则 x x x不变，反之 x x x取反
x x x最后的位置一定为1，值也为1
最后判断是否取反
不要忘记是多组测试数据

AC Code

#include<bits/stdc++.h>
using namespace std;
long long cf[40];
void getpow()
{
	cf[0]=1;
	for(int i=1;i<=32;i++)
	{
		cf[i]=cf[i-1]*2;
	}
}
int main()
{
	freopen("filp.in","r",stdin);
	freopen("filp.out","w",stdout);
	int t;
	getpow();
	scanf("%d",&t);
	while(t--)
	{
		long long x;
		scanf("%lld",&x);
		string s;
		int cnt=0;
		for(int i=32;i>=0;i--)
		{
			if(x>cf[i])
			{
				x-=cf[i];
				cnt++;
			}
		}
		if(cnt%2==0)
		{
			printf("1\n");
		}
		else
		{
			printf("0\n");
		}
	}
	return 0;
}
/*
 ********  ********
*          *       *
*          *       *
*********  ********
        *  *       *
		*  *       *
********   ********

*/
//I AK IOI!!!
/*

*/

方格取数(square)

赛时DP写炸，最后一刻总司令了30pts

题面

时间限制：1秒 内存限制：256M

题目描述

想必大家都做过方格取数吧。

现在，你需要做一个特殊的方格取数。

每个格子都有一个数字，走过便能收集，也必须收集。

你从 ( 1 , 1 ) (1,1) (1,1) 出发，目标是 ( n , m ) (n,m) (n,m)，只能向右或者向下走，但是你不能一次性往一个方向走大于等于 k k k 步。

求收集到的数字的和的最大值。

如果无解，输出No Answer!。

输入描述

第 1 行三个正整数 n , m , k n,m,k n,m,k。

接下来 n n n 行每行 m m m 个整数，依次代表每个方格中的整数。

输出描述

一个整数，表示收集到的数字的和的最大值。

输入样例1

3 3 2
1 1 1
1 1 2
1 1 1

输出样例1

6

输入样例2

3 3 2
1 1 2
1 1 1
2 1 1

输出样例2

5

数据范围

被我吃了

思路

记忆化搜索
i , j i,j i,j为坐标， s t e p step step为向同一个方向走的步数， d d d为方向

AC Code

#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
int n,m,k,a[205][205];
int dx[]={0,1},dy[]={1,0};
pair<int,bool>f[205][205][205][2];
int dfs(int x,int y,int step,int d)
{
	if(x>n||y>m||step>k)
	{
		return -0x3f3f3f3f;
	}
	if(x==n&&y==m)
	{
		return a[x][y];
	}
	if(f[x][y][step][d].second)
	{
		return f[x][y][step][d].first;
	}
	f[x][y][step][d].second=1;
	int ans=-0x3f3f3f3f;
	if(step<k)
	{
		ans=max(ans,dfs(x+dx[d],y+dy[d],step+1,d));
	}
	ans=max(ans,dfs(x+dx[d^1],y+dy[d^1],2,d^1));
	if(ans<-1e9)
	{
		return f[x][y][step][d].first=-0x3f3f3f3f;
	}
	return f[x][y][step][d].first=ans+a[x][y];
}
int main()
{
	freopen("square.in","r",stdin);
	freopen("square.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	int tmp=max(dfs(1,2,2,0),dfs(2,1,2,1));
	if(tmp>-1e9)
	{
		printf("%d",tmp+a[1][1]);
		return 0;
	}
	printf("No Answer!");
	return 0;
}
/*

*/

T4 圆圆中的方方(round)

完全不会啊qwq

题面

时间限制：1秒 内存限制：256M

题目描述

你有一个四个边界点为 ( 0 , 0 ) ， ( n , 0 ) ， ( 0 , m ) ， ( n , m ) (0,0)，(n,0)，(0,m)，(n,m) (0,0)，(n,0)，(0,m)，(n,m) 的矩形。

有一点 A ( a , b ) A(a,b) A(a,b)，保证 A A A在矩形内部或边界上，求以 A A A 为圆心，半径为
r r r 的圆与矩形的重叠部分的面积。

输入描述

一行五个浮点数， n , m , a , b , r n,m,a,b,r n,m,a,b,r，含义见题目描述。

输出描述

一行一个浮点数，表示答案。

输入样例

1 1 0 0 1

输出样例

0.7853981634

数据范围被我吃了

AC Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const double pi=acos(-1),eps=1e-8; 
double n,m,a,b,r;
double cal(double n,double m,double r)
{
	if(n<m)
	{
		swap(n,m);
	}
	if(n<=eps||m<=eps)
	{
		return 0;
	}
	if(r<=m)
	{
		return 0.25*pi*r*r;
	}
	if(r>=sqrt(n*n+m*m))
	{
		return n*m;
	}
	if(r<=n)
	{
		return sqrt(r*r-m*m)*m*0.5+0.5*r*r*(0.5*pi-acos(m/r));
	}
	return sqrt(r*r-m*m)*m*0.5+sqrt(r*r-n*n)*n*0.5+0.5*r*r*(0.5*pi-acos(m/r)-acos(n/r));
}
int main()
{
	freopen("round.in","r",stdin);
	freopen("round.out","w",stdout);
	cin>>n>>m>>a>>b>>r;
	printf("%lf",cal(a,b,r)+cal(n-a,b,r)+cal(a,m-b,r)+cal(n-a,m-b,r));
	return 0;
}
/*
 ********  ********
*          *       *
*          *       *
*********  ********
        *  *       *
		*  *       *
********   ********

*/
/*
 ********  *       *   *******   ********    *********
*          *       *      *      *               *
*          *       *      *      *               *
*********  *********      *      ********        *
        *  *       *      *      *               *
		*  *       *      *      *               *
********   *       *   *******   *               *

*/

思路

考虑将整块面积分为四部分，圆心的左上，圆心的左下，圆心的右上，圆心的右下。
那么问题将转化为了，一个圆心在角落的 圆与矩形的面积交。
除去重叠部分为扇形和全部覆盖的，其他情况把图形分割为三角形和扇形计算。
利用亿点点三角函数计算

标签：cnt,return,int,样例,long,step,赛一,补题,CSP
From： https://blog.csdn.net/zth413021/article/details/142670301

相关文章

  • DAY3-补题
    一题之计在于补呐补题很快乐的一点就是看不懂且听不明白但是写注释中理解到了。果然学会一道题最简单的方式是给一个纯萌新讲。说在前面今天%你赛手感非常好，可能是换了一个位置的原因（玄首先T1没有读错题是一个比较大的进步，因为DAY1和2都是因为差不多这个原因寄掉了，读对题目果......
  • 补题报告3
    背景2024-10-3上午打的比赛（CSP-J模拟2），作赛后总结报告。IP地址（\(ip\)）赛时AC。概述每个设备有一个对应的\(IP\),先给出对应的设备与\(IP\),再给出几个\(IP\)，求对应的设备。思路\(map\)存储，映射我的代码代码(点左边三角展开)#include<map>#include<cstdio>#includ......
  • CSP-S 2024 第八次
    忘记写了，补一下A依次加入每个\(a_i\)，拿个大根堆维护当前以\(i\)结尾的和最大子段，和超过\(s\)了就弹堆顶直到和不超过\(s\)。不过好像出现了一些语文事故，先不管了。B倍增预处理出\(f_i\)表示\(i\)上方第一个大于\(a_i\)的点，询问\(u,v,c\)时，先倍增找到\(u\)上......
  • 信息学奥赛复赛复习10-CSP-J2020-03表达式求值-栈、后缀表达式、isdigit函数、c_str函
    PDF文档公众号回复关键字:202410031P7073[CSP-J2020]表达式[题目描述]小C热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种逻辑表达式中，所有操作数都是变量，且它们的取值只能为0或1，运算从左往右进行。如果表达式中有括号，则先计算括号内的子表达式的......
  • CSP 模拟 37
    Amedian如果保证每个数互不相同，直接统计每个序列中小于\(x\)和大于\(x\)的数量就好。但是有重复的数，答案会算重，考虑给每一个数一个独一无二的特征，保证满足大小关系，直接给所有数排个序后，记录排序后的位置即可。时间复杂度\(\mathcal{O}(n\logn)\)。Btravel当\(k\to\in......
  • 2024/10/2 CSP-S daimayuan模拟赛复盘
    2024/10/2CSP-Sdaimayuancontestlink(Day7)A.序列题面描述给你一个序列\(r_1,r_2,\dots,r_n\)，问有多少非负整数序列\(x_1,x_2,\dots,x_n\)满足：对于所有\(i\)，\(0\leqx_i\leqr_i\)。满足\(x_1|x_2|…|x_n=x_1+x_2+⋯+x_n\)，左边为二进制或。输出答案对......
  • CSP-J模拟赛补题报告
    前言最SB的一次&做的最差的一次T1：AC100pts......
  • 南沙C++信奥赛陈老师解一本通题 2099：【23CSPJ普及组】公路(road)
    ​ 2099：【23CSPJ普及组】公路(road)时间限制:1000ms      内存限制:524288KB提交数:3793   通过数: 1575【题目描述】小苞准备开着车沿着公路自驾。公路上一共有 nn 个站点，编号为从 11 到nn。其中站点 ii 与站点i+1i+1 的距离为vivi 公里。......
  • 2024/10/2 CSP-S模拟赛
    B好题。这题其实是原题，在大工VS辽实的T3里出现过，基本是一摸一样。对于观看这个题解呢，我的理解是把两个结合起来观看，分别是这个和这个，结合起来看的话无论是从感官还是从方便理解来看都很舒服。好了，接下来我们说一下这个题的思路。你考虑，你在一段长度为\(m\)的区间里至少要选......
  • 补题报告2
    背景2024-10-2上午打的比赛（CSP-J模拟2），作赛后总结报告。下棋（\(chess\)）赛时AC。概述高星\(x\)中星\(y\)低星\(z\)\(3\timesz=y\)\(3\timesy=x\)阵容强度：\(18\timesx+3\timesy+z\)求转换完后强度的顺序思路１.将能转的低星英雄转高星２.结构体排序输出......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99