PAT甲级考前整理（2019年3月备考）之一
2024-10-21 03:55:51
转载请注明出处：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,并查集,树遍历算法。
题目分类：
（dfs or dijkstra）、（dfs）、（最长子和）、（二分查找）、（并查集）、（二叉树，前后序求广度）、（并查集）、（大数加法）、（归并排序）、（dikstra）、（前序判断是否是二叉收缩树）、（二分查找）、（lcs）、（dfs）、（set）、（二叉搜索树）、（AVL）、（背包问题）、（bfs）、（hash二次探测）、（bfs，dfs）、（中前序求后序）、（排序）、（bfs or 并查集），（排序）、（BST）、（快排）、（反转二叉树）、（dfs剪枝）、（并查集）、（完全二叉树）、（dijkstra）、（并查集）、（BST）、（并查集）、（前后序求中序）、（AVL）、（bfs）、（dfs）
dijkstra: 、、
dfs: 、、、、（dfs剪枝）、
bfs：、、、
排序：（归并排序）、、、（快排）
并查集：、、、、、
二叉树：（前后序求广度）、（前序判断是否是二叉搜索树）、（二叉搜索树）、（AVL）、（中前序求后序）、（BST）、（反转二叉树）、（完全二叉树）、（BST）、（前后序求中序）、（AVL）
二分查找：、
其他：（最长子和）、（大数加法）、（lcs）、（set）、（背包问题）、（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 = ;
for(long long int i=len-,k=;i>=;--i,k*=jinzhi)
{
long long int a;
if(strnum[i]>=''&& strnum[i]<='') a = strnum[i]-'';
else a = strnum[i]-'a'+;
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)/;
long long int midnum = change(strnum,mid);
if(left==right)
{
if(dst != midnum) return -;
return left;
}
else if(left > right)
{
return -;
}
if(midnum==dst)
{
return mid;
}
if(midnum<||dst<midnum)
{
return Find_Radix(strnum,dst,left,mid-);
}
else
{
return Find_Radix(strnum,dst,mid+,right);
}
} int main()
{
//freopen("test.txt","r",stdin);
char s1[],s2[];
int tag,jinzhi;
scanf("%s%s%d%d",s1,s2,&tag,&jinzhi);
if(tag==) {swap(s1,s2);}
long long int a = change(s1,jinzhi);
long long int left = ;
int len = strlen(s2);
for(int i=;i<len;++i)
{
long long int temp;
if(s2[i]>=''&&s2[i]<='')
{
temp = s2[i]-'';
}
else
{
temp = s2[i] - 'a'+;
}
left = max(temp+,left);
}
left = max((long long int),left);
long long int right = max(a,left);
long long int res = Find_Radix(s2,a,left,right);
if(res==-)
{
printf("Impossible\n");
}
else
{
printf("%lld\n",res);
}
return ;
}
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**+m*+s;
}
const int window_starttime = gettick(,,);
const int window_endtime = gettick(,,);
struct Customer
{
int cometime; //来到时间
int protime; //处理时间,秒
};
int getfreewindow(int* windows,int k)
{
int mintime = windows[],mink = ;
for(int i=;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=;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(*p,*);
if(cus.cometime <= window_endtime) //过滤17点以后来的人
vcus.push_back(cus);
}
n = vcus.size();
sort(vcus.begin(),vcus.end(),cmp);
int twaittime = /*总等待时间*/,cnt=/*得到处理的人数*/,windowstime[k]/*该窗口空闲时间*/;
for(int i=;i<k;++i)
windowstime[i] = window_starttime;
for(int i=;i<n;++i)
{
int iw = getfreewindow(windowstime,k);
if(iw==-) 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==) printf("0.0\n");
else printf("%.1lf\n",1.0f*twaittime/cnt/);
return ;
}
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 = (<<);
int cmax,n,sp,m;
int cap[N];
int Len[N][N];
vector<int> Map[N];
bool bVis[N];
int minlen = INF;
int minsend = ;
int minback= ;
vector<int> minPath;
void dfs(int curI,int len,vector<int> path)
{
if(curI==sp)
{
if(len <= minlen)
{
int curminsend = ,curminback = ;
for(int i=;i<path.size();++i)
{
int curcap = cap[path[i]];
if(curcap<cmax/) //少了
{
int adjust = cmax/ - curcap;
if(adjust <= curminback)
{
curminback -= adjust;
}
else
{
adjust -= curminback;
curminback = ;
curminsend += adjust;
}
}
else if(curcap>cmax/) //多了
{
curminback += (curcap-cmax/);
}
}
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=;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=;i<=n;++i)
for(int j=;j<=n;++j)
if(i==j) Len[i][j] = ;
else Len[i][j] = INF;
for(int i=;i<=n;++i)
scanf("%d",&cap[i]);
for(int i=;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[] = true;
vector<int> path;
path.push_back();
dfs(,,path);
printf("%d ",minsend);
for(int i=;i<minPath.size();++i)
{
if(i) printf("->");
printf("%d",minPath[i]);
}
printf(" %d\n",minback);
return ;
}
1022题，需要用到整行输入字符串，而PAT的c++编译器是无法调用gets的，可以用fgets(buf,sizeof(buf),stdin);//读入的数据需要去掉\n。如果在fgets函数之前调用了scanf，就必须要使用getchar把换行好读掉。
当然也可以用 while(cin>>str)
{ char c; c=getchar(); if(c=='\n') 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[];
fgets(temp,sizeof(temp),stdin);
temp[strlen(temp)-] = '\0';
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=;i<len;++i)
{
if(key[i]!=' ') words += key[i];
if(i==len-||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\n",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\n",opt,str.c_str());
map<string,set<int> > *mss = NULL;
if(opt==) mss = &mapbname;
else if(opt==) mss = &mapauthor;
else if(opt==) mss = &mapkey;
else if(opt==) mss = &mappublisher;
else if(opt==) 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\n",*it);
}
if(si.size()==) printf("Not Found\n");
}
else
{
printf("Not Found\n");
}
}
return ;
}
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=;i<l/;++i)
if(str[i] != str[l-i-]) return false;
return true;
}
void Add(char* str)
{
char temp[N];
int iAdd = ;
int l = strlen(str);
int tlen = ;
for(int i=;i<l;++i)
{
int res = str[i]-''+str[l-i-]-'' +iAdd;
temp[tlen++] = res% + '';
iAdd = res/;
}
if(iAdd) temp[tlen++] = iAdd + '';
temp[tlen] = '\0';
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 = ;
while(!isPal(strNum)&&step<k)
{
Add(strNum);
++step;
}
printf("%s\n",strNum);
printf("%d\n",step);
return ;
}
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 **h+*m+s;
}
const int SartTime = getTick(,,);
const int EndTime = getTick(,,);
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 = -,mintime = getTick(,,),minviptime=getTick(,,);
freeviptableid = -;
for(int i=;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/,tick%/,tick%);
}
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=;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(**,c.playingtime*); //转换成秒
if(bVip) cusvip.push_back(c);
else cus.push_back(c);
}
//加入末尾哨兵，这样当下面运用是不需要考虑vector为空的时候
Custom finalcus;
finalcus.arrivingtime = getTick(,,);
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=;i<m;++i)
{
int tableid;
scanf("%d",&tableid);
bTableVip[tableid] = ;
}
for(int i=;i<tables;++i) tabfreetime[i+] = SartTime;
vector<Custom> res;
for(int i=;i<n;++i)
{
int freeviptableid;
int freetableid = getFreeTable(freeviptableid);
Custom curcus;
if(cusvip[].arrivingtime<cus[].arrivingtime|| /*当vip用户早到时，vip用户肯定先上桌*/
bTableVip[freetableid]&&cusvip[].arrivingtime<=tabfreetime[freetableid]) /*如果vip用户晚到，但是这桌是vip专用桌，此时要看vip到达时间是否在桌有空之前到达*/
{
curcus = cusvip[];
cusvip.erase(cusvip.begin());
if(freeviptableid!=-&&curcus.arrivingtime>=tabfreetime[freeviptableid]) //vip用户来的比最小vip桌空闲时间晚，这个时候前面即使有空闲普通桌，也要选择vip桌。
freetableid = freeviptableid;
}
else
{
curcus = cus[];
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=;i<res.size();++i)
{
printtime(res[i].arrivingtime);
printtime(res[i].servingtime);
int waittime = max(,res[i].servingtime - res[i].arrivingtime);
waittime = (int)(1.0*waittime/+0.5);
printf("%d\n",waittime);
}
for(int i=;i<=tables;++i)
{
if(i-) printf(" ");
printf("%d",tableperson[i]);
}
printf("\n");
return ;
}
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=;i<n;++i)
{
int temp;
scanf("%d",&temp);
a.push(temp);
}
a.push(INF);
scanf("%d",&m);
int iCnt = ;
int iMid = -;
for(int i=;i<m;++i)
{
int temp;
scanf("%d",&temp);
if(iMid == -)
{
b.push(temp);
if(iCnt==(m+n+)/-)
{
iMid = min(a.front(),b.front());
}
if(a.front()<b.front()) a.pop();
else b.pop();
}
++iCnt;
}
b.push(INF);
for(;iCnt<=(m+n+)/-;++iCnt)
{
iMid = min(a.front(),b.front());
if(a.front()<b.front()) a.pop();
else b.pop();
}
printf("%d\n",iMid);
return ;
}
用数组的做法，类似分治排序的方法（可以看算法导论中对分治排序的讲解，写的特别好！！）
#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+];
for(int i=;i<n1;++i)
scanf("%d",&a1[i]);
scanf("%d",&n2);
int res = ,k=,j=;
for(int i=;i<n2;++i)
{
int num;
scanf("%d",&num);
while(a1[j]<num&&k<(n1+n2+)/)
{
res = a1[j++];
k++;
}
if(a1[j]>=num&&k<(n1+n2+)/)
{
res = num;
k++;
}
}
//这一行容易忘记,因为k可能没有到中位数。
while(k++<(n1+n2+)/)
res = a1[j++];
printf("%d\n",res);
return ;
}
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[];
//while(true)
{
scanf("%s",str);
int len = strlen(str);
int n1,n2,n3 = (len++)/;
n3 = max(,n3);
for(;n3<=len;++n3)
if((len+-n3)%==)
break;
int space = n3-;
n1 = n2 = (len - n3 + )/;
for(int i=;i<n1-;++i)
{
printf("%c",str[i]);
for(int j=;j<space;++j)
printf(" ");
printf("%c\n",str[len-i-]);
}
printf("%c",str[n1-]);
for(int i=n1;i<n1+space;++i)
printf("%c",str[i]);
printf("%c\n",str[n1-+n3-]);
} return ;
}
1032题：坑点，当搜索的两个起点是一样的时候测试点 。个人觉得应该还要考虑两个起点是直接父子关系的情况（但是测试点中没有。。。）
c
a
b -
#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] = {};
int iComPos = -;
void dfs(int iCurI)
{
bVis[iCurI] = true;
for(int i=;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=;i<n;++i)
{
int a,b;
char c[];
scanf("%d%s%d",&a,c,&b);
if(s1 == a && s2 == b || s2==a&&s1==b)
{
iComPos = b;
}
if(b != -)
{
vcPath[a].push_back(b);
}
}
if(- == iComPos)
{
dfs(s1);
dfs(s2);
}
if(-==iComPos) printf("%d\n",-);
else printf("%05d\n",iComPos);
return ;
}
/*
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=;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()==||mis.begin()->first!=) //一个测试点
{
printf("The maximum travel distance = 0.00\n");
}
else if(d==) //没有测试点
{
printf("0.00\n");
}
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 = -;
double fMinDis = -;
//如果当前加油点可以直接开到终点，并且后面几个点都比他大的话，就无需遍历接来的点了
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 == - || 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 = ;
double fCurCap = ;
for(int i=;sit != si.end();sit++,++i)
{
if(i == si.size()-)
{
if(*sit+iMaxLen < d)
{
printf("The maximum travel distance = %.2lf\n",*sit+iMaxLen);
}
else
{
//printf("gas=%.2lf\n",1.0*(d-*sit)/davg-fCurCap);
fTotal += (1.0*(d-*sit)/davg-fCurCap)*mis[*sit];
printf("%.2lf\n",fTotal);
}
}
else
{
set<int>::iterator nextsit = sit;
++nextsit;
if(mis[*nextsit] > mis[*sit])
{
//printf("gas=%.2f\n",iCmax-fCurCap);
fTotal += 1.0*(iCmax-fCurCap)*mis[*sit];
fCurCap = iCmax - 1.0*(*nextsit-*sit)/davg;
}
else
{
//printf("gas=%.2f\n",(*nextsit-*sit)/davg-fCurCap);
fTotal += (1.0*(*nextsit-*sit)/davg-fCurCap)*mis[*sit];
fCurCap = ;
}
}
//printf("[%d %.2f]\n",*sit,fTotal);
}
}
return ;
}
解法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=;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] = ;
if(d&&mis.size()==||mis.begin()->first!=) //一个测试点
{
printf("The maximum travel distance = 0.00\n");
}
else if(d==) //没有测试点
{
printf("0.00\n");
}
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 = -;
double fMinDis = -;
while(++tit != mis.end())
{
if(tit->first - fDis <= iMaxLen)
{
if(fMinDis == - || 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 = ;
double fCurCap = ;
for(int i=;sit != si.end();sit++,++i)
{
if(i == si.size()-)
{
if(*sit+iMaxLen < d)
{
printf("The maximum travel distance = %.2lf\n",*sit+iMaxLen);
}
else
{
//printf("gas=%.2lf\n",1.0*(d-*sit)/davg-fCurCap);
fTotal += (1.0*(d-*sit)/davg-fCurCap)*mis[*sit];
printf("%.2lf\n",fTotal);
}
}
else
{
set<int>::iterator nextsit = sit;
++nextsit;
if(mis[*nextsit] > mis[*sit])
{
//printf("gas=%.2f\n",iCmax-fCurCap);
fTotal += 1.0*(iCmax-fCurCap)*mis[*sit];
fCurCap = iCmax - 1.0*(*nextsit-*sit)/davg;
}
else
{
//printf("gas=%.2f\n",(*nextsit-*sit)/davg-fCurCap);
fTotal += (1.0*(*nextsit-*sit)/davg-fCurCap)*mis[*sit];
fCurCap = ;
}
}
//printf("[%d %.2f]\n",*sit,fTotal);
}
}
return ;
}
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] = {};
bool bVis[N] = {};
vector<int> vcMap[N];
map<int,int> Res;
int GetNum(char* str)
{
return (str[]-'A')+(str[]-'A')*+(str[]-'A')**;
}
string GetStr(int num)
{
char str[] = {};
str[] = num%+'A';
str[] = num/%+'A';
str[] = num//+'A';
return str;
}
int iMaxCnt = ,iMaxI = ,iMaxMin = ;
void dfs(int curI)
{
bVis[curI] = true;
++iMaxCnt;
iMaxMin += val[curI];
if(val[iMaxI] < val[curI]) iMaxI = curI;
for(int i=;i<vcMap[curI].size();++i)
{
int NextI = vcMap[curI][i];
if(!bVis[NextI])
dfs(NextI);
}
}
int main()
{
scanf("%d%d",&n,&k);
int iMaxN = ;
for(int i=;i<n;++i)
{
char s1[],s2[];
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=;i<=iMaxN;++i)
{
if(!bVis[i])
{
iMaxCnt = ,iMaxI = i,iMaxMin = ;
dfs(i);
if(iMaxCnt > && iMaxMin>*k)
{
Res[iMaxI] = iMaxCnt;
}
}
}
printf("%d\n",Res.size());
map<int,int>::iterator it = Res.begin();
for(;it!=Res.end();it++)
printf("%s %d\n",GetStr(it->first).c_str(),it->second);
return ;
}
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=;i<temp1.length();++i)
{
if(temp1[i] != temp2[i])
return temp1[i] - temp2[i] < ;
}
return ;
}
int main()
{
//while(true)
{
vector<string> vs;
int n;
scanf("%d",&n);
for(int i=;i<n;++i)
{
char str[];
scanf("%s",str);
vs.push_back(str);
}
sort(vs.begin(),vs.end(),cmp);
bool bFirst = true;
for(int i=;i<vs.size();++i)
{
if(bFirst)
{
int a = atoi(vs[i].c_str());
if(a== && i!= vs.size()-) continue;
printf("%d",a);
bFirst = false;
}
else
{
printf("%s",vs[i].c_str());
}
}
printf("\n");
} return ;
}
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=;i<n;++i)
{
int a;
scanf("%d",&a);
vc.push_back(a);
}
int iMin = INF;
bool bCanBreak = false;
for(int i=;i<n;++i)
{
int sum = ;
for(int j=i;j<n;++j)
{
sum += vc[j];
if(sum == dst)
{
res[i+] = j+;
break;
}
else if(sum > dst)
{
if(iMin > sum)
{
iMin = sum;
res2.clear();
}
if(iMin == sum)
{
res2[i+] = j+;
}
break;
}
if(j==n-) bCanBreak = true;
}
if(bCanBreak) break;
}
if(res.size())
{
map<int,int>::iterator it = res.begin();
for(;it != res.end();it++)
printf("%d-%d\n",it->first,it->second);
}
else
{
map<int,int>::iterator it = res2.begin();
for(;it != res2.end();it++)
printf("%d-%d\n",it->first,it->second);
}
return ;
}
二刷的时候用的方法：计算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 = ;
for(int i=,j=;i<n;++i)
{
while(res < needm&&j<n)
res += a[j++];
if(res == needm)
{
printf("%d-%d\n",i+,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=;i<n;++i)
scanf("%d",&a[i]);
print(m);
if(minM!=m)
{
print(minM);
}
return ;
}
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",&n);
scanf("%d",&m);
for(int i=;i<m;++i)
{
scanf("%d",&love[i]);
bHave[love[i]] = true;
}
scanf("%d",&l);
for(int i=;i<l;++i)
{
int a;
scanf("%d",&a);
if(bHave[a])
vcColor.push_back(a);
}
n = vcColor.size();
int dp[m+][n+];
memset(dp,,sizeof(dp));
for(int i=;i<m;++i)
for(int j=;j<n;++j)
{
if(love[i]==vcColor[j])
{
dp[i+][j+] = max(dp[i+][j]+,dp[i][j] + );
}
else
{
dp[i+][j+] = max(dp[i][j+],dp[i+][j]);
}
}
printf("%d\n",dp[m][n]);
return ;
}
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 = ;
for(int i=;i<n;++i)
{
int a;
scanf("%d",&a);
len += a;
dis[i+] = len;
}
int m;
scanf("%d",&m);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
if(a > b) swap(a,b);
int l = ;
if(a != b)
{
l = dis[b-] - dis[a-];
}
l = min(l,len-l);
printf("%d\n",l);
}
return ;
}
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+];
for(int i=;i<n;++i)
{
char name[];
int m;
scanf("%s%d",name,&m);
for(int j=;j<m;++j)
{
int c;
scanf("%d",&c);
Course[c].push_back(name);
}
}
for(int i=;i<=k;++i)
{
printf("%d %d\n",i,Course[i].size());
if(Course[i].size())
{
sort(Course[i].begin(),Course[i].end());
}
for(int j=;j<Course[i].size();++j)
{
printf("%s\n",Course[i][j].c_str());
}
}
return ;
}
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=;i<n;++i)
{
int a;
scanf("%d",&a);
++Hash[a];
}
for(int i=;i<=m;++i)
{
if(Hash[i]&&Hash[m-i])
{
if(i==m-i&&Hash[i]==) continue;
printf("%d %d\n",i,m-i);
return ;
}
}
printf("No Solution\n");
return ;
}
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 = -;
addr = -;
}
}; Node Map[N];
vector<Node> vc;
int n,iStart;
void dfs(int CurI)
{
if(CurI == - || Map[CurI].addr==-) 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 < ;
}
int main()
{
scanf("%d%d",&n,&iStart);
for(int i=;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[].addr);
else printf(" -1");
printf("\n");
for(int i=;i<nVcSize;++i)
{
printf("%05d %d ",vc[i].addr,vc[i].key);
if(i != nVcSize-)
{
printf("%05d\n",vc[i+].addr);
}
else printf("-1\n");
}
return ;
}
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]={};
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=;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=;i<v1.size()&&i<v2.size();++i)
{
if(v1[i] != v2[i])
return v1[i]-v2[i] > ;
}
return ;
}
int main()
{ scanf("%d%d%d",&n,&m,&s);
for(int i=;i<n;++i)
scanf("%d",&w[i]);
for(int i=;i<m;++i)
{
int a,k,b;
scanf("%d%d",&a,&k);
for(int j=;j<k;++j)
{
scanf("%d",&b);
vcMap[a].push_back(b);
}
}
//方便判断结束
for(int i=;i<n;++i)
if(vcMap[i].size()==) vcMap[i].push_back(n);
vector<int> vc;
dfs(,,vc);
sort(vcPath.begin(),vcPath.end(),cmp);
for(int i=;i<vcPath.size();++i)
{
vector<int> &vc2 = vcPath[i];
bool bFirst = true;
for(int j=;j<vc2.size();++j)
{
if(bFirst) bFirst = false;
else printf(" ");
printf("%d",vc2[j]);
}
printf("\n");
}
return ;
}
1055题：之前由于每次查询都去排序导致超时，傻了
#include<iostream>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<iterator>
#include<algorithm>
#include<cstring>
using namespace std;
struct ST
{
char name[];
int age;
int net;
};
int cmp(const ST& st1,const ST& st2)
{
if(st1.net != st2.net) return st1.net-st2.net > ;
if(st1.age != st2.age) return st1.age - st2.age < ;
return strcmp(st1.name,st2.name)<; }
int main()
{
int n,k;
scanf("%d%d",&n,&k);
vector<ST> vc;
for(int i=;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=;i<k;++i)
{
int m,amin,amax;
scanf("%d%d%d",&m,&amin,&amax);
printf("Case #%d:\n",i+);
int iCnt = ;
for(int i=;i<vc.size();++i)
{
if(iCnt == m)
{
break;
}
if(amin<=vc[i].age&&vc[i].age<=amax)
{
printf("%s %d %d\n",vc[i].name,vc[i].age,vc[i].net);
++iCnt;
}
}
if(iCnt==)
printf("None\n");
}
return ;
}
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<;
}
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=;i<np;++i)
scanf("%d",&w[i]);
for(int i=;i<np;++i)
{
scanf("%d",&st[i].i);
st[i].w = w[st[i].i];
vc.push_back(&st[i]);
}
while(vc.size()>)
{
vector<ST*> vcTemp = vc;
vc.clear();
int i=;
vector<ST*> oneRes;
while(i<vcTemp.size())
{
ST* bigone = NULL;
for(int j=;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 = ;
if(vc.size())
vc[]->iRank = iCurRank++;
for(int i=vcRes.size()-;i>=;--i)
{
for(int j=;j<vcRes[i].size();++j)
vcRes[i][j]->iRank = iCurRank;
iCurRank += vcRes[i].size();
}
sort(st,st+np,cmp);
for(int i=;i<np;++i)
if(i) printf(" %d",st[i].iRank);
else printf("%d",st[i].iRank);
return ;
}
1057题：分块搜索第k大的数字。
#include<iostream>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<iterator>
#include<algorithm>
#include<cstring>
using namespace std;
const char strPop[] = "Pop";
const char strPush[] = "Push";
const char strPeek[] = "PeekMedian";
#define N (100010)
#define BLOCK 400
int block[]={};
int table[N]={};
int FindK(int k)
{
int cnt = ;
int i;
for(i=;i<;++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 ;
}
int main()
{
int n;
scanf("%d",&n);
vector<int> vc;
for(int i=;i<n;++i)
{
char cmd[];
scanf("%s",&cmd);
if(strcmp(cmd,strPop)==)
{
if(vc.size()==)
{
printf("Invalid\n");
}
else
{
int key = vc[vc.size()-];
printf("%d\n",key);
if(table[key]) --table[key];
if(block[key/BLOCK]) --block[key/BLOCK];
vc.pop_back();
}
}
else if(strcmp(cmd,strPush)==)
{
int num;
scanf("%d",&num);
vc.push_back(num);
++table[num];
++block[num/BLOCK]; }
else
{
if(vc.size()==)
{
printf("Invalid\n");
}
else
{
int k = vc.size();
int iMid = k%== ? k/ : (k+)/;
int iRes = FindK(iMid);
printf("%d\n",iRes);
}
}
}
return ;
}
/*
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==-?len:dot;
string res = str;
str = "";
for(int i=;i<len;++i)
{
if(res[i]=='') --wei;
else if(res[i]!='.')
{
res = res.substr(i,len-i);
len = res.length();
str = "";
for(int j=;j<len;++j)
if(res[j]!='.') str+=res[j];
break;
}
} len = str.length();
if(len==) wei = ; {
res = "0.";
int i;
for(i=;i<len&&i<m;++i)
res += str[i];
for(;i<m;++i)
res += "";
char subfix[];
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[],str2[];
scanf("%d%s%s",&n,str1,str2);
string res1 = getstr(str1,n),res2=getstr(str2,n);
if(strcmp(res1.c_str(),res2.c_str())==)
printf("YES %s\n",res1.c_str());
else printf("NO %s %s\n",res1.c_str(),res2.c_str());
return ;
}
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>=''&&c<='') return true;
return false;
}
int getPos(char c)
{
if(c>='a'&&c<='z') return c-'a'+;
if(c>='A'&&c<='Z') return c-'A'+;
return ;
}
int main()
{
string weeks[] = {"","MON","TUE","WED","THU","FRI","SAT","SUN"};
char s1[],s2[],s3[],s4[];
scanf("%s%s%s%s",s1,s2,s3,s4);
int week = ,iWeek=,h=,m=;
int i;
for(i=;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-)%+;
break;
}
} for(i=i+;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]-'';
}
else
{
h = s1[i]-'A'+;
}
break;
}
}
for(i=;i<strlen(s3)&&i<strlen(s4);++i)
{
if(s3[i]==s4[i]&&isEnglish(s3[i]))
{
m = i;
break;
}
}
printf("%s %02d:%02d\n",weeks[week].c_str(),h,m);
return ;
}
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=;i<n;++i)
{
scanf("%d",&m);
for(int j=;j<m;++j)
{
int temp;
scanf("%d",&temp);
si[i].insert(temp);
}
}
int k;
scanf("%d",&k);
for(int i=;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==) printf("0.0%%\n");
else printf("%.1lf%%\n",100.0*same/total); } return ;
}
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=;i<n;++i)
{
int m;
scanf("%d",&m);
for(int j=;j<m;++j)
{
int a;
scanf("%d",&a);
s[i].insert(a);
}
}
int k;
scanf("%d",&k);
for(int i=;i<k;++i)
{
int a,b;
scanf("%d%d",&a,&b);
if(a==b) printf("0.00%%\n");
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%%\n",fRes);
}
}
return ;
}
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=;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>&&b>&&res<=) bBig = true;
else if(a<&&b<&&res>=) bBig = false;
else bBig =res>c;
printf("Case #%d: %s\n",t,bBig?"true":"false"); }
return ;
}
很神奇的是用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=;t<=T;++t)
{
long double a,b,c;
scanf("%llf%llf%llf",&a,&b,&c);
bool bBig = a+b>c;
printf("Case #%d: %s\n",t,bBig?"true":"false");
}
return ;
}
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=;
set<int> si;
for(int i=;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=;
while(cnt < n-)
{
if(a[]==)
{
int i = *(si.begin());
if(a[i]!=i)
{
int b1 = a[i]; //i在b1位置
a[] = b1; //0移到b1位置
a[i] = ; //i移到0位置
} }
else
{
int b1 = a[]; //0在b1位置
int b2 = a[b1]; //b1在b2位置
a[] = b2;
a[b1] = b1;
si.erase(si.find(b1));
++cnt;
}
++step;
}
printf("%d\n",step);
return ;
}
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=;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+];
vector<int> path[m+];
for(int i=;i<=m;++i)
dp[i] = -;
int c[n];
for(int i=;i<n;++i)
scanf("%d",&c[i]);
dp[] = ;
sort(c,c+n);
for(int i=;i<n;++i)
{
for(int v=m;v>=c[i];--v)
if(dp[v-c[i]]>=)
{
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\n");
}
else
{
for(int i=;i<path[m].size();++i)
{
if(i) printf(" ");
printf("%d",path[m][i]);
}
}
return ;
}
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 == )
{
return ;
}
else if(m2.num == )
{
return ;
}
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=;i<n;++i)
scanf("%lf",&mc[i].num);
for(int i=;i<n;++i)
scanf("%lf",&mc[i].fprice);
sort(mc,mc+n,cmp);
double sum = ;
int i = ;
while(d>=&&i<n)
{
if(mc[i].num==||mc[i].fprice==)
{ }
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 = ;
}
++i;
}
printf("%.2lf\n",sum);
return ;
}
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>=''&&c<='') 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 = ;
string res = "";
string word = "";
int iStrLen = strlen(str);
for(int i=;i<iStrLen;++i)
{
char c = ToLower(str[i]);
if(isAlphanum(c)==false) continue;
word += c;
if(isAlphanum(str[i+])==false)
{
int tempcnt = ++msi[word];
if((num==tempcnt&&word.length()<res.length())||num<tempcnt)
{
num = tempcnt;
res = word;
}
word = "";
}
}
if(res!="")
{
printf("%s %d\n",res.c_str(),num);
}
return ;
}
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 = ;
if(str[]=='G') ++str,add=;
return add+atoi(str);
}
int n,m,k,ds;
int Map[N][N]={};
int dp[N];
bool bVis[N];
void Dijkstra(int iStart)
{
for(int i=;i<N;++i)
dp[i] = Map[iStart][i];
for(int i=;i<N;++i)
{
int iMindj = INT_MAX,iPos = iStart;
for(int j=;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=;j<N;++j)
{
//printf("dp[%d]=%d,dp[%d]=%d Map[%d][%d]=%d\n",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\n",dp[j]);
}
}
}
}
int main()
{
for(int i=;i<N;++i)
for(int j=;j<N;++j)
if(i==j)
Map[i][j] = ;
else Map[i][j] = INT_MAX;
scanf("%d%d%d%d",&n,&m,&k,&ds);
for(int i=;i<k;++i)
{
char str1[],str2[];
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=-,iMinPath=-;
for(int i=;i<m;++i)
{
int gas = +i;
memset(bVis,,sizeof(bVis));
bVis[gas] = true;
Dijkstra(gas);
int j,Sum=,iPath=INT_MAX;
for(j=;j<=n;++j)
{
//printf("gas=%d j=%d dp[j]=%d\n",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==-) printf("No Solution\n");
else
{
printf("G%d\n",iGas-);
printf("%.1lf %.1lf\n",1.0*iMinPath,1.0*iMinSum/n);
}
return ;
}
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 = -;
}
};
ST st[N];
bool bVis[N] = {true};
int iStart,n,k;
vector<int> res;
void travel(int iCurI,vector<int> vi)
{
//printf("CurI=%05d\n",iCurI);
if(iCurI==- || bVis[iCurI])
{
if(vi.size()==k)
for(int i=vi.size()-;i>=;--i)
{
res.push_back(vi[i]);
}
else
{
for(int i=;i<vi.size();++i)
{
res.push_back(vi[i]);
}
}
return;
}
else if(vi.size()==k)
{
for(int i=vi.size()-;i>=;--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=;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=;i<res.size();++i)
{
int ID = res[i];
if(i != res.size()-)
{
int iNextID = res[i+];
printf("%05d %d %05d\n",ID,st[ID].val,iNextID);
}
else
printf("%05d %d -1\n",ID,st[ID].val);
}
return ;
}
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]={};
int n,k,m;
struct PAT
{
int id;
int grade[K];
PAT()
{
for(int i=;i<=k;++i)
grade[i] = -;
}
bool bUseful()
{
for(int i=;i<=k;++i)
if(grade[i]>=) return true;
return false;
}
int getSum() const
{
int sum = ;
for(int i=;i<=k;++i)
if(grade[i]>=) sum+=grade[i];
return sum;
}
int getPerfectNum() const
{
int res = ;
for(int i=;i<=k;++i)
if(grade[i]>=prom[i])
++res;
return res;
}
void Print()
{
printf("%05d %d",id,getSum());
for(int i=;i<=k;++i)
if(grade[i]==-) printf("");
else if(grade[i]==-) printf(" -");
else printf(" %d",grade[i]);
printf("\n");
}
};
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=;i<=k;++i)
scanf("%d",&prom[i]);
for(int i=;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 = ;
for(int i=;i<vc.size()-;++i)
{
printf("%d ",iCurRank);
vc[i].Print();
if(vc[i].getSum() != vc[i+].getSum())
iCurRank = i+;
}
return ;
}
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=;i<n;++i)
{
char str[];
fgets(str,sizeof(str),stdin);
vs.push_back(str);
}
vector<char> res;
bool bOK = true;
for(int i=;i< && bOK;++i)
{
char c;
for(int j=;j<vs.size();++j)
{
int len = vs[j].length();
int iCurI = len - i -;
if(iCurI < )
{
bOK = false;
break;
}
if(vs[j][iCurI]==' ')
{
//考虑了单词，其实空格也算公有的一部分
//bOK = false;
//break;
}
if(j==) c = vs[j][iCurI];
else if(vs[j][iCurI] != c)
{
bOK = false;
break;
}
}
if(bOK==true)
{
res.push_back(c);
}
} if(res.size()==) printf("nai\n");
else
{
for(int i=res.size()-;i>=;--i)
if(res[i]!='\n') printf("%c",res[i]);
printf("\n");
}
return ;
}
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 < ) a = -a;
if(b < ) b = -b;
if(b==) return a;
return gcd(b,a%b);
}
long long bei(long long a,long long b)
{
if(a < ) a = -a;
if(b < ) b = -b;
return a/gcd(a,b)*b;
}
int main()
{
int n;
scanf("%d",&n);
vector<Fen> vc;
for(int i=;i<n;++i)
{
Fen fen;
scanf("%lld/%lld",&fen.a,&fen.b);
if(fen.a&&fen.b) vc.push_back(fen);
} long long com = ;
for(int i=;i<vc.size();++i)
{
com = bei(com,vc[i].b);
} long long son = ;
for(int i=;i<vc.size();++i)
{
son += com/vc[i].b*vc[i].a;
}
if(son == ) printf("0\n");
else
{
long long temp = gcd(son,com);
son = son/temp;
com = com/temp;
bool bN = false;
if(son > && com < || son< && com>)
{
bN = true;
if(son<) son = -son;
if(com<) com = -com;
}
if(son/com>)
{
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("\n");
}
return ;
}
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 = ;
const int WAN = ;
string strNum[] = {"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
void Print(long long int n)
{
if(n>=)
{
printf("%s Qian",strNum[n/].c_str());
n = n%;
if(n)
{
printf(" ");
if(n<) printf("ling ");
}
}
if(n>=)
{
printf("%s Bai",strNum[n/].c_str());
n=n%;
if(n)
{
printf(" ");
if(n<) printf("ling ");
}
}
if(n>=)
{
printf("%s Shi",strNum[n/].c_str());
n = n%;
if(n) printf(" ");
}
if(n) printf("%s",strNum[n].c_str());
}
int main()
{
long long int n;
scanf("%lld",&n);
if(n==) printf("ling\n");
else
{
if(n<)
{
printf("Fu ");
n = -n;
}
if(n>=YI)
{
printf("%s Yi",strNum[n/YI].c_str());
n = n%YI;
if(n)
if(n<) printf(" ling ");
else printf(" ");
}
if(n>=WAN)
{
Print(n/WAN);
printf(" Wan");
n = n%WAN;
if(n)
if(n<) printf(" ling ");
else printf(" ");
}
if(n) Print(n);
printf("\n");
}
return ;
}
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[],str2[];
scanf("%s%s",str1,str2);
int i=,j=;
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\n",res.c_str());
return ;
}
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[]-'A')**+(str[]-'A')*+(str[]-'A');
}
int hap[N] = {};
int Map[N][N];
bool bVis[N] = {false};
int n,k;
char strStart[];
vector<int> vc[N];
string toStr(int n)
{
char str[]={'\0'};
str[] = n//+'A';
str[] = n/% + 'A';
str[] = n% + 'A';
return str;
}
int iMaxHap = ;
int iMinCost = INT_MAX;
int paths = ;
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\n",toStr(iCurI).c_str(),iCost,iMinCost,h,iMaxHap);
if(iCost == iMinCost && iCurI==dst)
{
++paths;
}
else if(iCost < iMinCost && iCurI == dst)
{
paths = ;
}
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\n",iMinCost,iMaxHap);
vcRes = v;
iMinCost = iCost;
iMaxHap = h;
return;
}
bVis[iCurI] = true;
for(int i=;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=;i<n-;++i)
{
char str[];
int h;
scanf("%s%d",str,&h);
int iStr = toNum(str);
hap[iStr] = h;
}
for(int i=;i<k;++i)
{
char str1[],str2[];
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),,,temp);
if(vcRes.size()>)
{
printf("%d %d %d %d\n",paths,iMinCost,iMaxHap,iMaxHap/(vcRes.size()-));
}
for(int i=;i<vcRes.size();++i)
{
if(i) printf("->");
printf("%s",toStr(vcRes[i]).c_str());
}
printf("\n");
return ;
}
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]={};
bool bVis[N]={};
int Map[N][N];
struct ST
{
int cost;
int hap;
int pre;
int cnt;
int iStep;
ST()
{
hap = ;
pre = ;
cnt = ;
iStep = ;
}
};
ST dp[N];
void dijstra()
{
for(int i=;i<n;++i)
{
dp[i].cost = Map[][i];
dp[i].hap = H[i];
} for(int i=;i<n;++i)
{
int minDj = INT_MAX,pos = ;
for(int j=;j<n;++j)
{
if(!bVis[j]&&dp[j].cost < minDj)
{
minDj = dp[j].cost;
pos = j;
}
}
bVis[pos] = true;
for(int j=;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+;
}
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+;
}
else if(dp[j].hap == dp[pos].hap+H[j] && dp[j].iStep > dp[pos].iStep+)
{
dp[j].pre = pos;
dp[j].iStep = dp[pos].iStep+;
}
}
}
}
}
}
int main()
{
int k;
char strStart[];
scanf("%d%d%s",&n,&k,strStart);
msi[strStart] = ;
mis[] = strStart;
for(int i=;i<n;++i)
{
char str[];
scanf("%s%d",str,&H[i]);
msi[str] = i;
mis[i] = str;
}
for(int i=;i<n;++i)
for(int j=;j<n;++j)
if(i==j) Map[i][j] = ;
else Map[i][j] = INT_MAX;
for(int i=;i<k;++i)
{
char s1[],s2[];
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\n",dp[dst].cnt,dp[dst].cost,dp[dst].hap,dp[dst].hap/dp[dst].iStep);
vector<int> res;
for(int i=dst;i!=;i=dp[i].pre)
{ res.push_back(i);
}
res.push_back();
bool bFirst = true;
for(int i=res.size()-;i>=;--i)
{
if(bFirst) bFirst = false;
else printf("->");
printf("%s",mis[res[i]].c_str());
}
printf("\n");
return ;
}
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==) return a;
return gcd(b,a%b);
}
string getstr(long long a)
{
char str[];
sprintf(str,"%lld",a);
return str;
}
struct Fen
{
long long a;
long long b;
void change()
{
if(b==) return;
if(b<) a = -a,b=-b;
long long g = gcd(abs(a),b);
a = a/g;
b = b/g;
}
string gettext()
{
change();
if(b==)
{
return "Inf";
}
else if(a==)
{
return "";
}
long long ia = abs(a),ib = b;
string res = "";
if(a<) res="(-";
if(ib==) res += getstr(ia);
else
{
long long k = ia/ib;
ia = ia%ib;
if(k>) res = res + getstr(k) + " ";
res = res + getstr(ia) + "/" + getstr(ib); }
if(a<) 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\n",f1.gettext().c_str(),f2.gettext().c_str(),f.gettext().c_str());
f = jian(f1,f2);
printf("%s - %s = %s\n",f1.gettext().c_str(),f2.gettext().c_str(),f.gettext().c_str());
f = cheng(f1,f2);
printf("%s * %s = %s\n",f1.gettext().c_str(),f2.gettext().c_str(),f.gettext().c_str());
f = chu(f1,f2);
printf("%s / %s = %s\n",f1.gettext().c_str(),f2.gettext().c_str(),f.gettext().c_str()); return ;
}
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=;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=;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\n");
for(int j=;j<n;++j)
{
if(j) printf(" ");
printf("%d",temp[j]);
}
return true;
}
}
printf("Merge Sort\n");
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=;i<n;++i)
scanf("%d",&a[i]);
for(int i=;i<n;++i)
scanf("%d",&b[i]);
bool bInsert = isInsert(a,b,n);
if(!bInsert)
{
for(int len=;;len*=)
{
bool bequ = equalarr(a,b,n);
for(int i=;i<n;i+=len)
{
sort(a+i,a+min((i+len),n));
}
if(bequ)
{
for(int i=;i<n;++i)
{
if(i) printf(" ");
printf("%d",a[i]);
}
printf("\n");
break;
}
}
}
return ;
}
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[][][];
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<||curl>=l||curm<||curm>=m||curn<||curn>=n) return false;
if(a[curm][curn][curl]==) return false;
return true;
}
int bfs(int curl,int curm,int curn)
{
int cnt = ;
Point p(curl,curm,curn);
if(bOK(p.l,p.m,p.n)==false) return ;
a[curm][curn][curl]=;
queue<Point> qi;
qi.push(p);
while(!qi.empty())
{
p = qi.front();
qi.pop();
++cnt;
if(bOK(p.l+,p.m,p.n))
{
qi.push(Point(p.l+,p.m,p.n));
a[p.m][p.n][p.l+] = ;
}
if(bOK(p.l-,p.m,p.n))
{
qi.push(Point(p.l-,p.m,p.n));
a[p.m][p.n][p.l-] = ;
}
if(bOK(p.l,p.m+,p.n))
{
qi.push(Point(p.l,p.m+,p.n));
a[p.m+][p.n][p.l] = ;
}
if(bOK(p.l,p.m-,p.n))
{
qi.push(Point(p.l,p.m-,p.n));
a[p.m-][p.n][p.l] = ;
}
if(bOK(p.l,p.m,p.n+))
{
qi.push(Point(p.l,p.m,p.n+));
a[p.m][p.n+][p.l] = ;
}
if(bOK(p.l,p.m,p.n-))
{
qi.push(Point(p.l,p.m,p.n-));
a[p.m][p.n-][p.l] = ;
} }
return cnt>=t?cnt:;
}
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=;i<l;++i)
for(int j=;j<m;++j)
for(int k=;k<n;++k)
scanf("%d",&a[j][k][i]);
int res=;
for(int i=;i<l;++i)
for(int j=;j<m;++j)
for(int k=;k<n;++k)
{
res += bfs(i,j,k);
}
printf("%d\n",res);
return ;
}
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")==) bIn = true;
else bIn = false;
tick = **h+*m+s;
}
};
int cmp(const CarInOutTime& t1,const CarInOutTime& t2)
{
return t1.tick<t2.tick;
}
int Ti[TN]; //每秒钟车的个数
int Tm[TN/]; //每分钟
struct Car
{
string carid;//车牌
vector<CarInOutTime> inouttime; //出入时间
int captime; //在校园中逗留的时间
Car(){captime=;}
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=;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%==&&tick+<=inouttime[i].tick)
{
++Tm[tick/]; //因为这车在这一分钟都在
tick += ;
}
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 = ;
for(int i=;i<n;++i)
{
char carid[],opt[];
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 = ;
for(int i=;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=;i<k;++i)
{
int h,m,s;
scanf("%d:%d:%d",&h,&m,&s);
int tick = h**+m*+s;
printf("%d\n",Ti[tick]+Tm[tick/]);
}
sort(vs.begin(),vs.end());
for(int i=;i<vs.size();++i)
printf("%s ",vs[i].c_str());
printf("%02d:%02d:%02d\n",maxti/,maxti%/,maxti%);
return ;
}
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 = ;
for(int i=;i<len;++i)
sum = sum*(n+i);
return sum;
}
int main()
{
int n;
scanf("%d", &n); for(int len=;len>=;--len)
{
long long int sum;
for(int i=;(sum=getSum(i,len))<=n;++i)
{
//sum必须是long long否则撑起来会负数。
if(len==&&sum*sum > n)
{
break;
}
if(n%sum==)
{
printf("%d\n",len);
for(int j=;j<len;++j)
{
if(j) printf("*");
printf("%d",i+j);
}
return ;
}
}
}
printf("1\n%d\n",n);
return ;
}
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 = ;
for(int i=;i<p;++i)
{
res *= n;
}
return res;
}
int n,k,p,sum2=;
bool bOK;
vector<int> res;
void dfs(int sum,int totalsum,int i,int len,vector<int> vi)
{
//printf("totalsum=%d i=%d\n",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>=;--j)
{
vi.push_back(j);
dfs(sum+mypow(j,p),totalsum+j,j,len+,vi);
vi.pop_back();
}
}
int main()
{
//freopen("test.txt","r",stdin);
scanf("%d%d%d",&n,&k,&p);
if(k==)
{
int sum;
for(int i=;(sum=mypow(i,p))<=n;++i)
{
if(sum == n)
{
printf("%d = ",n);
printf("%d^%d\n",i,p);
return ;
}
}
printf("Impossible\n");
}
else
{
int sum,iMaxF = ;
for(int i=;true;++i)
{
sum = mypow(i,p)+(k-);
if(sum >= n)
{
iMaxF = i;
break;
}
}
for(int i=iMaxF;i>=;--i)
{
vector<int> vi;
vi.push_back(i);
dfs(mypow(i,p),i,i,,vi);
}
if(bOK)
{
printf("%d = ",n);
for(int i=;i<res.size();++i)
{
if(i) printf(" + ");
printf("%d^%d",res[i],p);
}
printf("\n");
}
else
printf("Impossible\n");
}
return ;
}
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=;i<H;++i)
p[i] = i;
int n;
scanf("%d",&n);
for(int i=;i<n;++i)
{
int k,pre;
scanf("%d:",&k);
for(int ik=;ik<k;++ik)
{
int a;
scanf("%d",&a);
if(ik==)
{
peo[i] = a;
}
else
{
Union(pre,a);
}
pre = a;
}
}
map<int,int> mii;
for(int i=;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\n",vi.size());
for(int i=vi.size()-;i>=;--i)
{
if(i) printf("%d ",vi[i]);
else printf("%d\n",vi[i]);
}
return ;
}
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[];
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)<;
}
void Print(ST* st,int istart,int len)
{
string strname[len];
int imid = (len)/;
strname[imid] = st[istart].name;
for(int i=istart+,j=;i<istart+len;i += ,++j)
{
if(i<istart+len)
strname[imid-j] = st[i].name;
if(i+<istart+len)
strname[imid+j] = st[i+].name;
}
for(int i=;i<len;++i)
{
if(i) printf(" ");
printf("%s",strname[i].c_str());
}
printf("\n");
}
int main()
{
//freopen("test.txt","r",stdin);
int n,k;
scanf("%d%d",&n,&k);
ST st[n];
for(int i=;i<n;++i)
{
scanf("%s%d",st[i].name,&st[i].height);
}
sort(st,st+n,cmp);
k = n/k;
for(int i=;i<n;)
{
int len = k;
if(i==)
{
len = (n>=k?k:)+n%k;
}
Print(st,i,len);
i += len;
}
return ;
}
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]={};
int cnt = ;
Node* lastnode = NULL;
bool bVis[N] = {};
void level_travel(vector<Node*> vn,int level)
{
if(vn.size()==) return;
cnt += vn.size();
vector<Node*> vnnext;
for(int i=;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 = ;
for(int i=;i<level;++i)
{
stdcnt *= ;
}
if(stdcnt != vn.size())
{
return;
}
level_travel(vnnext,level+);
}
}
int main()
{
//freopen("test.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i=;i<n;++i)
{
char cl[],cr[];
scanf("%s%s",cl,cr);
nodes[i].key = i;
if(cl[]!='-')
{
nodes[i].left = &nodes[atoi(cl)];
++indegree[atoi(cl)];
}
if(cr[]!='-')
{
nodes[i].right = &nodes[atoi(cr)];
++indegree[atoi(cr)];
}
}
Node* root = NULL;
for(int i=;i<n;++i)
{
if(indegree[i]==)
{
root = &nodes[i];
break;
}
}
vector<Node*> vn;
lastnode = root;
bVis[root->key] = true;
vn.push_back(root);
level_travel(vn,);
if(cnt == n)
{
printf("YES %d\n",lastnode->key);
}
else
{
printf("NO %d\n",root->key);
}
return ;
}
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,,sizeof(bVis));
int dp[n];
int fast[n];
int pre[n];
for(int i=;i<n;++i)
{
dp[i] = Dis[startpos][i];
fast[i] = Tim[startpos][i];
pre[i] = startpos;
}
bVis[startpos] = true;
for(int i=;i<n;++i)
{
int mindj=INF,minti=INF,pos = startpos;
for(int j=;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=;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,,sizeof(bVis));
int dp[n];
int ins[n];
int pre[n];
for(int i=;i<n;++i)
{
dp[i] = Tim[startpos][i];
ins[i] = ;
pre[i] = startpos;
}
bVis[startpos] = true;
for(int i=;i<n;++i)
{
int mindj=INF,minins=INF,pos = startpos;
for(int j=;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=;j<n;++j)
{
if(!bVis[j] && (dp[j] > dp[pos]+Tim[pos][j] ||
dp[j] == dp[pos]+Tim[pos][j]&&ins[j] > ins[pos]+))
{
pre[j] = pos;
dp[j] = dp[pos]+Tim[pos][j];
ins[j] = ins[pos]+;
}
}
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=;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=;i<n;++i)
for(int j=;j<n;++j)
{
if(i==j)
{
Dis[i][j] = Tim[i][j] = ;
}
else
{
Dis[i][j] = Tim[i][j] = INF;
}
}
for(int i=;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==)
{
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=;i<vcDis.size();++i)
{
if(i) printf(" -> ");
printf("%d",vcDis[i]);
}
printf("\n");
}
else
{
printf("Distance = %d: ",resDis);
for(int i=;i<vcDis.size();++i)
{
if(i) printf(" -> ");
printf("%d",vcDis[i]);
}
printf("\n");
printf("Time = %d: ",resTim);
for(int i=;i<vcTim.size();++i)
{
if(i) printf(" -> ");
printf("%d",vcTim[i]);
}
printf("\n");
}
return ;
}
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=;i<n;++i)
{
scanf("%d",&a[i]);
}
sort(a,a+n,cmp);
for(int len=n;len>=;--len)
{
if(a[len-]>len)
{
printf("%d\n",len);
return ;
}
}
printf("0\n");
return ;
}
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 != )
{
//printf("len=%d\n",len);
if(*(pre+) == *(post+len-))
{
bOnly = false;
node->left = CreateTree(pre+,post,len-);
}
else
{
int rightkey = *(post+len-);
int rightindex = ;
for(;rightindex<len;++rightindex)
{
if(rightkey == *(pre+rightindex))
{
break;
}
}
node->left = CreateTree(pre+,post,rightindex-);
node->right = CreateTree(pre+rightindex,post+rightindex-,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=;i<n;++i)
scanf("%d",&pre[i]);
for(int i=;i<n;++i)
scanf("%d",&post[i]);
Node* root = CreateTree(pre,post,n);
if(bOnly)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
inorder_travel(root);
printf("\n");
return ;
}
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=;
void dfs(int curI,int istep)
{
++sum;
for(int nextI=;nextI<=n;++nextI)
{
if(Map[curI][nextI]&&!bVis[nextI])
{
bVis[nextI] = true;
dfs(nextI,istep+);
}
}
}
/*给定一个图，计算该图的每个结点的度
若所有的节点的度均为偶数则为“Eulerian”，
若恰好有两个为奇数则为“Semi-Eulerian”，
其他为“Non-Eulerian”。
需要判断是否是连通图。
*/
int main()
{
//freopen("test.txt","r",stdin);
scanf("%d%d",&n,&m);
memset(Map,,sizeof(Map));
memset(indegree,,sizeof(indegree));
memset(bVis,,sizeof(bVis));
for(int i=;i<m;++i)
{
int a,b;
scanf("%d%d",&a,&b);
Map[a][b] = Map[b][a] = ;
++indegree[a];
++indegree[b];
}
int iOddnum=;
for(int i=;i<=n;++i)
{
if(indegree[i]%)
{
++iOddnum;
}
if(i>) printf(" ");
printf("%d",indegree[i]);
}
printf("\n");
bVis[] = true;
dfs(,);
if(sum==n)
{
if(iOddnum==) printf("Eulerian\n");
else if(iOddnum==) printf("Semi-Eulerian\n");
else printf("Non-Eulerian\n");
}
else
{
printf("Non-Eulerian\n");
} return ;
}
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=;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()-].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()-].stop = nextI;
}
dfs(nextI,len+,vi);
if(bNeedAdd)
vi.pop_back();
else
{
vi[vi.size()-].stop = curI;
}
bVis[nextI] = false;
}
}
}
int main()
{
//freopen("test.txt","r",stdin);
int n;
scanf("%d",&n);
int prestop;
for(int i=;i<n;++i)
{
int m;
scanf("%d",&m);
for(int j=;j<m;++j)
{
int a;
scanf("%d",&a);
if(j==) prestop = a;
else
{
vcMap[prestop].push_back(a);
vcMap[a].push_back(prestop);
line[prestop+a*N] = i+;
line[a+prestop*N] = i+;
prestop = a;
}
}
}
int k;
scanf("%d",&k);
for(int i=;i<k;++i)
{
memset(bVis,,sizeof(bVis));
iMinLen = N;
scanf("%d%d",&iStartStop,&iEndStop);
bVis[iStartStop] = ;
vs.clear();
vector<ST> vi;
dfs(iStartStop,,vi);
printf("%d\n",iMinLen);
for(int j=;j<vs.size();++j)
{
printf("Take Line#%d from %04d to %04d.\n",vs[j].line,vs[j].start,vs[j].stop);
}
}
return ;
}
最新文章
- Mono 4.0 Mac上运行asp.net mvc 5.2.3
- java 基础三 下雪
- Studio for Winforms FlexGrid: 创建分类汇总
- 【BZOJ】1146: [CTSC2008]网络管理Network（树链剖分+线段树套平衡树+二分 / dfs序+树状数组+主席树）
- OAuth2.0协议
- Java三十个面试题总结
- Java学习之国际化程序
- GtkImageMenuItem
- jQuery给表单设置值
- [ABP]浅谈工作单元 在整个 ABP 框架当中的应用
- get_k_data 接口文档 全新的免费行情数据接口
- @Html自定义属性
- 为Sublime Text 设置全局启动快捷键
- div左右居中css
- 分布式系统缓存系列之guava cache
- mysql 数据表操作 目录
- PAT 甲级 1011 World Cup Betting (20)（20 分）
- 02-centOS6.7安装
- Oracle 声明常量 (转)
- PCI Simple Communications Controller