CF 1561 D. Up the Strip(数学+思维)

简介: 【7月更文挑战第5天】

链接

题意:

给出你长度为n的两个序列ab,从中找出子集S1,2,3,4,...n从中找子集然后要求

  • $max_{i∈S}ai>=\sum{i∈S}b_i$

对方案数取模与998244353

分析:

首先我们看数据范围是5000说明我们可以O(N2)
然后我们贪心的想先看Ai比较小的,这样在看大的就不用看MAX,

然后我们对其按照$Ai[b[i],a[i]]\sum{i∈S}b_i$ 是符合条件的。

然后我们知道最大值是5000,所以就又用到了背包的思想。状态转移。我们可以用dp[i]维护和为i的方案数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

#define x first
#define y second
#define sf scanf
#define pf printf
#define PI acos(-1)
#define inf 0x3f3f3f3f
#define lowbit(x) ((-x)&x)
#define mem(a,x) memset(a,x,sizeof(a))
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
#define debug(x) cout << #x << ": " << x << endl;

const int MOD = 998244353;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;  
const int dx[] = {
   0, 1, -1, 0, 0};
const int dy[] = {
   0, 0, 0, 1, -1};
const int dz[] = {
   1, -1, 0, 0, 0, 0 };
int day[] = {
   0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

struct node {
   
    ll x,y;
}q[maxn];
bool cmp(node a,node b){
   
    return a.x<b.x;
}
ll dp[maxn];
ll n;
void solve()
{
   
    cin>>n;
    for(int i=1;i<=n;i++)cin>>q[i].x;
    for(int i=1;i<=n;i++)cin>>q[i].y;

    sort(q+1,q+1+n,cmp);

    ll ans=0;
    dp[0]=1;
    for(int i=1;i<=n;i++){
   
        for(int j=q[i].y;j<=q[i].x;j++){
   
            ans=(ans+dp[j-q[i].y])%MOD;
        }
        for(int j=5000;j>=q[i].y;j--){
   
            dp[j]=(dp[j]+dp[j-q[i].y])%MOD;
        }
    }
    cout<<ans<<endl;
}   

int main()
{
   
    //init();
    ll t = 1;
    //scanf("%lld",&t);
    while(t--)
    {
   
        solve();
    }
    return 0;
}
AI 代码解读

链接

题意:

给出一个数n,两种操作,求将n变成1的方案数?对m取模

  1. 减去[1,n1]
  2. 除以[2,n]

分析:

我们看操作1,可以看出我们只与要维护前缀和即可,抛开操作1,不看我们只看操作2,

我们看除以[2,n1] 我看i,那些数除以2等于i2i,2i+1这两个数除以2等于i。然后我们看那些数除以3等于i.3i,3i+1,3i+2.依次类推,我们发现,i可以继承的一些数,呈块状。然后我们就可以找出继承谁的。

ll n,m;
ll sum[maxn],dp[maxn];
void solve()
{
   
    scanf("%lld%lld",&n,&m);
    dp[n]=1;///ans
    sum[n]=1;///qianzui
    for(ll i=n-1;i>=1;i--){
   
        dp[i]=(dp[i]+sum[i+1]) %m;
        for(ll j=2;j*i<=n;j++){
   
            ll r = min(n+1,i*j+j);
            dp[i]=(dp[i]+sum[i*j]-sum[r]+m)%m;
        }
        sum[i] = (sum[i]+sum[i+1]+dp[i])%m;///gengxindangqian sum
    }
    cout<<dp[1]<<endl;    
}
AI 代码解读
iamzfh
+关注
目录
打赏
0
10
10
0
48
分享
相关文章
|
8月前
CF 1538 G. Gift Set (贪心+思维)
【6月更文挑战第14天】
52 0
CF763A Timofey and a tree(思维)
CF763A Timofey and a tree(思维)
94 0
CF979B Treasure Hunt(贪心 思维)
CF979B Treasure Hunt(贪心 思维)
105 0
CF979B Treasure Hunt(贪心 思维)
CF1556D. Take a Guess(交互 性质)
CF1556D. Take a Guess(交互 性质)
102 0
CF1556D. Take a Guess(交互 性质)
CF817C.Really Big Numbers(二分 思维)
CF817C.Really Big Numbers(二分 思维)
80 0
CF1398C. Good Subarrays(思维 前缀和)
CF1398C. Good Subarrays(思维 前缀和)
120 0
CF76.E. Points (贡献 思维)
CF76.E. Points (贡献 思维)
79 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等