ABC056

[ABC056C] Go Home

题面翻译

在0秒的时候有一只袋鼠在左右无限长的数轴上的原点上。在i-1到i的时间内，袋鼠可以选择不动，也可以向任意方向跳i个单位长度。也就是说，如果袋鼠在坐标x，时间i-1到i的时候，可以存在x-i,x,x+i三点之中。袋鼠的家在坐标X。袋鼠想尽快移动到它家。求袋鼠到达家的时间的最小值。

输入格式：

输入由标准输入以下列格式给出：$X$

输出：

袋鼠到达坐标的最早时间

题目描述

無限に左右に伸びている数直線上の $0$ の地点に時刻 $0$ にカンガルーがいます。 カンガルーは時刻 $i-1$ から $i$ にかけて、なにもしないか、もしくは長さがちょうど $i$ のジャンプを、左右どちらかの方向を選んで行えます。 つまり、時刻 $i-1$ に座標 $x$ にいたとすると、時刻 $i$ には $x-i$, $x$, $x+i$ のどれかに存在することが出来ます。 カンガルーの家は座標 $X$ にあります。カンガルーはできるだけ早く座標 $X$ まで移動しようとしています。 カンガルーが座標 $X$ に到着する時刻の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$X$

输出格式

カンガルーが座標 $X$ に到着する時刻の最小値を出力せよ。

样例 #1

样例输入 #1

6

样例输出 #1

3

样例 #2

样例输入 #2

2

样例输出 #2

2

样例 #3

样例输入 #3

11

样例输出 #3

5

提示

制約

• $X$ は整数
• $1\leqq X\leqq {10}^9$

Sample Explanation 1

$3$ 回右にジャンプすると時刻 $3$ に家にたどり着けて、これが最小です。

Sample Explanation 2

時刻 $0$ にはなにもせず、時刻 $1$ に右にジャンプすることで時刻 $2$ に家にたどり着けます。

思路

可以发现，一直往前跳，肯定跳得是最多的，所以我们采取贪心想法，一直跳，直到超过范围即可结束。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e3+10;
const int mod=1e9+7;
const int INF=1e9;
int main(){
    ios::sync_with_stdio(false);
    int n;cin>>n;
    //ans记录的是时间
    ll ans=0;
    //i记录的是跳过的路程
    for(int i=0;i<n;i++){
        i+=ans++;
    }
    cout<<ans;
    return 0;
}

[ABC056D] No Need

题面翻译

给出一个由 $N$ 个整数构成的集合和一个整数 $K$，若该集合中的的非空子集和大于等于 $K$，则称该子集为优秀的集合

若所有包含这个数的优秀子集去掉该数后仍然是优秀集合，则称该数字为“可有可无的数字”。

请求出在 $N$ 个数中“可有可无的数字”个数。

题目描述

シカのAtCoDeerくんは正整数が書かれたカードを $N$ 枚持っています。$i(1\leqq i\leqq N)$ 枚目に書かれている数は $a_i$ です。 AtCoDeerくんは大きい数が好きなので、カードに書かれた数の総和が $K$ 以上になるようなカードの部分集合をよい集合と呼びます。

そして、各カード $i$ に対して、そのカードが不必要かどうかを次のように判定します。

• 「カード $i$ を含む任意のよい集合に対して、その集合からカード $i$ を除いたものもよい集合」 ならカード $i$ は不必要
• それ以外の場合は、不必要でない

不必要なカードの枚数を求めてください。ただし、それぞれの判定は独立に行われ、不必要だからと言ってカードが途中で捨てられたりすることはありません。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $a_1$ $a_2$ ... $a_N$

输出格式

不必要なカードの枚数を出力せよ。

样例 #1

样例输入 #1

3 6
1 4 3

样例输出 #1

1

样例 #2

样例输入 #2

5 400
3 1 4 1 5

样例输出 #2

5

样例 #3

样例输入 #3

6 20
10 4 3 10 25 2

样例输出 #3

3

提示

制約

• 入力は全て整数
• $1\leqq N\leqq 5000$
• $1\leqq K\leqq 5000$
• $1\leqq a_i\leqq {10}^9(1\leqq i\leqq N)$

部分点

• $N,K\leqq 400$ を満たすデータセットに正解した場合は、部分点として $300$ 点が与えられる。

Sample Explanation 1

よい集合は {$ 2,3 \(} と {\) 1,2,3 $\text{Extra close brace or missing open brace}$ 1 $\mathrm{を}\mathrm{含}\mathrm{む}\mathrm{よ}\mathrm{い}\mathrm{集}\mathrm{合}\mathrm{は}\$1,2,3\$\mathrm{し}\mathrm{か}\mathrm{な}\mathrm{く}、\mathrm{こ}\mathrm{れ}\mathrm{か}\mathrm{ら}$ 1 $\mathrm{を}\mathrm{取}\mathrm{り}\mathrm{除}\mathrm{い}\mathrm{た}\$2,3\$\mathrm{も}\mathrm{よ}\mathrm{い}\mathrm{集}\mathrm{合}\mathrm{な}\mathrm{の}\mathrm{で}、\mathrm{カ}\mathrm{ー}\mathrm{ド}$ 1 $\mathrm{は}\mathrm{不}\mathrm{必}\mathrm{要}\mathrm{で}\mathrm{す}。\mathrm{ま}\mathrm{た}、\mathrm{よ}\mathrm{い}\mathrm{集}\mathrm{合}\mathrm{で}\mathrm{あ}\mathrm{る}\$2,3\$\mathrm{か}\mathrm{ら}$ 2 $\mathrm{を}\mathrm{取}\mathrm{り}\mathrm{除}\mathrm{い}\mathrm{た}\mathrm{集}\mathrm{合}\$3\$\mathrm{は}\mathrm{よ}\mathrm{い}\mathrm{集}\mathrm{合}\mathrm{で}\mathrm{は}\mathrm{な}\mathrm{い}\mathrm{た}\mathrm{め}、\mathrm{カ}\mathrm{ー}\mathrm{ド}$ 2 $\mathrm{は}\mathrm{不}\mathrm{必}\mathrm{要}\mathrm{で}\mathrm{は}\mathrm{あ}\mathrm{り}\mathrm{ま}\mathrm{せ}\mathrm{ん}。\mathrm{カ}\mathrm{ー}\mathrm{ド}$ 3 $\mathrm{も}\mathrm{同}\mathrm{様}\mathrm{に}\mathrm{不}\mathrm{必}\mathrm{要}\mathrm{で}\mathrm{は}\mathrm{な}\mathrm{い}\mathrm{た}\mathrm{め}、\mathrm{答}\mathrm{え}\mathrm{は}$ 1 $ です。

Sample Explanation 2

この場合よい集合は存在しないため、全てのカードは不必要となります。

思路

直接算可有可无的，似乎有点困难，所以算那些是必须的。不难想到，只要一个数本身大于$k$，那么他就是必须的，所以可以先排个序，那些大于$k$的数肯定不是可有可无的。

接下来就是进行判断了：怎么判断一个数是不是必须的呢？我们不妨假设$x$是必须的，那么设原有的和为$sum$，则$sum<k$且$sum+x\ge k$必成立。

那么我们不妨枚举一下$sum$，然后进行判断（可以用$DP$解决）。

设$dp[i]$表示的是当总和为$i$时，是否符合大于$k$，$0$表示不合法，$1$表示合法。并对此进行状态转移，具体看看代码。

思路参考自：[题解 AT2346【ARC070B] No Need】 - 洛谷专栏 (luogu.com.cn)

​ [题解 ABC056D] No Need - 洛谷专栏 (luogu.com.cn)

题解区还有一些有趣的写法：[AT_arc070_b ABC056D] No Need - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e11;
int n,k;
ll a[MAXN];
bool dp[MAXN];
bool cmp(ll a,ll b){
    return a>b;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n,cmp);
    int cnt=0;
    
    //注意初始化
    dp[0]=1;
    
    for(int i=1;i<=n;i++){
        //a[i]>=k，更新答案
        if(a[i]>=k)cnt=i;
        
        //枚举不合法的总和，并枚举对应可能的a[i]
        for(int j=k-1;j>=0;j--){
            //如果dp[j]合法且j+a[i]>=k,说明i不是必须的
            if(dp[j]&&j+a[i]>=k)cnt=i;
            //如果dp[j]是合法的，则dp[j+a[i]]也是合法的
            else if(dp[j])dp[j+a[i]]=1;
        }
    }
    cout<<n-cnt;
    return 0;
}