GPLT – 第2页 – 柳婼の blog

L2-025 分而治之-PAT团体程序设计天梯赛GPLT

分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。

输入格式：
输入在第一行给出两个正整数 N 和 M（均不超过10 000），分别为敌方城市个数（于是默认城市从 1 到 N 编号）和连接两城市的通路条数。随后 M 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 K （<= 100）和随后的 K 行方案，每行按以下格式给出：
Np v[1] v[2] … v[Np]
其中 Np 是该方案中计划攻下的城市数量，后面的系列 v[i] 是计划攻下的城市编号。

输出格式：
对每一套方案，如果可行就输出“YES”，否则输出“NO”。

输入样例：
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 10
2 4
5
4 10 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2

输出样例：
NO
YES
YES
NO
NO

分析：存图用邻接表存，aa数组表示此城有兄弟城市（即有多少城市与之连接），a组为每次攻城后的次城有多少兄弟城，aa作为原始连接情况，不变，每次用的时候，复制到a上即可。每攻下一座城，次城兄弟成变成0，其兄弟城的兄弟城减少一个。最后检查，如果所有城市的兄弟城都小于零，则输出YES，否则输出NO。

#include <iostream>
#include <vector>
using namespace std;
int n, m, k, aa[10010] = {0}, a[10010];
void check() {
    for(int i = 1; i <= n; i++) {
        if(a[i] > 0) {
            cout << "NO\n";
            return ;
        }
    }
    cout << "YES\n";
    return ;
}
int main(){
    cin >> n >> m;
    vector<vector<int>> v(n+1);
    while(m--) {
        int c1, c2;
        cin >> c1 >> c2;
        aa[c1]++;
        aa[c2]++;
        v[c1].push_back(c2);
        v[c2].push_back(c1);
    }
    cin >> k;
    while(k--) {
        int cnt, num;
        cin >> cnt;
        for(int i = 1; i <= n; i++)
            a[i] = aa[i];
        for(int i = 0; i < cnt; i++) {
            cin >> num;
            a[num] = 0;
            for(int j = 0; j < v[num].size(); j++)
                a[v[num][j]]--;
        }
        check();
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int n, m, k, aa[10010] = {0}, a[10010];

void check() {

for(int i = 1; i <= n; i++) {

if(a[i] > 0) {

cout << "NO\n";

return ;

}

cout << "YES\n";

return ;

}

int main(){

cin >> n >> m;

vector<vector<int>> v(n+1);

while(m--) {

int c1, c2;

cin >> c1 >> c2;

aa[c1]++;

aa[c2]++;

v[c1].push_back(c2);

v[c2].push_back(c1);

}

cin >> k;

while(k--) {

int cnt, num;

cin >> cnt;

for(int i = 1; i <= n; i++)

a[i] = aa[i];

for(int i = 0; i < cnt; i++) {

cin >> num;

a[num] = 0;

for(int j = 0; j < v[num].size(); j++)

a[v[num][j]]--;

}

check();

}

return 0;

}

L2-023 图着色问题-PAT团体程序设计天梯赛GPLT

图着色问题是一个著名的NP完全问题。给定无向图 G = (V, E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？

但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。

输入格式：

输入在第一行给出3个整数V（0 < V <= 500）、E（>= 0）和K（0 < K <= V），分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1到V编号。随后E行，每行给出一条边的两个端点的编号。在图的信息给出之后，给出了一个正整数N（<= 20），是待检查的颜色分配方案的个数。随后N行，每行顺次给出V个顶点的颜色（第i个数字表示第i个顶点的颜色），数字间以空格分隔。题目保证给定的无向图是合法的（即不存在自回路和重边）。

输出格式：

对每种颜色分配方案，如果是图着色问题的一个解则输出“Yes”，否则输出“No”，每句占一行。

输入样例：
6 8 3
2 1
1 3
4 6
2 5
2 4
5 4
5 6
3 6
4
1 2 3 3 1 2
4 5 6 6 4 5
1 2 3 4 5 6
2 3 4 2 3 4

输出样例：
Yes
Yes
No
No

分析：给出无向图，和颜色的数量k，求是否给出的颜色数量==k，并且任意两个点之间颜色都不同。
依次判断每一个点是否和周围的点颜色相同，出现一次，就立刻得出结果“No”，如果一次都没出现，结果为“Yes”。
判断给出的颜色个数的时候用set方便（本题数据规模不大，不会对运行时间影响太大）。

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int n, m, k, num;
vector<vector<int>> v(510);
vector<int> color(510);
bool f(int i) {
    for(int j = 0; j < v[i].size(); j++)
        if(color[i] == color[v[i][j]])
            return false;
    return true;
}
int main() {
    cin >> n >> m >> k;
    for(int i = 0; i < m; i++) {
        int t1, t2;
        cin >> t1 >> t2;
        v[t1].push_back(t2);
        v[t2].push_back(t1);
    }
    cin >> num;
    while(num--) {
        int flag = 0;
        set<int> s;
        for(int i = 1; i <= n; i++) {
            cin >> color[i];
            s.insert(color[i]);
        }
        if(s.size() != k ) {
            flag = 1;
            cout << "No\n";
        }else {
            for(int i = 1; i <= n; i++) {
                if(f(i) == false) {
                    cout << "No\n";
                    flag = 1;
                    break;
                }
            }
        }
        if(flag == 0)  cout << "Yes\n";
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <set>

using namespace std;

int n, m, k, num;

vector<vector<int>> v(510);

vector<int> color(510);

bool f(int i) {

for(int j = 0; j < v[i].size(); j++)

if(color[i] == color[v[i][j]])

return false;

return true;

}

int main() {

cin >> n >> m >> k;

for(int i = 0; i < m; i++) {

int t1, t2;

cin >> t1 >> t2;

v[t1].push_back(t2);

v[t2].push_back(t1);

}

cin >> num;

while(num--) {

int flag = 0;

set<int> s;

for(int i = 1; i <= n; i++) {

cin >> color[i];

s.insert(color[i]);

}

if(s.size() != k ) {

flag = 1;

cout << "No\n";

}else {

for(int i = 1; i <= n; i++) {

if(f(i) == false) {

cout << "No\n";

flag = 1;

break;

}

if(flag == 0) cout << "Yes\n";

}

return 0;

}

L2-021 点赞狂魔-PAT团体程序设计天梯赛GPLT

微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。然而有这么一种人，他们会通过给自己看到的一切内容点赞来狂刷存在感，这种人就被称为“点赞狂魔”。他们点赞的标签非常分散，无法体现出明显的特性。本题就要求你写个程序，通过统计每个人点赞的不同标签的数量，找出前3名点赞狂魔。

输入格式：
输入在第一行给出一个正整数N（<=100），是待统计的用户数。随后N行，每行列出一位用户的点赞标签。格式为“Name K F~1~ … F~K~”，其中 Name 是不超过8个英文小写字母的非空用户名，1<=K<=1000，F~i~（i=1, …, K）是特性标签的编号，我们将所有特性标签从1到10^7^编号。数字间以空格分隔。

输出格式：
统计每个人点赞的不同标签的数量，找出数量最大的前3名，在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列，则输出标签出现次数平均值最小的那个，题目保证这样的用户没有并列。若不足3人，则用“-”补齐缺失，例如“mike jenny -”就表示只有2人。

输入样例：
5
bob 11 101 102 103 104 105 106 107 108 108 107 107
peter 8 1 2 3 4 3 2 5 1
chris 12 1 2 3 4 5 6 7 8 9 1 2 3
john 10 8 7 6 5 4 3 2 1 7 5
jack 9 6 7 8 9 10 11 12 13 14

输出样例：
jack chris john

分析：用一个a数字标记某个标签是否访问过，统计每个人点赞的标签数，用部分排序或者优先队列，最后输出结果。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
struct stu{
    string name;
    int sum, cnt;
};
bool cmp(stu a, stu b){
    if(a.cnt != b.cnt)  return a.cnt > b.cnt;
    return 1.0 * a.sum / a.cnt < 1.0 * b.sum / b.cnt;
}
bool a[10000010];
int main() {
    int n;
    cin >> n;
    vector<stu> ans(n);
    for(int i = 0; i < n; i++) {
        memset(a, false, sizeof(a));
        int m, t, cnt = 0;
        string name;
        cin >> name >> m;
        for(int j = 0; j < m; j++) {
            cin >> t;
            if(a[t] == false) {
                a[t] = true;
                cnt++;
            }
        }
        ans[i] = {name, m, cnt};
    }
    int nn = min(n, 3);
    partial_sort(ans.begin(),ans.begin() + nn, ans.end(), cmp);
    for(int i = 0; i < nn; i++) {
        if(i != 0) cout << " ";
             cout << ans[i].name;
    }
    for(int i = 0; i < 3 - n; i++)
        cout << " " <<  "-";
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <cstring>

using namespace std;

struct stu{

string name;

int sum, cnt;

};

bool cmp(stu a, stu b){

if(a.cnt != b.cnt) return a.cnt > b.cnt;

return 1.0 * a.sum / a.cnt < 1.0 * b.sum / b.cnt;

}

bool a[10000010];

int main() {

int n;

cin >> n;

vector<stu> ans(n);

for(int i = 0; i < n; i++) {

memset(a, false, sizeof(a));

int m, t, cnt = 0;

string name;

cin >> name >> m;

for(int j = 0; j < m; j++) {

cin >> t;

if(a[t] == false) {

a[t] = true;

cnt++;

}

ans[i] = {name, m, cnt};

}

int nn = min(n, 3);

partial_sort(ans.begin(),ans.begin() + nn, ans.end(), cmp);

for(int i = 0; i < nn; i++) {

if(i != 0) cout << " ";

cout << ans[i].name;

}

for(int i = 0; i < 3 - n; i++)

cout << " " << "-";

return 0;

}

L1-056 猜数字-PAT团体程序设计天梯赛GPLT

一群人坐在一起，每人猜一个 100 以内的数，谁的数字最接近大家平均数的一半就赢。本题就要求你找出其中的赢家。

输入格式：
输入在第一行给出一个正整数N（<= 10^4^）。随后 N 行，每行给出一个玩家的名字（由不超过8个英文字母组成的字符串）和其猜的正整数（<= 100）。

输出格式：
在一行中顺序输出：大家平均数的一半（只输出整数部分）、赢家的名字，其间以空格分隔。题目保证赢家是唯一的。

输入样例：
7
Bob 35
Amy 28
James 98
Alice 11
Jack 45
Smith 33
Chris 62

输出样例：
22 Amy

分析：用猜数做下表，用名字做数组中的数据，遍历数组，找出最接近平均值的一半的下标。输出平均值的一半，和对应下标存的名字即可。题目保证赢家唯一，所以，只有一个人猜到的最终结果。即使出现多个人猜一个数，对应下标存的名字会被覆盖也没关系，反正他们都不是最终答案

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n, t, sum = 0, mindet = 1000, minid;
    string name, a[110];
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> name >> t;
        a[t] = name;
        sum += t;
    }
    double avg = 0.5 * sum / n;
    for(int i = 0; i <= 100; i++)
        if(a[i] != "" && abs(avg - i) < mindet) {
            minid = i;
            mindet = abs(avg - i);
        }
    cout << (int)avg << " " <<  a[minid];
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n, t, sum = 0, mindet = 1000, minid;

string name, a[110];

cin >> n;

for(int i = 0; i < n; i++) {

cin >> name >> t;

a[t] = name;

sum += t;

}

double avg = 0.5 * sum / n;

for(int i = 0; i <= 100; i++)

if(a[i] != "" && abs(avg - i) < mindet) {

minid = i;

mindet = abs(avg - i);

}

cout << (int)avg << " " << a[minid];

return 0;

}

L1-055 谁是赢家-PAT团体程序设计天梯赛GPLT

某电视台的娱乐节目有个表演评审环节，每次安排两位艺人表演，他们的胜负由观众投票和3名评委投票两部分共同决定。规则为：如果一位艺人的观众票数高，且得到至少1名评委的认可，该艺人就胜出；或艺人的观众票数低，但得到全部评委的认可，也可以胜出。节目保证投票的观众人数为奇数，所以不存在平票的情况。本题就请你用程序判断谁是赢家。

输入格式：
输入第一行给出 2 个不超过 1000 的正整数 Pa 和 Pb，分别是艺人 a 和艺人 b 得到的观众票数。题目保证这两个数字不相等。随后第二行给出 3 名评委的投票结果。数字 0 代表投票给 a，数字 1 代表投票给 b，其间以一个空格分隔。

输出格式：
按以下格式输出赢家：
The winner is x: P1 + P2
其中 x 是代表赢家的字母，P1 是赢家得到的观众票数，P2 是赢家得到的评委票数。

输入样例：
327 129
1 0 1

输出样例：
The winner is a: 327 + 1

#include <iostream>
using namespace std;
int main() {
    int votea, voteb, adj1, adj2, adj3, suma; 
    cin >> votea >> voteb >> adj1 >> adj2 >> adj3;
    suma=  3 - (adj1 + adj2 + adj3);
    if(suma == 3 || (suma >= 1 && votea > voteb))
      printf("The winner is a: %d + %d", votea, suma);
    else
      printf("The winner is b: %d + %d", voteb, 3-suma);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int votea, voteb, adj1, adj2, adj3, suma;

cin >> votea >> voteb >> adj1 >> adj2 >> adj3;

suma= 3 - (adj1 + adj2 + adj3);

if(suma == 3 || (suma >= 1 && votea > voteb))

printf("The winner is a: %d + %d", votea, suma);

else

printf("The winner is b: %d + %d", voteb, 3-suma);

return 0;

}

L1-054 福到了-PAT团体程序设计天梯赛GPLT

“福”字倒着贴，寓意“福到”。不论到底算不算民俗，本题且请你编写程序，把各种汉字倒过来输出。这里要处理的每个汉字是由一个 N x N 的网格组成的，网格中的元素或者为字符“@”或者为空格。而倒过来的汉字所用的字符由裁判指定。

输入格式：

输入在第一行中给出倒过来的汉字所用的字符、以及网格的规模 N （不超过100的正整数），其间以 1 个空格分隔；随后 N 行，每行给出 N 个字符，或者为“@”或者为空格。

输出格式：

输出倒置的网格，如样例所示。但是，如果这个字正过来倒过去是一样的，就先输出“bu yong dao le”，然后再用输入指定的字符将其输出。

输入样例 1：
$ 9
@ @@@@@
@@@ @@@
@ @ @
@@@ @@@
@@@ @@@@@
@@@ @ @ @
@@@ @@@@@
@ @ @ @
@ @@@@@
输出样例 1：
$$$$$ $
$ $ $ $
$$$$$ $$$
$ $ $ $$$
$$$$$ $$$
$$$ $$$
$ $ $
$$$ $$$
$$$$$ $

输入样例 2：
& 3
@@@
@
@@@

输出样例 2：
bu yong dao le
&&&
&
&&&

分析：设置flag记录是否倒过来和原来相同，输出时候倒序输出即可～

#include <iostream>
#include <vector>
using namespace std;
int main() {
    char c;
    int n, flag = 0;
    scanf("%c%d",&c, &n);
    getchar();
    vector<string> a(n);
    for(int i = 0; i < n; i++)
        getline(cin,a[i]);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(a[i][j] != a[n-1-i][n-1-j])
                flag = 1;
    if(flag == 0) cout << "bu yong dao le\n";
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(a[n-1-i][n-1-j] == '@')
                cout << c;
            else
                cout << " ";
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

char c;

int n, flag = 0;

scanf("%c%d",&c, &n);

getchar();

vector<string> a(n);

for(int i = 0; i < n; i++)

getline(cin,a[i]);

for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)

if(a[i][j] != a[n-1-i][n-1-j])

flag = 1;

if(flag == 0) cout << "bu yong dao le\n";

for(int i = 0; i < n; i++) {

for(int j = 0; j < n; j++) {

if(a[n-1-i][n-1-j] == '@')

cout << c;

else

cout << " ";

}

cout << endl;

}

return 0;

}