头像

And


访客:4709

离线:1个月前



And
2个月前

ADDE0966D3DC7DEB7B26A9C66839A4AC.png

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];
int ans;

int gca(int a,int b)//求最大公因数
{
    return b?gca(b,a%b):a;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i<n;i++) scanf("%d",&a[i]);
    sort(a,a+n);//从小到大排序

    int d = 0;//和所有整数的约数都是整数的
    for(int i = 1;i<n;i++) d = gca(d,a[i]-a[0]);//由每项之间的差相互比较,求的所有项数的最大公约数
    if(!d) printf("%d\n",n);如果d = 0,等差数列每个数都相等
    else{
        printf("%d\n",(a[n-1]-a[0])/d +1);//求最小的项数
    }
    return 0;
}



And
3个月前

AcWing 1015. 摘花生
Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。

地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走,不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

1.gif

输入格式
第一行是一个整数T,代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有C个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式
对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。

数据范围
1≤T≤100,
1≤R,C≤100,
0≤M≤1000
输入样例:
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例:
8
16
QQ图片20200301180034.png

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;
const int N = 1010;
int q[N][N];
int f[N][N];
int a,b;
int main(){
    int n;
    cin>>n;//代表组数
    while(n--){

        cin>>a>>b;//输出每组数据的行列数
        for(int i = 1;i<=a;i++){
            for(int j =1;j<=b;j++){
                cin>>q[i][j];//输入每组的数据

            }
        }
        //memset(f,0,sizeof f);
        for(int i = 1;i<=a;i++){
            for(int j =1;j<=b;j++){
                f[i][j] = max(f[i-1][j]+q[i][j],f[i][j-1]+q[i][j]);//状态计算,分为两种状态,一种是从上向下的,一种是从左到右的
            }
        }
       cout<<f[a][b]<<endl;  //输出每一种数据得出的果实最多的路线
    }

    return 0;
}



And
3个月前

AcWing 1205. 买不到的数目
//超简单,供自己课后回顾 主要普及公式 蜀裴定理:求最大买不到的数量 ab-a-b = m(a,b是给的两个组合数)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    cout<<(n-1)*(m-1)-1<<endl;
    return 0;
}



And
3个月前

AcWing 730. 机器人跳跃问题
QQ图片20200301140144.png

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;
const int N = 1e5+10;
int q[N];
int n;
bool check(int e){
    for(int i = 1;i<=n;i++){
        e = 2*e-q[i];
        if(e>=1e5) return true;//当能量值大于最高值,能量区间呈递增趋势
        if(e<0) return false;//未满足题干条件
    }
    return true;
}

int main(){

    cin>>n;
    for(int i = 1;i<=n;i++) cin>>q[i];//输出每层楼的高度
    //二分
    int l = 0,r = 1e5;
    while(l<r){
        int mid = (l+r)/2;
        if(check(mid))r = mid;
        else l = mid+1;
    }
    //最后L和r的值是相同的
    cout<<r<<endl;
    return 0;
}



And
3个月前

AcWing 1208. 翻硬币
仅供自己课后学习

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;
const int N = 100;
int n;
char start[N],aim[N];


void turn(int i)//实现换硬币正反的操作
{

    if(start[i] =='*') start[i] ='o';
    else start[i] = '*';
}

int main(){

    cin>>start>>aim;//两条字符串
    n = strlen(start);

    int res = 0;
    for(int i = 0;i<n-1;i++)
        if(start[i]!=aim[i]){
            turn(i),turn(i+1);
            res++;
        }

    cout<<res<<endl;
    return 0;
}



And
3个月前

AcWing 93. 递归实现组合型枚举
QQ图片20200229164221.png
QQ图片20200229164215.png
供自己课后复习而已

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
const int N = 30;
int way[N];//方案数
int n,m;

void dfs(int u,int start){
    if(u+n-start<m) return;//不符合条件(一个方案不满三个数)的直接过滤
    if(u == m+1)//边界
    {
        for(int i = 1;i<=m;i++) printf("%d ",way[i]);//输出不同方案数的内容
        puts(" ");
        return;
    }
    for(int i = start;i<=n;i++)//填坑,从起始位置开始
    {
        way[u] = i;//填坑
        dfs(u+1,i+1);//递归遍历
        //恢复现场
        way[u] = 0;
    }
}


int main(){
    cin>>n>>m;
    dfs(1,1);
    return 0;
}


活动打卡代码 AcWing 95. 费解的开关

And
3个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 6;

char g[N][N], backup[N][N];
int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {0, 1, 0, -1, 0};

void turn(int x, int y)
{
    for (int i = 0; i < 5; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;   // 在边界外,直接忽略即可
        g[a][b] ^= 1;
    }
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        for (int i = 0; i < 5; i ++ ) cin >> g[i];

        int res = 10;
        for (int op = 0; op < 32; op ++ )
        {
            memcpy(backup, g, sizeof g);
            int step = 0;
            for (int i = 0; i < 5; i ++ )
                if (op >> i & 1)
                {
                    step ++ ;
                    turn(0, i);
                }

            for (int i = 0; i < 4; i ++ )
                for (int j = 0; j < 5; j ++ )
                    if (g[i][j] == '0')
                    {
                        step ++ ;
                        turn(i + 1, j);
                    }

            bool dark = false;
            for (int i = 0; i < 5; i ++ )
                if (g[4][i] == '0')
                {
                    dark = true;
                    break;
                }

            if (!dark) res = min(res, step);
            memcpy(g, backup, sizeof g);
        }

        if (res > 6) res = -1;

        cout << res << endl;
    }

    return 0;
    }



And
3个月前

递归实现排列型枚举
供自己课后回顾

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

const int N = 10;
int n;
int st[N];
bool used[N];//false表示没有用过,true表示该坑用过

void dfs(int u){
    if(u>n){
        for(int i = 1;i<=n;i++)printf("%d ",st[i]);//输出不同的方案数
        puts("");
        return ;
    }
        //遍历每一个分支
    for(int i = 1;i<=n;i++){
        if(!used[i]){
            st[u] = i;//填上坑
            used[i] = true;//表示该坑已经被用过
            dfs(u+1);

             //恢复现场
            st[u] = 0;
            used[i] = false;
        }
    }
}

int main(){
    cin>>n;
    dfs(1);

    return 0;
}



And
3个月前

仅仅自己思路整理

#include<iostream>
#include<cstdio>

using namespace std;
const int N = 16;
int n;
int st[N] ;//状态数组 1.选了 2.不选 0.还未选

void  dfs(int u)//确定方案内部
{
    if(u>n){
        for(int i =1;i<=n;i++){
            if(st[i]==1)
                printf("%d ", i);
        }
        printf("\n");
        return;
    }

    st[u] = 2;//不选的状态
    dfs(u+1);
    st[u] = 0;//恢复到没选的状态

    st[u] = 1;//选的状态
    dfs(u+1);
    st[u] = 0;//下同
}

int main(){
    cin>>n;

    dfs(1);
    return 0;
}


活动打卡代码 AcWing 616. 两点间的距离

And
3个月前
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int main(){
    double x,y,x1,y1;
    cin>>x>>y>>x1>>y1;
    double ans=sqrt(((x1-x)*(x1-x))+((y1-y)*(y1-y)));
    printf("%.4lf",ans );
    return 0;
}