agc040

2024-04-12 18:08:08

A. ><

大意: 给定一个序列相邻元素的大小关系, 求序列和的最小值

贪心, 最低点取0, 然后向左右延伸即可.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(_i,_a,_n) for(int _i=_a;_i<=_n;++_i)
#define PER(_i,_a,_n) for(int _i=_n;_i>=_a;--_i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e6+10;
int n, a[N], vis[N];
char s[N];

void solve(int x) {
    a[x] = 0;
    int t = x-1, now = 1;
    while (t>=0&&s[t+1]=='>') a[t--] = now++;
    t = x+1, now = 1;
    while (t<=n&&s[t]=='<') a[t++] = now++;
}

int main() {
    scanf("%s",s+1);
    n = strlen(s+1);
    if (s[1]=='<') solve(0);
    REP(i,1,n-1) if (s[i]=='>'&&s[i+1]=='<') solve(i);
    if (s[n]=='>') solve(n);
    REP(i,1,n) if (s[i]=='<'&&s[i+1]=='>') a[i] = max(a[i-1],a[i+1])+1;
    ll ans = 0;
    REP(i,0,n) ans += a[i];
    printf("%lld\n", ans);
}

View Code

B. Two Contests
大意: 给定$n$个区间, 要求划分成两部分, 每部分的价值为区间交集的长度, 求最大价值.

假设某一部分交集为空, 那么另一部分只放一块最长的区间.否则的话, 两部分一定都有价值.

那么考虑右端点最小的一块区间$L$, 与$L$不相交的区间一定不与$L$在同一部分, 一定全在另一个区间内, 可以合并成一块区间$R$.

然后考虑剩余区间如何分配, 首先左端点一定在$L$的右端点左侧, 所以就可以按左端点从大到小排序, 枚举一下它们与$L$相交的长度即可.

最后要再特判一下$R$为空的情况

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(_i,_a,_n) for(int _i=_a;_i<=_n;++_i)
#define PER(_i,_a,_n) for(int _i=_n;_i>=_a;--_i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e6+10;
int n;
pii a[N],b[N],c[N],L,R;
pii add(pii a, pii b) {
    if (!a.x) return b;
    if (!b.x) return a;
    return pii(max(a.x,b.x),min(a.y,b.y));
}
int len(pii a) {
    if (!a.x) return -INF;
    return a.y-a.x+1;
}

int main() {
    scanf("%d",&n);
    REP(i,1,n) scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+1+n,[](pii a,pii b){return a.y-a.x<b.y-b.x;});
    int ans = len(a[n]), cnt = 0;
    sort(a+1,a+1+n,[](pii a,pii b){return a.y<b.y;});
    L = a[1];
    REP(i,2,n) {
        pii t(add(L,a[i]));
        if (t.x>t.y) R = add(R,a[i]);
        else b[++cnt] = a[i];
        if (R.x>R.y) return printf("%d\n",ans),0;
    }
    sort(b+1,b+1+cnt,greater<pii>());
    c[cnt] = b[cnt];
    PER(i,1,cnt-1) c[i] = add(c[i+1],b[i]);
    ans = max(ans, len(add(c[1],L))+len(R));
    if (!R.x) {
        int ma = -INF;
        REP(i,1,cnt) ma = max(ma, len(b[i]));
        ans = max(ans, len(add(c[1],L))+ma);
    }
    REP(i,1,cnt) {
        R = add(R,b[i]);
        ans = max(ans, len(add(c[i+1],L))+len(R));
    }
    printf("%d\n", ans);
}

View Code

C. Neither AB nor BA

大意: 给定偶数$n$, 求所有长$n$的字符串个数, 满足只含$ABC$, 每次删除相邻两个字符, 不能删$AB$或$BA$, 最终可以删完.

假设奇数位$A_1$个$A$,$B_1$个$B$,偶数位$A_0$个$A$,$B_0$个$B$.

那么题目条件就等价于$A_1+B_0\le \frac{n}{2},A_0+B_1\le \frac{n}{2}$

用总方案减一下不合法方案即可.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(_i,_a,_n) for(int _i=_a;_i<=_n;++_i)
#define PER(_i,_a,_n) for(int _i=_n;_i>=_a;--_i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 998244353;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head


const int N = 1e7+10;
int n, fac[N], ifac[N], po[N];
int C(int n, int m) {
    return (ll)fac[n]*ifac[m]%P*ifac[n-m]%P;
}

int main() {
    fac[0] = po[0] = 1;
    REP(i,1,N-1) fac[i]=(ll)fac[i-1]*i%P,po[i]=(ll)po[i-1]*2%P;
    ifac[N-1] = inv(fac[N-1]);
    PER(i,0,N-2) ifac[i]=(ll)ifac[i+1]*(i+1)%P;
    scanf("%d", &n);
    int ans = qpow(3,n);
    REP(i,n/2+1,n) ans = (ans-2ll*C(n,i)*po[n-i])%P;
    if (ans<0) ans += P;
    printf("%d\n", ans);
}

View Code

码农公寓

相关文章