Degrees of Separation
#include<bits/stdc++.h>
using namespace std;
int p,r;//人数 关系数
map<string,int> mp;
string s,str;
int cnt=0,ans=0;
vector<int> graph[55];//邻接表
bool vis[55];
int dis[55];
int Case=0;
void bfs(int n){
memset(dis, 0, sizeof(dis));
memset(vis, 0, sizeof(vis));
queue<int> Q;
vis[n] = 1;
Q.push(n);
int num = 1;
while (!Q.empty()) {
int now = Q.front();
if (num == p && Q.size() == 1)
ans = max(ans, dis[now]);
Q.pop();
for (int i = 0; i < graph[now].size(); i++) {
int next = graph[now][i];
if (!vis[next]) {
vis[next] = 1;
dis[next] = dis[now] + 1;
num++;
Q.push(next);
}
}
}
}
int main(){
while(cin>>p>>r&&p&&r){
ans=0;
cnt=0;
Case++;
mp.clear();
for(int i=0;i<55;i++) graph[i].clear();//上一个没清空的人多wa了两发
for(int i=0;i<r;i++){
cin>>s>>str;
if(mp.find(s)==mp.end()){
mp[s]=cnt++;
}
if(mp.find(str)==mp.end()){
mp[str]=cnt++;
}
graph[mp[s]].push_back(mp[str]);
graph[mp[str]].push_back(mp[s]);
}
for(int i=1;i<=p;i++) bfs(i);//每个点都搜一下,找到最大的关系数
if(ans==0) cout<<"Network"<<' '<<Case<<':'<<' '<<"DISCONNECTED"<<'\n'<<'\n';
else cout<<"Network"<<' '<<Case<<':'<<' '<<ans<<'\n'<<'\n';
}//注意一下这个毒瘤输出,有两个换行,这边建议printf
return 0;
}
}
小X的购物计划
#include<bits/stdc++.h>
using namespace std;
int n,m,p,r,c,w[1100],v[1100],dp[1100];
int main(){
int cnt=1;
cin>>m>>n;
for(int i=0;i<m;i++){
cin>>p>>r>>c;
if(c==-1){
c=0x3f3f3f;
int a=1;
while(c>=a&&a<=n){
w[cnt]=p*a;
v[cnt++]=r*a;
c-=a;
a<<=1;//(二进制优化成01背包)背包九讲里有说
}
}
else{
int a=1;
while(c>=a){
w[cnt]=p*a;
v[cnt++]=r*a;
c-=a;
a<<=1;
}
if(c){
w[cnt]=p*c;
v[cnt++]=r*c;
}
}
}
for(int i=1;i<cnt;i++)
for(int j=n;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
cout<<dp[n]<<'\n';
return 0;
}
第二点五个不高兴的小明
#include<cstring>
using namespace std;
int n,p,t;
const int N = 1111;
int g[N];
int f[N][N];
int main(){
cin>>n>>p>>t;
memset(f,-0x3f,sizeof(f));
for(int i=1;i<=n;i++) {
cin>>g[i];
if(i<=p) f[1][i] = g[i];
}
for(int i=2;i<=t;i++){
for(int j=i;j<=n+1;j++){
for(int k=1;k<=p&&(j-k>0);k++){
f[i][j]=max(f[i][j],f[i-1][j-k]+g[j]);
}
}
}
cout<<f[t][n+1];
return 0;
}
P0402
#include<bits/stdc++.h>
using namespace std;
int num=1;
int main(){
for(int i=0;i<9;i++){
num=(num+1)*2;
}
cout<<num;
return 0;
}
学生成绩统计
#include<bits/stdc++.h>
using namespace std;
struct node{
string Name;
int num;
double eg,mt,cjj,score;
}N[1000];
int n;
// double score[1000];
bool cmp(node x,node y){
return x.score<y.score;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>N[i].Name>>N[i].num>>N[i].eg>>N[i].mt>>N[i].cjj;
N[i].score=(N[i].eg+N[i].mt+N[i].cjj)/3.0;
}
sort(N,N+n,cmp);
cout<<N[n-1].Name<<endl;
cout<<N[0].Name<<endl;
return 0;
}
第一次讲题太紧张了,第一题的邻接表忘记讲了,万分抱歉,又只能靠各位自己去学了
相信我我本来打算讲的!(乐)