算法竞赛入门指南第八章
程序员文章站
2024-03-18 23:47:16
...
8.3 递归与分治
棋盘覆盖问题
#include <iostream>
using namespace std;
const int maxNum = 1 << 10;
int chess[maxNum][maxNum]; // 棋盘
int number; // L型牌放置顺序编号
void chessBoard(int row, int column, int x, int y, int siz) {
// 递归出口
if(siz == 1) {
return;
}
// 对半划分成2^(siz - 1) * 2^(siz - 1)的棋盘
int s = siz / 2;
// L型牌编号自增
int t = ++number;
// 中间点，以此判别(x,y)在哪个子棋盘中
int centerRow = row + s;
int centerColumn = column + s;
// 黑色方格在左上子棋盘
if(x < centerRow && y < centerColumn) {
chessBoard(row, column, x, y, s);
} else {
// 不在则填充左上子棋盘的右下角
chess[centerRow - 1][centerColumn - 1] = t;
// 然后覆盖其他格子，注意这时(x,y)要看做已填充位置
chessBoard(row, column, centerRow - 1, centerColumn - 1, s);
}
// 黑色方格在右上子棋盘
if(x < centerRow && y >= centerColumn) {
chessBoard(row, centerColumn, x, y, s);
} else {
// 不在则填充右上子棋盘的左下角
chess[centerRow - 1][centerColumn] = t;
// 然后覆盖其他格子，注意这时(x,y)要看做已填充位置
chessBoard(row, centerColumn, centerRow - 1, centerColumn, s);
}
// 黑色方格在左下子棋盘
if(x >= centerRow && y < centerColumn) {
chessBoard(centerRow, column, x, y, s);
} else {
// 不在则填充左下子棋盘的右上角
chess[centerRow][centerColumn - 1] = t;
// 然后覆盖其他格子，注意这时(x,y)要看做已填充位置
chessBoard(centerRow, column, centerRow, centerColumn - 1, s);
}
// 黑色方格在右下子棋盘
if(x >= centerRow && y >= centerColumn) {
chessBoard(centerRow, centerColumn, x, y, s);
} else {
// 不在则填充右下子棋盘的左上角
chess[centerRow][centerColumn] = t;
// 然后覆盖其他格子，注意这时(x,y)要看做已填充位置
chessBoard(centerRow, centerColumn, centerRow, centerColumn, s);
}
}
int main() {
// 大小，黑色方格位置
int siz, x, y;
while(true) {
cout << "(x,y)从(0,0)开始,输入数据为0 0 0即结束程序。" << endl;
cout << "请输入棋盘大小和黑色方格位置(x,y)：";
cin >> siz >> x >> y;
// 退出条件
if(siz == 0) {
break;
}
chess[x][y] = number = 1; // 涂黑(x,y)，初始化L型牌编号
chessBoard(0, 0, x, y, siz); // 分治法填满棋盘
// 输出该棋盘
for(int i = 0; i < siz; i++) {
for(int j = 0; j < siz; j++) {
cout << chess[i][j] << "\t";
}
cout << endl << endl << endl;
}
}
return 0;
}巨人与鬼
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
//#include<bits/stdc++.h>
using namespace std;
struct node {
int biao, x, y;//序号和坐标
bool id;//标识巨人还是鬼
};
int n;
node p[1000],ji;
node ans[1000];
bool cmp(node &a, node &b) {
return a.y != b.y ? a.y < b.y : a.x < b.x;
}
bool cmp1(node &a, node &b) {
return (atan2((a.y - ji.y),(a.x - ji.x))<atan2((b.y - ji.y),(b.x - ji.x)));
// atan2 的优点在于 如果 x2-x1等于0 依然可以计算，但是atan函数就会导致程序出错
}
void go(int l,int r) {
if (l > r)
return;
sort(p + l, p + r + 1, cmp);//获取最左下的点作为基点
ji = p[l];
sort(p + l + 1, p + r + 1, cmp1);//根据其他点与基点连线和水平线的角度进行排序
int c1 = 0, c2 = 0;
int k = r;
while (!(ji.id != p[k].id&&c1 == c2)) {
if (p[k].id == ji.id)c1++;//c1是相同标识的数量
else c2++;//c2是与基点不同标识的数量
k--;
}
//ans[p[k].biao] = ji.biao;//只有当c1与c2的数量相等且基点与当前点标识不同时才能配对
//ans[ji.biao] = p[k].biao;
ans[p[k].biao]=ji;
ans[ji.biao]=p[k];
go(l + 1, k - 1);//左半部分
go(k + 1, r);//右半部份
}
int main(void) {
while (cin >> n) {
for (int i = 1; i <= n; i++) {
cin >> p[i].x >> p[i].y >> p[i].id;
p[i].biao = i;
}
go(1, n);
for (int i = 1; i <= n; i++)
cout << i<<":"<<ans[i].biao<<" "<<"("<<ans[i].x<<","<<ans[i].y<<")"<<endl;
}
system("pause");
}例题8-1 煎饼 UVa120
#include<bits/stdc++.h>
using namespace std;
int n,s[35];
bool cmp(int a,int b){
return a>b;
}
void fan(int k,int n,stack<int> &pan){
int num=n-k+1,j=1;
int zancun[35];
memset(zancun,0,sizeof(zancun));
while(num--){
zancun[j++]=pan.top();pan.pop();
}
for(int i=1;i<j;i++){
s[k+i-1]=zancun[i];
pan.push(zancun[i]);
}
}
void solve(int k,stack<int>& pan,int siz){ //k其实是k-1
int r[30];
if(k==siz)
return;
else if(k!=n){
int i=1;
cout<<k<<" ";
fan(k,n,pan);
}
if(siz!=n){
cout<<siz<<" ";
fan(siz,n,pan);
}
}
int main(){
int t[35];
stack<int> pan;
cin>>n;
memset(s,0,sizeof(s));
memset(t,0,sizeof(t));
while(!pan.empty())
pan.pop();
for(int i=n;i>=1;i--){
cin>>s[i];
t[i]=s[i];
}
for(int i=0;i<=n;i++){
pan.push(s[i]);
}
sort(t+1,t+n+1,cmp);
int siz=1;
while(siz<=n){
for(int i=1;i<=n;i++){
if(s[i]==t[siz]){
solve(i,pan,siz);
}
}
siz++;
}
cout<<"0"<<endl;
return 0;
}例题8-2 联合国大楼 UVa1605
好像没啥好写的。。。
例题8-3 和为0的4个值 UVa1152
#include<bits/stdc++.h>
using namespace std;
#define maxn 4010
int main(){
int n,A[maxn],B[maxn],C[maxn],D[maxn];
int ab[maxn*maxn];//,cd[maxn*maxn];
int sum=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&A[i]);
//cin>>A[i];
for(int i=0;i<n;i++)
//cin>>B[i];
scanf("%d",&B[i]);
for(int i=0;i<n;i++)
//cin>>C[i];
scanf("%d",&C[i]);
for(int i=0;i<n;i++)
//cin>>D[i];
scanf("%d",&D[i]);
int k;
k=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
ab[k++]=A[i]+B[j];
}
}
sort(ab,ab+k);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
//cd[k++]=C[i]+D[j];
sum+=upper_bound(ab,ab+k,-C[i]-D[j])-lower_bound(ab,ab+k,-C[i]-D[j]);
}
}
cout << sum << endl; ;
return 0;
}例题8-4
下面程序的输出长这样
样例输出的排序应该是区间几个从小到大趋势排的，巴特自己写的这个是从大到小趋势排的
虽然看着有点难受，但是就这么着吧
#include<bits/stdc++.h>
using namespace std;
struct Node{
int x,y;
int xl,xr,yl,yr;
int id;
};
Node node[5010];
int vis[5010];
bool cmp_x(const Node a,const Node b){
return (a.xl > b.xl || (a.xl == b.xl&&a.xr < b.xr));
}
bool cmp_y(const Node a,const Node b){
return (a.yl>b.yl||(a.yl==b.yl&&a.yr<b.yr));
}
bool cmp_id(const Node a,const Node b){
return (a.id<b.id);
}
bool solve(int n){
//排序
memset(vis,0,sizeof(vis));
sort(node,node+n,cmp_x);
for(int i=0;i<n;i++){
int j;
for(j=node[i].xr;j>=node[i].xl;j--){
if(vis[j]==0){
node[i].x=j;
vis[j]=1;
break;
}
}
if(j==node[i].xl-1)
return false;
}
memset(vis,0,sizeof(vis));
sort(node,node+n,cmp_y);
for(int i=0;i<n;i++){
int j;
for(j=node[i].yr;j>=node[i].yl;j--){
if(vis[j]==0){
node[i].y=j;
vis[j]=1;
break;
}
}
if(j==node[i].yl-1)
return false;
}
sort(node,node+n,cmp_id);
return true;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>node[i].xl>>node[i].yl>>node[i].xr>>node[i].yr;
node[i].id=i;
}
if(solve(n)){
for(int i=0;i<n;i++){
cout<<i+1<<":";
cout<<"("<<node[i].x<<","<<node[i].y<<")"<<endl;
}
}
else{
cout<<"IMPOSSIBLE"<<endl;
}
//shuchu
return 0;
} 例题8-5 Gergovia的酒交易
#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
int main(){
long long n,a[maxn];
while(cin>>n&&n){
long long ans=0,an;
for(long long i=0;i<n;i++)
cin>>a[i];
an=a[0];
cout<<an<<endl;
for(long long i=1;i<n;i++){
ans+=abs(an);
an+=a[i];
cout<<an<<" "<<ans<<endl;
}
cout<<ans<<endl;
//cout<<abs(-1000);
}
return 0;
} 例题8-10 抄书 UVa714
#include<bits/stdc++.h>
using namespace std;
long long s[505];
long long solve(long long l,long long r,int m,int k){
if(r<=l+1){
return r;
}
int x=l+(r-l)/2;
int sum=0,kk=1;
for(int i=0;i<m;i++){
sum+=s[i];
if(sum>x){
sum=s[i];
kk++;
}
}
if(kk<=k)
return solve(l,x,m,k);
else if(kk>k)
return solve(x,r,m,k);
}
int main(){
int m,k;
int t;
long long max;
cin>>t;
while(t--){
cin>>m>>k;
int x=0;
for(int i=0;i<m;i++){
cin>>s[i];
x+=s[i];
}
max=solve(0,x,m,k);
long long sum=0;
for(int i=0;i<m;i++){
sum+=s[i];
if(sum>max){
cout<<"/ "<<s[i]<<" ";
sum=s[i];
}
else{
cout<<s[i]<<" ";
}
}
cout<<endl;
}
return 0;
} 例题8-11 全部相加 UVa10954
贪心、优先队列
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
priority_queue<int,vector<int>,greater<int> > S;
while(cin>>n&&n){
while(!S.empty())
S.pop();
int m,ans=0;
for(int i=0;i<n;i++){
cin>>m;
S.push(m);
}
while(S.size()!=1){
int a=S.top();S.pop();
int b=S.top();S.pop();
ans+=a+b;
S.push(a+b);
}
cout<<ans<<endl;
}
return 0;
} 哈夫曼树
例题8-12 奇怪的气球膨胀 UVa12627
#include<bits/stdc++.h>
using namespace std;
int solve_below(int k,int row){
//气球数组k小时后长度为：n=1<<k,
//设g(x,k)为从下往上数第x行的气球总数。a-b行可以表示为g(n-a,k)-g(n-b,k);
//如果n-a<(1<<(k-1)):g(n-a,k)=g(n-a,k-1);
//如果n-a>(1<<(k-1)):g(n-a,k)=2*g(n-a-(1<<(k-1)),k-1)+k-1小时后的红气球总数(3^k);
int n=1<<k;
int m=n/2;
if(row==0)
return 0;
if(row==1&&m==0)
return 1;
if(row==n)
return pow(3,k);
if(row==m)
return pow(3,k-1);
else if(row<m)
return solve_below(k-1,row);
else if(row>m)
return 2*solve_below(k-1,row-m)+pow(3,k-1);
}
int main(){
int T,t=0;
cin>>T;
while(T--){
int k,a,b,n;
cin>>k>>a>>b;
n=1<<k;
a=n-a+1;b=n-b+1;
//cout<<a<<" "<<b<<endl;
cout<<"Case "<<++t<<": "<<solve_below(k,a)-solve_below(k,b-1)<<endl;//jieguo
}
return 0;
} 例题8-13 环形跑道 UVa11093
#include<bits/stdc++.h>
using namespace std;
int main(){
int T,t=0;
cin>>T;
while(T--){
int n,p[100000],q[100000];
int prvd,need;
cin>>n;
memset(p,0,sizeof(p));
memset(q,0,sizeof(q));
for(int i=0;i<n;i++)
cin>>p[i];
for(int i=n;i<2*n;i++)
p[i]=p[i%n];
for(int i=0;i<n;i++)
cin>>q[i];
for(int i=n;i<2*n;i++)
q[i]=q[i%n];
/*for(int i=0;i<n*2;i++){
cout<<p[i]<<" ";
}
cout<<endl;
for(int i=0;i<n*2;i++){
cout<<q[i]<<" ";
}
cout<<endl;*/
int i=0,j;
cout<<"Case "<<++t<<": ";
while(i<n){
int flag=1;
prvd=need=0;
for(j=i;j<n+i;j++){
prvd=prvd+p[j];
need=need+q[j];
//cout<<i<<" "<<j<<" ";
//cout<<prvd<<" "<<need<<endl;
if(prvd<need){
flag=0;
break;
}
}
if(flag==1&&i<=n){
cout<<prvd<<" "<<need<<endl;
cout<<"Possible from station "<<i+1<<endl;
break;
}
if(flag==0){
i=j+1;
}
}
if(i>n)
cout<<"Not possible"<<endl;
}
return 0;
} 例题8-14 与非门电路 UVa1607
例题8-15 Shuffle的播放记录 UVa12174