背景
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\):方向
方程：
- 方向一致且不超步数：
- 方向不一致：
代码
#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!";
else
cout << 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;
} else
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)<< endl;
return 0;
}