SMU 2024 spring 天梯赛2(补题)
https://pintia.cn/problem-sets/1772539187410104320/exam/overview
7-10 红色警报
错误：
① 没写
② 用的unordered_map<>判断的联通条件。只要有城市和它相连就判它在城市群里，只对了样例。。。
③ 不会深搜。。。
#include<bits/stdc++.h>
using namespace std;
int degree[510];
int G[510][510];
int vis[510];//访问标记。
int del[510];//占领标记。
int n,k;
void dfs(int step)
{
for(int i=0;i<n;i++)
{
if(vis[i]==0 and del[i]==0 and G[step][i])
{//如果这个点没有被标记过，并且没有被占领过，并且他和这个传入城市点联通；
vis[i]=1;
dfs(i);
//只要联通的城市没有被扫完，那么就一直搜索。
}
}
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>n>>k;
for(int i=0;i<k;i++)
{
int x,y;
cin>>x>>y;
G[x][y]=G[y][x]=1;
//建立联通状况
}
int num_line=0;
for(int i=0;i<n;i++)
{
//起始第一个点一定会被加，即使全部联通总数也会是1.
if(vis[i]==0)
{
vis[i]=1;
num_line++;
dfs(i);
}
//通过深搜来避免城市的错误统计。
}
int m;
cin>>m;
for(int i1=0;i1<m;i1++)
{
int x;
cin>>x;
for(int i=0;i<n;i++)
{
if(G[x][i]==1)
{
G[x][i]=G[i][x]=0;
}
//删去被占领城市的联通城市。
}
del[x]=1;
memset(vis,0,sizeof(vis));
int num_line_after=0;
for(int i=0;i<n;i++)
{
if(vis[i]==0 and del[i]==0)
{
vis[i]=1;
num_line_after++;
dfs(i);
}
//同样用深搜来查找城市块个数
}
if(num_line<num_line_after)
cout<<"Red Alert: City "<<x<<" is lost!\n";
else
cout<<"City "<<x<<" is lost.\n";
num_line=num_line_after;
if(i1==n-1)
cout<<"Game Over.\n";
}
return 0;
}
memset函数及其用法
void *memset(void src, int value, size_t n);
这里srs可以是数组名，也可以是指向某一内存空间的指针；
value为要填充的值；
n为要填充的字节数，通常为sizeof(s)；
函数的功能：将指针变量 src 所指向的前 n 字节的内存单元用一个“整数” value 替换，注意 value是 int 型。src 是 void 型的指针变量，所以它可以为任何类型的数据进行初始化。
解释memset(a,'0',sizeof(a)); 的意思
这条语句是把a中所有字节换做字符“0”，常用来对指针或字符串的初始化。
7-11 排座位
-_-*如果if(),else if()...else if();最后某个选项结果不合预期时可以是这个把最后一个换成else...(天梯）。。。分数从4变到了22。。。
这里的代码设置了两个初始数组，mp用来存放两个人彼此的关系情况，fri用来保存两个人是否为朋友。
利用三重循环，对于每一个人，以其为中间人，遍历他的所有朋友和所有以他为朋友的人，将这些人的关系网全都扩展开（朋友的朋友也是朋友）。
接着按照题目的要求。如果两个宾客间是。。。那么。。。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mp[200][200],fri[200][200];
int main()
{
int n,m,k;
cin>>n>>m>>k;
int a,b,c;
for(int i=1;i<=m;i++)
{
cin>>a>>b>>c;
mp[a][b]=c;
mp[b][a]=c;
if(c==1)
{
fri[a][b]=c;
fri[b][a]=c;
}
}
for(int z=1;z<=n;z++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(fri[i][z]==1&&fri[z][j]==1)
{
fri[i][j]=1;
}
}
}
}
while(k--)
{
cin>>a>>b;
if(mp[a][b]==-1&&fri[a][b]==0)
{
cout<<"No way"<<endl;
}else if(mp[a][b]==-1&&fri[a][b]==1)
{
cout<<"OK but..."<<endl;
}else if(mp[a][b]==0)
{
cout<<"OK"<<endl;
}else
{
cout<<"No problem"<<endl;
}
}
return 0;
}
unordered_map解法：
设立结构体数组，存放每个人的敌和友，对于每个人遍历他所有朋友的所有朋友。最后按要求来^_^
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct p
{
unordered_map<int,int>di;
unordered_map<int,int>you;
};
int main()
{
int n,m,k;
cin>>n>>m>>k;
vector<p>s(n+1);
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
if(c==-1)
{
s[a].di[b]++;
s[b].di[a]++;
}else if(c==1)
{
s[a].you[b]++;
s[b].you[a]++;
}
}
for(int i=1;i<n;i++)
{
for(auto&c:s[i].you)
{
for(auto&d:s[c.first].you)
{
s[i].you[d.first]++;
}
}
}
for(int i=0;i<k;i++)
{
int a1,a2;
cin>>a1>>a2;
if(s[a1].you[a2]>0&&s[a1].di[a2]==0
&&s[a2].you[a1]>0&&s[a2].di[a1]==0)
{
cout<<"No problem"<<endl;
}else if(s[a1].you[a2]==0&&s[a1].di[a2]==0
&&s[a2].you[a1]==0&&s[a2].di[a1]==0)
{
cout<<"OK"<<endl;
}else if(s[a1].you[a2]==0&&s[a1].di[a2]>0
&&s[a2].you[a1]==0&&s[a2].di[a1]>0)
{
cout<<"No way"<<endl;
}else
{
cout<<"OK but..."<<endl;
}
}
return 0;
}
7-7 估值一亿的AI核心代码
字符串随笔
https://www.cnblogs.com/miao-jc/p/18056399
点击查看题目
本题要求你实现一个稍微更值钱一点的 AI 英文问答程序，规则是：
· 无论用户说什么，首先把对方说的话在一行中原样打印出来；
· 消除原文中多余空格：把相邻单词间的多个空格换成 1 个空格，
把行首尾的空格全部删掉，把标点符号前面的空格删掉；
· 把原文中所有大写英文字母变成小写，除了 I；
· 把原文中所有独立的 can you、could you 对应地换成 I can、I could
—— 这里“独立”是指被空格或标点符号分隔开的单词；
· 把原文中所有独立的 I 和 me 换成 you；
· 把原文中所有的问号 ? 换成惊叹号 !；
· 在一行中输出替换后的句子作为 AI 的回答。
**输入格式：**
输入首先在第一行给出不超过 10 的正整数 N，
随后 N 行，每行给出一句不超过 1000 个字符的、以回车结尾的用户的对话，
对话为非空字符串，仅包括字母、数字、空格、可见的半角标点符号。
**输出格式：**
按题面要求输出，每个 AI 的回答前要加上 AI: 和一个空格。
输入样例：
6
Hello ?
Good to chat with you
can you speak Chinese?
Really?
Could you show me 5
What Is this prime? I,don 't know
输出样例：
Hello ?
AI: hello!
Good to chat with you
AI: good to chat with you
can you speak Chinese?
AI: I can speak chinese!
Really?
AI: really!
Could you show me 5
AI: I could show you 5
What Is this prime? I,don 't know
AI: what Is this prime! you,don't know
解题代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);
int n;
cin>>n;
string s;
getline(cin,s);
while(n--)
{
getline(cin,s);//读入一句话。
cout << s << "\nAI: ";//原封不动的输出并加上开头。
//把行首尾的空格全删掉。
while(s.back()==' ')
s.pop_back();
reverse(s.begin(),s.end());
while(s.back()==' ')
s.pop_back();
reverse(s.begin(),s.end());
string ans;
int cnt=0;//记录一句话中某个单词的长度。
for(auto& c:s){
if(c==' ')//如果当前不是字符。
{
cnt++;
}else if(isalpha(c)||isdigit(c))//判断是否为字母或数字。
{
if(cnt)//如果这个字符是空格后的第一个字符。那就先在语句上加一个空格。
ans+=' ';
if(isupper(c)&&c!='I')//如果是大写字母并且不等于'I'就将其转化为小写字母
c-='A'-'a';
ans+=c;//将改过的字符加入新的语句中。
cnt=0;//重新等待空格的到来。
}else{
if(c=='?')//如果是符号'?'就转化为'!'
c='!';
ans+=c;
cnt=0;//重新等待空格的到来。
}
}
//在主函数内部设立函数。
auto f=[&](const string &k,const string&v)
{
int now=-1;
while((now=ans.find(k,now+1))!=ans.npos)//在字符串ans中查找关键字k的位置，并更新now的值。
{
int ok=0;
//判断边界条件，如果字符串前后不是数字或字符（是空格或标点）就让ok达到替换条件。
if(now-1<0||(!isalnum(ans[now-1])&&!isdigit(ans[now-1])))
{
ok++;
}
if(now+k.size()>=ans.size()||(!isalpha(ans[now+k.size()])&&!isdigit(ans[now+k.size()])))
{
ok++;
}
//字符串替换。
if(ok==2)
{
ans.erase(now,k.size());
ans.insert(now,v);
}
}
};
f("can you","IS can");//①//将替换样例中的I替换为IS可以避免进行③操作时将I再换成you
f("could you","IS could");//②
f("I","you");//③
f("me","you");//④
for(int i=0;i<ans.size();i++)
{
cout<<ans[i];
//设立了I的输出条件。
if(ans[i]=='I'&&i+1<ans.size()&&ans[i+1]=='S')
{
i++;
}
}
cout<<'\n';
}
}
SMU 2024 spring 天梯赛3(补题)
7-8 连续因子
点击查看题目
一个正整数 N 的因子中可能存在若干连续的数字。
例如 630 可以分解为 3×5×6×7，其中 5、6、7 就是 3 个连续的数字。
给定任一正整数 N，要求编写程序求出最长连续因子的个数，并输出最小的连续因子序列。
输入格式：
输入在一行中给出一个正整数 N（1<N<2^31）。
输出格式：
首先在第 1 行输出最长连续因子的个数；
然后在第 2 行中按 因子1*因子2*……*因子k 的格式输出最小的连续因子序列，
其中因子按递增顺序输出，1 不算在内。
输入样例：
630
输出样例：
3
5*6*7
这个题。。。要求的是什么啊，是这个啊：题目的逻辑是先把N拆成几个因子，再在这几个因子里找连续，而不是直接找到所有因子再找连续
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1000];
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int n;
cin>>n;
int i=0,j=0,sum=0,num=0,temp=0,qidian=0,longqidian=0;
int x=sqrt(n);
//最终形式要成为n=x1*x2*x3*x4*x5....xm。
//例如：如果n是625的话，如果下面的循环到达25了，就不必在进行26了。
//因为因子的相乘是递增的，如果一个数的平方到达了n，那么和下一个数的再乘积一定会超过n。
//所以只用判到sqrt(n)就好。
for(int i=2;i<=x;i++)
{
num=0;
sum=n;
qidian=i;
for(j=i;sum%j==0&&sum!=0;j++)
{
sum/=j;
num++;
}
if(num>temp)
{
temp=num;
longqidian=qidian;
}
}
//如果n为质数的话就会用到这个条件。
if(temp==0)
{
cout<<"1"<<endl<<n<<endl;
}else
{
cout<<temp<<endl;
i=longqidian;
while(i<longqidian+temp)
{
if(i!=longqidian)
{
cout<<"*";
}
cout<<i;
i++;
}
}
return 0;
}
7-9 哈利·波特的考试
Dijkstra算法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxint 2147483647
typedef struct
{
int arcs[102][102];
int vexnum,arcnum;
}aaa;
int s[102];
int d[102];
int path[102];
int n,i,u,j,m,v,min0,w,a,b,c,min1=999999,max1=-991111,p=0;
void djstela(aaa g,int v0)
{
n=g.vexnum;
for(v=0;v<n;v++)
{
s[v]=0;
d[v]=g.arcs[v0][v];
if(d[v]<maxint)
path[v]=v0;
else
path[v]=-1;
}
s[v0]=1;
d[v0]=0;
for(i=1;i<n;i++)
{
min0=maxint;
for(w=0;w<n;w++)
{
if(!s[w]&&d[w]<min0)
{
min0=d[w];
v=w;
}
}
s[v]=1;
for(w=0;w<n;w++)
{
if(!s[w]&&(d[v]+g.arcs[v][w]<d[w]))
{
d[w]=d[v]+g.arcs[v][w];
path[w]=v;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
aaa g;
memset(s,0,sizeof(s));
memset(d,0x3f3f3f3f,sizeof(d));
memset(g.arcs,0x3f3f3f3f,sizeof(g.arcs));
cin>>g.vexnum>>m;
for(i=0;i<m;i++)
{
cin>>a>>b>>c;
g.arcs[a-1][b-1]=c;
g.arcs[b-1][a-1]=c;
}
for(u=0;u<g.vexnum;u++)
{
max1=-9999999;
djstela(g,u);
for(j=0;j<g.vexnum;j++)
{
if(d[j]>max1)
{
max1=d[j];
}
}
if(max1<min1)
{
min1=max1;
p=u+1;
}
}
if(p==0)
{
cout<<"0";
}else
{
cout<<p<<" "<<min1<<endl;
}
return 0;
}
7-10 列车厢调度 (•̀ᴗ•́)و ̑̑
点击查看错误代码
//设置了一个栈3，来模拟第三铁道，存在段错误和数组答案错误。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
stack<char>s3;
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
string ss1,ss2;
cin>>ss1>>ss2;
int p1=0,p2=0;
while(p1!=ss1.size()||!s3.empty())
{
while(ss1[p1]==ss2[p2])
{
p1++;
p2++;
}
while(!s3.empty())
{
if(s3.top()==ss2[p2])
{
s3.pop();
p2++;
}else
{
break;
}
}
while(ss1[p1]!=ss2[p2])
{
s3.push(ss1[p1]);
p1++;
if(p1>=ss1.size())
break;
}
if(p2==ss2.size())
break;
if(s3.top()!=ss2[p2]&&ss1[p1]!=ss2[p2])
{
break;
}
}
if(p2!=ss2.size())
{
cout<<"Are you kidding me?"<<endl;
}else
{
int p1=0,p2=0;
while(p1!=ss1.size()||!s3.empty())
{
while(ss1[p1]==ss2[p2])
{
p1++;
p2++;
cout<<"1->2"<<endl;
}
while(!s3.empty())
{
if(s3.top()==ss2[p2])
{
cout<<"3->2"<<endl;
s3.pop();
p2++;
}else
{
break;
}
}
while(ss1[p1]!=ss2[p2])
{
cout<<"1->3"<<endl;
s3.push(ss1[p1]);
p1++;
if(p1>=ss1.size())
break;
}
if(p2==ss2.size())
break;
if(s3.top()!=ss2[p2]&&ss1[p1]!=ss2[p2])
{
break;
}
}
}
return 0;
}
正确代码：
1-》1->2;
2-》1->3;
3-》3->2;
先把s1和s2两个栈填充好（逆序）（先进后出），由于能用1->2完成，就不用1->3,3->2完成，首先，如果s1的顶和s2的顶相同，那么两个栈顶分别弹出，记作过程1，如果不行，才进行过程2，即从s3里面找，如果1也空了，s2有没被排空，s3的栈顶又不合要求，那么就无法完成操作。全不是，就从s1中抽元素填入s3。在s2被排空之前，重复进行操作。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
//ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
string a,b;
cin>>a>>b;
stack<char>s1,s2,s3;
vector<int>way;
int len1=a.size(),len2=b.size();
int i;
for(i=len1-1;i>=0;i--)
{
s1.push(a[i]);
}
for(i=len2-1;i>=0;i--)
{
s2.push(b[i]);
}
bool flag=true;
while(!s2.empty())
{
if(!s1.empty()&&s1.top()==s2.top())
{
s1.pop();
s2.pop();
way.push_back(1);
}
else if(!s3.empty()&&s3.top()==s2.top())
{
s3.pop();
s2.pop();
way.push_back(3);
}else if(s1.empty()&&!s2.empty()&&s3.top()!=s2.top())
{
flag=false;
break;
}else
{
s3.push(s1.top());
s1.pop();
way.push_back(2);
}
}
if(!flag)
{
cout<<"Are you kidding me?\n";
}
else
{
int count=way.size();
for(i=0;i<count;i++)
{
if(way[i]==1)
{
cout<<"1->2\n";
}
else if(way[i]==2){
cout<<"1->3\n";
}
else
cout<<"3->2\n";
}
}
return 0;
}