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≦X≦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≦i≦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≦N≦5000 $

$ 1≦K≦5000 $

$ 1≦a_i≦10^9 (1≦i≦N) $

部分点

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

Sample Explanation 1

よい集合は {$ 2,3 $} と {$ 1,2,3 $} の二つです。カード $ 1 $ を含むよい集合は {$ 1,2,3 $} しかなく、これから $ 1 $ を取り除いた {$ 2,3 $} もよい集合なので、カード $ 1 $ は不必要です。また、よい集合である {$ 2,3 $} から $ 2 $ を取り除いた集合 {$ 3 $} はよい集合ではないため、カード $ 2 $ は不必要ではありません。カード $ 3 $ も同様に不必要ではないため、答えは $ 1 $ です。

Sample Explanation 2

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

思路

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

接下来就是进行判断了：怎么判断一个数是不是必须的呢？我们不妨假设$x$是必须的，那么设原有的和为$sum$，则$sum<k$且$sum+x\geq 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;
}