neerc专题

2015-2016 ACM-ICPC, NEERC, Moscow Subregional Contest C. Colder-Hotter

交互题首先三分x坐标，然后因为三分不准确，所以在附近震荡求精确值。其次同样的方法求出y坐标。注意，询问次数的上限是500。每次询问的时候， (x,y) (x,y)的两个坐标必须在 [0,1E9] [0,1E9]之间。 // whn6325689// Mr.Phoebe// http://blog.csdn.net/u013007900#incl

[Codeforces - Gym10081D (NEERC)] Distribution in Metagonia （构造+数的拆分）

Codeforces - Gym10081D (NEERC) 给定一个数，将其变成若干个数的和如果这些数有因子，那么只能是 2或 3 并且这些数两两不能除尽构造题如果这个数为 1,那么答案就为 1 若不为 1，那么如果他是奇数那么我减去最大的一个 3次幂转化为一个偶数，再不断地提出 2，变成一个奇数，循环直到其变为 1 所以这个数 N=3a1+2b1(3a2

[Codeforces - Gym100801H (NEERC)] Hash Code Hacker （字符串构造）

Codeforces - Gym100801H (NEERC) 给定一个字符串hash，为 ∑i=0len−1str[i]×31len−1−i \displaystyle\sum_{i=0}^{len-1} str[i]\times 31^{len-1-i} 求 K K个长度不超过 1000的字符串，使得他们的 hash值相等其中每个 hash值是 32位有符号整数，K≤1000K\l

例题4-1 古老的密码（Ancient Cipher，NEERC 2004，UVa1339）

原题链接：https://vjudge.net/problem/UVA-1339 分类：函数备注：思维分析：因为每种字母可以映射的字母不受限制，那么可以映射的字母出现的次数要相同即可，在两个字符串中都有相对应的字母出现的次数相同就能达到题目条件。作者把此题列出来的一个重要应该是为了让我们见识一下函数作为函数参数吧。毕竟本章是讲函数和递归。代码如下：按作者的意思来 #include<std

习题5-14 交易所（Exchange，ACM/ICPC NEERC 2006，UVa1598）

原题链接：https://vjudge.net/problem/UVA-1598 分类：STL综合备注：复杂模拟,阅读理解前言：在别处找到一篇很nice的翻译：https://blog.csdn.net/zju2016/article/details/75005098?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=

例题5-9 数据库（Database，ACM/ICPC NEERC 2009，UVa1592)

原题链接：https://vjudge.net/problem/UVA-1592 分类：<map> 备注：map的妙用分析：已经有过几个题通过map把某个数据以数字代表的经历了，这点其实不难想到。为了快一点遍历，不能搞四重循环，按紫书上说的，对于每两列一行行遍历，把之前发现的数据记录下来，如果发现重复的则输出答案然后进入下一个循环即可。代码如下： #include<iostream>#i

例题 7-14 网格动物（Lattice Animals, ACM/ICPC NEERC 2004, UVa1602）

原题链接：https://vjudge.net/problem/UVA-1602 分类：数据结构,好题备注：生成n连块，考验思维，打表代码与其它博客一样，似乎起源都是lrj老师。很神奇，也很好理解，翻转旋转很容易想到，平移依靠坐标的相对位置就感觉很奇妙。然后每次增块都是基于上一次的图形的。对set的应用也很巧妙。因为从(0,0)开始增块，因此当前连块的长宽就取最大的x,y再加一即可。

习题 8-9 K度图的着色（K-Graph Oddity, ACM/ICPC NEERC 2010, UVa1613）

原题链接：https://vjudge.net/problem/UVA-1613 分类：贪心法备注：简单思维题 #include<bits/stdc++.h>using namespace std;const int maxn=1e4+5;vector<int>e[maxn];int n,m,k,color[maxn];bool check(int x,int c){for(int

习题 8-10 奇怪的股市（Hell on the Markets,ACM/ICPC NEERC 2008, UVa1614）

原题链接：https://vjudge.net/problem/UVA-1614 分类：数学结论备注：思维，证明下面是抄的知乎DL的证明过程，两个重要的命题。补充：Si是从后往前算的。 #include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=1e5+5;ll a[maxn],su

例题 9-19 团队分组（Team them up!, ACM/ICPC NEERC 2001, UVa1627)

原题链接：https://vjudge.net/problem/UVA-1627 分类：0-1背包备注：二分图，背包变体按照紫书的思路，将不互相认识的连在一起，这样形成连通图必须要能够变为二分图，否则不合题意，然后黑白染色，两种颜色对应两个分组，互换一下分组，组员数量的差值就会变化，可以据此来进行DP。开始以为，只要对每个连通图看两种情况即可，每次都求出最优结果。WA了之后再看别人的解法

例题 10-6 无关的元素（Irrelevant Elements, ACM/ICPC NEERC 2004, UVa1635）

原题链接：https://vjudge.net/problem/UVA-1635 分类：基础数论备注：唯一分解定理，递推一开始想对每个数求出质因子的指数，然后看能不能符合条件，发现会T。看了下别人的，原来是对m的每个质因子进行判断。最近可能退步了许多，只会想暴力，应该要多换换角度来看问题，不能一根筋。 #include<bits/stdc++.h>using namespace std;

2018-2019 ICPC, NEERC, Northern Eurasia Finals G-Guest Student（思维）

题目链接：http://codeforces.com/contest/1089/problem/G 题意：给你一个t代表t组数据，然后一个k，代表你需要上k节课，下一行有七个数代表一周七天，1是你需要上的课，0是不需要上的课，第一次上课你可以从周一到周日选一天从这天开始上课，接下来只能按顺序一天一天的上课（0也要上课），比如k = 3，序列为1 0 1 1 0 0 0，则需要上四节课，让你输出

2018-2019 ICPC, NEERC, Northern Eurasia Finals L- Lazyland(思维)

题目链接：http://codeforces.com/contest/1089/problem/L 题意：是有n个人，k份工作，每份工作的编号是1-k，然后输入n个ai，第二行输入n个bi，ai代表当前第i个人所选的工作编号，bi代表如果让这个人去换一个工作所需要花费的时间，现在要让每一份工作都有人去做，问最少需要花费多少时间可以实现。思路：就是在输入的时候把每个工作的人数记录下来然后记录一

习题5-1 代码对齐（Alignment of Code, ACM/ICPC NEERC 2010, UVa1593）

输入若干行代码，要求各列单词的左边界对齐且尽量靠左。单词之间至少要空一格。每个单词不超过80个字符，每行不超过180个字符，一共最多1000行，样例输入与输出如图所示。 //代码对齐 //思路：统计每列最长的单词不够长度补空格#include<cstdio>#include<iostream>#include<vector>#include<sstream>using namesp

2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest C. Carpet (树链剖分+构造)

http://codeforces.com/gym/101611/problem/C 题意：给定一棵 n n n个结点的树( n ≤ 100000 n\leq100000 n≤100000)，将其放入 1000000 ∗ 20 1000000*20 1000000∗20的方格中，使其任意两条边互不相交，求各个点的位置坐标。看了题解才想到轻重链剖分。因为该方格的特点是x轴很长，y轴比较短，所以将