目录
一、得分情况
T1[交替出场（alter）]：100分
T2[翻翻转转（filp）]：60分
T3[方格取数（square）]：60分
T4[圆圆中的方方（round）]：20分
总分：120分
二、比赛概况
拿到题面后，先看了T1，5min 打出 O(n) 复杂度的DP代码，AC
再看T2，我看了样例之后就手推了后面的几个字符串，但是貌似推了半个小时推了个寂寞
T2没思路，切到T3，很像之前做过的 dp 方格取数，但是加了移动步数 k 的限制，
随后看了眼数据，前几个样例的数据都很小，直接 dfs 了 ，调了将近一个小时，最后发现是因为输入时没有输入 k qwq，改完也是拿了 60 分
T3打完部分分后回到T2，发现前几个样例依旧能做，于是按照题目描述搓了个模拟，拿到60分
T4直接开摆，看到数据范围有一句”对于测试点1，保证数据同样例。“
样例给的数据直接输出，拿到20分
三、题目分析
T1[交替出场（alter）]
题意：
给定一个字符串 ，定义每两个相邻字符都不同的字符串为 ”01交替串“
特殊的，任意长度为 1 的字符串也被定义为 01交替串
赛时思路&正解思路：
想到了夏令营做过的一道位运算dp ，尝试用 dp 解决问题
首先定义状态：
我们定义 dp[i] 表示以 i 为结尾的 01交替串 的个数 ，因为任意长度为 1 的字符串都是 01交替串 ，所以任意的 dp[i] 的初始值都为 1
状态转移方程：
不难发现 ，如果 s[0] ~ s[i-1] 为01交替串 , 那么 s[i] != s[0] 时，s[i] 即可拼接到任意以 s[i-1] 为结尾的 01 交替串后 ，组成若干个新的 01 交替串
那么我们就推出了状态转移方程： if ( s[i] != s[i-1] ) dp[i] += dp[i-1]
最后将所有的 dp[i] 累加即可得到答案
赛时代码&AC代码
#include<bits/stdc++.h>
using namespace std;
int main() {
//freopen("alter.in","r",stdin);
//freopen("alter.out","w",stdout);
int dp[1005],ans=0;
string s;
cin>>s;
for(int i=0;i<s.size();i++){
dp[i]=1;
if(i>0&&s[i]!=s[i-1]) dp[i]+=dp[i-1];
ans+=dp[i];
}
cout<<ans;
//fclose(stdin);
//fclose(stdout);
return 0;
}T2[翻翻转转（filp）]
题目大意
有一些字符串：
s0 = 1
s1 = 10
s2 = 1001
s3 = 10010110
s[i] 是 s[i-1] 逐位取反后拼接在 s[i-1] 后的串
求 s114514 的第 x 个字符
赛时思路
按照题意进行模拟，构造字符串，再输出相应位置的字符（期望得分：60）
正解思路：
列出每个位置是由哪个位置构造出来的，不难看出，每次将要开始进行取反操作时，当前的字符串下标都是 2^k ，
所以当询问第 x 个位置的值时 ，只需要找到与 x 最接近且比 x 小的 2^k ，由于 x 位置是由 x- 2^k 位置构造的 ，
所以 s[x] = ! s[x-2^k] ，第一个位置是 1 ，所以递归边界是 if(x==1) return 1 , 依次递归往前找 ，即可找到答案
注意 ！当 x == 2^k 时 ，此时的 x 位置是由 2^(k-1) 构造的 ，即 s[x] = s[2^(k-1)]
AC代码
#include<bits/stdc++.h>
using namespace std;
int fun(int x){
if(x==1) return 1;
int k=log2(x);
if((1<<k)==x)
return !fun(1<<(k-1));
else
return !fun(x-(1<<k));
}
int main() {
int t,n;
cin>>t;
while(t--){
cin>>n;
cout<<fun(n);
}
return 0;
}T3[方格取数（square）]
题目大意：
有一个 n*m 的矩阵 ，需要从 1,1 位置走到 n,m 位置，每走过一个格子都会收集当前格子上的值
只能向下或向右走 ，且相同方向走的次数不能大于等于 k
求收集到的数字的和的最大值
无解输出“No Answer!"
赛时思路：
相比于普通的方格取数，这道题增加了同方向步数的限制 ，dp 可能会很麻烦 ，所以我用DFS拿部分分
dfs( x , y , step , to , num )
对于每一次 dfs ，(x,y)表示当前点的坐标 ，to 表示从上一个格子走到 (x,y)的行进方向 ， step 表示当前方向走过的步数 ，num 表示当前收集的值
如果接下来行进的方向与走过来的方向(to)不一致，则将 step 清零，否则将 step+1 ，每次将 num += a[x][y] ，当x==n&&y==m时，更新答案 maxx=max(maxx,num);
赛时代码(暴搜）
#include<bits/stdc++.h>
using namespace std;
int n,m,k,maxx=-1000000000;
int dx[]={0,1};
int dy[]={1,0};
int a[205][205];
void dfs(int x,int y,int step,bool to,int now){
if(step>=k) return;
//cout<<x<<' '<<y<<' '<<step<<endl;
now+=a[x][y];
if(x==n&&y==m){
maxx=max(maxx,now);
return ;
}
int xx=dx[0]+x;
int yy=dy[0]+y;
//cout<<xx<<' '<<yy<<endl;
if(xx<=n&&yy<=m){
if(to==0){
dfs(xx,yy,step+1,0,now);
}
else{
dfs(xx,yy,1,0,now);
}
}
xx=dx[1]+x;
yy=dy[1]+y;
if(xx<=n&&yy<=m){
if(to==0) dfs(xx,yy,1,1,now);
else dfs(xx,yy,step+1,1,now);
}
}
int main() {
//freopen("square.in","r",stdin);
//freopen("square.out","w",stdout);
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
dfs(1,1,0,1,0);
if(maxx>0) cout<<maxx;
else cout<<"No Answer!";
//fclose(stdin);
//fclose(stdout);
return 0;
}
正解思路：
100%的数据中 n,m<=200，这种情况下 dfs 一定会超时 ，所以用 dp
用 dp[ i ][ j ][ 1/0 ] 来表示每一个状态 ，( i , j ) 表示当前坐标 ，
第三维 1 表示从左侧走到当前格子
0 表示从上方走到当前格子
分别假设当前格子 dp [ i ][ j ] 是由某个格子连续向下走到的或者是由某个格子连续向右走到的 ，
按照 k 的限制 ，两次for循环分别尝试每一种可能性，最后 max ( dp[n][m][1] , dp[n][m][0] )即为答案
注意判断无解的情况
正解代码：
#include<bits/stdc++.h>
using namespace std;
long long dp[205][205][3],n,m,k,a[205][205];
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
dp[i][j][1]=dp[i][j][0]=-1e18;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i==1&&j==1){
dp[i][j][1]=dp[i][j][0]=a[i][j];
continue;
}
long long sd=0,sr=0,md=-1e18,mr=-1e18;
for(int t=1;i-t>=1&&t<k;t++){
sd+=a[i-t+1][j];
md=max(md,dp[i-t][j][0]+sd);
}
dp[i][j][1]=md;
for(int t=1;j-t>=1&&t<k;t++){
sr+=a[i][j-t+1];
mr=max(mr,dp[i][j-t][1]+sr);
}
dp[i][j][0]=mr;
}
}
long long ans=max(dp[n][m][1],dp[n][m][0]);
if(ans<=-1e15){
cout<<"No Answer!";
}
else{
cout<<ans;
}
return 0;
}
............................................................................................................................................................................................................................................................................................................
T4[圆圆中的方方（round）]
题目大意
给定矩形的四个顶点的坐标及圆的圆心坐标和半径
求矩形与圆的相交面积
赛时思路：
没什么思路，直接输出样例拿到20分
正解思路：
把矩形分成四个部分：圆心左上 、圆心右上 、圆心左下 、圆心右下
分类讨论再累加求和
正解代码：
#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1),eps=1e-6;
double n,m,x,y,r;
double calc(double n,double m,double r){
if(n>m) swap(n,m);
if(n<eps||m<eps) return 0;
if(r<=n) return 0.25*pi*r*r;
else if(r<=m){
double tt=sqrt(r*r-n*n);
double res=n*tt/2.0;
double ang=pi/2-acos(n/r);
res+=ang/2*r*r;
return res;
}
else if(r<=sqrt(n*n+m*m)){
double t1=sqrt(r*r-n*n),t2=sqrt(r*r-m*m);
double res=n*t1/2.0 + m*t2/2.0;
double ang=pi/2-acos(n/r)-acos(m/r);
res+=ang/2*r*r;
return res;
}
return n*m;
}
int main() {
cin>>n>>m>>x>>y>>r;
cout<<fixed<<setprecision(10)<<calc(x,y,r)+calc(x,m-y,r)+calc(n-x,y,r)+calc(n-x,m-y,r);
return 0;
}四、反思
今天的成绩一般 ，第一题5分钟切掉了很正常，但是在写完T2T3的部分分后，应该不断尝试优化代码，争取得到更多的分数 ，
T4也不应该草草看眼样例就原样输出 ，根据特殊样例，完全可以再拿40分
以后模拟赛一定要沉住气 ，仔细阅读数据范围和题面 ，无法AC但也要尽量拿到所有能拿的部分分
扫一扫
1328
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
