どうしようもなくカンニングしてしまう日

データ構造の扱いムズイよ(´ε｀；)

1742

蟻本そのまんまだったので写した。
理解はしたよ、うん。
dp[j]:=jをつくるときに余る数
だからこういう漸化式になるんでしょ、うん。

#include <cstdio>
#include <cstring>
int dp[100001];
int a[100], c[100];
int main() {
    int n, m;
    while (scanf("%d%d",&n,&m)) {
        if (!n&&!m) break;
        for (int i=0; i<n; i++) scanf("%d",&a[i]);
        for (int i=0; i<n; i++) scanf("%d",&c[i]);
        memset(dp, -1, sizeof(dp));
        dp[0]=0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<=m; j++) {
                if (dp[j]>=0) {
                    dp[j]=c[i];
                } else if (j<a[i]||dp[j-a[i]]<=0) {
                    dp[j]=-1;
                } else {
                    dp[j]=dp[j-a[i]]-1;
                }
            }
        }
        int res=0;
        for (int i=1; i<=m; i++) if (dp[i]!=-1) res++;
        printf("%d\n",res);
    }
}

果たして自分で書けるのか？（最近DP耐性できてきたからワンチャン

3368

なんだかんだ色々やって結局ほとんど人のコードに頼ってた←
わかると納得、たしかに個数でSegTree作っとけばはみ出した部分とRMQした答えのでっかいほうが答えになる。
一応個数でまとめるというアイデアは思いついていたけどはみ出した部分の処理ができないとかで却下してた。SegTreeの要素をステレオタイプで見てたから。

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
const int MAX_N=200000;
int n, ni, q, dat[2*MAX_N-1];
int a[MAX_N];
int x[MAX_N], sum[MAX_N];
void init(int n_) {
    n=1;
    while (n<n_) n*=2;
    for (int i=0; i<2*n-1; i++) dat[i]=INT_MIN;
}
void update(int k, int a) {
    k += n-1;
    dat[k]=a;
    while (k>0) {
        k=(k-1)/2;
        dat[k]=max(dat[k*2+1], dat[k*2+2]);
    }
}
int query(int a, int b, int k, int l, int r) {
    if (r<=a||b<=l) return INT_MIN;
    if (a<=l&&r<=b) return dat[k];
    else {
        int vl=query(a,b,k*2+1,l,(l+r)/2);
        int vr=query(a,b,k*2+2,(l+r)/2,r);
        return max(vl,vr);
    }
}
int solve(int l, int r) {
    int a=lower_bound(sum, sum+ni+1, l)-sum;
    int b=lower_bound(sum, sum+ni+1, r)-sum-1;
    // printf("%d %d %d %d %d %d\n",l,r,sum[a],sum[b],a,b);
    if (a==b+1) return r-l+1;
    int aa=sum[a]-l+1;
    int bb=r-sum[b];
    int ret=max(aa,bb);
    return max(ret, query(a+1,b+1,0,0,n));
}
int main() {
    while (scanf("%d",&ni)) {
        if (!ni) break;
        scanf("%d",&q);
        for (int i=0; i<ni; i++) scanf("%d",&a[i]);
        fill(x, x+MAX_N, 0);
        fill(sum, sum+MAX_N, INT_MAX);
        int pos=0, bef=a[0];
        x[0]=1;
        for (int i=1; i<ni; i++) {
            if (bef==a[i]) {
                x[pos]++;
            } else {
                bef=a[i]; pos++;
                x[pos]=1;
            }
        }
        sum[0]=x[0];
        for (int i=1; i<=pos; i++) {
            sum[i]=sum[i-1]+x[i];
        }
        init(++pos);
        for (int i=0; i<pos; i++) update(i,x[i]);
        for (int i=0; i<q; i++) {
            int l, r; scanf("%d%d",&l,&r);
            printf("%d\n",solve(l,r));
        }
    }
}

SegTreeムズイよ、おいw

3258

蟻本そのままhoge
にぶたんぐらい自力で解けるようになれよw

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
int l, n, m;
ll x[50002];
bool C(int d) {
    int last=0;
    for (int i=1; i<n-m; i++) {
        int crt=last+1;
        while (crt<n&&x[crt]-x[last]<d) {
             crt++;
        }
        if (crt==n) return false;
        last=crt;
    }
    return true;
}
int main() {
    scanf("%d%d%d",&l,&n,&m);
    x[0]=0; x[n+1]=l;
    for (int i=1; i<=n; i++) scanf("%lld",&x[i]);
    n+=2;
    sort(x,x+n);
    ll lb=0, ub=l+1;
    while (ub-lb>1) {
        ll mid=(lb+ub)/2;
        if (C(mid)) lb=mid;
        else ub=mid;
    }
    printf("%lld\n",lb);
}

蟻本セット全体的に英語がむずい←

3250

なんだなんだ？なんで思考時間10分で他人の考え見ているんだ？(´ε｀；)(´ε｀；)
stackを使えばできるというのは、それ以前にその要素を見えていた数を数えられるということです。

#include <cstdio>
#include <stack>
using namespace std;
typedef long long ll;
int n;
int main() {
    scanf("%d",&n);
    stack<ll> st;
    ll res=0;
    for (int i=0; i<n; i++) {
        ll h;
        scanf("%lld",&h);
        while (!st.empty()&&st.top()<=h) st.pop();
        res+=st.size();
        st.push(h);
    }
    printf("%lld\n",res);
}