出栈序列

方法二：贪心

分析一波：

栈内为空时选择入栈。

待入栈元素为空时选择出栈。

即可入栈也能出栈时，应如何选择呢？题意要求得到最小字典序，即下一个出栈字符越小越好。

栈顶元素小于等于待入栈元素最小值，则出栈。

栈顶元素大于待入栈元素最小值，入栈。

程序实现：

预处理出后缀最小值，栈不为空并且还有元素未入栈，比较栈顶元素与待入栈元素最小值决定入栈还是出栈。

时间复杂度：O(n)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1E5 + 10; 

string s;
int n;
char a[MAXN]; 

int main(){
	cin >> n >> s;
	//预处理出后缀最小值
	a[n - 1] = s[n - 1];	
	for (int i = n - 2; i >= 0; --i)
		a[i] = min(s[i], a[i + 1]);
	//模拟贪心求解
	stack<char>stk;
	stk.push(s[0]);
	int inc = 1;//指向下一个入栈字符
	while (!stk.empty() || inc < n){
		if (stk.empty() || inc < n && stk.top() > a[inc]){
			stk.push(s[inc++]);
		} else{
			cout << stk.top();
			stk.pop();
		}
	}
	cout << endl;
	return 0;	
}

数对统计

如果直接暴力枚举，那么会T

这里考虑策略

不重复的数对数量
只要每个最后的数乘前面出现的不同数的数量就行了（包括前面的他自己）
再求个和

#include <bits/stdc++.h>
using namespace std;
int n,a[100010];long long c,ans;int v[100010];bool v2[100010];
int main(){
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = n;i > 0;i--){
		if(!v[a[i]]) v[a[i]] = i;
	}
	for(int i = 1;i <= n;i++){
		if(v[a[i]] == i) ans += c; 
		if(!v2[a[i]]) v2[a[i]] = 1,c++;
	}
	cout << ans;
    return 0;
}

加与乘

对于每个+ 和 * 进行维护 ， 统计每次加上需要进行的*次数

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010
#define ll long long
const int d=1e9+7;
int n,q,a[MAXN],b[MAXN];
char op[MAXN];
ll ans[MAXN],g=1;//当前已经被乘上多少了
int main(){
	cin>>n>>q;
	for(int i=1;i<=q;++i){
		cin>>op[i];
		if(op[i]=='+')
			cin>>a[i]>>b[i];
		else
			cin>>b[i];
	}for(int i=q;i>=1;--i){
		if(op[i]=='+')
			ans[a[i]]=(ans[a[i]]+b[i]*g%d)%d;//加法运算,去掉取模即为(ans[a[i]]+b[i]*g)，ans为被运算的数组
		else
			g=g*b[i]%d;//乘法对g操作
	}for(int i=1;i<=n;++i)
		cout<<ans[i]<<" ";
	cout<<endl;
	return 0;
}

点菜

树形背包的原题了。

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int x(0), f(1);
    char c = getchar();

    while (c < '0' || c > '9')
        f = c == '-' ? -1 : 1, c = getchar();

    while (c <= '9' && c >= '0')
        x = x * 10 + c - 48, c = getchar();

    return x * f;
}
const int N = 50010;
int n, W, w[N], v[N];
vector<int>G[N];
void add(int x, int y) {
    G[x].push_back(y);
}
vector<vector<int>>f;
//int f[5000][5000];
void dfs(int x, int dep) {
    for (auto y : G[x]) {
        for (int j = dep + w[y]; j <= W; j++)
            f[y][j] = f[x][j - w[y]] + v[y]; //转移向子树 y

        dfs(y, dep + w[y]);

        for (int j = dep + w[y]; j <= W; j++)
            f[x][j] = max(f[x][j], f[y][j]); //合并子树 y
    }
}
int main() {
    n = read(), W = read();
    f.resize(n + 1);

    for (int i = 0; i <= n; i++)
        f[i].resize(W + 1);

    for (int i = 1; i <= n; i++)
        add(read(), i);

    for (int i = 1; i <= n; i++)
        w[i] = read();

    for (int i = 1; i <= n; i++)
        v[i] = read();

    dfs(0, 0);
    printf("%d", f[0][W]);
    return 0;
}