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