9.12网易笔试
二分图匹配裸题
#include<bits/stdc++.h> using namespace std; constexpr const int MAXVAL = 505; int k, m, n; int couples[MAXVAL][MAXVAL]; int girls[MAXVAL]; int visited[MAXVAL]; int find(int x) { int i; for (i = 1; i <= m; ++i) { if(couples[x][i]==1 && visited[i]==0) { visited[i] = 1; if(girls[i]==0 || find(girls[i])) { girls[i] = x; return 1; } } } return 0; } int solve() { int ans = 0; int i = 0; memset(girls, 0, sizeof(girls)); for (i = 1; i <= n; ++i) { memset(visited, 0, sizeof(visited)); if(find(i) == 1) ans = ans + 1; } return ans; } int main(int argc, char const *argv[]) { /* code */ int i; int a,b; while(cin>>k && k) { cin>>m>>n; memset(couples,0,sizeof(couples)); for (i = 1; i <=k; ++i) { /* code */ cin>>a>>b; couples[b][a] = 1; } cout<<solve()<<endl; } return 0; }
理解
BGM算法本质上是递归的算法,其中对每个男生,都会考虑全部女生,这点有点像BootStrap算法。
关于未知行数数据读取方式
今天碰到未知输入数量的情况,对C++来说,有点麻烦。而且要想和基本形式一致,还需要采用映射的方式把女生ID映射为从1开始
#include<bits/stdc++.h> using namespace std; constexpr const int MAXVAL = 505; int m = 0, n = 0; int girls[MAXVAL]; int girls_map_id[MAXVAL]; int main(int argc, char const *argv[]) { /* code */ string S=""; getline(cin,S); cout<<"S "<<S<<endl; int l=S.size(), base = 0; for(int i=0;i<l;i++) { if(S[i]==' ') { girls[++m]=base; girls_map_id[base] = m; base=0; } else base = base*10+S[i]-'0'; } girls[++m] = base; girls_map_id[base] = m; for (int i = 1; i < m; ++i) { cout<<"girl "<<girls[i]<<' '; } return 0; }
关于python复杂排序问题
编程时候经常会遇到复杂的排序情况,之前没有好好总结过,这里总结一下
from operator import itemgetter alist = [( '1' , '5' , '1' ), ( '2' , '4' , '1' ), ( '3' , '3' , '3' ), ( '4' , '2' , '3' ), ( '5' , '1' , '2' )] # 多级排序,先按照第3个元素排序,然后按照第2个元素排序: #字典序 print (sorted(alist, key = itemgetter(2,1), reverse = False)) # 转化为整数 单级排序 print (sorted(alist, key = lambda x: int(itemgetter(1)(x)), reverse = False)) # 全部转化为整数 print (sorted(alist, key = lambda x: list(map(int,itemgetter(2 , 1)(x))), reverse = False)) #比较直接的方式 print (sorted(alist, key = lambda x:(int(x[2]), int(x[1])), reverse = False)) blist = {"abcd123_c10000":4,"abcd12_c33":3,"abcd23_c100":2,"abcd21_c9999":1} # 字典按值排序 print(dict(sorted(blist.items(), key=lambda x:x[1] ,reverse=False))) # 字典按键排序 print(dict(sorted(blist.items(), key=lambda x:x[0] ,reverse=False))) #按部分的分割字符串排序 print(dict(sorted(blist.items(), key=lambda x:(int(x[0].split('_c')[1]),x[0].split('_c')[0]) ,reverse=False)))
总结
今天虽然只做出了两道题,但是第一道题我一边就写对了,没有调试,还是很开心。写程序的时候还是要小心,今天第二题我用C++写好了,但是不知咋滴有问题,本地调试发现程序里有输入,但是运行时候没输入数据就结束了。我把程序全部删掉,只剩个main,和输入部分,还是这样,真是玄学,我服了。考试来不及找错误,谁知道哪里错了。赶紧用python又写了一边,过了,但是浪费了好多时间啊。
第三题做过原题(事后才知道,基本忘完了),但是还是没想出来,只想着暴力出奇迹。明显超时了。第四题一开始的以为是贪心,我理解的题意是输入的是每个人的意向,按照意向最少的优先,排个序。
后来发现题目给的直接是双方都有意思的组合,也没啥思路。
总结下来就是,题目要读清楚,不要慌。还有就是写程序一定要细心,最好用本地文本编辑器,有语法检测,有时候写程序会出现莫名奇妙的问题,防不胜防。还有,再次强调的是,理解出题人意图,不要傻傻的暴力破解。