CSP-J模拟赛(1)补题报告

前言：

1.交替出场（alter) ：10

2.翻翻转转（filp)：0

3.方格取数（square）：0

4.圆圆中的方方（round)：0

总结一下：第一次考，没爆零就是胜利，下次注意一些小错误，争取AC第一题。目标50，先立个flag（本人菜的离谱）

1.交替出场

题意：

给你一个只包含01的字符串，求这个字符串中所有01交替字串的个数(单个字符也算）

考试回顾：

想出O(n^3)的暴力枚举，但没敢用，写了个半对不对的dp，得了10分。最后老师讲O(n^3)也能过（破防），总体花的时间太长了，没达到AC。

题解：

用dp枚举左端点，一位一位向右拓展。右端点最终是几，就有几个以ta结尾的子串。最后累加即可。

AC:

const int N = 1010;
int n, ans;
char s[N];
void main() {
scanf("%s", s + 1), n = strlen(s + 1);
for (int i = 1; i <= n; i++) {
ans++;
for(j, i + 1, n) if (s[j] + s[j - 1] == '0' + '1') ans++;
else break;
}
write(ans);
}

2.翻翻转转

题意：

子串si是si-1逐位取反后拼接在si-1之后的子串，现在s1为1，求s14514的第x个字符是什么。

考试回顾：

使用递归暴力，最后时间超限。（这我除了暴力想不出其他方法来了）

题解：

序列的构成非常有规律，前一半和后一半是互反的，可以考虑分治：如果答案处在前半段，继续递归下去，如果答案处在后半段，通过递归上来的答案取反后再上传即可。

AC：

#include<iostream>
#include<iomanip>
#include<cmath> 
#include<string>
#include<algorithm> 
#include<cstdio>
#include<queue>
#include<map>
#include<stack>
using namespace std;
int T,n;
int solve(int L,int R,int p){if(L==R) return p;int mid=L+R>>1;if(n<=mid) return solve(L,mid,p);return solve(mid+1,R,p^1);//取反
}
int main(){scanf("%d",&T);while(T--){scanf("%d",&n);printf("%d\n",solve(1,1<<30,1));}return 0;
}

3.方格取数

题意：

你从（1，1）出发，目标是（n,m），只能向右或向下走，走过一个格子累加那个格子里的数，但不能一次性往一个方向走大于等于k步（矩阵里不能有超过k个连续的格子），求累加的最大值。如果无解输出"No Answer!"。

考试回顾：

当时没想到dp，做了个矩阵dfs，没写完。（无解的特判输出能得30！悔不当初啊）

题解：

dp，搜索记忆化。求的是走过点的权值和，考虑限制，在状态转移时，需要有：当前坐标、步数限制、走的方向。如果走到不同方向，那么步限制清空（注意，这里要赋值为2）然后走到新点。
AC：

#include<iostream>
#include<iomanip>
#include<cmath> 
#include<string>
#include<algorithm> 
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<stack>
using namespace std; 
const int N=201;
int n,m,k,a[N][N];
int dx[]={0,1},dy[]={1,0};
pair<int,bool> f[N][N][N][2];
int dfs(int x,int y,int step,int d){//dfs搜索记忆化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(){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]);else printf("No Answer!");return 0;
}

4.圆圆中的方方

题意：

求一个四个边界点为（0，0），（n，0），（0，m），（n,m）的矩形与以A为圆心，r为半径的圆的重叠部分的面积。

考试回顾：

一看解析几何，（这我怎么做？）就放弃了。但是这道题输出样例是可以骗到分的（下次不要轻易弃题了）。

题解：

将相交的部分分成四个部分（见下图），几个部分公式如下：

1. return 0.25*pi*r*r;

2.sqrt(r*r-m*m)*m*0.5+0.5*r*r*(0.5*pi-acos(m/r)

3.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))

4.n*m

AC：

#include<iostream>
#include<iomanip>
#include<cmath> 
#include<string>
#include<algorithm> 
#include<cstdio>
#include<queue>
#include<map>
#include<stack>
using namespace std;
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(){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;
}