526互联

AtCoder Beginner Contest 288(D,E,F)

发布时间 2023-05-31 19:17:36作者: righting

AtCoder Beginner Contest 288(D,E,F)

D(思维)

D

有一个数组，然后有\(q\)次询问，每一次输入一对\(l,r\),我们要判断这一段里面的数是不是好数组

好数组，在进行下面任意次操作后可以把这一段数字都变成\(0\),那么这就是个好数组

操作是选择一个\(i\)和一个\(c\),但是\(i+k-1\)要小于\(r\),我们会把\(i\)到\(i+k-1\)的数都加上\(c\)

这个正解感觉比较难想

我们把那些位置取模一样的加在一起，然后我们判断\(l,r\)这一段\(k\)个取模的结果的和都是一样的，那么就可以成为好数组，反之不然

这个可以这么来理解，可以假如只有一个长度为\(k\)的数组，我们只有这\(k\)个数都是一样的才可以，正好每一个位置都代表着不同的取模，就和上面的解法没有相悖的

至于证明，可以看这 博客

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=2e5+10;
const int mod=998244353;
int n,k;
int q;
int sum[maxn][14];
int a[maxn];
bool solve()
{
    int l,r;
    cin>>l>>r;
    int p=sum[r][0]-sum[l-1][0];
    for (int i=1;i<k;i++)
    {
        if(sum[r][i]-sum[l-1][i]!=p) return false;
    }
    return true;
}
signed main ()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        for (int j=0;j<k;j++)
        {
            sum[i][j]=sum[i-1][j];
        }
        sum[i][i%k]+=a[i];
    }
    cin>>q;
    while (q--)
    {
        if(solve())
        {
            cout<<"Yes\n";
        }
        else 
        {
            cout<<"No\n";
        }
    }
    system ("pause");
    return 0;
}

E(dp)

E

大意为一共有\(n\)个物品，每一个物品都有一个原来的价格，我们需要\(m\)个物品，而且，我们每次选择购买那一件物品还需要额外的费用，如果这个物品的编号在剩余还未售出的物品编号中排名为\(k\)，那么购买这一件物品的价值为原价加上\(c_k\)

问我们至少得到我们所需的\(m\)件物品的最少费用为多少

最开始想过是贪心，我找到最小的额外费用，然后把那些可以使用这个额外费用的加上去，但是可能我们还得加上那些不需要的，后来想了，不对，极端的想，万一，我所需要的还没有选择，但是因为每次先考虑较低的额外费用导致其他非必须的都购买了，显然不太可行

上面只是我的拙见

下面的解法是\(dp\)

\(dp[i] [j]\)代表从\(1\)到\(i\),我已经购买了\(j\)个物品

如果我还想要再购买一个物品的话，假设额外费用为\(add\),那么状态转移方程如下

\[dp[i][j+1]=dp[i-1][j]+val[i]+add \]

然后我们来分析\(add\)

如果只是我们购买\(i\)是在前面已经购买了\(j\)的情况下，那么在\(1\)到\(i\)剩下就只有\(i-j\)个了，而\(i\)一定是比前面的都大的，所以我们这次的额外费用为\(c_{i-j}\)了

这是我们购买\(i\)在就是在第\(j+1\)次购买，但是如果我们购买\(i\)在第\(j+1\)次购买之前，对比第\(j+1\)次购买的排名一定是更大的，那么我们可以知道\(i\)物品可能存在的额外费用所有比他坐标小于等于的\(c\)，但是那些什么时候可以取，最小的\(c\)的坐标取决于目前的\(j+1\),即它作为最新的一次购买

所以我们又可以得到一个状态转移方程

\[dp[i][j+1]=dp[i-1][j]+val[i]+min(add,c[i-j]) \]

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=2e5+10;
const int mod=998244353;
int n,m;
int val[maxn],add[maxn];
bool must[maxn];
signed main ()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        cin>>val[i];
        must[i]=false;
    }
    for (int i=1;i<=n;i++)
    {
        cin>>add[i];
    }
    for (int i=1;i<=m;i++)
    {
        int x;
        cin>>x;
        must[x]=true;
    }
    vector<int>dp(n+5,inf);
    dp[0]=0;
    for (int i=1;i<=n;i++)
    {
        vector<int>tmp(n+5,inf);
        int w=inf;
        for (int j=0;j<i;j++)
        {
            w=min(w,add[i-j]);
            tmp[j+1]=min(tmp[j+1],dp[j]+val[i]+w);
            if(!must[i])
            {
                tmp[j]=min(tmp[j],dp[j]);
            }
        }
        dp=tmp;
    }
    int ans=*min_element(dp.begin(),dp.end());
    cout<<ans<<"\n";
    system ("pause");
    return 0;
}

F(dp)

F

把一个字符串拆成若干个数，如可以把\(234\)拆成\(34\)和\(5\)这种，我们求的是把这个字符串拆成任可能的大小的数字的乘积

感觉做动态规划的题需要一步一步来

我们先什么都不考虑的话，就是直接暴力的求答案话，可以得到一个状态转移方程

\(f[i]\)是长度为\(i\)的字符串被拆后的乘积

\(dp[i]\)是前\(i\)个不同的拆分的乘积和

\(sum[i]\)是\(f[i]\)的前缀和

\(s[l] [r]\)是从\(l\)到\(r\)这一段形成的数字

\[dp[i]=\sum_{j=0}^{i-1}f[j]\times s[j+1][i] \]

但是我们不太可能去一一枚举\(j\)的，那么我们可以对\(dp\)进行前缀处理，但是\(s[j+1] [i]\)这个还是要一一枚举呀

然后我们可以试着变换一下，

\[dp[i+1]=\sum_{j=0}^{i}f[j] \times s[j+1][i+1] \]

再变化

\[dp[i+1]=\sum_{j=0}^{i}f[j] \times (s[j+1][i]\times10+s[i+1]) \]

发现只有一点不同，那就是累加的最右端，但是我们仔细想一下，在\(i\)的时候，不会出现那样的情况，那么它的贡献是不计的，那么我们也可以忽略。

所以可以再把括号去掉

\[dp[i+1]=10\times\sum_{j=0}^{i}f[j] \times s[j+1][i]+\sum_{j=0}^{i}f[j] \times s[i+1] \]

我们可以发现关系

\[dp[i+1]=10\times dp[i]+sum[i]\times s[i+1] \]

其实也可以理解为把前面所有的情况都往前挪一位，就一个个位给\(s[i]\)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=2e5+10;
const int mod=998244353;
int n;
string s;
int dp[maxn];
int sum[maxn];
signed main ()
{
    cin>>n;
    cin>>s;
    s=" "+s;
    dp[0]=0;
    sum[0]=1;
    for (int i=1;i<=n;i++)
    {
        int now=s[i]-'0';
        dp[i]=(dp[i-1]*10+sum[i-1]*now)%mod;
        sum[i]=(sum[i-1]+dp[i])%mod;
    }
    int ans=dp[n];
    cout<<ans<<"\n";
    system ("pause");
    return 0;
}