class="superseo">链表合并
#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 %05d\n",i,e[i],ne[i]);
else printf("%05d %d -1\n",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;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)