9.27小测试

T1:删除

题目

现在,我的手上有 n 个数字,分别是 a1, a2, a3, …, an。
我现在需要删除其中的 k 个数字。当然我不希望随随便便删除,我希望删除 k
数字之后,剩下的 n − k 个数中有最多的不同的数。

题解

排序去重 有m种数 然后输出min(m, n-k)
解释:如果抛去k张牌后有超过m张牌 因为只有m种牌 所以答案为m 如果抛去k张牌后有少于m张牌
那么就可以保证只剩n-k张牌不同的牌

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define LL long long
#define Max(x, y) (x >= y ? x : y)
#define Min(x, y) (x <= y ? x : y)
#define MM(x, y) memset(x, y, sizeof(x))
#define F(i, x, y) for(register int i=x; i<=y; i++)
#define R(i, x, y) for(register int i=x; i>=y; i--)
using namespace std;
inline void in(int &x)
{
static int ch; static bool flag;
for(flag=false, ch=getchar(); ch<'0'||ch>'9'; ch=getchar()) flag |= ch=='-';
for(x=0; isdigit(ch); ch=getchar()) x = (x<<1) + (x<<3) + ch - '0';
x = flag ? -x : x;
}
int n, k, a[100005], b[100005];
int sum[100005];
inline int work()
{
freopen("del.in","r",stdin); freopen("del.out","w",stdout);
in(n); in(k);
F(i, 1, n) in(a[i]), b[i] = a[i];
sort(b + 1, b + n + 1);
int m = unique(b + 1, b + n + 1) - b - 1;
printf("%d\n", Min(n-k, m));
return 0;
}
int TAT = work();
int main() {;}

T2:同花顺

题目

所谓同花顺,就是指一些扑克牌,它们花色相同,并且数字连续。
现在我手里有 n 张扑克牌,但它们可能并不能凑成同花顺。我现在想知道,最
少更换其中的多少张牌,我能让这 n 张牌都凑成同花顺?

题解

先去重 再按照花色排序 然后花色相同再按照数字排序 枚举每一种花色找一段区间[l,r]然后
让其他牌往区间内进行插 区间要满足num[r]-num[l]+1<=n-2 这样就可以保证可以剩余的牌填
满区间 更新ans=Max(ans, l-r+1) 此时求解的ans是有ans张牌不需要动 最终的答案Ans=n-ans;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define LL long long
#define Max(x, y) (x >= y ? x : y)
#define Min(x, y) (x <= y ? x : y)
#define MM(x, y) memset(x, y, sizeof(x))
#define F(i, x, y) for(register int i=x; i<=y; i++)
#define R(i, x, y) for(register int i=x; i>=y; i--)
using namespace std;
inline void in(int &x)
{
static int ch; static bool flag;
for(flag=false, ch=getchar(); ch<'0'||ch>'9'; ch=getchar()) flag |= ch=='-';
for(x=0; isdigit(ch); ch=getchar()) x = (x<<1) + (x<<3) + ch - '0';
x = flag ? -x : x;
}
int n;
struct node{
int a, b;
bool operator < (const node &t) const {return a==t.a ? b<t.b : a<t.a;}
bool operator == (const node &t) const {return a==t.a && b==t.b;}
}ca[100005];
inline int solve(int l, int r)
{
int ret = 0, i, j;
for (i=j=l; i<=r; i++) {
while(j+1<=r && ca[j+1].b-ca[i].b<n) j++;
ret = Max(ret, j-i+1);
}
return ret;
}
inline int work()
{
freopen("card.in","r",stdin); freopen("card.out","w",stdout);
in(n);
F(i, 1, n) in(ca[i].a), in(ca[i].b);
sort(ca+1, ca+n+1);
int m=unique(ca+1, ca+n+1)-ca-1;
int i, j, ans=0;
for (i=2, j=1; i<=m; i++) {
if (ca[i].a != ca[i-1].a) {
ans = Max(ans, solve(j, i-1));
j = i;
}
}
ans = Max(ans, solve(j, i-1));
printf("%d\n", n-ans);
return 0;
}
int TAT = work();
int main() {;}

T3:等式

题目

我有 n 个式子
对于每一个式子,要么是 xi = xj 的形式,要么是 xi ̸= xj 的形式。
现在我给出这 n 个式子,你要告诉我,这 n 个式子是否可能同时成立。

题解

离散化去重 先处理=用并查集维护 然后用≠进行判断

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#define LL long long
#define Max(x, y) (x >= y ? x : y)
#define Min(x, y) (x <= y ? x : y)
#define MM(x, y) memset(x, y, sizeof(x))
#define F(i, x, y) for(register int i=x; i<=y; i++)
#define R(i, x, y) for(register int i=x; i>=y; i--)
using namespace std;
inline void in(int &x)
{
static int ch; static bool flag;
for(flag=false, ch=getchar(); ch<'0'||ch>'9'; ch=getchar()) flag |= ch=='-';
for(x=0; isdigit(ch); ch=getchar()) x = (x<<1) + (x<<3) + ch - '0';
x = flag ? -x : x;
}
int T, n, cnt;
int u[100005<<1], v[100005<<1], e[100005<<1];
int f[100005<<1];
int b[100005<<1];
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
inline int work()
{
freopen("equ.in","r",stdin); freopen("equ.out","w",stdout);
in(T);
while(T--) {
in(n); cnt = 0;
int all = 0;
F(i, 1, n*2) f[i] = i;
F(i, 1, n) {
in(u[i]); in(v[i]); in(e[i]);
b[i*2-1]=u[i]; b[i*2]=v[i];
}
cnt = n*2;
sort(b + 1, b + cnt + 1); unique(b + 1, b + cnt + 1);
F(i, 1, n) {
u[i] = lower_bound(b+1, b+cnt+1, u[i])-b;
v[i] = lower_bound(b+1, b+cnt+1, v[i])-b;
if (e[i]) {
int uu = find(u[i]), vv = find(v[i]);
if (uu != vv) f[uu] = vv;
}
} bool flag = 1;
F(i, 1, n) {
if (!e[i]) {
int uu = find(u[i]), vv = find(v[i]);
if (uu == vv) {
printf("NO\n");
flag = 0;
break;
}
}
}
if (flag) printf("YES\n");
}
return 0;
}
int TAT = work();
int main() {;}