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