链表合并 + 走路 + 子串最大差(Day 3)

链表合并

#include
using namespace std;

#define x first
#define y second
#define rep(i,a,n) for (int i = a; i < n; i ++ )
#define repn(i,a,n) for (int i = a; i <= n; i ++ )
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
typedef long long ll;
typedef pair PII;

ll gcd(ll a,ll b) { return b ? gcd(b,a % b) : a; }
const int mod = 1e9+7;
const int N = 1e5 + 10, M = 2e5;
int e[M], ne[M], idx;
int h1, h2, n;


int main()
{
    IOS;
    cin >> h1 >> h2 >> n;
   for (int i = 0; i < n; i ++ )
    {
        int x;
        cin >> x;
        cin >> e[x] >> ne[x];
    }
    int cnt1, cnt2;
    cnt1 = cnt2 = 0;
    for (auto i = h1; ~i; i = ne[i])    cnt1 ++;
    for (auto i = h2; ~i; i = ne[i])    cnt2 ++;
    if(cnt1 < cnt2) swap(h1, h2);
    int last = -1;
    while(~h2)//将c->a->b 变成c<-a,last记录上一个位置
    {
        int temp = h2;
        h2 = ne[h2];//必须先取出下一个点的位置，因为后面ne会改变
        ne[temp] = last;
        last = temp;
    }
    //合并
    for (int i = h1, cnt = 1; ~i; i = ne[i], cnt ++)
    {
        if(cnt % 2 == 0 && ~last)//偶数且短的没到终点
        {
            int temp = last;
            last = ne[last];
            ne[temp] = ne[i];
            ne[i] = temp;
            i = ne[i];//提前跳到下一个位置,防止又计数
        }
    }
    for (int i = h1; ~i; i = ne[i])
    {
        if(~ne[i])  printf("%05d %d %05dn",i,e[i],ne[i]);
        else printf("%05d %d -1n",i,e[i]);
    }
    return 0;
}

走路

#include
using namespace std;

#define x first
#define y second
#define rep(i,a,n) for (int i = a; i < n; i ++ )
#define repn(i,a,n) for (int i = a; i <= n; i ++ )
#define pb push_back

typedef long long ll;
typedef pair PII;

ll gcd(ll a,ll b) { return b ? gcd(b,a % b) : a; }
int n, m;
const int N = 1e5 + 10;
int dp[110][N];//表示走了i步,能否走到j这个位置
//从上一个位置转移过来,f[i-1][j] = 1, 则f[i][j + a[i]] = 1......
int a[N], b[N];
//问的是走了n步，第n步能走到哪些位置
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )  cin >> a[i] >> b[i];

    dp[0][0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 0; j <= m; j ++ )
        {
            if(a[i] + j <= m && dp[i - 1][j])   dp[i][j + a[i]] = 1;
            if(b[i] + j <= m && dp[i - 1][j])   dp[i][j + b[i]] = 1;
        }
    }
    for (int i = 0; i <= m; i ++ )
        cout << dp[n][i];
    return 0;
}

 子串最大差(单调栈)

 可以这样思考，因为我们是要求出所有子串的max-min，可以看出这俩者无关。所以我们可以先求出子串的最大值之和，同理最小值之和，然后减一减就出来了。

那么如何求出所有最大值之和呢？

我们看一下每一个位置的数，是哪些子串的最大值就可以了，那么怎么确定这个子串的区间呢？

对于一个数，我们可以找到这个位置前面的比他大的第一个数，和后面的第一个大于等于他的数，那么这就是子串的区间了。（为什么要这样找，而不是两边都找最大的？因为比如1 4 1，第一个1最为最小值的时候会算一个1 4 1，第三个1最为最小值的时候也会算一个1 4 1。所以这样子会重复，那么我们就不妨左边找大的，右边找一个大于等于的即可）由于子串中必须包含当前位置，但是在前面可以有i - l[i]种选择，右边同理，所以一个位置的子串最大值之和就算出来了。同理再算最小值即可。

给出单调栈模板题 ​​​​​​​​​​​​单调栈

AC代码

#include
using namespace std;

#define x first
#define y second
#define rep(i,a,n) for (int i = a; i < n; i ++ )
#define repn(i,a,n) for (int i = a; i <= n; i ++ )
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
typedef long long ll;
typedef pair PII;

ll gcd(ll a,ll b) { return b ? gcd(b,a % b) : a; }
const int mod = 1e9+7;
const int N=1e6+10;
ll a[N];
int l[N], r[N];
int stk[N];//存储下标
int tt;

int main()
{
    IOS;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ )
    {
        while(tt && a[stk[tt]] <= a[i]) tt --;//找左边第一个比他大的 
        l[i] = stk[tt];
        stk[ ++ tt] = i;
    }
    tt = 0;
    for (int i = n; i; i -- )
    {
        while(tt && a[stk[tt]] < a[i]) tt --;找右边第一个大于等于他的，如果没有，那个位置就应该是n+1 
        if(tt) r[i] = stk[tt];
        else r[i] = n + 1;
        stk[ ++ tt] = i;
    }

    ll ansmax = 0;
    for (int i = 1; i <= n; i ++ )
        ansmax += a[i] * (i - l[i]) * (r[i] - i);

    tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        while(tt && a[stk[tt]] >= a[i]) tt --;
        l[i] = stk[tt];
        stk[ ++ tt] = i;
    }
    tt = 0;
    for (int i = n; i; i -- )
    {
        while(tt && a[stk[tt]] > a[i]) tt --;
        if(tt) r[i] = stk[tt];
        else r[i] = n + 1;
        stk[ ++ tt] = i;
    }

    ll ansmin = 0;
    for (int i = 1; i <= n; i ++ )
        ansmin += a[i] * (i - l[i]) * (r[i] - i);
    ll ans = ansmax - ansmin;
    cout << ans << endl;

    return 0;
}