2019-07-24 17:51 已编辑浙江中医药大学软件测试

关注

第一章

例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(二分查找）

题目地址：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1636

把问题转化为“是否可以让每个人得到一块面积为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;
}

结果：