Day 1的题难度上来说不算太高，但是T2和T3还是有一定的思维量的。
一个比较好的开始。虽然AK的人只有几个。。
（懒得去翻result了。。忘了当时拿了多少分了
（哦，前两天我们机房是没有成绩的，我好像忘了这一点。
那么我们直奔主题吧。
T1：删除
文件名del.cpp/c/pas输入文件 输出文件 时间限制 空间限制del.in del.out 1s 512MB题目描述现在，我的手上有 n 个数字，分别是 a1, a2, a3, ..., an。我现在需要删除其中的 k 个数字。当然我不希望随随便便删除，我希望删除 k个数字之后，剩下的 n − k 个数中有最多的不同的数。输入格式第一行两个正整数 n 和 k，含义如题目描述。接下来一行，有 n 个非负整数，分别是 a1到 an。输出格式一共一行，一个整数 ans，表示删除了 k 个数字后最多的不同的数的个数。样例输入4 11 3 1 2样例输出3样例解释如果删去第一个 1:在［3，1，2］中有 3 个不同的数如果删去 3:在［1，1，2］中有 2 个不同的数如果删去第二个 1:在［1，3，2］中有 3 个不同的数如果删去 2:在［1，3，1］中有 1 个不同的数数据范围对于 30% 的数据，n ≤ 10，a ≤ 10。对于 60% 的数据，n ≤ 100，a ≤ 100。对于 80% 的数据，n ≤ 105，a ≤ 105对于 100% 的数据，n ≤ 105，a ≤ 109
这道题算是比较基础的一道题了。当时我在考场上想到了一个自认为是正解的做法，但下午讲解时被告知是80分的伪正解做法。。
我太菜了.jpg
我当时想的是，开一个数组，统计每个数字出现的次数，既然我们要删除k个数字而且要保证删除后的数字是最多的，那很显然想到要先删除重复的。
统计一下有多少个重复的数字，将这个数与k比较。
如果k比这个数小或者等于这个数，那说明我们删除k个数对数字的种类没有任何影响。我们仅仅删除了重复的数字而已。那么答案就是数字的种数。
如果k比这个数字大，那说明我们即使全部删除所有的重复数字，也达不到k这个值，那只好再去删除不重复的数字，我们无需关心到底是删除了哪个数，而只需要统计出数字有多少种即可。
假设有m种数字，删除k个数，设x等于删除完所有重复数字后还需要删除多少数，那么根据上边的分析，答案应该是m-x.
100分做法：
善用排序。我们完全可以不用统计每个数字出现的次数，只需要读入之后sort（salt）一下，这样相同的数字会排在一起，我们就能统计出有多少相同的数字可供删除，以及数字的种类。
GTY哥哥的std：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std; const int max_n = 1e5 + ;
int n, k, a[max_n]; int main() {
freopen("del.in", "r", stdin);
freopen("del.out", "w", stdout); cin >> n >> k; for (int i = ; i <= n; i++)
cin >> a[i]; sort(a + , a + + n); int multi = ;
for (int i = ; i <= n; i++)
if (a[i] == a[i - ]) multi++;
if (k <= multi) cout << n - multi << endl;
else cout << n - multi - (k - multi) << endl;
}
T2：同花顺
题目描述所谓同花顺，就是指一些扑克牌，它们花色相同，并且数字连续。现在我手里有 n 张扑克牌，但它们可能并不能凑成同花顺。我现在想知道，最少更换其中的多少张牌，我能让这 n 张牌都凑成同花顺？输入格式第一行一个整数 n，表示扑克牌的张数。接下来 n 行，每行两个整数 a 和 b 。其中 ai表示第 i 张牌的花色，bi表示第i 张牌的数字。输出格式一行一个整数，表示最少更换多少张牌可以达到目标。样例输入 151 11 21 31 41 5样例输出 1样例输入 251 91 102 112 122 13样例输出 22数据范围对于 30% 的数据，n ≤ 10。对于 60% 的数据，n ≤ 105，1 ≤ a ≤ 105，1 ≤ b ≤ n。对于 100% 的数据，n ≤ 105，1 ≤ ai, bi ≤ 109。
当时在考场上只想到了暴力搜索。。。不过仔细一考虑，这题其实挺简单的。
数据量比较大，需要我们进行离散化，去除相同的牌。一个显然的贪心就是找到花色出现次数最多的花色，则其他的花色的牌一定要换掉。
做到这里，应该能拿60.
100分做法：我们枚举在已有的同花顺序列上的最后一张牌，去寻找可能的第一张牌。我们令last为当前牌作为同花顺序列的最后一张牌时，可能的第一张牌。如果当前牌的点数是a，last牌的点数是b，则必须要满足a-b+1≤n。
GTY哥哥的std：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std; const int max_n = 1e5 + ; struct card {
int color, value;
bool operator < (const card &o) const {
return color < o.color || (color == o.color && value < o.value);
}
bool operator == (const card &o) const {
return color == o.color && value == o.value;
}
} a[max_n];
int n; int main() {
freopen("card.in", "r", stdin);
freopen("card.out", "w", stdout);
cin >> n;
for (int i = ; i <= n; i++) {
cin >> a[i].color >> a[i].value;
} sort(a + , a + + n);
int ori_n = n;
n = unique(a + , a + + n) - (a + ); int last_one = ;
int max_ans = ;
for (int i = ; i <= n; i++) {
if (i == || a[i].color != a[i - ].color)
last_one = i;
while (a[i].value - a[last_one].value + > ori_n)
last_one++;
max_ans = max(max_ans, i - last_one + );
} cout << ori_n - max_ans << endl;
}
T3：等式
题目描述我有 n 个式子对于每一个式子，要么是 x = x 的形式，要么是 x ≠ x 的形式。现在我给出这 n 个式子，你要告诉我，这 n 个式子是否可能同时成立。输入格式每一个测试点有多组测试数据。第一行有一个整数 T，表示测试数据的组数。对于每一组测试数据，第一行包含一个正整数 n，表示式子的数目。接下来 n 行，每行三个整数 i，j，e，描述一个式子。如果 e = 1，则这个式子为 x = x 。如果 e = 0，则这个式子是 x ≠ x 。输出格式对于每一个测试数据输出一行。如果存在一种方案，使得所有的式子都被满足，输出“YES”（不包含引号）。否则输出“NO”（不包含引号）。样例输入 1221 2 11 2 021 2 12 1 1样例输出 1NOYES6样例输入 2231 2 12 3 13 1 141 2 12 3 13 4 11 4 0样例输出 2YESNO数据范围对于 20% 的数据，n ≤ 10。对于 40% 的数据，n ≤ 100。对于 70% 的数据，n ≤ 105，1 ≤ i, j ≤ 104对于 100% 的数据，n ≤ 105，1 ≤ i, j ≤ 109 ，1 ≤ t ≤ 10。
这题其实就是NOI2015D1T1那个等价表达式。。
不过GTY哥哥为我们提供了一个算法，虽然只有70分但是听起来很有趣，读者不妨一试。
floodfill算法。将所有的等式关系建成一个图。然后我们循环每一个点，如果当前点还没有被访问过，则从这个点开始，dfs遍历所有和它有边相连的点，并标记。注意，标记是不一样的。从1开始遍历就标记为1，从2开始遍历就标记为2。然后我们检查所有的不等式。如果要求不等的两个点i和j标记相同，说明它们被要求“等于”，就输出NO。如果所有要求不等的两个点都不在一个联通块内，则输出YES。
正解应该是离散化+并查集，我在Day2内容整理里稍微说了一下。。
GTY哥哥的std：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std; const int max_n = 2e5 + ; struct data {
int x, y, e;
bool operator < (const data &o) const {
return e > o.e;
}
} a[max_n]; int fa[max_n];
int tmp[max_n], tot, n; int getfather(int x) {
if (fa[x] == x) return x;
return fa[x] = getfather(fa[x]);
} inline int getnum() {
int ans = ; char c; bool flag = false;
while (!isdigit(c = getchar()) && c != '-');
if (c == '-') flag = true; else ans = c - '';
while (isdigit(c = getchar())) ans = ans * + c - '';
return ans * (flag ? - : );
} int main() {
freopen("equ.in", "r", stdin);
freopen("equ.out", "w", stdout); int t = getnum();
while (t--) {
n = getnum();
tot = ;
for (int i = ; i <= n; i++) {
a[i].x = getnum();
a[i].y = getnum();
a[i].e = getnum();
tmp[++tot] = a[i].x;
tmp[++tot] = a[i].y;
} sort(a + , a + + n);
sort(tmp + , tmp + + tot);
tot = unique(tmp + , tmp + + tot) - (tmp + ); for (int i = ; i <= tot; i++) fa[i] = i; bool isok = true;
for (int i = ; i <= n; i++) {
a[i].x = lower_bound(tmp + , tmp + + tot, a[i].x) - tmp;
a[i].y = lower_bound(tmp + , tmp + + tot, a[i].y) - tmp;
if (a[i].e == ) fa[getfather(a[i].x)] = getfather(a[i].y);
else {
if (getfather(a[i].x) == getfather(a[i].y)) {
isok = false;
break;
}
}
} if (isok) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
你问我为啥这些标程都不是我写的？
源代码丢了……只能用一下天宇哥哥的std了。。。