第一章
例2：突击战
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
struct Job{
int j,b;
bool operator <(const Job &x) const{
return j> x.j;//看不懂
}
};
int main(){
int n,b,j,kase=1;
while(scanf("%d",&n)==1&&n){
vector<Job>v;
for(int i=0;i<n;i++){
scanf("%d%d",&b,&j);
v.push_back((Job){j,b});
}
sort(v.begin(),v.end());
int s=0;
int ans=0;
for(int i=0;i<n;i++){
s+=v[i].b;//当前任务的开始执行时间
ans=max(ans,s+v[i].j);//更新任务执行完毕最晚时间
}
printf("Case %d: %d\n",kase++,ans) ;
}
return 0;
}
结果：
图片.png
例3：分金币p4
转化为中位数求解
本例题的重点是代数分析
#include<cstdio>
#include<algorithm>
//#include<vector>
using namespace std;
const int maxn=1000000+10;
long long A[maxn],C[maxn],tot,M;
int main(){
int n;
while(scanf("%d",&n)==1)//数据量大的时候要用scanf
{
tot=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&A[i]);
tot+=A[i];
}
M=tot/n;
C[0]=0;
for(int i=1;i<n;i++)
C[i]=C[i-1]+A[i]-M;//递推 C数组
sort(C,C+n);
long long x1=C[n/2],ans=0;//计算x1（中位数）
for(int i=0;i<n;i++)
ans+=abs(x1-C[i]);//把x1代入，计算转手的总金币数
printf("%lld\n",ans);
}
return 0;
}
结果：
例3
例4: 墓地雕塑p7
#include<cstdio>
#include<algorithm>
#include<cmath>
//#include<vector>
using namespace std;
int main(){
int n,m;
while(scanf("%d%d",&n,&m)==2)//数据量大的时候要用scanf
{
double ans=0.0;
for(int i=0;i<n;i++){
double pos=(double)i/n*(n+m);//计算每个需要移动的雕塑的坐标
ans+=fabs(pos-floor(pos+0.5))/(n+m);//累加移动距离
//floor(pos+0.5)是pos四舍五入的结果
}
printf("%.4f\n",ans*10000);//比例扩大坐标 ，注意周长10000
}
return 0;
}
结果：
例4
例5 蚂蚁:p9
#include<cstdio>
#include<algorithm>
#include<cmath>
//#include<vector>
using namespace std;
const int maxn=10000+5;
struct Ant{
int id;//顺序
int p;//位置
int d;//朝向：-1左，0正转向，1右
bool operator<(const Ant& a)const{
//重载<操作符。可以对两个Anr使用<操作符进行比较
return p<a.p;
}
}before[maxn],after[maxn];
const char dirName[][10]={"L","Turning","R"};
int order[maxn];//输入的第i只蚂蚁是终态中左数第order[i]只蚂蚁
int main(){
int K;
scanf("%d",&K);
for(int kase=1;kase<=K;kase++){
int L,T,n;
printf("Case #%d:\n",kase);
scanf("%d%d%d",&L,&T,&n);
for(int i=0;i<n;i++){
int p,d;
char c;
scanf("%d %c",&p,&c);
d=(c=='L'?-1:1);
before[i]=(Ant){i,p,d};//???
after[i]=(Ant){0,p+T*d,d};//此处id未知
}
//计算order数组
sort(before,before+n);
for(int i=0;i<n;i++)
order[before[i].id]=i;
//计算终态
sort(after,after+n);
for(int i=0;i<n-1;i++)//修改碰撞中蚂蚁方向
if(after[i].p==after[i+1].p)
after[i].d=after[i+1].d=0;
//输出结果
for(int i=0;i<n;i++){
int a=order[i];
if(after[a].p<0||after[a].p>L)
printf("Fell off\n");
else printf("%d %s\n",after[a].p,dirName[after[a].d+1]);
}
printf("\n");
}
return 0;
}
结果：
例5
例6 立方体成像(代码有错)p13
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
//#include<vector>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
const int maxn=10;
int n;
int i,j,k;
char pos[maxn][maxn][maxn];
char view[6][maxn][maxn];
char read_char(){
char ch;
for(;;){
ch=getchar();
if((ch>='A'&&ch<='Z')||ch=='.')
return ch;
}
}
void get(int k,int i,int j,int len,int &x,int &y,int &z)
{
if(k==0){x=len; y=j; z=i;}
if(k==1){x=n-1-j; y=len; z=i;}
if(k==2){x=n-1-len;y=n-1-j; z=i;}
if(k==3){x=j; y=n-1-len;z=i;}
if(k==4){x=n-1-i; y=j; z=len;}
if(k==5){x=i; y=j; z=n-1-len;}
}
int main(){
while(scanf("%d",&n)==1&&n){
REP(i,n) REP(k,6) REP(j,n) view[k][i][j]=read_char();
REP(i,n) REP(j,n) REP(k,n) pos[i][j][k]='#';
REP(k,6) REP(i,n) REP(j,n) if(view[k][i][j]=='.')
REP(p,n){
int x,y,z;
get(k,i,j,p,x,y,z);
pos[x][y][z]='.';
}
for(;;){
bool done=true;
REP(k,6) REP(i,n) REP(j,n) if(view[k][i][j]!='.'){
REP(p,n){
int x,y,z;
get(k,i,j,p,x,y,z);
if(pos[x][y][z]=='.')continue;
if(pos[x][y][z]=='#'){
pos[x][y][z]=view[k][i][j];
break;
}
if(pos[x][y][z]==view[k][i][j])
break;
pos[x][y][z]='.';
done=false;
}
}
if(done)break;
}
int ans=0;
REP(i,n) REP(j,n) REP(k,n);
if(pos[i][j][k]!='.')ans++;
printf("Maximum wieght:%d gram(s)\n",ans);
}
return 0;
}
例7 偶数矩阵：p15
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=20;
const int INF=1000000000;
int n,A[maxn][maxn],B[maxn][maxn];
int check(int s){
memset(B,0,sizeof(B));
for(int c=0;c<n;c++){
if(s&(1<<c))B[0][c]=1;
else if(A[0][c]==1)
return INF;//1不能变为0
}
for(int r=1;r<n;r++)
for(int c=0;c<n;c++){
int sum=0;//元素B[r-1][c]的上左右3个元素之和
if(r>1) sum+=B[r-1][c];
if(c>0) sum+=B[r-1][c-1];
if(c<n-1) sum+=B[r-1][c+1];
B[r][c]=sum%2;
if(A[r][c]==1&&B[r][c]==0)return INF;
}
int cnt=0;
for(int r=0;r<n;r++)
for(int c=0;c<n;c++)
if(A[r][c]!=B[r][c])
cnt++;
return cnt;
}
int main(){
int T;
scanf("%d",&T);
for(int kase=1;kase<=T;kase++){
scanf("%d",&n);
for(int r=0;r<n;r++)
for(int c=0;c<n;c++)
scanf("%d",&A[r][c]);
int ans=INF;
for(int s=0;s<(1<<n);s++)
ans=min(ans,check(s));
if(ans==INF)ans=-1;
printf("Case %d: %d\n",kase,ans);
}
return 0;
}
结果：我也不知道对不对的结果
p15
例8 彩色立方体：(模拟+立体几何）
uva 1352 LA3401 - Colored Cubes(模拟，4级)
参照剑不飞大佬的博客和《算法竞赛入门训练》
方法1：思路：模拟暴力。第一种是最后那个“相同的立方体”的每个面是什么，四个立方体最多24种颜色，故要枚举24^6种“最后的立方体”，枚举量太大。
//算法1:生成常量表
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
//原来的顺序应该是{0,1,2,3,4,5}{前，右，顶，底，左，后}
int left[]={4,0,2,3,5,1};//往右翻90
int up[]={2,1,5,0,4,3};//往下翻90
//按照排列T的顺序旋转姿态B(旋转函数）
void rot(int* T,int* p){
int q[6];
memcpy(p,q,sizeof(q));
for (int i=0;i<6;i++)
p[i]=T[q[i]];
}
void enumerate_permutations(){
int p0[6]={0,1,2,3,4,5};
printf("int dice24[24][6]={\n");
for(int i=0;i<6;i++){
int p[6];
memcpy(p,p0,sizeof(p0));
if(i==0)rot(up,p);
if(i==1){
rot(left,p);
rot(up,p);
}
if(i==3)//思考一下为什么没有2
{
rot(up,p);
rot(up,p);
}
if(i==4)
{
rot(left,p);rot(left,p);
rot(left,p);rot(up,p);
}
if(i==5){
rot(left,p);rot(left,p);rot(up,p);
}
for(int j=0;j<4;j++){
printf("{%d,%d,%d,%d,%d,%d,%d},\n",
p[0],p[1],p[2],p[3],p[4],p[5]);
rot(left,p);
}
}
printf("};\n");
}
int main(){
enumerate_permutations();
return 0;
}
另一种方法是枚举每个立方体的姿态，第一个为参考系，然后六个面，分别选一个出现次数最多的颜色作为标准，和他不同颜色的一律重涂，由于每个立方体的姿态有24种，3个立方体（出去不用旋转的第一个）的姿态组合一共有23的3次方种，比第一种方法好。
//算法2
int dice24[24][6]={//生成的常量表（枚举）
{2,1,5,0,4,3},{2,0,1,4,5,3},{2,4,0,5,1,3},{2,5,4,1,0,3},{4,2,5,0,3,1}
,{5,2,1,4,3,0},{1,2,0,5,3,4},{0,2,4,1,3,5},{0,1,2,3,4,5},{4,0,2,3,5,1}
,{5,4,2,3,1,0},{1,5,2,3,0,4},{5,1,3,2,4,0},{1,0,3,2,5,4},{0,4,3,2,1,5}
,{4,5,3,2,0,1},{1,3,5,0,2,4},{0,3,1,4,2,5},{4,3,0,5,2,1},{5,3,4,1,2,0}
,{3,4,5,0,1,2},{3,5,1,4,0,2},{3,1,0,5,4,2},{3,0,4,1,5,2}};
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=4;
int n,dice[maxn][6],ans;
vector<string>names;
int ID(const char* name){
string s(name);
int n=names.size();
for(int i=0;i<n;i++)
if(names[i]==s)
return i;
names.push_back(s);
return n;
}
int r[maxn],color[maxn][6];//每个立方体的旋转方式和旋转后各个面得颜色
void check(){
for(int i=0;i<n;i++)
for(int j=0;j<6;j++)
color[i][dice24[r[i]][j]]=dice[i][j];
int tot=0; //需要重新涂色的面数
for(int j=0;j<6;j++){//考虑每个面
int cnt[maxn*6];
memset(cnt,0,sizeof(cnt));
int maxface=0;
for(int i=0;i<n;i++)
maxface=max(maxface,++cnt[color[i][j]]);
tot+=n-maxface;
}
ans=min(ans,tot);
}
void dfs(int d){
if(d==n)check();
else for(int i=0;i<24;i++){
r[d]=i;
dfs(d+1);
}
}
int main()
{
while(scanf("%d",&n)==1&&n){
names.clear();
for(int i=0;i<n;i++)
for(int j=0;j<6;j++){
char name[30];
scanf("%s",name);
dice[i][j]=ID(name);
}
ans=n*6;//上届：所有面都不涂色
r[0]=0;
dfs(1);
printf("%d\n",ans);
}
return 0;
}
输入：
图片.png
输出：
图片.png
例9 ：中国麻将
题目大意：给出13张麻将牌，问在取一张牌就可以胡牌的牌，所处所有满足的情况。这里的胡牌不需要考虑太多，只需要满足存在一个对子， 而其他的全是3个顺或者3个相同的就可以了，一些特殊的胡牌不需要考虑。
解题思路：将所有给出的麻将牌转化成数字进行处理，对应的用一个数组统计牌的个数cnt[i]表示标号为i的麻将牌有cnt[i]张。因为存在特殊的牌面，所以可以将特殊牌面的标号分开，这样在dfs的过程中就无需考虑连续的标号是否是顺子的问题。接下来就是枚举所有可能拿到的牌（出现过4次的不能再取），加入后用dfs判断是否可以胡牌，因为只有三种情况，dfs的时候直接写出来就可以了，注意对子只出现一次。
原文：https://blog.csdn.net/keshuai19940722/article/details/10034505
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
using namespace std;
const char* mahjong[]={
"1T","2T","3T","4T","5T","6T","7T","8T","9T"
,"1S","2S","3S","4S","5S","6S","7S","8S","9S"
,"1W","2W","3W","4W","5W","6W","7W","8W","9W"
,"DONG","NAN","XI","BEI","ZHONG","FA","BAI"
};
int convert(char* s){ //只在预处理的时候调用，因此速度无关紧要
for(int i=0;i<34;i++)
if(strcmp(mahjong[i],s)==0)
return i;
return -1;
}
int c[34];
bool search(int dep){ //回溯法递归过程
int i;
for(i=0;i<34;i++)
if(c[i]>=3){ //刻子
if(dep==3)return true;
c[i]-=3;
if(search(dep+1))return true;
c[i]+=3;
}
for(i=0;i<=24;i++)
if(i%9<=6&&c[i]>=1&&c[i+1]>=1&&c[i+2]>=1){ //顺子
if(dep==3)return true;
c[i]--;c[i+1]--;c[i+2]--;
if(search(dep+1))return true;
c[i]++;c[i+1]++;c[i+2]++;
}
return false;
}
bool check(){
int i;
for(i=0;i<34;i++)
if(c[i]>=2){ //将牌
c[i]-=2;
if(search(0))return true;
c[i]+=2;
}
return false;
}
int main(){
int caseno=0,i,j;
bool ok;
char s[100];
int mj[15];
while(scanf("%s",&s)==1){
if(s[0]=='0')break;
printf("Case &d:",++caseno);
mj[0]=convert(s);
for(i=1;i<13;i++){
scanf("%s",&s);
mj[i]=convert(s);
}
ok=true;
for(i=0;i<34;i++){
memset(c,0,sizeof(c));
for(j=0;j<13;j++)
c[mj[j]]++;
if(c[i]>=4)continue; //每种牌最多4张
c[i]++; //假设拥有这张牌
if(check()){ //如果“和”了
ok=true; //说明听这张牌
printf(" %s",mahjong[i]);
}
c[i]--;
}
if(!ok)printf(" Not ready");
printf("\n");
}
return 0;
}
结果：
图片.png
例10 ：正整数数列p25-p26
为了平衡，保留1~n/2,剩下的数同时减去n/2+1，找规律f(n)=f(n/2)+1,边界f(1）=1
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
using namespace std;
int f(int n){
return n==1?1:f(n/2)+1; //f(n)=f(n/2)+1
}
int main(){
int n;
while(scanf("%d",&n)==1){
printf("%d\n",f(n));
}
return 0;
}
结果：
图片.png
例12 组装电脑 p28
例13 派 p30(二分查找）
把问题转化为“是否可以让每个人得到一块面积为x的派”，于是求解的目标变成了“看看这写条件是否矛盾”。
矛盾为：“x太大，满足不了所有F+1个人”---->看看一个半径为r的派能不能切出（πr2/x）个派（其他部分浪费）然后再相加
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
using namespace std;
const double PI=acos(-1.0);
const int maxn=10000+5;
int n,f;
double A[maxn];
bool ok(double area){
int sum=0;
for(int i=0;i<n;i++)
sum+=floor(A[i]/area);//向下取整函数
return sum >=f+1;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&f);
double maxa=-1;
for(int i=0;i<n;i++){
int r;
scanf("%d",&r);
A[i]=PI*r*r;
maxa=max(maxa,A[i]);
}
double L=0,R=maxa;
while(R-L>1e-5){
double M=(L+R)/2;//二分法
if(ok(M))L=M;
else R=M;
}
printf("%.4lf\n",L);
}
return 0;
}
结果：
预期结果
实际结果
例题14 ：填充正方形（贪心）
//模板
bool lexicographicallySmaller(vector<T>a,vector<T>b){
int n=a.size();
int m=b.size();
int i;
for(i=0;i<n&&i<m;i++)
if(a[i]<b[i])return true;
else if(b[i]<a[i]) return false;
return (i==n&&i<m);
}
//有错的代码
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=20;
char grid[maxn][maxn];
int n;
int main(){
int T;
scanf("%d",&T);
for(int kase=1;kase<=T;kase++){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%s",grid[i]);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(grid[i][j]=='.'){//没填过的字母需要填入
for(char ch='A';ch<='Z';ch++){//依照字典序依次尝试
bool ok=true;
if(i>0 &&grid[i-1][j]==ch) ok=false;//和上面的字母冲突
if(i<n-1&&grid[i+1][j]==ch) ok=false;
if(j>0 &&grid[i][j-1]==ch) ok=false;
if(j<n-1&&grid[i][j+1]==ch) ok=false;
if(ok)
grid[i][j]==ch;break;//没有冲突，填进网络，并停止继续尝试
}
}
printf("Case %d:\n",kase);
for(int i=0;i<n;i++)
printf("%s\n",grid[i]);
}
return 0;
}
//AC代码，虽然看起来一模一样，挠头
#include <cstdio>
#include <cstring>
using namespace std;
int n , t;
char a[20][20];
int main()
{
int T=0;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%s",a[i]);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(a[i][j]=='.')
{
for(char ch = 'A'; ch<='Z'; ch++)
{
if(i>0 && a[i-1][j]==ch) continue;
if(i<n-1 && a[i+1][j]==ch) continue;
if(j>0 && a[i][j-1]==ch) continue;
if(j<n-1 && a[i][j+1]==ch) continue;
a[i][j]=ch;
break;
}
}
printf("Case %d:\n",++t);
for(int i=0;i<n;i++) printf("%s\n",a[i]);
}
return 0;
}
结果：
图片.png
例15 ：网络 p34
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
using namespace std;
//只需要覆盖叶子结点，不用覆盖中间结点
const int maxn=10000+10;
vector<int>gr[maxn],nodes[maxn];
int n,s,k,fa[maxn];
bool covered[maxn];
//无根树转化为有根树，计算fa数组，根据深度吧叶子结点插入nodes表里
void dfs(int u,int f,int d)
{
fa[u]=f;
int nc=gr[u].size();
if(nc==1&&d>k)nodes[d].push_back(u);
for(int i=0;i<nc;i++){
int v=gr[u][i];
if(v!=f)dfs(v,u,d+1);
}
}
void dfs2(int u,int f,int d){
covered[u]=true;
int nc=gr[u].size();
for(int i=0;i<nc;i++){
int v=gr[u][i];
if(v!=f&&d<k)dfs2(v,u,d+1);//只覆盖到新服务器距离不超过k的结点
}
}
int solve(){
int ans=0;
memset(covered,0,sizeof(covered));
for(int d=n-1;d>k;d--)
for(int i=0;i<nodes[d].size();i++){
int u=nodes[d][i];
if(covered[u])continue;//不考虑已经覆盖的结点
int v=u;
for(int j=0;j<k;j++)
v=fa[v]; //v是u的k级祖先
dfs2(v,-1,0); //在结点v放服务器
ans++;
}
return ans;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&s,&k);
for(int i=1;i<=n;i++){
gr[i].clear();
nodes[i].clear();
}
for(int i=0;i<n-1;i++){
int a,b;
scanf("%d%d",&a,&b);
gr[a].push_back(b);
gr[b].push_back(a);
}
dfs(s,-1,0);
printf("%d\n",solve());
}
return 0;
}
结果：
结果
