題目1 : 九宮
時間限制:10000ms
單點時限:1000ms
記憶體限制:256MB
描寫叙述
小Hi近期在教鄰居家的小朋友國小奧數。而近期正好講述到了三階幻方這個部分，三階幻方指的是将1~9不反複的填入一個3*3的矩陣其中，使得每一行、每一列和每一條對角線的和都是同樣的。
三階幻方又被稱作九宮格，在國小奧數裡有一句很有名的口訣：“二四為肩，六八為足。左三右七。戴九履一。五居當中”。通過這種一句口訣就行很完美的構造出一個九宮格來。
有意思的是，全部的三階幻方，都可以通過這樣一個九宮格進行若幹鏡像和旋轉操作之後得到。如今小Hi準備将一個三階幻方（不一定是上圖中的那個）中的一些數組抹掉，交給鄰居家的小朋友來進行還原，而且希望她可以推斷出到底是不是僅僅有一組解。
而你呢，也被小Hi傳遞了相同的任務，可是不同的是。你須要寫一個程式~
輸入
輸入僅包括單組測試資料。
每組測試資料為一個3*3的矩陣。當中為0的部分表示被小Hi抹去的部分。
對于100%的資料。滿足給出的矩陣至少能還原出一組可行的三階幻方。
輸出
假設僅能還原出一組可行的三階幻方，則将其輸出，否則輸出“Too Many”（不包括引號）。
例子輸入
0 7 2
0 5 0
0 3 0
例子輸出
6 7 2
1 5 9
8 3 4
比較簡單的DFS。
AC代碼：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=10;
int graph[MAXN],vis[MAXN],ans[MAXN];
int flag=0;
bool isok()
{
for(int i=1;i<=7;i+=3)
{
if((graph[i]+graph[i+1]+graph[i+2])!=15) return false;
}
for(int i=1;i<=3;i++)
{
if((graph[i]+graph[i+3]+graph[i+6])!=15) return false;
}
if((graph[1]+graph[5]+graph[9])!=15||(graph[3]+graph[5]+graph[7])!=15) return false;
return true;
}
void dfs(int pos)
{
if(pos==10&&isok())
{
flag++;
if(flag==1)
{
memcpy(ans,graph,sizeof(graph));
return;
}
}
if(graph[pos]) dfs(pos+1);
else
{
for(int i=1;i<=9;i++)
{
if(vis[i]) continue;
vis[i]=1;
graph[pos]=i;
dfs(pos+1);
vis[i]=0;
graph[pos]=0;
}
}
}
int main()
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=9;i++)
{
scanf("%d",&graph[i]);
vis[graph[i]]=1;
}
dfs(1);
if(flag==1)
{
for(int i=1;i<=9;i++)
{
printf("%d%c",ans[i],(i%3==0)?'\n':' ');
}
}
else printf("Too Many\n");
}
題目2 : 優化延遲
時間限制:10000ms
單點時限:1000ms
記憶體限制:256MB
描寫叙述
小Ho編寫了一個處理資料包的程式。程式的輸入是一個包括N個資料包的序列。每一個資料包依據其重要程度不同。具有不同的"延遲懲處值"。序列中的第i個資料包的"延遲懲處值"是Pi。
假設N個資料包依照<Pi1, Pi2, ... PiN>的順序被處理，那麼總延遲懲處SP=1*Pi1+2*Pi2+3*Pi3+...+N*PiN（當中i1, i2, ... iN是1, 2, 3, ... N的一個排列)。
小Ho的程式會依次處理每個資料包，這時N個資料包的總延遲懲處值SP為1*P1+2*P2+3*P3+...+i*Pi+...+N*PN。
小Hi希望能夠減少總延遲懲處值。他的做法是在小Ho的程式中添加一個大小為K的緩沖區。
N個資料包在被處理前會依次進入緩沖區。當緩沖區滿的時候會将目前緩沖區内"延遲懲處值"最大的資料包移出緩沖區并進行處理。直到沒有新的資料包進入緩沖區時，緩沖區内剩餘的資料包會依照"延遲懲處值"從大到小的順序被依次移出并進行處理。
比如，當資料包的"延遲懲處值"依次是<5, 3, 1, 2, 4>。緩沖區大小K=2時，資料包被處理的順序是：<5, 3, 2, 4, 1>。這時SP=1*5+2*3+3*2+4*4+5*1=38。
如今給定輸入的資料包序列。以及一個總延遲懲處門檻值Q。小Hi想知道假設要SP<=Q。緩沖區的大小最小是多少？
輸入
Line 1: N Q
Line 2: P1 P2 ... PN
對于50%的資料： 1 <= N <= 1000。
對于100%的資料： 1 <= N <= 100000, 0 <= Pi <= 1000, 1 <= Q <= 1013。
輸出
輸出最小的正整數K值能滿足SP<=Q。
假設沒有符合條件的K，輸出-1。
例子輸入
5 38
5 3 1 2 4
例子輸出
2
用優先隊列模拟緩沖區的功能，二分搜尋得到最小的緩沖區。
AC代碼：
#include<cstdio>
#include<queue>
using namespace std;
const int MAXN=100005;
int P[MAXN],N;
long long Q;
bool isOk(int value)
{
long long cnt=0;
int index=1;
priority_queue<int> queue;
for(int i=1;i<=N;i++)
{
if(queue.size()==value)
{
int temp=queue.top();
queue.pop();
cnt+=temp*index++;
}
queue.push(P[i]);
}
while(queue.size())
{
int temp=queue.top();
queue.pop();
cnt+=temp*index++;
}
if(cnt<=Q) return true;
else return false;
}
int main()
{
while(scanf("%d%lld",&N,&Q)>0)
{
for(int i=1;i<=N;i++) scanf("%d",&P[i]);
int minn=1;int maxn=100000;
while(minn<=maxn)
{
int mid=(minn+maxn)/2;
if(isOk(mid)) maxn=mid-1;
else minn=mid+1;
}
if(minn>100000) minn=-1;
printf("%d\n",minn);
}
return 0;
}
題目3 : 建造基地
時間限制:10000ms
單點時限:1000ms
記憶體限制:256MB
描寫叙述
在遙遠的未來。小Hi成為了地球聯邦外空間聯合開發工作組的一員。前往一顆新發現的星球開發當地的重金屬資源。
為了可以在當地生存下來，小Hi首先要建立一個基地。
建立基地的材料可以直接使用當地的石材和富裕的重金屬資源。
基地建設分為N級，每一級都須要達成K的建設值後才可以完畢建設。目前級别的建設值溢出後不會影響到下一級的建設。
小Hi能夠産出的重金屬資源依照精煉程度分為M級，依據開採的數量和精煉的工藝，能夠将擷取精煉程度為第i級的重金屬資源的成本量化為Ai。
在建設第1級基地時，一塊精煉度為i的重金屬能夠提供Bi的建設值，此後基地的級别每提高一級。建設值将除以T并下取整(整除)。
現給定N、M、K、T、A[]和B[]。小Hi須要你幫助他計算他完畢基地建設的最小成本。
輸入
輸入包括多組測試資料。
輸入的第一行為一個整數Q。表示測試資料的組數。
每組測試資料的第一行為4個整數N、M、K和T。意義如前文所述。
接下來的一行為M個整數，分别表示A1~AM。
接下來的一行為M個整數，分别表示B1~BM。
對于100%的資料，滿足1<=N<=10，1<=M<=100。1<=K,T<=104。
對于100%的資料，滿足Ai和Bi均為32位整型範圍内的正整數。
對于100%的資料，滿足1<=Q<=10。
輸出
對于每組測試資料，假設小Hi終于可以完畢基地建設，則輸出小Hi完畢基地建設所須要的最小成本。否則輸出“No Answer”。
例子輸入
2
2 2 2 2
1 3
1 2
2 2 2 2
1 2
1 1
例子輸出
8
No Answer
題意有點繞，想清楚是全然背包問題以後還是比較簡單的。
AC代碼：
#include<cstdio>
#include<algorithm>
#define INF 1<<30
using namespace std;
typedef long long ll;
int main()
{
int Q,N,M,K,T;
int a[110],b[110];
ll dp[10010];
//dp[i]表示價值為i時的最小成本
while(~scanf("%d",&Q))
{
while(Q--)
{
ll res=0;
scanf("%d%d%d%d",&N,&M,&K,&T);
for(int i=1;i<=M;i++) scanf("%d",&a[i]);
for(int i=1;i<=M;i++) scanf("%d",&b[i]);
for(int u=1;u<=N;u++)
{
for(int i=1;i<10010;i++) dp[i]=INF;
dp[0]=0;
for(int i=1;i<=M;i++)
{
for(int j=0;j<=K;j++)
{
if(j+b[i]>K) dp[K]=min(dp[K],dp[j]+a[i]);
else dp[j+b[i]]=min(dp[j+b[i]],dp[j]+a[i]);
}
}
res+=dp[K];
//将每級累加
for(int v=1;v<=M;v++) b[v]/=T;
}
if(res>=INF) puts("No Answer");
else printf("%lld\n",res);
}
}
return 0;
}
題目4 : 艦隊遊戲
時間限制:10000ms
單點時限:1000ms
記憶體限制:256MB
描寫叙述
小Hi近期在玩一款組建艦隊出海進行戰争的遊戲，在這個遊戲中，小Hi須要依據須要組建一僅僅艦隊。一支艦隊裡最多同一時候存在N艘艦船。每艘艦船最多同一時候裝備M個裝備。
在一次關卡中，小Hi希望可以組建一僅僅僅由航母構成的艦隊，這意味着全部艦船的裝備都是某種類型的飛機，小Hi将要使用的飛機有兩種類型：對空飛機和對艦飛機，顧名思義，對空飛機用于和敵對艦船搭載的飛機進行對抗，而對艦飛機則直接用于攻擊敵對艦船本身。
每艘航母的M個裝備欄位是不一樣的，我們能夠用“搭載量”來對其進行量化描寫叙述，有些裝備欄位的搭載量較高。有些裝備欄位的搭載量較低，對于第i艘艦船，我們用Ai,j表示其第j個裝備欄位的搭載量。
小Hi的軍備庫裡有T架飛機。我們Bi表示第i架飛機的對空攻擊力，并用Ci表示第i架飛機的對艦攻擊力，當中對空飛機的對艦攻擊力為0，對艦飛機的對空攻擊力為0。
為艦船裝備飛機，會提高艦隊的“制空值”和“傷害值”。
艦隊的制空值為全部飛機的對空攻擊力與其相應的裝備欄位的搭載量的乘積之和，即：
制空值=
當中pi,j表示放置在第i艘艦船的第j個裝備欄位的飛機編号。同理，艦隊的傷害值為全部飛機的對艦攻擊力與其相應的裝備欄位的搭載量的乘積之和，即
傷害值=
為了可以順利的通過關卡，小Hi須要使得艦隊的制空值不低于一個給定的值S，而且希望在這個條件下艦隊的傷害值越高越好，這樣可以盡量降低艦隊的損耗。
同一時候，因為一艘艦船至少要裝備一架對艦飛機才可以在炮擊戰中發動攻擊。是以小Hi也好奇是否存在在滿足制空值限制且傷害值最高的情況下，同一時候滿足每一艘艦船至少裝備一架對艦飛機。
而這個問題。就有待你來進行計算了~
輸入
輸入第一行為一個正整數Q。表示測試資料的組數。
在每組測試資料的第一行，為4個正整數N、M、T和S。意義如之前所述。
第2行~第n+1行，每行m個正整數。相應矩陣A。
第n+2行，為T個正整數B1 .. BT。
第n+3行，為T個正整數C1 .. CT。
對于30%的資料。滿足N<=2，M<=2，T<=20，Q<=100。
對于剩下70%的資料，滿足N<=4。M<=4，T<=1000。Q<=3。
對于100%的資料，滿足1<=Ai,j, Bi, Ci <= 1000。0<= S <= 108。
輸出
對于每組測試資料，假設存在滿足制空值限制的方案的話，則首先在第一行輸出在滿足制空值限制下可以達到的最大攻擊力D，在第二行中。假設在滿足制空值限制且傷害值最高的情況下。可以同一時候滿足每一艘艦船至少裝備一架對艦飛機，則輸出Yes，否則輸出No。
假設不存在滿足制空值限制的方案的話。則輸出一行Not Exist。
例子輸入
3
1 2 1 38
4 5
5
1 2 8 7
1 4
0 3 2 0 0 2 0 0
5 0 0 3 3 0 3 4
2 1 4 29
5
3
0 4 3 0
1 0 0 3
例子輸出
Not Exist
5
Yes
No
對值直接從小到大排序，然後就是枚舉狀态貪心計算。
AC代碼：
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const MAX=1e3+5;
int N,M,T,S;
int sz_a;
int sz_b;
//對空飛機的數量
int sz_c;
//對艦飛機的數量
int b[MAX],B[MAX],c[MAX],C[MAX];
struct A
{
int num,pos;
}a[5][5],temp[20];
bool cmp(A x,A y)
{
return x.num>y.num;
}
//計算對空值
int cal_air(int k)
{
memset(temp,0,sizeof(temp));
sz_a=0;
//搭載了多少架對空飛機
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
if(k&(1<<(i*M+j)))
{
temp[sz_a++].num=a[i][j].num;
}
}
}
sort(temp,temp+sz_a,cmp);
int res=0;
for(int i=0,j=0;i<sz_a&&j<sz_b;i++,j++) res+=temp[i].num*B[j];
return res;
}
//計算對艦值
int cal_ship(int k)
{
memset(temp,0,sizeof(temp));
sz_a=0;
//搭載了多少架對艦飛機
for(int i=0;i<N&&sz_a<=sz_c;i++)
{
for(int j=0;j<M&&sz_a<=sz_c;j++)
{
if(!(k&(1<<(i*M+j))))
//假設已經搭載了對空飛機就不能搭載對艦飛機
{
temp[sz_a].num=a[i][j].num;
temp[sz_a++].pos=a[i][j].pos;
//後面還要用到艦艇的資訊
}
}
}
sort(temp,temp+sz_a,cmp);
int res=0;
for(int i=0,j=0;i<sz_a&&j<sz_c;i++,j++) res+=temp[i].num*C[j];
return res;
}
//計算能不能滿足每一艘艦船至少裝備一架對艦飛機
bool judge_ship()
{
//枚舉每一艘艦艇
for(int i=0;i<N;i++)
{
bool flag=false;
for(int j=0;j<M&&!flag;j++)
{
for(int k=0;k<min(sz_a,sz_c)&&!flag;k++)
{
if(((1<<(i*M+j))&temp[k].pos)) flag=true;
}
}
if(!flag) return false;
}
return true;
}
int main()
{
int Q;
scanf("%d",&Q);
while(Q--)
{
sz_b=0;
sz_c=0;
scanf("%d%d%d%d",&N,&M,&T,&S);
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
scanf("%d",&a[i][j].num);
a[i][j].pos=(1<<(i*M+j));
}
}
for(int i=0;i<T;i++)
{
scanf("%d",&b[i]);
if(b[i]) B[sz_b++]=b[i];
}
for(int i=0;i<T;i++)
{
scanf("%d",&c[i]);
if(c[i]) C[sz_c++]=c[i];
}
sort(B,B+sz_b,greater<int>());
sort(C,C+sz_c,greater<int>());
int ans=-1,tot=1<<(N*M);
// N艘艦船,每艘艦船M個裝備,每一個裝備有裝載和未裝載兩種情況,一共枚舉2*n*m種可能
bool has=false;
for(int i=0;i<tot;i++)
{
if(cal_air(i)>=S)
{
int temp=cal_ship(i);
if(temp>ans||(temp==ans&&!has))
{
ans=temp;
has=judge_ship();
}
}
}
if(ans==-1) printf("Not Exist\n");
else printf("%d\n%s\n",ans,has?"Yes":"No");
}
}