题目链接
2019牛客多校第一场
A题
题解
知道了单调栈，那么第一题就很好解决了，就是两个串到每个位置都比较一下前面的最小值的下标是否相等(用单调栈来实现–后面讲)，如果相等则继续，如果都没有找到就是都是自己最小，也用单调栈处理成为相等，如果遇到不相等，那么i-1就是题目所要求出来的k的值
补充
![A+]()
单调栈
单调栈的一大优势就是线性的时间复杂度，所有的元素只会进栈一次，而且一旦出栈后就不会再进来了。
单调递增栈可以找到左起第一个比当前数字小的元素。比如数组 [2 1 4 6 5]，刚开始2入栈，数字1入栈的时候，发现栈顶元素2比较大，将2移出栈，此时1入栈。那么2和1都没左起比自身小的数字。然后数字4入栈的时候，栈顶元素1小于4，于是1就是4左起第一个小的数字。此时栈里有1和4，然后数字6入栈的时候，栈顶元素4小于6，于是4就是6左起第一个小的数字。此时栈里有1，4，6，然后数字5入栈的时候，栈顶元素6大于5，将6移除，此时新的栈顶元素4小于5，那么4就是5左起的第一个小的数字，最终栈内数字为 1，4，5。
1
2
3
4
5
6
7
8
9
10
11
|
void solve(int* c, int* L) {
int top = 0;
s[0] = node{0, 0};
for(int i = 1; i <= n; i++) {
while(top && s[top].val >= c[i]) top--;
L[i] = s[top].id;
s[++top] = node{i, c[i]};
}
}
|
参考链接:
https://www.cnblogs.com/grandyang/p/8887985.html
AC代码
代码是队友写的,orz
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 100000 + 5;
struct node { int id; int val; };
int a[maxn], b[maxn];
int l1[maxn], l2[maxn];
node s[maxn];
int n;
void solve(int* c, int* L) {
int top = 0;
s[0] = node{0, 0};
for(int i = 1; i <= n; i++) {
while(top && s[top].val >= c[i]) top--;
L[i] = s[top].id;
s[++top] = node{i, c[i]};
}
}
int main() {
while(~scanf("%d", &n)) {
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
solve(a, l1); solve(b, l2);
int ans = n;
for(int i = 1; i <= n; i++) {
if(l1[i] != l2[i]) {
ans = i-1;
break;
}
}
printf("%d\n", ans);
}
return 0;
}
|
B题
看到大佬的分析
C题，D题
能力有限，战略计划原因没有补这两题
C题解推荐
C题可以看大佬的题解
E题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN 2000
#define MOD 1000000007
int n,m;
int dp[MAXN+5][MAXN+5];
int main()
{
while(~scanf("%d%d",&n,&m)){
for(int i=0;i<=n+m;i++)
for(int j=0;j<=n+m;j++)
dp[i][j]=0;
dp[0][0]=1;
for(int i=0;i<=n+m;i++)
for(int j=0;j<=n+m;j++){
if(i+1<=j+n&&j<=i+m)
dp[i+1][j]=(dp[i+1][j]+dp[i][j])%MOD;
if(i<=j+n&&j+1<=i+m)
dp[i][j+1]=(dp[i][j+1]+dp[i][j])%MOD;
}
printf("%d\n",dp[n+m][n+m]);
}
}
|
F
图片以及思路转载+少量整理+感谢
借鉴两位大佬的思路和博文进行整理的，感谢
Izayoi_w
WAautomaton
![F1]()
![F2]()
题目要求36*E，而E = (22/36) * S，所以ans = 22 * S
关于三角形的面积，已知三个顶点坐标，我们可以用叉积来求，如ΔABC，S = (1/2) * ( 向量(AB) ✖ 向量(AC) )。
这里要注意，叉积有正有负，最终的答案为11倍叉积的绝对值。
![F3]()
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 100000 + 5;
int main() {
ll x1, y1, x2, y2, x3, y3;
while(cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3) {
ll res = 11*((x1-x2)*(y3-y2)-(y1-y2)*(x3-x2));
if(res < 0) res = -res;
cout << res << endl;
}
return 0;
}
|
G,H,I因己太菜先留坑
J
题解
解法一: 直接交叉相乘
解法二: 直接看出题人叉姐的解法
![]()
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <iostream>
#include <cstdio>
using namespace std;
typedef __int128 ll;
int main() {
long long x, a, y, b;
while (scanf("%lld %lld %lld %lld", &x, &a, &y, &b) != EOF) {
ll p = x; p *= b;
ll q = y; q *= a;
if (p > q) printf(">\n");
else if (p == q) printf("=\n");
else printf("<\n");
}
return 0;
}
|
