题目链接

2019牛客多校第一场

A题

题解

知道了单调栈，那么第一题就很好解决了，就是两个串到每个位置都比较一下前面的最小值的下标是否相等(用单调栈来实现--后面讲)，如果相等则继续，如果都没有找到就是都是自己最小，也用单调栈处理成为相等，如果遇到不相等，那么i-1就是题目所要求出来的k的值

补充

单调栈

单调栈的一大优势就是线性的时间复杂度，所有的元素只会进栈一次，而且一旦出栈后就不会再进来了。

单调递增栈可以找到左起第一个比当前数字小的元素。比如数组 [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。

/* 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

#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题

#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代码

#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代码

#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;
}