装水

题目详情

题目描述
一天小理买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着小理发现瓶子实在太多了，于是他决定保留不超过K个瓶子，每次他选择两个当前含水量相同的瓶子合并。（即把一个瓶子的水全部倒进另一个里然后把空瓶丢弃）

（注：不能丢弃有水的瓶子）

显然在某些情况下小理无法达到目标，比如N = 3, K = 1。此时小理会重新购买一些新的瓶子（新瓶子容量无限，开始时有1升水）以达到目标。

现在小理想知道最少需要多少新瓶子才能达到目标呢？

输入格式
一行两个正整数N和K，含义见题。

输出格式
输出文件包含一个非负整数，表示最少需要购买的瓶子数量。

1.4 测试样例
1.4.1 样例输入1(water.in)
3 1
1.4.2 样例输出1(water.out)
1
1.4.3 样例输入2(water.in)
13 2
2
CSP-J 模拟题 执理OI
1.4.4 样例输出2(water.out)
3
1.4.5 样例输入3(water.in)
1000000 5
1.4.6 样例输出3(water.out)
15808
1.5 任务约束
对于50%的数据，保证1 ⩽ n ⩽ 10^7
对于100%的数据，保证1 ⩽ n ⩽ 10^9, 0 ⩽ k ⩽ 1000

AC代码

这道题只需要将瓶子数转化为2进制看看里面包含多少个1即可,例如13的二进制是1101,16的二进制是10000,只有一个1,小于输入的2,所以最终答案就是16-13,所以这道题的难点就在于如何不超时传化二进制

代码1(90分)

可以用到__builtin_popcount(n)来做到快速计算二进制的1的个数
代码如下

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main(){
    //freopen("water.in","r",stdin);
    //freopen("water.out","w",stdout);
    int n,k;
    cin >> n >> k;
    int ans = 0;
    while(__builtin_popcount(n) > k){
        ans++;
        n++;
    }
    cout << ans << endl;
    return 0;
}

如果不会的话手写也是可以的

代码2(90分)

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std ;

int count(int x){//这里的作用是一样的
    int s=0;
    while(x){
        if(x%2) s++;
        x/=2;
    }
    return s;
}

int main()
{
    int n,k;
    cin >> n >> k;
    int ans = 0;
    while(count(n) > k){
        ans++;
        n++;
    }
    cout << ans << endl;
    return 0;
}

怎么做到ac呢?

代码3(AC)

代码如下

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std ;

int count(int x){
    int s=0;
    while(x){
        if(x%2) s++;
        x/=2;
    }
    return s;
}

int lowbit(int x){
    return x&-x;
}

int main()
{
    int n,k;
    cin >> n >> k;
    int ans = 0;
    while(count(n) > k){
        ans+=lowbit(n);//直接寻找二进制最后一个1的位置,这样做不会超时
        n+=lowbit(n);
    }
    cout << ans << endl;
    return 0;
}

和数(sum)

题目详情

2.1 问题描述
小理对数字之美的追求不局限于质数了，他发现了一种非常靓丽的数字，
并命名为「和数」。「和数」就是能表示为一些互不相同的整数的阶乘之和的
数。如9 = 1! + 2! + 3!。
现在给定一个非负整数n，要求判断n是否为「和数」。
如果是，则输出“YES”，否则输出“NO”(引号不输出)。
2.2 输入格式
每行一个非负整数n，最后一行是一个负数，作为输入的结束。
2.3 输出格式
对于每个非负整数n，在输出文件中分别输出“YES”或“NO”，各占1行。
2.4 测试样例
2.4.1 输入文件(sum.in)
9
5
-1
2.4.2 输出文件(sum.out)
YES
NO
2.5 任务约束
对于20%的数据，保证n ⩽ 10000
对于60%的数据，保证n ⩽ 100000
对于所有的数据，保证n ⩽ 1000000

AC代码

可以发现所有的数字都是由1-10中的数字组成的,所以只需要看他们是否可以被1-10中小于等于他们的数字减完等于0,如果等于就是yes,否则是no

#include<cmath>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int a[1006];
int n,wc=0;
int ans[100006];
int main(){
    //freopen("sum.in","r",stdin);
    //freopen("sum.out","w",stdout);
    a[0]=1;
    for(int i=1;i<=11;i++)
        a[i]=a[i-1]*i;
    while(cin>>n){        
        if(n<0){//注意题目要求,输入负数结束程序
            break;
        }
        if(n==0){//特判下
            cout<<"NO"<<endl;
            continue;
        }
        for(int i=10;i>=0;i--){
            if(n>=a[i]) n-=a[i];
        }
        wc++;
        if(n==0){
            ans[wc]=1;
            continue;        
        }else{
            ans[wc]=0;
            continue;
        }
    }
    for(int i=1;i<=wc;i++){//我这里单独记录了答案输出,边做边输出也是可以的,不用在意(一开始不停的wa,以为是输出格式的问题......)
        if(i==wc){
            if(ans[i]){
                cout<<"YES";
            }else{
                cout<<"NO";
            }    
        }else
            if(ans[i]){
                cout<<"YES"<<endl;
            }else{
                cout<<"NO"<<endl;
            }
    }
} 

解方程(equationagain)

题目详情

3.1 问题描述
小理学习了计算机编程之后，他发现运用编程可以轻松结局令他头疼的一
元一次方程问题，于是他准备编一个程序用于解方程。
给出一个字符串，表达一个方程。
数据保证方程有且只有一个解，而且方程只会有一个未知数X，且X的最
高指数也只会有1。方程中所有的系数都是整数，且系数是1就会被省略。只会
出现加、减符号，不会出现乘、除。
3.2 输入格式
输入一个字符串表示方程。
3.3 输出格式
输出X的解，保留三位小数。
3.4 测试样例
3.4.1 输入文件(equationagain.in)
6x+7x+8x+1=6x+7x+9x
3.4.2 输出文件(equationagain.out)
1.000
3.5 任务约束
对于10%的数据，输入满足ax = b 的形式
对于另外的30%的数据，含未知数的参数仅一项
对于另外的10%的数据，未知数仅出现在等号左边且符号仅为加号
对于另外的10%的数据，未知数仅出现在等号左边
对于100%的数据，保证字符串的长度不会超过255

AC代码

#include<cmath>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char a[10006]; 
int main(){
    //freopen("equationagain.in","r",stdin);
    //freopen("equationagain.out","w",stdout);
    cin>>a;
    int c=strlen(a);
    int wc=0;
    for(int i=0;i<=c;i++){
        if(a[i]=='('){
            wc=1;
            c-=1;
            for(int j=i;j<=c;j++){
                a[j]=a[j+1];
            }
        }
        if(a[i]==')'){
            wc=0;
            c-=1;
            for(int j=i;j<=c;j++){
                a[j]=a[j+1];
            }
        }
        if(wc){
            if(a[i]=='+'){
                a[i]='-';
            }else if(a[i]=='-'){
                a[i]='+';
            }

        }
    }
    a[c]='-';
    int fg=0;
    double wcc=0;
    double x=0,y=0;
    int p=1;
    for(int i=0;i<=c;i++){
        if(a[i]=='x'&&(a[i-1]!='9'&&a[i-1]!='8'&&a[i-1]!='7'&&a[i-1]!='6'&&a[i-1]!='5'&&a[i-1]!='4'&&a[i-1]!='3'&&a[i-1]!='2'&&a[i-1]!='1'&&a[i-1]!='0'))//这里用isdigit(n)更方便,这个是判断字符是不是数字的
        {
            wcc=1;
        }
        if (isdigit(a[i]))
            wcc=wcc*10+(a[i]-'0');
        if((a[i-1]<='9'&&a[i-1]>='0')&&(a[i]=='-'||a[i]=='+'||a[i]=='=')){
            wcc=wcc*p;
            if(!fg){
                y=y-wcc;    
            }else{
                y=y+wcc;
            }
            wcc=0;
        }else if(a[i]=='x'){
            wcc=wcc*p;
            if(!fg){
                x+=wcc;
            }else{
                x-=wcc;
            }
            wcc=0;    
        }
        if(a[i]=='+'||a[i]=='='||a[i]=='-'){
            if(a[i]=='-'){
                p=-1;
            }else {
                p=1;
            }}    
        if(a[i]=='='){
            fg=1;
        }
    }
    double ww;
    ww=y/x;
    printf("%.3lf\n",ww);
} 

溜乌龟(tortoise)

题目详情

4.1 问题描述
乌龟们在被划分成N行M列的草地上游走。
设S为乌龟在T秒内从(R1,C1)走到(R2,C2)所能选择的路径总数，每一秒
内，乌龟会水平或垂直地移动1单位距离（乌龟总是在移动，不会在某秒内停在
它上一秒所在的点）。草地上的某些地方有树，自然，乌龟不能走到树所在的
位置，也不会走出草地。
现在你拿到了一张整块草地的地形图，其中.表示平坦的草地，∗表示挡路
的树。你的任务是计算出，乌龟在T秒内从(R1,C1)移动到(R2,C2)可能经过的
路径条数。
4.2 输入格式
第1行: 3个用空格隔开的整数：N，M，T
第2..N+1行: 第i+1行为M个连续的字符，描述了草地第i行各点的情况，保
证字符是.和*中的一个
第N+2行: 4个用空格隔开的整数：R1，C1，R2，以及C2。
4.3 输出格式
输出S，表示乌龟在T秒内从(R1,C1)移动到(R2,C2)可能经过的路径条数。
4.4 测试样例
以文件形式下发
4.5 任务约束
对于10%的数据，保证地图中没有「挡路的树」
对于另外60%的数据，2 ⩽ N, M ⩽ 20
对于100%的数据，2 ⩽ N ⩽ 100; 2 ⩽ M ≤ 100; 0 < T ≤ 15

AC代码

记忆化搜索完事

#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int tx[5]={0,1,-1,0,0};
int ty[5]={0,0,0,1,-1};
int t,x,y,x1,y11;
int mapp[1000][1000];
int n,m;
struct node{
    int x,y,st;
};
int dp[101][101][20];
void bfs(int xx,int yy){
    queue<node> q;
    q.push((node){xx,yy,0});
    dp[xx][yy][0]=1;
    while(!q.empty()){
        node c;
        c=q.front();
        for(int i=1;i<=4;i++){
            int dx=c.x+tx[i];
            int dy=c.y+ty[i];
            int dt=c.st+1;
            if(dp[dx][dy][dt])
                dp[dx][dy][dt]+=dp[c.x][c.y][c.st];
            if(dx>0&&dy>0&&dx<=n&&dy<=n&&mapp[dx][dy]==0){
                dp[dx][dy][dt]+=dp[c.x][c.y][c.st];
                q.push((node){dx,dy,dt});
            } 
        }
    }
}
int main(){
    //freopen("tortoise.in","r",stdin);
    //freopen("tortoise.out","w",stdout);
    cin>>n>>m>>t;
    char w;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>w;
            if(w=='*'){
                mapp[i][j]=1;
            }else{
                mapp[i][j]=0;
            }
        }
    }
    cin>>x>>y>>x1>>y11;
    bfs(x,y);
    cout<<dp[x1][y11][t];
}

@^ _ ^@