CSP-J Day 1 模拟赛补题报告

前言

考了我们班 Rank $1$。

本人在发烧状态下进行写作，勿喷。

分数

T1 alter: $Accepeted100$
T2 filp: $Accepeted100$
T3 square $Wrong\_answer60$
T4 round $Wrong\_answer40$

题解

T1

题面

思路

首先从下标 $i$ 开始，然后逐次判断是否与上一个相等（它具有单调性，如果到这里不行，那么后面一定不合法），如果不相等，答案加 $1$，否则跳出。

赛时 $Accepeted$ 代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool is(string s){
	int len=s.size(); 
	for(int i=1; i<len; i++){
		if(s[i]==s[i-1]){
			return false;
		}
	}
	return true;
}
int main(){
	freopen("alter.in","r",stdin);
	freopen("alter.out","w",stdout);
	string s;
	cin>>s;
	int kkk=s.size(),cnt=0;
	for(int i=0;i<kkk; i++){
		cnt++;
		for(int j=i+1; j<kkk; j++){
			if(s[j]==s[j-1]){
				break;
			}
			else{
				cnt++;
			}
		}
	}
	cout<<cnt;
	return 0;
} 

T2

题面

思路

我一开始不会，然后想到了二进制，发现他是一个满二叉树，如果这个位上的二进制是 $1$，那么答案翻转（一开始答案是 $1$），否则不变。

但是要注意一个点，$x$ 要 $-1$，可以使用 C++ 自带的 __builtin_popcount 进行统计，最后判断数量是否为偶数。

赛时代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	freopen("filp.in","r",stdin);
	freopen("filp.out","w",stdout);
	int T;
	cin>>T;
	while(T--){
		int x;
		cin>>x;
		x--;
		string s;
		for(int i=1; i<=31; i++) s+='0';
		int i=0;
		while(x){
			s[i++]=(char)('0'+x%2);
			x>>=1;
		}
		reverse(s.begin(),s.end());
		int k=10;
		for(int i=0;i<s.size(); i++){
			if(s[i]=='1'){
				if(k==10) k=1;
				else k=10;
			}
		}
		cout<<k/10;
		cout<<"\n";
	} 
	return 0;
}

赛后简化代码

#include<bits/stdc++.h>
int main(){
	int T,x;
	std::cin>>T;
	while(T--){
		std::cin>>x;
		std::cout<<(__builtin_popcount(x-1)%2==0)<<"\n";
	} 
}

T3

题面

思路

经典 dp 问题，就不实现过程了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 210;
ll dx[2] = {1, 0}, dy[2] = {0, 1};ll n, m, k, a[N][N], dp[N][N][N][2], ans = -1e18;
int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m >> k;
	for (ll i = 1; i <= n; i++)
		for (ll j = 1; j <= m; j++)
			cin >> a[i][j];
	memset(dp, -0x3f, sizeof(dp));dp[1][1][0][0] = dp[1][1][0][1] = a[1][1];
	for (ll x = 1; x <= n; x++)
		for (ll y = 1; y <= m; y++)
			for (ll l = 0; l < k; l++)
					for (ll d = 0; d <= 1; d++) {
					    if (dp[x][y][l][d] < -1e18)continue;for (ll nd = 0; nd <= 1; nd++) {
							ll nx = x + dx[nd], ny = y + dy[nd];
							if (nx < 1 || nx > n || ny < 1 || ny > m)continue;
							if (d != nd)
							dp[nx][ny][1][nd] = max(dp[nx][ny][1][nd], dp[x][y][l][d] + a[nx][ny]);
							else if (l < k - 1)
								dp[nx][ny][l + 1][nd] =max(dp[nx][ny][l + 1][nd], dp[x][y][l][d] +a[nx][ny]);
						}
					}
	for (ll l = 0; l < k; l++)
		for (ll d = 0; d <= 1; d++)
			ans = max(ans, dp[n][m][l][d]);
	if (ans == -1e18)
		cout << "No Answer!";
	else
		cout << ans;
	return 0;
}

T4

题面

思路

初中奥数。
首先，分成四块

然后覆盖的话，不难发现经过旋转后有这四种情况



然后前两种好计算，后两种我们拆开看。

第一种的话，就是 $n\times m$。
第二种的话，就是 $\frac{\pi r^2}{4}$
不难发现，第三种答案，就是 $\frac{\sqrt{r^2-m^2}\times m}{2}+\frac{r^2\times (\frac{\pi }{2}-\arccos (\frac{m}{r}))}{2}$
第四种答案的话，就是 $\frac{\sqrt{r^2-m^2}\times m}{2}+\frac{\sqrt{r^2-n^2}\times n}{2}+\frac{r^2\ast (\frac{\pi }{2}-\arccos (\frac{m}{r})-\arccos (\frac{n}{r}))}{2}$

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
double eps=1e-8;
const double pi=acos(-1);
double p(double n,double m,double r){
    if(n<m) swap(n,m);
    if(max(n,m)<eps||min(n,m)<eps) return 0;
    if(r>=sqrt(n*n+m*m)) return n*m;
    if(r<=n&&r<=m) return pi*r*r*0.25;
    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(){
    double n,m,a,b,r;
    cin>>n>>m>>a>>b>>r;
    printf("%.10lf",p(a,b,r)+p(n-a,b,r)+p(a,m-b,r)+p(n-a,m-b,r));
    return 0;
}