liuchuo – 第113页 – 我不管，反正我最萌～

PAT 1129. Recommendation System (25) 甲级

Recommendation system predicts the preference that a user would give to an item. Now you are asked to program a very simple recommendation system that rates the user’s preference by the number of times that an item has been accessed by this user.

Input Specification:

Each input file contains one test case. For each test case, the first line contains two positive integers: N (<= 50000), the total number of queries, and K (<= 10), the maximum number of recommendations the system must show to the user. Then given in the second line are the indices of items that the user is accessing — for the sake of simplicity, all the items are indexed from 1 to N. All the numbers in a line are separated by a space.

Output Specification:

For each case, process the queries one by one. Output the recommendations for each query in a line in the format:

query: rec[1] rec[2] … rec[K]

where query is the item that the user is accessing, and rec[i] (i = 1, … K) is the i-th item that the system recommends to the user. The first K items that have been accessed most frequently are supposed to be recommended in non-increasing order of their frequencies. If there is a tie, the items will be ordered by their indices in increasing order.

Note: there is no output for the first item since it is impossible to give any recommendation at the time. It is guaranteed to have the output for at least one query.

Sample Input:
12 3
3 5 7 5 5 3 2 1 8 3 8 12
Sample Output:
5: 3
7: 3 5
5: 3 5 7
5: 5 3 7
3: 5 3 7
2: 5 3 7
1: 5 3 2
8: 5 3 1
3: 5 3 1
8: 3 5 1
12: 3 5 8

题目大意：根据用户每次点击的东西的编号，输出他在点当前编号之前应该给这个用户推荐的商品的编号～只推荐k个～也就是输出用户曾经点击过的商品编号的最多的前k个～如果恰好两个商品有相同的点击次数，就输出编号较小的那个～
分析：【并不复杂～只是写的比较详细～不怕不怕～(摸头…】因为每个商品有两个属性：编号value和出现的次数cnt，编号具有唯一性，然后set又会根据大小自动排序，所以我们可以考虑将value和cnt组成一个node属性，把所有商品编号和它对应的次数变成node放入set里面，重载小于号，使<根据set中node的cnt排序，如果cnt相等就按照node的value排序～
这样set里面就是按照出现次数排序好的商品node，每次输出set的前k个node的value值就可以～（要记住，因为是点击前推荐，所以我们在接收完num的值后，应该先输出再插入让set帮忙排序当前num，当前的这个点击编号暂时先不算在输出结果里面的～）
首先在struct node里面重载<号，如果当前cnt不等于a.cnt就将cnt大的排在前，否则将value小的排在前面～
每次输入的时候，先不插入，先输出，当i != 0时候开始输出，因为i==0时候用户才第一次点击，没有可以推荐的～(沮丧脸…) 输出的同时记录输出过的个数tempCnt，当tempCnt < k的时候输出，因为只要前k个～所以就从头到尾依次输出set中的值就可以啦～
book[num]标记num出现的次数，每次寻找set中当前值为num和次数为book[num]的那个值，如果找到了就把他移除，（找到说明这个数已经出现过啦，cnt已经不对啦，先移除掉吧～）然后将book[num]+1，在将node(num, book[num])插入到set中，set会帮忙根据我们自定义的<的规则自动排序哒～

#include <iostream>
#include <set>
using namespace std;
int book[50001];
struct node {
    int value, cnt;
    bool operator < (const node &a) const {
        return (cnt != a.cnt) ? cnt > a.cnt : value < a.value;
    }
};
int main() {
    int n, k, num;
    scanf("%d%d", &n, &k);
    set<node> s;
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        if (i != 0) {
            printf("%d:", num);
            int tempCnt = 0;
            for(auto it = s.begin(); tempCnt < k && it != s.end(); it++) {
                printf(" %d", it->value);
                tempCnt++;
            }
            printf("\n");
        }
        auto it = s.find(node{num, book[num]});
        if (it != s.end()) s.erase(it);
        book[num]++;
        s.insert(node{num, book[num]});
    }
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

int book[50001];

struct node {

int value, cnt;

bool operator < (const node &a) const {

return (cnt != a.cnt) ? cnt > a.cnt : value < a.value;

}

};

int main() {

int n, k, num;

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

set<node> s;

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

scanf("%d", &num);

if (i != 0) {

printf("%d:", num);

int tempCnt = 0;

for(auto it = s.begin(); tempCnt < k && it != s.end(); it++) {

printf(" %d", it->value);

tempCnt++;

}

printf("\n");

}

auto it = s.find(node{num, book[num]});

if (it != s.end()) s.erase(it);

book[num]++;

s.insert(node{num, book[num]});

}

return 0;

}

CCCC-GPLT L3-015. 球队“食物链” 团体程序设计天梯赛

某国的足球联赛中有N支参赛球队，编号从1至N。联赛采用主客场双循环赛制，参赛球队两两之间在双方主场各赛一场。
联赛战罢，结果已经尘埃落定。此时，联赛主席突发奇想，希望从中找出一条包含所有球队的“食物链”，来说明联赛的精彩程度。“食物链”为一个1至N的排列{ T1 T2 … TN }，满足：球队T1战胜过球队T2，球队T2战胜过球队T3，……，球队T(N-1)战胜过球队TN，球队TN战胜过球队T1。
现在主席请你从联赛结果中找出“食物链”。若存在多条“食物链”，请找出字典序最小的。
注：排列{ a1 a2 …aN }在字典序上小于排列{ b1 b2 … bN }，当且仅当存在整数K（1 <= K <= N），满足：aK < bK且对于任意小于K的正整数i，ai=bi。

输入格式：
输入第一行给出一个整数N（2 <= N <= 20），为参赛球队数。随后N行，每行N个字符，给出了NxN的联赛结果表，其中第i行第j列的字符为球队i在主场对阵球队j的比赛结果：“W”表示球队i战胜球队j，“L”表示球队i负于球队j，“D”表示两队打平，“-”表示无效（当i=j时）。输入中无多余空格。

输出格式：
按题目要求找到“食物链”T1 T2 … TN，将这N个数依次输出在一行上，数字间以1个空格分隔，行的首尾不得有多余空格。若不存在“食物链”，输出“No Solution”。

输入样例1：
5
-LWDW
W-LDW
WW-LW
DWW-W
DDLW-
输出样例1：
1 3 5 4 2
输入样例2：
5
-WDDW
D-DWL
DD-DW
DDW-D
DDDD-
输出样例2：
No Solution

分析：
0.既然是字典序最小的，而且必须包含所有的球队编号，那如果存在的话1肯定是结果数组的第一位～
1.接收数据：用v[21][21]存储比赛结果，如果是W就将v[i][j]置为1，表示i战胜过j，如果是L就将v[j][i]置为1，表示j战胜过i，其余的不用管～
2.dfs(int index, int num)：index从1到n用来表示当前即将写入的结果数组result的下标，num表示当前的球队的编号，从1开始。
3.flag用来标记是否已经找到一个这样的结果数组，如果已经找到了（flag == 1）就return; 否则将当前下标index的result写入num值。
当index等于n的时候，并且v[num][1]等于true，表示已经写到了n个球员，而且这个球队num也曾经战胜过球队1～如果仅仅是index == n，就直接return不用继续向下找了～
4.cut标记剪枝，首先cut等于false，当所有没有访问过的结点中没有一个结点的v[i][1] == true，即没有一个球队战胜过1，就直接return，因为这条路径肯定找不到回路啦～
5.然后将num球队编号标记为已经访问过【visit[num] = true;】遍历num所有打败过的球队，并将index + 1，直到dfs结束的最后将visit标记回false
6.最后根据flag的值输出结果，如果flag为0说明没有满足题意的球队，就输出No Solution，如果flag = 1就输出result数组中保存的结果～

#include <cstdio>
using namespace std;
int n, flag = 0;
int result[21];
bool v[21][21], visit[21];
void dfs(int index, int num) {
    if (flag == 1) return;
    result[index] = num;
    if (index == n && v[num][1] == true) {
        flag = 1;
        return;
    }
    if (index == n) return;
    bool cut = false;
    for (int i = 1; i <= n; i++) {
        if (visit[i] == false && v[i][1] == true)
            cut = true;
    }
    if (cut == false) return;
    visit[num] = true;
    for (int i = 1; i <= n; i++) {
        if (visit[i] == false && v[num][i] == true)
            dfs(index + 1, i);
    }
    visit[num] = false;
}
int main() {
    scanf("%d", &n);
    char s[21];
    for (int i = 1; i <= n; i++) {
        scanf("%s", s + 1);
        for (int j = 1; j <= n; j++) {
            if (s[j] == 'W') v[i][j] = true;
            if (s[j] == 'L') v[j][i] = true;
        }
    }
    dfs(1, 1);
    if (flag == 1) {
        for (int i = 1; i <= n; i++)
            printf("%s%d", i == 1 ? "" : " ", result[i]);
    } else {
        printf("No Solution");
    }
    return 0;
}

#include <cstdio>

using namespace std;

int n, flag = 0;

int result[21];

bool v[21][21], visit[21];

void dfs(int index, int num) {

if (flag == 1) return;

result[index] = num;

if (index == n && v[num][1] == true) {

flag = 1;

return;

}

if (index == n) return;

bool cut = false;

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

if (visit[i] == false && v[i][1] == true)

cut = true;

}

if (cut == false) return;

visit[num] = true;

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

if (visit[i] == false && v[num][i] == true)

dfs(index + 1, i);

}

visit[num] = false;

}

int main() {

scanf("%d", &n);

char s[21];

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

scanf("%s", s + 1);

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

if (s[j] == 'W') v[i][j] = true;

if (s[j] == 'L') v[j][i] = true;

}

dfs(1, 1);

if (flag == 1) {

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

printf("%s%d", i == 1 ? "" : " ", result[i]);

} else {

printf("No Solution");

}

return 0;

}

CCCC-GPLT L3-013. 非常弹的球团体程序设计天梯赛

刚上高一的森森为了学好物理，买了一个“非常弹”的球。虽然说是非常弹的球，其实也就是一般的弹力球而已。森森玩了一会儿弹力球后突然想到，假如他在地上用力弹球，球最远能弹到多远去呢？他不太会，你能帮他解决吗？当然为了刚学习物理的森森，我们对环境做一些简化：

假设森森是一个质点，以森森为原点设立坐标轴，则森森位于(0, 0)点。
小球质量为w/100 千克（kg），重力加速度为9.8米/秒平方（m/s2）。
森森在地上用力弹球的过程可简化为球从(0, 0)点以某个森森选择的角度ang (0 < ang < pi/2) 向第一象限抛出，抛出时假设动能为1000 焦耳（J）。
小球在空中仅受重力作用，球纵坐标为0时可视作落地，落地时损失p%动能并反弹。
地面可视为刚体，忽略小球形状、空气阻力及摩擦阻力等。
森森为你准备的公式：

动能公式：E = m * v2 / 2
牛顿力学公式：F = m * a
重力：G = m * g
其中：
E – 动能，单位为“焦耳”
m – 质量，单位为“千克”
v – 速度，单位为“米/秒”
a – 加速度，单位为“米/秒平方”
g – 重力加速度
输入格式：

输入在一行中给出两个整数：1 <= w <= 1000 和 1 <= p <= 100，分别表示放大100倍的小球质量、以及损失动力的百分比p。

输出格式：

在一行输出最远的投掷距离，保留3位小数。

输入样例：
100 90
输出样例：
226.757

分析：
因为E=1/2mv^2，所以v^2=2E/m
当v分解为垂直方向的vsinθ和水平方向的vcosθ，所以水平方向的v为vsinθ，t为vcosθ/g，抛到最高点时通过的路程为s = vt = vsinθvcosθ/g，落下来同样相同的距离，s = 2vsinθvcosθ/g
因为2sinθvcosθ=sin2θ，sin2θ的最大值为1，即2θ=90°，θ=45°的时候s取得最大值～
这样s = v^2/g
又因为v^2=2E/m，在代码中v^2为变量v2，所以v2 = 2 * 1000 * 100 / w，即E = 1000， m = w/100
每次将v2/g 即v2 / 9.8的结果累加到s中，可以得到s为最后求得的总距离，每一次while循环，都要将v2损失百分比p，直到v2足够小（这里取0.000001可以通过所有测试用例，如果是0.00001会有一个测试点答案错误）的时候退出循环～

#include <cstdio>
int main() {
    double w, p, v2, s = 0;
    scanf("%lf%lf", &w, &p);
    v2 = 2 * 1000 * 100 / w;
    while (v2 > 0.000001) {
        s += v2 / 9.8;
        v2 *= (100 - p) * 0.01;
    }
    printf("%.3f", s);
    return 0;
}

#include <cstdio>

int main() {

double w, p, v2, s = 0;

scanf("%lf%lf", &w, &p);

v2 = 2 * 1000 * 100 / w;

while (v2 > 0.000001) {

s += v2 / 9.8;

v2 *= (100 - p) * 0.01;

}

printf("%.3f", s);

return 0;

}

CCCC-GPLT L2-020. 功夫传人团体程序设计天梯赛

一门武功能否传承久远并被发扬光大，是要看缘分的。一般来说，师傅传授给徒弟的武功总要打个折扣，于是越往后传，弟子们的功夫就越弱…… 直到某一支的某一代突然出现一个天分特别高的弟子（或者是吃到了灵丹、挖到了特别的秘笈），会将功夫的威力一下子放大N倍 —— 我们称这种弟子为“得道者”。
这里我们来考察某一位祖师爷门下的徒子徒孙家谱：假设家谱中的每个人只有1位师傅（除了祖师爷没有师傅）；每位师傅可以带很多徒弟；并且假设辈分严格有序，即祖师爷这门武功的每个第i代传人只能在第i-1代传人中拜1个师傅。我们假设已知祖师爷的功力值为Z，每向下传承一代，就会减弱r%，除非某一代弟子得道。现给出师门谱系关系，要求你算出所有得道者的功力总值。

输入格式：
输入在第一行给出3个正整数，分别是：N（<=105）——整个师门的总人数（于是每个人从0到N-1编号，祖师爷的编号为0）；Z——祖师爷的功力值（不一定是整数，但起码是正数）；r ——每传一代功夫所打的折扣百分比值（不超过100的正数）。接下来有N行，第i行（i=0, …, N-1）描述编号为i的人所传的徒弟，格式为：

Ki ID[1] ID[2] … ID[Ki]

其中Ki是徒弟的个数，后面跟的是各位徒弟的编号，数字间以空格间隔。Ki为零表示这是一位得道者，这时后面跟的一个数字表示其武功被放大的倍数。

输出格式：
在一行中输出所有得道者的功力总值，只保留其整数部分。题目保证输入和正确的输出都不超过1010。

输入样例：
10 18.0 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3
输出样例：
404

分析：一开始没弄懂题意，以为是是放大师傅的功力，原来是师傅功力减弱r%后的功力。。用二维数组v存储师门谱系关系，v[i]表示编号为i的师傅所拥有的徒弟，如果徒弟个数等于0，也就是说这是个得道者，那么v[i][0]保存放大的倍数，而且用visit[i] = true标记当前的这个编号的人是得道者～用深度优先搜索，每当遇到visit[index] = true也就是说这是个得道者的时候，就累加放大后的功力，power * v[index][0]，累加到result中～遍历v[index]的所有弟子，并将功力减弱r%，也就是power * (1 – r/100)，最后输出的是result的整数值(int)result ～～～

#include <cstdio>
#include <vector>
using namespace std;
vector<vector<int> > v;
int n, k;
double z, r, result = 0.0;
bool visit[100010];
void dfs(int index, double power) {
    if (visit[index] == true) {
        result += power * v[index][0];
        return;
    }
    for (int i = 0; i < v[index].size(); i++)
        dfs(v[index][i], power * (1 - r/100));
}
int main() {
    scanf("%d%lf%lf", &n, &z, &r);
    v.resize(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &k);
        int temp;
        if (k == 0) {
            scanf("%d", &temp);
            v[i].push_back(temp);
            visit[i] = true;
        }
        for (int j = 0; j < k; j++) {
            scanf("%d", &temp);
            v[i].push_back(temp);
        }
    }
    dfs(0, z);
    printf("%d", (int)result);
    return 0;
}

#include <cstdio>

#include <vector>

using namespace std;

vector<vector<int> > v;

int n, k;

double z, r, result = 0.0;

bool visit[100010];

void dfs(int index, double power) {

if (visit[index] == true) {

result += power * v[index][0];

return;

}

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

dfs(v[index][i], power * (1 - r/100));

}

int main() {

scanf("%d%lf%lf", &n, &z, &r);

v.resize(n);

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

scanf("%d", &k);

int temp;

if (k == 0) {

scanf("%d", &temp);

v[i].push_back(temp);

visit[i] = true;

}

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

scanf("%d", &temp);

v[i].push_back(temp);

}

dfs(0, z);

printf("%d", (int)result);

return 0;

}

CCCC-GPLT L2-019. 悄悄关注团体程序设计天梯赛

新浪微博上有个“悄悄关注”，一个用户悄悄关注的人，不出现在这个用户的关注列表上，但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探，根据某人的关注列表和其对其他用户的点赞情况，扒出有可能被其悄悄关注的人。

输入格式：
输入首先在第一行给出某用户的关注列表，格式如下：

人数N 用户1 用户2 …… 用户N

其中N是不超过5000的正整数，每个“用户i”（i=1, …, N）是被其关注的用户的ID，是长度为4位的由数字和英文字母组成的字符串，各项间以空格分隔。

之后给出该用户点赞的信息：首先给出一个不超过10000的正整数M，随后M行，每行给出一个被其点赞的用户ID和对该用户的点赞次数（不超过1000），以空格分隔。注意：用户ID是一个用户的唯一身份标识。题目保证在关注列表中没有重复用户，在点赞信息中也没有重复用户。

输出格式：
我们认为被该用户点赞次数大于其点赞平均数、且不在其关注列表上的人，很可能是其悄悄关注的人。根据这个假设，请你按用户ID字母序的升序输出可能是其悄悄关注的人，每行1个ID。如果其实并没有这样的人，则输出“Bing Mei You”。

输入样例1：
10 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao
8
Magi 50
Pota 30
LLao 3
Ammy 48
Dave 15
GAO3 31
Zoro 1
Cath 60
输出样例1：
Ammy
Cath
Pota
输入样例2：
11 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao Pota
7
Magi 50
Pota 30
LLao 48
Ammy 3
Dave 15
GAO3 31
Zoro 29
输出样例2：
Bing Mei You

分析：将关注的人存储在集合set里，将点赞的人和点赞的次数存储在map中，并统计点赞的平均次数sum / M，遍历map，如果map的值大于平均次数，且在set中找不到该用户名，就输出当前用户名（因为map中的键是已经按照字典序排序过的，所以直接输出就可以），并用flag标记是否有过输出，如果从始至终没有输出，说明没有悄悄关注的人，就输出Bing Mei You～～～

#include <iostream>
#include <map>
#include <set>
using namespace std;
int main() {
    int N, M, sum = 0, cnt, flag = 0;
    string str;
    cin >> N;
    set<string> s;
    for (int i = 0; i < N; i++) {
        cin >> str;
        s.insert(str);
    }
    cin >> M;
    map<string, int> m;
    for (int i = 0; i < M; i++) {
        cin >> str >> cnt;
        m[str] = cnt;
        sum += cnt;
    }
    sum /= M;
    for (auto it : m) {
        if (it.second > sum && s.find(it.first) == s.end()) {
            cout << it.first << endl;
            flag = 1;
        }
    }
    if (flag == 0) cout << "Bing Mei You";
    return 0;
}

#include <iostream>

#include <map>

#include <set>

using namespace std;

int main() {

int N, M, sum = 0, cnt, flag = 0;

string str;

cin >> N;

set<string> s;

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

cin >> str;

s.insert(str);

}

cin >> M;

map<string, int> m;

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

cin >> str >> cnt;

m[str] = cnt;

sum += cnt;

}

sum /= M;

for (auto it : m) {

if (it.second > sum && s.find(it.first) == s.end()) {

cout << it.first << endl;

flag = 1;

}

if (flag == 0) cout << "Bing Mei You";

return 0;

}

【解释】while(~scanf(“%d”, &n))的~的含义～scanf

~是按位取反

scanf的返回值是输入值的个数

如果没有输入值就是返回-1

-1按位取反结果是0

while(~scanf(“%d”, &n))就是当没有输入的时候退出循环

喵喵喵～