JLOI2015 真的不愧是NOI出題組出的，題目難度夠吊。不過每一道都是結(jié)論題和亂搞題真的很不好玩。。。

T1：[JLOI2015]有意義的字符串

首先貼下popoqqq的blog吧

感性的認(rèn)識就是感覺到部分分是個斐波那契數(shù)列的通項公式然后考慮是否能把該式子化成遞推式然后矩陣乘法算了。。感覺是超級惡心的一道題了，還得用快速乘法。。。

T2：[JLOI2015]城池攻占

首先這道題我們先考慮暴力，也就是每個點向父親跑，我們考慮能否一起做，可以發(fā)現(xiàn)在同一個點的騎士可以用一個堆維護(hù)一起跳（因為沒有改變優(yōu)先級的操作）然后再用懶標(biāo)記維護(hù)，我們可以直接用一個可合并堆來維護(hù)就可以啦

當(dāng)然這道題用線段樹，倍增都是可行的，就是空間比較拙計罷了，需要用一些奇奇怪怪的方法來干

CODE：

1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 typedef long long ll; 7 struct node{ 8 node *l,*r;int id,dis;ll s,lx,ly; 9 node(ll _s,int _id){ 10 l=r=0; 11 s=_s,id=_id,lx=1,ly=0;dis=1; 12 } 13 }; 14 inline void update(node* x) { 15 if (x->l) { 16 x->l->s*=x->lx; 17 x->l->s+=x->ly; 18 x->l->lx*=x->lx; 19 x->l->ly*=x->lx; 20 x->l->ly+=x->ly; 21 } 22 if (x->r) { 23 x->r->s*=x->lx; 24 x->r->s+=x->ly; 25 x->r->lx*=x->lx; 26 x->r->ly*=x->lx; 27 x->r->ly+=x->ly; 28 } 29 x->lx=1;x->ly=0; 30 } 31 node* merge(node* x,node *y) { 32 if (!x) return y; 33 if (!y) return x; 34 update(x);update(y); 35 if (x->s>y->s) swap(x,y); 36 x->r=merge(x->r,y); 37 if (!x->l||x->l->dis<x->r->dis) swap(x->l,x->r); 38 x->dis=x->r?x->r->dis+1:0; 39 return x; 40 } 41 inline node* del(node *x) { 42 update(x); 43 return merge(x->l,x->r); 44 } 45 #define maxn 300010 46 int dep[maxn],fa[maxn],a[maxn],ans[maxn],sum[maxn]; 47 ll h[maxn],v[maxn]; 48 node *root[maxn]; 49 int main(){ 50 freopen("fall.in","r",stdin); 51 freopen("fall.out","w",stdout); 52 int n,m; 53 scanf("%d%d",&n,&m); 54 for (int i=1;i<=n;i++) scanf("%lld",h+i); 55 dep[1]=1; 56 for (int i=2;i<=n;i++) { 57 scanf("%d%d%lld",fa+i,a+i,v+i); 58 dep[i]=dep[fa[i]]+1; 59 } 60 for (int i=1;i<=m;i++) { 61 ll s;int c; 62 scanf("%lld%d",&s,&c); 63 root[c]=merge(root[c],new node(s,i)); 64 ans[i]=dep[c]; 65 } 66 for (int i=n;i;i--) { 67 while (root[i]&&root[i]->s<h[i]) { 68 sum[i]++; 69 ans[root[i]->id]-=dep[i]; 70 root[i]=del(root[i]); 71 } 72 if (!root[i]) continue; 73 if (a[i]==0) { 74 root[i]->s+=v[i]; 75 root[i]->ly+=v[i]; 76 } 77 else { 78 root[i]->s*=v[i]; 79 root[i]->lx*=v[i]; 80 root[i]->ly*=v[i]; 81 } 82 root[fa[i]]=merge(root[fa[i]],root[i]); 83 } 84 for (int i=1;i<=n;i++) printf("%d\n",sum[i]); 85 for (int i=1;i<=m;i++) printf("%d\n",ans[i]); 86 return 0; 87 } View Code

T3:[JLOI2015]裝備購買

首先這個其實是求一個代價最小的最大線性無關(guān)集合（不會去線性代數(shù)把），線性無關(guān)集合也就是指在該集合中沒有一個向量能由該集合的其他向量組成

所以該集合其實就是一組基，那么我們可以每次用高斯消元判斷當(dāng)前的向量是否能由其他向量組成，如果不行的話就加入答案了

求代價最小就排個序即可

CODE：

1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define maxn 510 7 double a[maxn][maxn]; 8 int c[maxn]; 9 const double epx=1e-4; 10 inline bool zero(double x) {return x>-epx&&x<epx;} 11 int main(){ 12 freopen("purchase.in","r",stdin); 13 freopen("purchase.out","w",stdout); 14 int n,m; 15 scanf("%d%d",&n,&m); 16 int l=1,ans=0; 17 for (int i=1;i<=n;i++) 18 for (int j=1;j<=m;j++) scanf("%lf",a[i]+j); 19 for (int i=1;i<=n;i++) scanf("%d",&c[i]); 20 c[0]=1000000; 21 for (int i=1;i<=m;i++) { 22 int id=0; 23 for (int j=l;j<=n;j++) 24 if (!zero(a[j][i])&&c[id]>c[j]) id=j; 25 if (id==0) continue; 26 for (int j=1;j<=m;j++) swap(a[l][j],a[id][j]); 27 swap(c[id],c[l]); 28 ans+=c[l]; 29 for (int j=l+1;j<=n;j++) { 30 double t=a[j][i]/a[l][i]; 31 for (int k=i;k<=m;k++) a[j][k]-=a[l][k]*t; 32 } 33 l++; 34 } 35 printf("%d %d\n",l-1,ans); 36 return 0; 37 } View Code

T4：[JLOI2015]騙我呢

這道題比較奇葩啦

首先我們考慮每一行，可以發(fā)現(xiàn)是單調(diào)遞減的，并且肯定只缺了一個格，所以我們設(shè)f[i][j]為第i行缺j的方案數(shù)

可得f[i][j]=sigma(f[i-1][k]) k<=j+1

也就是f[i][j]=f[i][j-1]+f[i-1][j+1]

發(fā)現(xiàn)這個形式長得很像組合數(shù)，也可想求組合數(shù)那樣看成求路徑數(shù)。

我們把第i行向右平移i位，那么這個圖就變成這樣了

也就是把求這樣子的路徑方案數(shù)。

我們考慮先記下組合數(shù)那樣的矩形圖，再如何去掉左下和右上的點

很明顯我們可以將終點按y=-x-1那條線鏡面反射即可。

右上角也相似，但可能出現(xiàn)：左上->右下的情況，所以我們還要再去掉這種情況

...?

這樣推下去

CODE：

1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 typedef long long ll; 7 #define mod 1000000007 8 #define maxn 3001000 9 ll fac[maxn],inv[maxn]; 10 int n,m; 11 inline ll c(int x,int y) { 12 return fac[x]*1ll*inv[y]%mod*inv[x-y]%mod; 13 } 14 inline void _swap1(int &x,int &y) { 15 swap(x,y); 16 x--,y++; 17 } 18 inline void _swap2(int &x,int &y) { 19 swap(x,y); 20 x+=m+2,y-=m+2; 21 } 22 int main(){ 23 freopen("pwn.in","r",stdin); 24 freopen("pwn.out","w",stdout); 25 scanf("%d%d",&n,&m); 26 fac[0]=fac[1]=1; 27 inv[0]=inv[1]=1; 28 for (int i=2;i<=n+n+m+10;i++) { 29 fac[i]=fac[i-1]*i%mod; 30 inv[i]=(mod-mod/i)*inv[mod%i]%mod; 31 } 32 for (int i=1;i<=n+m+n+10;i++) (inv[i]=inv[i]*inv[i-1])%=mod; 33 int x=n+m+1,y=n; 34 ll ans=c(x+y,y); 35 for (;;) { 36 _swap1(x,y); 37 if (x<0||y<0) break; 38 (ans-=c(x+y,y))%=mod; 39 _swap2(x,y); 40 if (x<0||y<0) break; 41 (ans+=c(x+y,y))%=mod; 42 } 43 x=n+m+1,y=n; 44 for (;;) { 45 _swap2(x,y); 46 if (x<0||y<0) break; 47 (ans-=c(x+y,y))%=mod; 48 _swap1(x,y); 49 if (x<0||y<0) break; 50 (ans+=c(x+y,y))%=mod; 51 } 52 printf("%d\n",(ans+mod)%mod); 53 return 0; 54 } View Code

T5:[JLOI2015]管道連接

這是一個叫斯坦納樹的東西= =，以前知道但沒寫過，今天終于寫了一次了

首先我們可以記f[i][j]為點的聯(lián)通狀態(tài)為i，經(jīng)過點j的距離最小值，那么有兩種狀態(tài)轉(zhuǎn)移

i的轉(zhuǎn)移f[i][j]=max(f[k][j]+f[i^k][j])k為i的子集

j的轉(zhuǎn)移：我們先求出i的轉(zhuǎn)移，然后一邊spfa即可

這樣可以證明是正確的

這樣我們就求出了一組點的答案，那么多組點我們可以用一個dp來合并答案

寫起來還是挺舒服的，很多東西都能用這個東西解決，插頭dp啊什么的

CODE：

1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 #define maxk 1030 8 #define maxn 1100000 9 #define maxm 3100 10 #define inf 0x7fffffff 11 struct edges{ 12 int to,next,dist; 13 }edge[maxm*2]; 14 int next[maxk],l; 15 inline void addedge(int x,int y,int z) { 16 edge[++l]=(edges){y,next[x],z};next[x]=l; 17 } 18 typedef pair<int,int> ii; 19 #define fi first 20 #define se second 21 int f[maxk][maxk],n,p,a[15],c[15]; 22 priority_queue<ii,vector<ii>,greater<ii> > q; 23 bool b[maxk]; 24 inline void dij(){ 25 for (int i=1;i<1<<p;i++) 26 for (int j=1;j<=n;j++) f[i][j]=inf; 27 for (int i=0;i<p;i++) f[1<<i][a[i+1]]=0; 28 for (int i=1;i<1<<p;i++) { 29 while (!q.empty()) q.pop(); 30 memset(b,0,sizeof(b)); 31 for (int j=(i-1)&i;j>0;j=(j-1)&i) 32 for (int k=1;k<=n;k++) f[i][k]=min(f[i][k],f[j][k]+f[i^j][k]); 33 int *dist=f[i]; 34 for (int j=1;j<=n;j++) { 35 if (dist[j]==inf) continue; 36 q.push(ii(dist[j],j)); 37 } 38 int cnt=0; 39 while (!q.empty()) { 40 ii u=q.top();q.pop(); 41 if (b[u.se]) continue; 42 b[u.se]=1;cnt++; 43 if (cnt==n) break; 44 for (int i=next[u.se];i;i=edge[i].next) 45 if (edge[i].dist+dist[u.se]<dist[edge[i].to]){ 46 dist[edge[i].to]=edge[i].dist+dist[u.se]; 47 q.push(ii(dist[edge[i].to],edge[i].to)); 48 } 49 } 50 } 51 } 52 int g[maxk],d[15]; 53 inline int get(int x) { 54 int ans=0; 55 for (int i=1;x;i++,x>>=1) if (x&1) ans|=d[i]; 56 return ans; 57 } 58 int main(){ 59 freopen("channel.in","r",stdin); 60 freopen("channel.out","w",stdout); 61 int m; 62 scanf("%d%d%d",&n,&m,&p); 63 for (int i=1;i<=m;i++) { 64 int u,v,w; 65 scanf("%d%d%d",&u,&v,&w); 66 addedge(u,v,w); 67 addedge(v,u,w); 68 } 69 for (int i=1;i<=p;i++) scanf("%d%d",c+i,a+i); 70 dij(); 71 for (int i=1;i<=p;i++) d[c[i]]|=1<<(i-1); 72 for (int i=1;i<1<<p;i++) { 73 g[i]=inf; 74 int x=get(i); 75 for (int j=1;j<=n;j++) g[i]=min(g[i],f[x][j]); 76 } 77 for (int i=1;i<1<<p;i++) 78 for (int j=(i-1)&i;j>0;j=(j-1)&i) 79 g[i]=min(g[i],g[j]+g[i^j]); 80 printf("%d\n",g[(1<<p)-1]); 81 return 0; 82 } View Code

T6:[JLOI2015]戰(zhàn)爭調(diào)度
這道題還是挺不錯的，jloi考了好多要讓你算空間的題- -

記f[i][j][k]為第i個節(jié)點祖先狀態(tài)為j有k個兒子選擇戰(zhàn)爭的最小答案，那么我們考慮一下這樣的狀態(tài)數(shù)以及轉(zhuǎn)移復(fù)雜度

第i層的節(jié)點祖先狀態(tài)有2^i兒子數(shù)有2^n-i一共有2^n個狀態(tài)，所以總狀態(tài)數(shù)為4^n

每個節(jié)點的轉(zhuǎn)移是O(k)的，總的時間復(fù)雜度就是n*4^n，可以解決本題

這個主要還是得考你對時間和空間復(fù)雜度的分析= =

CODE：

1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<map> 6 using namespace std; 7 typedef pair<int,int>ii; 8 typedef pair<int,ii> iii; 9 #define maxn 1030 10 int n,m,w[2][maxn][13],ans; 11 map<iii,int> ma; 12 int dfs(int x,int y,int z,int size) { 13 if (ma.find(iii(x,ii(y,z)))!=ma.end()) return ma[iii(x,ii(y,z))]; 14 int s=0; 15 if (x>=(1<<(n-1))) { 16 x-=(1<<(n-1))-1; 17 for (int i=0;i<n-1;i++) s+=((y>>i)&1)==z?w[z][x][i]:0; 18 ma[iii(x+(1<<(n-1))-1,ii(y,z))]=s; 19 return s; 20 } 21 for (int i=0;i<=z;i++) { 22 if (i>(size>>1)||z-i>(size>>1)) continue; 23 s=max(s,max(dfs(x<<1,y<<1,i,size>>1)+dfs((x<<1)^1,y<<1,z-i,size>>1),dfs(x<<1,(y<<1)^1,i,size>>1)+dfs((x<<1)^1,(y<<1)^1,z-i,size>>1))); 24 } 25 ma[iii(x,ii(y,z))]=s; 26 return s; 27 } 28 int main(){ 29 freopen("war.in","r",stdin); 30 freopen("war.out","w",stdout); 31 scanf("%d%d",&n,&m); 32 for (int i=1;i<=1<<(n-1);i++) 33 for (int j=0;j<n-1;j++) scanf("%d",w[1][i]+j); 34 for (int i=1;i<=1<<(n-1);i++) 35 for (int j=0;j<n-1;j++) scanf("%d",w[0][i]+j); 36 for (int i=0;i<=m;i++) ans=max(ans,dfs(1,0,i,1<<(n-1))); 37 printf("%d\n",ans); 38 } View Code

好啦總結(jié)一下這套題吧= =

首先我覺得出得太noi化了沒有省選的感覺，但又沒有noi那么難，有種四不像的感覺

很多題目的想法都很值得學(xué)習(xí)，而且題解的ppt上的總結(jié)寫得非常好

總的來說還是值得一刷的

轉(zhuǎn)載于:https://www.cnblogs.com/New-Godess/p/4469898.html

總結(jié)

以上是生活随笔為你收集整理的JLOI2015 解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。