当前位置：首页 > news >正文

CSP-J模拟赛一补题报告

news 来源：原创 2024/10/1 18:37:22

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$ ，保证仅包含字符 0 或 1。

输出描述

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

输入样例

输出样例

样例解释

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

数据范围

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

$1 \leq n \leq 3$

对于另外 60% 数据：

$1 \leq n \leq 100$
$1 \leq n \leq 100$

对于全部数据：

$1 \leq n \leq 1000$

解析

$c n t$ 为找到的01交替子串长度， $s i z$ 为字符串长度
枚举子串的开头 $i$ ，结尾 $j$
$j$ 一定要从 $i$ 按顺序枚举到 $s i ze$
如果子串 $[i, j - 1]$ 不是01交替子串，子串 $[i, j]$ 必定也不是，此时直接break。
否则发现了一个新的01交替子串， $c n t + +$ 。
秒了
$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$ 个名为 $s_i$ 。

$s_0=1$
$s_1=10$
$s_2=1001$
$s_3=10010110$

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

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

多测。

输入描述

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

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

输出描述

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

输入样例

1
3

输出样例

数据范围

对于 10%的数据：

$x \leq 100$ 。

对于另外 50% 的数据：

$x≤10^7$ 。

对于全部数据：

$x≤10^9$ 。

思路

类似倍增
用 $x$ 依次尝试减去 $2^{32}$ 到 $2^0$
每次操作后， $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)$ 出发，目标是 $(n, m)$ ，只能向右或者向下走，但是你不能一次性往一个方向走大于等于 $k$ 步。

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

如果无解，输出No Answer!。

输入描述

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

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

输出描述

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

输入样例1

输出样例1

输入样例2

输出样例2

数据范围

被我吃了

思路

记忆化搜索
$i, j$ 为坐标， $s t e p$ 为向同一个方向走的步数， $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)$ 的矩形。

有一点 $A (a, b)$ ，保证 $A$ 在矩形内部或边界上，求以 $A$ 为圆心，半径为
$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;
}
/*********  ********
*          *       *
*          *       *
*********  *********  *       **  *       *
********   *********/
/*********  *       *   *******   ********    *********
*          *       *      *      *               *
*          *       *      *      *               *
*********  *********      *      ********        **  *       *      *      *               **  *       *      *      *               *
********   *       *   *******   *               **/