天梯赛练习题集
L2-005 集合相似度
find函数，Nt用集合关系求
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,k;
set<int>s[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++){int cnt;cin>>cnt;for(int j=1;j<=cnt;j++){int x;cin>>x;s[i].insert(x);}}cin>>k;while(k--){int a,b;cin>>a>>b;int Nc=0,Nt=0;for(auto i:s[a])if(s[b].find(i)!=s[b].end())Nc++;Nt=s[a].size()+s[b].size()-Nc;printf("%.2f%\\n",100.0*Nc/Nt);}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);// ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-008 最长对称子串
思路：f[i]表示以第i个字符结尾的最长对称子串的长度。
注意初始化：若s[i]==s[i-1] ,f[i]=f[i-1]+1;否则f[i]=1
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
string s;
int f[N];
void solve()
{getline(cin,s);s='?'+s;int n=s.length();for(int i=1;i<n;i++) {if(s[i]==s[i-1]) f[i]=f[i-1]+1;else f[i]=1;}for(int i=1;i<n;i++){if(i-f[i-1]-1>=1&&s[i-f[i-1]-1]==s[i]) f[i]=max(f[i],f[i-1]+2);else f[i]=max(f[i],1);}int ans=1;for(int i=1;i<n;i++)ans=max(ans,f[i]);cout<<ans<<'\\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-010 排座位
题意：
思路：二维数组g表示两者之间的朋友和敌对关系。将存在朋友的关系的合并在一块，做一个并查集。
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=110;
const int inf=0x3f3f3f3f;using namespace std;
int n,m,k;
int fa[2*N],g[N][N];
int find(int x)
{return fa[x]==x? x:fa[x]=find(fa[x]);
}
void merge(int a,int b)
{fa[find(a)]=find(b);
}
void solve()
{cin>>n>>m>>k;for(int i=0;i<N;i++) fa[i]=i;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;if(c==1){g[a][b]=g[b][a]=1;merge(a,b);}else{g[a][b]=g[b][a]=-1;}}while(k--){int a,b;cin>>a>>b;if(g[a][b]==1) puts("No problem");else if(g[a][b]==0) puts("OK");else {if(find(a)==find(b)) puts("OK but...");else puts("No way");}}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-011 玩转二叉树
题意：
思路：根据中序遍历和前序遍历还原二叉树，反转后输出答案。
中序遍历：LDR，可以划分出左右子树
前序遍历：DLR，可以找到子树的根。
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
struct node{int l,r;
}tr[N];
int n;
int z[N],q[N];
bool st[N];
map<int,int>pos;
void dfs(int u)
{st[u]=1;int p=0;for(int i=1;i<=n;i++)if(z[i]==u){p=i;break;}priority_queue<PII,vector<PII>,greater<PII>>L,R;for(int i=p-1;i>=1;i--)if(!st[z[i]]) L.push({pos[z[i]],z[i]});else break;for(int i=p+1;i<=n;i++)if(!st[z[i]]) R.push({pos[z[i]],z[i]});else break;if(L.size()) {int t=L.top().second;tr[u].l=t;dfs(t);}else tr[u].l=-1;if(R.size()) {int t=R.top().second;tr[u].r=t;dfs(t);}else tr[u].r=-1;
}
vector<int>ans;
void get(int u)
{queue<int>q;q.push(u);while(q.size()){int t=q.front();q.pop();ans.push_back(t);if(tr[t].r!=-1) q.push(tr[t].r);if(tr[t].l!=-1) q.push(tr[t].l);}
}
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>z[i];for(int i=1;i<=n;i++) {cin>>q[i];pos[q[i]]=i;}int root=q[1];dfs(root);get(root);for(int i=0;i<ans.size();i++)cout<<ans[i]<<" \\n"[i==n-1];
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-012 关于堆的判断
题意：
思路：模拟堆，注意up的写法。注意xy可能为负
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,m;
int h[N],sz;
void up(int u)
{while(u/2&&h[u/2]>h[u]){swap(h[u/2],h[u]);u/=2;}
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++){int x;cin>>x;sz++;h[sz]=x;up(sz);}// for(int i=1;i<=n;i++)// cout<<i<<' '<<h[i]<<'\\n';getchar();while(m--){string s;getline(cin,s);char c;int cnt=0;for(int i=0;i<s.length();i++){if(cnt==3) {c=s[i];break;}if(s[i]==' ') cnt++;}int x=0;bool f=0;for(int i=0;i<s.length();i++){if(s[i]==' ') break;else{if(s[i]>='0'&&s[i]<='9') x=x*10+int(s[i]-'0');else f=1;}}if(f) x*=-1;if(c=='r'){if(h[1]==x) puts("T");else puts("F");}else if(c=='a'){cnt=0;int y=0;f=0;for(int i=0;i<s.length();i++){if(cnt==2){if(s[i]=='-') f=1;else if(s[i]>='0'&&s[i]<='9') y=y*10+int(s[i]-'0');else break;}if(s[i]==' ') cnt++;}if(f) y*=-1;int px=0,py=0;for(int i=1;i<=sz;i++)if(h[i]==x) {px=i;break;}for(int i=1;i<=sz;i++)if(h[i]==y) {py=i;break;}if(px/2==py/2) puts("T");else puts("F");}else if(c=='p'){cnt=0;int y=0;f=0;for(int i=0;i<s.length();i++){if(cnt==5){if(s[i]=='-') f=1;else if(s[i]>='0'&&s[i]<='9') y=y*10+int(s[i]-'0');else break;}if(s[i]==' ') cnt++;}if(f) y*=-1;int px=0,py=0;for(int i=1;i<=sz;i++)if(h[i]==x) {px=i;break;}for(int i=1;i<=sz;i++)if(h[i]==y) {py=i;break;}if(px==py/2) puts("T");else puts("F");}else{cnt=0;int y=0;f=0;for(int i=0;i<s.length();i++){if(cnt==5){if(s[i]=='-') f=1;else if(s[i]>='0'&&s[i]<='9') y=y*10+int(s[i]-'0');else break;}if(s[i]==' ') cnt++;}if(f) y*=-1;int px=0,py=0;for(int i=1;i<=sz;i++)if(h[i]==x) {px=i;break;}for(int i=1;i<=sz;i++)if(h[i]==y) {py=i;break;}if(px/2==py) puts("T");else puts("F");}}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-013 红色警报
题意：
思路：若一个城市失去会影响其他城市的连通性，那么失去后的连通块个数>失去前的连通块个数+1.
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=510;
const int inf=0x3f3f3f3f;using namespace std;
int n,m,k;
bool g[N][N];
bool st[N];
void bfs(int x)
{queue<int>q;q.push(x);st[x]=1;while(q.size()){int t=q.front();q.pop();for(int i=0;i<n;i++){if(g[t][i]&&!st[i]){q.push(i);st[i]=1;} }}
}
int get()
{for(int i=0;i<n;i++) st[i]=0;int ret=0;for(int i=0;i<n;i++){if(!st[i]){bfs(i);ret++;}}return ret;
}
void solve()
{cin>>n>>m;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;g[a][b]=g[b][a]=1;}int last=get();cin>>k;int cnt=0;for(int i=1;i<=k;i++){int x;cin>>x;cnt++;for(int j=0;j<n;j++)g[x][j]=g[j][x]=0;int cur=get();if(cur>last+1) printf("Red Alert: City %d is lost!\\n",x);else printf("City %d is lost.\\n",x);if(cnt==n) printf("Game Over.\\n");last=cur;}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-014 列车调度
题意：
思路：因为要递减出站，同时为减少轨道条数，那么同一轨道上的火车从前到后编号一定是递减的。我们只需要关注每条轨道上最后一辆的编号即可。当要入站的编号比所有的都大，那么我们要新开一条轨道；否则我们就对大于要放入的值的轨道的值检索，找出跟其相差最少的一条轨道，把值放进去。
因为当要开新轨道时，新轨道的值一定是最大的。那么每条轨道的编号一定是递增的。我们在检索相差最少的一条轨道时就可以通过二分法来检索。
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e5+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,cur;
int a[N];
int tra[N],k;
int search(int x)
{int l=0,r=k-1;while(l<r){int mid=l+r>>1;if(tra[mid]<x) l=mid+1;else r=mid;}return l;
}
void fun(int x)
{if(tra[k-1]<x) tra[k++]=x;else tra[search(x)]=x;
}
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) fun(a[i]);cout<<k<<'\\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-016 愿天下有情人都是失散多年的兄妹
题意：
思路：对于每对查询的a,b，找出a，b五代内的亲人并标记，若有人被标记两次，则No。
注意要保存父母的性别。否则，父母的性别没给出的情况下，查询性别都是默认值，会出错。
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
struct node{int l=-1,r=-1;char sex;
}tr[N];
int n;
bool check(int a,int b)
{map<int,int>mp;mp[a]++,mp[b]++;if(mp[a]>=2) return 0;queue<node>q;q.push(tr[a]);q.push(tr[b]);for(int i=1;i<=4;i++){queue<node>cur;while(q.size()){node t=q.front();q.pop();if(t.l!=-1) {cur.push(tr[t.l]),mp[t.l]++;if(mp[t.l]>=2) {return 0;}}if(t.r!=-1) {cur.push(tr[t.r]),mp[t.r]++;if(mp[t.r]>=2) {return 0;}}}q=cur;}for(auto [a,b]:mp)if(b>=2) {return 0;}return 1;
}
void solve()
{cin>>n;for(int i=1;i<=n;i++){int num,l,r;char sex;cin>>num>>sex>>l>>r;if(l!=-1) tr[l].sex='M';if(r!=-1) tr[r].sex='F';tr[num]={l,r,sex};}int k;cin>>k;while(k--){int a,b;cin>>a>>b;if(tr[a].sex==tr[b].sex) puts("Never Mind");else {if(check(a,b)) puts("Yes");else puts("No");}}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-018 多项式A除以B
题意：
思路：模拟除法
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,m;
int b[N];
double a[N],c[N],d[N];
//a[i]=m x^i的系数为m
void solve()
{cin>>n;int f=0;for(int i=0;i<n;i++){int x;cin>>x;cin>>a[x];if(i==0) f=x;}cin>>m;for(int i=0;i<m;i++)cin>>b[i]>>d[i];for(int i=f;i>=b[0];i--){int t=i-b[0];c[t]=a[i]/d[0];for(int j=0;j<m;j++) a[t+b[j]]=a[t+b[j]]-c[t]*d[j];}int cntc=0,cntr=0;for(int i=f;i>=0;i--){if(fabs(c[i])>=0.05) cntc++;if(fabs(a[i])>=0.05) cntr++;}cout<<cntc;for(int i=f;i>=0;i--)if(fabs(c[i])>=0.05)printf(" %d %.1f",i,c[i]);if(cntc==0) printf(" 0 0.0");printf("\\n");cout<<cntr;for(int i=f;i>=0;i--)if(fabs(a[i])>=0.05)printf(" %d %.1f",i,a[i]);if(cntr==0) printf(" 0 0.0");printf("\\n");
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-020 功夫传人
题意：
思路：bfs/dfs
注意要先存图再搜索。
注意祖师爷为得道者的情况。
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
double n;
double z,r;
int h[N],e[N],ne[N],idx;
double p[N];
double st[N];
bool vis[N];
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
double ans;
void bfs()
{queue<int>q;q.push(0);vis[0]=1;if(st[0]) ans+=p[0]*st[0];while(q.size()){int t=q.front();q.pop();for(int i=h[t];~i;i=ne[i]){int j=e[i];if(vis[j]) continue;if(st[j]) {p[j]=p[t]*r;p[j]=p[j]*st[j];ans+=p[j];}else{p[j]=p[t]*r;}q.push(j);vis[j]=1;}}
}
void solve()
{memset(h,-1,sizeof h);cin>>n>>z>>r;r = (100-r)/100;p[0]=z;for(int i=0;i<n;i++){int k;cin>>k;if(k==0){int x;cin>>x;st[i]=x;}else{for(int j=0;j<k;j++){int x;cin>>x;add(i,x);}}}bfs();cout<<int(ans)<<'\\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-021 点赞狂魔
题意：
思路：结构体排序。当人数不足3时，可以多加几个“-”
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
struct node{string name;int cnt;int sum;
}a[N];
bool cmp(node a,node b)
{if(a.cnt==b.cnt) return a.sum<b.sum;else return a.cnt>b.cnt;
}
void solve()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i].name>>a[i].sum;set<int>s;for(int j=0;j<a[i].sum;j++){int x;cin>>x;s.insert(x);}a[i].cnt=s.size();// gao(a[i].cnt);}a[n+1]={"-"};a[n+2]={"-"};a[n+3]={"-"};n+=3;sort(a+1,a+n+1,cmp);for(int i=1;i<=3;i++)cout<<a[i].name<<" \\n"[i==3];
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-022 重排链表
题意：
思路：创建双向链表，双指针分别位于头尾交替输出
注意：输入的结点可能是不在链表里的“废结点”，需要统计有效节点的个数cnt
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
struct node{int data,nex;int pre;
}l[N];
void solve()
{int h,t;cin>>h>>n;for(int i=1;i<=n;i++){int a,b,c;cin>>a>>b>>c;l[a]={b,c};if(c==-1) t=a;}int H=h;int cnt=0;//有效节点个数while(H!=-1){cnt++;int tem=l[H].nex;l[tem].pre=H;H=tem;}for(int i=1;i<=cnt;i++){if(i&1){if(i!=cnt) printf("%05d %d %05d\\n",t,l[t].data,h);else printf("%05d %d -1\\n",t,l[t].data);t=l[t].pre;}else{if(i!=cnt) printf("%05d %d %05d\\n",h,l[h].data,t);else printf("%05d %d -1\\n",h,l[h].data);h=l[h].nex;}}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-023 图着色问题
题意：
思路：set判断颜色个数是否等于k，再暴力检查是否有相邻点颜色相同。
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=610;
const int inf=0x3f3f3f3f;using namespace std;
int v,e,k;
int g[N][N];
int col[N];
int n;
bool check()
{for(int i=1;i<=v;i++)for(int j=1;j<=v;j++)if(g[i][j]&&col[i]==col[j])return 0;return 1;
}
void solve()
{cin>>v>>e>>k;for(int i=1;i<=e;i++){int a,b;cin>>a>>b;g[a][b]=1;g[b][a]=1;}cin>>n;while(n--){set<int>s;for(int i=1;i<=v;i++){cin>>col[i];s.insert(col[i]);}if(s.size()==k){if(check()) puts("Yes");else puts("No");}else puts("No");}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-024 部落
题意：
思路：用并查集判断两人是否在同一个部落。用set判断这个社区的总人数、以及互不相交的部落的个数
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e4+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
int fa[N];
int find(int x)
{return fa[x]==x? x:fa[x]=find(fa[x]);
}
void merge(int a,int b)
{fa[find(a)]=find(b);
}
void solve()
{cin>>n;for(int i=0;i<N;i++) fa[i]=i;set<int>s;for(int i=1;i<=n;i++){int k;cin>>k;int a;if(k!=0) {cin>>a;s.insert(a);}for(int j=2;j<=k;j++){int x;cin>>x;s.insert(x);merge(x,a);}}cout<<s.size()<<' ';set<int>cnt;for(auto i:s){cnt.insert(find(i));}cout<<cnt.size()<<'\\n';int q;cin>>q;while(q--){int a,b;cin>>a>>b;if(find(a)==find(b)) puts("Y");else puts("N");}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-025 分而治之
题意：
思路：方案是否可行，即是否城市之间还有通路。可以把m条边存起来，标记攻下的城市，再遍历m条边，看是否还有通路。
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,m;
struct node{int x,y;
}e[N];
void solve()
{cin>>n>>m;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;e[i]={a,b};}int k;cin>>k;while(k--){map<int,bool>mp;int cnt;cin>>cnt;for(int i=1;i<=cnt;i++){int x;cin>>x;mp[x]=1;}bool f=0;for(int i=1;i<=m;i++){if(mp[e[i].x]==0&&mp[e[i].y]==0){f=1;puts("NO");break;}}if(!f) puts("YES");}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-026 小字辈
思路：建树，辈分最小的即为树中深度最大的。用dfs求点的深度
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e5+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
int h[N],e[N],ne[N],idx;
int dep[N],maxd;
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int d)
{dep[u]=d;maxd=max(maxd,d);for(int i=h[u];~i;i=ne[i]){int j=e[i];dfs(j,d+1);}
}
void solve()
{memset(h,-1,sizeof h);cin>>n;int root=-1;for(int i=1;i<=n;i++){int x;cin>>x;if(x==-1) root=i;else add(x,i);}dfs(root,1);cout<<maxd<<'\\n';vector<int>ans;for(int i=1;i<=n;i++)if(dep[i]==maxd)ans.push_back(i);sort(ans.begin(),ans.end());for(int i=0;i<ans.size();i++)cout<<ans[i]<<" \\n"[i==ans.size()-1];
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-027 名人堂与代金券
题意：
思路：结构体排序，注意排名的计算和成绩并列时的输出
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,g,k;
struct node{string name;int s;
}a[N];
bool cmp(node a,node b)
{if(a.s==b.s) return a.name<b.name;return a.s>b.s;
}
void solve()
{cin>>n>>g>>k;int sum=0;for(int i=1;i<=n;i++){cin>>a[i].name>>a[i].s;if(a[i].s>=60&&a[i].s<g) sum+=20;else if(a[i].s>=g) sum+=50;}cout<<sum<<'\\n';sort(a+1,a+n+1,cmp);int cnt=0,last=-1;int i;for(i=1;i<=k;i++){if(a[i].s==last)cout<<cnt<<' '<<a[i].name<<' '<<a[i].s<<'\\n';else{cout<<i<<' '<<a[i].name<<' '<<a[i].s<<'\\n';cnt=i;}// cnt=i;last=a[i].s;}while(a[i].s==last){cout<<cnt<<' '<<a[i].name<<' '<<a[i].s<<'\\n';i++;}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-028 秀恩爱分得快
题意：
思路：r数组存照片中的人，只计算与a和b有关的亲密度，st数组存性别。注意-0的输入和输出，输入用字符串。
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1010;
const int inf=0x3f3f3f3f;using namespace std;
int n,m;
int st[N];
vector<int>r[N];
double pa[N],pb[N];
int change(string x)
{bool f=0;if(x[0]=='-') f=1;int ret=0;for(int i=0;i<x.length();i++){if(x[i]>='0'&&x[i]<='9')ret=ret*10+int(x[i]-'0');}if(f) st[ret]=-1;return ret;
}
void solve()
{cin>>n>>m;for(int i=0;i<n;i++) st[i]=1;for(int i=0;i<m;i++){int k;cin>>k;for(int j=0;j<k;j++){string s;cin>>s;int x=change(s);r[i].push_back(x);}}string A,B;cin>>A>>B;int a,b;a=change(A);b=change(B);bool exist_a,exist_b;double maxa=0,maxb=0;//a，b与异性的最大亲密度for(int i=0;i<m;i++){exist_a=(find(r[i].begin(),r[i].end(),a)!=r[i].end());exist_b=(find(r[i].begin(),r[i].end(),b)!=r[i].end());if(exist_a||exist_b){int k=r[i].size();for(int j=0;j<k;j++){if(exist_a&&st[r[i][j]]!=st[a]){pa[r[i][j]]+=1.0/(1.0*k);maxa=max(maxa,pa[r[i][j]]);}if(exist_b&&st[r[i][j]]!=st[b]){pb[r[i][j]]+=1.0/(1.0*k);maxb=max(maxb,pb[r[i][j]]);}}}}if(maxa==pa[b]&&maxb==pb[a]){printf("%s%d %s%d\\n",st[a]==1? "":"-",a,st[b]==1? "":"-",b);}else{for(int i=0;i<n;i++)if(pa[i]==maxa)printf("%s%d %s%d\\n",st[a]==1? "":"-",a,st[i]==1? "":"-",i);for(int i=0;i<n;i++)if(pb[i]==maxb)printf("%s%d %s%d\\n",st[b]==1? "":"-",b,st[i]==1? "":"-",i);}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-029 特立独行的幸福
题意：
思路：我们可以把数指向他迭代的下一个数来建树。然后判断区间内每个数的祖宗节点是不是1，有没有依附来判断。
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e4+10;
const int inf=0x3f3f3f3f;using namespace std;
int a,b;
bool st[N];
int primes[N],cnt;
void get(int n)
{for(int i=2;i<=n;i++){if(!st[i]) primes[cnt++]=i;for(int j=0;primes[j]<=n/i;j++){st[i*primes[j]]=1;if(i%primes[j]==0) break;}}
}
int fa[N];
int change(int x)//平方和
{int ret=0;while(x){int t=x%10;x/=10;ret+=t*t;}return ret;
}
int num;
int find(int x)//找祖宗节点
{num=0;while(fa[x]!=x){num++;x=fa[x];if(num>N) return -1;}return x;
}
bool check(int x)//[a,b]有没有数依附于x
{for(int i=a;i<=b;i++)if(fa[i]==x) return 0;return 1;
}
void solve()
{cin>>a>>b;get(b);for(int i=1;i<N;i++) fa[i]=i;for(int i=1;i<N;i++)fa[i]=change(i);//每个数指向其平方和int ans=0;for(int i=a;i<=b;i++){if(find(i)==1&&check(i)){if(!st[i]) num*=2;cout<<i<<' '<<num<<'\\n';ans++;}}if(ans==0) puts("SAD");
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}L2-030 冰岛人
题意：
思路：名字是唯一的，以名字作为map的key。check函数内，枚举五代内的关系，判断是否有公共祖先。r[A]用来存储A的性别以及父亲姓名.注意：五代以内无公共祖先的意思，若公共祖先为A的父亲，为B的十几代祖宗，那么也输出No
#include <bits/stdc++.h>
const int N=1e5+10;
using namespace std;
int n;
map<string,pair<int,string>>r;
bool check(string a,string b)
{string b2=b;int cnt1=0,cnt2=0;while(a!="-1"){b=b2;cnt2=0;while(b!="-1"){if(a==b&&(cnt1<4||cnt2<4)) {return 0;}else if(cnt1>=4&&cnt2>=4){return 1;}cnt2++;b=r[b].second;}cnt1++;a=r[a].second;}return 1;
}
int main()
{ cin>>n;for(int i=1;i<=n;i++){string fname,sname;cin>>fname>>sname;int m=sname.length();if(sname[m-1]=='n'){string fa=sname.substr(0,m-4);r[fname]={1,fa};}else if(sname[m-1]=='r'){string fa=sname.substr(0,m-7);r[fname]={-1,fa};}else if(sname[m-1]=='f'){r[fname]={-1,"-1"};}else {r[fname]={1,"-1"};}}int m;cin>>m;while(m--){string f1,s1,f2,s2;cin>>f1>>s1>>f2>>s2;if(!r.count(f1)||!r.count(f2)) puts("NA"); else if(r[f1].first!=r[f2].first){if(check(f1,f2)) puts("Yes");else puts("No");}else puts("Whatever");}return 0;
}