NOIP模拟 17.8.14

NOIP模拟17.8.14

（天宇哥哥考察细心程度的题）

A 删除
文件名输入文件输出文件时间限制空间限制
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 1
1 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，ai ≤ 10。
对于 60% 的数据，n ≤ 100，ai ≤ 100。
对于 80% 的数据，n ≤ 105，ai ≤ 105。
对于 100% 的数据，n ≤ 105，ai ≤ 109

【题解】

读错题，以为必须只出现一次才能被记入，还以为删除操作的次数<=k。。。作孽啊

很水的，排序，去重，直接减。我由于数次读错题，代码爆炸。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <set>
 7 
 8 const int INF = 0x3f3f3f3f;
 9 const int MAXN = 200000 + 10;
10 
11 inline void read(int &x)
12 {
13     x = 0;char ch = getchar(), c = ch;
14     while(ch < '0' || ch > '9')c = ch, ch = getchar();
15     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
16     if(c == '-')x = -x;
17 }
18 
19 int n, num[MAXN], cnt, shu[MAXN], k, ans;
20 
21 int main()
22 {
23     read(n);read(k);
24     for(register int i = 1;i <= n;++ i)read(num[i]);
25     std::sort(num + 1, num + 1 + n);
26     ++ cnt;++ ans;
27     for(register int i = 2;i <= n;++ i)
28         if(num[i] == num[i - 1])++shu[cnt];
29         else if(shu[cnt])++shu[cnt], ++cnt, ++ans;
30         else ++ans;
31     if(shu[cnt])++shu[cnt];
32     else --cnt;
33     std::sort(shu + 1, shu + cnt + 1);
34     register int i;
35     for(i = 1;i <= cnt;++ i)
36     {
37         if(k - shu[i] + 1 < 0)
38         {
39             k = 0;break;
40         }
41         else k -= shu[i] - 1;
42     }
43     printf("%d", ans - k);
44     return 0;
45 }

My T1

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 const int MAXN = 100005;
 5 
 6 int n, m, k, a[MAXN];
 7 
 8 int main(){
 9     scanf("%d%d", &n, &k);
10     for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
11     sort(a + 1, a + 1 + n);
12     m = unique(a + 1, a + 1 + n) - a - 1;
13     printf("%d
", min(n - k, m));
14     return 0;
15 }

Std T1

B 同花顺
文件名输入文件输出文件时间限制空间限制
card.cpp/c/pas card.in card.out 1s 512MB
【题目描述】
所谓同花顺，就是指一些扑克牌，它们花色相同，并且数字连续。
现在我手里有 n 张扑克牌，但它们可能并不能凑成同花顺。我现在想知道，最
少更换其中的多少张牌，我能让这 n 张牌都凑成同花顺？
【输入格式】
第一行一个整数 n，表示扑克牌的张数。
接下来 n 行，每行两个整数 ai 和 bi。其中 ai 表示第 i 张牌的花色，bi 表示第
i 张牌的数字。
【输出格式】
一行一个整数，表示最少更换多少张牌可以达到目标。
【样例输入 1】
5
1 1
1 2
1 3
1 4
1 5
【样例输出 1】
0
【样例输入 2】
5
1 9
1 10
2 11
2 12
2 13
【样例输出 2】
2
【数据范围】
对于 30% 的数据，n ≤ 10。
对于 60% 的数据，n ≤ 105，1 ≤ ai ≤ 105，1 ≤ bi ≤ n。
对于 100% 的数据，n ≤ 105，1 ≤ ai, bi ≤ 109

【题解】

再次理解错题。我以为 2 2 3 4 5也是同花顺。。。。于是没有去重。。

于是炸掉

正解是先去重，然后按花色排，花色相同按数字升序排。对每种花色，找一段[l,r]，让其他牌插空，

使得num[r] - num[i] - 1 <= n - 2，这样答案就可以更新为min(ans, n - (r - l + 1))

这里显然可以用尺取法，然而我修改的时候，左端点是固定不动的，于是愉快的炸掉。。炸掉。。。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #define min(a, b) ((a) < (b) ? (a) : (b))
 7 
 8 const int INF = 0x3f3f3f3f;
 9 const int MAXN = 2000000 + 10;
10 
11 inline void read(int &x)
12 {
13     x = 0;char ch = getchar(), c = ch;
14     while(ch < '0' || ch > '9')c = ch, ch = getchar();
15     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
16     if(c == '-')x = -x;
17 }
18 
19 struct Node
20 {
21     int hua, num;
22     Node(int _hua, int _num){hua = _hua;num = _num;}
23     Node(){}
24 }pai[MAXN];
25 
26 int n, ans;
27 
28 bool cmp(Node a, Node b)
29 {
30     return a.hua == b.hua ? a.num < b.num : a.hua < b.hua;
31 }
32 
33 int main()
34 {
35     read(n);
36     for(register int i = 1;i <= n;++ i)read(pai[i].hua), read(pai[i].num);
37     std::sort(pai + 1, pai + 1 + n, cmp);
38     register int p = 1;
39     for(register int i = 2;i <= n;++ i)
40         if(pai[p].hua != pai[i].hua || pai[p].num != pai[i].num)
41             pai[++p].hua = pai[i].hua,pai[p].num = pai[i].num;
42     register int now = pai[1].hua, l = 1, ok = 1;
43     ans = n - 1;
44     for(register int i = 2;i <= p;++ i)
45     {
46         if(pai[i].hua == now)
47         {
48             if(pai[i].num - pai[l].num - 1 <= n - 2)
49                 ans = min(ans, n - (i - l + 1));
50             else 
51             {
52                 ans = min(ans, n - (i - l));
53                 while(pai[i].num - pai[l].num - 1 > n - 2 && l < i) ++ l;
54                 if(l <= i)ans = min(ans, n - (i - l + 1));
55             }
56         }
57         else
58             now = pai[i].hua, l = i, ok = 1;
59     }
60     printf("%d" ,ans);
61     return 0;
62 }

My T2

 1 /*Orz gty big brother! 233*/
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 const int MAXN = 100005;
 6 
 7 struct Cards{
 8     int a, b;
 9     bool operator < (const Cards& rhs) const{
10         return a == rhs.a ? b < rhs.b : a < rhs.a;
11     }
12     bool operator == (const Cards& rhs) const{
13         return a == rhs.a && b == rhs.b;
14     }
15 }cd[MAXN];
16 int n, m;
17 
18 int solve(int s, int t){
19     int i, j, ret = 0;
20     for(i = j = s; i <= t; ++ i){
21         while(j < t && cd[j + 1].b - cd[i].b < n) ++ j;
22         ret = max(ret, j - i + 1);
23     }
24     return ret;
25 }
26 int main(){
27     int i, j, ans = 0;
28     scanf("%d", &n);
29     for(i = 1; i <= n; ++ i)
30         scanf("%d%d", &cd[i].a, &cd[i].b);
31     sort(cd + 1, cd + 1 + n);
32     m = unique(cd + 1, cd + 1 + n) - cd - 1;
33     for(i = 2, j = 1; i <= m; ++ i)
34         if(cd[i].a != cd[i - 1].a){
35             ans = max(ans, solve(j, i - 1));
36             j = i;
37         }
38     ans = max(ans, solve(j, i - 1));
39     printf("%d
", n - ans);
40     return 0;
41 }

Std T2

C 等式
文件名输入文件输出文件时间限制空间限制
equ.cpp/c/pas equ.in equ.out 2s 512MB
【题目描述】
我有 n 个式子
对于每一个式子，要么是 xi = xj 的形式，要么是 xi ̸= xj 的形式。
现在我给出这 n 个式子，你要告诉我，这 n 个式子是否可能同时成立。
【输入格式
每一个测试点有多组测试数据。
第一行有一个整数 T，表示测试数据的组数。
对于每一组测试数据，第一行包含一个正整数 n，表示式子的数目。
接下来 n 行，每行三个整数 i，j，e，描述一个式子。如果 e = 1，则这个式子
为 xi = xj。如果 e = 0，则这个式子是 xi ̸= xj。
【输出格式】
对于每一个测试数据输出一行。如果存在一种方案，使得所有的式子都被满足，
输出“YES”（不包含引号）。否则输出“NO”（不包含引号）。
【样例输入 1】
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
【样例输出 1】
NO
YES
【样例输入 2】
2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0
【样例输出 2】
YES
NO
【数据范围】
对于 20% 的数据，n ≤ 10。
对于 40% 的数据，n ≤ 100。
对于 70% 的数据，n ≤ 105，1 ≤ i, j ≤ 104。
对于 100% 的数据，n ≤ 105，1 ≤ i, j ≤ 109，1 ≤ t ≤ 10。

【题解】

离散化，先处理等号，并查集维护，然后看不等号，是否满足条件。竟然是NOI2015D1T1，NOI2015果然很水，，

唯一A了的一道题

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 
 7 const int INF = 0x3f3f3f3f;
 8 const int MAXN = 2000000 + 10;
 9 
10 inline void read(int &x)
11 {
12     x = 0;char ch = getchar(), c = ch;
13     while(ch < '0' || ch > '9')c = ch, ch = getchar();
14     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
15     if(c == '-')x = -x;
16 }
17 
18 int t, n, fa[MAXN << 1], num[MAXN << 1], cnt[MAXN << 1], e[MAXN];
19 
20 bool cmp(int a, int b)
21 {
22     return num[a] < num[b];
23 }
24 
25 bool cmpp(int a, int b)
26 {
27     return e[a] > e[b];
28 }
29 
30 int find(int x)
31 {
32     return fa[x] == x ? x : fa[x] = find(fa[x]);
33 }
34 
35 int main()
36 {
37     read(t);
38     for(;t;--t)
39     {
40         read(n);
41         n <<= 1;
42         for(register int i = 1;i <= n;i += 2)read(num[i]), read(num[i + 1]), read(e[(i + 1)/2]), cnt[i] = fa[i] = i, cnt[i + 1] = fa[i + 1] = i + 1;
43         std::sort(cnt + 1, cnt + 1 + n, cmp);
44         register int now = 1, pre = num[cnt[1]], tmp;num[cnt[1]] = now;
45         for(register int i = 2;i <= n;++ i)
46         {
47             tmp = num[cnt[i]];
48             if(num[cnt[i]] != pre)++now;
49             num[cnt[i]] = now;
50             pre = tmp;
51         }
52         n >>= 1;
53         register int f1,f2;
54         for(register int i = 1;i <= n;++ i)
55         {
56             if(e[i])
57             {
58                 f1 = find(num[(i << 1) - 1]), f2 = find(num[(i << 1)]);
59                 fa[f1] = f2;
60             }
61         }
62         for(register int i = 1;i <= n;++ i)
63         {
64             if(!e[i])
65             {
66                 f1 = find(num[(i << 1) - 1]), f2 = find(num[(i << 1)]);
67                 if(f1 == f2)
68                 {
69                     printf("NO
");
70                     goto L1;
71                 }
72             }
73         }
74         printf("YES
");
75 L1:        ;
76     }
77     return 0;
78 }

My T3

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 const int MAXN = 100005;
 5 
 6 int u[MAXN], v[MAXN], e[MAXN], f[MAXN << 1], n, tmp[MAXN << 1];
 7 
 8 int find(int x){return x == f[x] ? x : f[x] = find(f[x]);}
 9 void merge(int x, int y){f[find(x)] = find(y);}
10 void solve(){
11     int i;
12     scanf("%d", &n);
13     for(i = 1; i <= n * 2; ++ i) f[i] = i;
14     for(i = 1; i <= n; ++ i){
15         scanf("%d%d%d", &u[i], &v[i], &e[i]);
16         tmp[i * 2 - 1] = u[i], tmp[i * 2] = v[i];
17     }
18     sort(tmp + 1, tmp + 1 + n * 2);
19     for(i = 1; i <= n; ++ i){
20         u[i] = lower_bound(tmp + 1, tmp + 1 + n * 2, u[i]) - tmp;
21         v[i] = lower_bound(tmp + 1, tmp + 1 + n * 2, v[i]) - tmp;
22         if(e[i] && find(u[i]) != find(v[i])) merge(u[i], v[i]);
23     }
24     for(i = 1; i <= n; ++ i){
25         if(e[i]) continue;
26         if(find(u[i]) == find(v[i])){
27             printf("NO
");
28             return;
29         }
30     }
31     printf("YES
");
32 }
33 int main(){
34     int testcase;
35     scanf("%d", &testcase);
36     while(testcase --)
37         solve();
38     return 0;
39 }

Std T3

【总结】

连续读错两道题愉快考炸了。。。本来是三道送分题。。。细节处理和审题还要加强。。