Acwing.第134场周赛
A排序
思路：
简单的模拟
代码：
#include<bits/stdc++.h>
using namespace std;
void solve(){
int a,b,c;
cin>>a>>b>>c;
int ans=a+b+c;
int maxn=max(a,max(b,c));
int minn=min(a,min(b,c));
cout<<minn<<" "<<ans-maxn-minn<<" "<<maxn<<endl;
}
int main(){
int t=1;
while(t--){
solve();
}
return 0;
}
B 中等计算
思路：
代码：
#include<bits/stdc++.h>
using namespace std;
int b[1000005];
int main(){
int n,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)b[i]=b[i-1]^i;//预处理
int s=n%2?2:1;
for(;s<n;s+=2)ans^=s;
for(int i=2;i<=n;i++){
int j=n-i+1;
if(j%i==0&&j/i%2==0)continue;
ans^=b[j%i-1];//被省了
if(j/i%2)ans^=b[i-1];//被省了
}
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
ans^=x;
}
cout<<ans;
return 0;
}
C建立新边
思路：
我们可以对s点和t点都求一下跟所有点的最短路，之后我们在考虑新建的边对s到t最短路的影响，由于是无向边，所以我们要考虑两个方向
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1100;
const int INF=0x3f3f3f3f;
bool st[N][N];
int dist[2][N];
int n,m,s,t;
int ans;
std::vector<int> g[N];
void dfs(int x){
int sd=s;
if(x==1){
sd=t;
}
queue<int> q;
q.push(sd);
for(int i=1;i<=n;i++){
dist[x][i]=INF;
}
dist[x][sd]=0;
while(q.size()){
int y=q.front();
q.pop();
for(auto i:g[y]){
if(dist[x][i]>dist[x][y]+1){
dist[x][i]=dist[x][y]+1;
q.push(i);
}
}
}
}
void solve(){
// int n,m,s,t;
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
st[x][y]=st[y][x]=true;
//无向边
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=0;i<2;i++){
dfs(i);
}
int dist1=dist[0][t];
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(st[i][j]){
continue;
}
if(dist[0][i]+dist[1][j]+1<dist1||dist[0][j]+dist[1][i]+1<dist1){
continue;
}
ans++;
}
}
cout<<ans<<endl;
return ;
}
signed main(){
int t=1;
while(t--){
solve();
}
return 0;
}