L2-001 紧急救援
题意：就是给你一张n<500的图；让你求最短路径，最短路条数，以及路径；
做法，先用dijkstra求最短路，然后dfs找最短路条数，以及点权的最大值；
一般dfs不就可以解决这个问题吗，像n皇后求次数，注意回溯即可；
那如何dfs确定这条路是最短路径呢？贪心思想，枚举每一个邻居，如果满足 dis[y.v]==dis[x]+y.w 说明当前邻居 通过这个点可以一直是最短路径，这样dfs下去，如果碰到d就return掉；
主要是没有想到用dfs求最短路径条数，然后注意回溯即可；
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define pf push_front
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
const db PI=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3fLL;
const int inf=0x3f3f3f3f;//0x7fffffff;
const double eps=1e-;
const ll MOD=1e9+;
const int maxn=1e3+;
int n,m,s,d;
int dis[maxn],val[maxn];
bool vis[maxn];
struct edge{int v,w;edge(int a,int b){v=a,w=b;}};
vector<edge>e[maxn];
struct node{
int id,dis;
node(int a,int b){id=a,dis=b;}
friend bool operator<(node a,node b){
return a.dis>b.dis;
}
};
void solve(){
rep(i,,n)vis[i]=,dis[i]=inf;
dis[s]=;
priority_queue<node>Q;
Q.push(node(s,));
while(!Q.empty()){
node u=Q.top();
Q.pop();
if(vis[u.id])continue;
vis[u.id]=;
for(int i=;i<e[u.id].size();i++){
edge y=e[u.id][i];
if(vis[y.v])continue;
if(dis[y.v]>y.w+u.dis){
dis[y.v]=y.w+u.dis;
Q.push(node(y.v,dis[y.v]));
}
}
}
}
int Max,cnt;
vector<int>path,pre;
void dfs(int x,int w){
if(x==d){
if(w>Max){
Max=w;
path=pre;
}
cnt++;
return ;
}
for(int i=;i<e[x].size();i++){
edge y=e[x][i];
if(!vis[y.v]&&dis[y.v]==dis[x]+y.w){
vis[y.v]=;
pre.pb(y.v);
dfs(y.v,w+val[y.v]);
vis[y.v]=;
pre.pop_back();
}
} }
int main(){
scanf("%d %d %d %d",&n,&m,&s,&d);
rep(i,,n-)scanf("%d",&val[i]);
while(m--){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
e[a].pb(edge(b,c));
e[b].pb(edge(a,c));
}
solve();
cnt=,Max=-;
rep(i,,n)vis[i]=;
dfs(s,val[s]);
printf("%d %d\n",cnt,Max);
int len=path.size();
printf("%d ",s);
for(int i=;i<len;i++)
printf("%d%c",path[i],i==len-?'\n':' ');
return ;
}
L2-002 链表去重
假链表
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define pf push_front
// #define fi first
// #define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
const db PI=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3fLL;
const int inf=0x3f3f3f3f;//0x7fffffff;
const double eps=1e-;
const ll MOD=1e9+;
const int maxn=1e5+;
struct node{int to,k;}arr[maxn];
vector<int>lis1,lis2;
bool vis[maxn]={};
int main(){
int fi,n;
scanf("%d %d",&fi,&n);
for(int i=;i<=n;i++){
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
arr[x].k=y,arr[x].to=z;
}
for(int i=fi;i!=-;i=arr[i].to){
int x=fabs(arr[i].k);
if(vis[x])lis2.pb(i);
else {
lis1.pb(i);
vis[x]=;
}
}
for(int i=;i<lis1.size();i++){
int x=lis1[i];
if(i==lis1.size()-)printf("%.5d %d -1\n",x,arr[x].k);
else printf("%.5d %d %.5d\n",x,arr[x].k,lis1[i+]); }
for(int i=;i<lis2.size();i++){
int x=lis2[i];
if(i==lis2.size()-)printf("%.5d %d -1\n",x,arr[x].k);
else printf("%.5d %d %.5d\n",x,arr[x].k,lis2[i+]); }
return ;
}
L2-003 月饼
水
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define pf push_front
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
const db PI=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3fLL;
const int inf=0x3f3f3f3f;//0x7fffffff;
const double eps=1e-;
const ll MOD=1e9+;
const int maxn=1e3+;
struct node{double v,w,ave;}a[maxn];
bool cmp(node a,node b){return a.ave>b.ave;}
int main(){
int n,d;
scanf("%d %d",&n,&d);
rep(i,,n)scanf("%lf",&a[i].w);
rep(i,,n){
scanf("%lf",&a[i].v);
a[i].ave=a[i].v/a[i].w;
}
sort(a+,a++n,cmp);
double ans=;
for(int i=;i<=n;i++){
if(d>a[i].w)ans+=a[i].v,d-=a[i].w;
else {
ans+=a[i].ave*d;
break;
}
}
printf("%.2lf\n",ans);
return ;
}
L2-004 这是二叉搜索树吗？
题意：给你个序列，问你是不是 BST 先序遍历或镜像的结果，是的话，输出后序遍历，
这题不会做，看完题解感觉这题很巧妙；
做法：一个 BST 先序遍历的第一个点，必为根节点，然后先序遍历去找左节点，然后回来，在这个过程中所有点都比根节点小；
在遍历右节点的时候，所有节点都比根节点大；
所以可以找一个分界线，使得分界线前面的元素都比根小，分界线后面的元素都比根大，那分界线前面的元素必是左子树上的点，分界线后面的元素必然是
右子树上的点，然后递归处理左子树和右子树，最终建成了一颗树，然后回溯时 符合后序遍历的特点，先左后右，再根；
回溯的时候有个问题，就是 root和tail 相等的时候，这时候会再递归一次，return掉以后，把节点记录下来；
确实很巧妙的题；
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define pf push_front
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
const db PI=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3fLL;
const int inf=0x3f3f3f3f;//0x7fffffff;
const double eps=1e-;
const ll MOD=1e9+;
const int maxn=1e3+;
vector<int>post;
int pre[maxn];
bool ismirror;
void buildtree(int root,int tail){
int i=root+;
int j=tail;
if(!ismirror){
while(i<=tail&&pre[i]<pre[root])i++;
while(j>root&&pre[j]>=pre[root])j--;
}
else {
while(i<=tail&&pre[i]>=pre[root])i++;
while(j>root&&pre[j]<pre[root])j--;
}
if(i-j!=)return ;
buildtree(root+,j);
buildtree(i,tail);
post.pb(pre[root]);
}
int main(){
int n;
scanf("%d",&n);
rep(i,,n)scanf("%d",&pre[i]);
ismirror=false;
buildtree(,n);
if(post.size()!=n){
ismirror=true;
buildtree(,n);
}
if(post.size()!=n)printf("NO\n");
else {
printf("YES\n");
for(int i=;i<n;i++)
printf("%d%c",post[i],i==n-?'\n':' '); }
return ;
}
L2-005 集合相似度
今天才知道set也可以搞个数组；
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define pf push_front
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
const db PI=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3fLL;
const int inf=0x3f3f3f3f;//0x7fffffff;
const double eps=1e-;
const ll MOD=1e9+;
const int maxn=1e4+;
set<int>st[];
int main(){
int k,n;
scanf("%d",&n);
rep(i,,n){
int x,m;
scanf("%d",&m);
while(m--){
scanf("%d",&x);
st[i].insert(x);
}
}
scanf("%d",&k);
while(k--){
int a,b;
scanf("%d %d",&a,&b);
int tot=st[a].size()+st[b].size();
set<int>::iterator it;
int cnt=;
for(it=st[a].begin();it!=st[a].end();it++){
int x=*it;
if(st[b].find(x)!=st[b].end())cnt++;
}
double ans=cnt*1.0/(tot-cnt);
printf("%.2lf%\n",ans*);
}
return ;
}
L2-006 树的遍历
题意：给出后序遍历和中序遍历，让你求层次遍历；这题不会做，看了大神解法；
解法：二叉树遍历有这样的性质：中序遍历的序列：一个节点左边的元素一定是它左子树上的点，同理一个节点右边的元素一定是它右子树上的点；
后序遍历有这样的特点：最后一个元素，一定是根；
前序遍历有这样的特点：最前面一个元素，一定是根；
那根据这个特点，每次从 后序遍历 找出一个根，在由 中序遍历 找他的左右子树元素，递归处理就行了；
注意边界情况：当只有递归到叶节点后：ra=la，rb=lb；在递归一次，发现ra<la,或者rb<lb 处理为 return 0；
层次遍历广搜即可，这里我开始先遍历右树，后遍历左树，错了一次；应该是先遍历左树，后遍历右树；
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define pf push_front
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
const db PI=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3fLL;
const int inf=0x3f3f3f3f;//0x7fffffff;
const double eps=1e-;
const ll MOD=1e9+;
const int maxn=1e5+;
int in[],post[];
struct tree{int r,l;}trees[maxn];
int n;
int build(int la,int ra,int lb,int rb){
if(la>ra)return ;
int root=post[rb];
int p1=la;
while(in[p1]!=root)p1++;
int dis=p1-la;
trees[root].l=build(la,p1-,lb,lb+dis-);
trees[root].r=build(p1+,ra,lb+dis,rb-);
return root;
}
void bfs(){
vector<int>v;
queue<int>Q;
Q.push(post[n]);
while(!Q.empty()){
int x=Q.front();
Q.pop();
// if(x==-1)break;
v.pb(x);
if(trees[x].l!=)Q.push(trees[x].l);
if(trees[x].r!=)Q.push(trees[x].r); }
int len=v.size();
for(int i=;i<len;i++){
printf("%d%c",v[i],i==len-?'\n':' ');
}
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&post[i]);
for(int i=;i<=n;i++)scanf("%d",&in[i]);
build(,n,,n);
bfs();
// system("pause");
return ;
}
L2-008 最长对称子串
暴力即可，注意 对称子串可以是奇数，也可以是偶数，两层枚举即可；
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
getline(cin,s);
int maxlen=;
int len=s.size();
for(int i=;i<len;i++){
int cnt=;
while(i+cnt<len&&i-cnt>=&&s[i+cnt]==s[i-cnt])cnt++;
cnt--;
if(cnt*+>maxlen)maxlen=cnt*+;
}
for(int i=;i<len;i++){
int cnt=;
while(i+cnt+<len&&i-cnt>=&&s[i+cnt+]==s[i-cnt])cnt++;
// cnt--;
if(cnt*>maxlen)maxlen=cnt*;
}
printf("%d\n",maxlen);
// system("pause");
return ;
}
L2-009 抢红包
水
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define pf push_front
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
const db PI=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3fLL;
const int inf=0x3f3f3f3f;//0x7fffffff;
const double eps=1e-;
const ll MOD=1e9+;
const int maxn=1e4+;
struct node{int cnt,id,tot;}a[maxn];
bool cmp(node a,node b){
if(a.tot!=b.tot)return a.tot>b.tot;
else if(a.cnt!=b.cnt)return a.cnt>b.cnt;
else return a.id<b.id;
}
int n;
void init(){
for(int i=;i<=n;i++){
a[i].tot=a[i].cnt=,a[i].id=i;
}
}
int main(){
scanf("%d",&n);
init();
for(int i=;i<=n;i++){
int k;
int cnt=;
scanf("%d",&k);
while(k--){
int x,y;
scanf("%d %d",&x,&y);
a[x].tot+=y;
a[x].cnt++;
cnt+=y;
}
a[i].tot-=cnt;
} sort(a+,a++n,cmp);
for(int i=;i<=n;i++){
printf("%d %.2lf\n",a[i].id,a[i].tot*1.0/);
} return ; }
L2-010 排座位
这题和帮派问题的带权并查集不一样，
帮派问题：敌人的敌人是朋友，朋友的敌人是敌人，敌人的朋友是敌人；
食物链那个题：如果同被一类生物吃，或者同吃一类生物，那么他们是同类；
这是带权并查集，有明显的对立关系，
但这个题，敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人，敌人的朋友也不一定是敌人；
所以不用带权并查集，朋友关系是共享的，用并查集关系解决，敌对关系不是共享的，用map数组处理；
因为题目说明了 只有直接的敌对关系才算敌对，而朋友关系是可以共享的；
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define pf push_front
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
const db PI=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3fLL;
const int inf=0x3f3f3f3f;//0x7fffffff;
const double eps=1e-;
const ll MOD=1e9+;
const int maxn=1e4+;
int fa[],MP[][];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void build(int x,int y){int dx=find(x),dy=find(y);if(dx!=dy)fa[dx]=dy;}
int main(){ int n,k,m;
scanf("%d %d %d",&n,&m,&k);
// init();
for(int i=;i<=*n;i++)fa[i]=i;
while(m--){
int x,y,op;
scanf("%d %d %d",&x,&y,&op);
if(op==)build(x,y);
else if(op==-)MP[x][y]=MP[y][x]=-;
}
while(k--){
int x,y;
scanf("%d %d",&x,&y);
bool isfriend=,isenemy=;
if(find(x)==find(y))isfriend=;
if( MP[x][y]==-)isenemy=;
if(isfriend&&!isenemy)
cout<<"No problem"<<endl;
else if(!isfriend&&!isenemy)
cout<<"OK"<<endl;
else if(isfriend&&isenemy)
cout<<"OK but..."<<endl;
else if(!isfriend&&isenemy)
cout<<"No way"<<endl; }
return ;
}
L2-011 玩转二叉树
这个是前面一个题的变化版
就是给你前序和中序，让你求镜像的层次遍历；
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int pre[],in[];
struct tree{int r,l;}trees[];
int buildtree(int la,int ra,int lb,int rb){
//la 前序，lb 后序
if(la>ra)return ;
int root=pre[la];
int p1=lb;
while(in[p1]!=root)p1++;
int dis=p1-lb;
trees[root].l=buildtree(la+,la+dis,lb,p1-);
trees[root].r=buildtree(la+dis+,ra,p1+,rb);
return root;
}
void bfs(){
vector<int>v;
queue<int>Q;
Q.push(pre[]);
while(!Q.empty()){
int x=Q.front();
Q.pop();
v.pb(x);
if(trees[x].r!=)Q.push(trees[x].r);
if(trees[x].l!=)Q.push(trees[x].l);
}
int len=v.size();
for(int i=;i<len;i++){
printf("%d%c",v[i],i==len-?'\n':' ');
}
}
int main(){ int n;
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&in[i]);
for(int i=;i<=n;i++)scanf("%d",&pre[i]);
buildtree(,n,,n);
bfs();
return ;
}
L2-012 关于堆的判断 ；
这题有这样几个知识点：
堆就是一个完全二叉树，且每个根节点都满足最大或者最小，
建立堆：边读取边调整，每次从下往上调整父节点，最后一定是一个正确的堆，复杂度O（nlog（n））；
判断父结点，子节点，什么的，除2就行了；
但这题截取字符串比较麻烦；
我用流处理的；方便一些；
#include<bits/stdc++.h>
using namespace std;
int trees[];
void adjust(int x){
if(x==)return ;
if(trees[x]<trees[x/]){
swap(trees[x],trees[x/]);
adjust(x/);
}
}
bool judge1(int a,int b){
int p1=,p2=;
while(trees[p1]!=a)p1++;
while(trees[p2]!=b)p2++;
if(p1/!=p2/)return ;
return ;
}
bool judge2(int a,int b){
int p1=,p2=;
while(trees[p1]!=a)p1++;
while(trees[p2]!=b)p2++;
if(p2/!=p1)return ;
return ;
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d",&trees[i]);
if(i!=)adjust(i);
}
while(m--){
int a,b;
string op;
scanf("%d ",&a);
getline(cin,op);
int len=op.size();
if(op[]=='i'&&op[len-]=='t'){
if(trees[]!=a)printf("F\n");
else printf("T\n");
}
else if(op[]=='a'){
istringstream in(op);
string tmp;
in>>tmp>>b>>tmp>>tmp;
if(judge1(a,b))printf("T\n");
else printf("F\n");
}
else if(op[]=='i'&&op[]=='t'){
istringstream in(op);
string tmp;
in>>tmp>>tmp>>tmp>>tmp>>b;
if(judge2(a,b))printf("T\n");
else printf("F\n");
}
else {
istringstream in(op);
string tmp;
in>>tmp>>tmp>>tmp>>tmp>>b;
if(judge2(b,a))printf("T\n");
else printf("F\n");
}
} return ;
}
L2-013 红色警报
这个题折腾了好久；
题意：给你一张连通图，每次删除一个点，问你这个点是不是桥；
做法：本来想用邻接表存图，但你用vector 确实不好删除元素呀，而且每次把他的邻居踢掉，还要把以他为邻居的点踢掉，
这个复杂度就不对了，所以存图的结构看情况而定，
邻接矩阵能很好的描述两两的 邻接关系 ，但邻接表就比较麻烦，要遍历整个vector；
每次踢掉一个点，统计这张图的联通分量，做个判断即可，
然后这里我没有递归处理邻居的邻居，邻居的邻居不还是邻居吗？
我傻傻的不知道递归处理；
但这个题，复杂度真的很高呀；算的复杂度是 1e8 居然过了，真是神奇；
#include<bits/stdc++.h>
using namespace std;
int gp[][];
bool vis[];
int n,m,k;
void dfs(int x){
vis[x]=;
for(int i=;i<n;i++){
if(!vis[i]&&gp[x][i]==)dfs(i);
}
}
int countcnt(){
memset(vis,,sizeof(vis));
int cnt=;
for(int i=;i<n;i++){
if(!vis[i]){
cnt++;
dfs(i);
}
}
return cnt;
}
int main(){ memset(gp,,sizeof gp);
scanf("%d %d",&n,&m);
while(m--){
int a,b;
scanf("%d %d",&a,&b);
gp[a][b]=gp[b][a]=; } scanf("%d",&k);
int cnt=countcnt();
for(int i=;i<=k;i++){
int x;
scanf("%d",&x);
for(int j=;j<n;j++){
if(gp[x][j]==||gp[j][x]==)gp[x][j]=gp[j][x]=;
}
int tmpcnt=countcnt();
if(tmpcnt>cnt+)printf("Red Alert: City %d is lost!\n",x);
else printf("City %d is lost.\n",x);
if(i==n)printf("Game Over.\n");
cnt=tmpcnt;
}
return ;
}
L2-014 列车调度；
最开始想的暴力，然后时间复杂度肯定是不对；
傻傻的还想着优先队列，看不到这是个递增的数列吗？
每次选取刚好大于num的数，然后替换掉，咋不知道二分？
STL的三种二分（都是已经排好序的）：
binary_search 二分查找一个 左闭右开的区间，有这个元素返回1，否则0；
lower_bound 二分查找一个 左闭右开的区间 返回值大于或者等于的 最小的 迭代器; 找不到就是 end
upper_bound 二分查找一个 左闭右开的区间 返回值大于该值的 最大的 迭代器 找不到就是 end
以上是从小到大的顺序；
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn=1e5+;
int a[maxn];
int main(){
int n;
scanf("%d",&n);
vector<int>v;
vector<int>::iterator it;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
it=upper_bound(v.begin(),v.end(),a[i]);
if(it!=v.end()) *it=a[i];
else v.pb(a[i]);
}
printf("%d\n",v.size());
return ;
}
L2-015 互评成绩
set里是双向迭代器，不能说 it+1
这题就是：你用mulitset是不能直接访问最大值的，要转换一下；每次it++；看看能不能访问end如果是，就退出；
否则回退；
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn=1e5+;
bool cmp(double a,double b){return a<b;}
int main(){
vector<double>v;
int n,k,m;
scanf("%d %d %d",&n,&k,&m);
for(int i=;i<=n;i++){
multiset<int>st;
int x;
for(int j=;j<=k;j++){
scanf("%d",&x);
st.insert(x);
}
set<int>::iterator it;
double sum=;
for(it=st.begin();it!=st.end();it++){
if(it==st.begin())continue;
it++;
if(it==st.end()){
break;
}
else it--;
sum+=*it;
}
sum/=k-;
v.pb(sum);
}
sort(v.begin(),v.end(),cmp);
for(int i=n-m;i<n;i++){
printf("%.3lf%c",v[i],i==n-?'\n':' ');
} return ; }
L2-016 愿天下有情人都是失散多年的兄妹
感觉自己还是太懒了，堕于思考。
题意：让你判断两个人能不能结婚；但数据会卡你，有的人并没有给出性别这种情况；
你如果用bool 标记，那默认值是0，即为默认男性，那就不对了，所以用字符数组标记；
做法，对于一对男女，搜索五代，看看是不是同父或者同母；
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
int fa[maxn],mo[maxn];
char sex[maxn];
bool ok(int x,int y,int cnt){
if(cnt>=)return ;
if(x==-||y==-)return ;
if(fa[x]!=-&&fa[y]!=-&&fa[x]==fa[y])
return ;
if(mo[x]!=-&&mo[y]!=-&&mo[x]==mo[y])
return ;
cnt++;
return ok(fa[x],mo[y],cnt)&&ok(fa[y],mo[x],cnt)&&ok(fa[x],fa[y],cnt)&&ok(mo[x],mo[y],cnt);
}
int main(){ for(int i=;i<maxn;i++)fa[i]=mo[i]=-;
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
int x,f,m;
char op;
scanf("%d %c %d %d",&x,&op,&f,&m);
sex[x]=op;
fa[x]=f;
mo[x]=m;
if(f!=-)sex[f]='M';
if(m!=-)sex[m]='F';
}
int m;
scanf("%d",&m);
while(m--){
int x,y;
scanf("%d %d",&x,&y);
int cnt =;
if(sex[x]==sex[y])printf("Never Mind\n");
else if(ok(x,y,cnt))printf("Yes\n");
else printf("No\n");
}
return ;
}
L2-017 人以群分
把输入文件搞错了，瞎改了半天bug
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
const int maxn=1e5+;
ll a[maxn];
int main(){
int n;
scanf("%d",&n);
// cout<<n<<endl;
// rep(i,1,n)scanf("%lld",&a[i]);
for(int i=;i<=n;i++)scanf("%lld",&a[i]);
// cout<<"test :"<<endl;
// for(int i=1;i<=n;i++)cout<<a[i]<<endl;
// cout<<"test "<<endl;
sort(a+,a++n);
if(n%==){
ll sum1=,sum2=;
rep(i,,n/)sum1+=a[i];
rep(i,n/+,n)sum2+=a[i];
// cout<<"test :"<<sum1<<" "<<sum2<<endl;
printf("Outgoing #: %d\n",n/+);
printf("Introverted #: %d\n",n/);
printf("Diff = %lld\n",sum2-sum1+a[n/+]);
}
else {
ll sum1=,sum2=;
rep(i,,n/)sum1+=a[i];
rep(i,n/+,n)sum2+=a[i];
// cout<<"test :"<<sum1<<" "<<sum2<<endl;
printf("Outgoing #: %d\n",n/);
printf("Introverted #: %d\n",n/);
printf("Diff = %lld\n",sum2-sum1); }
return ;
}
L2-019 悄悄关注
搞个string类的set就可以过了
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
typedef long long ll;
typedef long double ldb;
const int maxn=1e5+;
struct peo{string name;ldb cnt;}man[maxn];
int main(){
int n;
scanf("%d",&n);
set<string>st,List;
rep(i,,n){
string tmp;
// cin>>List[i].name;
cin>>tmp;
List.insert(tmp);
}
int m;
scanf("%d",&m);
ldb sum=; rep(i,,m){
cin>>man[i].name>>man[i].cnt;
sum+=man[i].cnt;
}
sum/=m;
rep(i,,m){ if(man[i].cnt>sum&&List.find(man[i].name)==List.end())st.insert(man[i].name);
}
set<string>::iterator it;
for(it=st.begin();it!=st.end();it++){
cout<<*it<<endl;
}
if(st.empty())cout<<"Bing Mei You"<<endl;
return ;
}
L2-020 功夫传人
这个题就是遍历图，深搜可以解决；
就是 printf("%.0llf",ans); 这个式子是会四舍五入的；
你只能转为 longlong
这里 long double
读取：scanf("%Lf",&x);
打出：printf("%Lf",x);
下次让打出整数记得 转为 int
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define pb push_back
typedef double db;
typedef long double ldb;
typedef long long ll;
int n;
ldb r,rootpow,ans;
const int maxn=1e5+;
vector<int>v[maxn];
int big[maxn];
void dfs(int x,ldb frontpow){
if(big[x]!=&&v[x].empty()){
ans+=frontpow*big[x];
return;
}
for(int i=;i<v[x].size();i++){
dfs(v[x][i],frontpow*r);
}
}
int main(){
memset(big,,sizeof big);
scanf("%d %Lf %Lf",&n,&rootpow,&r);
r=-r*1.0/;
rep(i,,n-){
int k;
scanf("%d",&k);
if(k==){
scanf("%d",&big[i]);
}
while(k--){
int x;
scanf("%d",&x);
v[i].pb(x);
}
} ans=;
dfs(,rootpow);
printf("%lld\n",(ll)ans);
return ;
}
L2-021 点赞狂魔
没啥意思；
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define pb push_back
typedef long long ll;
typedef long double ldb;
const int maxn=1e5+;
struct node{string name;int cnt,k;};
vector<node>v;
bool cmp(node a,node b){
if(a.cnt!=b.cnt)
return a.cnt>b.cnt;
else return a.k<b.k;
}
int main(){
int n;
cin>>n;
node tmp;
rep(i,,n){
// tmp.cnt=0;
cin>>tmp.name>>tmp.k;
// cin>>a[i].name;
set<int>st;
int x;
// scanf("%d",&tmp.k);
rep(j,,tmp.k){
scanf("%d",&x);
st.insert(x);
}
tmp.cnt=st.size();
v.pb(tmp);
}
sort(v.begin(),v.end(),cmp);
tmp.name="-";
rep(i,,)v.pb(tmp);
// for(int i=0;i<v.size();i++)
// cout<<v[i].name<<" "<<v[i].cnt<<endl;
rep(i,,){
cout<<v[i].name;
if(i!=)cout<<" ";
}
cout<<endl;
return ; }
L2-023 图着色问题
没看懂题意就急着写，瞎改bug半天；
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(int )j;i<=(int)k;i++)
const int maxn=;
#define pb push_back
struct edge{int u,v;edge(int x,int y){u=x,v=y;}};
vector<edge>e;
int color[maxn];
int V,E,K;
bool ok(){
for(int i=;i<e.size();i++){
if(color[e[i].u]==color[e[i].v])return ;
}
return ;
}
int main(){ int n,x,y;
scanf("%d %d %d",&V,&E,&K);
rep(i,,E){
scanf("%d %d",&x,&y);
e.pb(edge(x,y));
}
scanf("%d",&n);
rep(k,,n){
set<int>st;
int flag=;
rep(i,,V){
scanf("%d",&color[i]);
if(color[i]>V||color[i]<=)flag=;
st.insert(color[i]);
}
if(st.size()!=K||!flag)printf("No\n");
else if(ok())printf("Yes\n");
else printf("No\n"); }
return ;
}