[ZJ] a812 動物排隊

聽學長解說才會的
dp[i][j][k]表示當雞i隻 鴨j隻時整齊度為k的組合數

設原先整齊度k
若放雞整齊度會變成(k*2)%m (k在二進制往左進一位)
放鴨整齊度會變成(k*2+1)%m 

組合數乘上該整齊度的總和即為所求

#include<cstdio>
#define LL long long
LL dp[65][65][3605],cnt;
int x,y,m;
int min(int a,int b){
    return a<b? a:b;
}
int main(){
    scanf("%d%d%d",&x,&y,&m);
    dp[0][0][0]=1;
    for(int i=0;i<=x;i++){
        for(int j=0;j<=min(y,i);j++){
            for(int k=0;k<m;k++){
                if(i)dp[i][j][(k*2)%m]+=dp[i-1][j][k];
                if(j)dp[i][j][(k*2+1)%m]+=dp[i][j-1][k];
            }
        }
    }
    for(int i=0;i<m;i++)
        cnt+=dp[x][y][i]*i;
    printf("%lld\n",cnt);
}

[HOJ] 84 聖誕老人送禮物

找到中位數後找中位數離的最遠點，讓他只要走一次
若有偶數個點要四個X Y值都考慮

#include<cstdio>
#include<algorithm>
#include<cmath>
#define MAX 100005
using namespace std;
int x[MAX],y[MAX],w,h,n,mid,l,r;
struct node{
    int x,y;
}a[MAX];
long long ans=10e18,ma,tmp,now;
long long check(int k,int m){
    ma=now=0;
    for(int i=0;i<n;i++){
        now+=(long long)(abs(x[k]-a[i].x)+abs(y[m]-a[i].y))*2;
        ma=max(ma,(long long)abs(x[k]-a[i].x)+abs(y[m]-a[i].y));
    }
    return now-ma;
}
int main(){
    scanf("%d%d%d",&w,&h,&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&x[i],&y[i]);
        a[i]=node{x[i],y[i]};
    }
    mid=n>>1;
    sort(x,x+n);
    sort(y,y+n);
    for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++){
            tmp=check(mid-i,mid-j);
            if(tmp<ans||(tmp==ans&&(mid-i<l||(mid-i==l&&mid-j<r)))){
                ans=tmp;
                l=mid-i;
                r=mid-j;
            }
        }
    }
    printf("%lld\n%d %d\n",ans,x[l],y[r]);
}

[HOJ] 78 食物鏈

并查集

#include<cstdio>
#define n 50001
int pa[n*3],N,K,x,y,cmd,ans;
int find(int k){
    if(pa[k]==k)return k;
    return pa[k]=find(pa[k]);
}
int un(int a,int b){
    pa[find(a)]=find(b);
}
int main(){
    scanf("%d%d",&N,&K);
    for(int i=1;i<n*3;i++)pa[i]=i;
    while(K--){
        scanf("%d%d%d",&cmd,&x,&y);
        if(x>N||y>N){
            ans++;
            continue;
        }
        if(cmd==1){
            if(find(pa[x])==find(pa[y+n])||find(pa[x])==find(pa[y+n*2]))
                ans++;
            else {
                un(x,y);
                un(x+n,y+n);
                un(x+n*2,y+n*2);
            }
        }
        else {
            if(find(pa[x])==find(pa[y+n*2])||find(pa[x])==find(pa[y]))
                ans++;
            else {
                un(x,y+n);
                un(x+n,y+n*2);
                un(x+n*2,y);
            }
        }
    }
    printf("%d\n",ans);
}

[HOJ] 54 青蛙子

從邊邊隨便跳

複雜度不知道

#include<cstdio>
#define MAX 5005
int max(int a,int b){
    return a>b? a:b;
}
bool map[MAX][MAX],f;
int r[MAX],c[MAX],n,dr,dc,rn,cn,nr,nc,cnt,ans;
int main(){
    scanf("%d%d%d",&rn,&cn,&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&r[i],&c[i]);
        map[r[i]][c[i]]=true;
    }
         
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)continue;
            dr=r[j]-r[i];
            dc=c[j]-c[i];
            if((r[i]-dr>0&&r[i]-dr<=rn)&&(c[i]-dc>0&&c[i]-dc<=cn))
                continue;
            f=false;
            cnt=2;
            nr=r[j]+dr;
            nc=c[j]+dc;
            while(1){
                if(nr<1||nr>rn||nc<1||nc>cn){
                    f=true;
                    break;
                }
                if(!map[nr][nc])break;
                cnt++;
                nr+=dr;
                nc+=dc;
            }
            if(f)ans=max(ans,cnt);
        }
    }
    if(ans>2)printf("%d\n",ans);
    else puts("0");
}

[HOJ] 55 情報網

SCC縮環後找入度為0的點就是第一題的解
把入度為0和出度為0的點都連起來就可以讓整張圖連通

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define MAX 100005
using namespace std;
 
struct node{
    int val;
    bool dir;
};
vector<node> v[MAX];
vector<int> ord;
int p[MAX],in[MAX],out[MAX],cnt_in,cnt_out,to,n,cnt;
bool vis[MAX];
 
void dfs(int k){
    vis[k]=true;
    for(int i=0;i<v[k].size();i++){
        if(v[k][i].dir&&!vis[v[k][i].val])
            dfs(v[k][i].val);
    }
    ord.push_back(k);
}
 
void dfs1(int k,int gp){
    vis[k]=true;
    p[k]=gp;
    for(int i=0;i<v[k].size();i++){
        if(!v[k][i].dir&&!vis[v[k][i].val])
            dfs1(v[k][i].val,gp);
    }
}
 
void init(int k){
    for(int i=0;i<v[k].size();i++){
        if(v[k][i].dir&&p[v[k][i].val]!=p[k]){
            in[p[v[k][i].val]]++;
            out[p[k]]++;
        }
    }
}
 
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        while(1){
            scanf("%d",&to);
            if(!to)break;
            v[i].push_back(node{to,1});
            v[to].push_back(node{i,0});
        }
    }
    for(int i=1;i<=n;i++)
        if(!vis[i])dfs(i);
    memset(vis,0,sizeof(vis));
    for(int i=n-1;i>=0;i--)
        if(!vis[ord[i]])dfs1(ord[i],cnt++);
    if(cnt==1){
        printf("1\n0\n");
        return 0;
    }
    for(int i=1;i<=n;i++)init(i);
    for(int i=0;i<cnt;i++){
        if(!in[i])cnt_in++;
        if(!out[i])cnt_out++;
    }
    printf("%d\n",cnt_in);
    printf("%d\n",max(cnt_in,cnt_out));
}

[HOJ] 70 植樹問題

每段竹竿脆弱度*該竹竿上的物品重量=每個物品的重量*該物品到根所經過竹竿的脆弱度總和
取每物品到根的最短路

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define MAX 50005
#define INF 3000000000
using namespace std;
 
struct node{
    int to,val;
};
vector<node> v[MAX];
queue<int> q;
bool inq[MAX];
int w[MAX],fr,to,val,n,m,now;
long long dis[MAX],ans;
 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
        dis[i]=INF;
    }
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&fr,&to,&val);
        v[fr].push_back(node{to,val});
        v[to].push_back(node{fr,val});
    }
    dis[1]=0;
    q.push(1);
    inq[1]=true;
    while(!q.empty()){
        now=q.front();
        q.pop();
        inq[now]=false;
        for(int i=0;i<v[now].size();i++){
            if(dis[now]+v[now][i].val<dis[v[now][i].to]){
                dis[v[now][i].to]=dis[now]+v[now][i].val;
                if(!inq[v[now][i].to])q.push(v[now][i].to);
                inq[v[now][i].to]=true;
            }
        }
    }
    for(int i=1;i<=n;i++){
        ans+=w[i]*dis[i];
        if(dis[i]==INF){
            puts("No Answer\n");
            return 0;
        }
    }
    printf("%lld\n",ans);
}

[TIOJ] 1012 Rails

紀錄違規發生的時間區間
任意點違規次數總和超過就錯

#include<cstdio>
#include<stack>
#define MAX 1005
using namespace std;
stack<int> st;
int n,m,tmp,t,now=1,p[MAX],cnt[MAX];
bool in[MAX],f;

int main(){
    scanf("%d%d",&n,&m);
    while(n--){
        f=false;
        scanf("%d",&tmp);
        while(!st.empty()&&in[st.top()])st.pop();
        while(st.empty()||(!st.empty()&&st.top()<tmp)){
            st.push(++now);
            p[now]=t;
            f=true;
        }
        if(f)t++;
        if(st.top()==tmp)st.pop();
        else {
            for(int i=p[tmp];i<t;i++)cnt[i]++;
            in[tmp]=true;
        }
    }
    f=false;
    for(int i=0;i<t;i++){
        if(cnt[i]>m)f=1;
    }
    if(f)puts("no");
    else puts("yes");
}

[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);
}

[HOJ]20 堆石頭遊戲

若剩下偶數組兩兩石頭數目一樣的堆
先取者必輸
剩下的就普通Nim遊戲

#include<cstdio>
int main(){
    int n,p,tmp,T,now;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        now=p=0;
        for(int i=0;i<n;i++){
            scanf("%d",&tmp);
            if((n-i)%2){
                now^=tmp-p;
            }
            p=tmp;
        }
        if(now)puts("TAK");
        else puts("NIE");
    }
}

[HOJ]21 大象

先考慮個別的循環節
並且以該循環節的最小值mn當作調換的點
求出調換該循環節所有點所花費的值

令所有點中的最小值為mm
枚舉所有循環節
如果在mm和mn調換後會有更佳解
則更新值

#include<cstdio>
#include<vector>
#define MAX 1000005
#define INF 1000000000
using namespace std;
struct node{
    int m,l;
};
vector<node> e;
int v[MAX],a[MAX],b[MAX],nt[MAX];
int n,siz,mn,mm=INF;
long long ans,val;
bool vis[MAX];
void dfs(int k){
    siz++;
    val+=v[k];
    vis[k]=true;
    if(mn>v[k])mn=v[k];
    if(!vis[nt[k]])dfs(nt[k]);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<n;i++){
        scanf("%d",&b[i]);
        nt[a[i]]=b[i];
    }
    for(int i=1;i<=n;i++){
        if(v[i]<mm)mm=v[i];
        if(!vis[i]){
            mn=INF;
            siz=val=0;
            dfs(i);
            ans+=val+mn*(siz-2);
            e.push_back(node{mn,siz});
        }
    }
    for(int i=0;i<e.size();i++){
        if(e[i].m*(e[i].l-1)>e[i].m*2+mm*2+mm*(e[i].l-1))
            ans-=e[i].m*(e[i].l-1)-e[i].m*2-mm*2-mm*(e[i].l-1);
    }
    printf("%lld\n",ans);
}

[HOJ]235 ATM

一個點可以重覆經過
SCC縮環+SPFA

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAX 500005
using namespace std;
int val[MAX],dis[MAX],p[MAX],nval[MAX];
int fr,to,s,t,tmp,cnt,n,m,ans;
vector<int> ed,nv[MAX];
vector<pair<int,bool> > v[MAX];
queue<int> q;
bool bar[MAX],vis[MAX];
void dfs(int k){
    vis[k]=true;
    for(int i=0;i<v[k].size();i++){
        if(v[k][i].second&&!vis[v[k][i].first])
            dfs(v[k][i].first);
    }
    ed.push_back(k);
}
void dfs2(int k,int num){
    p[k]=num;
    nval[num]-=val[k];
    vis[k]=true;
    for(int i=0;i<v[k].size();i++){
        if(!v[k][i].second&&!vis[v[k][i].first])
            dfs2(v[k][i].first,num);
    }
}
void dfs3(int k){
    for(int i=0;i<v[k].size();i++)
        if(v[k][i].second&&p[v[k][i].first]!=p[k])
            nv[p[k]].push_back(p[v[k][i].first]);   
} 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&fr,&to);
        v[fr].push_back(make_pair(to,1));
        v[to].push_back(make_pair(fr,0));
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&val[i]);
        dis[i-1]=1000000000;
    }
    scanf("%d%d",&s,&t);
    for(int i=1;i<=n;i++)
        if(!vis[i])dfs(i);
    memset(vis,0,sizeof(vis));
    for(int i=n-1;i>=0;i--)
        if(!vis[ed[i]])dfs2(ed[i],cnt++);
    for(int i=1;i<=n;i++)
        dfs3(i);
    memset(vis,0,sizeof(vis));
    dis[p[s]]=nval[p[s]];
    vis[p[s]]=true;
    q.push(p[s]);
    while(!q.empty()){
        tmp=q.front();
        q.pop();
        vis[tmp]=0;
        for(int i=0;i<nv[tmp].size();i++){
            if(dis[tmp]+nval[nv[tmp][i]]<dis[nv[tmp][i]]){
                dis[nv[tmp][i]]=dis[tmp]+nval[nv[tmp][i]];
                if(!vis[nv[tmp][i]]){
                    q.push(nv[tmp][i]); 
                    vis[nv[tmp][i]]=true;       
                }
            }   
        }
    }
    for(int i=0;i<t;i++){
        scanf("%d",&tmp);
        ans=min(ans,dis[p[tmp]]);
    }
    printf("%d\n",-ans);
}

[HOJ]28 看動畫

貪心

對於每次抽換都換掉離目前最遠的點
若已經在裡面了要更新

#include<cstdio>
#include<set>
#include<vector>
#include<functional>
#include<utility>
#define MAX 100005
using namespace std;
int n,p,k,tmp,a[5*MAX],t,pos[MAX];
set<pair<int,int> > s;
vector<int> v[MAX];
int main(){
    scanf("%d%d%d",&n,&k,&p);
    for(int i=0;i<p;i++){
        scanf("%d",&a[i]);
        v[a[i]].push_back(i);
    }
    for(int i=0;i<=n;i++)v[i].push_back(1000000000);
    for(int i=0;i<p;i++){
        if(s.find(make_pair(-v[a[i]][pos[a[i]]],a[i]))!=s.end()){
            s.erase(make_pair(-v[a[i]][pos[a[i]]],a[i]));
            s.insert(make_pair(-v[a[i]][++pos[a[i]]],a[i]));
            continue;
        }
        if(s.size()>=k){
            s.erase(s.begin());
            t++;
        }
        s.insert(make_pair(-v[a[i]][++pos[a[i]]],a[i]));
    }
    printf("%d\n",t);
}

[HOJ]394 壞掉的水表

流入=流出

#include<cstdio>
int n,m,tmp,a;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%d",&tmp);
            if(tmp==-1)continue;
            if((i+j)%2)a+=tmp;
            else a-=tmp;
        }
    }
    printf("%d\n",a>0? a:-a);
}

[HOJ]343 老鼠愛大米

#include<cstdio>
#include<vector>
#define MAX 100005
using namespace std;
vector<int> v[MAX];
int num[MAX],n,m,k,fr,to,sum;
bool vis[MAX];
void dfs(int t){
    vis[t]=1;
    sum+=num[t];
    for(int i=0;i<v[t].size();i++){
        if(!vis[v[t][i]])dfs(v[t][i]);
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++){
        scanf("%d%d",&fr,&to);
        v[to].push_back(fr);
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);
    dfs(k);
    printf("%d\n",sum);
}

[HOJ]241 APIO 2012 Dispatching

題目

維護最大根可併堆

左偏樹+枚舉領導者dfs求解

#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
#define MAX 100005
using namespace std;
struct node{
    node *l,*r;
    int val,deep;
};
struct info{
    int c,v;
}p[MAX];
vector<int> v[MAX];
node *head[MAX];
int n,m,b,rt;
long long sum[MAX],num[MAX],ans;
node* merge(node *a,node *b){
    if(a==NULL)return b;
    if(b==NULL)return a;
    if(b->val>a->val)swap(a,b);
    a->r=merge(a->r,b);
    if(a->l==NULL||a->r!=NULL&&a->r->deep>a->l->deep)swap(a->r,a->l);
    a->deep=a->r==NULL? 0:a->r->deep+1;
    return a;
}
void dfs(int k){
    head[k]=new(node);
    sum[k]=1;
    num[k]=p[k].c;
    head[k]->val=p[k].c;
    head[k]->l=NULL;
    head[k]->r=NULL;
    for(int i=0;i<v[k].size();i++){
        dfs(v[k][i]);
        sum[k]+=sum[v[k][i]];
        num[k]+=num[v[k][i]];
        head[k]=merge(head[k],head[v[k][i]]);
    }
    while(num[k]>m){
        sum[k]--;
        num[k]-=head[k]->val;
        head[k]=merge(head[k]->l,head[k]->r);
    }
    ans=max(ans,p[k].v*sum[k]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&b,&p[i].c,&p[i].v);
        if(b==0)rt=i;
        v[b].push_back(i);
    }
    dfs(rt);
    printf("%lld\n",ans);
}

[HOJ]367 23213

#include<cstdio>
#include<utility>
#include<map>
#include<algorithm>
#define MAX 200005
using namespace std;
pair<int,int> tmp;
map<pair<int,int>,int> m;
char s[MAX];
int a[MAX],b[MAX],n,ans;
int main(){
    scanf("%d%s",&n,s);
    for(int i=0;i<n;i++){
        if(s[i]=='1')a[i+1]=1;
        if(s[i]=='2')a[i+1]=b[i+1]=-1;
        if(s[i]=='3')b[i+1]=1;
    }
    for(int i=0;i<=n;i++){
        if(i!=0){
            a[i]+=a[i-1];
            b[i]+=b[i-1];
        }
        tmp=make_pair(a[i],b[i]);
        if(m.count(tmp)){
            ans=max(ans,i-m[tmp]);
        }
        else m[tmp]=i;
    }
    printf("%d\n",ans);
}

[HOJ]333 今天情人節ㄛ

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,p,mi,val[10005],cost[10005],dp[10005];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d",&mi);
        for(int j=0;j<mi;j++)
            scanf("%d%d",&cost[j],&val[j]);
        for(int C=n;C>=0;C--){
            for(int j=0;j<mi;j++){
                if(C-cost[j]>=0){
                    dp[C]=max(dp[C],dp[C-cost[j]]+val[j]);
                }
            }
        }
    }
    printf("%d\n",dp[n]);
}

[HOJ]205 妖怪之山

#include<cstdio>
int dp[2][2][1505],a[1505],n,ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        for(int j=i-1;j>=1;j--){
            if(a[j]<a[i]){
                dp[1][0][i]++;
                dp[1][1][i]+=(dp[0][1][j]+dp[0][0][j]);
            }
            if(a[j]>a[i]){
                dp[0][0][i]++;
                dp[0][1][i]+=(dp[1][1][j]+dp[1][0][j]);
            }
            dp[1][1][i]%=12345;
            dp[0][1][i]%=12345;
        }
        ans+=dp[1][1][i]+dp[0][1][i];
        ans%=12345;
    }
    printf("%d\n",ans);
}