比赛靠手机码代码真累QAQ
B-减成一
1）知识点
- 就是一道简单的动态规划。
2）看题目
- 就是你每次都可以让一个区间数字都-1，求最少几次全变1。
3）算法分析
- 一开始我以为不是连续区间，还直接就排个序来搞了。但是看到连续区间的时候我就发现这一定是个dp。
- 说到dp：动态规划最重要的就是递推和dp数组的含义。
- 首先我们讲一下dp数组的含义：这里重要的是数的位置。所以dp数组就是一个一维数组：dp[位置] = 最小次数。
- 然后是递推：
- 首先很简单，如果我们这一位比上一位要大，那么说明要比上一位要多操作x次（x为前后的差值）。
- 如果后面比前面小呢，就不用增加操作次数，因为可以在前面操作的时候就操作掉ta了。
- 就是这样，这是一道十分简单的动态规划。
4）算法操作
- 就先写一下dp数组的含义：
int dp[MAX];//dp[位置] = 最小次数 - 然后是我们的递推公式：
dp[0] = 0; info[0] = 1; for (int i = 1; i <= n; i++) { if (info[i] >= info[i - 1]) dp[i] = dp[i - 1] + info[i] - info[i - 1]; else dp[i] = dp[i - 1]; }
5）打代码
- 首先输入数据。
- 然后按照上面的dp就好了。
- 下面全代码~
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 1e5 + 7;
int info[MAX], dp[MAX];
int main() {
int T; cin >> T;
while (T--) {
int n; cin >> n;
for (int i = 1; i <= n; i++)
cin >> info[i];
dp[0] = 0; info[0] = 1;
for (int i = 1; i <= n; i++) {
if (info[i] >= info[i - 1])
dp[i] = dp[i - 1] + info[i] - info[i - 1];
else
dp[i] = dp[i - 1];
}
cout << dp[n] << endl;
}
return 0;
}
C-面积
啊这
签到题我懂的。
正方向是边长平方，圆是πr2就不用我说了吧。
py再见
AC代码
T = int(input())
for _ in range(T):
a = int(input())
r = a / 2
ans = a * a + 2 * 3.14 * r * r
print("%.2f" % ans)
E-赛马
1）知识点
这道题是二分，并且可以用STL简化代码。
2）看题目
题目的意思就是叫我们田忌赛马，求最大能赢的比赛。
3）算法分析
- 田忌赛马我们都懂，其实就是选择比对方的马大仅仅一号的马去比赛。
- 所以我们先把我们的马保存下来，然后排个序（这里阔以用STL的multiset，放入自动排序，但是会慢很多），就可以二分找答案了。
- 每次选比这个马大一号的就行了。
4）算法操作
- 我们用multiset保存数据（可自动排序）：
for(int i = 0 ; i < n ;++i){ int x; cin >> x; q.insert(x); } - 然后就可以去二分找答案啦：
int ans = 0; for(int i = 0 ; i < n ;++i){ int x; cin >> x; auto it = upper_bound(q.begin(), q.end(), x); if(it != q.end()){ ++ans; q.erase(it); } }
5）打代码
- 首先STL保存数据。
- 然后按上面二分找答案。
- 下面全代码~
AC代码
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
multiset<int> q;
int main(){
int T; cin >> T;
while(T--){
q.clear();
int n; cin >> n;
for(int i = 0 ; i < n ;++i){
int x; cin >> x;
q.insert(x);
}
int ans = 0;
for(int i = 0 ; i < n ;++i){
int x; cin >> x;
auto it = upper_bound(q.begin(), q.end(), x);
if(it != q.end()){
++ans;
q.erase(it);
}
}
cout << ans << endl;
}
}
F-三角形
1）知识点
- 递推，就是递推。
2）看题目
- 题目说就是把一个长度为a的可以最多分成几个棒子，使其全不可组成三角形。
3）算法分析
- 首先最小的是1，所以先裁出两个1，然后最小肯定两边之和，就是1 + 1。
- 同理往后，现在有1,1,2，下一个就要1 + 2。我们就看出了这就是个斐波那契。
4）算法操作
- 先初始化斐波那契数列，因为很大，开一个__int128：
for(int i = 3 ; i < 1005 ; ++i) fib[i] = fib[i-1]+fib[i-2];
- 就拿出来判断呗：
for(int i = 3 ; i < 1005 ;++i){ if(fib[i]-1 > a){ ans = i-3; break; } }
5）打代码
- 先初始化斐波那契序列。
- 然后遍历查找就好了。
- 下面全代码~
AC代码
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const int maxn = 100005;
__int128 fib[1005] = {0,1,1};
int main(){
js;
for(int i = 3 ; i < 1005 ; ++i)
fib[i] = fib[i-1]+fib[i-2];
int T; cin >> T;
while(T--){
ull a; cin >> a;
if(a < 3){
cout << a << endl;
continue;
}
ll ans;
for(int i = 3 ; i < 1005 ;++i){
if(fib[i]-1 > a){
ans = i-3;
break;
}
}
cout << ans << endl;
}
}
H-直线
啊这
你高中学过。
证明我就不证了。看我代码
AC代码
T = int(input()) for _ in range(T): n = int(input()) ans = n * (n - 1) // 2 print(ans)
J-最大值
1）知识点
- 就是kmp嘛
2）看题目
- 题目叫你找一个非前缀的最大的匹配串，可以和前缀最大匹配多长。
3）算法分析
- 其实就是个kmp都能看出来，但是怎么kmp呢？
- 我们kmp其实就是一个对着匹配串原串往后匹配的过程。
- 然后呢我们就可以把原串分为一个原串，一个非前缀串（就是原串去掉第一个字符）。
- 进行一遍匹配，在途中保存最大的匹配长度就好了。
4）算法操作
- 我们的next数组我相信大家都没有问题：
void getnext(char b[]) { int i, j, len = strlen(b); Next[0] = -1; for(i = 0, j = -1; i < len;) if(j == -1 || b[i] == b[j]){ ++i; ++j; if(b[i] != b[j]) Next[i] = j; else Next[i] = Next[j]; } else j = Next[j]; } - 然后kmp也就是正常匹配，也就是加了一个读最大值而已：
void kmp(char a[],char b[]) { getnext(b); int n = strlen(a); int len = strlen(b); for(int i = 0, j = 0; i < n && j < len;) { if(j == -1 || a[i] == b[j]) { i++, j++; } else j = Next[j], cnt = 0; ans = max(j, ans);//读取最大值 } }
5）打代码
- 先就是输入。
- 然后按上面kmp一下就好了
- 下面全代码~
AC代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const int maxn = 100005;
int cnt = 0, ans = 0;
int Next[maxn];
char a[maxn], b[maxn];
void getnext(char b[]) {
int i, j, len = strlen(b);
Next[0] = -1;
for(i = 0, j = -1; i < len;)
if(j == -1 || b[i] == b[j]){
++i; ++j;
if(b[i] != b[j]) Next[i] = j;
else Next[i] = Next[j];
}
else j = Next[j];
}
void kmp(char a[],char b[]) {
getnext(b);
int n = strlen(a);
int len = strlen(b);
for(int i = 0, j = 0; i < n && j < len;) {
if(j == -1 || a[i] == b[j]) {
i++, j++;
}
else j = Next[j], cnt = 0;
ans = max(j, ans);
}
}
int main() {
IOS;
int n; cin >> n;
while (n--) {
ans = 0;
cin >> b;
strcpy(a, b + 1);
kmp(a, b);
cout << ans << endl;
}
}
京公网安备 11010502036488号