2021牛客国庆集训派对day2 (A/D)

比赛传送门

传送门

题目描述

输入描述

输出描述

输入样例

3 3
3 3
1 4
1 5

输出样例

2
7
11

题目大意： 某直线上从 L 到 R 共有两种行动方式：一次前进 1m 或一次前进 k m，问共有几种不同的行动方式。

对着 3 , 3 样例思考了良久都想不通为什么是 2（渴望未来的我能解决该疑惑），因此本题思路可能具有误导作用，请谨慎观看。

由于无法模出样例，决定用类前缀和的方式进行求解，由坐标原点到该点处有以下状态转移方程（用0表示走，1表示跑）：

dp [ i ] [ 0 ] = ( dp [ i - 1 ] [ 0 ] + dp [ i - 1 ] [ 1 ] )；

dp [ i ] [ 1 ] = dp [ i - k ] [ 0 ] ；

仅有当 i >= k 时可以跑

参考代码

#include
using namespace std;
const int mod=1000000007;
int dp[100005][2];
int sum[100005];
int n,q,k,l,r;

void solve(){
    dp[0][0]=1;
    for(int i=1;i<=1e5;i++){
        dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;
        if(i>=k)
			dp[i][1]=dp[i-k][0]%mod;
    }
    for(int i=1;i<=1e5;i++)
        sum[i]=(sum[i-1]+dp[i][0]+dp[i][1]+mod)%mod;
}

int main(){
    cin>>q>>k;
    solve();
    while(q--){
        cin>>l>>r;
        printf("%dn",(sum[r]-sum[l-1]+mod)%mod);
    }
    return 0;
}

传送门

题目描述

输入描述

输出描述

输入样例

1
5
9 10 7 6 8

输出样例

3 4

题目大意： 现有一种全商店通用的物品，每个商店对该物品的收购/出售值相等且为 ai ，问顺序访问完所有商店后，能够获得的最大利润以及获得该利润需要的最小交易次数各为多少。

考虑单调性+反悔贪心（？）即可解决的问题，以下以样例 8 5 6 7 2 1 4 3 进行举例说明 ：

由最大利润和最小次数可知，最优解一定是在最低价买入最高价卖出，且由于每次只能够持有一个物品（或不持有物品），可用 flag 标记手上是否有货物，借此判断在进入下一个商店时的目的是买入还是卖出。

走到 8 时（以下均以商店的物品价格指代该商店），由于此时手上没有货物，即 flag = 0 ，标记如果现在买下最低价 min = 8，并继续往下贪；

走到 5 时，此时 flag = 0（未买入，具体见之后解释），标记如果现在买下最低价 min = 5，并继续往下贪；

走到 6 时，发现如果此时买下将大于先前购买的最低价，因此掉头（反悔，并不是真的掉头x）在 min = 5 处购买商品，并记下当前手中价值 now = 5，同时更改 flag = 1，并记现在卖出最高价 max = 6；

走到 7 时，此时 flag = 1，标记如果现在卖出最高价 max = 7，并继续往下贪；

走到 2 时，发现如果此时卖出将低于先前卖出的最高价，因此掉头在 max = 7 处卖出商品，利润 + =（ 7 - 5 ），同时更改 flag = 0 ，并记现在买下最低价 min = 2；

……

以上每次买入/卖出时都需要注意操作次数的累加，同时如果当走到最后一个店铺时手中有货且该店铺价值大于手中物品价值，则在该店卖出并增加操作次数和利润值。

参考代码

#include 
using namespace std;

const int N=1e5+10;
typedef long long ll;
ll a[N];

int main(){
    int t;
    cin>>t;
    while(t--){
        ll n,ans=0,maxx,minn,cnt=0,now;
        int flag=0;//0为手上无货 1为有货
        cin>>n;
        for(ll i=1;i<=n;i++)
            cin>>a[i];
        
        if(n==1){
            cout<<"0"<<" "<<"0"<=a[2]){
                cout<<"0"<<" "<<"0"<a[1]){
            cnt++;
            now=a[1];
            maxx=a[2];
            flag=1;
        }
        else{
            minn=a[2];
            flag=0;
        }
        for(ll i=3;i<=n;i++){
            if(flag==1&&a[i]=a[i-1]){//标记现在可行的最高卖出价为a[i]
                maxx=a[i];
                continue;
            }
            else if(flag==0&&a[i]<=a[i-1]){//标记现在可行的最低买入价为a[i]
                minn=a[i];
                continue;
            }
            else if(flag==0&&a[i]>a[i-1]){//在a[i-1]的价格买入 并标记现在最高卖出价为a[i]
                flag=1;
                now=a[i-1];
                maxx=a[i];
                cnt++;
                continue;
            }
        }
        if(flag==1&&a[n]>now){
            ans+=(a[n]-now);
            cnt++;
        }
        cout<