序列(sequence)
【題目描述】
蛤布斯有一個序列,初始為空。它依次將 1-n 插入序列,其中 i插到當前第 ai 個數的右邊 (ai=0 表示插到序列最左邊)。它希望你幫
它求出最終序列。
【輸入數據】
第一行一個整數 n。第二行 n 個正整數 a1~an。
【輸出數據】
輸出一行 n 個整數表示最終序列,數與數之間用一個空格隔開。
【樣例輸入】
5
0 1 1 0 3
【樣例輸出】
4 1 3 5 2
【數據范圍】
對於 30%的數據,n<=1000。
對於 70%的數據,n<=100000
對於 100%的數據,n<=1000000,0<=ai<i。
題解
從後往前插入,對於一個數,插入到當前第個空格即可。用線段樹維護當前第個空格的位置下標。
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int n; int a[1000005],ans[1000005]; struct hh { int l,r,val; bool flag; }; hh lt[5000005]; void build(int root,int l,int r) { int mid; lt[root].l=l; lt[root].r=r; if(l==r) { lt[root].val=1; return; } mid=(l+r)>>1; build(root<<1,l,mid); build(root<<1|1,mid+1,r); lt[root].val=lt[root<<1].val+lt[root<<1|1].val; } int query(int root,int now) { int mid; if(lt[root].l==lt[root].r) return lt[root].l; if(lt[root<<1].val>=now) return query(root<<1,now); else return query(root<<1|1,now-lt[root<<1].val); } void del(int root,int pre) { if(lt[root].l<=pre&<[root].r>=pre) lt[root].val--; if(lt[root].l==lt[root].r) { lt[root].flag=true; return; } if(lt[root<<1].l<=pre&<[root<<1].r>=pre) del(root<<1,pre); else if(lt[root<<1|1].l<=pre&<[root<<1|1].r>=pre) del(root<<1|1,pre); } int main() { int i,j,pre; freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); for(i=n;i>=1;i--) { pre=query(1,a[i]+1); ans[pre]=i; del(1,pre); } for(i=1;i<=n;i++) printf("%d ",ans[i]); fclose(stdin); fclose(stdout); return 0; }
背包(pack)
【題目描述】
蛤布斯有 n 個物品和一個大小為 m 的背包,每個物品有大小和價值,它希望你幫它求出背包裡最多能放下多少價值的物品。
【輸入數據】
第一行兩個整數 n,m。接下來 n 行每行兩個整數 xi,wi,表示第 i個物品的大小和價值。
【輸出數據】
一行一個整數表示最大價值。
【樣例輸入】
5 100
95 80
4 18
3 11
99 100
2 10
【樣例輸出】
101
【數據范圍】
對於 20%的數據,xi<=1500。
對於 30%的數據,wi<=1500。
對於 100%的數據,n<=40,0<=m<=10^18,0<=xi,wi<=10^15。
題解
折半搜索+二分查找
#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int n,tn,cnt,tot; long long m,ans=0; struct hh { long long x,w; }a[45],q[2000005]; void dfsa(int,long long,long long); void dfsb(int,long long,long long); long long search(long long); bool cmp(hh a,hh b){return a.x==b.x?a.w>b.w:a.x<b.x;} long long maxx(long long a,long long b){return a>b?a:b;} int main() { int i,j; freopen("pack.in","r",stdin); freopen("pack.out","w",stdout); scanf("%d%lld",&n,&m); tn=n>>1; for(i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].w); dfsa(1,0,0);tot=1; sort(q+1,q+cnt+1,cmp); for(i=2;i<=cnt;i++) if(q[i].x!=q[i-1].x) q[++tot]=q[i]; for(i=1;i<=tot;i++) if(q[i].w<q[i-1].w) q[i].w=q[i-1].w; dfsb(tn+1,0,0); printf("%lld",ans); fclose(stdin); fclose(stdout); return 0; } void dfsa(int pre,long long xx,long long ww) { if(pre>tn) { q[++cnt]=(hh){xx,ww}; return; } dfsa(pre+1,xx,ww); if(xx+a[pre].x<=m) dfsa(pre+1,xx+a[pre].x,ww+a[pre].w); } void dfsb(int pre,long long xx,long long ww) { long long temp; if(pre>n) { temp=search(m-xx); ans=maxx(ans,ww+temp); return; } dfsb(pre+1,xx,ww); if(xx+a[pre].x<=m) dfsb(pre+1,xx+a[pre].x,ww+a[pre].w); } long long search(long long xx) { int l,r,mid; if(xx<q[1].x) return 0; l=1;r=tot; while(l<r) { mid=l+r+1>>1; if(q[mid].x<=xx) l=mid; else r=mid-1; } return q[l].w; }
線段樹(segment)
【題目描述】
重新定義一個線段樹,根結點仍然表示[1,n],但[l,r]的左右兒子分別表示[l,k]和[k+1,r],這裡的 k 可以在[l,r)中任取。
每次訪問從根結點開始,而且只有在當前結點是葉子結點時才會直接結束訪問,否則一定會向下訪問。
蛤布斯將對 m 個區間[ai,bi]進行訪問,你需要幫他為每個結點選取合適的 k,輸出每次訪問的結點個數最小和。
【輸入數據】
第一行兩個整數 n,m,接下來 m 行每行兩個整數 ai,bi。
【輸出數據】
一行一個整數表示答案。
【樣例輸入】
6 6
1 4
2 6
3 4
3 5
2 3
5 6
【樣例輸出】
40
【數據范圍】
對於 20%的數據,n<=50,m<=100。
對於 40%的數據,n<=200。
對於 70%的數據,n<=1000。
對於 100%的數據,n<=5000,m<=100000。
題解
f[i,j]表示結點[i,j]的子樹中被訪問的最小次數,w[i,j]表示結點[i,j]被訪問的次數,即與[i,j]相交的區間數。
f[i,j]=min{f[i,k]+f[k+1,j]}+w[i,j] (i<=k<j)
首先預處理出 w,那麼這個 dp 復雜度是 O(n^3),用四邊形不等式可以優化到 O(n^2)
#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int n,m; int l[5005],r[5005],f[5005][5005],w[5005][5005]; int main() { int i,j,k,x,y; freopen("segment.in","r",stdin); freopen("segment.out","w",stdout); scanf("%d%d",&n,&m); for(i=1;i<=m;++i) { scanf("%d%d",&x,&y); l[x]++;r[y]++; } for(i=1;i<=n;++i) r[i]+=r[i-1]; for(i=n;i>=1;i--) l[i]+=l[i+1]; memset(f,9999999,sizeof f); for(i=1;i<=n;i++) f[i][i]=m-r[i-1]-l[i+1]; for(i=1;i<=n;i++) w[i][i]=i; for(k=1;k<=n-1;k++) for(i=1;i<=n-k;i++) { for(j=w[i][i+k-1];j<=w[i+1][i+k]&&j+1<=i+k;++j) if(f[i][j]+f[j+1][i+k]<f[i][i+k]) { f[i][i+k]=f[i][j]+f[j+1][i+k]; w[i][i+k]=j; } f[i][i+k]+=(m-r[i-1]-l[i+k+1]); } printf("%d",f[1][n]); fclose(stdin); fclose(stdout); return 0; }