solve 4/11
Code:KK
Thinking :KK
用ans表示当前最优答案，maxx表示遍历到的最大数字，一开始ans肯定等于a[ 1 ]+a[ 2 ]，然后每次往后找，都把当前的a [ j ]拼到maxx后面，然后和答案比较，每次也更新maxx，时间复杂度o（n）
注意数据是1e19，会爆long long，用unsigned long long 就可以过。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #define CLR(a,b) memset(a,b,sizeof(a)); const int inf=0x3f3f3f3f; using namespace std; typedef unsigned long long ll; const int maxn= 6010; int T; int n; ll a[maxn],maxx,ans; int d[maxn]; void cut(int i,ll val){ d[i]=0; while(val>0) { val/=10; d[i]++; } if(d[i]==0)d[i]=1; } int main(){ cin>>T; int cat=1; while(T--) { cin>>n; for(int i=1;i<=n;i++) { //scanf("%lld",&a[i]); cin>>a[i]; cut(i,a[i]); } maxx=max(a[1],a[2]); ans=a[1]; int time=d[2]; while(time--){ ans*=10; } ans+=a[2]; for(int j=3;j<=n;j++) { ll temp=0; temp =maxx; time=d[j]; while(time--) { temp*=10; } temp+=a[j]; ans=max(ans,temp); maxx=max(maxx,a[j]); } printf("Case #%d: ",cat++); cout<<ans; printf(" "); } }
Code ：zz
Thinking：zz
题意：给出一串数（>=3），要求删除两个数，使得剩下的数拼接起来后最大。
删除的两个必然是长度最短的，先找出最短的数的长度，然后从前往后遍历数组，遇到长度最短的数就开始判断，如果发现拿走这个数后，总体的字典序是增加的，就去掉，并break;否则不去掉。如果长度最短的数至少有两个，那再进行一次上一步操作。在上两次操作中，如果有一次的操作进行了但却没有删除数，那就删掉数组最后面的长度最短的数。如果长度最短的数只有一个，那么进行类似第一步操作删除长度次短的数，如果没有删除数，那就删除数组最靠后的长度次短的数。
//#pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<string> #include<math.h> #include<cmath> #include<time.h> #include<map> #include<set> #include<vector> #include<queue> #include<algorithm> #include<numeric> #include<stack> #include<bitset> const int inf = 0x3f3f3f3f; using namespace std; typedef long long ll; struct s { long long num; int len; bool flag; }z[6010]; int c1[100010], cc[110]; int main(void) { //ios::sync_with_stdio(false); int T, n, i, N = 1, id, len, sum, id2, len2, cnt1, j, ss, k, cntcc; long long tmp, tmp1, tmp2, z1, z2; int zz, ttmp; scanf("%d", &T); while (T--) { scanf("%d", &n); id = -1; sum = 0; id2 = -1; cnt1 = 0; for (i = 0; i < n; i++) { scanf("%lld", &z[i].num); z[i].len = 0; z[i].flag = true; tmp = z[i].num; cntcc = 0; while (tmp) { cc[cntcc++] = tmp % 10; tmp /= 10; z[i].len++; } for (j = z[i].len - 1; j >= 0; j--) { c1[cnt1++] = cc[j]; } if (id == -1) { id = i; len = z[i].len; sum = 1; } else if (len > z[i].len) { len = z[i].len; id = i; sum = 1; } else if (len == z[i].len) { sum++; } } if (sum == 1) { for (i = 0; i < n; i++) { if (len != z[i].len) { if (id2 == -1) { id2 = i; len2 = z[i].len; } else if (len2 > z[i].len) { id2 = i; len2 = z[i].len; } } } } ss = 2; z1 = 0; for (i = 0; i < n - 1 && ss > 1; i++) { z1 += z[i].len; if (z[i].len == len) { z2 = z1; for (j = i + 1; j < n; j++) { z2 += z[j].len; if (z[j].flag) { break; } } zz = 0; for (k = 0;; k++) { if (z1 - z[i].len + k > cnt1 || z2 - z[j].len + k > cnt1) { break; } if (c1[z1 - z[i].len + k] > c1[z2 - z[j].len + k]) { zz = 1; break; } if (c1[z1 - z[i].len + k] < c1[z2 - z[j].len + k]) { zz = 2; break; } } if (zz == 2) { z[i].flag = false; ss--; } } } z1 = 0; for (i = 0; i < n - 1 && ss; i++) { z1 += z[i].len; if (z[i].len == len && z[i].flag) { z2 = z1; for (j = i + 1; j < n; j++) { z2 += z[j].len; if (z[j].flag) { break; } } zz = 0; for (k = 0;; k++) { if (z1 - z[i].len + k > cnt1 || z2 - z[j].len + k > cnt1) { break; } if (c1[z1 - z[i].len + k] > c1[z2 - z[j].len + k]) { zz = 1; break; } if (c1[z1 - z[i].len + k] < c1[z2 - z[j].len + k]) { zz = 2; break; } } if (zz == 2) { z[i].flag = false; ss--; } } } sum -= (2 - ss); for (i = n - 1; i >= 0 && sum > 0 && ss; i--) { if (z[i].flag && z[i].len == len) { z[i].flag = false; ss--; sum--; } } z1 = 0; for (i = 0; i < n - 1 && ss; i++) { z1 += z[i].len; if (z[i].len == len2 && z[i].flag) { z2 = z1; for (j = i + 1; j < n; j++) { z2 += z[j].len; if (z[j].flag) { break; } } zz = 0; for (k = 0;; k++) { if (z1 - z[i].len + k > cnt1 || z2 - z[j].len + k > cnt1) { break; } if (c1[z1 - z[i].len + k] > c1[z2 - z[j].len + k]) { zz = 1; break; } if (c1[z1 - z[i].len + k] < c1[z2 - z[j].len + k]) { zz = 2; break; } } if (zz == 2) { z[i].flag = false; ss--; } } } if (ss) { for (i = n - 1; i >= 0; i--) { if (z[i].flag && z[i].len == len2) { z[i].flag = false; ss--; } if (ss == 0) { break; } } } printf("Case #%d: ", N++); for (i = 0; i < n; i++) { if (z[i].flag) { printf("%lld", z[i].num); } } printf(" "); } return 0; }
Code：KK zz
Thinking：KK
板子题，记住求球交的板子真的只能处理两个球相交的情况，然后小学数学处理一下各种球关系就好了（然而比赛时脑子打结，小学数学卡了了一下）
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #define CLR(a,b) memset(a,b,sizeof(a)); const int inf=0x3f3f3f3f; using namespace std; const double PI = acos(-1.0); typedef unsigned long long ll; const int maxn= 110; typedef struct point { double x,y,z; point() { } point(double a, double b,double c) { x = a; y = b; z = c; } point operator -(const point &b)const { //返回减去后的新点 return point(x - b.x, y - b.y,z-b.z); } point operator +(const point &b)const { //返回加上后的新点 return point(x + b.x, y + b.y,z+b.z); } //数乘计算 point operator *(const double &k)const { //返回相乘后的新点 return point(x * k, y * k,z*k); } point operator /(const double &k)const { //返回相除后的新点 return point(x / k, y / k,z/k); } double operator *(const point &b)const { //点乘 return x*b.x + y*b.y+z*b.z; } }point; double dist(point p1, point p2) { //返回平面上两点距离 return sqrt((p1 - p2)*(p1 - p2)); } typedef struct sphere {//球 double r; point centre; }sphere; sphere s,a[maxn]; void SphereInterVS(sphere a, sphere b,double &v,double &s) { double d = dist(a.centre, b.centre);//球心距 double t = (d*d + a.r*a.r - b.r*b.r) / (2.0 * d);// double h = sqrt((a.r*a.r) - (t*t)) * 2;//h1=h2，球冠的高 double angle_a = 2 * acos((a.r*a.r + d*d - b.r*b.r) / (2.0 * a.r*d)); //余弦公式计算r1对应圆心角，弧度 double angle_b = 2 * acos((b.r*b.r + d*d - a.r*a.r) / (2.0 * b.r*d)); //余弦公式计算r2对应圆心角，弧度 double l1 = ((a.r*a.r - b.r*b.r) / d + d) / 2; double l2 = d - l1; double x1 = a.r - l1, x2 = b.r - l2;//分别为两个球缺的高度 double v1 = PI*x1*x1*(a.r - x1 / 3);//相交部分r1圆所对应的球缺部分体积 double v2 = PI*x2*x2*(b.r - x2 / 3);//相交部分r2圆所对应的球缺部分体积 v = v1 + v2;//相交部分体积 double s1 = PI*a.r*x1; //r1对应球冠表面积 double s2 = PI*a.r*x2; //r2对应球冠表面积 s = 4 * PI*(a.r*a.r + b.r*b.r) - s1 - s2;//剩余部分表面积 } int T,n; double x,y,z,r; int cas=1; int main(){ cin>>T; while(T--) { cin>>n; for(int i=1;i<=n;i++) { scanf("%lf%lf%lf%lf",&x,&y,&z,&a[i].r); a[i].centre={x,y,z}; } scanf("%lf%lf%lf%lf",&x,&y,&z,&r); s.r=r; s.centre={x,y,z}; double ans=0,v=0; for(int i=1;i<=n;i++) { double ss,dis=dist(s.centre,a[i].centre); //double if(dis>=s.r+a[i].r)continue; if(dist(s.centre,a[i].centre) + min(s.r,a[i].r) <= max(s.r,a[i].r)) { ans += 4.0 / 3.0 * PI * min(s.r,a[i].r) * min(s.r,a[i].r) * min(s.r,a[i].r); continue; } SphereInterVS(s, a[i],v,ss); ans+=v; } printf("Case #%d: %.14f ",cas++,ans); } }
Code：pai爷 zz
Thinking ：pai爷
时间复杂度为O(C(12,3)*C(9,3)*C(6,3)/24*T)
先预处理出所有的分割情况总共有369600种，之后去重24种，暴力判断。（用set去重或者hash，map去重待补）
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<set> using namespace std; int p[401000][15],a[20],w[20],t,n,l,zc=0; int check(int a,int b,int c) { if(a+b>c&&a+c>b&&b+c>a) return 1; return 0; } struct s { int c[15]; bool operator < (const s &rhs) const { for(int i = 1;i <= 12;i++) { if(c[i] != rhs.c[i]) { return c[i] < rhs.c[i]; } } return 0; } }aa; set<s>st; set<s>::iterator it; void solve() { int i,j,k,l; st.clear(); // printf("zc %d ",zc); for(k = 1;k <= zc;k++) { for(i = 10;i >0 ;i -= 3) { for(j = 1;j <= i-3;j += 3) { if(p[k][j] > p[k][j + 3]) { int temp[5]; for(l = 1;l <= 3;l++) { temp[l] = p[k][j + l - 1]; } for(l = 1;l <= 3;l++) { p[k][j + l - 1] = p[k][j + 3 + l - 1]; } for(l = 1;l <= 3;l++) { p[k][j + 3 + l - 1] = temp[l]; } } } } memcpy(aa.c,p[k],sizeof(p[k])); st.insert(aa); //printf("**** "); //zzz++; // printf(" size = %d ",st.size()); } //printf(" %d ",zzz); zc = 0; for(it = st.begin();it != st.end();it++) { zc++; //printf("111******************************** "); //(*it)->second; memcpy(p[zc],(*it).c,sizeof((*it).c)); } // printf("zc = %d ",zc); } int main() { /*for(int zzzz = 1;zzzz <= 12;zzzz++) { aa.c[zzzz] = zzzz; } st.insert(aa); //aa.c[1] = 2; st.insert(aa); printf("%d ",st.size());*/ scanf("%d",&t); for(int x1=1;x1<=10;x1++) for(int x2=x1+1;x2<=11;x2++) for(int x3=x2+1;x3<=12;x3++) for(int x4=1;x4<=7;x4++) for(int x5=x4+1;x5<=8;x5++) for(int x6=x5+1;x6<=9;x6++) for(int x7=1;x7<=4;x7++) for(int x8=x7+1;x8<=5;x8++) for(int x9=x8+1;x9<=6;x9++) { //printf("%d ",x9); for(int k=1;k<=12;k++) a[k]=0; l=0; p[++zc][++l]=x1;p[zc][++l]=x2;p[zc][++l]=x3; a[x1]=1;a[x2]=1;a[x3]=1; int sum=0; for(int k=1;k<=12;k++) if(a[k]==0) { sum++; if(sum==x4) p[zc][++l]=k,a[k]=1; if(sum==x5) p[zc][++l]=k,a[k]=1; if(sum==x6) p[zc][++l]=k,a[k]=1; } sum=0; for(int k=1;k<=12;k++) if(a[k]==0) { sum++; if(sum==x7) p[zc][++l]=k,a[k]=1; if(sum==x8) p[zc][++l]=k,a[k]=1; if(sum==x9) p[zc][++l]=k,a[k]=1; } for(int k=1;k<=12;k++) if(a[k]==0) p[zc][++l]=k; // for(int i=1;i<=12;i++) printf("%d ",p[zc][i]); // printf(" "); } solve(); int cas=0; while(t--) { int ans=0; for(int i=1;i<=12;i++) scanf("%d",&a[i]); for(int i=1;i<=zc;i++) { int sum=check(a[p[i][1]],a[p[i][2]],a[p[i][3]]) +check(a[p[i][4]],a[p[i][5]],a[p[i][6]]) +check(a[p[i][7]],a[p[i][8]],a[p[i][9]]) +check(a[p[i][10]],a[p[i][11]],a[p[i][12]]); if(sum>ans) { ans=sum; for(int j=1;j<=12;j++) w[j]=p[i][j]; if(ans==4) break; } } printf("Case #%d: %d ",++cas,ans); for(int i=1;i<=4;i++) { if(check(a[w[(i-1)*3+1]],a[w[(i-1)*3+2]],a[w[(i-1)*3+3]]))printf("%d %d %d ",a[w[(i-1)*3+1]],a[w[(i-1)*3+2]],a[w[(i-1)*3+3]]); } } }
赛后总结：
KK：比赛开局oj有点爆炸，oj好了之后读a题，基本是读完就想到了解法，但是没和队友说清楚，纠结了一段时间，然后数据范围被坑了一下，快速ac。队友此时接管电脑写B，我就在旁边看计算几何，等队友wa了我也差不多想好了计算几何怎么写，然后再判断球相交的地方脑残了一些，卡了一会，ac。后面先和zz交流B，提供了几种不能ac的想法，zzAC，又和pai爷交流K题关于如何去重的东西，一直没理解pai爷的需求是啥，所以没想到用set，后来帮zz看了一些set的一些bug，还有改正了冒泡排序的写法？今天打的主要还是有一点点交流问题吧，总体还行，其他题目都处于题目都看不懂的状态了。div2Rank3，吹一波队友，希望大家一起加油！for dream！
pai爷：今天的比赛状态还行吧，莽了一下，TLE了，之后想到了去重的方法，在队友的帮助下解决了这个问题，要多学STL知识。
zz：今天做的B题可以说是很自闭了，在想出思路后，觉得自己的想法没什么问题就开始写了，写完后测了几组数据，没什么问题就交了一发，果不其然，wa了，然后很快找出了一个bug，有交了一发，果不其然，有wa了。然后看了好久代码，想了好久，都觉得没什么问题，直到碰巧造出了一组样例，我的代码没跑过，然后就意识到了问题的严重性，有个地方出了问题，后来花了点时间，写了一半，kk叫我去写H题里的一个东西，写完以后H题A了，我有继续写B题，有些了大概十几分钟，B题A了。然后金老师让我写一个去重的东西，我大概过程想好了就开始写了，写完以后测了下数据，哦豁完蛋，写崩了，调了下后发现是重载的问题，后来发现冒泡写的有问题，弄了好久才过了这题。然后就一起和金老师数三角形，这题比南京的那个数三角形难了好多，时间也不够，就没写出来。这个故事告诉我们，写代码以前要想清楚，不能拍拍脑袋就开始写了，也要加强和队友的交流。