[HOJ] 61 獨木橋

兩種情況比較
1. a[1]+a[0]+a[max]+a[1]
2. a[max]+a[0]+a[max-1]+a[0]

#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,a[100005],k;
long long ans;
int main(){
    scanf("%d",&n);
    k=n;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    sort(a,a+n);
    if(n>3){
        k=n%2+2;
        for(int i=n-1;i>2;i-=2)
            ans+=min(a[0]+a[1]*2+a[i],a[0]*2+a[i]+a[i-1]);
    }
    if(k==1)printf("%d\n",a[0]);
    else if(k==2)printf("%lld\n",ans+a[1]);
    else if(k==3)printf("%lld\n",ans+a[0]+a[1]+a[2]);
}

[HOJ] 60 -2進位

一般短除法後再轉成-2進位

短除法後此時每一位會有0、1、-1、2四種情況
0、1不用管，-1和2討論如何進位

#include<cstdio>
#include<cstring>
#define LL long long
int a[105],st;
bool f;
LL k;
int main(){
    while(~scanf("%lld",&k)){
        if(!k){
            puts("0");
            continue;
        }
        memset(a,0,sizeof(a));
        f=st=0;
        while(k!=0){
            a[st]=k%(-2);
            k/=(-2);
            st++;
        }
        for(int i=0;i<st+2;i++){
            if(a[i]==-1){
                a[i]=1;
                a[i+1]++;
            }
            if(a[i]==2){
                a[i]=0;
                a[i+1]++;
                a[i+2]++;
            }
        }
        for(int i=st+2;i>=0;i--){
            if(a[i])f=true;
            if(f)printf("%d",a[i]);
        }
        puts("");
    }
}

[HOJ] 46 正值DE

參考這個
dp[i][i+L]表示從第i個矩陣乘到第i+L的最佳解

每次尋找i~L之間的最佳中間點k
dp[i][i+L]=min(dp[i][i+L],dp[i][k]+dp[k+1][i+L]+R[i]*C[k]*c[i+L])

#include<cstdio>
#define MAX 1005
#define LL long long
int n,r[MAX],c[MAX],T;
LL dp[MAX][MAX],tmp,ans,cnt;
LL min(LL a,LL b){
    return a<b? a:b;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&r[i],&c[i]);
        for(int L=1;L<n;L++){
            for(int i=1;i+L<=n;i++){
                tmp=9*(10e18);
                for(int k=i;k<i+L;k++){
                    tmp=min(tmp,dp[i][k]+dp[k+1][i+L]+r[i]*c[k]*c[i+L]);
                }
                dp[i][i+L]=tmp;
            }
        }
        ans=dp[1][n];
        cnt+=ans;
        printf("%lld\n",(ans-1)/1000+1);
    }
    printf("%lld\n",(cnt-1)/1000+1);
}

[HOJ] 317 體重問題

#include<cstdio>
#include<algorithm>
#define MAX 100005
using namespace std;
int n,m,w[MAX],ans[MAX],st,ed,mid;
char s[MAX];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
        scanf("%d",&w[i]);
    scanf("%s",s);
    sort(w,w+m);
    for(int i=0;i<n-1;i++){
        if(s[i]=='L')mid--;
        if(s[i]=='R')mid++;
        ans[i+1]=mid;
        st=min(st,mid);
        ed=max(ed,mid);
    }
    if(ed-st+1>m)puts("No");
    else for(int i=0;i<n;i++)
        printf("%d\n",w[ans[i]-st]);
}

[HOJ] 66 Farmer John

一開始白癡用set維護區間最大(小)值噴MLE

後來想到資芽手寫有deque

對於長度Y的區間，每次都詢問其左界最大值和右界最小值

每次拿到一個元素a[i]後都和最尾端比較，若尾端比較小(大)則pop_back直到找到尾端大(小)於等於a[i]後push_back，使deque內呈單調序列，並詢問前端是否=a[i-Y]，若是則pop_front，而此時front將是此區間最大(小)的元素

#include<cstdio>
#include<deque>
#include<cstring>
#define MAX 5000001
using namespace std;
 
deque<int> ql,qr;
int l[MAX],r[MAX],L,R,S,n,m,x,y;
long long ans;
inline void cnt(){
    for(int i=1;i<=m;i++){
        while(!ql.empty()&&ql.back()<l[i])ql.pop_back();
        ql.push_back(l[i]);
        while(!qr.empty()&&qr.back()<r[i])qr.pop_back();
        qr.push_back(r[i]);
         
        if(i<y)continue;
        if(ql.front()==l[i-y])ql.pop_front();
        if(qr.front()==r[i-y])qr.pop_front();
         
        L=ql.front();
        R=-qr.front();
        if(R-L+1>=x)ans+=R-L+2-x;
    }
         
}
int main(){
    scanf("%d%d%d%d",&n,&m,&x,&y);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&S,&L);
        l[i]=S;
        r[i]=-(S+L-1);
    }
    cnt();
    if(x!=y){
        x^=y; y^=x; x^=y;
        while(!ql.empty())ql.pop_back();
        while(!qr.empty())qr.pop_back();
        cnt();
    }
    printf("%lld\n",ans);
}

[TIOJ] 1014 打地鼠

位元DP
dp[i][k]代表已經打掉哪些的地鼠(以二進位i表示)的情況下，最後打第k個

#include<cstdio>
#include<cmath>
#include<algorithm>
#define INF 2000000000
using namespace std;
int dp[1<<16][21],n,a[21],t,ans;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<n;i++)
        for(int j=0;j<(1<<n);j++)
            dp[j][i]=INF;
    ans=INF;
    dp[0][0]=1;
    for(int i=1;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                for(int k=0;k<n;k++){
                    t=dp[i-(1<<j)][k]+abs(k-j);
                    dp[i][j]=min(dp[i][j],(((t-1)/a[j]+1)*a[j]));
                }
            }
        }
    }
    for(int i=0;i<n;i++)
        ans=min(ans,dp[(1<<n)-1][i]);
    printf("%d\n",ans);
} 

[HOJ] 127 移方塊

跟這題的做法有點像
把前綴分別由後往前和由前往後做成單調序列
有點貪心的觀念

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define MAX 1000005
using namespace std;
int l[MAX],r[MAX],n,m,li,ri,ptl,ptr,ans;
bool fr;
long long sum[MAX],a[MAX],k;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&k);
        sum[i]=sum[i-1]+k;
    }
    while(m--){
        ans=li=ri=ptr=ptl=0;
        scanf("%lld",&k);
        for(int i=1;i<=n;i++)
            a[i]=sum[i]-k*i;
        for(int i=1;i<=n;i++){
            while(li&&a[l[li]]<=a[i])li--;
            l[++li]=i;
        }
        r[0]=n;
        for(int i=n-1;i>=0;i--){
            while(ri&&a[r[ri]]>=a[i])ri--;
            r[++ri]=i;
        }
        ptr=ri;
        while(ptl<=li&&ptr>=0){
            if(a[l[ptl]]>=a[r[ptr]]){
                ans=max(ans,l[ptl]-r[ptr]);
                ptl++;
            }
            else ptr--;
        }
        if(fr)printf(" %d",ans);
        else printf("%d",ans);
        fr=true;
    }
}

[HOJ] 302 最大平均值

二分搜平均值
驗證用貪心弄成單調序列
再從deque前面檢查

之前用凸包法不知道為什麼第12筆測資過不去

#include<cstdio>
#include<algorithm>
#include<queue>
#define MAX 100005
#define LL long long
using namespace std;
long long sum[MAX],a[MAX],tmp,l,r,mid;
int n,f;
struct node{
    int pos;
    LL val;
};
deque<node> dq;
bool ok(LL k){
    for(int i=1;i<=n;i++){
        tmp=sum[i]-k*i;
        while(!dq.empty()&&dq.back().val<=tmp)
            dq.pop_back();
        dq.push_back(node{i,tmp});
    }
    for(int i=0;i<=n;i++){
        tmp=sum[i]-k*i;
        while(!dq.empty()&&dq.front().pos<i+f)
            dq.pop_front();
        if(!dq.empty()&&dq.front().val>=tmp)return true;
    }
    return false;
}
int main(){
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++){
        scanf("%lld",&tmp);
        sum[i]=sum[i-1]+tmp*1000;
        r=max(tmp*1000,r);
    }
    r++;
    while(l!=r-1){
        mid=l+r>>1;
        while(!dq.empty())dq.pop_front();
        if(ok(mid))l=mid;
        else r=mid;
    }
    printf("%lld\n",l);
}

[HOJ] 118 猜數字

二分搜數字的位置

#include<cstdio>
#include<cstring>
#include "interactive/118.h"
int ans[105],tmp[105],n,k,l,r,mid;
 
int main(){
    n=Init();
    for(int j=1;j<=n;j++){
        l=1; r=n;
        while(l!=r){
            mid=l+r>>1;
            memset(tmp,0,sizeof(tmp));
            for(int i=l;i<=mid;i++){
                tmp[i]=j;
            }
            k=Answer(tmp);
            if(k)r=mid;
            else l=mid+1;
        }
        ans[l]=j;
    }
    Answer(ans);
}

[HOJ] 228 Mobiles

兩邊子樹最大深度都>0無解
任意節點深度差>1無解

#include<cstdio>
#include<algorithm>
#define INF 1000000000
using namespace std;
struct node{
    int l,r,mn,mx;
}t[100005];
int n,l,r,cnt,f;
void dfs(int k){
    if(!k)return;
    t[k].mx=1;
    t[k].mn=INF;
    if(t[k].l){
        dfs(t[k].l);
        t[k].mn=min(t[k].mn,t[t[k].l].mn+1);
        t[k].mx=max(t[k].mx,t[t[k].l].mx+1);
    }
    if(t[k].r){
        dfs(t[k].r);
        t[k].mn=min(t[k].mn,t[t[k].r].mn+1);
        t[k].mx=max(t[k].mx,t[t[k].r].mx+1);
    }
    if(!t[k].l||!t[k].r)t[k].mn=1;
}
void dfs1(int k){
    if(!k)return;
    if(t[t[k].l].mx-t[t[k].l].mn>0&&
    t[t[k].r].mx-t[t[k].r].mn>0){
        f=1;
        return;
    }
    if(t[k].mx==t[k].mn)return;
     
    if(t[k].mx-t[k].mn>1){
        f=1;
        return;
    }
    int R,L;
    R=t[t[k].r].mn+t[t[k].r].mx;
    L=t[t[k].l].mn+t[t[k].l].mx;
    if(L<R)cnt++;
    dfs1(t[k].l);
    dfs1(t[k].r);
}
int main(){
    scanf("%d",&n);
    int L,R;
    t[0].mn=t[0].mx=0;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&L,&R);
        if(L==-1)L=0;
        if(R==-1)R=0;
        t[i].l=L;
        t[i].r=R;
    }
         
    dfs(1);
    dfs1(1);
    if(!f)printf("%d\n",cnt);
    else puts("-1");
}

[HOJ] 186 壞掉的項鍊

#include<cstdio>
int tmp,now,n,mx,a[3000005],sum;
int max(int a,int b){
    return a>b? a:b;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    now=a[0];
    for(int j=0;j<n*2;j++){
        int i=j%n;
        if(a[i]==now||!a[i])sum++;
        else sum=tmp+1,now=a[i];
        if(!a[i])tmp++;
        else tmp=0;
        mx=-max(-n,-max(mx,sum));
        //printf("%d ",sum);
    }
    printf("%d\n",mx);
}

[HOJ] 363 拉麵比較

單淘汰賽

#include<cstdio>
#include<algorithm>
#include<vector>
#include"interactive/363.h"
using namespace std;
struct node{
    int val,nxt;
};
vector<node> mn,mx;
int n,k,now,siz,a[]={1,2,3,4,5};
/*int Compare(int x,int y){
    if(a[x]>a[y])return 1;
    else return -1;
}
void Answer(int X,int Y){
    printf("%d %d\n",X,Y);
}
int Ramen(){
    return 5;
}*/
int main (){
    n=Ramen();
    siz=(n+1>>1)-1;
    for(int i=0;i<n-1;i+=2){
        k=Compare(i,i+1);
        if(k==1){
            mx.push_back(node{i,i/2+1});
            mn.push_back(node{i+1,i/2+1});
        }
        else {
            mn.push_back(node{i,i/2+1});
            mx.push_back(node{i+1,i/2+1});
        }
    }
    if(n%2){
        mx.push_back(node{n-1,0});
        mn.push_back(node{n-1,0});
    }
    mn[siz].nxt=mx[siz].nxt=0;
    while(siz--){
        k=Compare(mn[now].val,mn[mn[now].nxt].val);
        if(k==1)swap(mn[now].val,mn[mn[now].nxt].val);
        mn[now].nxt=mn[mn[now].nxt].nxt;
 
        k=Compare(mx[now].val,mx[mx[now].nxt].val);
        if(k==-1)swap(mx[now].val,mx[mx[now].nxt].val);
        now=mx[now].nxt=mx[mx[now].nxt].nxt;
    }
    Answer(mn[now].val,mx[now].val);
}

[HOJ]68 征服者

割點好容易忘記...

#include<cstdio>
#include<vector>
#include<algorithm>
#define MAX 100005
using namespace std;
vector<int> v[MAX];
int n,m,fr,to,in[MAX],low[MAX],t;
long long cnt[MAX];
int dfs(int k,int pa){
    int ch=1,tmp,all=1,now,nt;
    now=in[k]=++t;
    for(int i=0;i<v[k].size();i++){
        nt=v[k][i];
        if(!in[nt]){
            tmp=dfs(nt,k);
            ch+=tmp;
            now=min(now,low[nt]);
            if(low[nt]>=in[k]){
                all+=tmp;
                cnt[k]+=(long long)(n-1-tmp)*tmp;
            }
        }
        else if(in[nt]<in[k]&&nt!=pa){
            now=min(now,in[nt]);
        }
    }
    low[k]=now;
    cnt[k]+=(long long)(all-1)*(n-all);
    return ch;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&fr,&to);
        v[fr].push_back(to);
        v[to].push_back(fr);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++){
        printf("%lld\n",cnt[i]+2*n-2);
    }
}

[HOJ]83 FOMI洗腦計畫

Dijkstra

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define INF 1000000000
using namespace std;
struct node{
    int pos,val;
};
struct pt{
    int pa,now,val;
    friend bool operator <(pt a,pt b){
        return a.val>b.val;
    }
};

priority_queue<pt> pq;
vector<node> v[3005];
int n,k,p,m,fr,to,val,dis[3005],pa[3005],ans;

int main(){
    scanf("%d%d%d",&n,&k,&m);
    for(int i=0;i<=n;i++)dis[i]=INF;
    for(int i=0;i<k;i++){
        scanf("%d%d%d",&fr,&to,&val);
        v[fr].push_back(node{to,val});
        v[to].push_back(node{fr,val});
    }
    while(m--){
        scanf("%d",&fr);
        dis[fr]=0;
        pa[fr]=fr;
        pq.push(pt{fr,fr,0});
    }
    while(!pq.empty()){
        p=pq.top().pa;
        fr=pq.top().now;
        pq.pop();
        for(int i=0;i<v[fr].size();i++){
            if(dis[fr]+v[fr][i].val<dis[v[fr][i].pos]){
                dis[v[fr][i].pos]=dis[fr]+v[fr][i].val;
                pa[v[fr][i].pos]=p;
                pq.push(pt{p,v[fr][i].pos,dis[v[fr][i].pos]});
            }
        }
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,dis[i]);
        for(int j=0;j<v[i].size();j++){
                k=dis[i]+dis[v[i][j].pos]+v[i][j].val+1;
                ans=max(ans,k/2);
        }
    }
    printf("%d\n",ans);
}