Codeforces Round #700 (Div. 2) C D1 2题解

C题 1480C
一个交互题，题目给你一个n代表数组长度，然后询问该数组的谷底，也就是存在一个pos 他两边相邻的值都大于他。如果当前pos的值没有给出，就输入它。划重点 ，不超过100次找出来，那么显然就是二分了 。
分析： 我们二分mid 作为谷底，那么如果 a[mid]<a[mid-1] 要构成谷底就要往右边找，所以 l= mid 这样子二分 很easy

int a[222222];
inline int check(ll p) {
	if(a[p]) return a[p];
	printf("? %lld\n", p), fflush(stdout);
	scanf("%lld", &a[p]); return a[p];
}


signed main()
{
    ll n;
    read(n);
    a[0] = a[n + 1] =1e18;
    int l = 1, r = n;
    while(l < r)
    {
        ll mid = l + r + 1 >> 1;
        if(check(mid) < check(mid - 1))
            l = mid;
        else
            r = mid - 1;
    }
    printf("! %lld\n", l);
    fflush(stdout);
}
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

1480 D1
题意：给我们一个长度为n的序列，现在可以染色黑白，抽出来形成a0序列和a1序列，现在合并相邻的相同值，最终序列剩下的元素个数就是贡献，D1询问我们最大贡献，D2询问我们最小贡献。先考虑下最大贡献，那必然是尽可能的使得a0 序列 a1 序列相邻位不相同。那么我们维护两个序列s1 ,s2 只需要记录他们的末尾元素即可 不妨令s1 =a[1] 那么维护过程从i=2开始遍历数组，详情看代码，分类讨论下ai放在s1还在s2 即可

ll a[111111];
ll vis[111111];
ll op[50];
signed main(){

ll n;
read(n);
ll num_1=0;
ll num_ma=0;
for(int i=1;i<=n;i++){
   read(a[i]);
   vis[a[i]]++;
}
op[1]=a[1];
ll cnt=1;
for(int i=2;i<=n;i++){
   if(a[i]!=op[1]){
   cnt++;//  可以放
   if(op[1]!=a[i+1]&&a[i]!=op[2]){
   // 可放1 也可放2  优先照顾2
   op[2]=a[i];
   }
   else{
    op[1]=a[i];
   }

   }
   else if(a[i]!=op[2]){
    cnt++;
    op[2]=a[i];
   }
}

printf("%lld\n",cnt);
}
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

1480D2 求min
这个题就要尽可能的把相同的值堆在一起 ，我们先给每个连续段归为1 ，例如12222223 归为123
然后开始遍历，打标记，当还没有遇到重复标记 的点时，遇到一个没有标记过的数贡献就+1. 如果遇到了标记相同的数 比如样例
7
1 2 3 1 3 2 2
（我先演示一遍
合并一下变为序列1 2 3 1 3 2
然后1 2 3 独立标记后 1重复标记 之前我们的操作相当于每次分别往s1 s2序列丢进去一个值 那么到了 pos=4 1标记重复 此时
s1 : 1 3 1 _待定
s2: 2
那么我们清空标记数组 并且把 1,3 标记 把3 丢在s2 里面 于是
s1:1 1 2
s2:2 3 3
于是总贡献为 4

 
ll a[111111];
ll vis[111111];
ll op[50];
vector<ll>s;
map<ll,ll>sb;
signed main(){
 
ll n;
read(n);
ll num_1=0;
ll num_ma=0;
a[n+1]=0;
for(int i=1;i<=n;i++){
   read(a[i]);
   vis[a[i]]++;
   
 
}
for(int i=1;i<=n;i++){
    if(a[i]!=a[i+1]){
        s.push_back(a[i]);
    }
}
ll ans=0;
for(int i=0;i<s.size();i++){
    if(sb[s[i]]==0){
        ans++;
        sb[s[i]]++;
    }
    else{
        sb.clear();
        sb[s[i]]++;
        sb[s[i-1]]++;
    }
    
}
printf("%lld",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

感觉挺简单的 qwq 下午SAM冲冲冲