網(wǎng)易雷火 筆試 AC數(shù) + 題解

第一題(100%)
//#pragma?GCC?optimize(3) #include?<bits/stdc++.h> using?namespace?std; int?getCommonCount(string&?a,?string&?b){ ????for(int?len?=?5;?len?>?0;?len--){ ????????unordered_map<string,?bool>?vis; ????????for(int?i?=?0;?i?<=?a.size()-len;?i++){ ????????????vis[a.substr(i,len)]?=?true; ????????} ????????for(int?i?=?0;?i?<=?b.size()-len;?i++){ ????????????if(vis[b.substr(i,len)])?return?len; ????????} ????} ????return?0; } double?getScore(string&?a,?string&?b){ ????double?score?=?0; ????char?colorA?=?a[0],?colorB?=?b[0]; ????string?areaA?=?a.substr(1,a.size()-6),?areaB?=?b.substr(1,b.size()-6); ????string?numA?=?a.substr(a.size()-5,5),?numB?=?b.substr(b.size()-5); ????if(colorA?==?colorB)?score?+=?2; ????if(areaA?==?areaB)?score?+=?3; ????score?+=?getCommonCount(numA,?numB); ????score?*=?10; ????return?score; } int?main()?{ #ifndef?ONLINE_JUDGE ????freopen("in1.txt",?"r",?stdin); #endif ????ios::sync_with_stdio(0); ????int?totalCount; ????double?score?=?0; ????string?a,?b; ????cin?>>?totalCount; ????for(int?i?=?0;?i?<?totalCount;?i++){ ????????cin?>>?a?>>?b; //????????double?tmp?=?getScore(a,?b); //????????cout?<<?a?<<?'?'?<<?b?<<?'?'?<<?tmp?<<?endl; ????????score?+=?getScore(a,?b); ????} ????printf("%.2lf%\n",score/totalCount); ????return?0; }第二題(100%,一開始還以為是拓?fù)湫颍?/strong>
//#pragma?GCC?optimize(3) #include?<bits/stdc++.h> using?namespace?std; const?int?MAXN?=?1e4?+?10; vector<int>?G[MAXN]; //int?du[MAXN]?=?{0}; unordered_map<int,?int>?used; int?remove(int?u){ ????queue<int>?que; ????unordered_set<int>?vis; ????que.push(u); ????while(!que.empty()){ ????????u?=?que.front();?que.pop(); ????????if(vis.count(u)?>?0)?continue; ????????vis.insert(u); ????????used[u]--; ????????if(used[u]?==?0)?used.erase(u); ????????for(int?v:?G[u]){ ????????????que.push(v); ????????} ????} ????return?used.size(); } int?apply(int?u){ ????queue<int>?que; ????unordered_set<int>?vis; ????que.push(u); ????while(!que.empty()){ ????????u?=?que.front();?que.pop(); ????????if(vis.count(u)?>?0)?continue; ????????vis.insert(u); ????????used[u]++; ????????for(int?v:?G[u]){ ????????????que.push(v); ????????} ????} ????return?used.size(); } int?main()?{ #ifndef?ONLINE_JUDGE ????freopen("in1.txt",?"r",?stdin); #endif ????ios::sync_with_stdio(0); ????int?n,?m; ????cin?>>?n?>>?m; ????for(int?u?=?0;?u?<?n;?u++){ ????????int?count,?v; ????????cin?>>?count; ????????while(count--){ ????????????cin?>>?v; ????????????G[u].push_back(v); ????????} ????} ????int?flag,?id,?ans?=?0; ????while(m--){ ????????cin?>>?flag?>>?id; ????????if(flag)?ans?=?max(ans,apply(id)); ????????else?ans?=?max(ans,?remove(id)); ????} ????cout?<<?ans?<<?endl; ????return?0; }
//#pragma?GCC?optimize(3) #include?<bits/stdc++.h> using?namespace?std; const?int?MAXN?=?1e4?+?10; typedef?pair<int,int>?Point; typedef?pair<double,double>?FloatPoint; typedef?pair<Point,?Point>?Line; vector<Line>?recs; Point?getPoint(Line&?a,?Line&?b){ ????Point?&p1?=?a.first,?&p2?=?a.second,?&p3?=?b.first,?&p4?=?b.second; ????if(p1.second?>=?p3.second?&&?p1.second?<=?p4.second?&& ????p3.first?>=?p1.first?&&?p3.first?<=?p2.first){ ????????return?Point(p3.first,p1.second); ????} ????return?Point(-1,-1); } //?右上?左上?右下?左下 double?dir[][2]?=?{0.5,0.5,?-0.5,0.5,?0.5,-0.5,?-0.5,-0.5}; bool?PointinRec(double?x,?double?y){ ????for(Line&?rec:?recs){ ????????Point?&a?=?rec.first,?&b?=?rec.second; ????????bool?con1?=?x?>?a.first?&&?x?<?b.first; ????????bool?con2?=?y?>?a.second?&&?y?<?b.second; ????????if(con1?&&?con2){ ????????????return?true; ????????} ????} ????return?false; } bool?check(Point?p){ ????if(p.first?<?0)?return?false; ????//?右上?左上?右下?左下 ????bool?ok1?=?PointinRec(p.first?+?dir[0][0],?p.second?+?dir[0][1]); ????bool?ok2?=?PointinRec(p.first?+?dir[1][0],?p.second?+?dir[1][1]); ????bool?ok3?=?PointinRec(p.first?+?dir[2][0],?p.second?+?dir[2][1]); ????bool?ok4?=?PointinRec(p.first?+?dir[3][0],?p.second?+?dir[3][1]); ????int?count?=?ok1?+?ok2?+?ok3?+?ok4; ????if(count?==?1?||?count?==?3)?return?true; ????if(count?==?2?&&?(ok1?&&?ok4?||?ok2?&&?ok3)){ ????????return?true; ????} ????return?false; } int?main()?{ #ifndef?ONLINE_JUDGE ????freopen("in1.txt",?"r",?stdin); #endif ????ios::sync_with_stdio(0); ????int?n; ????set<Point>?points; ????set<Line>?vecLine,?colLine; ????cin?>>?n; ????for(int?i?=?0;?i?<?n;?i++){ ????????Point?a,?b,?c,?d; ????????cin?>>?a.first?>>?a.second?>>?b.first?>>?b.second; ????????c?=?Point(a.first,b.second); ????????d?=?Point(b.first,a.second); ????????recs.push_back(Line(a,b)); ????????vecLine.insert(Line(a,d)); ????????vecLine.insert(Line(c,b)); ????????colLine.insert(Line(a,c)); ????????colLine.insert(Line(d,b)); ????} ????for(Line?vec:?vecLine){ ????????for(Line?col:?colLine){ ????????????Point?p?=?getPoint(vec,col); ????????????if(check(p)) ????????????????points.insert(p); ????????} ????} ????for(Point?p:?points){ ????????cout?<<?p.first?<<?'?'?<<?p.second?<<?endl; ????} ????return?0; }第四題(過了1.6%,逃~~)
//#pragma?GCC?optimize(3) #include?<bits/stdc++.h> using?namespace?std; int?main()?{ #ifndef?ONLINE_JUDGE ????freopen("in1.txt",?"r",?stdin); #endif ????ios::sync_with_stdio(0); ????int?blood,?power; ????cin?>>?blood?>>?power; ????cout?<<?500?<<?endl; ????return?0; }