CSP-J/S 第一轮知识点选讲 NOIP（全国青少年信息学奥林匹克竞赛）于2019年取消。取而代之的是由CCF推出的非专业级软件能力认证，也就是现在的CSP−J/S。作为一名于2019年1月入OI的蒟蒻OIer，没能参加NOIP是我一生的遗憾。但在遗憾之余，我不得不备战CSP的认证。而CSP非专业级认证的第一轮（也就是NOIP初赛）常常使某些大神OIer（就是对基础知识不太了解）无缘复赛...所以今天来盘一下初赛知识点，顺带着自己也学习一下...... 信息学史及基本知识 一、信息学及计算机史 计算机的顶级奖项：图灵奖、冯·诺依曼奖 图灵奖：由ACM（美国计算机协会）设立于1966年...

今天考了一道分层图，本来是一道板题，结果我被误导了，想成了 架设电话线一题，考完写炸了才发现，架设电话线只需要求出第k+1大的长度，只需要满足局部最优==，但是飞行线路要使总和最小，只能用分层图，然后我翻了半天标签，找到了这道题。 link 但是当旁边LH看到之后，他告诉我，这是一道DP。 结果我没看出来。。。 分层图倒是很简单。 Sulotion step1 首先，他可以在图上到处走动，所以很自然地可以建一张图，所有的边权都是0。 然后这道题只与水晶球的价格有关，所以我们把点权搬到边权上面。 step2 因为他只进行一次买卖，所以有下面两种情况： 假设从\(u\)到\(v\)，水晶球在\...

struct Matrix { int r, c; LL m[MAXN][MAXN]; Matrix(){} Matrix(int r, int c) : r(r), c(c){}; void clear() { memset(m, 0, sizeof(m)); } void init() { for (int i = 1; i <= r; i++) m[i][i] = 1; } Matrix operator * (const Matrix B) const { Matrix C(r, B.c); for (int i = 1; i <= ...

刚刚听了jmy讲他的证明方法，大致意思就是树上的任意一点所能到达的最远距离一定会在直径的两个端点上。 但我认为反证法其实来得更快。思路如下： 证明： 反证法。假设已经用两次bfs/dfs求得的直径为\(AB\),且\(AB\)上有一点\(N\)。如果\(AB\)不是这颗树的直径，那么一定存在一条链\(CD\)，使得\(CD > AB\)，不妨设\(CD\)与\(AB\)的交点为\(M\)，所以\(NB > NC\)即可以得到\(MB > MC\)，可以得到\(MB + MD > MC + MD\)所以\(CD\)不是树的直径，与假设矛盾。故假设不成立，原命题成立。 证...

假日住宿 题目描述 给出一棵\(N\)节点的树，每个节点代表一个城市，每个城市有一个人，每个人离开自己的城市到另一个城市，每个城市只能有一个人，问这\(N\)个人移动距离和的最大值。 输入格式 输入的第一行包含一个整数 \(T(1<=t<=10)\)，表示测试用例的数量。每个测试用例包含几行。 第一行包含一个整数\(2<=N<=10^5\) ，代表城市数。 然后接下来的行分别包含三个整数\(X， Y， Z\) 意味着在城市\(X\)和城市\(Y\)之间有一条高速公路，其长度为\(Z\)。 您可以假设所有城市都已连接并且高速公路是双向的。 输出格式 输出每个样...

多校联考 CSP-JS 2019 第三次模拟赛Solutions 前言 Q:为什么叫入门提高级? A:因为前两题手滑出的偏难，于是打算通过题面给大家一点安慰。后面两道难度还好吧... 《历史上的今天》解题报告 出题人: Panda_hu 前言 这是一道简单的大模拟题。 首先很抱歉这道题完全不符合T1的难度，原来打算放在T2的... 大概看了题面也知道我为什么要出这道题了... 主要考察参赛者的模拟能力。 其实我写完标程也挺惊讶的...居然会有50多行... 得分估计 大多数同学在90分以上，少数同学可能会失误。 算法1:针对测试点1-5 将输入数据去掉日期原样输出即可。 ...

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int MAXN = 1e3 + 5; const int MAXM = 2 * 1e3 + 5; int n, m, head[MAXN], cnt; struct node { int to, dis, next; } a[MAXM]; void AddEdge(int u, int v, int w) { a[++cnt].to = v; a[cnt].dis = w;...

数你太美【第一周】 题目描述 PB 获得了两个正整数数列 \({a_i}\) , \({b_i}\) ，长度分别为 n , m ，其中每个数都小于 10。 定义一个正整数是“美丽的正整数”，当且仅当:这个数的十进制表示中，至少有一个 数位上的数在数列 a_i 出现过，至少有一个数位上的数在数列 b_i 出现过。现在 PB 希 望求出最小的“美丽的正整数”。 输入格式 第一行，两个正整数 n , m ; 第二行，n 个正整数，第 i 个为 a_i ; 第三行，m 个正整数，第 i 个为 b_i 。 输出格式 一行，一个正整数表示最小的“美丽的正整数”。 样例 样例输入 样例...

原始生物 分析 一句话题意： 给定一张图，将其扩展成欧拉回路。 如果是欧拉回路，那么就应该在边上再加一 否则直接加上入度和出度间的较大者。 end。。。 判环 void dfs(int x, int root) { vis[x] = 1;//标记 if (in[x] != out[x]) { c[root] = 0; } for (int i = 0; i < G[x].size(); i++) { if (vis[G[x][i]] == 0) dfs(G[x][i], root); } } 代码 #include <vector> ...

Ant Trip 分析 题意很简单，爆搜的时间复杂度比较高，不考虑。 应该使用欧拉回路的相关知识求解。 intn() 输入时将两个节点的入度都加一（无向），然后将两个节点合并在一个连通图中. for (int i = 1, u, v; i <= m; i++) { scanf ("%d %d", &u, &v); in[v] ++, in[u] ++; UnionSet(u, v); } TFW居然都不知道要将两个节点合并在一个连通图中 work() step1 从1~n循环，依次枚举，记录每个连...

叶子清除计划【第五周】 题目描述 ⼩Y同学是⼀位数据结构⼤师同时也是⼀位园艺⼤师。 秋天到了，⼩Y同学需要对学校内的⼀棵树展现他顶尖的修叶⽔平。 学校内的这棵树是⼀颗拥有n个点的⽆根树，每次⼩Y会删去所有的叶⼦节点（即度数小于等于1的节点)，直到所有的点都被删除了为⽌。 ⼩Y现在想问你对于每个点，求出它是第⼏次操作中被删除的。 输入格式 第⼀⾏⼀个数字n，表⽰树上节点个数 接下来n−1⾏，每⾏两个数字u,v，表⽰树上的⼀条边。 输出格式 ⼀⾏n个数字，第i个数字表⽰节点i在第⼏次操作中被删除。 样例 样例输入1: 5 1 2 1 3 2 4 2 5 样例输出1: ...

年功序列 分析 此题如果没有Chtholly年纪大了记忆力未必好，如果第\(i\)个序列与前\(i−1\)个序列冲突的话那么就只需要考虑前\(i−1\)个序列就好了的限制，就会是一道\(topsort\)的板题。 判断是否有环 建立邻接表 输入时前后相连，建立邻接表，如果无环则会形成一个长链。 判环 从\(x[1]\)开始判断，如果有环，就直接退出循环。 具体方法 bool check(int x) { for (int i = 0; i < G[x].size(); i++) { if (vis[G[x][i]] == 1) {//如果已经访问过，就说明有环存在...

题目链接 分析 一道树状数组，但坑点比较多。。。 首先在草稿纸上画图可以得知：星星的等级与\(x\)无关，至于\(y\)的大小有关，于是我们可以根据输入顺序一一将其插入树状数组进行维护，此星星的等级其实就是在插入前以\(1\)~星星的\(y\)的星星数量和。 注意 星星的坐标是从\((0, 0)\)开始存，但树状数组不能够维护，所以要提前将所有星星的\(x\)加上一。(如果在求和函数中把限度跳到0就会卡死循环我就错了) 代码 #include <cstdio> #include <cstring> #include <iostream> #inc...