头像

在线白给


访客:9982

离线:3天前



在线白给
2个月前

思路

1.最优解一定是每个灯最多按一次。

2.从最终效果看,按灯的顺序是无所谓的

接下来我们只要思考怎么不重不漏地枚举所有情况就好

因为按灯的顺序无所谓,所以我们尝试直接枚举第一行被按的情况。

第一行形式都被确定了之后,为了让第一行全部的灯都亮,第二行的怎么按都已经是定数了.........以此类推,第五行的按法会被第四行决定。

由第一行的情况,一直推导出第五行的按法。

但是这种”成全上一行“的做法,无法保证第五行的灯全亮。

所以最后要验证第五行。如果第五行也全亮,就说明这个按法是可行的。

最后根据步数输出结果即可。

AC code

#include<iostream>
#include <cstring>
using namespace std;
int light[10][10],n;
int dx[] = {0,-1,0,1,0},dy[]={0,0,1,0,-1};

//debug用
void print()
{
    cout<<endl;
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++)
            cout<<light[i][j]<<" ";

            cout<<endl;
    }
    cout<<endl;
}

//传入行列
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)
        {
            light[a][b]=1-light[a][b];
        }
    }

}

int work()
{

    int tmp[10][10],res=99999;
    memcpy(tmp,light,sizeof light);
    //枚举第一行都按法
    for(int i = 0 ; i <(1<<5) ; i++)
    {
        int count = 0;

        //按下第一行
        for(int k = 0 ; k < 5 ; k ++)
            if(i>>k&1)
            {   
                count++;
                turn(0,k);
            }


        //确保前四行成立
        for(int j = 0 ; j < 4; j++)
        {
            for(int k = 0 ; k <5; k++)
            {
                if(light[j][k]==0) 
                {   
                    count++;
                    turn(j+1,k);
                }
            }
        }


        //检查
        for(int j=0;j<5;j++)
        for(int k=0;k<5;k++)
        {
            //失败
            if(light[j][k]==0)count = 99999;
        }
        res = min(res,count);

        memcpy(light,tmp,sizeof tmp);

    }

    if(res>6) return -1;
    else return res;

}

int main()
{
    cin>>n;
    while(n--)
    {
    //贼坑 输入是一串数字 不是一个个01数字
    for(int i=0;i<5;i++)
    {   
        string s;
        cin>>s;
        for(int j=0;j<5;j++)
            light[i][j] = s[j]-'0';

    }
   // print();
    cout<<work()<<endl;

    }

    return 0;
}



在线白给
3个月前

背背背
反正我觉得这就是bugfree的lower_bound()和upper_bound()的模板

我也创造不出更好的

背吧

C++ 代码

#include<iostream>
using namespace std;
int a[100010];
int n,k;
//返回 x>=value 的最小值
int lower_bound(int key)
{
    int l = 0,r = n-1;

    while(l<r)
    {
        int mid = (l + r + 1)>>1;
        if(a[mid]<=key) l = mid;
        else r = mid - 1;
    }
    if(a[l]!=key) return -1;
    return l;
}
//返回 x<=value 的最大值
int upper_bound(int key)
{
    int l = 0,r = n-1 ;
    while(l<r)
    {
        int mid = (l + r) >> 1;
        if(a[mid] >= key) r = mid;
        else l = mid + 1;
    }
    if(a[l]!=key) return -1;
    return l;
}


int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    while(k--)
    {
        int x;
        cin>>x;

        cout<<upper_bound(x)<<" "<<lower_bound(x)<<endl;
    }
}



在线白给
3个月前

算法/复杂度

前导知识,我的解法涉及一个贪心模板 ,请先看透这个题 :糖果传递

核心问题分析:

  1. 首先提醒一下,在一行中,各列摊位之间交换位置,是不改变行的摊位数量的。列同理。
  2. 我们模拟一下交换的过程:

​ 假设七夕祭有12个摊位,图中有红圈的是题目主角喜欢的摊位。

​ 经过两轮交换后各列的摊位的红圈的数量都一样了,但各行的红圈数量没有发生过变化。

image.png

这个题和 糖果传递 那个题有什么关联呢?

别急,我先把这个图改一改(把线擦去了)。

image.png

​ 你们看,这些红圈像不像糖果,哈哈哈哈哈哈哈哈,相邻列之间交换摊位,就像是相邻两个小朋友正交换糖果嘛。

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
typedef long long ll;
ll res1,res2;
int row[N],col[N],tmp[N];

int main()
{
    int n,m,c;
    cin>>n>>m>>c;

    //开始分别记录行列
    for(int i=0,x,y;i<c;i++)
    {
        cin>>x>>y;
        row[x]++;
        col[y]++;
    }


    //计算行的最小交换次数
    if(c%n==0)
    {
        //求平均值
        int rowi = c/n;
        int x1;
        //从1开始,x,y都是大于1的
        for(int i = 2 ; i <= n ; i++)
            tmp[i] = tmp[i-1] + rowi -row[i];
        //排序
        sort(tmp+1,tmp+n+1);
        if(n%2==0) x1 = (tmp[n/2] + tmp[n/2+1])/2;
        else x1 = tmp[n/2];
        //求距离和
        for(int i = 1 ; i <= n  ; i++)
          res1 += abs(x1 - tmp[i]);
    }

    //计算列的最小交换次数
    if(c%m==0)
    {
        //求平均值
        int coli = c/m;
        int  x1=0;
        //从1开始,x,y都是大于1的
        for(int i = 1 ; i <= m ; i++)
            tmp[i] = tmp[i-1] + coli -col[i];
        //排序
        sort(tmp+1,tmp+m+1);
        if(m%2==0) x1 = (tmp[m/2] + tmp[m/2+1])/2;
        else x1 = tmp[m/2];
        //求距离和
        for(int i = 1 ; i <= m  ; i++)
          res2 += abs(x1 - tmp[i]);

    }

    if(res1&&res2) cout<<"both "<<res1+res2;
    else if(res1) cout<<"row "<<res1;
    else if(res2) cout<<"column "<<res2;
    else cout<<"impossible";

    return 0;
}



在线白给
3个月前

算法/复杂度

据说是贪心的经典题目,背背模板吧,hhhhh

思路:

  1. 题目默认每次只能给左边的人或者右边的人。同样, 最优解一定是没有来回的。所以,全局来看,两个小朋友间的给予关系,可以用一条单向线表示。

image.png

  1. 为了让每个人的糖果分的一样多,那么x1, x2 ,x3.....的取值就是这样子的

image.png

  1. 然后根据数学原理 X1 取 A B C D E 的中位数,可令距离和最小。

(不懂的百度货仓选址问题)

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[1000010],p[1000010],x1,n;
ll ai =0,res = 0;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        //cin>>a[i] 4806 ms
        scanf("%d",&a[i]);//2320 ms
        ai+=a[i];
    }
    //求平均值
    ai/=n;
    //求那几个推导出来的理论点
    p[1] = 0;
    for(int i = 1 ; i <= n; i++)
        p[i] = p[i-1] + ai - a[i];

    //取中位数
    sort(p+1,p+n+1);
    if(n%2==0) x1 = (p[n/2] + p[n/2+1])/2;
    else x1 = p[n/2];

    //求距离和
    for(int i = 1 ; i <= n  ; i++)
        res += abs(x1 - p[i]);

    cout<<res<<endl;
    return 0;

}



在线白给
3个月前

写代码时内存超限,简直离谱

C++ 代码

#include<iostream>
using namespace std;
int tmp[100010],a[100010],n;
//左闭右开
//尼玛内存超限可能是递归爆了?
void merge_sort(int l,int r)
{
    //注意看这里啊!!!!!!!!!!
    //写成l>=r就爆内存了
    if(l>=r-1) return ;
    int mid = (l+r)>>1;
    merge_sort(l,mid);
    merge_sort(mid,r);

    //合并,默认上面已经排序好左边和右边
    int i = l , j = mid ,p = 0 ;
    while(i<mid&&j<r)
        if(a[i]<a[j]) 
            tmp[p++]=a[i++];
        else 
            tmp[p++]=a[j++];

    while(i<mid)
        tmp[p++]=a[i++];
    while(j<r)
        tmp[p++]=a[j++];

    for(int i=l,k=0;i<r;i++)
        a[i]=tmp[k++];
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    merge_sort(0,n);
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
}



在线白给
3个月前

C++ 代码

#include<iostream>
using namespace std;
int dx[] = { 0 , 1 , 0 ,-1};
int dy[] = { 1 , 0 , -1 ,0};
int k=0;
int n,m;
int map[101][101];
int main()
{
    cin>>n>>m;

    int x=0,y=-1;
    for(int i = 1 ; i <= m*n ; i++)
    {
        //转向
        if(map[x+dx[k]][y+dy[k]]!=0||x+dx[k]>=n||y+dy[k]>=m||x+dx[k]<0||y+dy[k]<0) 
            k=(k+1)%4;

        x+=dx[k],y+=dy[k];
        map[x][y] = i;

    }

    for(int i = 0 ; i<n;i++)
    {
        for(int j=0;j<m;j++)
            cout<<map[i][j]<<" ";
        cout<<endl;
    }
}


活动打卡代码 AcWing 793. 高精度乘法

在线白给
4个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 792. 高精度减法

在线白给
4个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 791. 高精度加法

在线白给
4个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 790. 数的三次方根

在线白给
4个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~