8.27下午

· · 个人记录

T1

签到题，简单dp，我的做法是三重循环一重循环天数，一重循环当天选择完成的任务，一重枚举上次可能做过的任务，然后用二维dp来存储每i天选择了第j个任务 状态转移方程：

if(j!=k) {
  dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i][j]);
}

最后边算边求最大值就行

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
int a[maxn][3];
int dp[maxn][3];
int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<3;j++) {
            cin>>a[i][j];
        }
    }
    int maxx=0;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<3;j++) {
            for(int k=0;k<3;k++) {
                if(j!=k) {
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i][j]);
                }
                maxx=max(maxx,dp[i][j]);
            }
        }
    }
    cout<<maxx;
    return 0;
}

T2

首先用一个队列存储原来的排序序列，然后因为栈有先进后出的特性，所以用栈来存储插队的人，然后弹出栈内东西加入新的存储答案的队列，标记进入过队列元素，最后将原本没有插队的放入存储答案的队列就行

#include<bits/stdc++.h>
using namespace std;
stack<int>op;
queue<int>Q;
queue<int>ans;
const int maxn = 1e5+7;
int vis[maxn];
int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        Q.push(i);
    }
    for(int i=1;i<=m;i++) {
        int a;
        cin>>a;
        op.push(a);
    }
    while(!op.empty()) {
        vis[op.top()]++;
        if(vis[op.top()]==1)
            ans.push(op.top());
        op.pop();
    }
    while(!Q.empty()) {
        if(vis[Q.front()]<1) {
            vis[Q.front()]++;
            ans.push(Q.front());
        }
        Q.pop();
    }
    while(!ans.empty()) {
        cout<<ans.front()<<'\n';
        ans.pop();
    }
    return 0;
}

T3

获得了k瓶汽水，说明在获得k瓶汽水之前，会有k-1个积分，可以兑换 \lfloor (k-1)/p \rfloor瓶汽水，然后通过画图，我们可以发现除了第一次兑换，后面要兑换一瓶汽水只要买(p-1)瓶汽水，也就是说可以凑出（k-1)/p组，每一组获得p瓶汽水要买(p-1)汽水，然后将总汽水数-1- \lfloor ((k-1)/p) \rfloor*p(就是不能凑成一组的汽水)加上就行
公式：

int num=(k-1)/p;
        cout<<1+num*(p-1)+k-1-num*(p)<<'\n';

T4

本题可以通过后面的减所以不能使用dp因为没有后效性
正解由于乘法运算可以达到log级别，但存在大量重复状态，于是我们可以使用记忆化搜索去除重复状态，然后让是2，3，5倍数的数可以直接从它除以2，3，5的因子达到然后再求最小值，而对于有余数的数，对于每一个数，我们都有两种方式
x - x%3的方式-x%3个1
x+3-x%3的方式+3-x%3个1 后面如法炮制即可

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int maxn = 1e18;
map<int,int>mp;
int n,a,b,c,d;
int dfs(int x) {
    if (mp.count(x)) {
        return mp[x];
    }
    int ans = x * d;
    if (x % 2) {
        ans = min(ans, min(dfs((x - x % 2) / 2), dfs((x + 2 - x % 2) / 2)) + a + d);
    } else {
        ans = min(ans, dfs(x / 2) + a);
    }
    if (x % 3) {
        ans = min(ans, min(dfs((x - x % 3) / 3) + (x % 3) * d, dfs((x + 3 - x % 3) / 3) + (3 - x % 3) * d) + b);
    } else {
        ans = min(ans, dfs(x / 3) + b);
    }

    if (x % 5) {
        ans = min(ans, min(dfs((x - x % 5) / 5) + (x % 5) * d, dfs((x + 5 - x % 5) / 5) + (5 - x % 5) * d) + c);
    } else {
        ans = min(ans, dfs(x / 5) + c);
    }
    mp[x] = ans;
    return ans;
}
signed main() {
    int t;
    cin>>t;
    while(t--) {
        cin>>n>>a>>b>>c>>d;
        mp.clear();
        mp[0]=0;
        mp[1]=d;
        cout<<dfs(n)<<'\n';
    }
    return 0;
}

T5

40pts

直接暴力枚举每一个区间算中间数

80pts

注意到当一个区间内大于x的数-小于x的数>=0，说明有中位数>=x，所以用前缀和来求出每个区间≥x的数的数量就行

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5+7;
int a[maxn],sum[maxn];
int n,x;
signed main() {
    cin>>n>>x;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        if(a[i]>=x) {
            a[i]=1;
        } else {
            a[i]=-1;
        }
        sum[i]=sum[i-1]+a[i];
    }
    int ans=0;
    for(int l=1;l<=n;l++) {
        for(int r=l;r<=n;r++) {
            if(sum[r]-sum[l-1]>=0) {
                ans++;
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

100pts

基于80pts做法，可以得出sum[r]>=sum[l-1];
此时发现问题可以转化成二维偏序的问题，所以可以用值域树状数组首先枚举r,然后找到<=其值的sum[l-1]的范围
要注意的是：
1：0<=l-1<=n-1,所以别忘记+0 2：有负数的情况，所以要增加一个偏移量
3：lowbit处理0会死循环，所以要让数位偏移 

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int maxn = 1e18;
map<int,int>mp;
int n,a,b,c,d;
int dfs(int x) {
    if (mp.count(x)) {
        return mp[x];
    }
    int ans = x * d;
    if (x % 2) {
        ans = min(ans, min(dfs((x - x % 2) / 2), dfs((x + 2 - x % 2) / 2)) + a + d);
    } else {
        ans = min(ans, dfs(x / 2) + a);
    }
    if (x % 3) {
        ans = min(ans, min(dfs((x - x % 3) / 3) + (x % 3) * d, dfs((x + 3 - x % 3) / 3) + (3 - x % 3) * d) + b);
    } else {
        ans = min(ans, dfs(x / 3) + b);
    }

    if (x % 5) {
        ans = min(ans, min(dfs((x - x % 5) / 5) + (x % 5) * d, dfs((x + 5 - x % 5) / 5) + (5 - x % 5) * d) + c);
    } else {
        ans = min(ans, dfs(x / 5) + c);
    }
    mp[x] = ans;
    return ans;
}
signed main() {
    int t;
    cin>>t;
    while(t--) {
        cin>>n>>a>>b>>c>>d;
        mp.clear();
        mp[0]=0;
        mp[1]=d;
        cout<<dfs(n)<<'\n';
    }
    return 0;
}