补题报告

背景

2024-10-1上午打的比赛(CSP-J模拟),作赛后总结报告。


交替出场(Alter)

赛时AC。

思路

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

我的代码
#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]); \]

  1. 方向不一致:

\[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!";
	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;
}

官方题解

请登录后发表评论

    没有回复内容