首页 > 代码库 > CSU-ACM2014暑假集训基础组训练赛(1) 解题报告
CSU-ACM2014暑假集训基础组训练赛(1) 解题报告
•Problem A HDU 4450 水题，签到题
水题。。没啥好说的。给大家签到用的。
1 #include <cstdio> 2 int main(){ 3 int n,a,ans; 4 while(scanf("%d",&n),n){ 5 ans = 0; 6 for(int i = 0;i < n;i++){ 7 scanf("%d",&a); 8 ans += a*a; 9 }10 printf("%d\n",ans);11 }12 return 0;13 }
•Problem B Codeforces 230A 排序+贪心
题意：Kirito 要打n个怪兽，每个怪兽有两种属性(xi,yi)，xi代表怪兽的力量，yi代表击败怪兽后可以为Kirito自己增加的力量。
初始时， Kirito有s力量，只有当Kirito的当前力量s比怪兽的力量xi的时候， Kirito才能击败这只怪兽i，同时，他自己的力量还将增加yi
你可以按任意顺序挑战这些怪兽，问Kirito最终能否击败所有的n只怪兽。
将n只怪兽的力量x按升序排列
假设Kirito当前挑战了一只他可以战胜的怪兽，且这只怪兽的力量不是最小的，那么他一定可以战胜那只力量更小的怪兽。
并且如果他先战胜了那只力量更小的怪兽，他在挑战这只当前怪兽的时候可以有更大的力量。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 const int maxn = 1010; 5 struct Dragon{ 6 int x,y; 7 bool operator < (const Dragon &rhs) const{ 8 return x < rhs.x; 9 }10 }dragon[1010];11 12 int main(){13 int s,n;14 scanf("%d%d",&s,&n);15 for(int i = 0;i < n;i++){16 scanf("%d%d",&dragon[i].x,&dragon[i].y);17 }18 sort(dragon,dragon+n);19 bool flag = 1;20 for(int i = 0;i < n;i++){21 if(s <= dragon[i].x){22 flag = 0;23 break;24 }else{25 s += dragon[i].y;26 }27 }28 if(flag) puts("YES");29 else puts("NO");30 return 0;31 }
•Problem C POJ 3258 二分
题意：长为L(L<=10^9)的河上有N(N<=50,000)颗石头，除此之外，左岸和右岸还各有一块石头。它们在河上排成一条直线。每颗石头距离左岸石头的距离分别为Di。
现在让你拿走：除岸边2块石头外的任意M颗石头。你要使得剩下的石头（包括岸边的2块）它们之间的最短距离最大。
求这个最大的最短距离。
先将石头排序
最后的答案ans在[0,L]之间
二分答案ans
假设石头间的最短距离距离是ans，我们计算在该情况下需要拿走多少块(cnt)石头
如果cnt<=M 说明我们设定的最短距离可以更大
否则，我们设定的最短距离必须更小
O(NlogN)
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 const int maxn = 50010; 5 int a[maxn],L,N,M; 6 7 bool judge(int mid){ 8 int cnt = 0,last = 0; 9 for(int i = 1;i <= N;i++){10 if(a[i]-a[last] < mid){11 cnt++;12 }else{13 last = i;14 }15 }16 if(L - a[last] < mid) cnt++;17 return cnt <= M ? 1 : 0;18 }19 20 int main(){21 scanf("%d%d%d",&L,&N,&M);22 for(int i = 1;i <= N;i++){23 scanf("%d",&a[i]);24 }25 sort(a+1,a+N+1);26 int l = 0,r = L,ans = 0;27 while(l <= r){28 int mid = (l+r)>>1;29 if(judge(mid)) ans = mid,l = mid+1;30 else r = mid-1;31 }32 printf("%d\n",ans);33 return 0;34 }
•Problem D POJ 3984 BFS
我们在bfs的时候，需要边bfs边记录路径
具体的来说，就是bfs到下一个点的时候，要记录它是通过谁走到这个点的
输出的时候要从终点反向寻找路径，用数组保存起来
最后将记录结果的数组反向输出
1 #include <iostream> 2 #include <queue> 3 using namespace std; 4 5 const int dx[]={0, 1 ,0 ,-1} ; 6 const int dy[]={1, 0 ,-1 ,0} ; 7 int a[5][5] ,vis[5][5], fa[25], ans[25]; 8 9 int main()10 {11 for(int i=0;i<5;i++)12 for(int j=0;j<5;j++)13 cin>>a[i][j];14 queue<int>Q;15 Q.push(0) ;16 vis[0][0] = 1 ;17 while(!Q.empty()){18 int u = Q.front(); Q.pop() ;19 int x=u/5 , y = u%5;20 for(int d=0; d<4; d++){21 int nx = x + dx[d] , ny = y + dy[d];22 if(nx<0 || nx>=5 || ny<0 || ny>=5 || vis[nx][ny] || a[nx][ny]) continue ;23 int v = nx * 5 + ny ;24 vis[nx][ny] = 1 , fa[v] = u ;25 Q.push(v);26 }27 }28 int p = 24 , top = 0 ;29 while(true){30 ans[top++] = p ;31 if(p == 0) break;32 p = fa[p];33 }34 while(top>0) {35 --top ;36 cout<<"("<<ans[top]/5<<", "<<ans[top]%5<<")"<<endl;37 }38 return 0;39 }
•Problem E UVA 10036 DP
题意：给你N(1<=N<=10,000)个数字，你可以在它们之间的N-1个位置任意放“+”或“-”，放完之后，我们可以计算出表达式的值。
存不存在一种摆放方案使得最后表达式的值可以被K(1<=K<=100)整除
f[i][j]=1表示前i个数字形成的表达式的值除以K之后可以余j
f[0][0]=1
考虑第i个数字x,假设它是正的。
如果 f[i-1][j] = 1，说明前i-1个数字的表达式的值除以K可以余j
在x的前面放“+”， f[i][(j+x)%K] = 1
在x的前面放“-”，f[i][(j-x+K)%K]=1
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 int N,K; 7 bool f[2][100]; 8 9 int main()10 {11 int T ;12 scanf("%d",&T);13 while(T--) {14 scanf("%d%d" , &N ,&K) ;15 memset(f , false , sizeof(f)) ;16 f[0][0] = true ;17 int cur = 0 , x ;18 for(int i=1; i<=N; i++){19 cur ^= 1 ;20 memset(f[cur] , false , sizeof(f[cur])) ;21 scanf("%d" , &x);22 if(x<0) x = -x;23 x%=K;24 for(int u = 0; u<K; u++) if(f[cur^1][u]) {25 f[cur][(u+x)%K] = true;26 if(i>1) f[cur][(u-x+K)%K]=true;27 }28 }29 if(f[cur][0]) puts("Divisible") ;30 else puts("Not divisible") ;31 }32 return 0;33 }
•Problem F Codeforces 229D DP
题意：有n(1<=n<=5,000)座塔排在一条直线上，从左到右每个塔的高度分别为hi(1<=hi<=100,000)，每次操作你可以选择一座塔（假设是第i座），用吊车把它吊起来，然后放到与它相邻的一座塔上（可以是第i-1座也可以是第i+1座），这样，新塔的高度为两座塔的和，完成操作后，塔的总数减少一座。问最少需要多少次操作可以使得所有的塔从左到右形成一个非递减序列。
解法:
dp(i)表示对前i座塔进行操作后形成非递减序列所需要的最小操作步数
last(i)表示在dp(i)最小的前提下，第i座塔的最低高度。
易知，将[i,j]区间内的塔合并成一座需要j-i步
于是我们得到dp方程：dp(i)=max{dp(j)+i-j+1| j<i, h(j+1)+h(j+2)+...+h(i-1)+h(i) <= last(j)}
注意，我们在递推的过程中要同时记录、更新last(j)的值来确保得到最优解。
1 #include <cstdio> 2 int dp[5010],sum[5010],last[5010]; 3 int main() 4 { 5 int n; 6 scanf("%d",&n); 7 for(int i = 1;i <= n;i++){ 8 int a; 9 scanf("%d",&a);10 sum[i] = sum[i-1]+a;11 dp[i] = last[i] = 1<<30;12 }13 for(int i = 1;i <= n;i++){14 for(int j = 0;j < i;j++){15 if(sum[i]-sum[j] >= last[j] && dp[i] >= dp[j]+i-j-1){16 dp[i] = dp[j]+i-j-1;17 if(last[i] > sum[i]-sum[j]) last[i] = sum[i]-sum[j];18 }19 }20 }21 printf("%d\n",dp[n]);22 return 0;23 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。