AtCoder Beginner Contest 056(ABCD) Atcoder题解

AtCoder Beginner Contest 056(ABCD) A - HonestOrDishonest
【AtCoder Beginner Contest 056(ABCD)】思路：特判
B - NarrowRectanglesEasy
思路：讨论特判。
C - Go Home
思路：贪心，求和第一个大于等于 x x x的 i i i即为答案。
D - No Need
思路：考虑答案是排序后的某个前缀。
因为当 a [ i ] a[i] a[i]是 n e c e s s a r y necessary necessary时， x ≥ a [ i ] x\ge a[i] x≥a[i]都是 n e c e s s a r y necessary necessary
1.从 n n n开始 d p dp dp，若不存在 [ m a x ( k ? s u m , 0 ) , k ? 1 ] [max(k-sum,0),k-1] [max(k?sum,0),k?1]的数说明 [ 1 , i ] [1,i] [1,i]的数都可以不要。

#include using namespace std; typedef long long ll; const int N=5e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair #define fi first #define se second #define pb push_back #define il inline int a[N],dp[N],n,k; ll s; int main(){ scanf("%d%d",&n,&k); for(int i=1; i<=n; s+=a[i++]){ scanf("%d",&a[i]); if(a[i]>k) a[i]=k; }sort(a+1,a+n+1); dp[0]=1; for(int i=n; ~i; s-=a[i--]){ bool ok=1; for(int j=k-1; j>=max(k-s,0LL); j--) if(dp[j]){ ok=0; break; } if(ok){ printf("%d\n",i); break; } for(int j=k; j>=a[i]; j--) dp[j]|=dp[j-a[i]]; } return 0; }

2. b i t s e t + bitset+ bitset+二分，找到最小的 n e c e s s a r y necessary necessary数，答案就是 x ? 1 x-1 x?1。
具体来说就是对于其他 n ? 1 n-1 n?1个数组成的和存在 [ k ? a [ x ] , k ? 1 ] [k-a[x],k-1] [k?a[x],k?1]的数说明， a [ x ] a[x] a[x]是 n e c e s s a r y necessary necessary。

#include using namespace std; typedef long long ll; const int N=5e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair #define fi first #define se second #define pb push_back #define il inline int a[N],n,k; bitsets; bool check(int x){ if(a[x]>=k) return true; s.reset(); s[0]=1; for(int i=1; i<=n; i++) if(i!=x) s|=s<=k-a[x]; i--) if(s[i]) return true; return false; } int main(){ scanf("%d%d",&n,&k); for(int i=1; i<=n; i++) scanf("%d",&a[i]); sort(a+1,a+n+1); int l=1,r=n+1; while(l>1; if(check(mid)) r=mid; else l=mid+1; } printf("%d",l-1); return 0; }