首页 > 代码库 > CF 378(2) C D 模拟
CF 378(2) C D 模拟
CF 378(2) 好坑，有时间再做一遍
CodeForces 733C
题意：n只怪物，每只重ai，一开始有给定序列a[]。问最后是否能变到x只特定序列b[]，变化只能是相邻的大吃小。
题解：坑死人的题，，但不要怕去写这种题，在草稿纸上写好思路，一定要动手写。 思路：先把a[]根据b[]进行分段，再对每一段进行分析。细节太多，不自己动手写一遍根本体会不到。。
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define FF(i,a,b) for (int i=a;i<=b;i++)#define F(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 510;int n, k, a[N], b[N], L[N], R[N], ans1[N], ans2[N], tot;int main(){ scanf("%d", &n); FF(i,1,n) scanf("%d", &a[i]); scanf("%d", &k); int j, now=1; FF(i,1,k) { scanf("%d", &b[i]); int sum=0; for(j=now; j<=n; j++) { sum+=a[j]; if(sum==b[i]) { L[i]=now, R[i]=j, now=j+1; break; } if(sum>b[i]) { puts("NO"); return 0; } } } if(j!=n) { puts("NO"); return 0; } FF(i,1,k) { if(L[i]==R[i]) continue; int maxn=-INF, mi=-1, l; for(l=L[i]; l<=R[i]; l++) if(maxn<a[l]) { mi=-1; if(l-1>=L[i] && a[l-1]<a[l]) maxn=a[l], mi=l; if(l+1<=R[i] && a[l+1]<a[l]) maxn=a[l], mi=l; } if(mi==-1) { puts("NO"); return 0; } if(mi!=R[i] && a[mi]>a[mi+1]) { for(l=mi+1; l<=R[i]; l++) ans1[tot]=i-1+mi-L[i]+1, ans2[tot++]=1; for(l=mi-1; l>=L[i]; l--) ans1[tot]=i-1+l-L[i]+1+1, ans2[tot++]=-1; } else { ans1[tot]=i-1+mi-L[i]+1, ans2[tot++]=-1; for(l=mi+1; l<=R[i]; l++) ans1[tot]=i-1+mi-L[i]+1-1, ans2[tot++]=1; for(l=mi-2; l>=L[i]; l--) ans1[tot]=i-1+l-L[i]+1+1, ans2[tot++]=-1; } } puts("YES"); FF(i,0,tot-1) { char ch= ans2[i]==1 ? ‘R‘ : ‘L‘; printf("%d %c\n", ans1[i], ch); } return 0;}
CodeForces 733D
题意：n个长方体，可取一个，或取两个粘合，求可得最大球体的方案。
题解：这个D题，但更好做一点点。 注：还是要在草稿纸上写好思路，不要求快。 就是取最小的一条边，但两个粘合的情况要注意粘合后哪条是最小的边。
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define FF(i,a,b) for (int i=a;i<=b;i++)#define F(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define mp make_pairtypedef long long ll;const int N = 1e5+10;int n, x, y, z, m, mi, mj, maxn=-INF;map<pair<int ,int >, int>A, id;int main(){ scanf("%d", &n); FF(i,1,n) { scanf("%d%d%d", &x, &y, &z); int t1=x, t2=y, t3=z; x=min(t1, min(t2, t3)), z=max(t1, max(t2, t3)), y=t1+t2+t3-x-z; if(maxn<x) maxn=x, m=1, mi=i; if(A[mp(y,z)] && maxn< min(y, A[mp(y,z)]+x)) maxn=min(y, A[mp(y,z)]+x), mi=i, mj=id[mp(y,z)], m=2; if(A[mp(x,y)]<z) A[mp(x,y)]=z, id[mp(x,y)]=i; if(A[mp(x,z)]<y) A[mp(x,z)]=y, id[mp(x,z)]=i; if(A[mp(y,z)]<x) A[mp(y,z)]=x, id[mp(y,z)]=i; } if(m==1) printf("1\n%d\n", mi); else printf("2\n%d %d\n", mi, mj); return 0;}
CF 378(2) C D 模拟
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。