Acwing.第132场周赛
A.大小写转换
思路：
简单的模拟，可以使用c++大小写转换库函数，但是由于我早上比赛时候没用好就不敢用了
就用了ASCII码转换
代码：
#include<bits/stdc++.h>
using namespace std;
void solve(){
string s;
cin>>s;
for(int i=0;i<s.size();i++){
s[i]=s[i]+32;
cout<<s[i];
}
}
int main(){
int t=1;
while(t--){
solve();
}
return 0;
}
B.不合群数
思路：
题目当中告诉的很详细了，10亿中两个质数之间不会超过300个数，这里我们需要注意下特殊情况，这里我们将特殊情况加在判断素数的过程当中就行，事实上最后不是在判断一个素数，二十在判断一个大于a的不能被[2,n]整除的数字。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b;
bool prime(int x){
if(x==1||x==0){
return false;
}
if(x==2){
return true;
}
for(int i=2;i<=x/i;i++){
if(x%i==0&&i<=a){
return false;
}
}
return true;
}
void solve(){
cin>>a>>b;
// cout<<a<<" "<<b<<endl;
if(a>=b){
cout<<-1<<endl;
return ;
}
if(a==2){
for(int i=b;;i--){
if(i%2){
cout<<i<<endl;
return ;
}
}
cout<<-1<<endl;
return ;
}
for(int i=b;i>b-300&&i>a;i--){
// cout<<i<<endl;
if(prime(i)){
// // cout<<1<<endl;
// // return ;
// cout<<i<<endl;
// return ;
cout<<i<<endl;
return ;
}
// else if(prime(sqrt(i))&&sqrt(i)>a){
// cout<<i<<endl;
// return ;
// }
}
cout<<-1<<endl;
return ;
}
signed main(){
int t=1;
while(t--){
solve();
}
return 0;
}
C.最短距离
思路：
这个题实际上是可以用floyd的，因为我们只需要判断每一类之间的最小距离，而不是两点之间的最小距离，简单用一下并查集，就可以解决这个问题,一开始我竟然还在用编号去判断，太天真了哈哈哈，事实上根本不需要
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
int c[505];
int l[505],r[505];
int f[100005];
int g[505][505];
int a[100005];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void merge(int u,int v){
f[find(u)]=find(v);
}
signed main(){
cin>>n>>m>>k;
for(int i=1;i<=k;i++){
cin>>c[i];
l[i]=r[i-1]+1;
r[i]=r[i-1]+c[i];
c[i]+=c[i-1];
}
for(int i=1;i<=k;i++){
for(int j=1;j<=k;j++){
g[i][j]=0x3f3f3f3f3f3f3f3fll;
}
g[i][i]=0;
}
for(int i=1,j=1;i<=n;i++){
if(i>c[j]){
j++;
}
a[i]=j;
f[i]=i;
}
while(m--){
int u,v,w;
cin>>u>>v>>w;
if(w==0){
merge(u,v);
}
u=a[u];v=a[v];
g[v][u]=g[u][v]=min(g[u][v],w);
}
//floyd
for(int t=1;t<=k;t++){
for(int i=1;i<=k;i++){
for(int j=1;j<=k;j++){
g[i][j]=min(g[i][j],g[i][t]+g[t][j]);
}
}
}
for(int i=1;i<=k;i++){
for(int j=l[i]+1;j<=r[i];j++){
if(find(j)!=find(l[i])){
cout<<"No"<<endl;
return 0;
}
}
}
cout<<"Yes"<<endl;
for(int i=1;i<=k;i++){
for(int j=1;j<=k;j++){
int s=g[i][j];
if(s>0x1f3f3f3f3f3f3f3fll)cout<<-1<<" ";
else cout<<s<<" ";
}
cout<<endl;
}
return 0;
}