团体程序设计天梯赛——普及赛解题记录

居然有判断和单选......感觉挺有机试风格。判断选择从这里开始就有讲究了第一题是斐波那契数列234全是数据结构重点5是算法特性。T2T3T4分析全在这里了T5 ABC都可以确定是否有非连通图。大题从这里开始就不那么好做了。最重要的是要让整个程序读完到-1不可以中途截断不然剩下的数据会读进下一个数组。#includeiostream #define i64 long long using namespace std; i64 n,t,a[1005]; int main(){ cint; while(t--){ bool flag0; i64 ans-1; for(i64 i0;i1000;i) a[i]0; while(1){ cinn; if(n-1) break; a[n]; if(a[n]2flag0){ flag1; ansn; } } if(flag) coutansendl; else coutNONEendl; } return 0; }#includeiostream #includecmath #define i64 long long using namespace std; i64 n,a; i64 tri(i64 x); i64 dou(i64 x); int main(){ cinn; for(i64 i1;in;i){ bool f10,f20; cina; if(tri(a)*tri(a)*tri(a)*3a){ f21; couta is a triple flowerendl; } else if(dou(a)*dou(a)*2a){ f11; couta is a double flowerendl; } if(!f1!f2){ couta is aendl; } } return 0; } i64 tri(i64 x){ if(x%3!0) return -1; i64 kx/3; for(i64 i1;isqrt(k);i){ if(i*i*ik){ //coutiendl; return i; } } return -1; } i64 dou(i64 x){ if(x%2!0) return -1; i64 kx/2; for(i64 i1;isqrt(k);i){ if(i*ik){ //coutiendl; return i; } } return -1; }我是真的没想到这题能把我弄死。我想不到怎么求开根号和开三次方根。一直用pow函数搞不定。直到最后磨了半小时才决定自己手写一份函数结果通过了。这题难炸了我到现在也没找出一个合适的答案。在AI的提示下我尝试考虑暴力解法。喜提17/25。#includeiostream #includevector #define i64 long long using namespace std; i64 n,t,a[10005],stack[10005],top0; i64 find(i64 x); void solve(); int main(){ cint; while(t--){ solve(); } return 0; } void solve(){ vectori64 num; i64 val; while(cinvalval!-1){ num.push_back(val); } if(num.size()3){ coutNONEendl; return ; } i64 nnum.size(); for(i64 j1;jn-3;j){ for(i64 i0;ij;i){ if(num[i]num[j]num[i1]num[j1]num[i2]num[j2]){ bool flag1; for(i64 kj1;kn-1;k){ if(num[k]num[j]){ if(num[k1]!num[j1]||num[k2]!num[j2]){ flag0; break; } } } if(flag1){ coutnum[j] num[j1] num[j2]endl; return ; } } } } coutNONEendl; return ; }这是一个需要很快看出来考并查集的题目。你知道了该用并查集这题就解决一大半了。就是把并查集的结果数组给求出来。有了数组然后我们需要的是最小集合。那么我们就可以考虑人为修改并查集结果让同一个集合指向最小的位置。我这个时间复杂度在最差情况下是O(n^2)居然也过了。#includeiostream #define i64 long long using namespace std; i64 pre[10005]; i64 n,m,k,a,b; void init(); i64 find(i64 num); int main(){ cinnm; init(); for(i64 i1;in;i){ cinka; for(i64 j2;jk;j){ cinb; pre[find(b)]find(a); //coutpre[a] pre[b]endl; } } for(i64 i1;im;i){ pre[i]find(pre[i]); //coutpre[i] ; } //coutendl; i64 tmp0,stack[10005],top0; bool s[10005]; for(i64 i1;im;i){ if(s[i]) continue; stack[top]i; //couti ; if(ipre[i]) { tmppre[i]; pre[i]i; s[i]1; for(i64 ji1;jm;j){ if(pre[j]tmp){ pre[j]i; s[j]1; } } } } for(i64 i1;itop;i) coutstack[i] ; coutstack[top]endl; return 0; } void init(){ for(i64 i1;im;i) pre[i]i; return ; } i64 find(i64 num){ if(pre[num]num) return num; else return pre[num]find(pre[num]); }