Educational Codeforces Round 45

一个小模拟不解释

//By SiriusRen
#include <bits/stdc++.h>
using namespace std;
long long n,m,a,b;
int main(){
    scanf("%I64d%I64d%I64d%I64d",&n,&m,&a,&b);
    printf("%I64d
",min((n%m)*b,(m-(n%m))*a));
}

给你一个数列A[i]

把所有Ai>Aj且Ai<=Aj+K的Aj去掉最少剩下多少数

//By SiriusRen
#include <bits/stdc++.h>
using namespace std;
int n,k,a[200050],vis[200050],ans;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<n;i++)if(a[i]!=a[i+1]&&a[i]+k>=a[i+1])vis[i]=1;
    for(int i=n;i;i--)if(vis[i]&&a[i]==a[i-1])vis[i-1]=1;
    for(int i=1;i<=n;i++)if(!vis[i])ans++;
    printf("%d
",ans);
}

题意：

给你n个括号序列，问两两合并能形成合法的组合有多少种（可以自己和自己合并）。

思路：

首先：)( 这样的括号序列肯定是不合法的

统计一下有多少个向右开的括号，有多少个向左开的括号。

乘一下就完了...

//By SiriusRen
#include <bits/stdc++.h>
using namespace std;
const int N=300050;
int n,re[N],a[N*2],vis[N];
char s[N];long long ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        int len=strlen(s),l=0,r=0;
        for(int j=0;j<len;j++)s[j]=='('?l++:l>0?l--:r++;
        if(l&&r){vis[i]=1;continue;}
        l?re[i]=l:re[i]=-r;
    }
    for(int i=1;i<=n;i++)if(!vis[i])a[N+re[i]]++;
    for(int i=0;i<=300000;i++)ans+=1ll*a[N-i]*a[N+i];
    printf("%I64d
",ans);
}