当前位置：首页 > news >正文

爪哇部落算法组2024新生赛热身赛题解

news 2025/8/11 18:55:05

第一题（签到）：

1、题意：

2、题解:
我们观察到happynewyear的长度是12个字符，我们直接从前往后遍历0到n - 12的位置（这里索引从0开始），使用C++的substr()函数找到以i开头的长度为12的字符串是不是我们要的，如果是的话直接输出，注意输出时索引是从0开始。

3、代码：
#include <bits/stdc++.h> 
using namespace std; 
const int N = 1e5 + 10; 
int n; 
int main() {string s; cin >> n >> s;  for(int i = 0; i < n - 12; i ++ ) {string tmp = s.substr(i, 12); if(tmp == "happynewyear") {cout << i << endl; return 0; }}return 0; 
}

第二题（思维构造）:

1、题意：

2、题解：

对于任意数字%7的解集是 $\{ 0, 1, 2, 3, 4, 5, 6\}$ ，，操作2我们可以构造方案为 $\{2^0,2^1,2^2,2^3,2^4,2^5 \}$ 使得得到了7的倍数，当任意要构造0-6时，我们发现会多出几个空位出来，当余数为x时我们构造7-x, 显然 0 <= 7 - x <= 7，当我们先给7-x分配好了二进制位置，可以发现0-6都只占二进制位1个，2个，会剩下5个或者4个，我们只需要多次执行操作二凑出7的二进制的占位的个数的倍数(只需要按构造方案那样的思想造不同的二进制位)，就一定能构造出任意情况。

3、代码
#include <bits/stdc++.h> 
using namespace std; 
using ll = long long; 
ll n, m; 
ll a[N], s[N]; 
int main() {int T; cin >> T; while(T -- ) {string s; cin >> s; cout << "YES" << endl; }return 0; 
}

第三题（前缀和）：

1、题意：

2、题解：
维护好长度为n的前缀和，每次到达<= n - m + 1的位置我们直接对 $s[i + m - 1] - s[i - 1]$ 取Max即可
3、代码：


#include <bits/stdc++.h> 
using namespace std; 
using ll = long long; 
const int N = 2e5 + 10; 
ll n, m; 
ll a[N], s[N]; 
int main() {cin >> n >> m; ll ans = -1; for(int i = 1; i <= n; i ++ ) {cin >> a[i];s[i] = a[i] + s[i - 1]; }for(int i = 1; i <= n - m + 1; i ++ )ans = max(ans, s[i + m - 1] - s[i - 1]); cout<<ans<<endl;  return 0; 
}

第四题 (贪心 + 维护)：

1、题意：

2、题解：
我们先维护好"AB"的每个位置和"BA"的每个位置，都是第一个字符出现的位置，遍历"AB"位置，二分出左边离它最远的"BA"位置，判断一下这个位置是否是和它差>=3的长度，如果是就是合法的，再二分出右边离它最远的"BA"位置，判断一下这个位置是否和它差>=3长度, 如果是就说合法的。
3、代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10; 
int n, m;
void solve() {string s;cin >> s; n = s.size();vector<int> ab, ba; for(int i = 0; i < n - 1; i ++ ) {string tmp; tmp += s[i]; tmp += s[i + 1]; if(tmp == "AB") ab.push_back(i);if(tmp == "BA") ba.push_back(i);}bool flag = 0; for(int i = 0; i < ab.size(); i ++ ) {int x = ab[i], i1 = -1, i2 = -1;  int l = 0, r = ba.size() - 1; while(l < r) {int mid = l + r >> 1; if(ba[mid] < x - 1) r = mid; else l = mid + 1; }i1 = l;l = 0, r = ba.size() - 1; while(l < r) {int mid = l + r + 1 >> 1; if(ba[mid] > x + 1) l = mid; else r = mid - 1; }i2 = l;if(ba.size() && ba[i1] < x - 1) {flag = 1; break; }if(ba.size() && ba[i2] > x + 1) {flag = 1;break;  }}if(flag) puts("YES");else puts("NO"); 
}
int main() {int ts = 1;cin >> ts;while(ts --) solve();return 0;
}