L1-3 判断素数

本题的目标很简单，就是判断一个给定的正整数是否素数。

输入格式：

输入在第一行给出一个正整数N（≤ 10），随后N行，每行给出一个小于231的需要判断的正整数。

输出格式：

对每个需要判断的正整数，如果它是素数，则在一行中输出Yes，否则输出No。

输入样例：

1
2
3

2
11
111

输出样例：

1
2

Yes
No

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5+7;
bool bushisu[maxn];
///不是素数true：不是素数；false：是素数

void init(){
    memset(bushisu,false,sizeof(bushisu));
    for(int i=2;i<maxn-1;i++){
        if(!bushisu[i]) {
            for (int j = 2; j * i < maxn; j++) {
                bushisu[j*i] = true;
            }
        }
    }
}

int main(){
    init();
    int n;cin>>n;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        if(bushisu[x]) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
}

所以快去写个素数筛！

埃氏筛

就是上边那个

复杂度O(nloglogn)？

欧拉筛

O(n)

维护一个素数表prime，每个合数只被自己的最大非自身因数筛。

到4，划掉的数也要用来运算，只是不加入质数表。

2*4筛8，但不筛12（应该被2*6筛掉，否则这里会重复运算），用4mod2=0退出

///不是素数 true：不是素数；false：是素数
const int maxn=1e5+7;
bool bushisu[maxn];
int prime[maxn];
int cnt=0;

void init(){
	for(int i=2;i<maxn;i++){
		if(!bushisu[i]){
			prime[cnt++]=i;
			for(int j=0;j<cnt&&prime[j]*i<=maxn;j++){
				bushisu[prime[j]*i]=true;
				if(i%prime[j]==0) break;
			}
		}
	}
}

第9行：

j<=cnt：prime数组最大长度，下标从1到cnt

i*prime[j]：要筛掉的数，当然不能大于maxn

L1-4 到底是不是太胖了

据说一个人的标准体重应该是其身高（单位：厘米）减去100、再乘以0.9所得到的公斤数。真实体重与标准体重误差在10%以内都是完美身材（即 | 真实体重 − 标准体重 | < 标准体重×10%）。已知市斤是公斤的两倍。现给定一群人的身高和实际体重，请你告诉他们是否太胖或太瘦了。

输入格式：

输入第一行给出一个正整数N（≤ 20）。随后N行，每行给出两个整数，分别是一个人的身高H（120 < H < 200；单位：厘米）和真实体重W（50 < W ≤ 300；单位：市斤），其间以空格分隔。

输出格式：

为每个人输出一行结论：如果是完美身材，输出You are wan mei!；如果太胖了，输出You are tai pang le!；否则输出You are tai shou le!。

输入样例：

输出样例：

1
2
3

You are wan mei!
You are tai shou le!
You are tai pang le!

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        float h,w;cin>>h>>w;
        w/=2.0;
        float temp = (h-100)*0.9;
        float res = w-temp;
        if(abs(res)<temp*0.1){
            cout<<"You are wan mei!"<<endl;
        }
        else if(res>0){
            cout<<"You are tai pang le!"<<endl;
        }
        else if(res<0){
            cout<<"You are tai shou le!"<<endl;
        }
    }
}

L1-5 跟奥巴马一起画方块

美国总统奥巴马不仅呼吁所有人都学习编程，甚至以身作则编写代码，成为美国历史上首位编写计算机代码的总统。2014年底，为庆祝“计算机科学教育周”正式启动，奥巴马编写了很简单的计算机代码：在屏幕上画一个正方形。现在你也跟他一起画吧！

输入格式：

输入在一行中给出正方形边长N（3≤N≤21）和组成正方形边的某种字符C，间隔一个空格。

输出格式：

输出由给定字符C画出的正方形。但是注意到行间距比列间距大，所以为了让结果看上去更像正方形，我们输出的行数实际上是列数的50%（四舍五入取整）。

输入样例：

10 a

输出样例：

aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa

#include<bits/stdc++.h>
using namespace std;


int main(){
    int n;cin>>n;
    char c;cin>>c;
    float lie = n/2.0;
    int rlie;
    if(lie-(int)lie>=0.5) rlie = (int)lie+1;
    else rlie = (int) lie;
    for(int i=0;i<rlie;i++){
        for(int j=0;j<n;j++){
            cout<<c;
        }
        cout<<endl;
    }
}

L1-6 一帮一

“一帮一学习小组”是中小学中常见的学习组织方式，老师把学习成绩靠前的学生跟学习成绩靠后的学生排在一组。本题就请你编写程序帮助老师自动完成这个分配工作，即在得到全班学生的排名后，在当前尚未分组的学生中，将名次最靠前的学生与名次最靠后的异性学生分为一组。

输入格式：

输入第一行给出正偶数N（≤50），即全班学生的人数。此后N行，按照名次从高到低的顺序给出每个学生的性别（0代表女生，1代表男生）和姓名（不超过8个英文字母的非空字符串），其间以1个空格分隔。这里保证本班男女比例是1:1，并且没有并列名次。

输出格式：

每行输出一组两个学生的姓名，其间以1个空格分隔。名次高的学生在前，名次低的学生在后。小组的输出顺序按照前面学生的名次从高到低排列。

输入样例：

8
0 Amy
1 Tom
1 Bill
0 Cindy
0 Maya
1 John
1 Jack
0 Linda

输出样例：

Amy Jack
Tom Linda
Bill Maya
Cindy John

#include<bits/stdc++.h>
using namespace std;
struct stu{
    int sex;
    string name;
    int vis;
};
stu s[55];
int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i].sex>>s[i].name;
        s[i].vis=0;
    }
    for(int i=0;i<n;i++){
        stu temp = s[i];
        if(temp.vis) continue;
        for(int j=n-1;j>=0;j--){
            stu ttemp = s[j];
            if(ttemp.vis) continue;
            if(temp.sex!=ttemp.sex){
                cout<<temp.name<<' '<<ttemp.name<<endl;
                s[i].vis=1;
                s[j].vis=1;
                break;
            }
        }
    }
}

L1-7 出租

下面是新浪微博上曾经很火的一张图：

一时间网上一片求救声，急问这个怎么破。其实这段代码很简单，index数组就是arr数组的下标，index[0]=2 对应 arr[2]=1，index[1]=0 对应 arr[0]=8，index[2]=3 对应 arr[3]=0，以此类推…… 很容易得到电话号码是18013820100。

本题要求你编写一个程序，为任何一个电话号码生成这段代码 —— 事实上，只要生成最前面两行就可以了，后面内容是不变的。

输入格式：

输入在一行中给出一个由11位数字组成的手机号码。

输出格式：

为输入的号码生成代码的前两行，其中arr中的数字必须按递减顺序给出。

输入样例：

1	`18013820100`

输出样例：

1 2	`int[] arr = new int[]{8,3,2,1,0}; int[] index = new int[]{3,0,4,3,1,0,2,4,3,4,4};`

#include<bits/stdc++.h>
using namespace std;
bool c[10];
vector<int> v;
vector<int> ind;
map<int,int> t;
int main(){
    memset(c,false,sizeof(c));
    string s;cin>>s;
    for(int i=0;i<s.size();i++){
        c[s[i]-'0']=true;
    }
    for(int i=9;i>=0;i--){
        if(c[i]){
            ///v 存所有用到的数字
            v.push_back(i);
            t[i]=v.size()-1;
        }
    }
    for(int i=0;i<s.size();i++){
        int temp = s[i]-'0';
        ind.push_back(t[temp]);
    }
    printf("int[] arr = new int[]{");
    cout<<v[0];
    for(int i=1;i<v.size();i++){
        cout<<','<<v[i];
    }
    printf("};\n");
    printf("int[] index = new int[]{");
    cout << ind[0];
    for(int i=1; i < ind.size(); i++){
        cout << ',' << ind[i];
    }
    printf("};");

}

L1-8 乘法口诀数列

本题要求你从任意给定的两个 1 位数字 a1 和 a2 开始，用乘法口诀生成一个数列 {a**n}，规则为从 a1 开始顺次进行，每次将当前数字与后面一个数字相乘，将结果贴在数列末尾。如果结果不是 1 位数，则其每一位都应成为数列的一项。

输入格式：

输入在一行中给出 3 个整数，依次为 a1、a2 和 n，满足 0≤a1,a2≤9，0<n≤103。

输出格式：

在一行中输出数列的前 n 项。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

2 3 10

输出样例：

1	`2 3 6 1 8 6 8 4 8 4`

样例解释：

数列前 2 项为 2 和 3。从 2 开始，因为 2×3=6，所以第 3 项是 6。因为 3×6=18，所以第 4、5 项分别是 1、8。依次类推…… 最后因为第 6 项有 6×8=48，对应第 10、11 项应该是 4、8。而因为只要求输出前 10 项，所以在输出 4 后结束。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+7;

vector<int> a;
int main(){
    int x,y,n;
    cin>>x>>y>>n;
    a.push_back(x);
    a.push_back(y);
    for(int i=0;i<n;i++){
        int temp = a[i]*a[i+1];
        if(temp>9){
            string s= to_string(temp);
            for(int j=0;j<s.size();j++){
                a.push_back(s[j]-'0');
            }
        }
        else{
            a.push_back(temp);
        }
        if(a.size()==n){
            break;
        }
    }
    cout<<a[0];
    for(int i=1;i<n;i++){
        cout<<" "<<a[i];
    }
}

L2-1 简单计算器

本题要求你为初学数据结构的小伙伴设计一款简单的利用堆栈执行的计算器。如上图所示，计算器由两个堆栈组成，一个堆栈 S1 存放数字，另一个堆栈 S2 存放运算符。计算器的最下方有一个等号键，每次按下这个键，计算器就执行以下操作：

从 S1 中弹出两个数字，顺序为 n1 和 n2；
从 S2 中弹出一个运算符 op；
执行计算 n2 op n1；
将得到的结果压回 S1。

直到两个堆栈都为空时，计算结束，最后的结果将显示在屏幕上。

输入格式：

输入首先在第一行给出正整数 N（1<N≤103），为 S1 中数字的个数。

第二行给出 N 个绝对值不超过 100 的整数；第三行给出 N−1 个运算符 —— 这里仅考虑 +、-、*、/ 这四种运算。一行中的数字和符号都以空格分隔。

输出格式：

将输入的数字和运算符按给定顺序分别压入堆栈 S1 和 S2，将执行计算的最后结果输出。注意所有的计算都只取结果的整数部分。题目保证计算的中间和最后结果的绝对值都不超过 109。

如果执行除法时出现分母为零的非法操作，则在一行中输出：ERROR: X/0，其中 X 是当时的分子。然后结束程序。

输入样例 1：

1
2
3

5
40 5 8 3 2
/ * - +

输出样例 1：

输入样例 2：

1
2
3

5
2 5 8 4 4
* / - +

输出样例 2：

1	`ERROR: 5/0`

#include <bits/stdc++.h>
using namespace std;

stack<int> num;
stack<char>op;
int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        num.push(x);
    }
    for(int i=0;i<n-1;i++){
        char c;cin>>c;
        op.push(c);
        getchar();
    }
    bool fl=true;
    while(!op.empty()){
        int n1 = num.top();
        num.pop();
        int n2 = num.top();
        num.pop();
        char oper = op.top();
        op.pop();
        if(oper == '+'){
            num.push(n2+n1);
        }
        if(oper == '-'){
            num.push(n2-n1);
        }
        if(oper == '*'){
            num.push(n2*n1);
        }
        if(oper == '/'){
            if(n1!=0){
                num.push(n2/n1);
            }
            else{
                printf("ERROR: %d/%d",n2,n1);
                fl=false;
                break;
            }
        }
    }
    if(fl) cout<<num.top();
}

L2-2 口罩发放

大模拟，麻了，感觉字符串没处理好然后t

为了抗击来势汹汹的 COVID19 新型冠状病毒，全国各地均启动了各项措施控制疫情发展，其中一个重要的环节是口罩的发放。

某市出于给市民发放口罩的需要，推出了一款小程序让市民填写信息，方便工作的开展。小程序收集了各种信息，包括市民的姓名、身份证、身体情况、提交时间等，但因为数据量太大，需要根据一定规则进行筛选和处理，请你编写程序，按照给定规则输出口罩的寄送名单。

输入格式:

输入第一行是两个正整数 D 和 P（1≤D,P≤30），表示有 D 天的数据，市民两次获得口罩的时间至少需要间隔 P 天。

接下来 D 块数据，每块给出一天的申请信息。第 i 块数据（i=1,⋯,D）的第一行是两个整数 T**i 和 S**i（1≤T**i,S**i≤1000），表示在第 i 天有 T**i 条申请，总共有 S**i 个口罩发放名额。随后 T**i 行，每行给出一条申请信息，格式如下：

1	`姓名身份证号身体情况提交时间`

给定数据约束如下：

姓名 是一个长度不超过 10 的不包含空格的非空字符串；
身份证号 是一个长度不超过 20 的非空字符串；
身体情况 是 0 或者 1，0 表示自觉良好，1 表示有相关症状；
提交时间 是 hh:mm，为24小时时间（由 00:00 到 23:59。例如 09:08。）。注意，给定的记录的提交时间不一定有序；
身份证号 各不相同，同一个身份证号被认为是同一个人，数据保证同一个身份证号姓名是相同的。

能发放口罩的记录要求如下：

身份证号 必须是 18 位的数字（可以包含前导0）；
同一个身份证号若在第 i 天申请成功，则接下来的 P 天不能再次申请。也就是说，若第 i 天申请成功，则等到第 i+P+1 天才能再次申请；
在上面两条都符合的情况下，按照提交时间的先后顺序发放，直至全部记录处理完毕或 S**i 个名额用完。如果提交时间相同，则按照在列表中出现的先后顺序决定。

输出格式:

对于每一天的申请记录，每行输出一位得到口罩的人的姓名及身份证号，用一个空格隔开。顺序按照发放顺序确定。

在输出完发放记录后，你还需要输出有合法记录的、身体状况为 1 的申请人的姓名及身份证号，用空格隔开。顺序按照申请记录中出现的顺序确定，同一个人只需要输出一次。

输入样例:

4 2
5 3
A 123456789012345670 1 13:58
B 123456789012345671 0 13:58
C 12345678901234567 0 13:22
D 123456789012345672 0 03:24
C 123456789012345673 0 13:59
4 3
A 123456789012345670 1 13:58
E 123456789012345674 0 13:59
C 123456789012345673 0 13:59
F F 0 14:00
1 3
E 123456789012345674 1 13:58
1 1
A 123456789012345670 0 14:11

输出样例:

D 123456789012345672
A 123456789012345670
B 123456789012345671
E 123456789012345674
C 123456789012345673
A 123456789012345670
A 123456789012345670
E 123456789012345674

样例解释：

输出中，第一行到第三行是第一天的部分；第四、五行是第二天的部分；第三天没有符合要求的市民；第六行是第四天的部分。最后两行按照出现顺序输出了可能存在身体不适的人员。

#include <bits/stdc++.h>
using namespace std;
struct people{
    string name;
    string sfz;
    int sta;
    int hh;
    int mm;
    int suc_day;//上次成功领取的时间
    int ling;//0表示不能领，1表示能领，记入排序
    people(){
        ling=1;
        suc_day=-1;
    }
};
bool cmp(people& a,people& b){
    if(a.ling==b.ling) {
        if (a.hh != b.hh) return a.hh < b.hh;
        else return a.mm < b.mm;
    }
    else return a.ling>b.ling;
}
vector<people> peo;
int num=0;//总人数

int main() {
    ///d：d天的数据；p：市民两次获得口罩的间隔时间
    int d, p;
    cin >> d >> p;
    for (int i = 0; i < d; i++) {
        vector<people> today;

        ///总共0-d-1天，i表示每一天
        int t, s;
        cin >> t >> s;
        ///t：有多少人来，s：多少个口罩
        for (int j = 0; j < t; j++) {
            people temp;
            cin >> temp.name >> temp.sfz >> temp.sta;
            scanf("%d:%d", &temp.hh, &temp.mm);

            //判断身份证号格式
            if(temp.sfz.size()!=18){
                continue;
            }
            bool f=true;
            for(int k=0;k<temp.sfz.size();k++){
                if(temp.sfz[k]-'0'<0||temp.sfz[k]-'0'>9){
                    f=false;
                    break;
                }
            }
            if(!f) continue;


            //判断以前是否领过
            bool peoyou=false;
            for (int k = 0; k < peo.size(); k++) {
                if (peo[k].sfz == temp.sfz) {
                    peoyou=true;
                    if (peo[k].suc_day==-1||peo[k].suc_day + p + 1 < i) {
                        //能领
                        peo[k].ling = 1;
                        temp.ling = 1;
                    } else {
                        peo[k].ling = 0;
                        temp.ling = 0;
                    }
                    if(temp.sta==1) peo[k].sta=1;
                    break;
                }
            }
            if(!peoyou) peo.push_back(temp);
            today.push_back(temp);
        }

        //每天排序
        sort(today.begin(), today.end(), cmp);
//        cout<<"day"<<i<<endl;
//        for(int j=0;j<today.size();j++){
//            cout<<today[j].name<<' ';
//        }
//        cout<<endl;

        for (int j = 0; j < s&& j<today.size(); j++) {
            people temp = today[j];
            if (temp.ling) {
                cout << temp.name << ' ' << temp.sfz<<endl;
                //找到peo中的数据，更新sucday
                for (int k = 0; k < peo.size(); k++) {
                    if (peo[k].sfz == temp.sfz) {
                        peo[k].suc_day =i;
                    }
                }
            }
        }
    }
    //输出有症状的
//    cout<<"有症状"<<endl;
    for(int i=0;i<peo.size();i++){
        if(peo[i].sta){
            cout<<peo[i].name<<' '<<peo[i].sfz<<endl;
        }
    }
}

L2-3 互评成绩

学生互评作业的简单规则是这样定的：每个人的作业会被k个同学评审，得到k个成绩。系统需要去掉一个最高分和一个最低分，将剩下的分数取平均，就得到这个学生的最后成绩。本题就要求你编写这个互评系统的算分模块。

输入格式：

输入第一行给出3个正整数N（3 < N ≤104，学生总数）、k（3 ≤ k ≤ 10，每份作业的评审数）、M（≤ 20，需要输出的学生数）。随后N行，每行给出一份作业得到的k个评审成绩（在区间[0, 100]内），其间以空格分隔。

输出格式：

按非递减顺序输出最后得分最高的M个成绩，保留小数点后3位。分数间有1个空格，行首尾不得有多余空格。

输入样例：

6 5 3
88 90 85 99 60
67 60 80 76 70
90 93 96 99 99
78 65 77 70 72
88 88 88 88 88
55 55 55 55 55

输出样例：

1	`87.667 88.000 96.000`

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+7;

float ping[15];
vector<float> cal;
int main(){
    int n,k,m;
    cin>>n>>k>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
            cin>>ping[j];
        }
        sort(ping,ping+k);
        float sum=0;
        for(int j=1;j<k-1;j++){
            sum+=ping[j];
        }
        cal.push_back((float)sum/(float)(k-2));
    }
    sort(cal.begin(),cal.end());
    for(int i=cal.size()-m;i<cal.size();i++){
        if(i==cal.size()-1){
            printf("%.3f",cal[i]);

        }
        else printf("%.3f ",cal[i]);
    }
}

L2-4 愿天下有情人都是失散多年的兄妹

呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？

输入格式：

输入第一行给出一个正整数N（2 ≤ N ≤104），随后N行，每行按以下格式给出一个人的信息：

1	`本人ID 性别父亲ID 母亲ID`

其中ID是5位数字，每人不同；性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考，则相应的ID位置上标记为-1。

接下来给出一个正整数K，随后K行，每行给出一对有情人的ID，其间以空格分隔。

注意：题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。

输出格式：

对每一对有情人，判断他们的关系是否可以通婚：如果两人是同性，输出Never Mind；如果是异性并且关系出了五服，输出Yes；如果异性关系未出五服，输出No。

输入样例：

24
00001 M 01111 -1
00002 F 02222 03333
00003 M 02222 03333
00004 F 04444 03333
00005 M 04444 05555
00006 F 04444 05555
00007 F 06666 07777
00008 M 06666 07777
00009 M 00001 00002
00010 M 00003 00006
00011 F 00005 00007
00012 F 00008 08888
00013 F 00009 00011
00014 M 00010 09999
00015 M 00010 09999
00016 M 10000 00012
00017 F -1 00012
00018 F 11000 00013
00019 F 11100 00018
00020 F 00015 11110
00021 M 11100 00020
00022 M 00016 -1
00023 M 10012 00017
00024 M 00022 10013
9
00021 00024
00019 00024
00011 00012
00022 00018
00001 00004
00013 00016
00017 00015
00019 00021
00010 00011

输出样例：

Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No

没做，但是一眼LCA，所以写了个LCA板子

L3-1 地铁一日游

森森喜欢坐地铁。这个假期，他终于来到了传说中的地铁之城——魔都，打算好好过一把坐地铁的瘾！

魔都地铁的计价规则是：起步价 2 元，出发站与到达站的最短距离（即计费距离）每 K 公里增加 1 元车费。

例如取 K = 10，动安寺站离魔都绿桥站为 40 公里，则车费为 2 + 4 = 6 元。

为了获得最大的满足感，森森决定用以下的方式坐地铁：在某一站上车（不妨设为地铁站 A），则对于所有车费相同的到达站，森森只会在计费距离最远的站或线路末端站点出站，然后用森森美图 App 在站点外拍一张认证照，再按同样的方式前往下一个站点。

坐着坐着，森森突然好奇起来：在给定出发站的情况下（在出发时森森也会拍一张照），他的整个旅程中能够留下哪些站点的认证照？

地铁是铁路运输的一种形式，指在地下运行为主的城市轨道交通系统。一般来说，地铁由若干个站点组成，并有多条不同的线路双向行驶，可类比公交车，当两条或更多条线路经过同一个站点时，可进行换乘，更换自己所乘坐的线路。举例来说，魔都 1 号线和 2 号线都经过人民广场站，则乘坐 1 号线到达人民广场时就可以换乘到 2 号线前往 2 号线的各个站点。换乘不需出站（也拍不到认证照），因此森森乘坐地铁时换乘不受限制。

输入格式:

输入第一行是三个正整数 N、M 和 K，表示魔都地铁有 N 个车站 (1 ≤ N ≤ 200)，M 条线路 (1 ≤ M ≤ 1500)，最短距离每超过 K 公里 (1 ≤ K ≤ 106)，加 1 元车费。

接下来 M 行，每行由以下格式组成：

<站点1><空格><距离><空格><站点2><空格><距离><空格><站点3> … <站点X-1><空格><距离><空格><站点X>

其中站点是一个 1 到 N 的编号；两个站点编号之间的距离指两个站在该线路上的距离。两站之间距离是一个不大于 106 的正整数。一条线路上的站点互不相同。

注意：两个站之间可能有多条直接连接的线路，且距离不一定相等。

再接下来有一个正整数 Q (1 ≤ Q ≤ 200)，表示森森尝试从 Q 个站点出发。

最后有 Q 行，每行一个正整数 Xi，表示森森尝试从编号为 Xi 的站点出发。

输出格式:

对于森森每个尝试的站点，输出一行若干个整数，表示能够到达的站点编号。站点编号从小到大排序。

输入样例:

6 2 6
1 6 2 4 3 1 4
5 6 2 6 6
4
2
3
4
5

输出样例:

1 2 4 5 6
1 2 3 4 5 6
1 2 4 5 6
1 2 4 5 6

L3-2 计算图

“计算图”（computational graph）是现代深度学习系统的基础执行引擎，提供了一种表示任意数学表达式的方法，例如用有向无环图表示的神经网络。图中的节点表示基本操作或输入变量，边表示节点之间的中间值的依赖性。例如，下图就是一个函数
f(x1,x2)=lnx1+x1x2−sinx2
的计算图。

现在给定一个计算图，请你根据所有输入变量计算函数值及其偏导数（即梯度）。例如，给定输入x1=2,x2=5，上述计算图获得函数值 f(2,5)=ln(2)+2×5−sin(5)=11.652；并且根据微分链式法则，上图得到的梯度 ∇f=[∂f/∂x1,∂f/∂x2]=[1/x1+x2,x1−cosx2]=[5.500,1.716]。

知道你已经把微积分忘了，所以这里只要求你处理几个简单的算子：加法、减法、乘法、指数（e**x，即编程语言中的 exp(x) 函数）、对数（lnx，即编程语言中的 log(x) 函数）和正弦函数（sinx，即编程语言中的 sin(x) 函数）。

友情提醒：

常数的导数是 0；x 的导数是 1；e**x 的导数还是 e**x；lnx 的导数是 1/x；sinx 的导数是 cosx。
回顾一下什么是偏导数：在数学中，一个多变量的函数的偏导数，就是它关于其中一个变量的导数而保持其他变量恒定。在上面的例子中，当我们对 x1 求偏导数 ∂f/∂x1 时，就将 x2 当成常数，所以得到 lnx1 的导数是 1/x1，x1x2 的导数是 x2，sinx2 的导数是 0。
回顾一下链式法则：复合函数的导数是构成复合这有限个函数在相应点的导数的乘积，即若有 u=f(y)，y=g(x)，则 d**u/d**x=d**u/d**y⋅d**y/d**x。例如对 sin(lnx) 求导，就得到 cos(lnx)⋅(1/x)。

如果你注意观察，可以发现在计算图中，计算函数值是一个从左向右进行的计算，而计算偏导数则正好相反。

输入格式：

输入在第一行给出正整数 N（≤5×104），为计算图中的顶点数。

以下 N 行，第 i 行给出第 i 个顶点的信息，其中 i=0,1,⋯,N−1。第一个值是顶点的类型编号，分别为：

0 代表输入变量
1 代表加法，对应 x1+x2
2 代表减法，对应 x1−x2
3 代表乘法，对应 x1×x2
4 代表指数，对应 e**x
5 代表对数，对应 lnx
6 代表正弦函数，对应 sinx

对于输入变量，后面会跟它的双精度浮点数值；对于单目算子，后面会跟它对应的单个变量的顶点编号（编号从 0 开始）；对于双目算子，后面会跟它对应两个变量的顶点编号。

题目保证只有一个输出顶点（即没有出边的顶点，例如上图最右边的 -），且计算过程不会超过双精度浮点数的计算精度范围。

输出格式：

首先在第一行输出给定计算图的函数值。在第二行顺序输出函数对于每个变量的偏导数的值，其间以一个空格分隔，行首尾不得有多余空格。偏导数的输出顺序与输入变量的出现顺序相同。输出小数点后 3 位。

输入样例：

输出样例：

1 2	`11.652 5.500 1.716`

L3-3 球队“食物链”

某国的足球联赛中有N支参赛球队，编号从1至N。联赛采用主客场双循环赛制，参赛球队两两之间在双方主场各赛一场。

联赛战罢，结果已经尘埃落定。此时，联赛主席突发奇想，希望从中找出一条包含所有球队的“食物链”，来说明联赛的精彩程度。“食物链”为一个1至N的排列{ T1 T2 ⋯ T**N }，满足：球队T1战胜过球队T2，球队T2战胜过球队T3，⋯，球队T(N−1)战胜过球队T**N，球队T**N战胜过球队T1。

现在主席请你从联赛结果中找出“食物链”。若存在多条“食物链”，请找出字典序最小的。

注：排列{ a1 a2 ⋯ a**N}在字典序上小于排列{ b1 b2 ⋯ b**N }，当且仅当存在整数K（1≤K≤N），满足：a**K<b**K且对于任意小于K的正整数i，a**i=b**i。

输入格式：

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

输出格式：

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

输入样例1：

5
-LWDW
W-LDW
WW-LW
DWW-W
DDLW-

输出样例1：

1	`1 3 5 4 2`

输入样例2：

5
-WDDW
D-DWL
DD-DW
DDW-D
DDDD-

输出样例2：

1	`No Solution`

L1-3 判断素数

输入格式：

输出格式：

输入样例：

输出样例：

埃氏筛

欧拉筛

L1-4 到底是不是太胖了

输入格式：

输出格式：

输入样例：

输出样例：

L1-5 跟奥巴马一起画方块

输入格式：

输出格式：

输入样例：

输出样例：

L1-6 一帮一

输入格式：

输出格式：

输入样例：

输出样例：

L1-7 出租

输入格式：

输出格式：

输入样例：

输出样例：

L1-8 乘法口诀数列

输入格式：

输出格式：

输入样例：

输出样例：

样例解释：

L2-1 简单计算器

输入格式：

输出格式：

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

L2-2 口罩发放

输入格式:

输出格式:

输入样例:

输出样例:

样例解释：

L2-3 互评成绩

输入格式：

输出格式：

输入样例：

输出样例：

L2-4 愿天下有情人都是失散多年的兄妹

输入格式：

输出格式：

输入样例：

输出样例：

L3-1 地铁一日游

输入格式:

输出格式:

输入样例:

输出样例:

L3-2 计算图

输入格式：

输出格式：

输入样例：

输出样例：

L3-3 球队“食物链”

输入格式：

输出格式：

输入样例1：

输出样例1：

输入样例2：

输出样例2：

STERNE