天梯赛赛前练习

模拟/暴力

L2-018 多项式A除以B（模拟多项式除法）

注意特殊的输出格式：零多项式是一个特殊多项式，对应输出为0 0 0.0

输出的系数保留小数点后1位，舍入后为0.0，则不输出

意味着输出的数的绝对值至少都要大于0.05

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; typedef long long ll; double c1[maxn],c2[maxn],ac[maxn]; int main(){int n;cin>>n;int maxa=0;for(int i=0;i<n;i++){int x;double y;cin>>x>>y;maxa=max(maxa,x);c1[x]=y;}int m;cin>>m;int maxb=0;for(int i=0;i<m;i++){int x;double y;cin>>x>>y;maxb=max(maxb,x);c2[x]=y;}if(maxa<maxb){printf("0 0 0.0\n");printf("%d",n);for(int i=maxa;i>=0;i--){if(fabs(c1[i])>=0.05){printf(" %d %.1lf",i,c1[i]);}}printf("\n");}else{int ans=0;while(maxa>=maxb){int e=maxa-maxb;double c=c1[maxa]/c2[maxb];//printf("%d %.1lf\n",e,c);ac[e]+=c;ans=max(ans,e);double tmp[maxn];for(int j=maxb;j>=0;j--){int ee=e+j;double cc=c*c2[j];tmp[ee]=cc;}int mmax=0;for(int j=maxa;j>=0;j--){if(fabs(c1[j]-tmp[j])<0.05){c1[j]=0.0;continue;}else{c1[j]-=tmp[j];mmax=max(mmax,j);}}maxa=mmax; }int cnt=0;int mmax=0;for(int i=ans;i>=0;i--){if(fabs(ac[i])>=0.05){cnt++;mmax=max(mmax,i);}}if(cnt==0){printf("0 0 0.0\n");}else{printf("%d",cnt);for(int i=mmax;i>=0;i--){if(fabs(ac[i])>=0.05){printf(" %d %.1lf",i,ac[i]);}}printf("\n");}cnt=0;for(int i=maxa;i>=0;i--){if(fabs(c1[i])>=0.05){cnt++;}}if(cnt==0){printf("0 0 0.0\n");}else{printf("%d",cnt);for(int i=maxa;i>=0;i--){if(fabs(c1[i])>=0.05){printf(" %d %.1lf",i,c1[i]);}}printf("\n");}} return 0; }

L2-028 秀恩爱分得快 (25 分)

“我们把所有人从 0 到 N-1 编号。为了区分性别，我们用编号前的负号表示女性”

注意==“-0”==的情况，代表0为女性，所以不能简单的使用int输入，判断正负。

注意时间复杂度！无用数据不要管，只看对最终结果有影响的数据！

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e4+10; vector<int>img[maxn]; double sum[maxn][maxn]; int vis[maxn][maxn]; vector<int>ans1,ans2; int xb[maxn]; int check(string s){int x;if(s[0]=='-'){x=stoi(s.substr(1));xb[x]=-1;}else x=stoi(s),xb[x]=1; return x; } int main(){int n,m;cin>>n>>m;//存照片、性别 //不是所有照片都有用，只有s和t出现的照片才有用for(int i=0;i<m;i++){int k;cin>>k;for(int j=0;j<k;j++){string s;int x;cin>>s;x=check(s); img[i].push_back(x);vis[i][x]=1;//表示x出现在第i张照片上}}int x,y;string s,t;cin>>s>>t;x=check(s);y=check(t);double mmax=0,mmay=0;for(int i=0;i<m;i++){int k=img[i].size();if(vis[i][x]){//x出现在第i张照片上for(int j=0;j<img[i].size();j++){int a=img[i][j];if(xb[x]!=xb[a]){sum[x][a]+=1.0/k;mmax=max(sum[x][a],mmax);}}}if(vis[i][y]){//y出现在第i张照片上for(int j=0;j<img[i].size();j++){int a=img[i][j];if(xb[y]!=xb[a]){sum[y][a]+=1.0/k;mmay=max(sum[y][a],mmay);}}}}if(sum[x][y]==mmax&&sum[y][x]==mmay) cout<<s<<" "<<t<<endl;else{for(int i=0;i<n;i++){if(xb[x]!=xb[i]&&sum[x][i]==mmax){cout<<s<<" ";if(i!=0) cout<<xb[i]*i<<endl;else{if(xb[i]==-1) cout<<"-0\n";else cout<<"0\n";}}}for(int i=0;i<n;i++){if(xb[y]!=xb[i]&&sum[y][i]==mmay){cout<<t<<" ";if(i!=0) cout<<xb[i]*i<<endl;else{if(xb[i]==-1) cout<<"-0\n";else cout<<"0\n";}}}}return 0; }

L2-030 冰岛人 (25 分)

读题！读题！读题！

冰岛人姓名组成：名+姓（姓为其父亲的名+性别后缀）

普通人姓名组成：名+姓（姓只是单纯的姓氏+性别后缀）

“五代以内无公共祖先”是指两人的公共祖先（如果存在的话）必须比任何一方的曾祖父辈分高。

意味着：如果a和b的公共祖先是c，c是a的第六代祖先，但却是b的第三代祖先，也属于五代以内存在公共祖先！

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; map<string,int>mp;//将名字转为数字 map<string,string>fa;//记录父辈 int xb[maxn];//性别 int vis[maxn]; int bx[maxn],by[maxn];//第几代 int check(string f,string s){//标记性别和其父辈int l=s.size();string name;int flag;if(s[l-1]=='m'||s[l-1]=='f'){//父辈未知name=s.substr(0,l-1);flag=(s[l-1]=='m')?1:-1;}else if(s[l-1]=='n'){name=s.substr(0,l-4);fa[f]=name;flag=1;}else{name=s.substr(0,l-7);flag=-1;fa[f]=name;}return flag; } int main(){int n;cin>>n;for(int i=1;i<=n;i++){string fir,sec;cin>>fir>>sec;mp[fir]=i;xb[i]=check(fir,sec);}int m;cin>>m;for(int i=0;i<m;i++){string m1,x1,m2,x2;cin>>m1>>x1>>m2>>x2;if(xb[mp[m1]]*xb[mp[m2]]>0) puts("Whatever");else if(mp[m1]==0||mp[m2]==0) puts("NA");else{memset(vis,0,sizeof(vis));memset(bx,0,sizeof(bx));memset(by,0,sizeof(by));vis[mp[m1]]=1;int cnt1=1,cnt2=1;while(fa[m1]!=""){x1=fa[m1];int fx=mp[x1];cnt1++;bx[fx]=cnt1;vis[fx]=1;m1=x1; }int flag=0;if(vis[mp[m2]]){//m2就是m1的祖先flag=1;}else{while(fa[m2]!=""){x2=fa[m2];int fx=mp[x2];cnt2++;by[fx]=cnt2;if(vis[fx]){//公共祖先if(by[fx]<5||bx[fx]<5){flag=1;break;}break;}vis[fx]=1;m2=x2;}}if(!flag) puts("Yes");else puts("No");}}return 0; }

L2-034 口罩发放 (25 分)

1、身份证号唯一标识一个人

2、合法记录：身份证号必须是18位的数字（不是18位或者出现其他字符都不可以！）

3、“如果提交时间相同，则按照在列表中出现的先后顺序决定。”

sort的时候不能只比时间，还要比较出现顺序！！！

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; struct peo{string name;string id;int pid;int s;int time; }p[maxn]; map<string,int>mp,vis; vector<peo>ans; bool cmp(peo a,peo b){if(a.time==b.time) return a.pid<b.pid;return a.time<b.time; } int main(){int d,P;cin>>d>>P;for(int i=1;i<=d;i++){int t,s;cin>>t>>s;int cnt=0;for(int j=0;j<t;j++){string a,b;int x,y,z;cin>>a>>b>>x;scanf("%d:%d",&y,&z);if(b.size()!=18) continue;//判断是否合法int flag=0;for(int i=0;i<b.size();i++){if(b[i]<'0'||b[i]>'9'){flag=1;break;}}if(flag) continue;p[cnt].pid=cnt;//出现顺序p[cnt].name=a;p[cnt].id=b;p[cnt].s=x;p[cnt].time=y*60+z;if(p[cnt].s==1&&vis[p[cnt].id]==0){ans.push_back(p[cnt]);vis[p[cnt].id]=1;}cnt++;}sort(p,p+cnt,cmp);int num=0;for(int j=0;j<cnt;j++){string id=p[j].id;if(num>=s) break;if(mp[id]==0||(i-mp[id]>P)){cout<<p[j].name<<" "<<p[j].id<<endl;mp[p[j].id]=i;//更新此人领口罩的snum++;}}}for(int i=0;i<ans.size();i++){cout<<ans[i].name<<" "<<ans[i].id<<endl;}return 0; }

L1-002 打印沙漏 (20 分)

主要是根据等差数列求和公式来计算行数，不要直接计算（容易出错）

这样遍历，不会出错，而且数据也很小，不会T。

while(1){//首项从3开始： 2*r*(r+2)+1>n//首项从1开始，公差为2，利用等差数列求和公式na+n(n-1)/2：r*r-1>n,r--if(2*(r+1)*(r+1)-1>n){//首项从1开始，利用奇数项求和公式(n+1)(a+nd)break;}r++; }

L1-006 连续因子 (20 分)

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){int n;cin>>n;int len=-1;int ans=2;for( l=2;l<=sqrt(n);l++){//如果写成l*l<=n，则要开long long，所以最好还是写成这样if(n%l==0){int m=n;int r=l;while(m%r==0){m/=r;r++;}if(len<r-l){len=r-l;ans=l;}}}if(len==-1){cout<<"1\n";cout<<n<<endl;return 0;}cout<<len<<endl;for(int i=ans;i<ans+len;i++){if(i==ans) cout<<i;else cout<<"*"<<i;}return 0; }

L1-009 N个数求和 (20 分)

注意审题！

输入格式：

输入第一行给出一个正整数N（≤100）。随后一行按格式a1/b1 a2/b2 ...给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外，负数的符号一定出现在分子前面。

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b); } int main(){ll n;scanf("%lld",&n);ll fz,fm,g,lcm;scanf("%lld/%lld",&fz,&fm);for(int i=1;i<n;i++){ll x,y;scanf("%lld/%lld",&x,&y);g=gcd(y,fm);lcm=fm*y/g;fz=(lcm/fm)*fz+(lcm/y)*x; fm=lcm; }if(fz==0) cout<<"0\n";else{g=gcd(fz,fm);fz/=g;fm/=g;if(fm==1) cout<<fz<<endl;else if(fz/fm>0) cout<<fz/fm<<" "<<fz-(fz/fm)*fm<<"/"<<fm<<endl;else cout<<fz<<"/"<<fm<<endl;}return 0; }

L3-006 迎风一刀斩 (30 分)

1、无论如何旋转，形状不会发生改变，由于只旋转90、180或270，所以相邻点要么横坐标相等，要么纵坐标相等（除非该边是斜边）

2、一共4种切法

3+5 、 3+4 、 3+5 、4+4

4+4又可细分为两种情况：

1）平行于坐标轴切开，两矩形不存在斜边,只需看是否有一边边长相等即可

2）两梯形存在斜边：需考虑一种特殊情况–>斜边相等，直角腰不相等

#include<bits/stdc++.h> using namespace std; struct point{int x,y; }; int main(){int n;cin>>n;for(int i=0;i<n;i++){int k1,k2;cin>>k1;vector<point>v1,v2;for(int j=0;j<k1;j++){ //图形输入 int x,y;cin>>x>>y;v1.push_back({x,y});}cin>>k2;for(int j=0;j<k2;j++){int x,y;cin>>x>>y;v2.push_back({x,y});}if(k1+k2>8){ //非法情况 cout<<"NO\n";continue;}if(k1==4&&k2==4){ //特殊情况 int l=0,w=0,a=0,b=0; int cnt=0,z1=0,z2=0;for(int j=0;j<k1;j++){if(v1[j].x==v1[(j+1)%k1].x||(v1[j].y==v1[(j+1)%k1].y)) continue;l=abs(v1[j].x-v1[(j+1)%k1].x); //补全缺口，所需三角形的两条直角边长 w=abs(v1[j].y-v1[(j+1)%k1].y);//直角腰 z1=abs(v1[(j+2)%k1].x-v1[(j+3)%k1].x)+abs(v1[(j+2)%k1].y-v1[(j+3)%k1].y);}for(int j=0;j<k2;j++){if(v2[j].x==v2[(j+1)%k2].x||(v2[j].y==v2[(j+1)%k2].y)) continue; a=abs(v2[j].x-v2[(j+1)%k2].x);b=abs(v2[j].y-v2[(j+1)%k2].y);z2=abs(v2[(j+2)%k2].x-v2[(j+3)%k2].x)+abs(v2[(j+2)%k2].y-v2[(j+3)%k2].y);}if(a==l&&b==w||(a==w&&b==l)){ //两梯形缺口互补 if(z1==z2) cout<<"YES\n"; //且直角腰相等 else cout<<"NO\n";}else cout<<"NO\n";continue;}vector<point>tmp;if(k1<k2){ //调整为 4-3、5-3 swap(k1,k2);tmp=v1;v1=v2;v2=tmp;}int l=0,w=0,a=0,b=0;for(int j=0;j<k1;j++){if(v1[j].x==v1[(j+1)%k1].x||(v1[j].y==v1[(j+1)%k1].y)) continue;l=abs(v1[j].x-v1[(j+1)%k1].x);w=abs(v1[j].y-v1[(j+1)%k1].y);}for(int j=0;j<k2;j++){if(v2[j].x==v2[(j+1)%k2].x){a=abs(v2[j].y-v2[(j+1)%k2].y);}else if(v2[j].y==v2[(j+1)%k2].y){b=abs(v2[j].x-v2[(j+1)%k2].x);}}if(a==l&&b==w||(a==w&&b==l)){ // 缺口和三角形可以匹配 cout<<"YES\n";}else cout<<"NO\n";}return 0; }

字符串题

L1-078 吉老师的回归 (15 分)

回想去年就是因为这道题有一个点一直过不了而痛失个人铜。。。

现在重新做题，也是发现了自己思维上的漏洞吧，果然还是自己实力有限。。。

#include<bits/stdc++.h> using namespace std; const int maxn=1e3+10; typedef long long ll; string s[maxn]; int main() {int n,m;cin>>n>>m;getchar();for(int i=0;i<n;i++){getline(cin,s[i]);}int cnt=0;int i=0;for(;i<n;i++){int f1=s[i].find("qiandao");int f2=s[i].find("easy");//cout<<f1<<" "<<f2<<endl;没找到返回-1if((f1!=-1)||(f2!=-1)) continue;else cnt++;if(cnt>m){//当前做题数为cnt+1，直接输出cout<<s[i]<<endl;break;}}if(cnt<=m) cout<<"Wo AK le\n";//虽然做题数没超过m，但是题目已经被全部做完了！AK！return 0; }

L2-008 最长对称子串 (25 分)

暴力

#include<bits/stdc++.h> using namespace std; int main(){string s;getline(cin,s);int l=0;int maxl=0;for(int i=0;i<s.size();i++){for(int j=s.size()-1;j>=i;j--){int l=i,r=j;while(l<=r&&s[l++]==s[r--]){if(l>r) maxl=max(maxl,j-i+1);}}}cout<<maxl<<endl;return 0; }

WA

#include<bits/stdc++.h> using namespace std; int main(){string s;getline(cin,s);int l=0;int maxl=0;while(l<s.size()){int r=s.size()-1;while(s[r]!=s[l]&&r>l) r--;if(r<l){l++;continue;}int i=l;int j=r;while(i<=j&&s[i++]==s[j--]){if(i>j) maxl=max(maxl,r-l+1);}l++;}cout<<maxl<<endl;return 0; }

STL

L2-039 清点代码库 (25 分)

map<vector,int>mp;

map默认按key值从小到大排序，因此vector会排好序

将map种的每对元素以pair的形式存入vector中，sort默认按pair的first从小到大进行排序

可将次数前加负号，也可重写cmp函数

(不知道为什么不能用map<string,int>来写，一直有两个点过不去。。。)

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e4+10; const int INF=0x3f3f3f3f; typedef pair<int,vector<int>> p; map<vector<int>,int>mp; vector<p>ans; //bool cmp(const p &a,const p &b){ // if(a.first!=b.first) return a.first>b.first; // for(int i=0;i<a.second.size();i++){ // if(a.second[i]!=b.second[i]){ // return a.second[i]<b.second[i]; // } // } //} int main(){int n,m;cin>>n>>m;for(int i=0;i<n;i++){vector<int>v;for(int j=0;j<m;j++){int x;cin>>x;v.push_back(x);}mp[v]++;}cout<<mp.size()<<endl;map<vector<int>,int>::iterator it1=mp.begin();for(;it1!=mp.end();it1++){ans.push_back(make_pair(-1*it1->second,it1->first));}sort(ans.begin(),ans.end());//sort(ans.begin(),ans.end(),cmp);vector<p>::iterator it2=ans.begin();for(;it2!=ans.end();it2++){cout<<-1*it2->first;for(int i=0;i<it2->second.size();i++){cout<<" "<<it2->second[i];}cout<<endl;}return 0; }

L3-002 特殊堆栈 (30 分)

vector在插入和删除的同时维护其升序状态

vector插入和删除时就按照大小顺序进行，避免每次重新排序

vector的妙用

//vector添加指定位置的元素（下标从0开始） //在最前面的元素插入x v.insert(v.begin(),x); //在下标为2的元素前插入x v.insert(v.begin()+2,x); //在末尾插入x v.insert(v.end(),x);//vector删除指定元素 //删除下标为2的元素（第3个元素） v.erase(v.begin()+2); //删除一段元素 v.erase(v.begin()+1,v.begin()+5);

vector做法

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; typedef long long ll; const int mod=1e9+7; vector<int>a; stack<int>st; int main(){int n;cin>>n;while(n--){string s;int x;cin>>s;if(s=="Pop"){if(st.empty()) puts("Invalid");else{int tmp=st.top();st.pop();int k=lower_bound(a.begin(),a.end(),tmp)-a.begin();a.erase(a.begin()+k);cout<<tmp<<endl;}}else if(s=="Push"){cin>>x;st.push(x);int k=lower_bound(a.begin(),a.end(),x)-a.begin();a.insert(a.begin()+k,x);}else{if(st.empty()) puts("Invalid");else{int l=a.size();int k=(l-1)/2;cout<<a[k]<<endl;}}}return 0; }

线段树做法

线段树维护各正整数出现的次数，查找中值，即查询线段树上的第$(cnt+1)/2$个值

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; struct node{int l,r;int cnt;//区间[l,r]中各数字出现次数之和 }tree[maxn<<2]; int st[maxn]; void bt(int root,int l,int r){if(l==r){tree[root].l=tree[root].r=l;}else{tree[root].l=l;tree[root].r=r;int mid=(l+r)>>1;bt(root<<1,l,mid);bt(root<<1|1,mid+1,r);} } void update(int root,int idx,int val){//单点修改 if(tree[root].l==tree[root].r){tree[root].cnt+=val;}else{int mid=(tree[root].l+tree[root].r)>>1;if(idx<=mid) update(root<<1,idx,val);//注意区间判断，无需进行无效递归else update(root<<1|1,idx,val);tree[root].cnt=tree[root<<1].cnt+tree[root<<1|1].cnt;//更新当前结点的值} } int query(int root,int num){//单点查询 if(tree[root].l==tree[root].r){return tree[root].l;}if(tree[root<<1].cnt>=num) return query(root<<1,num); //左区间各数字出现次数就达到了num，那就只查询左区间，否则在右区间中找剩下的else return query(root<<1|1,num-tree[root<<1].cnt); } int main(){bt(1,1,maxn);//建树，维护结点表示的区间int n;cin>>n;int num=0;while(n--){string s;cin>>s;if(s=="Pop"){if(num==0) cout<<"Invalid\n";else{cout<<st[num]<<endl;update(1,st[num],-1);//出栈，将对应数字出现次数减1num--;}}else if(s=="Push"){int x;cin>>x;st[++num]=x;update(1,st[num],1);//入栈，将对应数字出现次数加1}else{if(num<=0) cout<<"Invalid\n";else{int mid=(num+1)>>1;cout<<query(1,mid)<<endl;//查询，线段树上的第mid个数字}}}return 0; }

搜索

DFS

L3-029 还原文件（30分）

#include<bits/stdc++.h> using namespace std; const int maxn=2e5+10; const int mod=1000000007; const int INF=0x3f3f3f3f; typedef long long ll; int n,m; int H[maxn],k[maxn]; int h[110][maxn]; vector<int>ans; int vis[110]; void dfs(int idx){if(ans.size()==m){for(int i=0;i<m;i++){cout<<ans[i];if(i==m-1) cout<<endl;else cout<<" ";}return;}for(int i=1;i<=m;i++){if(!vis[i]){int flag=1;for(int j=1;j<=k[i];j++){if(H[idx+j]!=h[i][j]){flag=0;break;}}if(flag){vis[i]=1;ans.push_back(i);dfs(idx+k[i]-1);vis[i]=0;ans.pop_back();}}} } int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&H[i]);}scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d",&k[i]);for(int j=1;j<=k[i];j++){scanf("%d",&h[i][j]); }}dfs(0);return 0; }

L2-016 愿天下有情人都是失散多年的兄妹

每行给出以下信息： 本人ID 性别 父亲ID 母亲ID

本人性别明确，但其父母的性别未必明确（输入中可能根本不存在其父母的信息），所以需要手动补充父母的性别信息！！！便于后续的判断！

采集数据过程中注意数据的完整性！

#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; const int INF=0x3f3f3f3f; typedef long long ll; vector<int>p[maxn]; int xb[maxn]; int vis[maxn]; int flag; void dfs(int x,int cnt){if(flag) return; if(cnt>5) return;vis[x]=1;for(int i=0;i<p[x].size();i++){if(!vis[p[x][i]]){dfs(p[x][i],cnt+1);}else{flag=1;break;}} } int main(){int n;cin>>n;for(int i=0;i<n;i++){int id,fa,mo;char s;cin>>id>>s>>fa>>mo;if(fa!=-1){p[id].push_back(fa);xb[fa]=1;//手动补充性别信息}if(mo!=-1){p[id].push_back(mo);xb[mo]=2;}if(s=='M') xb[id]=1;else xb[id]=2;} int k;cin>>k;for(int i=0;i<k;i++){int x,y;cin>>x>>y;if(xb[x]==xb[y]) puts("Never Mind");else{ memset(vis,0,sizeof(vis));flag=0;dfs(x,1);dfs(y,1);if(!flag) puts("Yes");else puts("No");}}return 0; }

L3-001 凑零钱 (30 分)

DFS+剪枝

如果所有钱加在一起都不够，那直接输出"No Solution"，否则最后一个测试点超时。

dfs里return的条件和剪枝条件注意先后顺序！！！

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; typedef long long ll; const int mod=1e9+7; int n,m; vector<int>money,ans; int flag; void dfs(int x,int sum){if(flag) return;if(sum==m){flag=1;for(int i=0;i<ans.size();i++){cout<<ans[i];if(i==ans.size()-1) cout<<endl;else cout<<" ";}return;}if(x==n||sum>m) return;//对于x=n的判断不能放在sum=m的前面，有可能x=n时sum也恰好等于m，就会判错ans.push_back(money[x]);dfs(x+1,sum+money[x]);ans.pop_back();dfs(x+1,sum); } int main(){cin>>n>>m;ll sum=0;for(int i=0;i<n;i++){int x;cin>>x;sum+=x;money.push_back(x);}if(sum<m) puts("No Solution");else{sort(money.begin(),money.end());dfs(0,0);if(!flag) puts("No Solution");}return 0; }

01背包变形

恰好装满

//dp[i][j]:前i枚硬币凑成不超过j元，最多选择几枚 //dp[i][j]=dp[i-1][j-a[i]]+1 #include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; typedef long long ll; const int mod=1e9+7; int dp[maxn]; int a[maxn]; int pre[maxn]; int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);memset(dp,-0x3f,sizeof(dp));//初始化为不可能取到的值dp[0]=0;dp[a[1]]=1;pre[a[1]]=a[1];for(int i=2;i<=n;i++){for(int j=m;j>=0;j--){if(j>=a[i]&&dp[j-a[i]]>=0){if(dp[j-a[i]]+1>=dp[j]){//注意取等，更新路径dp[j]=dp[j-a[i]]+1;pre[j]=a[i];}}}}if(dp[m]<=0){cout<<"No Solution\n";}else{vector<int>ans;while(m>=a[1]){//cout<<pre[m]<<endl;ans.push_back(pre[m]);m-=pre[m];}for(int i=ans.size()-1;i>=0;i--){cout<<ans[i];if(i==0) cout<<endl;else cout<<" ";}}return 0; }

L3-015 球队“食物链” (30 分)

DFS+剪枝

输入格式：

输入第一行给出一个整数N（2≤N≤20），为参赛球队数。随后N行，每行N个字符，给出了N×N的联赛结果表，其中第i行第j列的字符为球队i在主场对阵球队j的比赛结果：W表示球队i战胜球队j，L表示球队i负于球队j*，D表示两队打平，-表示无效（当i=j时）。输入中无多余空格。

输出格式：

按题目要求找到“食物链”T1 T2 ⋯ T**N，将这N个数依次输出在一行上，数字间以1个空格分隔，行的首尾不得有多余空格。若不存在“食物链”，输出“No Solution”。

1、剪枝优化：当剩余的所有球队都未战胜过第一支球队时，无需继续搜索。

2、注意题意：

$L$表示球队$i$负于球队$j$，即：球队$j$战胜球队$i$

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=110; int n,flag; int vis[maxn],win[maxn][maxn]; vector<int>ans; void dfs(int x){if(flag) return;int f=0;for(int i=1;i<=n;i++){ //剪枝操作if(!vis[i]&&win[i][ans[0]]){f=1;break;}}if(!f) return;for(int i=1;i<=n;i++){if(!vis[i]&&win[x][i]){vis[i]=1;ans.push_back(i);if(ans.size()==n){if(win[i][ans[0]]){ //找到的第一个答案就是字典序最小的答案。flag=1;return;}}dfs(i);if(flag) return;//已经找到答案，直接returnvis[i]=0;ans.pop_back();}} } int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){char ch;cin>>ch;if(ch=='W') win[i][j]=1;else if(ch=='L') win[j][i]=1;}}for(int i=1;i<=n;i++){ //vis无需每次清空，未找到答案，回溯到i时，之前被标记过的已经又全部被归0了ans.push_back(i);flag=0;vis[i]=1;dfs(i);ans.pop_back();vis[i]=0;if(flag){for(int j=0;j<n;j++){if(j==0) cout<<ans[j];else cout<<" "<<ans[j];}cout<<endl;break;}}if(!flag) cout<<"No Solution\n";return 0; }

BFS

L3-004 肿瘤诊断 (30 分)

三维BFS求连通块的面积（连通数目）

注意审题！！！

六个方向搜索

#include<bits/stdc++.h> using namespace std; const int maxn=2e3+10; const int INF=0x3f3f3f3f; typedef long long ll; const int mod=1e9+7; int m,n,l,t; int num,flag; int a[100][maxn][200]; int vis[100][maxn][200]; int dir[][6]={{0,-1,0},{0,0,1},{0,1,0},{0,0,-1},{1,0,0},{-1,0,0}}; struct node{int x,y,z; }; int bfs(int x,int y,int z){queue<node>q;q.push({x,y,z});int num=1;while(!q.empty()){node p=q.front();q.pop();for(int i=0;i<6;i++){int dx=p.x+dir[i][0];int dy=p.y+dir[i][1];int dz=p.z+dir[i][2];if(dx>=l||dx<0||dy>=m||dy<0||dz>=n||dz<0) continue;if(a[dx][dy][dz]==0||vis[dx][dy][dz]) continue;vis[dx][dy][dz]=1;num++;q.push({dx,dy,dz});}}return num; } int main(){cin>>m>>n>>l>>t;int ans=0;for(int i=0;i<l;i++){for(int j=0;j<m;j++){for(int k=0;k<n;k++){cin>>a[i][j][k];}}}for(int i=0;i<l;i++){for(int j=0;j<m;j++){for(int k=0;k<n;k++){if(vis[i][j][k]==0&&a[i][j][k]==1){vis[i][j][k]=1;int num=bfs(i,j,k);// cout<<num<<endl;if(num>=t) ans+=num;}}}}cout<<ans<<endl;return 0; }

L3-008 喊山 (30 分)

第一想法DFS，但有两个测试点一直过不去

参考题解，重新读题，发现该题其实是分层的

如：

山头1和山头2临近

山头1和山头3临近

山头2和山头3临近

其实对于山头1来说，山头2和山头3的地位是一样的（属于同一层次），都是山头1可以直接呼叫到的。

这里并不存在两山头间距离远近的问题，dfs不适用

应该使用BFS，将各山头“分层”

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; typedef long long ll; const int mod=1e9+7; int n,m,k,q; vector<int>v[maxn]; int vis[maxn],lev[maxn]; int mmax; int ans; void bfs(int x){lev[x]=1;vis[x]=1;queue<int>q;q.push(x);while(!q.empty()){int y=q.front();q.pop();for(int i=0;i<v[y].size();i++){int z=v[y][i];if(vis[z]) continue;vis[z]=1;q.push(z);lev[z]=lev[y]+1;if(mmax<lev[z]){mmax=lev[z];ans=z;}else if(mmax==lev[z]){ans=min(ans,z);}}} } int main(){cin>>n>>m>>k;for(int i=0;i<m;i++){int x,y;cin>>x>>y;v[x].push_back(y);v[y].push_back(x); }for(int i=0;i<k;i++){cin>>q;ans=0;if(v[q].size()>0){memset(vis,0,sizeof(vis));mmax=0;ans=INF;vis[q]=1;bfs(q);}cout<<ans<<endl;}return 0; }

L3-018 森森美图 (30 分)

6 6
9 0 1 9 9 9
9 9 1 2 2 9
9 9 2 0 2 9
9 9 1 1 2 9
9 9 3 3 1 1
9 9 9 9 9 9
2 1 5 4

选择图像上的两个像素点A和B，则连接这两个点的直线就将图像分为两部分

• 图像的左上角是坐标原点(0,0)，我们假设所有像素按矩阵格式排列，其坐标均为非负整数（即横轴向右为正，纵轴向下为正）。横轴为x,纵轴为y
• 忽略正好位于连接A和B的直线（注意不是线段）上的像素点，即不认为这部分像素点在任何一个划分部分上，因此曲线也不能经过这部分像素点。
• 曲线是八连通的（即任一像素点可与其周围的8个像素连通），但为了计算准确，某像素连接对角相邻的斜向像素时，得分额外增加两个像素分数和的2倍减一。例如样例中，经过坐标为(3,1)和(4,2)的两个像素点的曲线，其得分应该是这两个像素点的分数和(2+2)，再加上额外的(2+2)乘以(2−1)，即约为5.66。

题目种的曲线指的是从起点（像素点A到像素点B的曲线），这样的曲线一共有两条，直线AB的上方一条，直线AB的下方也有一条。曲线上的点，可由现在所在的点向八个方向扩散，只要最终能连接AB即可。但最终曲线上的所有点的分数和应该最小（最短路）。

利用叉乘判断点在直线的哪一边

#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; const int INF=0x3f3f3f3f; typedef long long ll; const int mod=1e9+7; int a[110][110]; double dis[110][110]; int n,m; int tag;//0:上半部分，1:下半部分 int dir[][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}}; struct Point{int x,y;bool operator !=(const Point &c) const{//creturn x!=c.x||y!=c.y;} }A,B; int cross(Point a,Point b,Point p){//叉乘，判断点在直线的哪一边，等于0则在直线上return (b.x-a.x)*(p.y-a.y)-(p.x-a.x)*(b.y-a.y); } void bfs(){memset(dis,0x7f,sizeof(dis));//double不能直接memset成0x3fqueue<Point>q;while(!q.empty()) q.pop();q.push(A);dis[A.x][A.y]=a[A.x][A.y];while(!q.empty()){Point p=q.front();q.pop();for(int i=0;i<8;i++){int dx=p.x+dir[i][0];int dy=p.y+dir[i][1];Point next={dx,dy};if(dx<1||dx>n||dy<1||dy>m) continue;int f=cross(A,B,{dx,dy});//包含起点和终点if(tag==0&&next!=A&&next!=B&&cross(A,B,next)<=0) continue;else if(tag&&next!=A&&next!=B&&cross(A,B,next)>=0) continue;double num;if(i<4) num=a[dx][dy]+dis[p.x][p.y];//上下左右方向else num=(a[dx][dy]+dis[p.x][p.y])+(a[dx][dy]+a[p.x][p.y])*(sqrt(2)-1);//斜方向if(dis[dx][dy]<=num) continue;dis[dx][dy]=num;if(dx==B.x&&dy==B.y){//已经达到终点，无需再将其入队，否则陷入死循环continue;}q.push(next);}} } int main(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}cin>>A.y>>A.x>>B.y>>B.x;//注意坐标输入顺序A.y++,A.x++,B.y++,B.x++;double ans=0;tag=0;bfs();ans+=dis[B.x][B.y];//上半部分tag=1;bfs();ans+=dis[B.x][B.y];//下半部分printf("%.2lf\n",ans-a[A.x][A.y]-a[B.x][B.y]);//起点和终点算了两次，需要减去return 0; }

链表

L2-022 重排链表 (25 分)

坑点：输入数据中可能会出现多余的无关结点（不在此链表上的结点、出现多个next为-1的结点）

最终链表结点个数，不一定就是题目所给的输入$n$

#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; const int mod=1000000007; const int INF=0x3f3f3f3f; typedef long long ll; struct node{int add;int data;int next; }p[maxn]; vector<int>pre,las; int main(){int head,n;scanf("%d%d",&head,&n);for(int i=0;i<n;i++){int ad,x,nex;scanf("%d%d%d",&ad,&x,&nex);p[ad].add=ad;p[ad].data=x;p[ad].next=nex;}int q=head;int m=0;//链表实际结点个数while(p[q].next!=-1){m++;q=p[q].next;}q=head;int cnt=1;while(p[q].next!=-1){if(cnt<=m/2) las.push_back(p[q].add);else pre.push_back(p[q].add);cnt++;q=p[q].next;}pre.push_back(p[q].add);int l1=pre.size();int l2=las.size();int i=l1-1,j=0;while(i>=0&&j<l2){//cout<<"i: "<<i<<" j: "<<j<<endl;printf("%05d %d %05d\n",pre[i],p[pre[i]].data,las[j]);if(i==0) printf("%05d %d -1\n",las[j],p[las[j]].data);else printf("%05d %d %05d\n",las[j],p[las[j]].data,pre[i-1]);i--;j++;}if(i>=0) printf("%05d %d -1\n",pre[i],p[pre[i]].data);return 0; }

数据结构

线段树

L3-017 森森快递 (30 分)

一条直线上的$N$个城市，这些城市从左到右依次从0到$(N-1)$编号；第$i$号城市（$i=0,\cdots ,N-2$）与第$(i+1)$号城市中间往返的运输货物重量在同一时刻不能超过$C_i$公斤。

现有$Q$张订单，第$j$张订单描述了某些指定的货物要从$S_j$号城市运输到$T_j$号城市。所有货物都有无限货源，不定时的挑选一定的货物进行运输，且中途不能卸货。

如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制，求出运输货物重量的最大值。

即：若选择订单$j$，则运输的货物不能超过从$S_j$到$T_j$途径所有道路上运输限制的最小值

线段树维护区间最小值

由于运输货物的时间不定，任意时间都可以运输，所以可能出现某一条道路同时运输多个订单货物的情况。

如上图所示，如果在某一时刻选择从1到4运输重量为1的货物，则此时要选择从1到3运输货物，运输的货物重量也只能是1

也就是说每选取一个区间，就要将其所有子区间（途径的所有道路运输货物的重量）的值减去该区间的最小值（即修改区间最小值）。

而这就涉及到了区间修改的顺序问题，由于我们想让最终运输的货物重量尽可能地大，所以每次选择了一个区间之后，应该对尽可能少地区间产生影响。

区间顺序选择：

当区间左端点相同，我们应优先选择右端点小的区间（绿色的区间），不会对$[R_1,R_2]$中的值产生影响。

>
当区间右端点相同，我们应优先选择左端点大的区间（绿色的区间），不会对$[L_1,L_2]$中的值产生影响

注意求最小值时的初值：1ll<<60

赋成0x3f3f3f3f最后一个测试点过不了！

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; const ll INF=1ll<<60; struct node{int l,r; }p[maxn]; bool cmp(node a,node b){//区间排序if(a.r==b.r) return a.l>b.l;return a.r<b.r; } struct Tree{int l,r;ll mix;ll lazy; }tr[maxn<<2]; void push_up(int root){tr[root].mix=min(tr[root<<1].mix,tr[root<<1|1].mix); } void bt(int root,int l,int r){tr[root].l=l;tr[root].r=r;tr[root].lazy=0;if(l==r){cin>>tr[root].mix;return;}int mid=(l+r)>>1;bt(root<<1,l,mid);bt(root<<1|1,mid+1,r);push_up(root); } void push_down(int root){if(tr[root].lazy){tr[root<<1].lazy+=tr[root].lazy;tr[root<<1].mix+=tr[root].lazy;tr[root<<1|1].lazy+=tr[root].lazy;tr[root<<1|1].mix+=tr[root].lazy;tr[root].lazy=0;} } void update(int root,int l,int r,int val){if(tr[root].l>r||tr[root].r<l) return;if(tr[root].l>=l&&tr[root].r<=r){tr[root].mix+=val;tr[root].lazy+=val; return;}push_down(root);int mid=(tr[root].l+tr[root].r)>>1;update(root<<1,l,r,val);update(root<<1|1,l,r,val);push_up(root); } ll query(int root,int l,ll r){if(tr[root].l>r||tr[root].r<l) return INF;if(tr[root].l>=l&&tr[root].r<=r){return tr[root].mix;}push_down(root);ll ans;int mid=(tr[root].l+tr[root].r)>>1;ans=min(query(root<<1,l,r),query(root<<1|1,l,r));return ans; } int main(){int n,q;cin>>n>>q;bt(1,1,n-1);for(int i=0;i<q;i++){int x,y;cin>>x>>y;if(x>y) swap(x,y);p[i].l=x;p[i].r=y;}sort(p,p+q,cmp);ll ans=0;for(int i=0;i<q;i++){int l=p[i].l;int r=p[i].r;ll num=query(1,l+1,r);//区间查询ans+=num;if(num>0) update(1,l+1,r,-num);//区间修改}cout<<ans<<endl;return 0; }

树

1、按照题目所给定义建树：左子树键值大，右子树键值小

一边建树，一边维护层序

2、判断是否是完全二叉树

只需看层序遍历每个结点的序号是否满足从1到n，只要漏掉一个，都不是完全二叉树。

L3-010 是否完全二叉搜索树 (30 分)

#include<bits/stdc++.h> using namespace std; const int maxn=1e3+10; int a[maxn],vis[maxn]; map<int,int>lev; void bt(int root,int val){//建树if(val>lev[root]){ //将当前值插入适应结点int left=root<<1;while(1){if(lev[left]==0) {lev[left]=val;break;}if(val>lev[left]) left<<=1;else if(val<lev[left]) left=left<<1|1;}}else if(val<lev[root]){int right=root<<1|1;while(1){if(lev[right]==0){lev[right]=val;break;}if(val>lev[right]) right<<=1;else if(val<lev[right]) right=right<<1|1;}} } int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}lev[1]=a[1];for(int i=2;i<=n;i++){bt(1,a[i]);}vector<int>idx;map<int,int>::iterator it=lev.begin();vis[it->first]=1;cout<<it->second;it++;for(;it!=lev.end();it++){vis[it->first]=1;cout<<" "<<it->second;}cout<<endl;int flag=0;for(int i=1;i<=n;i++){if(!vis[i]){flag=1;break;}}if(!flag) cout<<"YES\n";else cout<<"NO\n";return 0; }

L3-016 二叉搜索树的结构 (30 分)

map中是否出现过key：

mp.count(key);

若存在，返回1，否则，返回0；

虽然说，map用[ ]访问不存在的key，value返回的是默认值（int为0，string为空串）

但是不知道为什么这道题，不能直接用mp[key]==0，来判，把这个改成count就对了。

#include<bits/stdc++.h> using namespace std; const int maxn=1e3+10; int a[maxn]; map<int,int>lev,mp; void bt(int root,int val){//建树if(lev.count(root)==0){//遇到空结点，则赋值lev[root]=val;mp[val]=root;return;}if(val<lev[root]) bt(root<<1,val); else if(val>lev[root]) bt(root<<1|1,val); } int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];bt(1,a[i]);}int m;cin>>m;while(m--){int x,y;string a;cin>>x>>a; if(a=="is"){cin>>a>>a;if(a=="root"){if(mp[x]==1) cout<<"Yes\n";else cout<<"No\n";}else if(a=="parent"){cin>>a>>y;if(mp.count(x)==0||mp.count(y)==0) cout<<"No\n";else if(mp[y]/2==mp[x]) cout<<"Yes\n";else cout<<"No\n";}else if(a=="left"){cin>>a>>a>>y;if(mp.count(x)==0||mp.count(y)==0) cout<<"No\n";else if(mp[y]*2==mp[x]) cout<<"Yes\n";else cout<<"No\n";}else if(a=="right"){cin>>a>>a>>y;if(mp.count(x)==0||mp.count(y)==0) cout<<"No\n";else if(mp[y]*2+1==mp[x]) cout<<"Yes\n";else cout<<"No\n";} }else if(a=="and"){cin>>y>>a>>a;if(a=="siblings"){if(mp.count(x)==0||mp.count(y)==0) cout<<"No\n";else if(abs(mp[x]-mp[y])==1) cout<<"Yes\n";else cout<<"No\n";}else if(a=="on"){cin>>a>>a>>a;if(mp.count(x)==0||mp.count(y)==0) cout<<"No\n";else{int c=mp[x],d=mp[y];while(c!=0&&d!=0) c/=2,d/=2;if(c==0&&d==0)cout<<"Yes\n";else cout<<"No\n";} }}}return 0; }

堆的建立

L2-012 关于堆的判断 (25 分) 小顶堆

对输入字符串的巧妙处理–>输入格式已知

向上调整建堆

#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; const int INF=0x3f3f3f3f; typedef long long ll; map<int,int>mp; int h[maxn]; int cnt; void up(int x){h[++cnt]=x;int t=cnt;while(t>1&&h[t/2]>h[t]){swap(h[t/2],h[t]);t/=2;//t>>=1}ans[t]=x; } int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){int x;cin>>x;up(x);}for(int i=1;i<=n;i++){mp[h[i]]=i;}getchar();for(int i=0;i<m;i++){int x,y;string s;cin>>x>>s;if(s=="and"){cin>>y>>s>>s;if(mp[x]/2==mp[y]/2) puts("T");else puts("F");}else if(s=="is"){cin>>s>>s;if(s=="root"){if(mp[x]==1) puts("T");else puts("F");}else if(s=="parent"){cin>>s>>y;if(mp[y]/2==mp[x]) puts("T");else puts("F");}else if(s=="child"){cin>>s>>y;if(mp[x]/2==mp[y]) puts("T");else puts("F");}} }return 0; }

堆的基本操作

push_heap( )函数

make_heap( ):生成一个堆，大顶堆或小顶堆

push_heap( ): 向堆中插入一个元素，并且使堆的规则依然成立

[点击参考此文章](make_heap()等函数的用法 - 阳离子 - 博客园 (cnblogs.com))

#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; const int INF=0x3f3f3f3f; typedef long long ll; map<int,int>mp; int h[maxn]; int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>h[i];push_heap(h + 1, h + 1 + i, greater<int>());}for(int i=1;i<=n;i++){mp[h[i]]=i;}getchar();for(int i=0;i<m;i++){int x,y;string s;cin>>x>>s;if(s=="and"){cin>>y>>s>>s;if(mp[x]/2==mp[y]/2) puts("T");else puts("F");}else if(s=="is"){cin>>s>>s;if(s=="root"){if(mp[x]==1) puts("T");else puts("F");}else if(s=="parent"){cin>>s>>y;if(mp[y]/2==mp[x]) puts("T");else puts("F");}else if(s=="child"){cin>>s>>y;if(mp[x]/2==mp[y]) puts("T");else puts("F");}} }return 0; }

并查集

L3-003 社交集群 (30 分)

具有同一兴趣爱好的人归为一类，最终可归为几类，每类各有多少人。

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; typedef long long ll; const int mod=1e9+7; vector<int>p[maxn]; int fa[maxn]; int num[maxn]; set<int>h; int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]); } bool cmp(int a,int b){return a>b; } int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){int k;scanf("%d:",&k);for(int j=0;j<k;j++){int x;scanf("%d",&x);h.insert(x);//记录所有兴趣爱好（去重）p[x].push_back(i);//具有这一兴趣爱好的人有哪些}}for(int i=1;i<=n;i++){fa[i]=i;num[i]=1;}set<int>::iterator it=h.begin();for(;it!=h.end();it++){int i=*it;int x=p[i][0];//将具有同一兴趣爱好的人加入同一集合中for(int j=1;j<p[i].size();j++){int y=p[i][j];int fx=find(x);int fy=find(y);if(fx!=fy){fa[fx]=fy;num[fy]+=num[fx];}x=y; }}vector<int>ans;for(int i=1;i<=n;i++){if(find(i)==i){//记录每个jans.push_back(num[i]);}}cout<<ans.size()<<endl;sort(ans.begin(),ans.end(),cmp);for(int i=0;i<ans.size();i++){if(i==0) cout<<ans[i];else cout<<" "<<ans[i];}return 0; }

图

L2-013 红色警报 (25 分)—连通块个数

DFS做法

被攻占的城市，不会再参与后续dfs找连通块中，所以不能只用一个vis来标记（vis每一次都会被全部清空），需要再借助另外一个标记！

#include<bits/stdc++.h> using namespace std; const int maxn=1e3+10; typedef long long ll; vector<int>v[maxn]; int vis[maxn];//每次dfs时，标记是否已被访问过 int lost[maxn];//标记某城市是否已被攻占 int n,m; vector<int>ans; void dfs(int x){vis[x]=1;if(x>=n) return;for(int i=0;i<v[x].size();i++){if(vis[v[x][i]]==0&&(lost[v[x][i]]==0)) dfs(v[x][i]);} } int main() {cin>>n>>m;while(m--){int a,b;cin>>a>>b;v[a].push_back(b);v[b].push_back(a);}int cnt=0;//计算连通块个数for(int i=0;i<n;i++){if(!vis[i]){dfs(i);cnt++;}}int k;cin>>k;for(int i=0;i<k;i++){int x;cin>>x;lost[x]=1;memset(vis,0,sizeof(vis));vis[x]=1;int num=0;for(int i=0;i<n;i++){if(!lost[i]&&(!vis[i])){dfs(i);num++;}}//cout<<"num: "<<num<<" cnt: "<<cnt<<endl;if(num>cnt) printf("Red Alert: City %d is lost!\n",x);else{printf("City %d is lost.\n",x);} cnt=num;if(i==n-1){cout<<"Game Over.\n";}}return 0; }

并查集做法

#include<bits/stdc++.h> using namespace std; const int maxn=1e3+10; typedef long long ll; int n,m; int fa[maxn]; int lost[maxn]; vector<pair<int,int> >road; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]); } int count(){for(int i=0;i<n;i++) fa[i]=i;for(int i=0;i<road.size();i++){int x=road[i].first;int y=road[i].second;if(!lost[x]&&(!lost[y])){int fx=find(x);int fy=find(y);fa[fx]=fy;}}int ans=0;for(int i=0;i<n;i++){if(find(i)==i) ans++;}return ans; } int main() {cin>>n>>m;for(int i=0;i<n;i++){fa[i]=i;}for(int i=0;i<m;i++){int x,y;cin>>x>>y;road.push_back({x,y});}int cnt=count();int k;cin>>k;for(int i=0;i<k;i++){int x;cin>>x;lost[x]=1;int num=count();//cout<<"num: "<<num<<" cnt: "<<cnt<<endl;//算连通块时，会把被攻占的那个城市也算上，所以num要减一 if(num-1>cnt) printf("Red Alert: City %d is lost!\n",x);else printf("City %d is lost.\n",x);cnt=num;if(i==n-1) puts("Game Over.");}return 0; }

最短路问题

L2-001 紧急救援 (25 分) 单源最短路

Dij做法

#include<bits/stdc++.h> using namespace std; const int maxn=1e3+10; const int INF=0x3f3f3f3f; typedef long long ll; int n,m,s,d; int c[maxn];//cure int e[maxn][maxn];//edge int dis[maxn];//shortest int vis[maxn];//visited int cis[maxn];//max_num int num[maxn];//the number of the shortest path vector<int>pre[maxn];//path vector<int>ans; void dfs(int x){ans.push_back(x);for(int i=0;i<pre[x].size();i++){dfs(pre[x][i]);} } void dij(){for(int i=0;i<n;i++){dis[i]=w[s][i];}cis[s]=c[s];num[s]=1;for(int i=0;i<n;i++){int mmin=INF,u=-1;for(int j=0;j<n;j++){if(!vis[j]&&dis[j]<mmin){mmin=dis[j];u=j;}}if(u==-1) break;vis[u]=1;for(int j=0;j<n;j++){if(!vis[j]&&dis[u]+e[u][j]<dis[j]){dis[j]=dis[u]+e[u][j];cis[j]=cis[u]+c[j];num[j]=num[u];pre[j].clear();pre[j].push_back(u);}else if(!vis[j]&&dis[u]+e[u][j]==dis[j]){num[j]+=num[u];if(cis[u]+c[j]>cis[j]){cis[j]=cis[u]+c[j];pre[j].clear();pre[j].push_back(u);}}}}cout<<num[d]<<" "<<cis[d]<<endl<<s;dfs(d);for(int i=ans.size()-2;i>=0;i--){cout<<" "<<ans[i];}} int main(){cin>>n>>m>>s>>d;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==j) e[i][j]=0;else e[i][j]=INF;}}for(int i=0;i<n;i++){cin>>c[i];}for(int i=0;i<m;i++){int u,v,h;cin>>u>>v>>h;if(h<e[u][v]){e[u][v]=e[v][u]=h;}}dij();return 0; }

优先队列优化dij做法

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; typedef long long ll; typedef pair<int,int> P; struct edge{int to,w; }; vector<edge>e[maxn]; int c[maxn]; int dis[maxn]; int cis[maxn]; int vis[maxn]; int num[maxn]; vector<int>pre[maxn],ans; int n,m,s,d; void dfs(int x){ans.push_back(x);for(int i=0;i<pre[x].size();i++){dfs(pre[x][i]);} } void dij(){priority_queue<P,vector<P>,greater<P> >q;memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));dis[s]=0;num[s]=1;cis[s]=c[s];q.push(P(0,s));while(!q.empty()){P a=q.top();q.pop();int u=a.second;if(vis[u]) continue;vis[u]=1;for(int i=0;i<e[u].size();i++){edge x=e[u][i];if(!vis[x.to]&&dis[x.to]>dis[u]+x.w){dis[x.to]=dis[u]+x.w;cis[x.to]=cis[u]+c[x.to];num[x.to]=num[u];q.push(P(dis[x.to],x.to));pre[x.to].clear();pre[x.to].push_back(u);}else if(!vis[x.to]&&dis[x.to]==dis[u]+x.w){num[x.to]+=num[u];if(cis[x.to]<cis[u]+c[x.to]){cis[x.to]=cis[u]+c[x.to];// q.push(P(dis[x.to],x.to));pre[x.to].clear();pre[x.to].push_back(u);}} }}cout<<num[d]<<" "<<cis[d]<<endl;cout<<s;dfs(d);for(int i=ans.size()-2;i>=0;i--){cout<<" "<<ans[i];}cout<<endl;} int main(){cin>>n>>m>>s>>d;for(int i=0;i<n;i++){cin>>c[i];}for(int i=0;i<m;i++){int u,v,h;cin>>u>>v>>h;//无向边！！！e[u].push_back({v,h});e[v].push_back({u,h});}dij();return 0; }

L3-005 垃圾箱分布 (30 分)

审清题意！！！

注意最值的初始化！！！

所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，同时还要保证每个居民点都在距离它一个不太远的范围内(距离不大于D）。

如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。

因为垃圾箱最多只有十个，所以从每个垃圾箱出发，做dij

#include<bits/stdc++.h> using namespace std; const int maxn=1e4+10; #define INF 0x3f3f3f3f typedef pair<int,int> P; int dis[maxn]; int e[maxn][maxn]; int vis[maxn]; int n,m,K,D,s; map<int,string>mp; int ans,des,ans_sum; void dij(){priority_queue<P,vector<P>,greater<P> >q; memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));dis[s]=0;q.push(P(0,s));while(!q.empty()){P a=q.top();q.pop();int u=a.second;if(vis[u]) continue;vis[u]=1;for(int i=1;i<=n+m;i++){if(!vis[i]&&dis[i]>dis[u]+e[u][i]){dis[i]=dis[u]+e[u][i];q.push(P(dis[i],i));}} }int mmin=INF;int flag=1;int sum=0;for(int i=1;i<=n;i++){if(dis[i]==INF||dis[i]>D){flag=0;break;}sum+=dis[i];mmin=min(mmin,dis[i]);}if(flag){if(ans<mmin){ans=mmin;des=s;}if(ans==mmin){//最短距离最长的位置不唯一，则选平均距离最小的if(ans_sum>sum){des=s;ans_sum=sum;}else if(ans_sum==sum&&des>s){//平均距离最小的不唯一，则选序号小的des=s;}}}} int main() {cin>>n>>m>>K>>D;des=n+m+1;ans_sum=INF;for(int i=1;i<=n+m;i++){for(int j=1;j<=n+m;j++){if(i==j) e[i][j]=0;else e[i][j]=INF;}}while(K--){string a,b;int u,v,w;cin>>a>>b>>w;if(a[0]=='G'){u=n+a[1]-'0';mp[u]=a;}else u=stoi(a);if(b[0]=='G'){v=n+b[1]-'0';mp[v]=b;}else v=stoi(b);if(w<e[u][v]){e[u][v]=w;e[v][u]=w;}}for(int i=1;i<=m;i++){s=n+i;dij();} if(des==n+m+1){puts("No Solution");return 0;}cout<<mp[des]<<endl;s=des;dij();int sum=0;for(int i=1;i<=n;i++){sum+=dis[i];}printf("%.1lf %.1lf\n",1.0*ans,round(1.0*sum/n*10)/10);return 0; }

L3-007 天梯地图 (30 分)

分别针对最短时间和最短距离进行dij

注意输出：

首先按下列格式输出最快到达的时间T和用节点编号表示的路线：

Time = T: 起点 => 节点1 => ... => 终点

然后在下一行按下列格式输出最短距离D和用节点编号表示的路线：

Distance = D: 起点 => 节点1 => ... => 终点

如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。

而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的。

如果这两条路线是完全一样的，则按下列格式输出：

Time = T; Distance = D: 起点 => 节点1 => ... => 终点

在求最快到达路线时，不能直接用之前求得的最短路来更新路径，因为最短路是按途径节点数最少来寻找最优解的，而求最快到达路线时的最短的那条并不一定是节点数最少的那条

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; typedef long long ll; const int mod=1e9+7; typedef pair<int,int>P; int n,m,s,t; int dis[maxn]; int tis[maxn]; int vis[maxn]; int num[maxn]; struct edge{int to;int time;int len; }; vector<edge>e[maxn]; vector<int>pre[maxn],tre[maxn],ans1,ans2; map<vector<int>,int>mp; void dfs1(int x){ans1.push_back(x);for(int i=0;i<tre[x].size();i++){dfs1(tre[x][i]);} } void dfs2(int x){ans2.push_back(x);for(int i=0;i<pre[x].size();i++){dfs2(pre[x][i]);} } void dij(){priority_queue<P,vector<P>,greater<P> >p,q;memset(dis,0x3f,sizeof(dis));memset(tis,0x3f,sizeof(tis));dis[s]=0;p.push(P(0,s));num[s]=1;while(!p.empty()){P a=p.top();p.pop();int u=a.second;if(vis[u]) continue;vis[u]=1;for(int i=0;i<e[u].size();i++){edge x=e[u][i];if(!vis[x.to]&&dis[x.to]>dis[u]+x.len){dis[x.to]=dis[u]+x.len;num[x.to]=num[u]+1;p.push(P(dis[x.to],x.to));pre[x.to].clear();pre[x.to].push_back(u);}if(!vis[x.to]&&dis[x.to]==dis[u]+x.len){if(num[x.to]>num[u]+1){//选择节点数少的那条路pre[x.to].clear();pre[x.to].push_back(u);}} }}memset(vis,0,sizeof(vis));int d[550];tis[s]=0;q.push(P(0,s));while(!q.empty()){P a=q.top();q.pop();int u=a.second;if(vis[u]) continue;vis[u]=1;for(int i=0;i<e[u].size();i++){edge x=e[u][i];if(!vis[x.to]&&tis[x.to]>tis[u]+x.time){tis[x.to]=tis[u]+x.time;d[x.to]=d[u]+x.len;q.push(P(tis[x.to],x.to));tre[x.to].clear();tre[x.to].push_back(u);}else if(!vis[x.to]&&tis[x.to]==tis[u]+x.time){if(d[x.to]>d[u]+x.len){//选择距离短的那条路（不能直接用前面的dis[]）d[x.to]=d[u]+x.len;tre[x.to].clear();tre[x.to].push_back(u);}}}}dfs1(t);mp[ans1]=1;dfs2(t);if(mp[ans2]){//判断路径是否完全一样cout<<"Time = "<<tis[t];cout<<"; ";}else{cout<<"Time = "<<tis[t]<<": "<<s;for(int i=ans1.size()-2;i>=0;i--){cout<<" => "<<ans1[i];}cout<<endl; }cout<<"Distance = "<<dis[t]<<": "<<s;for(int i=ans2.size()-2;i>=0;i--){cout<<" => "<<ans2[i];} } int main(){cin>>n>>m;for(int i=0;i<m;i++){int u,v,o,l,tt;cin>>u>>v>>o>>l>>tt;if(o){e[u].push_back({v,tt,l});}else{e[u].push_back({v,tt,l});e[v].push_back({u,tt,l});}}cin>>s>>t;dij();return 0; }

L3-011 直捣黄龙 (30 分)

选择合适的路径，以最快的速度占领敌方大本营。（最短路）

当这样的路径不唯一时，要求选择可以沿途解放最多城镇的路径。（经过节点最多）

若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径。（杀伤敌军最多）

注意路径不唯一时，条件的判断以及其他量的更新！！！

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; typedef long long ll; typedef pair<int,int> P; const int mod=1e9+7; map<string,int>mp; map<int,string>pm; int n,k,des; string s,t; int dis[maxn]; int vis[maxn]; int c[maxn]; int cis[maxn],num[maxn],sum[maxn]; struct node{int to;int w; }; vector<node>v[maxn]; vector<int>pre[maxn],ans; void dfs(int x){//输出路径ans.push_back(x);for(int i=0;i<pre[x].size();i++){dfs(pre[x][i]);} } void dij(){priority_queue<P,vector<P>,greater<P> >q;memset(dis,INF,sizeof(dis));dis[0]=0;q.push(P(0,0));cis[0]=0;num[0]=1;sum[0]=0;while(!q.empty()){P a=q.top();q.pop();int u=a.second;if(vis[u]) continue;vis[u]=1;for(int i=0;i<v[u].size();i++){node x=v[u][i];if(dis[x.to]>dis[u]+x.w){//最短路dis[x.to]=dis[u]+x.w;cis[x.to]=cis[u]+c[x.to];num[x.to]=num[u];sum[x.to]=sum[u]+1;pre[x.to].clear();pre[x.to].push_back(u);q.push(P(dis[x.to],x.to));}else if(dis[x.to]==dis[u]+x.w){num[x.to]+=num[u];//更新最多路的数量if(sum[x.to]<sum[u]+1){//经过节点数最多sum[x.to]=sum[u]+1;cis[x.to]=cis[u]+c[x.to];//不要忘记更新其他量pre[x.to].clear();pre[x.to].push_back(u); }else if(sum[x.to]==sum[u]+1&&cis[x.to]<cis[u]+c[x.to]){//杀伤敌军最多cis[x.to]=cis[u]+c[x.to];pre[x.to].clear();pre[x.to].push_back(u);}} }}dfs(des);cout<<s;for(int i=ans.size()-2;i>=0;i--){cout<<"->"<<pm[ans[i]];}cout<<endl;cout<<num[des]<<" "<<dis[des]<<" "<<cis[des]<<endl; } int main(){cin>>n>>k>>s>>t;mp[s]=0;int cnt=1;for(int i=1;i<n;i++){string name;int x;cin>>name>>x;if(!mp[name]){mp[name]=cnt++;}pm[mp[name]]=name;c[mp[name]]=x;}for(int i=0;i<k;i++){string a,b;int w;cin>>a>>b>>w;v[mp[a]].push_back({mp[b],w});v[mp[b]].push_back({mp[a],w});}des=mp[t];dij();return 0; }

计算几何

L3-021 神坛 (30 分)

从n个点中任选3个点，求其所形成的三角形面积的最小值。

1、利用叉乘计算三角形面积：$S=\frac{1}{2}|AB\times AC|$

2、级角排序

枚举点，该点可与其他所有点连边（形成向量），然后对所有向量按级角进行排序（顺时针或逆时针排序）；排好序之后，只有相邻的两个向量形成的三角形面积才可能是最小的。

参考：级角排序的方法：

1、利用atan2（）函数按极角从小到大排序

bool cmp1(point a,point b) {if(atan2(a.y,a.x)!=atan2(b.y,b.x))return atan2(a.y,a.x)<atan2(b.y,b.x);else return a.x<b.x; }

2、利用叉积按极角从小到大排序

bool cmp2(point a,point b) {point c;//原点c.x = 0;c.y = 0;if(compare(c,a,b)==0)//计算叉积，如果叉积相等，按照X从小到大排序return a.x<b.x;else return compare(c,a,b)>0; }

3、先按象限从小到大排序 再按极角从小到大排序

int Quadrant(point a)　　//象限排序，注意包含四个坐标轴 {if(a.x>0&&a.y>=0) return 1;if(a.x<=0&&a.y>0) return 2;if(a.x<0&&a.y<=0) return 3;if(a.x>=0&&a.y<0) return 4; } bool cmp3(point a,point b) //先按象限从小到大排序 再按极角从小到大排序 {if(Quadrant(a)==Quadrant(b))//返回值就是象限return cmp1(a,b);//return cmp2(a,b)else Quadrant(a)<Quadrant(b); }

注意要开long long

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=5e3+10; struct point{ll x,y; }p[maxn],q[maxn]; bool cmp(point a,point b){return a.x*b.y-a.y*b.x>0; } int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld%lld",&p[i].x,&p[i].y);}double mmin=1e18;for(int i=1;i<=n;i++){int cnt=0;for(int j=1;j<=n;j++){if(i==j) continue;q[cnt].x=p[j].x-p[i].x;q[cnt++].y=p[j].y-p[i].y;}sort(q,q+cnt,cmp);//级角排序for(int j=0;j<cnt;j++){double ans=0.5*abs(q[j].x*q[(j+1)%cnt].y-q[j].y*q[(j+1)%cnt].x);//计算相邻向量形成三角形的面积mmin=min(ans,mmin);}}printf("%.3lf\n",round(mmin*1000)/1000);return 0; }

其他

L3-013 非常弹的球 (30 分)

假设森森是一个质点，以森森为原点设立坐标轴，则森森位于(0, 0)点。

小球质量为w/100 千克（kg），重力加速度为9.8米/秒平方（m/s2）。

森森在地上用力弹球的过程可简化为球从(0, 0)点以某个森森选择的角度an**g (0<an**g<π/2) 向第一象限抛出，抛出时假设动能为1000 焦耳（J）。

小球在空中仅受重力作用，球纵坐标为0时可视作落地，落地时损失p%动能并反弹。

地面可视为刚体，忽略小球形状、空气阻力及摩擦阻力等。

求：最远的投掷距离，保留3位小数

被简单物理题难住。。。

求距离，那就需要知道速度和时间（s=vt)

假设以夹角$\alpha$抛出,初速度为$v_0$,将其沿水平和竖直两个方向分解。

竖直方向：

只受重力，做匀减速运动（加速度为$g$)，向上减速为0有：

$v_{0}sin\alpha =gt$,则$t=\frac{v_{0}sin\alpha }{g}$

从抛出到第一次落地的总时间即为$T=2t=\frac{2v_{0}sin\alpha }{g}$

水平方向：

$s=v_{0}Tcos\alpha =\frac{v_0^{2}sin2\alpha }{g}$

当$\alpha =\frac{\pi }{4}$时，s取最大值，$s=\frac{v_0^2}{g}=\frac{2E_k}{mg}$

#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; const int INF=0x3f3f3f3f; typedef long long ll; const int mod=1e9+7; int main(){double w,p;scanf("%lf%lf",&w,&p);w/=100;double s=0,Ek=1000,g=9.8;while(Ek>=1e-9){//zs+=2*Ek/(w*g);Ek-=p*Ek/100;} printf("%.3lf\n",s);return 0; }

L1-050 倒数第N个字符串 (15 分)

给定一个完全由小写英文字母组成的字符串等差递增序列，该序列中的每个字符串的长度固定为 L，从 L 个 a 开始，以 1 为步长递增。例如当 L 为 3 时，序列为 { aaa, aab, aac, …, aaz, aba, abb, …, abz, …, zzz }。这个序列的倒数第27个字符串就是 zyz。对于任意给定的 L，本题要求你给出对应序列倒数第 N 个字符串。

对于长度为$n$的字符串，可得到的序列共有$26^n$个字符串

类似于26进制，倒数第一个字母（幂次为0），每变换一次，字符串增加1个；倒数第二个字母（幂次为1），每变换一次，字符串增加26个；倒数第三个字母（幂次为2），每变换一次，字符串增加$26^2$个。

求倒数第$N$个字符串，即求第$26^L-N$个，将$26^L-N$转换成26进制，每一位输出对应的字母即可。

但是要注意求倒数第N个，即第0个的情况，或者是转换为26进制后，长度不足L，需补足前缀0

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; int ksm(int a,int b){int ans=1;while(b){if(b&1) ans=ans*a;a=a*a;b>>=1;}return ans; } vector<int>s; int main(){int l,n;cin>>l>>n;int res=ksm(26,l)-n;while(res){s.push_back(res%26);res/=26; }int len=s.size();for(int i=len;i<=l-len;i++) s.push_back(0);//补前缀0for(int i=l-1;i>=0;i--){char ch=s[i]+'a';cout<<ch;}cout<<endl;return 0; }

总结

以上是生活随笔为你收集整理的天梯赛赛前练习的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。