首页 > 代码库 > 寒假训练5解题报告
寒假训练5解题报告
1.HDU 1114 Piggy Bank
一道简单的背包问题
#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define ll long longconst int N = 10005;const int INF = 0x3f3f3f3f;int dp[N];int main(){ // freopen("a.in" , "r" , stdin); int T; scanf("%d" , &T); while(T--) { int E , F; scanf("%d%d" , &E , &F); int M = F-E; int n,v,w; scanf("%d" , &n); memset(dp , 0x3f , sizeof(dp)); dp[0]=0; for(int i=0 ; i<n ; i++){ scanf("%d%d" , &v , &w); for(int j=w ; j<=M ; j++){ dp[j] = min(dp[j] , dp[j-w]+v); } } if(dp[M]<INF) printf("The minimum amount of money in the piggy-bank is %d.\n" , dp[M]); else puts("This is impossible."); } return 0;}
2.CodeForces 236C LCM
n为奇数时，必然最大的lcm就是n*(n-1)*(n-2)
n为偶数时，判断一下lcm(n,n-1,n-3)还是(n-1)*(n-2)*(n-3)大
或者只要判断n是否为3的倍数，如果是那么n,n-3有约数，那么肯定是后者最小公倍数大
#include <iostream>#include <cstdio>using namespace std;#define ll long longint main(){ ll n ; while(scanf("%I64d" , &n) == 1) { if(n<=2){ printf("%I64d\n" , n); continue; } ll a,b,c; ll ans=0; if(n % 2==0){ if(n%3 != 0) ans = n*(n-1)*(n-3); n--; } a=n,b=n-1,c=n-2; ans = max(ans , a*b*c); printf("%I64d\n",ans); } return 0;}
3.CodeForces 231C maximum number of times
这里数据量比较大，不能暴力来
先从小到大排个序
再记录一个前缀和，用来方便计算一部分数变成a[i]所需要的加的次数
用两个指针 l ， r 分别表示最左端和最右端，如果这一段可以全转化为 a[r] ， 那么r++ ， 否则 l++
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define ll long longconst int N = 100005;ll sum[N] , a[N];int cnt , minn;bool ok(int l,int r , ll k){ ll time = a[r]*(ll)(r-l+1)-(sum[r]-sum[l-1]); if(time<=k){ if(cnt < r-l+1) cnt = r-l+1,minn=a[r]; return true; } return false;}int main(){ // freopen("a.in" , "r" , stdin); ll n,k; while(scanf("%I64d%I64d" , &n , &k) == 2) { for(int i=1 ; i<=n ; i++) { scanf("%I64d" , a+i); } if(n==1){ printf("%d %I64d\n" , 1 , a[1]); continue; } sort(a+1 , a+n+1); for(int i=1 ; i<=n ; i++) { sum[i] = sum[i-1] + a[i]; } cnt=1 , minn=a[1]; int l=1 , r=2; while(1){ if(ok(l,r,k)) r++; else l++; if(r>n) break; } printf("%d %d\n" , cnt , minn); } return 0;}
4.POJ 3254 Fields
一道简单的状态压缩dp
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define ll long longconst int N = 15;const int M = 1<<13;const int MOD = 100000000;int dp[N][M];int a[N][M] , state[N];void dfs(int i , int v , int u , int k , int val){ if(k<0){ dp[i][u] += val; dp[i][u]%=MOD; return; } if(!(v&(1<<k)) && state[i]&(1<<k)) dfs(i , v , u|(1<<k) , k-2 , val); dfs(i , v , u , k-1 , val);}int main(){ // freopen("a.in" , "r" , stdin); int n,m; while(scanf("%d%d" , &n , &m) == 2) { memset(dp , 0 , sizeof(dp)); for(int i=1 ; i<=n ; i++) { state[i]=0; for(int j=1 ; j<=m ;j ++){ scanf("%d" , &a[i][j]); state[i]<<=1; state[i]+=a[i][j]; } } dp[0][0] = 1; for(int i=1 ; i<=n ; i++){ for(int j=0 ; j<(1<<m) ; j++){ if(dp[i-1][j]) dfs(i , j , 0 , m-1 , dp[i-1][j]); } } int ans = 0; for(int u=0 ; u<(1<<m) ; u++) { ans += dp[n][u]; ans%=MOD; } printf("%d\n" , ans); } return 0;}
寒假训练5解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。