当前位置:   article > 正文

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

codeforces round #700 (div. 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冲冲冲

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/71307
推荐阅读
相关标签
  

闽ICP备14008679号