CSP-J模拟赛一补题报告

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 交替子串个数。

输入样例

0101

输出样例

10

样例解释

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

数据范围

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

$1\le n\le 3$

对于另外 60% 数据：

$1\le n\le 100$
$1\le n\le 100$

对于全部数据：

$1\le n\le 1000$

解析

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

输出样例

0

数据范围

对于 10%的数据：

$x\le 100$。

对于另外 50% 的数据：

$x\le 10^7$​​ 。

对于全部数据：

$x\le 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

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$为坐标，$step$为向同一个方向走的步数，$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;
}
/*
 ********  ********
*          *       *
*          *       *
*********  ********
        *  *       *
		*  *       *
********   ********

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

*/

思路

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