ACM日常训练日记——8.2

• 小训练

1. Kevin and Permutation
   题解很好不多说

#include<bits/stdc++.h>
using namespace std;
int T,n;
int main(){
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n/2;i++) cout<<i+n/2<<' '<<i<<' ';
		if(n%2==1) cout<<n<<' ';
		cout<<endl;
	}
}

总结就是遇到这类题自己找规律分析打表太弱了，不能专注认真去试，还是得多做多去冷静思考打表，去试

• codeforces(div2)

3. C. Even Positions
   一个简单的栈模拟一下就可以了，我当时也也想到了这道题的规律，但是没有敢交

//
#include <bits/stdc++.h>
using namespace std;

#define  int long long

const int MOD = 1e9 + 7;
int n;
char ans[300010];

vector<char> v1,v2;
int qpow(int a, int b, int m) {
    int result = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) {
            result = (result * a) % m;
        }
        a = (a * a) % m;
        b >>= 1;
    }
    return result;
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int ans=0;
        stack<int>sta;
        stack<int>s1;
        stack<int>s2;
        int n;
        cin>>n;
        for (int i = 0; i < n; ++i) {
            char c;
            cin>>c;
            if(c=='_'){
                if(!s2.empty()){
                    ans+=i-s2.top();
                    s2.pop();
                }else
                    sta.push(i);
            }else if(c==')'){
                if(!sta.empty()){
                    ans+=i-sta.top();
                    sta.pop();
                }else
                    s1.push(i);
            }else{
                s2.push(i);
            }
        }
        cout<<ans<<'\n';
    }
}

4. D. Maximize the Root
   讲的很好

#include <bits/stdc++.h>
using namespace std;

#define  int long long

const int MOD = 1e9 + 7;
char ans[300010];
int t,n;
long long a[200010];
vector<int> g[200010];

vector<char> v1,v2;
int qpow(int a, int b, int m) {
    int result = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) {
            result = (result * a) % m;
        }
        a = (a * a) % m;
        b >>= 1;
    }
    return result;
}

inline void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    vector<vector<int>> e(n + 1);
    for (int i = 2; i <= n; i ++ ) {
        int x; cin >> x;
        e[x].push_back(i);
    }
    function<void(int)> dfs = [&](int u) {
        for (int v : e[u]) dfs(v);
        if (e[u].empty()) return;
        if (u == 1) {
            int minv = 1e9 + 7;
            for (int v : e[1]) minv = min(minv, a[v]);
            a[1] += minv;
        }else {
            int minv = 1e9 + 7;
            for (int v : e[u]) minv = min(minv, a[v]);
            if (minv > a[u]) a[u] = (a[u] + minv) / 2;
            else a[u] = minv;
        }
    };
    dfs(1);
    cout << a[1] << endl;
    return;
}


int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>t;
    while(t--){
       solve();
    }
    return 0;
}