USACO 2015 December Contest, Gold Problem 2. Fruit Feast

每個方法可以表現成x*A+y*B + (z*A + u*B)/2

那麼，就可以輕鬆過了XDDD

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAX_T = 5000002;

int dp[MAX_T];

int main () {

freopen("feast.in","r",stdin);

freopen("feast.out","w",stdout);

int T,a,b;

while (scanf("%d %d %d",&T,&a,&b) != EOF) {

memset(dp,0,sizeof(dp));

for (int x=a;T>=x;x+=a) dp[x]=x;

for (int x=b;T>=x;x+=b) dp[x]=x; 

for (int x=1;T>=x;x++) {

if (dp[x]==x && x+b<=T) dp[x+b]=x+b;

}

// puts("hi");

int ans=-1;

for (int x=1;T>=x;x++) {

// cout << "dp["<<x<<"]="<<dp[x]<<endl;

if (dp[x]==x) {

int t1=dp[x];

if (ans<t1) ans=t1;

int t2=dp[x] + (a/2);

if (ans<t2 && t2<=T) ans=t2;

t1=dp[x] + (b/2);

if (ans<t1 && t1<=T) ans=t1;

t2=dp[x] + (a+b)/2;

if (ans<t2 && t2<=T && a+b<=T) ans=t2;

}

// cout<<ans<<endl;

} 

printf("%d\n",ans);

}

}

USACO 2015 January Contest, Gold Problem 2. Moovie Mooving [位元dp]

http://www.usaco.org/index.php?page=viewproblem2&cpid=515

我當初看的時候，也不知道題目再做什麼

再想想，就發現好像是bitmask的dp!!!

於是，就開了dp[1<<MAX_N][MAX_N]陣列，紀錄1<<MAX_N最後是MAX_N最長可以延伸到哪裡。

但是，不幸的很，TLE了！！

後來想想，後面那個維度根本用不到！！！(之前做bitmask有用到所以就不小心在腦海中留下不好印象XDD)

於是，就AC了

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_N = 21;
vector <int> C[MAX_N];
int t[MAX_N];
int dp[(1<<MAX_N)];
int n,l;

int count_bit(int x) {
    int ret=0;
    while (x>0) {
        if (x!=(x/2)+(x/2)) ret++;
        x/=2;
    }
    return ret;
}

int get_dp(int i,int j) {   //i-->which n , j-->dp_val
//    cout << "get " << i << " and " << j << endl;
    int tmp=j;
    int id=lower_bound(C[i].begin(),C[i].end(),tmp) - C[i].begin();
    
    if (C[i][id]!=j) id--;
//    cout<<"("<<j<<" vs "<<C[i][id]<<")";
    if (C[i][id]==-1) return 0;
//    puts("still alive ");
    return max(C[i][id]+t[i] , j);
}

int main () {
    if (fopen("movie.in","r")) {
        freopen("movie.in","r",stdin);
        freopen("movie.out","w",stdout);
    }
    
    int k,qq;
    while (scanf("%d %d",&n,&l) != EOF) {
        for (int x=0;n>x;x++) {
            scanf("%d %d",&t[x],&k);
            C[x].clear();
            C[x].push_back(-1);
            for (int y=0;k>y;y++) {
                scanf("%d",&qq);
                C[x].push_back(qq);
            }
        }
        memset(dp,0,sizeof(dp));
        //bitmask DP
        for (int i=0;n>i;i++) {
            dp[(1<<i)]=get_dp(i,0);
        }
        
        for (int x=1;(1<<n)>=x;x++) {
            int tmp=x;
            int i=0;
            
            for (int j=0;n>j;j++) {
                if (((1<<j)|x)!=x)dp[((1<<j)|x)]=max(dp[((1<<j)|x)],get_dp(j,dp[x]));
            }
                
    
//            cout<<"x="<<x<<" : "<<count_bit(x)<<endl;
        }
        int ans=19343;
        for (int x=0;(1<<n)>=x;x++) {
//            cout << "x = " <<x << " : ";
            for (int y=0;1>y;y++) {
                if (dp[x]>=l && count_bit(x)<ans) ans=count_bit(x);
//                cout<<dp[x][y] << ' ';
            }
//            cout << endl;
        }
        printf("%d\n",(ans==19343?-1:ans));
    }
}

(Zj) d712: The 3n + 1 problem

http://zerojudge.tw/ShowProblem?problemid=d712

這題是UVA加強版

我們要把每次做好的值紀錄下來

再開線段樹優化

就好了

對了, 如果值>1000000,不要傻傻的開map去存,會爛掉!!!

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <assert.h>
#include <map>
using namespace std;

int dp[20000002];
map<long long int, int> dp2;



struct Node {
Node* lc;
Node* rc;
int val;
int tag;
Node() {
lc=rc=NULL;
val=-1;
tag=0;
}
void pull() {
val=max(lc->val,rc->val);
tag=(lc->tag & rc->tag);
}
};

Node* root;

Node* Build(int L,int R) {
Node* node = new Node();
if (L==R) {
if (L!=1)node->val=1000;
else node->val=1;
return node;
}
int mid=(L+R)>>1;
node->lc=Build(L,mid);
node->rc=Build(mid+1,R);
node->pull();
return node;
}

void modify(Node* node,int L,int R,int pos,int Val) {
if (L==R) {
node->val=Val;
node->tag=1;
return;
}
int mid=(L+R)>>1;
if (node->lc->tag==0&&mid>=pos) modify(node->lc,L,mid,pos,Val);
if (node->rc->tag==0&&mid<pos) modify(node->rc,mid+1,R,pos,Val);
node->pull();
}

int query(Node* node,int L,int R,int l,int r) {
// cout<<L<<" ~ "<<R<<endl;
if (R<l || L>r) return -1;
else if (l<=L && R<=r) return node->val;
int mid=(L+R)>>1;
return max(query(node->lc,L,mid,l,r),query(node->rc,mid+1,R,l,r));
}

int get_ans(long long int id) {
// cout<<id<<endl;
// cout<<id<<endl;
if (id<20000000&&dp[id]!=0) return dp[id];
// else if (dp2[id]!=0) return dp2[id];
else if (id > 10000000 && id%2==0) {
return get_ans(id/2)+1;
}
else if (id > 10000000 && id%2==1) return get_ans(3*id+1)+1;
else if (id==1) return dp[id] = 1;
else if (id%2==0) {
dp[id] = get_ans(id/2)+1;
if (id<=1000000) modify(root,1,1000000,id,dp[id]);
return dp[id];
}
else {
dp[id] = 2+get_ans((3*id+1)/2);
if (id<=1000000) modify(root,1,1000000,id,dp[id]);
return dp[id];
}
}

void swap(int& a,int &b) {
int t=a;
a=b;
b=t;
}

int main () {
root = Build(1,1000000);
int i,j;
while (scanf("%d %d",&i,&j) != EOF) {
bool log=false;
if (i>j) swap(i,j),log=true;
if (query(root,1,1000000,i,j) == 1000) {
for (int x=i;j>=x;x++) {
if (dp[x]==0) {
get_ans(x);
// modify(root,1,1000000,x,dp[x]);
}
}

}
printf("%d %d %d\n",(log?j:i),(log?i:j),query(root,1,1000000,i,j));
}
}

USACO 2014 December Contest, Gold Problem 2. Marathon

http://www.usaco.org/index.php?page=viewproblem2&cpid=495

一開始也不知道這題是在做什麼

之後想想我們似乎要維護個兩點之間距離 + 跨一點的距離

然後似乎很麻煩

題解也不知道要怎麼寫XD

往上面兩個方向仔細去想即可

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <vector>

#include <utility>

#include <cmath>

using namespace std;

typedef long long LL;

const int MAX_N = 100003;

LL pre_seg[400021];

LL two_seg[400021];

LL d[MAX_N];

LL d2[MAX_N];

void Build(int id,int L,int R) {

if (L==R) {

pre_seg[id] = d[L];

return;

}

int mid=(L+R)>>1;

Build(id*2,L,mid);

Build(id*2+1,mid+1,R);

pre_seg[id]=pre_seg[id*2]+pre_seg[id*2+1];

}

void modify(int id,int L,int R,int pos,int val) {

if (L==R) {

pre_seg[id]=val;

return;

}

int mid=(L+R)>>1;

if (pos<=mid) modify(id*2,L,mid,pos,val);

else modify(id*2+1,mid+1,R,pos,val);

pre_seg[id]=pre_seg[id*2]+pre_seg[id*2+1];

}

int query(int id,int L,int R,int l,int r) {

if (L>r || l > R) return 0;

if (l<=L && R<=r) {

return pre_seg[id];

}

int mid=(L+R)>>1;

return query(id*2,L,mid,l,r)+query(id*2+1,mid+1,R,l,r);

}

void Build2(int id,int L,int R) {

if (L==R) {

two_seg[id]=d2[L];

return;

}

int mid=(L+R)>>1;

Build2(id*2,L,mid);

Build2(id*2+1,mid+1,R);

two_seg[id]=max(two_seg[id*2],two_seg[id*2+1]);

}

void modify2(int id,int L,int R,int pos,int val) {

if (L==R) {

two_seg[id]=val;

return;

}

int mid=(L+R)>>1;

if (pos<=mid) modify2(id*2,L,mid,pos,val);

else modify2(id*2+1,mid+1,R,pos,val);

two_seg[id]=max(two_seg[id*2],two_seg[id*2+1]);

}

int query2(int id,int L,int R, int l,int r) {

if (l>r) return 0;

if (L>r || l > R) return 0;

else if (l<=L && R<=r) return two_seg[id];

int mid=(L+R)>>1;

return max(query2(id*2,L,mid,l,r),query2(id*2+1,mid+1,R,l,r));

}

int x[MAX_N];

int y[MAX_N];

int main () {

freopen("marathon.in","r",stdin);

freopen("marathon.out","w",stdout);

int n,q;

while (scanf("%d %d",&n,&q) != EOF) {

for (int i=1;n>=i;i++) {

scanf("%d %d",&x[i],&y[i]);

if (i>1) {

d[i-1]=abs(x[i]-x[i-1]) + abs(y[i]-y[i-1]);

}

if (i>2) {

d2[i-2]=d[i-2]+d[i-1]-abs(x[i]-x[i-2])-abs(y[i]-y[i-2]);

}

}

Build(1,1,n-1);

Build2(1,1,n-2);

for (int i=0;q>i;i++) {

char t;

cin >> t;

if (t=='Q') {

int i,j;

scanf("%d %d",&i,&j);

printf("%d\n",query(1,1,n-1,i,j-1)-query2(1,1,n-2,i,j-2));

}

else {

int i,j,k;

scanf("%d %d %d",&i,&j,&k);

x[i]=j;

y[i]=k;

if (i>1&&n>i) {

d[i-1]=abs(x[i]-x[i-1]) + abs(y[i]-y[i-1]);

modify(1,1,n-1,i,abs(x[i+1]-x[i])+abs(y[i+1]-y[i]));

d[i]=abs(x[i+1]-x[i]) + abs(y[i+1]-y[i]);

modify(1,1,n-1,i-1,abs(x[i]-x[i-1])+abs(y[i]-y[i-1]));

}

else if (i==1) {

d[i]=abs(x[i+1]-x[i]) + abs(y[i+1]-y[i]);

modify(1,1,n-1,i,abs(x[i+1]-x[i])+abs(y[i+1]-y[i]));

}

else if (i==n) {

d[i-1]=abs(x[i]-x[i-1]) + abs(y[i]-y[i-1]);

modify(1,1,n-1,i-1,abs(x[i]-x[i-1])+abs(y[i]-y[i-1]));

}

if (i>2) d2[i-2]=d[i-2]+d[i-1]-abs(x[i]-x[i-2])-abs(y[i]-y[i-2]);

if (i>1&&i<n) d2[i-1]=d[i-1]+d[i]-abs(x[i+1]-x[i-1])-abs(y[i+1]-y[i-1]);

if (i<n-1)d2[i]=d[i]+d[i+1]-abs(x[i+2]-x[i])-abs(y[i+2]-y[i]);

if (i>2) modify2(1,1,n-2,i-2,d2[i-2]);

if (i>1 && i<n) modify2(1,1,n-2,i-1,d2[i-1]);

if (i<n-1) modify2(1,1,n-2,i,d2[i]);

}

}

// cout<<"---\n";

// for (int x=1;n-1>=x;x++) printf("%d\n",query(1,1,n-1,x,x));

// cout<<"---\n";

// for (int x=1;n-2>=x;x++) printf("%d\n",query2(1,1,n-2,x,x));

// for (int x=1;n-2>=x;x++) cout<<"d2["<<x<<"]="<<d2[x]<<endl;

}

}

(POJ) 3104 Drying

http://poj.org/problem?id=3104

首先，要先注意一下題目敘述：只有用散熱機(一次減k)，就不能風乾！！！

然後，答案具有單調性，而且似乎要用long long 存

於是，我們來列式：假設我們總共需要花id天，其中 j 天用散熱機， id - j 天用風乾，則：

a[x] - (id - j) - jk <= 0          -->    j >= (a[x] - id) / (k-1)

這裡要特別注意k=1的情況，要分case討論

於是乎，就AC啦XDDD

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAX_N = 100003;

long long int a[MAX_N];

long long int n,k;

bool check(long long int id) {

long long int ret=0;

for (int x=0;n>x;x++) {

if (a[x]<=id) continue;

else {

long long tmp=a[x];

if (k!=1) ret += (a[x]-id)/(k-1) + int(bool((a[x]-id)%(k-1)!=0));

else ret+=(a[x]-id);

}

// cout<<"x="<<x<<" ; ret = " <<ret<<endl;

}

// cout<<id<<" : "<<ret<<endl;

if (k==1&&ret>0)return false;

else if (k==1) return true;

if (id>=ret) return true;

else return false;

}

int main () {

while (scanf("%lld",&n) != EOF) {

for (int x=0;n>x;x++) scanf("%lld",&a[x]);

scanf("%lld",&k);

long long int l=0, r=450000000000000000;

while (r-l != 1) {

long long int mid=(l+r)/2;

if (check(mid)==true) r=mid;

else l=mid;

}

printf("%d\n",r);

}

}

(POJ) 3111 K. Best [平均最大值]

http://poj.org/problem?id=3111

這是「平均最大化」的題目。

我先把題目想成「求出最大的平均值S」。

若平均值=S，則代表說 ( v[1] + v[2] + v[3] + .... + v[k] ) / (w[1] + w[2] + w[3] + ..... + w[k] ) >=S ，則此S具有單調性，那我們可以二分搜 v[x] - S * w[x]  (移項試試看)，就okay了。

O (n lg n)

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

const int MAX_N = 100003;

double v[MAX_N];
double w[MAX_N];
double num[MAX_N];
int n,k;


double get_ans(double i) {
    for (int x=0;n>x;x++) num[x] = v[x] - i * w[x];
    sort(num,num+n);
    double ret=0.0;
    for (int x=n-1;x>=(n-k);x--) ret+=num[x];
    return ret;
}

struct Node {
    int id;
    double val;
} node[MAX_N];

bool operator< (const Node& n1, const Node& n2) {
    return n1.val < n2.val;
}

void print_ans(double i) {
    for (int x=0;n>x;x++) node[x].id=x;
    for (int x=0;n>x;x++) node[x].val = v[x] - i * w[x];
    sort(node,node+n);
    double ret=0.0;
    for (int x=n-1;x>=(n-k);x--) {
        printf("%d",node[x].id+1);
        if (x!=n-k) printf(" ");
    }
    puts("");
}

int main () {
    while (scanf("%d %d",&n,&k) != EOF) {
        for (int x=0;n>x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            v[x]=i;
            w[x]=j;
        }
        //算式>mu --> v[i] - mu*w[i] 二分搜XDDD
        double l=0.0,r=20000000.0;
        while (r-l > 1e-7) {
            double mid=(l+r)/2;
            double ret=get_ans(mid);
            if (ret>=0.0) l=mid;
            else r=mid;
        }
        print_ans(r);
    }
}

(TOJ) 293.樹重心

http://sprout.tw/oj/pro/293/

本題就是要求樹的重心

樹重心定義：使得「拔除某節點後，形成的若干棵樹分別的節點數量中的最大值」<=樹的大小/2。

題目中有範例。

要怎麼解呢？

如果把它看成一棵樹，我們會需要維護的是 1.兒子的總合 2.眾多兒子中的最大的那個

因為我們要取若干棵節點數量中的最大值，那父節點就是(全部節點 - 兒子節點總合 - 自己)，那就是max (父節點, 眾多兒子中的最大)。

那就一次dfs就可以完成了！

阿對了，哪個點當根都可以，所以我的code是用random

//樹重心


#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <ctime>
using namespace std;

const int MAX_N = 100003;

vector<int> edg[MAX_N];

struct Node {
    int val;
    int sum;
    int max;
} node[MAX_N];

bool visit[MAX_N];

int dfs(int id) {
    visit[id]=true;
    int len=edg[id].size();
    for (int x=0;len>x;x++) {
        int tmp=edg[id][x];
        if (visit[tmp]==true) ;  //回到父親
        else {
            int t=dfs(tmp);
            node[id].sum+=t;
            node[id].max = max(node[id].max,t);
        }
    }
    return node[id].sum+1;
}

int main () {
    srand(time(NULL));
    int T;
    scanf("%d",&T);
    while (T--) {
        int n;
        scanf("%d",&n);
        //init
        for (int x=0;n>x;x++) {
            edg[x].clear();
            node[x].sum=node[x].max = 0;
            node[x].val = x;
            visit[x]=false;
        }
        for (int x=0;n-1>x;x++) {
            int a,b;
            scanf("%d %d",&a,&b);
            edg[a].push_back(b);
            edg[b].push_back(a);
        }
        int id = rand() % n;
        dfs(id);
        int ans=n;
        for (int x=0;n>x;x++) {
            int tmp=max(node[x].max,n-node[x].sum-1);
            ans=min(ans,tmp);
        }
        for (int x=0;n>x;x++) {
            int tmp=max(node[x].max,n-node[x].sum-1);
            if (tmp==ans) {
                printf("%d\n",x);
                break;
            }
        }
        
    }
}