T1 彩虹
題目
【題目描述】
Mr.Raju和他的一個大家庭外出度假，他們想要乘著彩虹欣賞周圍的景色，但是這樣最會有一些問題，
在他們家族中，如果一個人想要騎上彩虹，那么他喜歡的所有人和喜歡他的所有人都必須一同騎上彩虹，如果一個人沒有喜歡的人，也沒有人喜歡他，那么他也可以乘上彩虹，
你被請來解決這個難題，我們會提供給你家族所有成員的體重，以及每個人喜歡的人的串列，同樣給出的還有彩虹能承受的總重量，你需要計算出在以上條件下彩虹所能承載的最多人數，
為了方便描述，所有的家庭成員都被標號，從1到n，
【輸入格式】
有多組資料，每組資料之間有一空行，
對于每一組資料，第一行為整數n(1≤n≤1000)和c(0≤c≤1000),n表示家庭成員的總人數，c表示彩虹的承載量，
第二行為n個數為1到n個家庭成員的體重（體重是1000以內的正整數），
接下來n行，每行第一個數k[i]表示第i個人有多少喜歡的人，接下來k[i]個整數為他喜歡的人的編號，
當n=0，c=0是表示資料結束，保證資料組數不超過3，
【輸出格式】
對于每一組資料，輸出可以同時騎彩虹的最大人數，（輸出的每個答案之間不要空行），
【輸入樣例】
5 200 50 50 50 50 50 1 2 1 3 0 1 5 1 4 3 200 100 100 100 1 2 1 3 1 1 0 0
【輸出樣例】
3 0
【資料規模】
對于20%的資料：n≤8；
對于100%的資料：n,c≤1000，
決議
先用并查集將每個人與其喜歡的人合并起來，計算他們的總重量與總人數，
再跑一遍01背包即可，
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } const int N=1010; int n,C,a[N],b[N],c[N],fa[N],f[N],maxn; int get(int x) { if(fa[x]==x) return x; return fa[x]=get(fa[x]); } int main() { //freopen("rainbow.in","r",stdin); //freopen("rainbow.out","w",stdout); while(1) { n=read(),C=read(),maxn=0; if(n==0&&C==0) break; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) a[i]=read(),b[i]=0,c[i]=0,fa[i]=i; for(int i=1;i<=n;i++) { int k=read(); for(int j=1;j<=k;j++) { int x=read(); fa[get(i)]=get(x); } } for(int i=1;i<=n;i++) { int temp=get(i); b[temp]+=a[i],c[temp]++; } for(int i=1;i<=n;i++) if(b[i]!=0) for(int j=C;j>=b[i];j--) f[j]=max(f[j],f[j-b[i]]+c[i]); for(int i=0;i<=C;i++) maxn=max(maxn,f[i]); cout<<maxn<<endl; } return 0; }View Code
T2 紅十字
題目
【題目描述】
通往藏寶庫的通道打開了，走下一段長長的樓梯，鉆過一條矮矮的地道，你和小可可終于來到了藏寶庫的門前，隨之而來的就是最后一個挑戰，只要能打開寶庫的門，里面的寶藏就是你們的了，
寶庫的門依然是通過機關打開，這個門很奇怪，是一個正方形，被劃分成許多大小一致的正方形的小方格，這些方格不是紅色就是白色，猛看上去這些方格組成了許多紅十字狀的標志，根據藏寶圖記載，只要找到門上最大的紅十字，按下它中心的方格，寶庫的門就能打開了，
紅十字標志也是一個正方形，邊長為(2k+1)*(2k+1)，其中k為非負整數，它的四條邊與門的邊平行，而且恰由門上的(2k+1)*(2k+1)個小方格組成，這里，紅十字標志是以白色為底色，紅色為十字的顏色，假設用1表示紅色，用0表示白色，對應到計算機處理的資料中，就是除了正中列與正中行全為1外，其余方格均為0，
以下是幾種不同大小的標志：
1*1:
1
3*3
010
111
010
5*5
00100
00100
11111
00100
00100
小可可被這個機關難到了，現在只有靠你了，請你幫助他在這個門上找到一個最大的紅十字標志，輸出它的邊長即可，
【輸入格式】
本題輸入量巨大，推薦使用以下輸入方法：
scanf("%d\n", &n);
for (i = 1; i<= n; i++) scanf("%s", s[i] + 1);
for (i = 1; i<= n; i++)
for (j = 1; j <= n; j++)
a[i][j] = s[i][j] - '0';
其中n是寶庫的門的邊長，s是字符陣列，a[i][j]是第i行第j列的數值，
【輸出格式】
對于每個詢問輸出一行表示答案，
【輸入樣例】
5 00011 01011 11100 01001 00010
【輸出樣例】
3
【資料規模】
對于30%的資料，n≤100，
對于50%的資料，n≤500，
對于100%的資料，n≤2000，
決議
用sum紀錄子矩陣的值，
對于以(x,y)為中心且長度為k的矩陣，如果是紅十字，那么以(x,y)為中心且長度為k-2(k>=3)的矩陣必然也是紅十字，
所以可以列舉紅十字的中心，求出以(x,y)為中心的最大紅十字的邊長，具體可以用二分實作，
Code
#include<bits/stdc++.h> using namespace std; const int N=2005; int n,a[N][N],sum[N][N],ans; char s[N][N]; int dfs(int lx,int ly,int rx,int ry) { return sum[rx][ry]+sum[lx-1][ly-1]-sum[lx-1][ry]-sum[rx][ly-1]; } int main() { scanf("%d\n",&n); for(int i=1;i<=n;i++) scanf("%s",s[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=s[i][j]-'0',sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]) { int l=1,r=min(min(i,j),min(n-i+1,n-j+1)),cnt=1; while(l<=r) { int mid=(l+r)>>1; if(dfs(i-mid+1,j,i+mid-1,j)==mid*2-1&&dfs(i,j-mid+1,i,j+mid-1)==mid*2-1&&dfs(i-mid+1,j-mid+1,i+mid-1,j+mid-1)==mid*4-3) l=mid+1,cnt=mid; else r=mid-1; } ans=max(ans,cnt*2-1); } printf("%d",ans); return 0; }View Code
T3 柱狀圖
題目
【題目描述】
在統計學中，柱狀圖是用來描述事件發生頻率的一種圖形語言，它是一種鋸齒形的多邊形，可以看做是一些長方形排列而成的，這些長方形的底邊同為一個單位長度，但它們有不同的高度，對于給定的長方形，某些排列會使組成的多邊形達到周長最長，你的任務是找出最長的周長以及構成最長周長的可能排列總數，
在圖（a）中，組成多邊形的長方形高度分別為{1，2，3，4}，它的周長為16個單位長度，在圖（b）中，組成多邊形的長方形高度分別為{3，1，2，4}，它的周長為20個單位長度，
【輸入格式】
輸入檔案包含多組資料，
每組資料第一行為一個整數n (2≤n≤15)，描述有一共有多少個長方形，第二行為n個整數，表示n個長方形的高，
當n=0 時，表示輸入資料結束，保證資料組數不超過16，
【輸出格式】
對于每組資料，輸出一個整數表示答案，
【輸入樣例】
4 1 2 3 4 3 2 6 5 0
【輸出樣例】
20 8 24 2
【資料規模】
決議
不難發現，這題其實是全排列，
Code
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; inline int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } int n,a[100],ans=0,tot,f[100]; long long sum; int main() { n=read(),f[0]=1; for(int i=1;i<=10;i++) f[i]=f[i-1]*i; while(n) { tot=n*2,ans=0; for(int i=1;i<=n;i++) a[i]=read(),tot+=a[i]*2; sort(a+1,a+1+n); if(n%2==1) { for(int i=1;i<=(n-1)/2;i++) ans+=a[i]*4; sum=f[n/2+1]*f[n/2]; } else { for(int i=1;i<=n/2-1;i++) ans+=a[i]*4; ans+=a[n/2]*2,sum=f[n/2-1]*f[n/2]*n; } cout<<tot-ans<<" "<<sum<<endl; n=read(); } return 0; }View Code
T4 最長公共子序列
題目
【題目描述】
給定兩個長度為5n的序列A,B，保證1~n這n個數在A,B中分別出現5次，求A,B最長公共子序列，
【輸入格式】
第一行一個正整數n，
接下來兩行，每行5n個正整數，表示序列A,B，
【輸出格式】
輸出一個整數，最長公共子序列的長度，
【輸入樣例】
2 1 1 2 2 1 1 2 1 2 2 1 2 2 2 1 1 2 2 1 1
【輸出樣例】
7
【資料規模】
對于30%的資料，n≤10，
對于60%的資料，n≤1000，
對于100%的資料，n≤20000，
決議
一下來自于出題人的題解，
注意1~n這n個數分別在A與B中出現5次，
列舉i，并維護f[j]表示A[1...i]和B[1...j]的最長公共子序列，且以B[j]為結尾，
對于每個x，用二維陣列存下x在B中的所有位置，再列舉A[i]在B中的所有位置k，
此時，所有f[j]都是A[1...i-1]和B[1...j]的最長公共子序列，
令g[k]=max(f[1]~f[k-1])+1，即g[k]為A[1...i]和B[1...k]的最長公共子序列，
若B[j]!=A[i]，則g[j]=f[j]，即f[j]不改動，
所以只需做單點修改，并求前綴最大值，具體可以用樹狀陣列維護f[j]的前綴最大值，
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <vector> #include <cmath> using namespace std; inline int read() { int num=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num; } const int N=2e4+5; int n,a[N*5],b[N*5],c[N*5],d[9]; vector<int> g[N*5]; void change(int x,int y) { for(int i=x;i<=n*5;i+=i&-i) c[i]=max(c[i],y); } int ask(int x) { int ans=0; for(int i=x;i;i-=i&-i) ans=max(ans,c[i]); return ans; } int main() { n=read(); for(int i=1;i<=n*5;i++) a[i]=read(); for(int i=1;i<=n*5;i++) b[i]=read(),g[b[i]].push_back(i); for(int i=1;i<=n*5;i++) { for(int j=0;j<=4;j++) { int x=g[a[i]][j]; d[j]=ask(x-1); } for(int j=0;j<=4;j++) { int x=g[a[i]][j]; change(x,d[j]+1); } } cout<<ask(n*5); return 0; }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/98141.html
標籤：C++
上一篇：【題解】洛谷 P1083 借教室