855学习记录算法刷题$Day$-$5$——炎泽汐$de$ Blog

求和

---

     因式分解加前缀和；

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M = 200010;
int a[M], n;
ll pre[M], ans;

int main(){
    memset(pre, 0, sizeof(pre));
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll ans = 0;
    int i;
    cin >> n;
    for(i = 1;i <= n;i++){
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    for(i = 1;i <= n - 1;i++){
        ans += a[i] * (pre[n] - pre[i]);
    }
    cout << ans;
    return 0;
}

导弹拦截

---

      最长不上升子序列和最长不上升子序列的最少数量，最少数量用 set 维护；

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis));

using namespace std;

int a[500001], dp[500001], l[500001];

set<int> sy;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    mem(dp, 0);
    mem(a, 0);
    mem(l, 0);
	
    int n = 0, ans1 = 1, x;
	
    while(cin>>x) a[++n]=x;
	
    dp[1] = 1;
    l[1] = a[1];
	
    for(int i = 2; i <= n; i++){
        dp[i] = 1;
        if(a[i] <= l[ans1]){
            dp[i] = ++ans1;
        }else{
            int j = upper_bound(l + 1, l + ans1 + 1, a[i], greater<int>()) - l;
            dp[i] = j;
        }
		
        l[dp[i]] = a[i];
		
        auto it = sy.lower_bound(a[i]);
        if(it == sy.end()){
            sy.insert(a[i]);
        }else{
            sy.erase(it);
            sy.insert(a[i]);
        }
    }
	
    cout << ans1 << endl << sy.size();
	
    return 0;
}

upper_bound 返回的是第一个大于给定值的元素的位置。

lower_bound 返回的是第一个不小于给定值的元素的位置。

传球游戏

---

     模拟链，状态为第 i 次传球传给 j 的方案数；

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis)); 

using namespace std;

int dp[31][31];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
    mem(dp, 0);
	
    int n, m;
	
    cin >> n >> m;
	
    dp[1][n] = 1;
    dp[1][2] = 1;
	
    for(int i = 2; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(j == 1){
                dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][n];
            }else if(j == n){
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][1];
            }else{
                dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][j - 1];
            }
        }
    }
	
    cout << dp[m][1] << endl;
	
    return 0;
}

借教室

---

      差分数组维护前 x 人每天需要的总教室数，然后依次判断有没有哪天超过可借数量，判断是否可行；然后二分答案找到第一个不满足订单；

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis)); 

using namespace std;

ll a[1000011], diff[1000011];
int d[1000011], s[1000011], t[1000011];
int n, m;

int search(int x){
    mem(diff, 0);
    for(int i = 1; i <= x; i++){
        diff[s[i]] += d[i];
        diff[t[i] + 1] -= d[i];
    }
    ll tag = 0;
    for(int i = 1; i <= n; i++){
        tag += diff[i];
        if(tag > a[i]){
            return -1;
        }
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
    cin >> n >> m;
	
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
	
    for(int i = 1; i <= m; i++){
        cin >> d[i] >> s[i] >> t[i];
    }
	
    int ans = search(m);
	
    cout << ans << endl;
	
    if(ans != 0){
        int l = 1, r = m, mid = 0;
        while(l < r){
            mid = (l + r) >> 1;
            if(search(mid) == 0){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        cout << l;
    }
	
    return 0;
}

守望者的逃离

---

     贪心，有魔法就魔法，没魔法看等 CD 和跑步哪个赚，最后看能跑多远；

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis));

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
    int m, s, t, l = 0, r, p;
	
    cin >> m >> s >> t;
	
    r = s;
	
    int w = 0;
	
    for(int i = 1;i <= t; i++){
        if(m >= 10){
            m -= 10;
            l += 60;
        }else{
            p = 10 - m;
            r = (p % 4) == 0 ? (p / 4) + 1 : (p / 4) + 2;
            if(t - i + 1 >= r && s - l > 17 * r){
                m += 4;
            }else{
                l += 17;
            }
        }
        if(l >= s){
            cout << "Yes" << endl << i;
            break;
        }
    }
	
    if(l < s){
        cout << "No" << endl << l;
    }
	
    return 0;
}