转载请注明出处：https://www.cnblogs.com/jlyg/p/7525244.html
终于在考前，刷完PAT甲级131道题目，不容易！！！每天沉迷在刷题之中而不能超脱，也是一种境界。PAT甲级题目总的说卡题目的比较多，卡测试点的比较少，有些题目还会有题意混淆，这点就不吐槽了吧。静下心来耍这130道题，其实磨练的是一种态度与手感，养成的是一种习惯。热爱AC没有错！！（根据自己的刷题情况持续更新中，这次是第二遍刷了，发现换了新网站后，oj严格很多了，有些之前可以过的，现在已经不能过了）
PAT甲级复习之二：主要写一些考前注意，以及常见算法。网址通道https://www.cnblogs.com/jlyg/p/10364696.html。
PAT甲级复习之三：主要是131题后的题目，网址通道https://www.cnblogs.com/jlyg/p/10364727.html
131道题目主要的考点：
1、排序：快速排序，直接插入排序，希尔排序，分治排序，堆排序。
2、图论：拓扑排序(好像没考过)、最短路径、深度搜索、广度搜索。
3、树：树的遍历、完全二叉树、AVL,CBT,BST。
4、其他：并查集，模拟，哈希(二次探测一次，简单hash多次)、背包(一次)，lcs（一次），最大子和（一次）,set(一次)，1057（分块搜索）
主要算法：快排、直接插入排序、希尔排序、分治排序、堆排序、拓扑排序、dijkstra,floyd,dfs,bfs,AVL,并查集,树遍历算法。
题目分类：
1003（dfs or dijkstra）、1004（dfs）、1007（最长子和）、1010（二分查找）、1013（并查集）、1020（二叉树，前后序求广度）、1021（并查集）、1024（大数加法）、1029（归并排序）、1030（dikstra）、1043（前序判断是否是二叉收缩树）、1044（二分查找）、1045（lcs）、1053（dfs）、1063（set）、1064（二叉搜索树）、1066（AVL）、1068（背包问题）、1076（bfs）、1078（hash二次探测）、1079（bfs，dfs）、1086（中前序求后序）、1089（排序）、1094（bfs or 并查集），1098（排序）、1099（BST）、1101（快排）、1102（反转二叉树）、1103（dfs剪枝）、1107（并查集）、1110（完全二叉树）、1111（dijkstra）、1114（并查集）、1115（BST）、1118（并查集）、1119（前后序求中序）、1123（AVL）、1127（bfs）、1130（dfs） dijkstra: 1003、1030、1111 dfs: 1003、1004、1053、1079、1103（dfs剪枝）、1130 bfs：1076、1079、1094、1127 排序：1029（归并排序）、1089、1098、1101（快排） 并查集：1013、1021、1094、1107、1114、1118 二叉树：1020（前后序求广度）、1043（前序判断是否是二叉搜索树）、1064（二叉搜索树）、1066（AVL）、1086（中前序求后序）、1099（BST）、1102（反转二叉树）、1110（完全二叉树）、1115（BST）、1119（前后序求中序）、1123（AVL） 二分查找：1010、1044 其他：1007（最长子和）、1024（大数加法）、1045（lcs）、1063（set）、1068（背包问题）、1078（hash二次探测）
错误修改：1013不是并查集，应该是dfs，刚刚发现，抱歉。
1010这题目会比较奇怪，属于题意不清，第一可能会超出long long int，第二需要使用二分法不然超时，第三进制是无限制的可以是2到无限
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; long long int change(const char* strnum,long long int jinzhi) { long long int len = strlen(strnum); long long int res = 0; for(long long int i=len-1,k=1;i>=0;--i,k*=jinzhi) { long long int a; if(strnum[i]>='0'&& strnum[i]<='9') a = strnum[i]-'0'; else a = strnum[i]-'a'+10; res += k*a; } return res; } long long int Find_Radix(char* strnum,long long int dst,long long int left,long long int right) { long long int mid = (left+right)/2; long long int midnum = change(strnum,mid); if(left==right) { if(dst != midnum) return -1; return left; } else if(left > right) { return -1; } if(midnum==dst) { return mid; } if(midnum<0||dst<midnum) { return Find_Radix(strnum,dst,left,mid-1); } else { return Find_Radix(strnum,dst,mid+1,right); } } int main() { //freopen("test.txt","r",stdin); char s1[20],s2[20]; int tag,jinzhi; scanf("%s%s%d%d",s1,s2,&tag,&jinzhi); if(tag==2) {swap(s1,s2);} long long int a = change(s1,jinzhi); long long int left = 0; int len = strlen(s2); for(int i=0;i<len;++i) { long long int temp; if(s2[i]>='0'&&s2[i]<='9') { temp = s2[i]-'0'; } else { temp = s2[i] - 'a'+10; } left = max(temp+1,left); } left = max((long long int)2,left); long long int right = max(a,left); long long int res = Find_Radix(s2,a,left,right); if(res==-1) { printf("Impossible "); } else { printf("%lld ",res); } return 0; }
1012题目排名是可以有并列的，比如有并列第1的情况。
1014这道题的问题在于只要在17:00之前开始的就是正常的，结束时间是可以超过17:00后的，有点坑吧。
1017模拟题，看代码和注释，很详细
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; int gettick(int h,int m,int s) { return h*60*60+m*60+s; } const int window_starttime = gettick(8,0,0); const int window_endtime = gettick(17,0,0); struct Customer { int cometime; //来到时间 int protime; //处理时间,秒 }; int getfreewindow(int* windows,int k) { int mintime = windows[0],mink = 0; for(int i=1;i<k;++i) { if(mintime > windows[i]) { mink = i; mintime = windows[i]; } } //注释1：该种情况就是，这个人是17点之前来的，但是前面有人结束后就已经是17点以后了，这种情况也不需要过滤，还是计算在内的。 //if(mintime>window_endtime) return -1; return mink; } int cmp(const Customer& c1,const Customer& c2) { return c1.cometime < c2.cometime; } int main() { #ifdef ONLINE_JUDGE #else freopen("test.txt","r",stdin); #endif int n,k; scanf("%d%d",&n,&k); vector<Customer> vcus; for(int i=0;i<n;++i) { int h,m,s,p; scanf("%d:%d:%d%d",&h,&m,&s,&p); Customer cus; cus.cometime = gettick(h,m,s); cus.protime = min(60*p,60*60); if(cus.cometime <= window_endtime) //过滤17点以后来的人 vcus.push_back(cus); } n = vcus.size(); sort(vcus.begin(),vcus.end(),cmp); int twaittime = 0/*总等待时间*/,cnt=0/*得到处理的人数*/,windowstime[k]/*该窗口空闲时间*/; for(int i=0;i<k;++i) windowstime[i] = window_starttime; for(int i=0;i<n;++i) { int iw = getfreewindow(windowstime,k); if(iw==-1) break; ++cnt; Customer &cus = vcus[i]; if(cus.cometime<windowstime[iw]) { twaittime+= (windowstime[iw]-cus.cometime); windowstime[iw] += cus.protime; } else { windowstime[iw] = cus.cometime + cus.protime; } } if(cnt==0) printf("0.0 "); else printf("%.1lf ",1.0f*twaittime/cnt/60); return 0; }
1018题：dfs，求最小路径，若相同求最小借出的bike数，再若相同，求最小还回的bike数。要注意路径（cmax=10）PBM->(3)->(10),它的send为2，back为5，而不是send为0，back3（后面多出来的不能补到前面的,前面多出来的可以补到后面）
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; #define N (510) const int INF = (1<<30); int cmax,n,sp,m; int cap[N]; int Len[N][N]; vector<int> Map[N]; bool bVis[N]; int minlen = INF; int minsend = 0; int minback= 0; vector<int> minPath; void dfs(int curI,int len,vector<int> path) { if(curI==sp) { if(len <= minlen) { int curminsend = 0,curminback = 0; for(int i=1;i<path.size();++i) { int curcap = cap[path[i]]; if(curcap<cmax/2) //少了 { int adjust = cmax/2 - curcap; if(adjust <= curminback) { curminback -= adjust; } else { adjust -= curminback; curminback = 0; curminsend += adjust; } } else if(curcap>cmax/2) //多了 { curminback += (curcap-cmax/2); } } if(len<minlen||(len==minlen&&curminsend<minsend)|| (len==minlen&&curminsend==minsend&&curminback<minback)) { minlen = len; minPath = path; minsend = curminsend; minback = curminback; } } return; } if(len >= minlen) return; for(int i=0;i<Map[curI].size();++i) { int nextI = Map[curI][i]; if(!bVis[nextI]) { bVis[nextI] = true; path.push_back(nextI); dfs(nextI,len+Len[curI][nextI],path); path.pop_back(); bVis[nextI] = false; } } } int main() { #ifdef ONLINE_JUDGE #else freopen("test.txt","r",stdin); #endif scanf("%d%d%d%d",&cmax,&n,&sp,&m); for(int i=0;i<=n;++i) for(int j=0;j<=n;++j) if(i==j) Len[i][j] = 0; else Len[i][j] = INF; for(int i=1;i<=n;++i) scanf("%d",&cap[i]); for(int i=0;i<m;++i) { int a,b,l; scanf("%d%d%d",&a,&b,&l); Len[a][b] = Len[b][a] = l; Map[a].push_back(b); Map[b].push_back(a); } bVis[0] = true; vector<int> path; path.push_back(0); dfs(0,1,path); printf("%d ",minsend); for(int i=0;i<minPath.size();++i) { if(i) printf("->"); printf("%d",minPath[i]); } printf(" %d ",minback); return 0; }
1022题，需要用到整行输入字符串，而PAT的c++编译器是无法调用gets的，可以用fgets(buf,sizeof(buf),stdin);//读入的数据需要去掉
。如果在fgets函数之前调用了scanf，就必须要使用getchar把换行好读掉。
当然也可以用 while(cin>>str)
{ char c; c=getchar(); if(c=='
') break; }
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; void mygets(string& str) { char temp[100]; fgets(temp,sizeof(temp),stdin); temp[strlen(temp)-1] = ' '; str = temp; } map<string,set<int> > mapbname; map<string,set<int> > mapauthor; map<string,set<int> > mapkey; map<string,set<int> > mappublisher; map<string,set<int> > mapyear; struct Book { int id; string bname; string author; string key; string publisher; string year; set<string> setkey; void Read() { scanf("%d",&id); getchar(); mygets(bname); mygets(author); mygets(key); mygets(publisher); mygets(year); DealKey(); mapbname[bname].insert(id); mapauthor[author].insert(id); mappublisher[publisher].insert(id); mapyear[year].insert(id); } void DealKey() { int len = key.length(); string words = ""; for(int i=0;i<len;++i) { if(key[i]!=' ') words += key[i]; if(i==len-1||key[i]==' ') { if(!words.empty()) { setkey.insert(words); mapkey[words].insert(id); } words = ""; } } /*set<string>::iterator it = setkey.begin(); for(;it!=setkey.end();it++) printf("%s ",it->c_str()); */ } }; int main() { #ifdef ONLINE_JUDGE #else freopen("test.txt","r",stdin); #endif int t; scanf("%d",&t); while(t--) { Book book; book.Read(); } scanf("%d",&t); while(t--) { int opt; string str; scanf("%d: ",&opt); mygets(str); printf("%d: %s ",opt,str.c_str()); map<string,set<int> > *mss = NULL; if(opt==1) mss = &mapbname; else if(opt==2) mss = &mapauthor; else if(opt==3) mss = &mapkey; else if(opt==4) mss = &mappublisher; else if(opt==5) mss = &mapyear; if(mss->find(str)!=mss->end()) { set<int> &si = (*mss)[str]; set<int>::iterator it = si.begin(); for(;it!=si.end();it++) { printf("%07d ",*it); } if(si.size()==0) printf("Not Found "); } else { printf("Not Found "); } } return 0; }
1024题：输入本身就是回文串时，直接输出该回文串，并且输出步数为0.
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<map> #include<algorithm> using namespace std; #define N (100) bool isPal(char* str) { int l = strlen(str); for(int i=0;i<l/2;++i) if(str[i] != str[l-i-1]) return false; return true; } void Add(char* str) { char temp[N]; int iAdd = 0; int l = strlen(str); int tlen = 0; for(int i=0;i<l;++i) { int res = str[i]-'0'+str[l-i-1]-'0' +iAdd; temp[tlen++] = res%10 + '0'; iAdd = res/10; } if(iAdd) temp[tlen++] = iAdd + '0'; temp[tlen] = ' '; string strTemp = temp; reverse(strTemp.begin(),strTemp.end()); //反转 strcpy(str,strTemp.c_str()); } int main() { char strNum[N]; int k; scanf("%s%d",strNum,&k); int step = 0; while(!isPal(strNum)&&step<k) { Add(strNum); ++step; } printf("%s ",strNum); printf("%d ",step); return 0; }
1026题：题目比较坑：
1、处理时间有超过2个小时的，需要自己代码判断大于2个小时，变成两个小时。
2、21：00:00之后不处理，包括21点整。
3、当有普通球台和VIP球台时，VIP客户遵循选择最小编号的VIP球台，而非编号最小的普通球台；普通客户遵循选择最小的球台
4、四舍五入，不然最后一个case过不了。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; #define N (10010) int getTick(int h,int m,int s) { return 60*60*h+60*m+s; } const int SartTime = getTick(8,0,0); const int EndTime = getTick(21,0,0); bool bTableVip[N]; int tableperson[N]; //每张桌子处理的人数 int tabfreetime[N]; //每张桌子空闲时间 int tables; //桌子数 struct Custom { int arrivingtime; //到达时间 int servingtime; //开始服务时间 int playingtime; //玩耍时间 }; int getFreeTable(int& freeviptableid) //该函数返回一个编号最小，最早空闲时间的桌子编号，freeviptable表示vip中编号最小的，最早空闲时间的桌子编号 { int tablesid = -1,mintime = getTick(30,0,0),minviptime=getTick(30,0,0); freeviptableid = -1; for(int i=1;i<=tables;++i) { if(tabfreetime[i]<mintime) { mintime = tabfreetime[i]; tablesid = i; } if(bTableVip[i]&&tabfreetime[i]<minviptime) { minviptime = tabfreetime[i]; freeviptableid = i; } } return tablesid; } bool cmp(const Custom& c1,const Custom& c2) { return c1.arrivingtime < c2.arrivingtime; } bool cmp2(const Custom& c1,const Custom& c2) { return c1.servingtime < c2.servingtime; } void printtime(int tick) { printf("%02d:%02d:%02d ",tick/3600,tick%3600/60,tick%60); } int main() { #ifndef ONLINE_JUDGE freopen("test.txt","r",stdin); #endif // ONLINE_JUDGE int n; scanf("%d",&n); vector<Custom>cus,cusvip; for(int i=0;i<n;++i) { Custom c; int h,m,s,bVip; scanf("%d:%d:%d%d%d",&h,&m,&s,&c.playingtime,&bVip); c.arrivingtime = getTick(h,m,s); c.playingtime = min(2*60*60,c.playingtime*60); //转换成秒 if(bVip) cusvip.push_back(c); else cus.push_back(c); } //加入末尾哨兵，这样当下面运用是不需要考虑vector为空的时候 Custom finalcus; finalcus.arrivingtime = getTick(30,0,0); cus.push_back(finalcus); cusvip.push_back(finalcus); sort(cus.begin(),cus.end(),cmp); sort(cusvip.begin(),cusvip.end(),cmp); int m; scanf("%d%d",&tables,&m); for(int i=0;i<m;++i) { int tableid; scanf("%d",&tableid); bTableVip[tableid] = 1; } for(int i=0;i<tables;++i) tabfreetime[i+1] = SartTime; vector<Custom> res; for(int i=0;i<n;++i) { int freeviptableid; int freetableid = getFreeTable(freeviptableid); Custom curcus; if(cusvip[0].arrivingtime<cus[0].arrivingtime|| /*当vip用户早到时，vip用户肯定先上桌*/ bTableVip[freetableid]&&cusvip[0].arrivingtime<=tabfreetime[freetableid]) /*如果vip用户晚到，但是这桌是vip专用桌，此时要看vip到达时间是否在桌有空之前到达*/ { curcus = cusvip[0]; cusvip.erase(cusvip.begin()); if(freeviptableid!=-1&&curcus.arrivingtime>=tabfreetime[freeviptableid]) //vip用户来的比最小vip桌空闲时间晚，这个时候前面即使有空闲普通桌，也要选择vip桌。 freetableid = freeviptableid; } else { curcus = cus[0]; cus.erase(cus.begin()); } if(tabfreetime[freetableid]>=EndTime||curcus.arrivingtime>=EndTime) { break; } curcus.servingtime = max(tabfreetime[freetableid],curcus.arrivingtime); tabfreetime[freetableid] = curcus.servingtime + curcus.playingtime; ++tableperson[freetableid]; res.push_back(curcus); } sort(res.begin(),res.end(),cmp2); for(int i=0;i<res.size();++i) { printtime(res[i].arrivingtime); printtime(res[i].servingtime); int waittime = max(0,res[i].servingtime - res[i].arrivingtime); waittime = (int)(1.0*waittime/60+0.5); printf("%d ",waittime); } for(int i=1;i<=tables;++i) { if(i-1) printf(" "); printf("%d",tableperson[i]); } printf(" "); return 0; }
1029题：坑点，内存超出限制，找到中位数之后，就无需再继续往队列中push。
#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<algorithm> #include<iterator> #include<queue> using namespace std; #define N (2*100000+1) #define INF (1<<30) queue<int> a; queue<int> b; int main() { int n,m; scanf("%d",&n); for(int i=0;i<n;++i) { int temp; scanf("%d",&temp); a.push(temp); } a.push(INF); scanf("%d",&m); int iCnt = 0; int iMid = -1; for(int i=0;i<m;++i) { int temp; scanf("%d",&temp); if(iMid == -1) { b.push(temp); if(iCnt==(m+n+1)/2-1) { iMid = min(a.front(),b.front()); } if(a.front()<b.front()) a.pop(); else b.pop(); } ++iCnt; } b.push(INF); for(;iCnt<=(m+n+1)/2-1;++iCnt) { iMid = min(a.front(),b.front()); if(a.front()<b.front()) a.pop(); else b.pop(); } printf("%d ",iMid); return 0; }
用数组的做法，类似分治排序的方法（可以看算法导论中对分治排序的讲解，写的特别好！！）
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> #include<climits> using namespace std; int main() { #ifndef ONLINE_JUDGE freopen("1.txt","r",stdin); #endif // ONLINE_JUDGE int n1,n2; scanf("%d",&n1); int a1[n1+1]; for(int i=0;i<n1;++i) scanf("%d",&a1[i]); scanf("%d",&n2); int res = 0,k=0,j=0; for(int i=0;i<n2;++i) { int num; scanf("%d",&num); while(a1[j]<num&&k<(n1+n2+1)/2) { res = a1[j++]; k++; } if(a1[j]>=num&&k<(n1+n2+1)/2) { res = num; k++; } } //这一行容易忘记,因为k可能没有到中位数。 while(k++<(n1+n2+1)/2) res = a1[j++]; printf("%d ",res); return 0; }
1031题：坑点，当字符串长度是9的时候，试试，比如123456789，正确输出是，计算 n2 = (N+2+2)/3，而不是n2=(N+2)/3;这种算出来n2可能会比n1,n3小
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<map> #include<set> #include<algorithm> using namespace std; int main() { char str[100]; //while(true) { scanf("%s",str); int len = strlen(str); int n1,n2,n3 = (len+2+2)/3; n3 = max(3,n3); for(;n3<=len;++n3) if((len+2-n3)%2==0) break; int space = n3-2; n1 = n2 = (len - n3 + 2)/2; for(int i=0;i<n1-1;++i) { printf("%c",str[i]); for(int j=0;j<space;++j) printf(" "); printf("%c ",str[len-i-1]); } printf("%c",str[n1-1]); for(int i=n1;i<n1+space;++i) printf("%c",str[i]); printf("%c ",str[n1-1+n3-1]); } return 0; }
1032题：坑点，当搜索的两个起点是一样的时候测试点 。个人觉得应该还要考虑两个起点是直接父子关系的情况（但是测试点中没有。。。）
1 1 3 1 c 2 2 a 3 3 b -1
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> using namespace std; #define N (100000+10) vector<int> vcPath[N]; bool bVis[N] = {0}; int iComPos = -1; void dfs(int iCurI) { bVis[iCurI] = true; for(int i=0;i<vcPath[iCurI].size();++i) { int iNextI = vcPath[iCurI][i]; if(false==bVis[iNextI]) dfs(iNextI); else { iComPos = iNextI; return; } } } int main() { int s1,s2,n; scanf("%d%d%d",&s1,&s2,&n); if(s1 == s2) iComPos = s1; for(int i=0;i<n;++i) { int a,b; char c[10]; scanf("%d%s%d",&a,c,&b); if(s1 == a && s2 == b || s2==a&&s1==b) { iComPos = b; } if(b != -1) { vcPath[a].push_back(b); } } if(-1 == iComPos) { dfs(s1); dfs(s2); } if(-1==iComPos) printf("%d ",-1); else printf("%05d ",iComPos); return 0; } /* 1 2 2 1 c 2 2 a -1 */
1033题：坑点2：1）终点可能是起点，2）如果当前加油点可以直接开到终点，并且后面几个点都比他大的话，就无需遍历接来的点了（这题是真的很烦。。。。目测不是考试原题，仅仅是练习题）
1）寻找必须要加油的站点加入到set中，搜索距离为dis的站点+满油时行驶距离之内的所有站点，找最近的比dis单价便宜的站点，如果没有，则找这段距离中价格最便宜的。
2）根据set中的判断这次的加油站价格是否比下一个加油站的价格小，如果是，则加满油，否则加的油能够支持到下一个加油站就行了。
解法1：第二点需要特殊处理
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> using namespace std; int main() { int iCmax,d,davg,n; scanf("%d%d%d%d",&iCmax,&d,&davg,&n); map<int,double> mis; for(int i=0;i<n;++i) { double p; int iDis; scanf("%lf%d",&p,&iDis); if(iDis >= d) continue; if(mis.find(iDis)==mis.end()) mis[iDis] = p; else if(mis[iDis]>p) mis[iDis] = p; } if(mis.size()==0||mis.begin()->first!=0) //一个测试点 { printf("The maximum travel distance = 0.00 "); } else if(d==0) //没有测试点 { printf("0.00 "); } else { double iMaxLen = iCmax*davg; map<int,double>::iterator it = mis.begin(); set<int> si; while(it!=mis.end()&&it->first < d) { map<int,double>::iterator tit = it; si.insert(it->first); double fDis = it->first; double fPrice = it->second; double fMinPrice = -1; double fMinDis = -1; //如果当前加油点可以直接开到终点，并且后面几个点都比他大的话，就无需遍历接来的点了 bool bBreak = true; if(fDis+iMaxLen>=d) { for(;tit!=mis.end();++tit) { if(tit->second < fPrice) { bBreak = false; break; } } if(bBreak) break; } tit = it; while(++tit != mis.end()) { if(tit->first - fDis <= iMaxLen && tit->first < d) { if(fMinDis == -1 || fMinPrice > tit->second) { fMinDis = tit->first; fMinPrice = tit->second; if(fMinPrice < fPrice) { break; } } } else { break; } } tit = mis.find(fMinDis); if(tit != it) { it = tit; } else break; } set<int>::iterator sit = si.begin(); double fTotal = 0; double fCurCap = 0; for(int i=0;sit != si.end();sit++,++i) { if(i == si.size()-1) { if(*sit+iMaxLen < d) { printf("The maximum travel distance = %.2lf ",*sit+iMaxLen); } else { //printf("gas=%.2lf ",1.0*(d-*sit)/davg-fCurCap); fTotal += (1.0*(d-*sit)/davg-fCurCap)*mis[*sit]; printf("%.2lf ",fTotal); } } else { set<int>::iterator nextsit = sit; ++nextsit; if(mis[*nextsit] > mis[*sit]) { //printf("gas=%.2f ",iCmax-fCurCap); fTotal += 1.0*(iCmax-fCurCap)*mis[*sit]; fCurCap = iCmax - 1.0*(*nextsit-*sit)/davg; } else { //printf("gas=%.2f ",(*nextsit-*sit)/davg-fCurCap); fTotal += (1.0*(*nextsit-*sit)/davg-fCurCap)*mis[*sit]; fCurCap = 0; } } //printf("[%d %.2f] ",*sit,fTotal); } } return 0; }
解法2：把终点看作一个加油站，油价为0，则无需再考虑第二点
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> using namespace std; int main() { int iCmax,d,davg,n; scanf("%d%d%d%d",&iCmax,&d,&davg,&n); map<int,double> mis; for(int i=0;i<n;++i) { double p; int iDis; scanf("%lf%d",&p,&iDis); if(iDis >= d) continue; if(mis.find(iDis)==mis.end()) mis[iDis] = p; else if(mis[iDis]>p) mis[iDis] = p; } mis[d] = 0; if(d&&mis.size()==1||mis.begin()->first!=0) //一个测试点 { printf("The maximum travel distance = 0.00 "); } else if(d==0) //没有测试点 { printf("0.00 "); } else { double iMaxLen = iCmax*davg; map<int,double>::iterator it = mis.begin(); set<int> si; while(it!=mis.end()) { map<int,double>::iterator tit = it; si.insert(it->first); double fDis = it->first; double fPrice = it->second; double fMinPrice = -1; double fMinDis = -1; while(++tit != mis.end()) { if(tit->first - fDis <= iMaxLen) { if(fMinDis == -1 || fMinPrice > tit->second) { fMinDis = tit->first; fMinPrice = tit->second; if(fMinPrice < fPrice) { break; } } } else { break; } } tit = mis.find(fMinDis); if(tit != it) { it = tit; } else break; } set<int>::iterator sit = si.begin(); double fTotal = 0; double fCurCap = 0; for(int i=0;sit != si.end();sit++,++i) { if(i == si.size()-1) { if(*sit+iMaxLen < d) { printf("The maximum travel distance = %.2lf ",*sit+iMaxLen); } else { //printf("gas=%.2lf ",1.0*(d-*sit)/davg-fCurCap); fTotal += (1.0*(d-*sit)/davg-fCurCap)*mis[*sit]; printf("%.2lf ",fTotal); } } else { set<int>::iterator nextsit = sit; ++nextsit; if(mis[*nextsit] > mis[*sit]) { //printf("gas=%.2f ",iCmax-fCurCap); fTotal += 1.0*(iCmax-fCurCap)*mis[*sit]; fCurCap = iCmax - 1.0*(*nextsit-*sit)/davg; } else { //printf("gas=%.2f ",(*nextsit-*sit)/davg-fCurCap); fTotal += (1.0*(*nextsit-*sit)/davg-fCurCap)*mis[*sit]; fCurCap = 0; } } //printf("[%d %.2f] ",*sit,fTotal); } } return 0; }
1034题：用dfs题来做，我把名字转换成数字的时候刚开始弄错了死活2个case没过去（(str[0]-'A')+(str[1]-'A')*26+(str[2]-'A')*26*26;）其实正确的是（(str[2]-'A')+(str[1]-'A')*26+(str[0]-'A')*26*26;）不然用map或者set默认排序时会有问题。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<string> #include<iterator> using namespace std; #define N (26*26*26+10) int n,k; int val[N] = {0}; bool bVis[N] = {1}; vector<int> vcMap[N]; map<int,int> Res; int GetNum(char* str) { return (str[2]-'A')+(str[1]-'A')*26+(str[0]-'A')*26*26; } string GetStr(int num) { char str[4] = {0}; str[2] = num%26+'A'; str[1] = num/26%26+'A'; str[0] = num/26/26+'A'; return str; } int iMaxCnt = 0,iMaxI = 0,iMaxMin = 0; void dfs(int curI) { bVis[curI] = true; ++iMaxCnt; iMaxMin += val[curI]; if(val[iMaxI] < val[curI]) iMaxI = curI; for(int i=0;i<vcMap[curI].size();++i) { int NextI = vcMap[curI][i]; if(!bVis[NextI]) dfs(NextI); } } int main() { scanf("%d%d",&n,&k); int iMaxN = 0; for(int i=0;i<n;++i) { char s1[4],s2[4]; int m; scanf("%s%s%d",s1,s2,&m); int ia = GetNum(s1),ib=GetNum(s2); val[ia] += m; val[ib] += m; bVis[ia] = false; bVis[ib] = false; vcMap[ia].push_back(ib); vcMap[ib].push_back(ia); iMaxN = max(iMaxN,max(ia,ib)); } for(int i=0;i<=iMaxN;++i) { if(!bVis[i]) { iMaxCnt = 0,iMaxI = i,iMaxMin = 0; dfs(i); if(iMaxCnt > 2 && iMaxMin>2*k) { Res[iMaxI] = iMaxCnt; } } } printf("%d ",Res.size()); map<int,int>::iterator it = Res.begin(); for(;it!=Res.end();it++) printf("%s %d ",GetStr(it->first).c_str(),it->second); return 0; }
1035题：注意输出是单数是 is 1 account ,双数是 are N accounts;
1038题：通过sort排序，比较方法是s1+s2,s2+s1判断谁小就好了。输出的时候考虑前面的0去掉，2 0 00 别输出是00，但是后面的0不能去掉了（刚开始我就把后面的0也去掉了）比如3 00 01 001我的输出是11（这是错的)
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> #include<string> using namespace std; int cmp(const string& s1,const string& s2) { string temp1 = s1 + s2; string temp2 = s2 + s1; for(int i=0;i<temp1.length();++i) { if(temp1[i] != temp2[i]) return temp1[i] - temp2[i] < 0; } return 1; } int main() { //while(true) { vector<string> vs; int n; scanf("%d",&n); for(int i=0;i<n;++i) { char str[10]; scanf("%s",str); vs.push_back(str); } sort(vs.begin(),vs.end(),cmp); bool bFirst = true; for(int i=0;i<vs.size();++i) { if(bFirst) { int a = atoi(vs[i].c_str()); if(a==0 && i!= vs.size()-1) continue; printf("%d",a); bFirst = false; } else { printf("%s",vs[i].c_str()); } } printf(" "); } return 0; }
1044题：如果暴力会超时，主要代码中的bCanBreak的判断，当里层循环遍历到最后一个数字的时候，就直接跳出大循环。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; #define INF (1<<30) vector<int> vc; map<int,int> res; map<int,int> res2; int main() { int n,dst; scanf("%d%d",&n,&dst); for(int i=0;i<n;++i) { int a; scanf("%d",&a); vc.push_back(a); } int iMin = INF; bool bCanBreak = false; for(int i=0;i<n;++i) { int sum = 0; for(int j=i;j<n;++j) { sum += vc[j]; if(sum == dst) { res[i+1] = j+1; break; } else if(sum > dst) { if(iMin > sum) { iMin = sum; res2.clear(); } if(iMin == sum) { res2[i+1] = j+1; } break; } if(j==n-1) bCanBreak = true; } if(bCanBreak) break; } if(res.size()) { map<int,int>::iterator it = res.begin(); for(;it != res.end();it++) printf("%d-%d ",it->first,it->second); } else { map<int,int>::iterator it = res2.begin(); for(;it != res2.end();it++) printf("%d-%d ",it->first,it->second); } return 0; }
二刷的时候用的方法：计算res等于从第i个加到j个。然后每次减去第i个，发现res小于寻找的数时，加上j+1，j+2直到res>=寻找的数，然后重复以上步骤。
#include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> #include<algorithm> #include<map> #include<set> #include<vector> #include<climits> #include<iterator> using namespace std; #define N (100010) int n,m; int a[N]; int minM = INT_MAX; void print(int needm) { int res = 0; for(int i=0,j=0;i<n;++i) { while(res < needm&&j<n) res += a[j++]; if(res == needm) { printf("%d-%d ",i+1,j); minM = needm; } else if(minM!=needm&&res>needm&&res<minM) minM = res; res -= a[i]; } } int main() { #ifndef ONLINE_JUDGE freopen("1.txt","r",stdin); #endif // ONLINE_JUDGE scanf("%d%d",&n,&m); for(int i=0;i<n;++i) scanf("%d",&a[i]); print(m); if(minM!=m) { print(minM); } return 0; }
1045题：变异的lcs，卡了一下
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<map> #include<set> #include<algorithm> using namespace std; #define N (210) int main() { int n; bool bHave[N] = {false}; int m,l,love[N]; vector<int> vcColor; scanf("%d ",&n); scanf("%d",&m); for(int i=0;i<m;++i) { scanf("%d",&love[i]); bHave[love[i]] = true; } scanf("%d",&l); for(int i=0;i<l;++i) { int a; scanf("%d",&a); if(bHave[a]) vcColor.push_back(a); } n = vcColor.size(); int dp[m+1][n+1]; memset(dp,0,sizeof(dp)); for(int i=0;i<m;++i) for(int j=0;j<n;++j) { if(love[i]==vcColor[j]) { dp[i+1][j+1] = max(dp[i+1][j]+1,dp[i][j] + 1); } else { dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]); } } printf("%d ",dp[m][n]); return 0; }
1046题：如果是记录每个点到下一个点的距离，然后用累加法会超时，应该是记录每个点到起点的距离，然后相减就是他们之间的距离。同时要注意，假设a<b，a到b的距离有两种可能性，一种是a到b，另一种是b到终点，然后在到a。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; #define N (100010) int main() { int dis[N]; int n; scanf("%d",&n); int len = 0; for(int i=0;i<n;++i) { int a; scanf("%d",&a); len += a; dis[i+1] = len; } int m; scanf("%d",&m); while(m--) { int a,b; scanf("%d%d",&a,&b); if(a > b) swap(a,b); int l = 0; if(a != b) { l = dis[b-1] - dis[a-1]; } l = min(l,len-l); printf("%d ",l); } return 0; }
1047题：不能用set存储，最后一个case会超时，由于set每一次插入都会排一次序，使用vector来存储，然后输入结束后排一次序就可以了
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> #include<string> #include<iterator> using namespace std; #define N (40010) #define K (2510) int main() { int n,k; scanf("%d%d",&n,&k); vector<string> Course[k+1]; for(int i=0;i<n;++i) { char name[5]; int m; scanf("%s%d",name,&m); for(int j=0;j<m;++j) { int c; scanf("%d",&c); Course[c].push_back(name); } } for(int i=1;i<=k;++i) { printf("%d %d ",i,Course[i].size()); if(Course[i].size()) { sort(Course[i].begin(),Course[i].end()); } for(int j=0;j<Course[i].size();++j) { printf("%s ",Course[i][j].c_str()); } } return 0; }
1048题：面值可能会相等，比如 2 14 7 7输出是 7 7
#include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> #include<algorithm> #include<map> #include<set> #include<vector> #include<climits> #include<iterator> using namespace std; #define N (100010) int Hash[N]; int main() { #ifndef ONLINE_JUDGE freopen("1.txt","r",stdin); #endif // ONLINE_JUDGE int n,m; scanf("%d%d",&n,&m); for(int i=0;i<n;++i) { int a; scanf("%d",&a); ++Hash[a]; } for(int i=0;i<=m;++i) { if(Hash[i]&&Hash[m-i]) { if(i==m-i&&Hash[i]==1) continue; printf("%d %d ",i,m-i); return 0; } } printf("No Solution "); return 0; }
1052题：dfs，有一个坑点，当起点是一个在图中的值时，输出一个是 0 -1；
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; #define N (100010) struct Node { int addr; int key; int nextaddr; Node() { nextaddr = -1; addr = -1; } }; Node Map[N]; vector<Node> vc; int n,iStart; void dfs(int CurI) { if(CurI == -1 || Map[CurI].addr==-1) return; Node curnode = Map[CurI]; vc.push_back(curnode); dfs(curnode.nextaddr); } int cmp(const Node& n1,const Node& n2) { return n1.key - n2.key < 0; } int main() { scanf("%d%d",&n,&iStart); for(int i=0;i<n;++i) { Node node; scanf("%d%d%d",&node.addr,&node.key,&node.nextaddr); Map[node.addr] = node; } dfs(iStart); sort(vc.begin(),vc.end(),cmp); int nVcSize = vc.size(); printf("%d",nVcSize); if(nVcSize) printf(" %05d",vc[0].addr); else printf(" -1"); printf(" "); for(int i=0;i<nVcSize;++i) { printf("%05d %d ",vc[i].addr,vc[i].key); if(i != nVcSize-1) { printf("%05d ",vc[i+1].addr); } else printf("-1 "); } return 0; }
1053题：简单题，dfs，使用vector<vector<int> >存储答案路径，使用vector<int>[]存储图，然后在叶子节点加上一个结束节点，方便判断。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; #define N (110) int w[N]={0}; int n,m,s; vector<int> vcMap[N]; vector<vector<int> > vcPath; void dfs(int CurI,int tw,vector<int> vc) { if(CurI==n) { if(tw == s) { vcPath.push_back(vc); } return; } vc.push_back(w[CurI]); for(int i=0;i<vcMap[CurI].size();++i) { int NextI = vcMap[CurI][i]; dfs(NextI,tw+w[CurI],vc); } vc.pop_back(); } int cmp(const vector<int>& v1,const vector<int>& v2) { for(int i=0;i<v1.size()&&i<v2.size();++i) { if(v1[i] != v2[i]) return v1[i]-v2[i] > 0; } return 0; } int main() { scanf("%d%d%d",&n,&m,&s); for(int i=0;i<n;++i) scanf("%d",&w[i]); for(int i=0;i<m;++i) { int a,k,b; scanf("%d%d",&a,&k); for(int j=0;j<k;++j) { scanf("%d",&b); vcMap[a].push_back(b); } } //方便判断结束 for(int i=0;i<n;++i) if(vcMap[i].size()==0) vcMap[i].push_back(n); vector<int> vc; dfs(0,0,vc); sort(vcPath.begin(),vcPath.end(),cmp); for(int i=0;i<vcPath.size();++i) { vector<int> &vc2 = vcPath[i]; bool bFirst = true; for(int j=0;j<vc2.size();++j) { if(bFirst) bFirst = false; else printf(" "); printf("%d",vc2[j]); } printf(" "); } return 0; }
1055题：之前由于每次查询都去排序导致超时，傻了
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; struct ST { char name[10]; int age; int net; }; int cmp(const ST& st1,const ST& st2) { if(st1.net != st2.net) return st1.net-st2.net > 0; if(st1.age != st2.age) return st1.age - st2.age < 0; return strcmp(st1.name,st2.name)<0; } int main() { int n,k; scanf("%d%d",&n,&k); vector<ST> vc; for(int i=0;i<n;++i) { ST st; scanf("%s%d%d",st.name,&st.age,&st.net); vc.push_back(st); } sort(vc.begin(),vc.end(),cmp); for(int i=0;i<k;++i) { int m,amin,amax; scanf("%d%d%d",&m,&amin,&amax); printf("Case #%d: ",i+1); int iCnt = 0; for(int i=0;i<vc.size();++i) { if(iCnt == m) { break; } if(amin<=vc[i].age&&vc[i].age<=amax) { printf("%s %d %d ",vc[i].name,vc[i].age,vc[i].net); ++iCnt; } } if(iCnt==0) printf("None "); } return 0; }
1056题：不难，题目比较难理解：大致题意有np个老鼠，每次nc只一组选出最大的，最后不满nc的算一组。反复，直到求得最大质量的老鼠。第二行输入表示从0到np的老鼠质量，第三行输入表示第几只老鼠。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; struct ST { int i; int w; int iRank; }; int cmp(const ST& st1,const ST& st2) { return st1.i-st2.i<0; } int main() { int np,nc; scanf("%d%d",&np,&nc); int w[np]; ST st[np]; vector<ST*> vc; vector<vector<ST*> > vcRes; for(int i=0;i<np;++i) scanf("%d",&w[i]); for(int i=0;i<np;++i) { scanf("%d",&st[i].i); st[i].w = w[st[i].i]; vc.push_back(&st[i]); } while(vc.size()>1) { vector<ST*> vcTemp = vc; vc.clear(); int i=0; vector<ST*> oneRes; while(i<vcTemp.size()) { ST* bigone = NULL; for(int j=0;j<nc&&i<vcTemp.size();++j,++i) { if(bigone==NULL) { bigone = vcTemp[i]; } else if(bigone->w < vcTemp[i]->w) { oneRes.push_back(bigone); bigone = vcTemp[i]; } else { oneRes.push_back(vcTemp[i]); } } vc.push_back(bigone); } vcRes.push_back(oneRes); } int iCurRank = 1; if(vc.size()) vc[0]->iRank = iCurRank++; for(int i=vcRes.size()-1;i>=0;--i) { for(int j=0;j<vcRes[i].size();++j) vcRes[i][j]->iRank = iCurRank; iCurRank += vcRes[i].size(); } sort(st,st+np,cmp); for(int i=0;i<np;++i) if(i) printf(" %d",st[i].iRank); else printf("%d",st[i].iRank); return 0; }
1057题：分块搜索第k大的数字。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; const char strPop[10] = "Pop"; const char strPush[10] = "Push"; const char strPeek[20] = "PeekMedian"; #define N (100010) #define BLOCK 400 int block[400]={0}; int table[N]={0}; int FindK(int k) { int cnt = 0; int i; for(i=0;i<400;++i) { if(cnt + block[i] >= k) break; cnt += block[i]; } for(int j=i*BLOCK;j<N;++j) { cnt += table[j]; if(cnt >= k) //易错（之前是cnt==k），最后两个case就过不了了 return j; } return 0; } int main() { int n; scanf("%d",&n); vector<int> vc; for(int i=0;i<n;++i) { char cmd[20]; scanf("%s",&cmd); if(strcmp(cmd,strPop)==0) { if(vc.size()==0) { printf("Invalid "); } else { int key = vc[vc.size()-1]; printf("%d ",key); if(table[key]) --table[key]; if(block[key/BLOCK]) --block[key/BLOCK]; vc.pop_back(); } } else if(strcmp(cmd,strPush)==0) { int num; scanf("%d",&num); vc.push_back(num); ++table[num]; ++block[num/BLOCK]; } else { if(vc.size()==0) { printf("Invalid "); } else { int k = vc.size(); int iMid = k%2==0 ? k/2 : (k+1)/2; int iRes = FindK(iMid); printf("%d ",iRes); } } } return 0; } /* 17 Push 6 Push 6 Push 7 PeekMedian */
1060题：题目还是挺难的，思路：
1、删除输入数字之前的0，例如像00014这样的数组
2、寻找小数点的位置dot，如果没有找到小数点，则位数等于字符串长度，如果找到了，位数等于dot。然后遍历字符串，如果发现前导0则去掉，位数减一，如果发现小数点，位数不变。这种算法需要考虑特殊情况0,如果发现是0，则位数强制赋值成0，不然位数时-1。
3、在第二步计算位置的同时并且去掉前导0和小数点，然后对剩下的数字进行n为输出，不够补0，超过截取。
4、0可以表示成 0.000*10^3，so。。。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<map> #include<set> #include<algorithm> using namespace std; string getstr(string str,int m) { int dot = str.find("."); int len = str.length(); int wei = dot==-1?len:dot; string res = str; str = ""; for(int i=0;i<len;++i) { if(res[i]=='0') --wei; else if(res[i]!='.') { res = res.substr(i,len-i); len = res.length(); str = ""; for(int j=0;j<len;++j) if(res[j]!='.') str+=res[j]; break; } } len = str.length(); if(len==0) wei = 0; { res = "0."; int i; for(i=0;i<len&&i<m;++i) res += str[i]; for(;i<m;++i) res += "0"; char subfix[20]; sprintf(subfix,"*10^%d",wei); res += subfix; } return res; } int main() { #ifdef ONLINE_JUDGE #else freopen("test.txt","r",stdin); #endif int n; char str1[200],str2[200]; scanf("%d%s%s",&n,str1,str2); string res1 = getstr(str1,n),res2=getstr(str2,n); if(strcmp(res1.c_str(),res2.c_str())==0) printf("YES %s ",res1.c_str()); else printf("NO %s %s ",res1.c_str(),res2.c_str()); return 0; }
1061题：题目难懂，题目大致意思，第1个字符串和第2个字符串第一个共有字符表示哪一天（该字符要求A-F），第二个共同字符表示时间（0-9，A-N）,第3个共同字符在第3和第4字符串中找（位置表示时间,0开始）
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> #include<string> using namespace std; bool isEnglish(char c) { if(c>='a'&&c<='z') return true; if(c>='A'&&c<='Z') return true; return false; } bool isBigEnglish(char c) { if(c>='A'&&c<='Z') return true; return false; } bool isNum(char c) { if(c>='0'&&c<='9') return true; return false; } int getPos(char c) { if(c>='a'&&c<='z') return c-'a'+1; if(c>='A'&&c<='Z') return c-'A'+1; return 0; } int main() { string weeks[] = {"","MON","TUE","WED","THU","FRI","SAT","SUN"}; char s1[65],s2[65],s3[65],s4[65]; scanf("%s%s%s%s",s1,s2,s3,s4); int week = 0,iWeek=0,h=0,m=0; int i; for(i=0;i<strlen(s1)&&i<strlen(s2);++i) { if(s1[i]==s2[i]&&isBigEnglish(s1[i])&&s1[i]<='G') { iWeek = i; week = getPos(s1[i]); week = (week-1)%7+1; break; } } for(i=i+1;i<strlen(s1)&&i<strlen(s2);++i) { if(s1[i]==s2[i]&&(isNum(s1[i])||(isBigEnglish(s1[i])&&s1[i]<='N'))) { if(isNum(s1[i])) { h = s1[i]-'0'; } else { h = s1[i]-'A'+10; } break; } } for(i=0;i<strlen(s3)&&i<strlen(s4);++i) { if(s3[i]==s4[i]&&isEnglish(s3[i])) { m = i; break; } } printf("%s %02d:%02d ",weeks[week].c_str(),h,m); return 0; }
1063题：正常情况会超时，所以不能把交集和并集全求出来，只能求出交集个数，然后通过减法得到并集个数。2种解法：
1、通过set_intersection函数求：
#include<iostream> #include<cstring> #include<cstdio> #include<set> #include<algorithm> using namespace std; int main() { int n,m; scanf("%d",&n); set<int> si[n]; for(int i=0;i<n;++i) { scanf("%d",&m); for(int j=0;j<m;++j) { int temp; scanf("%d",&temp); si[i].insert(temp); } } int k; scanf("%d",&k); for(int i=0;i<k;++i) { int s,e; set<int> ss,st; scanf("%d%d",&s,&e); --s,--e; //交集 set_intersection(si[s].begin(),si[s].end(),si[e].begin(),si[e].end(), inserter(ss,ss.begin())); //并集 /*set_union(si[s].begin(),si[s].end(),si[e].begin(),si[e].end(), inserter(st,st.begin())); */ int same = ss.size(); int total = si[s].size()+si[e].size()-same;//st.size(); if(total==0) printf("0.0%% "); else printf("%.1lf%% ",100.0*same/total); } return 0; }
2、通过自己写求交集的函数，具体实现看代码
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; void getInsert(set<int> &in_set,const set<int> &s1,const set<int> &s2) { set<int>::iterator it1 = s1.begin(); set<int>::iterator it2 = s2.begin(); while(it1!=s1.end()&&it2!=s2.end()) { if(*it1==*it2) { in_set.insert(*it1); it1++; it2++; } else if(*it1 > *it2) it2++; else it1++; } } int main() { int n; scanf("%d",&n); set<int> s[n]; for(int i=0;i<n;++i) { int m; scanf("%d",&m); for(int j=0;j<m;++j) { int a; scanf("%d",&a); s[i].insert(a); } } int k; scanf("%d",&k); for(int i=0;i<k;++i) { int a,b; scanf("%d%d",&a,&b); if(a==b) printf("0.00%% "); else { --a; --b; set<int> si; getInsert(si,s[a],s[b]); double fRes = 100.0*si.size()/(s[a].size()+s[b].size()-si.size()); printf("%.1lf%% ",fRes); } } return 0; }
1065题：用long long判断，通过判断溢出来判断大小，但是a+b的值需要用中间值保存，不然你只有可怜的12分。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> #include<climits> using namespace std; int main() { //freopen("test.txt","r",stdin); int T; scanf("%d",&T); for(int t=1;t<=T;++t) { long long int a,b,c; scanf("%lld%lld%lld",&a,&b,&c); bool bBig = true; /* 错误，a+b需要赋值，具体为什么我也不知道 if(a>0&&b>0&&a+b<=0) bBig = true; else if(a<0&&b<0&&a+b>=0) bBig = false; else bBig =a+b>c; */ long long res = a+b; if(a>0&&b>0&&res<=0) bBig = true; else if(a<0&&b<0&&res>=0) bBig = false; else bBig =res>c; printf("Case #%d: %s ",t,bBig?"true":"false"); } return 0; }
很神奇的是用long double也能过(注意不是double)
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> #include<climits> using namespace std; int main() { //freopen("test.txt","r",stdin); int T; scanf("%d",&T); for(int t=1;t<=T;++t) { long double a,b,c; scanf("%llf%llf%llf",&a,&b,&c); bool bBig = a+b>c; printf("Case #%d: %s ",t,bBig?"true":"false"); } return 0; }
1067题：0所在的b，b所在位置是b2，把0放到b2的位置，把b放到b的位置。数组a,a[b]=i表示数字b在i位置。不用去管他最小交换个数，当0交换到0位置后，如果没有有序，则0先跟任意未排序好的数字交换位置，然后重复交换。用set保存未有序的数字。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; int main() { //freopen("test.txt","r",stdin); int n; scanf("%d",&n); int a[n],cnt=0; set<int> si; for(int i=0;i<n;++i) { int b; scanf("%d",&b); a[b] = i; if(b==i&&b) ++cnt; else if(b!=i&&b) si.insert(b); } int step=0; while(cnt < n-1) { if(a[0]==0) { int i = *(si.begin()); if(a[i]!=i) { int b1 = a[i]; //i在b1位置 a[0] = b1; //0移到b1位置 a[i] = 0; //i移到0位置 } } else { int b1 = a[0]; //0在b1位置 int b2 = a[b1]; //b1在b2位置 a[0] = b2; a[b1] = b1; si.erase(si.find(b1)); ++cnt; } ++step; } printf("%d ",step); return 0; }
1068题：01背包，主要找路径时比较路径序号小的判断可能会搞错。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; bool cmp(vector<int> v1,vector<int> v2) { for(int i=0;i<v1.size()&&i<v2.size();++i) { if(v1[i] != v2[i]) return v1[i] > v2[i]; } return false; } int main() { //freopen("test.txt","r",stdin); int n,m; scanf("%d%d",&n,&m); int dp[m+1]; vector<int> path[m+1]; for(int i=0;i<=m;++i) dp[i] = -1; int c[n]; for(int i=0;i<n;++i) scanf("%d",&c[i]); dp[0] = 0; sort(c,c+n); for(int i=0;i<n;++i) { for(int v=m;v>=c[i];--v) if(dp[v-c[i]]>=0) { if(dp[v] < dp[v-c[i]]+c[i]) { dp[v] = dp[v-c[i]]+c[i]; path[v] = path[v-c[i]]; path[v].push_back(c[i]); } if(dp[v] == dp[v-c[i]]+c[i]&&cmp(path[v],path[v-c[i]])) { dp[v] = dp[v-c[i]]+c[i]; path[v] = path[v-c[i]]; path[v].push_back(c[i]); } } } if(dp[m] != m) { printf("No Solution "); } else { for(int i=0;i<path[m].size();++i) { if(i) printf(" "); printf("%d",path[m][i]); } } return 0; }
1070题：不难，就是略坑，数量需要用double存储，用int一个case过不了。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; typedef struct mooncake { double num; double fprice; }; int cmp(const mooncake& m1,const mooncake& m2) { if(m1.num == 0) { return 1; } else if(m2.num == 0) { return 0; } return 1.0*m1.fprice/m1.num > 1.0*m2.fprice/m2.num; } int main() { int n,d; scanf("%d%d",&n,&d); mooncake mc[n]; for(int i=0;i<n;++i) scanf("%lf",&mc[i].num); for(int i=0;i<n;++i) scanf("%lf",&mc[i].fprice); sort(mc,mc+n,cmp); double sum = 0; int i = 0; while(d>=0&&i<n) { if(mc[i].num==0||mc[i].fprice==0) { } else if(d >= mc[i].num) { d -= mc[i].num; sum += mc[i].fprice; } else { sum += (mc[i].fprice*(1.0*d/mc[i].num)); d = 0; } ++i; } printf("%.2lf ",sum); return 0; }
1071题：恶心之处就在于不能在循环条件中使用strlen函数，否则超时
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> #include<string> using namespace std; #define N (1048576+10) bool isAlphanum(char c) { if(c>='0'&&c<='9') return true; if(c>='a'&&c<='z') return true; if(c>='A'&&c<='Z') return true; return false; } char ToLower(char c) { if(c>='A'&&c<='Z') c = 'a' + c-'A'; return c; } int main() { char str[N]; fgets(str,sizeof(str),stdin); map<string,int> msi; int num = 0; string res = ""; string word = ""; int iStrLen = strlen(str); for(int i=0;i<iStrLen;++i) { char c = ToLower(str[i]); if(isAlphanum(c)==false) continue; word += c; if(isAlphanum(str[i+1])==false) { int tempcnt = ++msi[word]; if((num==tempcnt&&word.length()<res.length())||num<tempcnt) { num = tempcnt; res = word; } word = ""; } } if(res!="") { printf("%s %d ",res.c_str(),num); } return 0; }
1072题：题目不好理解，不难。1、求每个gas到house的最短距离，求最短距离中的最大。如果相等，求平均距离最小的。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<map> #include<set> #include<algorithm> #include<cstring> #include<climits> using namespace std; #define N (1100) int GetNo(char *str) { int add = 0; if(str[0]=='G') ++str,add=1000; return add+atoi(str); } int n,m,k,ds; int Map[N][N]={0}; int dp[N]; bool bVis[N]; void Dijkstra(int iStart) { for(int i=1;i<N;++i) dp[i] = Map[iStart][i]; for(int i=1;i<N;++i) { int iMindj = INT_MAX,iPos = iStart; for(int j=1;j<N;++j) { if(!bVis[j]&&iMindj>dp[j]) { iMindj = dp[j]; iPos = j; } } bVis[iPos] = true; if(dp[iPos] > ds) return; for(int j=1;j<N;++j) { //printf("dp[%d]=%d,dp[%d]=%d Map[%d][%d]=%d ",j,dp[j],iPos,dp[iPos],iPos,j,Map[iPos][j]); if(!bVis[j]&&Map[iPos][j]!=INT_MAX&&dp[j]>dp[iPos]+Map[iPos][j]) { dp[j] = dp[iPos] + Map[iPos][j]; //printf("res=%d ",dp[j]); } } } } int main() { for(int i=0;i<N;++i) for(int j=0;j<N;++j) if(i==j) Map[i][j] = 0; else Map[i][j] = INT_MAX; scanf("%d%d%d%d",&n,&m,&k,&ds); for(int i=0;i<k;++i) { char str1[10],str2[10]; int d; scanf("%s%s%d",str1,str2,&d); int a = GetNo(str1); int b = GetNo(str2); Map[a][b] = Map[b][a] = d; } int iMinSum = INT_MAX,iGas=-1,iMinPath=-1; for(int i=0;i<m;++i) { int gas = 1001+i; memset(bVis,0,sizeof(bVis)); bVis[gas] = true; Dijkstra(gas); int j,Sum=0,iPath=INT_MAX; for(j=1;j<=n;++j) { //printf("gas=%d j=%d dp[j]=%d ",gas,j,dp[j]); if(dp[j]>ds) break; Sum += dp[j]; if(iPath > dp[j]) iPath = dp[j]; } if(j > n && (iMinPath < iPath||(iMinPath == iPath && iMinSum > Sum))) { iGas = gas; iMinSum = Sum; iMinPath = iPath; } } if(iGas==-1) printf("No Solution "); else { printf("G%d ",iGas-1000); printf("%.1lf %.1lf ",1.0*iMinPath,1.0*iMinSum/n); } return 0; }
1074题：稍微有点麻烦，dfs就可以了
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<map> #include<set> #include<algorithm> using namespace std; #define N (100010) struct ST { int addr; int val; int nextaddr; ST() { nextaddr = -1; } }; ST st[N]; bool bVis[N] = {true}; int iStart,n,k; vector<int> res; void travel(int iCurI,vector<int> vi) { //printf("CurI=%05d ",iCurI); if(iCurI==-1 || bVis[iCurI]) { if(vi.size()==k) for(int i=vi.size()-1;i>=0;--i) { res.push_back(vi[i]); } else { for(int i=0;i<vi.size();++i) { res.push_back(vi[i]); } } return; } else if(vi.size()==k) { for(int i=vi.size()-1;i>=0;--i) { res.push_back(vi[i]); } vi.clear(); } bVis[iCurI] = true; vi.push_back(iCurI); int iNextI = st[iCurI].nextaddr; travel(iNextI,vi); } int main() { scanf("%d%d%d",&iStart,&n,&k); for(int i=0;i<n;++i) { int iaddr,v,inext; scanf("%d%d%d",&iaddr,&v,&inext); st[iaddr].val = v; st[iaddr].nextaddr = inext; st[iaddr].addr = iaddr; bVis[iaddr] = false; } vector<int> tempvi; travel(iStart,tempvi); for(int i=0;i<res.size();++i) { int ID = res[i]; if(i != res.size()-1) { int iNextID = res[i+1]; printf("%05d %d %05d ",ID,st[ID].val,iNextID); } else printf("%05d %d -1 ",ID,st[ID].val); } return 0; }
1075题：题目说明不清楚，坑点：当得分是-1时，表示编译未通过，在结果集中编译未通过的输出0，未提交的输出 -，当参赛者没有提交题目时，结果集中不输出此用户。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<map> #include<set> #include<algorithm> using namespace std; #define K (6) int prom[K]={100000000}; int n,k,m; struct PAT { int id; int grade[K]; PAT() { for(int i=1;i<=k;++i) grade[i] = -2; } bool bUseful() { for(int i=1;i<=k;++i) if(grade[i]>=0) return true; return false; } int getSum() const { int sum = 0; for(int i=1;i<=k;++i) if(grade[i]>=0) sum+=grade[i]; return sum; } int getPerfectNum() const { int res = 0; for(int i=1;i<=k;++i) if(grade[i]>=prom[i]) ++res; return res; } void Print() { printf("%05d %d",id,getSum()); for(int i=1;i<=k;++i) if(grade[i]==-1) printf(" 0"); else if(grade[i]==-2) printf(" -"); else printf(" %d",grade[i]); printf(" "); } }; int cmp(const PAT& p1,const PAT& p2) { if(p1.getSum()!=p2.getSum()) return p1.getSum()>p2.getSum(); if(p1.getPerfectNum()!=p2.getPerfectNum()) return p1.getPerfectNum() > p2.getPerfectNum(); return p1.id < p2.id; } map<int,PAT> mip; vector<PAT> vc; int main() { scanf("%d%d%d",&n,&k,&m); for(int i=1;i<=k;++i) scanf("%d",&prom[i]); for(int i=0;i<m;++i) { int ID,proID,sorce; scanf("%d%d%d",&ID,&proID,&sorce); if(ID <= n) { PAT &pat = mip[ID]; pat.id = ID; if(pat.grade[proID] < sorce) { pat.grade[proID] = sorce; } } } map<int,PAT>::iterator it = mip.begin(); for(;it!=mip.end();it++) { if(it->second.bUseful()) { vc.push_back(it->second); } } sort(vc.begin(),vc.end(),cmp); PAT temp; vc.push_back(temp); //加入一个哨兵，便于判断 int iCurRank = 1; for(int i=0;i<vc.size()-1;++i) { printf("%d ",iCurRank); vc[i].Print(); if(vc[i].getSum() != vc[i+1].getSum()) iCurRank = i+2; } return 0; }
1077题：我以为是公有单词的后缀，没想到都不需要考虑是不是单词，想得多反而错误了
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<map> #include<set> #include<algorithm> using namespace std; int main() { vector<string> vs; int n; scanf("%d",&n); getchar(); for(int i=0;i<n;++i) { char str[300]; fgets(str,sizeof(str),stdin); vs.push_back(str); } vector<char> res; bool bOK = true; for(int i=0;i<300 && bOK;++i) { char c; for(int j=0;j<vs.size();++j) { int len = vs[j].length(); int iCurI = len - i -1; if(iCurI < 0) { bOK = false; break; } if(vs[j][iCurI]==' ') { //考虑了单词，其实空格也算公有的一部分 //bOK = false; //break; } if(j==0) c = vs[j][iCurI]; else if(vs[j][iCurI] != c) { bOK = false; break; } } if(bOK==true) { res.push_back(c); } } if(res.size()==1) printf("nai "); else { for(int i=res.size()-1;i>=0;--i) if(res[i]!=' ') printf("%c",res[i]); printf(" "); } return 0; }
1088题：用就可以了long long
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<map> #include<set> #include<algorithm> using namespace std; struct Fen { long long int a; long long int b; }; long long gcd(long long a,long long b) { if(a < 0) a = -a; if(b < 0) b = -b; if(b==0) return a; return gcd(b,a%b); } long long bei(long long a,long long b) { if(a < 0) a = -a; if(b < 0) b = -b; return a/gcd(a,b)*b; } int main() { int n; scanf("%d",&n); vector<Fen> vc; for(int i=0;i<n;++i) { Fen fen; scanf("%lld/%lld",&fen.a,&fen.b); if(fen.a&&fen.b) vc.push_back(fen); } long long com = 1; for(int i=0;i<vc.size();++i) { com = bei(com,vc[i].b); } long long son = 0; for(int i=0;i<vc.size();++i) { son += com/vc[i].b*vc[i].a; } if(son == 0) printf("0 "); else { long long temp = gcd(son,com); son = son/temp; com = com/temp; bool bN = false; if(son > 0 && com <0 || son<0 && com>0) { bN = true; if(son<0) son = -son; if(com<0) com = -com; } if(son/com>0) { if(bN) printf("-"); printf("%lld",son/com); son = son%com; if(son) printf(" "); } else if(bN) printf("-"); if(son) { printf("%lld/%lld",son,com); } printf(" "); } return 0; }
1082题 108 yi Bai ling ba 1008 yi Qian ling ba
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; const int YI = 100000000; const int WAN = 10000; string strNum[] = {"ling","yi","er","san","si","wu","liu","qi","ba","jiu"}; void Print(long long int n) { if(n>=1000) { printf("%s Qian",strNum[n/1000].c_str()); n = n%1000; if(n) { printf(" "); if(n<100) printf("ling "); } } if(n>=100) { printf("%s Bai",strNum[n/100].c_str()); n=n%100; if(n) { printf(" "); if(n<10) printf("ling "); } } if(n>=10) { printf("%s Shi",strNum[n/10].c_str()); n = n%10; if(n) printf(" "); } if(n) printf("%s",strNum[n].c_str()); } int main() { long long int n; scanf("%lld",&n); if(n==0) printf("ling "); else { if(n<0) { printf("Fu "); n = -n; } if(n>=YI) { printf("%s Yi",strNum[n/YI].c_str()); n = n%YI; if(n) if(n<10000000) printf(" ling "); else printf(" "); } if(n>=WAN) { Print(n/WAN); printf(" Wan"); n = n%WAN; if(n) if(n<1000) printf(" ling "); else printf(" "); } if(n) Print(n); printf(" "); } return 0; }
1084题：123 12这个容易错
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; char toBig(char c) { if('a'<=c&&c<='z') return c-'a'+'A'; return c; } int main() { char str1[100],str2[100]; scanf("%s%s",str1,str2); int i=0,j=0; int len1=strlen(str1),len2=strlen(str2); string res=""; set<char> sc; for(;i<len1;) { char c1 = toBig(str1[i]); char c2 = '@'; if(j<len2) { c2 = toBig(str2[j]); } if(c1==c2) ++i,++j; else { if(sc.find(c1)==sc.end()) { sc.insert(c1); res += c1; } ++i; } } printf("%s ",res.c_str()); return 0; }
1087题：容易超时
dfs的解法：
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> #include<climits> using namespace std; #define N (26*26*26+10) int toNum(char* str) { return (str[0]-'A')*26*26+(str[1]-'A')*26+(str[2]-'A'); } int hap[N] = {0}; int Map[N][N]; bool bVis[N] = {false}; int n,k; char strStart[4]; vector<int> vc[N]; string toStr(int n) { char str[4]={' '}; str[0] = n/26/26+'A'; str[1] = n/26%26 + 'A'; str[2] = n%26 + 'A'; return str; } int iMaxHap = 0; int iMinCost = INT_MAX; int paths = 0; int dst = toNum("ROM"); vector<int> vcRes; void dfs(int iCurI,int iCost,int h,vector<int> v) { //printf("%s cost=%d iMincost=%d h=%d iMaxHap=%d ",toStr(iCurI).c_str(),iCost,iMinCost,h,iMaxHap); if(iCost == iMinCost && iCurI==dst) { ++paths; } else if(iCost < iMinCost && iCurI == dst) { paths = 1; } if(iCost > iMinCost || (iCost==iMinCost&&h<iMaxHap) || (iCost==iMinCost&&h==iMaxHap&&v.size()>vcRes.size())|| (iCost==iMinCost&&h==iMaxHap&&v.size()==vcRes.size())/*这一行不加容易超时*/) return; if(iCurI==dst) { //printf("minCost=%d maxHap=%d ",iMinCost,iMaxHap); vcRes = v; iMinCost = iCost; iMaxHap = h; return; } bVis[iCurI] = true; for(int i=0;i<vc[iCurI].size();++i) { int iNextI = vc[iCurI][i]; if(!bVis[iNextI]) { v.push_back(iNextI); dfs(iNextI,iCost+Map[iCurI][iNextI],h+hap[iNextI],v); v.pop_back(); } } bVis[iCurI] = false; } int main() { scanf("%d%d%s",&n,&k,strStart); for(int i=0;i<n-1;++i) { char str[4]; int h; scanf("%s%d",str,&h); int iStr = toNum(str); hap[iStr] = h; } for(int i=0;i<k;++i) { char str1[4],str2[4]; int a,b,len; scanf("%s%s%d",str1,str2,&len); a = toNum(str1); b = toNum(str2); //if(Map[a][b]==0) { vc[a].push_back(b); vc[b].push_back(a); } Map[a][b] = Map[b][a] = len; } vector<int> temp; temp.push_back(toNum(strStart)); dfs(toNum(strStart),0,0,temp); if(vcRes.size()>1) { printf("%d %d %d %d ",paths,iMinCost,iMaxHap,iMaxHap/(vcRes.size()-1)); } for(int i=0;i<vcRes.size();++i) { if(i) printf("->"); printf("%s",toStr(vcRes[i]).c_str()); } printf(" "); return 0; }
dijkstra方法：不容易理解，而且容易出错，但是效率高，自己把地名转换成数字。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<map> #include<set> #include<climits> #include<algorithm> using namespace std; #define N (210) map<int,string> mis; map<string,int> msi; int n; int H[N]={0}; bool bVis[N]={0}; int Map[N][N]; struct ST { int cost; int hap; int pre; int cnt; int iStep; ST() { hap = 0; pre = 0; cnt = 1; iStep = 1; } }; ST dp[N]; void dijstra() { for(int i=0;i<n;++i) { dp[i].cost = Map[0][i]; dp[i].hap = H[i]; } for(int i=1;i<n;++i) { int minDj = INT_MAX,pos = 0; for(int j=1;j<n;++j) { if(!bVis[j]&&dp[j].cost < minDj) { minDj = dp[j].cost; pos = j; } } bVis[pos] = true; for(int j=1;j<n;++j) { if(!bVis[j]&&Map[pos][j]!=INT_MAX) { if(dp[j].cost > dp[pos].cost + Map[pos][j]) { dp[j].cost = dp[pos].cost + Map[pos][j]; dp[j].pre = pos; dp[j].hap = dp[pos].hap + H[j]; dp[j].cnt = dp[pos].cnt; dp[j].iStep = dp[pos].iStep+1; } else if(dp[j].cost == dp[pos].cost + Map[pos][j]) { dp[j].cnt += dp[pos].cnt; if(dp[j].hap < dp[pos].hap+H[j]) { dp[j].hap = dp[pos].hap+H[j]; dp[j].pre = pos; dp[j].iStep = dp[pos].iStep+1; } else if(dp[j].hap == dp[pos].hap+H[j] && dp[j].iStep > dp[pos].iStep+1) { dp[j].pre = pos; dp[j].iStep = dp[pos].iStep+1; } } } } } } int main() { int k; char strStart[4]; scanf("%d%d%s",&n,&k,strStart); msi[strStart] = 0; mis[0] = strStart; for(int i=1;i<n;++i) { char str[4]; scanf("%s%d",str,&H[i]); msi[str] = i; mis[i] = str; } for(int i=0;i<n;++i) for(int j=0;j<n;++j) if(i==j) Map[i][j] = 0; else Map[i][j] = INT_MAX; for(int i=0;i<k;++i) { char s1[4],s2[4]; int cost; scanf("%s%s%d",s1,s2,&cost); int a1 = msi[s1],a2=msi[s2]; Map[a1][a2] = Map[a2][a1] = cost; } int dst = msi["ROM"]; dijstra(); printf("%d %d %d %d ",dp[dst].cnt,dp[dst].cost,dp[dst].hap,dp[dst].hap/dp[dst].iStep); vector<int> res; for(int i=dst;i!=0;i=dp[i].pre) { res.push_back(i); } res.push_back(0); bool bFirst = true; for(int i=res.size()-1;i>=0;--i) { if(bFirst) bFirst = false; else printf("->"); printf("%s",mis[res[i]].c_str()); } printf(" "); return 0; }
1088题：输入也要简化，只顾输出化简了，所以会有一个case过不了
#include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> #include<algorithm> #include<map> #include<set> #include<vector> #include<climits> #include<iterator> using namespace std; long long gcd(long long a,long long b) { if(b==0) return a; return gcd(b,a%b); } string getstr(long long a) { char str[100]; sprintf(str,"%lld",a); return str; } struct Fen { long long a; long long b; void change() { if(b==0) return; if(b<0) a = -a,b=-b; long long g = gcd(abs(a),b); a = a/g; b = b/g; } string gettext() { change(); if(b==0) { return "Inf"; } else if(a==0) { return "0"; } long long ia = abs(a),ib = b; string res = ""; if(a<0) res="(-"; if(ib==1) res += getstr(ia); else { long long k = ia/ib; ia = ia%ib; if(k>0) res = res + getstr(k) + " "; res = res + getstr(ia) + "/" + getstr(ib); } if(a<0) res+=")"; return res; } }; Fen add(Fen f1,Fen f2) { Fen f; f.a = f1.a*f2.b + f2.a*f1.b; f.b = f1.b*f2.b; return f; } Fen jian(Fen f1,Fen f2) { Fen f; f.a = f1.a*f2.b - f2.a*f1.b; f.b = f1.b*f2.b; return f; } Fen cheng(Fen f1,Fen f2) { Fen f; f.a = f1.a*f2.a; f.b = f1.b*f2.b; return f; } Fen chu(Fen f1,Fen f2) { Fen f; f.a = f1.a*f2.b; f.b = f1.b*f2.a; return f; } int main() { #ifndef ONLINE_JUDGE freopen("1.txt","r",stdin); #endif // ONLINE_JUDGE Fen f1,f2; scanf("%lld/%lld",&f1.a,&f1.b); scanf("%lld/%lld",&f2.a,&f2.b); Fen f; f = add(f1,f2); printf("%s + %s = %s ",f1.gettext().c_str(),f2.gettext().c_str(),f.gettext().c_str()); f = jian(f1,f2); printf("%s - %s = %s ",f1.gettext().c_str(),f2.gettext().c_str(),f.gettext().c_str()); f = cheng(f1,f2); printf("%s * %s = %s ",f1.gettext().c_str(),f2.gettext().c_str(),f.gettext().c_str()); f = chu(f1,f2); printf("%s / %s = %s ",f1.gettext().c_str(),f2.gettext().c_str(),f.gettext().c_str()); return 0; }
1089题：case2是插入排序，。。。分治排序跟正常的2分分治不一样。使用最暴力的解法就行了。case是这样的比如2 1 3 4 5 9 8。
#include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> #include<algorithm> #include<map> #include<set> #include<vector> #include<climits> #include<iterator> using namespace std; bool equalarr(int* a,int* b,int n) { for(int i=0;i<n;++i) if(a[i]!=b[i]) return false; return true; } /* 1 2 3 4 9 7 1 2 3 4 9 7 */ bool isInsert(int* a,int* b,int n) { int temp[n]; memcpy(temp,a,sizeof(temp)); for(int i=2;i<=n;++i) { bool bEqu = equalarr(temp,b,n); sort(temp,temp+i); //比如1 2 3 4 9 7，你排到i=2的时候就相等了，但是我们期望的是i=5的时候。 if(bEqu&&!equalarr(temp,b,n)) { printf("Insertion Sort "); for(int j=0;j<n;++j) { if(j) printf(" "); printf("%d",temp[j]); } return true; } } printf("Merge Sort "); return false; } int main() { #ifndef ONLINE_JUDGE freopen("1.txt","r",stdin); #endif // ONLINE_JUDGE int n; scanf("%d",&n); int a[n],b[n]; for(int i=0;i<n;++i) scanf("%d",&a[i]); for(int i=0;i<n;++i) scanf("%d",&b[i]); bool bInsert = isInsert(a,b,n); if(!bInsert) { for(int len=2;;len*=2) { bool bequ = equalarr(a,b,n); for(int i=0;i<n;i+=len) { sort(a+i,a+min((i+len),n)); } if(bequ) { for(int i=0;i<n;++i) { if(i) printf(" "); printf("%d",a[i]); } printf(" "); break; } } } return 0; }
1091题：用dfs会导致最后两个是段错误，因为dfs在图很大的时候回爆栈（递归太多）。数组如果是a[65][1300][130]会超时，a[1300][130][65]就会正常，注意了。使用非递归的bfs。其实我觉得像拓扑排序。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> #include<queue> using namespace std; int m,n,l,t; int a[1300][130][65]; struct Point { int l; int m; int n; Point(int l,int m,int n) { this->l = l; this->m = m; this->n = n; } }; bool bOK(int curl,int curm,int curn) { if(curl<0||curl>=l||curm<0||curm>=m||curn<0||curn>=n) return false; if(a[curm][curn][curl]==0) return false; return true; } int bfs(int curl,int curm,int curn) { int cnt = 0; Point p(curl,curm,curn); if(bOK(p.l,p.m,p.n)==false) return 0; a[curm][curn][curl]=0; queue<Point> qi; qi.push(p); while(!qi.empty()) { p = qi.front(); qi.pop(); ++cnt; if(bOK(p.l+1,p.m,p.n)) { qi.push(Point(p.l+1,p.m,p.n)); a[p.m][p.n][p.l+1] = 0; } if(bOK(p.l-1,p.m,p.n)) { qi.push(Point(p.l-1,p.m,p.n)); a[p.m][p.n][p.l-1] = 0; } if(bOK(p.l,p.m+1,p.n)) { qi.push(Point(p.l,p.m+1,p.n)); a[p.m+1][p.n][p.l] = 0; } if(bOK(p.l,p.m-1,p.n)) { qi.push(Point(p.l,p.m-1,p.n)); a[p.m-1][p.n][p.l] = 0; } if(bOK(p.l,p.m,p.n+1)) { qi.push(Point(p.l,p.m,p.n+1)); a[p.m][p.n+1][p.l] = 0; } if(bOK(p.l,p.m,p.n-1)) { qi.push(Point(p.l,p.m,p.n-1)); a[p.m][p.n-1][p.l] = 0; } } return cnt>=t?cnt:0; } int main() { #ifdef ONLINE_JUDGE #else freopen("test.txt","r",stdin); #endif // ONLINE_JUDGE scanf("%d%d%d%d",&m,&n,&l,&t); for(int i=0;i<l;++i) for(int j=0;j<m;++j) for(int k=0;k<n;++k) scanf("%d",&a[j][k][i]); int res=0; for(int i=0;i<l;++i) for(int j=0;j<m;++j) for(int k=0;k<n;++k) { res += bfs(i,j,k); } printf("%d ",res); return 0; }
1095题：模拟题，需要注意1：排序后，最接近的in和out一组，例如 in1,in2,out1,out2,in2和out1之间是这车在校园中逗留的时间，in1和out2是不符合规则的数据需要丢弃；2逗留时间是out2-out1,但是out2是不计入在学校的个数的。
以下是是用hash的思想做的，用两个hash数组记录当前时间车子的数量，Ti[24*60*60]当前秒车子停的个数，Tm[24*60]当前分钟车子的个数，因为光用ti一个会超时，所以我想如果in和out之间过大时，比如7:10:10到7:30:20出来，我不就可以这样算，7:10:10到7:10:59,每次遍历1秒，每次Ti加1；7:11:00到7:30:59每次遍历1分钟，每次Tm加1。最后7:30:00到7:30:19（最后一秒不算），每次遍历1秒，Ti加1。所以h:m:s时车子的个数是:res = 60*60*h+60*m+s,个数=Ti[res]+Tm[res/60]
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; #define N (10010) #define TN (24*60*60) struct CarInOutTime { int tick; bool bIn; CarInOutTime(int h,int m,int s,char* opt) { if(strcmp(opt,"in")==0) bIn = true; else bIn = false; tick = 60*60*h+60*m+s; } }; int cmp(const CarInOutTime& t1,const CarInOutTime& t2) { return t1.tick<t2.tick; } int Ti[TN]; //每秒钟车的个数 int Tm[TN/60]; //每分钟 struct Car { string carid;//车牌 vector<CarInOutTime> inouttime; //出入时间 int captime; //在校园中逗留的时间 Car(){captime=0;} void Add(char* id,int h,int m,int s,char* opt) { carid = id; inouttime.push_back(CarInOutTime(h,m,s,opt)); } void Deal() { sort(inouttime.begin(),inouttime.end(),cmp); //排序 int intick; //进入的人时间戳 bool bhavein=false; //前面是否进入过 for(int i=0;i<inouttime.size();++i) { if(inouttime[i].bIn) { bhavein = true; intick = inouttime[i].tick; } else if(bhavein&&!inouttime[i].bIn) { bhavein = false; captime += inouttime[i].tick-intick; for(int tick=intick;tick<inouttime[i].tick;) { if(tick%60==0&&tick+60<=inouttime[i].tick) { ++Tm[tick/60]; //因为这车在这一分钟都在 tick += 60; } else ++Ti[tick++]; } } } inouttime.clear();//清空 } }; map<string,int> msi; //把车的id转换成编号（从0开始） Car cars[N]; int main() { #ifdef ONLINE_JUDGE #else freopen("test.txt","r",stdin); #endif // ONLINE_JUDGE int n,k; scanf("%d%d",&n,&k); int carcnt = 0; for(int i=0;i<n;++i) { char carid[10],opt[5]; int h,m,s; scanf("%s %d:%d:%d %s",carid,&h,&m,&s,opt); if(msi.find(carid)==msi.end()) msi[carid] = carcnt++; cars[msi[carid]].Add(carid,h,m,s,opt); } vector<string> vs;//记录逗留最长时间的车牌号 int maxti = 0; for(int i=0;i<carcnt;++i) { cars[i].Deal(); if(cars[i].captime >= maxti) { if(cars[i].captime > maxti) vs.clear(),maxti = cars[i].captime; vs.push_back(cars[i].carid); } } for(int i=0;i<k;++i) { int h,m,s; scanf("%d:%d:%d",&h,&m,&s); int tick = h*60*60+m*60+s; printf("%d ",Ti[tick]+Tm[tick/60]); } sort(vs.begin(),vs.end()); for(int i=0;i<vs.size();++i) printf("%s ",vs[i].c_str()); printf("%02d:%02d:%02d ",maxti/3600,maxti%3600/60,maxti%60); return 0; }
1096题：容易超时，已知最大的长度是12，你可以从2*3...*13，所以从len等于12开始累乘，发现积能被n整除则输出，当len=1的时候需要判断sum*sum是否大于n，否则会超时，b当sum*sum大于n时，说明该数时素数则必须另外输出。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<map> #include<set> #include<algorithm> #include<cmath> using namespace std; long long int getSum(int n,int len) { long long int sum = 1; for(int i=0;i<len;++i) sum = sum*(n+i); return sum; } int main() { int n; scanf("%d", &n); for(int len=12;len>=1;--len) { long long int sum; for(int i=2;(sum=getSum(i,len))<=n;++i) { //sum必须是long long否则撑起来会负数。 if(len==1&&sum*sum > n) { break; } if(n%sum==0) { printf("%d ",len); for(int j=0;j<len;++j) { if(j) printf("*"); printf("%d",i+j); } return 0; } } } printf("1 %d ",n); return 0; }
1103题：dfs需要剪枝不然会超时，其实有点像N皇后的题目
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<map> #include<set> #include<algorithm> using namespace std; int mypow(int n,int p) { int res = 1; for(int i=0;i<p;++i) { res *= n; } return res; } int n,k,p,sum2=0; bool bOK; vector<int> res; void dfs(int sum,int totalsum,int i,int len,vector<int> vi) { //printf("totalsum=%d i=%d ",totalsum,i); if(len==k) { if(sum==n) { if(sum2 < totalsum) { sum2 = totalsum; bOK = true; res = vi; } } return; } if(sum >= n) { return; } /*容易超时，过滤*/ if(totalsum + (k-len)*i < sum2) { return; } for(int j = i;j>=1;--j) { vi.push_back(j); dfs(sum+mypow(j,p),totalsum+j,j,len+1,vi); vi.pop_back(); } } int main() { //freopen("test.txt","r",stdin); scanf("%d%d%d",&n,&k,&p); if(k==1) { int sum; for(int i=1;(sum=mypow(i,p))<=n;++i) { if(sum == n) { printf("%d = ",n); printf("%d^%d ",i,p); return 0; } } printf("Impossible "); } else { int sum,iMaxF = 0; for(int i=1;true;++i) { sum = mypow(i,p)+(k-1); if(sum >= n) { iMaxF = i; break; } } for(int i=iMaxF;i>=1;--i) { vector<int> vi; vi.push_back(i); dfs(mypow(i,p),i,i,1,vi); } if(bOK) { printf("%d = ",n); for(int i=0;i<res.size();++i) { if(i) printf(" + "); printf("%d^%d",res[i],p); } printf(" "); } else printf("Impossible "); } return 0; }
1107题：并查集
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; #define H (1100) int p[H]; int peo[H]; //记录每个人的第一个爱好 int Find(int x) { if(p[x]==x) return x; int root = Find(p[x]); p[x] = root; return root; } void Union(int x,int y) { int a = Find(x); int b = Find(y); if(a!=b) { p[a] = b; } } int main() { //freopen("test.txt","r",stdin); for(int i=0;i<H;++i) p[i] = i; int n; scanf("%d",&n); for(int i=0;i<n;++i) { int k,pre; scanf("%d:",&k); for(int ik=0;ik<k;++ik) { int a; scanf("%d",&a); if(ik==0) { peo[i] = a; } else { Union(pre,a); } pre = a; } } map<int,int> mii; for(int i=0;i<n;++i) ++mii[Find(peo[i])]; vector<int> vi; map<int,int>::iterator it = mii.begin(); for(;it!=mii.end();it++) vi.push_back(it->second); sort(vi.begin(),vi.end()); printf("%d ",vi.size()); for(int i=vi.size()-1;i>=0;--i) { if(i) printf("%d ",vi[i]); else printf("%d ",vi[i]); } return 0; }
1109题：k行看成k列，然后总是错误
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; struct ST { char name[10]; int height; }; int cmp(const ST &s1,const ST &s2) { if(s1.height != s2.height) return s1.height > s2.height; return strcmp(s1.name,s2.name)<0; } void Print(ST* st,int istart,int len) { string strname[len]; int imid = (len)/2; strname[imid] = st[istart].name; for(int i=istart+1,j=1;i<istart+len;i += 2,++j) { if(i<istart+len) strname[imid-j] = st[i].name; if(i+1<istart+len) strname[imid+j] = st[i+1].name; } for(int i=0;i<len;++i) { if(i) printf(" "); printf("%s",strname[i].c_str()); } printf(" "); } int main() { //freopen("test.txt","r",stdin); int n,k; scanf("%d%d",&n,&k); ST st[n]; for(int i=0;i<n;++i) { scanf("%s%d",st[i].name,&st[i].height); } sort(st,st+n,cmp); k = n/k; for(int i=0;i<n;) { int len = k; if(i==0) { len = (n>=k?k:0)+n%k; } Print(st,i,len); i += len; } return 0; }
1110题：进行bfs遍历，每次遍历完需要判断该层是否是2的（level-1）次方，如果有下一层，而且该层不满足2的level-1次方，说明不是bst（之前没考虑所以错了）
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<map> #include<set> #include<algorithm> using namespace std; #define N (100) struct Node { int key; Node *left; Node *right; Node(){left = right = NULL;} }; Node nodes[N]; int indegree[N]={0}; int cnt = 0; Node* lastnode = NULL; bool bVis[N] = {0}; void level_travel(vector<Node*> vn,int level) { if(vn.size()==0) return; cnt += vn.size(); vector<Node*> vnnext; for(int i=0;i<vn.size();++i) { Node* node = vn[i]; if(node->left==NULL) { break; } if(bVis[node->left->key]) return; bVis[node->left->key] = true; vnnext.push_back(node->left); lastnode = node->left; if(node->right==NULL) { break; } if(bVis[node->right->key]) return; bVis[node->right->key] = true; vnnext.push_back(node->right); lastnode = node->right; } if(vnnext.size()) { int stdcnt = 1; for(int i=1;i<level;++i) { stdcnt *= 2; } if(stdcnt != vn.size()) { return; } level_travel(vnnext,level+1); } } int main() { //freopen("test.txt","r",stdin); int n; scanf("%d",&n); for(int i=0;i<n;++i) { char cl[5],cr[5]; scanf("%s%s",cl,cr); nodes[i].key = i; if(cl[0]!='-') { nodes[i].left = &nodes[atoi(cl)]; ++indegree[atoi(cl)]; } if(cr[0]!='-') { nodes[i].right = &nodes[atoi(cr)]; ++indegree[atoi(cr)]; } } Node* root = NULL; for(int i=0;i<n;++i) { if(indegree[i]==0) { root = &nodes[i]; break; } } vector<Node*> vn; lastnode = root; bVis[root->key] = true; vn.push_back(root); level_travel(vn,1); if(cnt == n) { printf("YES %d ",lastnode->key); } else { printf("NO %d ",root->key); } return 0; }
1111题：dfs会超时，最多只能27分。只能用dijkstra，并且使用pre数组记录路径。写了40分钟泪崩。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<map> #include<set> #include<algorithm> using namespace std; #define N (510) #define INF (1<<30) int Dis[N][N]; int Tim[N][N]; bool bVis[N]; int startpos,endpos; int n,m; int resDis; vector<int> vcDis; int resTim; vector<int> vcTim; void dijkstraDis() { memset(bVis,0,sizeof(bVis)); int dp[n]; int fast[n]; int pre[n]; for(int i=0;i<n;++i) { dp[i] = Dis[startpos][i]; fast[i] = Tim[startpos][i]; pre[i] = startpos; } bVis[startpos] = true; for(int i=0;i<n;++i) { int mindj=INF,minti=INF,pos = startpos; for(int j=0;j<n;++j) { if(!bVis[j]&&(dp[j]<mindj|| dp[j]==mindj&&fast[j]<minti)) { mindj = dp[j]; minti = fast[j]; pos = j; } } bVis[pos] = true; for(int j=0;j<n;++j) { if(!bVis[j] && (dp[j] > dp[pos]+Dis[pos][j] || dp[j] == dp[pos]+Dis[pos][j]&&fast[j] > fast[pos]+Tim[pos][j])) { pre[j] = pos; dp[j] = dp[pos]+Dis[pos][j]; fast[j] = fast[pos]+Tim[pos][j]; } } if(bVis[endpos]) { resDis = dp[endpos]; for(int j=endpos;true;j=pre[j]) { vcDis.push_back(j); if(j==startpos) { break; } } reverse(vcDis.begin(),vcDis.end()); return; } } } void dijkstraTim() { memset(bVis,0,sizeof(bVis)); int dp[n]; int ins[n]; int pre[n]; for(int i=0;i<n;++i) { dp[i] = Tim[startpos][i]; ins[i] = 0; pre[i] = startpos; } bVis[startpos] = true; for(int i=0;i<n;++i) { int mindj=INF,minins=INF,pos = startpos; for(int j=0;j<n;++j) { if(!bVis[j]&&(dp[j]<mindj|| dp[j]==mindj&&ins[j]<minins)) { mindj = dp[j]; minins = ins[j]; pos = j; } } bVis[pos] = true; for(int j=0;j<n;++j) { if(!bVis[j] && (dp[j] > dp[pos]+Tim[pos][j] || dp[j] == dp[pos]+Tim[pos][j]&&ins[j] > ins[pos]+1)) { pre[j] = pos; dp[j] = dp[pos]+Tim[pos][j]; ins[j] = ins[pos]+1; } } if(bVis[endpos]) { resTim = dp[endpos]; for(int j=endpos;true;j=pre[j]) { vcTim.push_back(j); if(j==startpos) { break; } } reverse(vcTim.begin(),vcTim.end()); return; } } } bool isVecSame(vector<int> v1,vector<int> v2) { if(v1.size()!= v2.size()) return false; for(int i=0;i<v1.size();++i) { if(v1[i] != v2[i]) return false; } return true; } int main() { //freopen("test.txt","r",stdin); scanf("%d%d",&n,&m); for(int i=0;i<n;++i) for(int j=0;j<n;++j) { if(i==j) { Dis[i][j] = Tim[i][j] = 0; } else { Dis[i][j] = Tim[i][j] = INF; } } for(int i=0;i<m;++i) { int v1,v2,oneway,len,tim; scanf("%d%d%d%d%d",&v1,&v2,&oneway,&len,&tim); Dis[v1][v2] = len; Tim[v1][v2] = tim; if(oneway==0) { Dis[v2][v1] = len; Tim[v2][v1] = tim; } } scanf("%d%d",&startpos,&endpos); dijkstraDis(); dijkstraTim(); if(isVecSame(vcDis,vcTim)) { printf("Distance = %d; Time = %d: ",resDis,resTim); for(int i=0;i<vcDis.size();++i) { if(i) printf(" -> "); printf("%d",vcDis[i]); } printf(" "); } else { printf("Distance = %d: ",resDis); for(int i=0;i<vcDis.size();++i) { if(i) printf(" -> "); printf("%d",vcDis[i]); } printf(" "); printf("Time = %d: ",resTim); for(int i=0;i<vcTim.size();++i) { if(i) printf(" -> "); printf("%d",vcTim[i]); } printf(" "); } return 0; }
1117题：题意有点坑，具体题意解释在代码注释中
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; int cmp(const int& a,const int& b) { return a>b; } //题目不好理解，是从给出的序列中选出最大的E，满足E天每天骑行距离都大于E。（不用按顺序） int main() { //freopen("test.txt","r",stdin); int n; scanf("%d",&n); int a[n]; for(int i=0;i<n;++i) { scanf("%d",&a[i]); } sort(a,a+n,cmp); for(int len=n;len>=1;--len) { if(a[len-1]>len) { printf("%d ",len); return 0; } } printf("0 "); return 0; }
1119题：有先序和后序求中序，题目很新颖，光想不太容易想清楚，最后画图和编码一起这样方便找规律。什么时候二叉树不唯一，什么时候唯一呢？那例题来说1 2 3 4 6 7 5和2 6 7 4 5 3 1，我们第一步可以得到当前父节点1。然后如何判断左右孩纸呢。
先序1后面那个就是下一个节点（2），后序1前面那个就是下一个节点（3），这时候你发现2和3不一样，说明什么呢--其实说明一个是左孩纸，一个是有孩纸。然后从先序中找右孩纸（3）的节点位置，然后我们可以找到左右孩纸的两颗树的序：左孩纸树的先序序列2，后序也是2，右孩纸的先序序列就是3 4 6 7 5，后序序列是6 7 4 5 3。然后不断重复以上步骤就好了。
再看另一个例子：1 2 3 4、2 4 3 1。为什么不唯一呢,找左右孩纸序列，左孩纸2 右孩纸3 4（先序），4 3（后序）。然后对右孩纸进行递归，你会发现根节点是3，孩纸节点只有一个（4），然后你就不知道他是属于左节点还是右节点了，所以不唯一。
所以结论：先序和后序求中序，要求必须是孩纸节点要么没有，要么是2个，不能有任意节点只有一个孩纸节点。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; struct Node { int key; Node* left; Node* right; Node() { left = right = NULL; } }; bool bOnly = true; Node* CreateTree(int* pre,int *post,int len) { Node *node = new Node(); node->key = *pre; if(len != 1) { //printf("len=%d ",len); if(*(pre+1) == *(post+len-2)) { bOnly = false; node->left = CreateTree(pre+1,post,len-1); } else { int rightkey = *(post+len-2); int rightindex = 0; for(;rightindex<len;++rightindex) { if(rightkey == *(pre+rightindex)) { break; } } node->left = CreateTree(pre+1,post,rightindex-1); node->right = CreateTree(pre+rightindex,post+rightindex-1,len-rightindex); } } return node; } bool bFirst = true; void inorder_travel(Node* root) { if(root == NULL) return; inorder_travel(root->left); if(bFirst) bFirst = false; else printf(" "); printf("%d",root->key); inorder_travel(root->right); } int main() { //freopen("test.txt","r",stdin); int n; scanf("%d",&n); int pre[n],post[n]; for(int i=0;i<n;++i) scanf("%d",&pre[i]); for(int i=0;i<n;++i) scanf("%d",&post[i]); Node* root = CreateTree(pre,post,n); if(bOnly) { printf("Yes "); } else { printf("No "); } inorder_travel(root); printf(" "); return 0; }
1125题意还是搞错了。。。可以再做一遍看看。最后的四舍五入那一个可以忽略，好像没有case卡这个，直接转换成整型就行了。（可能他的case都是刚好整除的吧）
1126题：1）题意比较绕，想复杂了；2）遍历所有节点判断错了。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> #include<queue> using namespace std; #define N (510) int n,m; int Map[N][N]; int indegree[N]; bool bVis[N]; int sum=0; void dfs(int curI,int istep) { ++sum; for(int nextI=1;nextI<=n;++nextI) { if(Map[curI][nextI]&&!bVis[nextI]) { bVis[nextI] = true; dfs(nextI,istep+1); } } } /*给定一个图，计算该图的每个结点的度 若所有的节点的度均为偶数则为“Eulerian”， 若恰好有两个为奇数则为“Semi-Eulerian”， 其他为“Non-Eulerian”。 需要判断是否是连通图。 */ int main() { //freopen("test.txt","r",stdin); scanf("%d%d",&n,&m); memset(Map,0,sizeof(Map)); memset(indegree,0,sizeof(indegree)); memset(bVis,0,sizeof(bVis)); for(int i=0;i<m;++i) { int a,b; scanf("%d%d",&a,&b); Map[a][b] = Map[b][a] = 1; ++indegree[a]; ++indegree[b]; } int iOddnum=0; for(int i=1;i<=n;++i) { if(indegree[i]%2) { ++iOddnum; } if(i>1) printf(" "); printf("%d",indegree[i]); } printf(" "); bVis[1] = true; dfs(1,1); if(sum==n) { if(iOddnum==0) printf("Eulerian "); else if(iOddnum==2) printf("Semi-Eulerian "); else printf("Non-Eulerian "); } else { printf("Non-Eulerian "); } return 0; }
1131:题：简单dfs，刚开始理解错误，以为有公共线路，后来发现没有。最后一个case容易超时，是因为你把数组开太大。line[N][N],可以用map代替，key = i+j*N;
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; #define N (10010) struct ST { int start; int stop; int line; }; vector<int> vcMap[N]; //int line[N][N]; map<int,int> line; bool bVis[N]; int iMinLen = N; vector<ST> vs; int iStartStop,iEndStop; void dfs(int curI,int len,vector<ST>vi) { if(curI==iEndStop) { if(len < iMinLen) { iMinLen = len; vs = vi; } else if(len==iMinLen&&vs.size()>vi.size()) { vs = vi; } return; } if(len >= iMinLen) return; for(int i=0;i<vcMap[curI].size();++i) { int nextI = vcMap[curI][i]; if(!bVis[nextI]) { bVis[nextI] = true; int curLine = line[curI+nextI*N]; bool bNeedAdd = true; if(vi.size()&&vi[vi.size()-1].line==curLine) { bNeedAdd = false; } if(bNeedAdd) { ST st; st.line = curLine; st.start = curI; st.stop = nextI; vi.push_back(st); } else { vi[vi.size()-1].stop = nextI; } dfs(nextI,len+1,vi); if(bNeedAdd) vi.pop_back(); else { vi[vi.size()-1].stop = curI; } bVis[nextI] = false; } } } int main() { //freopen("test.txt","r",stdin); int n; scanf("%d",&n); int prestop; for(int i=0;i<n;++i) { int m; scanf("%d",&m); for(int j=0;j<m;++j) { int a; scanf("%d",&a); if(j==0) prestop = a; else { vcMap[prestop].push_back(a); vcMap[a].push_back(prestop); line[prestop+a*N] = i+1; line[a+prestop*N] = i+1; prestop = a; } } } int k; scanf("%d",&k); for(int i=0;i<k;++i) { memset(bVis,0,sizeof(bVis)); iMinLen = N; scanf("%d%d",&iStartStop,&iEndStop); bVis[iStartStop] = 1; vs.clear(); vector<ST> vi; dfs(iStartStop,0,vi); printf("%d ",iMinLen); for(int j=0;j<vs.size();++j) { printf("Take Line#%d from %04d to %04d. ",vs[j].line,vs[j].start,vs[j].stop); } } return 0; }