2021-4-2 【PTA】【天梯赛】

每日三百行代码 第二十八天

#include<bits/stdc++.h>
using namespace std;
const int maxn=510;
// int g[maxn][maxn];
vector<int> tu[maxn];
int main(){
   
    int v,e,k;
    cin>>v>>e>>k;
    for(int i=0;i<e;i++){
   
        int x,y;
        cin>>x>>y;
        // g[x][y]=g[y][x]=1; 并没有什么卵用
        tu[x].push_back(y);tu[y].push_back(x);
    }
    int m;cin>>m;
    for(int i=0;i<m;i++){
   
        vector<int> color(v+1);
        set<int> s;
        for(int j=1;j<=v;j++){
   
            cin>>color[j];s.insert(color[j]);
        }
        if(s.size()!=k) printf("No\n");
        else{
   
            bool flag=true;
            for(int j=1;j<=v;j++){
   
                for(int x=0;x<tu[j].size();x++){
   
                    if(color[j]==color[tu[j][x]]){
   
                        flag=false;break;
                    }
                }
            }
            if(flag) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
 
}

L2-024 部落 (25 分)

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
int arr[maxn];
int father[maxn];
int find(int x){
   
	if(x == father[x]) return x;
	else{
   
		int tmp = find(father[x]);
		father[x] = tmp;
		return tmp;
	}
}
void join(int x, int y){
   
	int fx = find(x), fy = find(y);
	if(fx != fy)
		father[fy] = fx;
} 
int main(){
   
	int n,k;
	set<int> st_total,st_group;
	cin>>n;
	for(int i=1;i<=maxn;i++){
   
		father[i]=i;
	}
	for(int i=1;i<=n;i++){
   
		cin>>k;
		for(int j=0;j<k;j++){
   
			cin>>arr[j];
			st_total.insert(arr[j]);
			if(j) join(arr[j-1], arr[j]); //j不为零的时候，合并两个元素 
		}
	}
	for(int i=1;i<=st_total.size();i++){
   
		st_group.insert(find(i));
	}
	cout<<st_total.size()<<" "<<st_group.size()<<endl;
	int m,u,v;
	cin>>m;
	for(int i=0;i<m;i++){
   
		cin>>u>>v;
		if(find(u)==find(v)) cout<<"Y"<<endl;
		else cout<<"N"<<endl;
	}
	
	return 0;
} 

L2-025 分而治之 (25 分)

#include <bits/stdc++.h>
#define mst(a, n) memset(a, n, sizeof(a))
using namespace std;
const int N = 1e4 + 10;
const int M = 55;
const int INF = 1e6 + 10;
const double eps = 0.05;
typedef long long ll;

int n, m, k;
int x, y;
vector<int> v[N];
int cnt[N];
int c[N];

int solve()
{
   
	for (int i = 1; i <= n; i++)
	{
   
		if (c[i] > 0)
		{
   
			return 0;
		}
	}
	return 1;
}

int main()
{
   
	cin >> n >> m;
	while (m--)
	{
   
		scanf ("%d%d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
		cnt[x]++;
		cnt[y]++;
	}
	cin >> k;
	while (k--)
	{
   
		scanf ("%d", &x);
		for (int i = 1; i <= n; i++)
		{
   
			c[i] = cnt[i];
		}
		while (x--)
		{
   
			scanf ("%d", &y);
			c[y] = 0;
			int siz = v[y].size();
			for (int i = 0; i < siz; i++)
			{
   
				c[v[y][i]]--;
			}
		}
		if (!solve())
		{
   
			cout << "NO\n";
		}
		else
		{
   
			cout << "YES\n";
		}
	}
	return 0;
} 

L2-026 小字辈 (25 分)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<vector<int>>man;
vector<int>small;
int sign;
int result = 0;
void dfs(int j,int cnt) {
   
	if (result < cnt&&man[j].size() == 0) {
   
		result = cnt;
		small.clear();		//因为找到了比当前更深的，所以要清空之前的数据.
	}
	if (result == cnt)
		small.push_back(j);
	for (int i = 0; i < man[j].size(); i++) {
   
		dfs(man[j][i],cnt+1);
	}
}
int main() {
   
	int num;
	cin >> num;
	man.resize(num+1);
	for (int i = 1; i <= num; i++) {
   
		int tmep;
		cin >> tmep;
		if (tmep == -1) {
   
			sign = i;
			continue;
		}
		man[tmep].push_back(i);
	}
	dfs(sign, 1);
	cout << result << endl;
	sort(small.begin(), small.end());
	for (int i = 0; i < small.size(); i++) {
   
		if (i != 0)
			cout << " ";
		cout << small[i];
	}
	system("pause");
}

L2-027 名人堂与代金券 (25 分)

#include<bits/stdc++.h>
using namespace std;
struct Node{
   
	string id;
	int score;
	int rank;
};
bool cmp(Node a,Node b){
   
	if(a.score==b.score){
   
		return a.id<b.id;
	}
	return a.score>b.score;
}
int main() {
   
    int n,g,k;
    cin>>n>>g>>k;
    Node a[n];
    int sum=0;
    for(int i=0;i<n;i++){
   
    	cin>>a[i].id>>a[i].score;
    	if(a[i].score>=g){
   
    		sum+=50;
		}
		else if(a[i].score>=60){
   
			sum+=20;
		}
	}
	sort(a,a+n,cmp);
	cout<<sum<<endl;
	int rank=1;
	a[0].rank=1;//先将第一名的rank设为1
	int count=1;
	for(int i=1;i<n;i++){
   //从第二名开始循环
		if(a[i].score!=a[i-1].score){
   //如果目前的人的分数不等于前面那个人的分数（排好序了，就是小于）
			a[i].rank=a[i-1].rank+count;//下一个人的排名加上count，count为前面成绩相等的人数
			count=1;//再将count置为1
		}
		else{
   //如果等于，那么这个人的排名和上一个人是一样的，记录count
			a[i].rank=a[i-1].rank;
			count++;
		}
		
	}
	for(int i=0;a[i].rank<=k;i++){
   
		cout<<a[i].rank<<" "<<a[i].id<<" "<<a[i].score<<endl;
	}
    return 0;
	
}

#include<bits/stdc++.h>
using namespace std;//18:58
int n,g,k,sum;
struct VV
{
   
    char name[200];
    int score;
}v[20000];
bool cmp(VV a,VV b)
{
   
    if(a.score==b.score)
        return strcmp(a.name,b.name)<0;
    return a.score>b.score;
}
int main()
{
   
    cin>>n>>g>>k;
    int x;
    for(int i = 1;i<=n;i++)
    {
   
        cin>>v[i].name>>v[i].score;
        x = v[i].score;
        if(x>=60&&x<g)
            sum+=20;
        else if(x>=g&&x<=100)
            sum+=50;
    }
    sort(v+1,v+n+1,cmp);
    cout<<sum<<endl;
    int t = 1,p = 1;
    cout<<t<<" "<<v[1].name<<" "<<v[1].score<<endl;
    for(int i = 2;i<=n;i++)
    {
   
        if(v[i].score<v[i-1].score)
        {
   
            t+=p;
            p = 1;
        }
        else p++;
        if(t<=k)
            cout<<t<<" "<<v[i].name<<" "<<v[i].score<<endl;
        else break;
    }
}