CF Round45 Div.2

前言

我太菜了……

本蒟蒻A了三题之后就A不动了……

T1

水题，要不就加否则就减，最后结合给你的a,b判断一下大小就行了

 
​x
#include<cstdio>
#include<algorithm>
#include<iostream>
#define LL long long
using namespace std;
LL n,m,a,b,lst;
int main(){
    cin>>n>>m>>a>>b;
    lst=n%m;
    cout<<min(a*(m-lst),b*lst)<<endl;
    return 0;
}

T2

依然是水题，但是不知道为什么dalao们纷纷想到了$O(n)$的想法，然后我只想到了了$O(nlog(n))$的想法，果然是我太菜了。

我的想法是对于每个数进行二分查找，如果有符合要求的数那么就$ans$就减去就行了。

 
xxxxxxxxxx
#include<cstdio>
#include<cctype>
#include<algorithm>
#define qmid(L,R) (L+((R-L)>>1))
using namespace std;
inline int read(){
    int ret=0,flg=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-')flg=-1;ch=getchar();}
    while (isdigit(ch))ret=ret*10+ch-48,ch=getchar();
    return ret*flg;
}
int n,ans,a[2000005],k;
inline bool fnd(int x){
    int L=1,R=n;
    bool vis=0;
    while (L<=R){
        int mid=qmid(L,R);
        if (a[mid]<=x)L=mid+1;else
        if (a[mid]>x&&a[mid]<=x+k){vis=1;break;}else
        if (a[mid]>x+k)R=mid-1;
    }
    return vis;
}
int main(){
//  freopen("B.in","r",stdin);
//  freopen("B.out","w",stdout);
    n=ans=read(),k=read();
    for (int i=1;i<=n;i++)a[i]=read();
    sort(a+1,a+1+n);
    for (int i=1;i<=n;i++)ans-=fnd(a[i]);
    printf("%d\n",ans);
    return 0;
}

T3

也算是水题吧，$hash$计数就行了，记录每一个字符串的需要右括号数量（负数的话就是左括号多了）。注意判断无解的情况，例如：$)($。这里我们会发现其实不管怎么接都是不成功的，特判一下如果中间$hash计数＜0$并且最后$hash计数≥0$那么就肯定是无解的。

 
xxxxxxxxxx
#include<cstdio>
#include<cstring>
#include<iostream>
#define LL long long 
#define maxn 300005
using namespace std;
LL ans;
int hsh[2*maxn],n;
struct ypc{
    bool vis;
    int stk;
}a[maxn];
int main(){
//  freopen("C.in","r",stdin);
//  freopen("C.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        char s[maxn];scanf("%s",s);
        int len=strlen(s),u=0,d=0;
        bool vis=0;
        for (int j=0;j<len;j++){
            u+=(s[j]=='('?1:-1),d+=(s[j]=='('?1:-1);
            if (u<0)vis=1;
            if (d<0)d-=d;
        }
        if (d>0&&vis)a[i].vis=1;else a[i].stk=u;
    }
    for (int i=1;i<=n;i++)if (!a[i].vis&&a[i].stk<=0)hsh[a[i].stk+maxn]++;
    for (int i=1;i<=n;i++)if (!a[i].vis&&a[i].stk>=0)ans+=hsh[maxn-a[i].stk];
    cout<<ans<<endl;
    return 0;
}

然后……

然后后面三题就不会做了QAQ。

但是$F$题感觉就是点分治（废话，这不是明摆着的吗），但是呢，因为某些不可抗力原因（比如说心系抗日神剧啊之类的）我没有写T_T。