补题报告

背景

2024-10-1上午打的比赛（CSP-J模拟），作赛后总结报告。

---

交替出场(Alter)

赛时AC。

思路

１.先将结果数设为长度(默认每个长度为1的子串符合要求)　　
２.遍历每个子串，判断是否满足01交替串，是+1 　　
３.输出　　

我的代码

#include <iostream>
#include <string>
#include <cstring>
#include <string.h>
using namespace std;
string s;
int n;
int main() {
//	freopen("alter.in","r",stdin);
//	freopen("alter.out","w",stdout);cin >> s;int l = s.length();n = l;for(int i=0; i+1<l; ++i) {for(int j=i+1; j<l; ++j) {bool flag=0;for(int k=i+1; k<=j; ++k) {if(s[k] == s[k-1]) {flag=1;break;}}if(!flag) ++n;}}cout << n;
//	fclose(stdin);
//	fclose(stdout);return 0;
}

时间复杂度\(O(N^3)\)

---

正解

枚举左端点，一位一位向右扩展。

正解代码

#include <iostream>
using namespace std;
int cnt;
string s; 
int main(){cin >> s;s = ' ' + s;int l = s.size();for(int i=1;i<=l-1;++i){++cnt;for(int j=i+1;j<=l;++j){if(s[j] + s[j-1] == '0' + '1') ++cnt;else break;}}cout << cnt;return 0;
}

时间复杂度\(O(N^2)\)

---

翻翻转转(filp)

赛时TLE+WA(悲)

思路(我的)

1.根据\(S_5\)，推出\(S_n[k]\)由\(S_n[k-x]\)转化来 (x为最大的小于k的二的正整数次幂)
2.一步一步减,直到\(k=1/k=2\)
但 是 写 炸 了

我的代码

#include <bits/stdc++.h>
#define long long int
using namespace std;
int t;
int num[44];
string s[44];
bool q[3] = {0,1,0};int f(int a){int l = 1;int r = 31;while(l <= r){int mid = (l+r) >> 1;if(num[mid] <= a) l = mid + 1;else r = mid - 1;}return r;
}signed main() {
//	freopen("filp.in","r",stdin);
//	freopen("filp.out","w",stdout);for(int i=1;i<=30;++i)num[i] = pow(2,i);cin >> t;while(t--){int x;cin >> x;bool flag = 0;while(x != 1 && x != 2){int k = f(x); x -= num[k];flag = !flag;} cout << flag && q[x];} //	fclose(stdin);
//	fclose(stdout);return 0;
}

正解

观察，得每一个串从中间劈开，前后为取反关系
可考虑分治
判断：如果答案在前半段，继续递归。
如果答案在后半段，通过递归上来的答案取反后再上传即可。

正解代码

#include <iostream>
using namespace std;
int t,x;void f(int l,int r,int k){if(l == x && r == x) { cout << (k==1) << "\n";return ;}int mid = (l+r) >> 1;if(x <= mid) f(l,mid,k);else f(mid+1,r,~k);return ;
}int main(){cin >> t;while(t--){cin >> x;f(1,1<<30,1);//1<<30 ----> 2^30}return 0;
}

---

方格取数(square)

赛时10分(用dfs)
赛后讲解时发现没判边界(大悲)
加后60分
搜索一点要判边界！！！！！

思路（我的）

基础DFS+步数判断

10分(90分RE)代码

#include <bits/stdc++.h>
#define long long int
using namespace std;
const int maxn = 211;
int n,m,k;
int g[maxn][maxn];
int ans;
bool flag;
void dfs(int x,int y,int cnt,int sum,int p) {if(cnt >= k) return ;if(x == n && y == m) {flag = 1;ans = max(ans,sum+g[n][m]);return ;}if(p == 2) {dfs(x+1,y,cnt+1,sum+g[x][y],0);dfs(x,y+1,cnt+1,sum+g[x][y],1);}else if(p == 1){dfs(x+1,y,1,sum+g[x][y],0);dfs(x,y+1,cnt+1,sum+g[x][y],1);}else{dfs(x+1,y,cnt+1,sum+g[x][y],0);dfs(x,y+1,1,sum+g[x][y],1);}return ;
}
signed 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 >> g[i][j];dfs(1,1,0,0,2);if(flag) cout << ans;else cout << "No Answer!";//	fclose(stdin);
//	fclose(stdout);return 0;
}

60分(40分TLE)代码

#include <bits/stdc++.h>
#define long long int
using namespace std;
const int maxn = 211;
int n,m,k;
int g[maxn][maxn];
int ans;
bool flag;
void dfs(int x,int y,int cnt,int sum,int p) {if(cnt >= k) return ;if(x == n && y == m) {flag = 1;ans = max(ans,sum+g[n][m]);return ;}if(p == 2) {if(x+1>=1&&x+1<=n&&y>=1&&y<=m) dfs(x+1,y,cnt+1,sum+g[x][y],0);if(x>=1&&x<=n&&y+1>=1&&y+1<=m) dfs(x,y+1,cnt+1,sum+g[x][y],1);}else if(p == 1){if(x+1>=1&&x+1<=n&&y>=1&&y<=m) dfs(x+1,y,1,sum+g[x][y],0);if(x>=1&&x<=n&&y+1>=1&&y+1<=m) dfs(x,y+1,cnt+1,sum+g[x][y],1);}else{if(x+1>=1&&x+1<=n&&y>=1&&y<=m) dfs(x+1,y,cnt+1,sum+g[x][y],0);if(x>=1&&x<=n&&y+1>=1&&y+1<=m) dfs(x,y+1,1,sum+g[x][y],1);}return ;
}
signed 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 >> g[i][j];dfs(1,1,0,0,2);if(flag) cout << ans;else cout << "No Answer!";//	fclose(stdin);
//	fclose(stdout);return 0;
}

正解

\(DP\)
类似数字三角形
核心数组：\(dp[x][y][l][f]\)
\(x\):横坐标
\(y\):纵坐标
\(l\):步数
\(f\):方向

方程：

1. 方向一致且不超步数：

\[dp[nx][ny][l + 1][nd] =\max(本身, dp[x][y][l][d] +a[nx][ny]); \]

2. 方向不一致：

\[dp[nx][ny][1][nd] = \max(本身, dp[x][y][l][d] + a[nx][ny]); \]

代码

#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]);//查找不同步数不同方向到A[n][m]的最大值if (ans == -1e18)//未改变cout << "No Answer!";elsecout << ans;return 0;
}

---

圆圆中的方方(round)

思路

一个一个样例分析
\(Sub1\) 样例，送分
\(Sub2\) 由描述+勾股定理得矩形一定在圆内，重叠部分是矩形面积
\(Sub3\) 分析，得圆一定在矩形内，重叠部分是圆面积
\(Sub4∼6\) 正解思路
\(Sub7\) 分四种情况，两种正常，两种可用三角函数

#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;} elsereturn 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)<< endl;return 0;
}

官方题解