标签：147 Educational int MAX scanf Codeforces ans 区间 using

A

题意

思路

有前导零结果直接为0，出现在第一位的？贡献为9，其他地方的？贡献为10。

代码

#include<bits/stdc++.h>
 
using namespace std;
using ll=long long;
 
char s[10];
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s);
        if(s[0]=='0')
        {
            printf("0\n");
            continue;
        }
        int res=s[0]=='?'?9:1;
        for(int i=1;i<strlen(s);i++)
            if(s[i]=='?')res*=10;
        printf("%d\n",res);
    }
}

B

题意

给一个数组，对其进行一次如下操作：选一个区间，然后将这个区间进行从小到大排序。现在给出操作前和操作后的数组，求可能选择的最长区间是哪里。

思路

刚开始想到可以直接找最长不降子串，但是实际上区间不一定是最长不降子串，因为有可能数组中本身存在一个长的不降区间，但是并没有选择这个区间操作。

所以想到可以先找到一个区间[l,r]，使得l,r位置修改前后的值不相等，然后再在修改后的数组中，向左向右扩展，扩展到可以得到的最大不降子串。因为可以等价于选择了扩展后的区间操作。

代码

#include<bits/stdc++.h>
 
using namespace std;
 
const int MAX=2e5+5;
 
int a[MAX],b[MAX];
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%d",&a[i]);
        for(int i=0; i<n; i++)
            scanf("%d",&b[i]);
       int l=0,r=n-1;
       while(a[l]==b[l])l++;
       while(a[r]==b[r])r--;
       while(l>0&&b[l-1]<=b[l])l--;
       while(r<n-1&&b[r+1]>=b[r])r++;
       printf("%d %d\n",l+1,r+1);
    }
}

C

题意

给一个小写字母组成的字符串，每次可以删除其中的任意字符，但是选择删除的字符位置不能相邻。求最少多少次操作可以使得字符串只剩下相同的某个字母。

思路

首先可以想到，操作一定有一个上限，那就是每次选择奇数或偶数位置的字符删除，最后留下一个字母，设字符串长度为length，操作次数的上限为

\[\lfloor log_2(length) \rfloor \]

然后可以想到，由于总共只有26个字母，那么可以枚举最后剩下哪个字母，其他的全部删除。枚举留下的字母，然后以当前字母为分隔符，将字符串分块，将各块全部删除，操作次数就是删除最长的分块需要的操作次数。根据上述的结论，这个操作次数为

\[\lfloor log_2(length) \rfloor+1 \]

因为要把最后剩的一个字符也删除。

代码

#include<bits/stdc++.h>
 
using namespace std;
 
const int MAX=2e5+5;
 
char s[MAX];
vector<int>pos[26];
 
int left1(int n)
{
    int res=28;
    while(((1<<res)&n)==0)res--;
    return res+1;
}
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        for(int i=0;i<26;i++)
            pos[i].clear();
        scanf("%s",s);
        int n=strlen(s),minn=n;
        for(int i=0;i<n;i++)
            pos[s[i]-'a'].push_back(i);
        for(int i=0;i<26;i++)
        {
            int last=-1,maxx=0;
            pos[i].push_back(n);
            for(int j=0;j<pos[i].size();j++)
            {
                maxx=max(maxx,pos[i][j]-last-1);
                last=pos[i][j];
            }
            minn=min(minn,maxx);
        }
        if(minn==0){printf("0\n");continue;}
        printf("%d\n",left1(minn));
    }
}

D

题意

给一个1*inf的格子条，以及一系列区间，区间互不相连，从左到右移动，每次在区间内，可以按下按钮开始染色，然后松开按钮停止染色，区间外不能染色。每移动一格，代价为1，按下和松开按钮代价也均为1。求最少代价，使得总共染色格子数量为k。

思路

决策的点就在于要不要跳过一些区间，由于区间不连续，那么从一个区间末端到下一个区间起点最少需要2的代价。然后很明显可以想到，只要区间长度>=2，那么就没必要跳过，因为如果跳过任意一个长度>=2的区间，那么尽管减少了按下和松开按钮的代价（共为2），但是收益也至少减少了2，那么在之后的区间中就必须至少额外染色2个格子，相当于代价增加了2，因此跳过不会带来收益。

只有跳过长为1的区间会带来收益，所以可以想到统计长为1的区间个数，遍历区间，每遇到染色格子数量>=k时，就尝试用当前的区间额外长度替换之前的长为1的区间，可以减少按按钮的代价，最后整体取最优解。

#include<bits/stdc++.h>
 
using namespace std;
 
const int MAX=2e5+5;
 
int l[MAX],r[MAX];
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        int cur=0,ans=2e9+7,cnt1=0;
        for(int i=0;i<n;i++)
            scanf("%d",&l[i]);
        for(int i=0;i<n;i++)
            scanf("%d",&r[i]);
        for(int i=0;i<n;i++)
        {
            int len=(r[i]-l[i]+1);
            if(len==1)cnt1++;
            cur+=len;
            if(cur>=k)
            {
                int remain=cur-k;
                int mincnt=min(cnt1,remain);
                ans=min(ans,(i+1-mincnt)*2+r[i]-remain+mincnt);
            }
        }
        if(ans==2e9+7)ans=-1;
        printf("%d\n",ans);
    }
}

标签：147,Educational,int,MAX,scanf,Codeforces,ans,区间,using
From： https://www.cnblogs.com/cryingrain/p/17350688.html