A 数字方阵

题目描述

 总是对数字的神秘感感到好奇。这次，他在纸上写下了  个从 到 的数字，并把这些数字排成了 的方阵。他惊奇地发现，这个方阵中每行、每列和两条主对角线上的数字之和都不一样。他想要更多的方阵，但他再写不出来了。于是他㕛跑来找你，请你给他一个边长为  的满足上述性质的方阵。

输入描述:

输入共一行，一个整数 

 ，意义同题面描述。

输出描述:

输出共 

 行，每行 

 个整数，表示答案方阵。输出任意一种可行方案即可。

示例1

输入

3

输出

1 2 3
8 9 4
7 6 5

备注:

 

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1010;
 4 int a[N][N];
 5 int main( ) {
 6     int n;
 7     std::cin >> n;
 8     int ans = (n-1)*n+1, ans1 = 1;
 9     for(int i = 1; i <= n; i ++) {
10         for(int j = 1; j < n; j ++) {
11             printf("%d ",ans1++);
12         }
13         printf("%d\n",ans++);
14     }
15     return 0;
16 }

B 小马过河

题目描述

 开始涉猎几何领域了。他现在正在研究小马喝水问题。
众所周知，这个问题中有一匹口渴的小马，一条笔直的河，以及小马的家。小马需要去河边喝水，然后再去家里。它需要走最短的路径。

解决这个问题也很简单，其中有一个步骤是要做小马家关于河水的对称点。
正对此感到一些烦恼。他不会做这个。他想请你帮他作一条过小马家且垂直于河水的线，然后告诉 垂足的位置。

输入描述:

第一行一个整数 

 ，表示 

 的询问个数。接下去 

 行，每行 

 个实数 

，表示小马家在点 

 ，河水为直线 

输出描述:

输出共 

 行，每行两个实数 

， 表示答案垂足点的坐标 

。 当你的答案与标准输出的误差小于 

 时，视为答案正确。

示例1

输入

3
0 1 0 0 1 1
2.13 -6.89 1.78 1.20 -7.73 0.56
3.473 -4.326 -4.851 -0.819 2.467 -2.729

输出

0.5000000 0.5000000
1.5864392 1.1869738
3.7990750 -3.076672

备注:

 
计算u v直接是否存在一点x 得的xp与uv垂直，几何问题。
uv斜率 a = (uy-vy)/(ux-vx)   
uv为y = a(x-ux)+uy 
xp为y = -(x-px)/a+py
联立就可以计算出x的坐标了。特殊值0考虑下。
 

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main() {
 5     int t;
 6     cin >>t;
 7     while(t--) {
 8         double px,py,ux,uy,vx,vy;
 9         cin >> px >> py >> ux >> uy >> vx >> vy;
10         if(ux == vx) printf("%.6lf %.6lf\n",ux,py);
11         else if(uy == vy) printf("%.6lf %.6lf\n",px,uy);
12         else{
13             double a = (uy-vy)/(ux-vx);
14             double x = (px+a*py+a*a*ux-a*uy)/(a*a+1);
15             double y = py + (px - x) / a;
16             printf("%.6lf %.6lf\n",x,y);
17         }
18     }
19     return 0;
20 }

C 真真假假

题目描述

乾为天，刚健中正，自强不息；坤为地，柔顺伸展，厚载万物。
乾卦：天行健，君子以自强不息。困龙得水好运交，不由喜气上眉梢，一切谋望皆如意，向后时运渐渐高。
坤卦：地势坤，君子以厚德载物。肥羊失群入山岗，饿虎逢之把口张，适口充肠心欢喜，卦若占之大吉昌。 

算卦先生来问你，对于每个他给出的 C++ 头文件，请告诉他是否存在。
头文件列表：algorithm, bitset, cctype, cerrno, clocale, cmath, complex, cstdio, cstdlib, cstring, ctime, deque, exception, fstream, functional, limits, list, map, iomanip, ios, iosfwd, iostream, istream, ostream, queue, set, sstream, stack, stdexcept, streambuf, string, utility, vector, cwchar, cwctype

输入描述:

第一行一个正整数 ，表示询问个数。
接下去 行，每行一个仅由小写字母构成的字符串 ，表示一个询问。 

输出描述:

输出共 

 行，每行一个字符串 

 表示这个头文件存在，或 

 表示这个头文件不存在。 

示例1

输入

3
cstdio
splay
fstream

输出

Qian
Kun
Qian

备注:

每个询问字符串 

 中保证不存在标点、空格或其他不可见字符。

签到题

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 string s[35] = {"algorithm", "bitset", "cctype", "cerrno", "clocale", "cmath",
 4  "complex", "cstdio", "cstdlib", "cstring", "ctime", "deque", "exception", "fstream", "functional",
 5  "limits", "list", "map", "iomanip", "ios", "iosfwd", "iostream", "istream", "ostream", "queue", "set", "sstream",
 6  "stack", "stdexcept", "streambuf", "string", "utility", "vector", "cwchar", "cwctype"};
 7 int main() {
 8     int t;
 9     map<string,int> mp;
10     for(int i = 0; i < 35; i ++) {
11         mp[s[i]]++;
12     }
13     cin >>t;
14     while(t--) {
15         string ss;
16         cin >> ss;
17         if(mp[ss]) cout << "Qian\n";
18         else cout << "Kun\n";
19     }
20     return 0;
21 }

D 虚虚实实

题目描述

震为雷，临危不乱，亨通畅达；巽为风，柔顺伸展，厚载万物。
震卦：洊雷，震，君子以恐惧修省。一口金钟在淤泥，人人拿着当玩石，忽然一日钟悬起，响亮一声天下知。
巽卦：随风，巽，君子以申命行事。一叶孤舟落沙滩，有篙无水进退难，时逢大雨江湖溢，不用费力任往返。 

算卦先生来问你，对于每个他给出的无向图，是否存在一条路径能够经过所有边恰好一次，并且经过所有点？不需要满足最后回到起点。 

输入描述:

第一行一个数 

 ，表示有 

 组数据。对与每组数据，第一行有两个数 

，接下去 

 行每行两个数 

 描述一条无向边 

。图不保证联通。输出描述:对于每组数据，如果存在，输出 

 ，否则输出  。 

示例1

输入

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

输出

Zhen
Xun

备注:

 
全部边都走一遍，满足奇点少于等于两个就行，然后判断是否都连在一起，并查集判断。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 33;
 4 std::vector<int> vs[N];
 5 int fa[N];
 6 int find(int x) {
 7     return fa[x] == x? x : find(fa[x]);
 8 }
 9 void unit(int x, int y) {
10     x = find(x), y = find(y);
11     if(x < y) fa[x] = y;
12     else fa[y] = x;
13 }
14 void init() {
15     for(int i = 0; i < N; i ++) {
16         vs[i].clear();
17         fa[i] = i;
18     }
19 }
20 int main() {
21     int t;
22     cin >> t;
23     while(t--) {
24         int n, m;
25         init();
26         cin >> n >> m;
27         for(int i = 0; i < m; i ++) {
28             int u, v;
29             cin >> u >> v;
30             unit(u,v);
31             vs[u].push_back(v);
32             vs[v].push_back(u);
33         }
34         int ans = 0, ans1 = 0;
35         for(int i = 1; i <= n; i ++) {
36             if(vs[i].size()%2) ans++;
37             if(find(i) == i) ans1++;
38         }
39         if(ans <= 2 && ans1 == 1) printf("Zhen\n");
40         else printf("Xun\n");
41     }
42     return 0;
43 }

E 是是非非

题目描述

坎为水，险阳失道，渊深不测；离为火，依附团结，光明绚丽。
坎卦：水洊至，习坎；君子以常德行，习教事。一轮明月照水中，只见影儿不见踪，愚夫当财下去取，摸来摸去一场空。
离卦：明两作，离，大人以继明照四方。官人来占主高升，庄农人家产业增，生意买卖利息厚，匠艺占之大亨通。 

有一些石子堆，第 堆有 个石子。你和算卦先生轮流从任一堆中任取若干颗石子（每次只能取自一堆，并且不能不取），取到最后一颗石子的人获胜。 
算卦先生来问你，如果你先手，你是否有必胜策略？若是改动其中几个石子堆中石子的数量呢？

输入描述:

第一行两个正整数 ，表示有 个石堆， 次操作。 
第二行 个整数，第 个数 表示第 个石堆初始有 个石子。 
接下去 行，每行两个正整数 ，表示把第 堆石子的个数修改成 。操作是累计的，也就是说，每次操作是在上一次操作结束后的状态上操作的。

输出描述:

共  行，输出每次操作之后先手是否有必胜策略。
如果有，输出  ，否则输出  。 

示例1

输入

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

输出

Kan
Kan
Li
Li

备注:

 
尼姆博弈，有奇异局势为0时为输，否则赢

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int ans[100010];
 4 int main(int argc, char const *argv[]) {
 5     int n,q, tmp = 0;
 6     cin >> n >> q;
 7     for(int i = 1; i <= n; i ++) {
 8         cin >> ans[i];
 9         tmp^= ans[i];
10     }
11     while(q--) {
12         int x, y;
13         cin >> x >> y;
14         tmp ^= ans[x];
15         tmp ^= y;
16         ans[x] = y;
17         if(tmp) cout << "Kan\n";
18         else cout << "Li\n";
19     }
20     return 0;
21 }

 

F 黑黑白白

题目描述

艮为山，动静得宜，适可而止；兑为泽，刚内柔外，上下相和。
艮卦：兼山，艮；君子以思不出其位。财帛常打心头走，可惜眼前难到手，不如意时且忍耐，逢着闲事休开口。
兑卦：丽泽，兑；君子以朋友讲习。这个卦象真可取，觉着做事不费力，休要错过这机关，事事觉得随心意。

有一个棋子放在一颗有根树的根上。你和算卦先生轮流把这个棋子向所在点的其中一个儿子移动（只能移动到儿子）。不能再移动就算失败（即棋子所在节点没有儿子）。
算卦先生来问你，如果你先手，你是否有必胜策略？ 

输入描述:

第一行一个数 ，表示有 组数据。接下去每组数据的第一行有两个数  ，表示树有 个节点，其中 为根节点编号（从 开始编号）。 
接下去 行每行两个数字  ，表示点 和 之间有一条边。 

输出描述:

每组数据输出一行，

 表示先手有必胜策略，

 表示没有。 

示例1

输入

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

输出

Dui
Gen

备注:

深度优先搜索下，假设在当前节点下，之前儿子节点有一个存在输的状态，那么当前节点一定可以赢，否则就必输。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e4+10;
 4 std::vector<int> vs[N];
 5 bool dfs(int u, int f){
 6     for(int i = 0;  i< vs[u].size(); i ++) {
 7         int v = vs[u][i];
 8         if(v == f) continue;
 9         if(!dfs(v,u)) return 1;
10     }
11     return 0;
12 }
13 int main( ){
14     int t;
15     cin >> t;
16     while(t--) {
17         int n, r;
18         cin >> n >> r;
19         for (int i = 0; i < n-1; i++) {
20             int u, v;
21             cin >> u >> v;
22             vs[u].push_back(v);
23             vs[v].push_back(u);
24         }
25         if(dfs(r,-1))printf("Gen\n");
26         else printf("Dui\n");
27         for(int i = 0;  i< N; i++) vs[i].clear();
28     }
29     return 0;
30 }

G 文

题目描述

Sεlιнα(Selina) 开始了新一轮的男友海选。她要求她的男友要德智体美劳样样都全。首先进行的是文化知识竞赛。
Sεlιнα 精心准备了一套选择题，每个选择题有且只有一个正确答案。她邀请参赛男友们来答题，并回收了试卷准备批改。可是她却犯了愁。她不知道怎么快速地批改完这些试卷。她知道你是计算机大佬，就跑来请你写个程序帮她批改试卷。
Sεlιнα 会给你一份标准答案，再给你每个参赛男友的答卷。答卷中的每道题可能有一个答案， 也可能没有作答。你要做的是最后告诉 Sεlιнα 谁拿到了最高分，以及最高分的分数（分数为 分制）。Sεlιнα 喜欢优美的名字，所以如果有同样的分数，请告诉她其中字典序最小的选手名字。
不要偷懒哦！要是你告诉了 Sεlιнα 错误的答案，她会很生气的！

输入描述:

第一行两个整数 ，表示有 道选择题和 个参赛男友。第二行一个长为 的字符串，表示标准答案。其中第 个字母表示第 个选择题的答案。保证所有字母在  中。接下去 行，每两行表示一个参赛男友： 
 · 第一行一个字符串，表示参赛者姓名，保证姓名仅由大小写字母组成；
 · 第二行一个长为 的字符串，表示该参赛者的答案。其中第 个字母表示该参赛者对于第 个选择题的答案。保证所有字母在 中。 表示该参赛者未作答此题。

输出描述:

输出共两行，第一行是最高分的参赛男友姓名，第二行为其分数。分数为 分制，保留两位小数。若有多人同分，输出字典序最小的姓名。 

示例1

输入

5 3
ADBBC
spiderman
ADBAC
niconico
BDXBC
ekstieks
ACBBC

输出

ekstieks
80.00

备注:

  姓名长度  

 
模拟 排序

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 struct Nod {
 4     string name;
 5     string s;
 6     int ans;
 7 }nod[110];
 8 bool cmp(Nod &a, Nod &b) {
 9     if(a.ans != b.ans) return a.ans > b.ans;
10     else return a.name < b.name;
11 }
12 int main( ){
13     int n, m;
14     cin >> n >> m;
15     string s;
16     cin >> s;
17     for(int i = 0; i < m; i ++) {
18         cin >> nod[i].name;
19         cin >> nod[i].s;
20         nod[i].ans = 0;
21         for(int j = 0; j < s.length(); j ++) {
22             if(s[j] == nod[i].s[j]) nod[i].ans ++;
23         }
24     }
25     sort(nod,nod+m,cmp);
26     cout << nod[0].name << endl;
27     printf("%.2lf\n",100.0*nod[0].ans/s.length());
28     return 0;
29 }

 

H 武

题目描述

其次，Sεlιнα(Selina) 要进行体力比武竞赛。
在 Sεlιнα 所在的城市，有 个街区，编号为 ，总共有 条的街道连接这些街区， 使得每两个街区之间都直接或间接地有街道将它们相连。Sεlιнα 把通过了文化知识竞赛的参赛男友们召集到她家所在的街区 ，并以这个街区为起点，让所有参赛男友们向其他街区跑去。这些参赛者们被命令不准重复跑某条街道，而且在规定时间内要尽可能地跑远。比赛结束后，所有参赛者将停留在他们此时所在的街区。之后 Sεlιнα 开始视察结果。现在她知道每个街区都有一些她的参赛男友停留着，她现在想先去看看离她家第 近的街区。所以作为一位好帮手，你的任务是要告诉她所有街区中，离 Sεlιнα 家第  近的街区与 Sεlιнα 家之间的距离。 

输入描述:

第一行三个整数，，含义同题面描述。
接下去  行，每行三个整数，，表示从第 个街区到第 个街区有一条权值为 的街道相连。街区从 开始标号。

输出描述:

输出共一行，一个整数，表示所有街区与 Sεlιнα 家所在街区之间最近距离的第 

 小值。 

示例1

输入

3 3 2
1 2 4
2 3 5

输出

9

示例2

输入

6 4 3
1 2 7
2 3 2
2 4 2
2 5 10
3 6 3

输出

7

备注:

最短路径，输出第k近的就行。

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 #define INF 0x3f3f3f3f
 4 using namespace std;
 5 const int N = 100010;
 6 ll d[N];
 7 struct edge{
 8     ll to, cost;
 9 };
10 
11 vector<edge> g[N];
12 typedef pair<ll,ll> P;
13 void dijistra(ll s){
14     priority_queue<P,vector<P>,greater<P> > que;
15     d[s] = 0;
16     que.push(P(0,s));
17     while(!que.empty()){
18         P p = que.top();que.pop();
19         ll v = p.second;
20         if(d[v] < p.first) continue;
21         for(int i = 0; i < g[v].size(); i ++){
22             edge e = g[v][i];
23             if(d[e.to] > d[v] + e.cost){
24                 d[e.to] = d[v] + e.cost;
25                 que.push(P(d[e.to],e.to));
26             }
27         }
28     }
29 }
30 int main() {
31     ll n, p, k;
32     cin >> n >> p >> k;
33     for(int i = 0; i <= n; i ++) d[i] = 2e10;
34     for(int i = 0; i < n-1; i ++) {
35         ll u, v, w;
36         cin >> u >> v >> w;
37         edge e;
38         e.to = v;
39         e.cost = w;
40         g[u].push_back(e);
41         edge ee;
42         ee.to = u;
43         ee.cost = w;
44         g[v].push_back(ee);
45     }
46     dijistra(p);
47     sort(d+1,d+1+n);
48     cout << d[k+1] << endl;
49     return 0;
50 }

I 艺

题目描述

接下去，Sεlιнα(Selina) 又搞了个文艺竞演。
虽说是文艺竞演，其实只是为了满足 Sεlιнα 的内心企盼——看群男友献歌献舞。她排列好了各个参赛男友的节目顺序，然后将他们安排在两个舞台上表演，自己则在演播室里使用两台闭路电视同时观看。万万没想到的是，当一切准备就绪时，其中一台电视炸了，她不会修，也没有时间修。于是只能尴尬地使用一台闭路电视观看两个舞台上的节目。当然，这台电视不支持分屏同时观看，所以 Sεlιнα 只能不停地换台观看。现在，作为导演的 Sεlιнα 已经知道了两个舞台的节目 单以及每个节目 对于她所能产生的愉悦度 ，她想安排电视在每个时刻播放的频道（可以在某些时刻不看），使得自己能得到最大的愉悦度。现在请优秀的你告诉 Sεlιнα 最大能产生的愉悦度是多少。
要注意的是，文艺竞演没有广告插播，所以当一个节目结束时，另一个节目会立刻开始演出。 并且 Sεlιнα 看节目以分钟为单位，也就是说，她只能在每分钟结束的那一刻切换舞台。节目对 Sεlιнα 产生愉悦度是以分钟为单位的，也就是说，她看第 个节目每一分钟就会产生 的愉悦度。而 Sεlιнα 对节目的完整性丝毫不在意，没有完整地看一个节目是没有关系的。 

输入描述:

第一行三个数 ，表示舞台一有 个节目，舞台二有 个节目，总时长为 分钟。
接下去 行，每行两个整数 ，表示舞台一的第 个节目在第  分钟结束后开始，每分钟能产生愉悦度 。当一个节目开始时，这个舞台之前正在播放的节目直接停止，中间没有暂停。
接下去 行，每行两个整数 ，表示舞台二的第 个节目在第 分钟结束后开始，每分钟能产生愉悦度 。当一个节目开始时，这个舞台之前正在播放的节目直接停止，中间没有暂停。
数据保证每个舞台都有一个在 分钟时开始的节目（即最开始的节目），并且在同一个舞台中没有两个节目开始时间相同（即没有一个节目时长为 ）。数据不保证输入中每个舞台的 会从小到大排序。 

输出描述:

输出共一行，一个整数，表示最大的愉悦度。

示例1

输入

2 2 5
2 3
0 2
0 3
3 1

输出

15

说明

在这个样例中，Sεlιнα 在开始时观看频道二的节目，每分钟产生愉悦度 

 ；在第二分钟结束时刻切换到频道一，每分钟产生愉悦度 

 ，然后直到结束。总共产生愉悦度 

 。 

示例2

输入

3 4 17
8 3
0 10
9 10
7 15
0 6
16 9
14 8

输出

205

备注:

恶心的模拟题

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1e5+10;
 5 struct Nod{
 6     ll x, v;
 7 }a[N], b[N];
 8 bool cmp(Nod &x, Nod &y) {
 9     return x.x < y.x;
10 }
11 int main() {
12     ll n, m, t;
13     cin >> n >> m >> t;
14     for(int i = 0; i < n; i ++) cin >> a[i].x >> a[i].v;
15     for(int i = 0; i < m; i ++) cin >> b[i].x >> b[i].v;
16     a[n].x = t;
17     b[m].x = t;
18     sort(a,a+n,cmp);
19     sort(b,b+m,cmp);
20     ll now = 0, a1 = 0, b1 = 0;
21     ll ans = 0;
22     while(now < t) {
23         ll cnt;
24         if(a[a1].v > b[b1].v) {
25             cnt = a[a1].v;
26         } else cnt = b[b1].v;
27         ll pre = now;
28         now = min(a[a1+1].x,b[b1+1].x);
29         if(cnt > 0) ans += (now-pre)*cnt;
30         if(now == t) break;
31         if(now == a[a1+1].x) a1++;
32         if(now == b[b1+1].x) b1++;
33     }
34     cout << ans << endl;
35     return 0;
36 }

J 美

题目描述

最后，Sεlιнα(Selina) 开始了选美大赛。 一如既往地，Sεlιнα 想最大化自己的愉悦度。她品味十分独特，对“美”有自己独到的见解。 她给每位经过层层选拔来到这一关的参赛男友都定义了一个帅气值 。Sεlιнα 需要将这些参赛者排成一排，她对于这个排列的“美”值的定义是： 

其中 表示排列中第 个人的帅气值。特别地，当 时，有 。
她依旧想使自己获得最大的愉悦值，所以她要使这个排列的 值尽可能地大。聪明的你，快来告诉 Sεlιнα，这个最大的值是多少。 

输入描述:

第一行一个整数 ，表示有 个男友。
第二行 个整数，第 个数表示值 。 

输出描述:

输出共一行，一个整数，表示最大的 

 值。 

示例1

输入

5
7 3 15 12 8

输出

34

示例2

输入

7
-2 0 8 9 -5 3 10

输出

68

备注:

 
假设是1 2 3 4 5 
分成1 5 2 4 3  这样分就行

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 1e5+10;
 5 ll r[N], a[N];
 6 int main() {
 7     int n;
 8     cin >> n;
 9     for(int i = 1; i <= n; i ++) cin >> r[i];
10     ll ans = 0, cnt = 1;
11     sort(r+1,r+1+n);
12     for(int i = 1; i <= n; i += 2) {
13         a[i] = r[cnt++];
14     }
15     for(int i = n+(n%2?-1:0); i >= 1; i -= 2) {
16         a[i] = r[cnt++];
17     }
18     for(int i = 2; i <= n; i ++) ans += abs(a[i]-a[i-1]);
19     ans += abs(a[1]-a[n]);
20     cout << ans << endl;
21     return 0;
22 }