2019牛客多校第一场补题笔记

题目链接

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
/* L是输出端,然后s是辅助数组,c是源数组 */
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;

/* L是输出端,然后s是辅助数组,c是源数组 */
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;
// ans = n-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

题目要求36E,而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;
}
点击查看

本文标题:2019牛客多校第一场补题笔记

文章作者:单林敏

发布时间:2019年07月19日 - 15:28:02

最后更新:2019年10月17日 - 21:44:06

原始链接:https://www.wolfdan.cn/牛客多校第一场补题笔记/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------------本文结束 感谢您的阅读-------------------
0%