《7-1 懂的都懂》
这道题其他没什么，就是暴力
但是注意上面，我们算平均值的时候要用double
如果对double不放心（因为double其实有时候并不准确）
可以写成如下样子：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int N=52;
int n,m,arr[N];
map<int,bool>mp;
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>arr[i];
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++)
for (int k=j+1;k<=n;k++)
for (int l=k+1;l<=n;l++)
{
int ans=(arr[i]+arr[j]+arr[k]+arr[l]);
mp[ans]=true;
}
while (m--)
{
cin>>n;
int num;
bool flag=true;
for (int i=1;i<=n;i++)
{
cin>>num;
if (mp[num*4]!=true)
flag=false;
}
if (flag)
cout<<"Yes";
else cout<<"No";
if (m)
cout<<endl;
}
return 0;
}
《7-2 芬兰木棋》
这道题要考虑的细节比较多：
1.首先要考虑当斜率计算不出来（即x==0）的情况
2.还有考虑在每个斜率上点的排序
不同地方点的排序方法不一样
比如：
在X正轴上的点要按照x从小到大排序
但是在X负轴上的点要按照x从大到小排序
在Y正轴上x是一样的，这个时候要按照y从小到大排序
在Y负轴上......等
同样，为了避免double可能不太精确的问题，这里用
记录 y/x 中 记录 y与x的方式记录斜率
同时将坐标轴分成4个象限
对于每个象限上的每个斜率上的点用vector装好，排序
#include<iostream> #include<cstring> #include<algorithm> #include<map> #include<vector> #include<set> using namespace std; typedef pair<int,int> PII; struct node{ int x,y,p; }; bool rule1(struct node a,struct node b){ if (a.x==b.x) return a.y>b.y; else return a.x<b.x; } bool rule2(struct node a,struct node b){ if (a.x==b.x) return a.y<b.y; else return a.x>b.x; } map<PII,vector<node>>mp[5]; set<PII>st[5]; int n,ans=0,cnt=0; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } void input() { cin>>n; for (int i=1;i<=n;i++) { int x,y,p; cin>>x>>y>>p; ans+=p; int k=gcd(x,y); if (y>=0 && x>0) mp[1][{y/k,x/k}].push_back({x,y,p}), st[1].insert({y/k,x/k}); else if (y>0 && x<=0) mp[2][{y/k,x/k}].push_back({x,y,p}), st[2].insert({y/k,x/k}); else if (y<=0 && x<0) mp[3][{y/k,x/k}].push_back({x,y,p}), st[3].insert({y/k,x/k}); else if (y<0 && x>=0) mp[4][{y/k,x/k}].push_back({x,y,p}), st[4].insert({y/k,x/k}); } } int main() { input(); for (int i=1;i<=4;i++) { //枚举出第i象限的k来 for (auto j=st[i].begin();j!=st[i].end();j++) { PII k=*j; //通过k枚举这个象限上，斜率k上的点 if (i==1 || i==4) sort(mp[i][k].begin(),mp[i][k].end(),rule1); else sort(mp[i][k].begin(),mp[i][k].end(),rule2); int buf=0; for (int l=0;l<mp[i][k].size();l++) { node t=mp[i][k][l]; if (t.p==1) buf++; else { if (buf!=0) cnt++,buf=0; cnt++; } } if (buf!=0) cnt++,buf=0; } } cout<<ans<<" "<<cnt<<endl; return 0; }
《7-3 打怪升级》
我总感觉这句话没说清楚
总之这个点的求解方式是：
先Floyd，求出每个点相互之间的最小距离
然后枚举每个点i，找出其中到某个点j的最大距离maxwi
然后找出这些maxwi中最小的那个，其所对应的点i就是我们要找的点
然后这题的关键就是用一次Floyd解决：
1.记录最短路路径问题
2.解决双决策标准问题
void Floyd()
{
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
ansW[i][j]=gw[i][j];
ansV[i][j]=gv[i][j];
}
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
if (ansW[i][j]>ansW[i][k]+ansW[k][j])
{
ansW[i][j]=ansW[i][k]+ansW[k][j];
ansV[i][j]=ansV[i][k]+ansV[k][j];
path[i][j]=k;
}
else if (ansW[i][j]==ansW[i][k]+ansW[k][j])
{
if (ansV[i][j]<ansV[i][k]+ansV[k][j])
{
ansV[i][j]=ansV[i][k]+ansV[k][j];
path[i][j]=k;
}
}
}
}
path[i][j]:表示点i到点j的最短路中，需要经过点path[i][j]
初始化 path初始全0
当我记录了path[N][N]该如何求出最短路呢？
递归！
void printRoad(int fr,int to)
{
if (fr==to)
return ;
if (path[fr][to]==0)
{
cout<<fr<<"->";
return ;
}
printRoad(fr,path[fr][to]);
printRoad(path[fr][to],to);
return ;
}
最后在函数返回处的后面输出
cout<<to<<endl;
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1002,INF=0x3f3f3f3f;
int gw[N][N],gv[N][N],n,m;
int ansW[N][N],ansV[N][N],path[N][N];
void Floyd()
{
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
ansW[i][j]=gw[i][j];
ansV[i][j]=gv[i][j];
}
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
if (ansW[i][j]>ansW[i][k]+ansW[k][j])
{
ansW[i][j]=ansW[i][k]+ansW[k][j];
ansV[i][j]=ansV[i][k]+ansV[k][j];
path[i][j]=k;
}
else if (ansW[i][j]==ansW[i][k]+ansW[k][j])
{
if (ansV[i][j]<ansV[i][k]+ansV[k][j])
{
ansV[i][j]=ansV[i][k]+ansV[k][j];
path[i][j]=k;
}
}
}
}
int sta;
void find()
{
int minw=INF,maxw=0;
for (int i=1;i<=n;i++)
{
maxw=0;
for (int j=1;j<=n;j++)
{
if (ansW[i][j]<INF)
maxw=max(maxw,ansW[i][j]);
}
if (minw>maxw)
minw=maxw,sta=i;
}
}
void printRoad(int fr,int to)
{
if (fr==to)
return ;
if (path[fr][to]==0)
{
cout<<fr<<"->";
return ;
}
printRoad(fr,path[fr][to]);
printRoad(path[fr][to],to);
return ;
}
int main()
{
memset(gw,0x3f,sizeof(gw));
memset(gv,-0x3f,sizeof(gv));
cin>>n>>m;
for (int i=1;i<=n;i++)
gw[i][i]=gv[i][i]=0;
for (int i=1;i<=m;i++)
{
int b1,b2,w,v;
cin>>b1>>b2>>w>>v;
gw[b1][b2]=gw[b2][b1]=w;
gv[b1][b2]=gv[b2][b1]=v;
}
Floyd();
find();
cout<<sta<<endl;
int t;
cin>>t;
while (t--)
{
int tar;
cin>>tar;
printRoad(sta,tar);
cout<<tar<<endl;
cout<<ansW[sta][tar]<<" "<<ansV[sta][tar]<<endl;
}
return 0;
}
《7-4 疫情防控》
问能否从某个地方到某个地方
其实就是在问这两个点的连通性咋样
对应连通性的问题当然用并查集
这里可以用加点的方式（而不是按照题目惯性思维来删点），来解决复杂度过高的问题
#include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<stack> using namespace std; typedef pair<int,int> PII; const int N=5*1e4; vector<int>sides[N]; vector<PII>cm[N]; int n,m,d,city[N],f[N]; bool die[N]; int find(int x) { if (f[x]!=x) f[x]=find(f[x]); return f[x]; } int main() { cin>>n>>m>>d; for (int i=1;i<=m;i++) { int a,b; cin>>a>>b; sides[a].push_back(b),sides[b].push_back(a); } for (int i=1;i<=d;i++) { int c,q; cin>>c>>q; city[i]=c,die[c]=true; while (q--) { int x,y; cin>>x>>y; cm[i].push_back({x,y}); } } for (int i=1;i<=n;i++) f[i]=i; for (int i=1;i<=n;i++) { if (die[i]) continue; for (int j=0;j<sides[i].size();j++) { int ch=sides[i][j]; if (die[ch]) continue; int fa=find(i),fb=find(ch); if (fa!=fb) f[fb]=fa; } } stack<int>ans; for (int i=d;i>=1;i--) { int dieC=city[i]; int cnt=0; for (int j=0;j<cm[i].size();j++) { int x=cm[i][j].first,y=cm[i][j].second; int fx=find(x),fy=find(y); if (fx!=fy) cnt++; } ans.push(cnt); die[dieC]=false; for (int j=0;j<sides[dieC].size();j++) { int ch=sides[dieC][j]; if (die[ch]) continue; int fa=find(dieC),fb=find(ch); if (fa!=fb) f[fb]=fa; } } while (ans.size()) { cout<<ans.top()<<endl; ans.pop(); } return 0; }