头像

今天你ac了吗


访客:423

离线:3小时前



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

const int N=1e5+10;
int a[N],b[N];
int n,m,x;

int find(int x,int a[])
{
    int l=0,r=sizeof(a);
    while(l<r)
    {
        int mid=l+r>>1;
        if(a[mid]>=x)r=mid;
        else
        l=mid+1;
    }
    return l;
}

int main()
{
    cin>>n>>m>>x;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=0;i<m;i++)
    {
        scanf("%d",&b[i]);
    }
    /*暴力做法

    for(int i=0;i<find(x,a);i++)
    {
        if(a[i]>x)return 0;

        for(int j=0;j<find(x,b);j++)
        {
            if(a[i]+b[j]==x){cout<<i<<" "<<j;return 0;};
            if(a[i]+b[j]>x)break;
        }
    }*/

    //双指针算法找单调性O(M+N);
    for(int i=0,j=m-1;i<n;i++)
    {
        while(j>=0&&a[i]+b[j]>x)j--;
        if(a[i]+b[j]==x){cout<<i<<" "<<j;break;}
    }

}


活动打卡代码 AcWing 802. 区间和

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=3e5+10;
typedef pair<int,int> PII;
int n,m;
int a[N],s[N];//a,s分别存离散化之后的数组和前缀和数组
/*

因为要将a数组中的元素映射到下标1~n,
使用vector all存下标

*/
vector<int>all;
vector<PII>add,query;

int find(int x)
{
    int l=0,r=all.size()-1;
    while(l<r)
    {
        int mid=l+r>>1;
        if(all[mid]>=x)r=mid;
        else 
        l=mid+1;
    }
    return l+1;
}

int main()
{

    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int x,t;cin>>x>>t;
        all.push_back(x);
        add.push_back({x,t});
    }

    for(int i=0;i<m;i++)
    {
        int l,r;cin>>l>>r;
        all.push_back(l);
        all.push_back(r);
        query.push_back({l,r});
    }

    sort(all.begin(),all.end());
    //unique返回的是重复元素的首地址。
    all.erase(unique(all.begin(),all.end()),all.end());

    //遍历add vecotr实现所有的插入操作

    for(auto item:add)
    {
        int x=find(item.first);
        a[x]+=item.second;
    }

    for(int i=1;i<=all.size();i++)
        s[i]=s[i-1]+a[i];
    /*

    for(auto item:query)
    {
        int l=find(item.first),r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }
    for (int i=0;i<query.size();i++)
    {
        vecotor<PII> item = query[i];
        int l = find(item.first);
        int r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }*/
    for(vector<PII>::iterator it=query.begin();it!=query.end();it++)
    {
        int l=find(it->first),r=find(it->second);
        cout<<s[r]-s[l-1]<<endl;
    }



    return 0;
}



#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e4+10;
int a[N];

//选择排序
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    for(int i=1;i<=n;i++)
    {
        int t=i;
        for(int j=i+1;j<=n;j++)
        {
            if(a[j]<a[t])
            {
                t=j;
            }
        }
        swap(a[i],a[t]);
        cout<<a[i]<<" ";
    }
}
//冒泡排序
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    for(int i=1;i<=n;i++)
    {
        int t=i;
        for(int j=i+1;j<=n;j++)
        {
            if(a[j]<a[t])
            {
                swap(a[j],a[t]);
            }
        }
        cout<<a[i]<<" ";
    }
}
//插入排序
/*
第一个元素是有序的,
从遍历第二~第n个元素,如果a[i]<a[j],把a[i]插到a[j]的前边去,直到遍历完整理序列。
*/
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    for(int i=2;i<=n;i++)
    {
        int j=i;
        while(j>=1&&a[j]<=a[j-1])
            swap(a[--j],a[j]);
    }

    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
}



活动打卡代码 AcWing 113. 特殊排序

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
int cnt=0;
//插排+二分
class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int>res;
        res.push_back(1);
        //给定一个已经排好序的序列,用logn的复杂度快速找到相应的位置
        for(int i=2;i<=N;i++)//寻找第i个插入的数
        {
            int l=0,r=res.size()-1;
            while(l<r)
            {
                int mid=l+r>>1;
                if(compare(i,res[mid]))r=mid;//由题干知,compare 只有大于和小于关系。
                else l=mid+1;
                //cout<<"   "<<mid<<l<<r<<endl;
            }
            //要插入的第i个数插到后边,再一个一个向前交换。
            res.push_back(i);
            //找到第i个要插入的数,调用compare是n*log n的

            //复杂度是n^2的
            //此时mid,l,r应该是相等的
            for(int j=res.size()-2;j>l;j--){swap(res[j],res[j+1]);cnt++;}
            //for(int j=res.size()-1;j>r;j--){swap(res[j-1],res[j]);cnt++;}//会比上一行那个多一次交换,结果不对!
            //如果说第i个数比所有的数都小,则把他换到第一个数上,
            //最左侧视为-无穷,最右侧视为+无穷
            if(compare(i,res[l]))swap(res[r],res[r+1]);
        }
        //cout<<endl<<cnt<<endl;
        return res;
    }
};


活动打卡代码 AcWing 102. 最佳牛围栏

#include<iostream>
#include<cmath>
using namespace std;
const int N=1e6+10;
//问题:为什么这个求前缀和的时候用一个数组算出来是0?
double  a[N];
double sum[N];
int n,m;
double res=0;
bool check(double mid)
{
    double mins=0;
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+a[i]-mid;


    for(int k=m;k<=n;k++)
    {
        mins=min(mins,sum[k-m]);
        //res=max(res,a[k]-mins);
        //if(res>=0)return 1;
        if(sum[k]>=mins)return true;
    }
    return false;
}

int main()
{
    cin>>n>>m;
    double l=0,r=2000;
    for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
    while(r-l>1e-5)
    {
        double mid=(l+r)/2;
        if(check(mid))l=mid;
        else
        r=mid;
    }
    //printf("%d",(int)r*1000);
    printf("%d\n", (int)(r * 1000));

}


活动打卡代码 AcWing 101. 最高的牛

#include<iostream>
using namespace std;
const int N=1e5+10;
//经过自己思考,完全自己写出来的题真是不一样!
int a[N],b[N],n,p,h,m;

int main()
{
    scanf("%d%d%d%d",&n,&p,&h,&m);
    for(int i=1;i<=n;i++)
        a[i]=h;
    b[1]=a[1];
    for(int i=2;i<=n;i++)
        b[i]=a[i]-a[i-1];
    int ol,orr;
    ol=orr=0;
    int l=0,r=0;
    while(m--)
    {
        orr=r,ol=l;
        scanf("%d%d",&l,&r);
        if(orr==r&&ol==l)continue;
        if(l>r)swap(l,r);

        if(abs(l-r)<=1)continue;
        else if(r-l==2)
            {b[l+1]-=1;b[r]+=1;}//对的
        else
        {
            b[l+1]-=1;
            b[r]+=1;
        }

    }
     a[1]=b[1];

        for(int i=2;i<=n;i++)
            a[i]=a[i-1]+b[i];
        //a[p]=h;//保证最高牛的身高每次操作都不变化。
        for(int i=1;i<=n;i++)
            printf("%d\n",a[i]);
}


活动打卡代码 AcWing 100. IncDec序列

#include<iostream>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,a[N],b[N];

/*b[1]~b[n+1]中任意选2个数,进行+1or-1操作.
使b[2]==b[3]==...b[n];

操作情况:
选择差分数组b的下标
1.    i,j    i>=2,j<=n;//根据贪心原则,尽量选1 res=min(sum1,sum2);
2.    1,j         j<=n;                2或者3操作数   t=abs(sum1-sum2);
3.    i,n+1  i>=2     ;                所以,最小操作数就是  res+t  根据数轴有  res+t==max(sum1,sum2);
4.    1,n+1  无效情况                        p,q      |p-q|=max(p,q)-min(p,q);    
*/


int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    b[1]=a[1];
    for(int i=2;i<=n;i++)
        b[i]=a[i]-a[i-1];
    ll sum1,sum2;
    sum1=sum2=0;
    for(int i=2;i<=n;i++)
        if(b[i]>0)sum1+=b[i];
        else if(b[i]<0)sum2+=abs(b[i]);
    ll res=0;
    res=min(sum1,sum2);//尽量执行第一种操作
    ll t=abs(sum1-sum2);

    //cout<<res+t<<endl;//记录最小操作数
    cout<<max(sum1,sum2)<<endl;
    cout<<t+1;//t次2,3操作,产生t+1中b1,所以t+1即为结果


}


活动打卡代码 AcWing 99. 激光炸弹

#include<iostream>
#include<cstring>
using namespace std;
const int N=5010;
int a[N][N];
int n;
int res=0;
int R;
//int s[N][N];  如果开两个5000的N*N数组空间大概是200mb
int main()
{
    cin>>n>>R;
    R=min(5000,R);
    memset(a,0,sizeof a);
    int N=0,M=0;
    while(n--)
    {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        a[x+1][y+1]+=w;//注意是+=
        //N=max(N,x+1),M=max(M,y+1);
    }

    for(int i=1;i<=5002;i++)
        for(int j=1;j<=5002;j++)
        {
            a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];// 1
          //s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];// 2
          //观察到如果用s存储每个格子的权重,并且用来表示前缀和数组的话,在s[i][j]没有更新的情况下
          //1式和2式中s[i][j]和a[i][j]是完全等价的,所以可以只用一个数组,大大节约了内存
        }
    //R<=1e9,而x,y远远比它小,所以可能越界。
    for(int i=R;i<=5002;i++)
        for(int j=R;j<=5002;j++)
        {
            res=max(res,a[i][j]-a[i-R][j]-a[i][j-R]+a[i-R][j-R]);
            //因为矩阵是从1开始的,所以第一项a[i][j]==a[R][R],后边全是0,正确。
        }

    cout<<res;

}


活动打卡代码 AcWing 96. 奇怪的汉诺塔

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=15;
int f[N],d[N];//d[i]表示i个盘子三塔最小步数,f是四塔模式
//人家的思路真的nb
int main()
{
    d[1]=1;
    for(int i=2;i<=12;i++)
        d[i]=1+d[i-1]*2;
    //把i-1个盘子移到b,1个盘子移到c,i-1个盘子从b->c
    memset(f,0x3f,sizeof f);
    f[0]=0;
    f[1]=1;
    for(int i=1;i<=12;i++)
    {
        for(int j=0;j<=i;j++)//移动0~i个盘子
        {
            //把j个盘子通过四柱方式移到非D的柱子,i-j个盘子移到D,j个盘子再移到D
            f[i]=min(f[i],2*f[j]+d[i-j]);
        }
    }

    for(int i=1;i<=12;i++)
        cout<<f[i]<<endl;
    return 0;

}


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

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

char a[5][6];
int n,res=0;
int d[5][2]={-1,0,0,0,0,1,1,0,0,-1};
char b[5][6];



void turn(int x,int y)
{
    for(int i=0;i<5;i++)
    {
        int dx=x+d[i][0],dy=y+d[i][1];
        if(dx>=0&&dx<5&&dy>=0&&dy<5)
        a[dx][dy]='0'+('1'-a[dx][dy]);
    }
}

int dfs()
{
    int ans=1000000;//ans不能设成全局100000否则进行完第一组数据之后ans就变成了第一组数据的值,
//不再是最大的INF,造成错误
    for(int i=0;i<1<<5;i++)//枚举第一行的2^5种操作  如i=0则i对应的二进制数是00000代表原来a中第一行的每个数都不翻转
    {//否则翻转
        res=0;
        memcpy(b,a,sizeof a);

        for(int j=0;j<5;j++)//枚举每一位
        {
            if(i>>j&1)
            {
                res++;
                turn(0,4-j);//和turn(0,j)差不多
            }
        }

        for(int i=0;i<4;i++)//通过已经确定的第一行来推第2~4行
        {
            for(int j=0;j<5;j++)
            {
                if(a[i][j]=='0')
                {
                    res++;
                    turn(i+1,j);
                }
            }
        }
        bool c=true;
        for(int i=0;i<5;i++)
            if(a[4][i]=='0')
            {
                c=false;
                break;
            }
        if(c)  {ans=min(ans,res);}

        memcpy(a,b,sizeof b);
    }

    if(ans>6) return -1;
    return ans;

}

int main()
{
    cin>>n;
    while(n--)
    {
        for(int i=0;i<5;i++)
            cin>>a[i];
        cout<<dfs()<<endl;
    }
    return 0;

}