头像

终不似少年游




离线:21分钟前


最近来访(6)
用户头像
酸奶盖盖
用户头像
1780044096@qq.com
用户头像
大瓜皮
用户头像
pointerHu

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

#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,k,a[7][7],ans1=1e6,b[7][7];//7,7是因为怕在最后一排溢出
int main() {
    int n;
    cin>>n;
    while(n--) {
        getchar();
        for (i=1; i<=5; i++) {
            for (j=1; j<=5; j++) {
                char ch=getchar();
                b[i][j]=ch-'0';
            }
            getchar();
        }
        //每一个位置有点击与不点击两种情况
        //故共有2^5种情况,枚举
        for (i=0; i<(1<<5); i++) {
            for (j=1; j<=5; j++) {
                for (k=1; k<=5; k++)
                    a[j][k]=b[j][k];
            }
            int ans=0;
            for (j=1; j<=5; j++)
                //这里枚举的是a[1][j]应不应该被点击
                if (!(i>>(j-1) & 1)) {
                    ans++;
                    a[1][j-1]^=1;
                    a[1][j+1]^=1;
                    a[1][j]^=1;
                    a[2][j]^=1;
                }
            for (j=1; j<=4; j++) //注意是1~4,而不是2~5,因为我们是去改变i+1行,而不是直接改变第i行
                for (k=1; k<=5; k++)
                    //第j行第k个未亮,那么需要下一行点亮
                    if (!a[j][k]) {
                        ans++;
                        a[j][k]^=1;//上面
                        a[j+2][k]^=1;//下面
                        a[j+1][k]^=1;//本身
                        a[j+1][k+1]^=1;//右面
                        a[j+1][k-1]^=1;//左面
                    }
            //cout<<ans<<endl;
            bool ok=true;
            for (j=1; j<=5; j++)
                for (k=1; k<=5; k++)
                    if (!a[j][k])
                        ok=false;
            if (ok)
                ans1=min(ans1,ans);
        }
        if (ans1>6)
            cout<<-1;
        else
            cout<<ans1;
        ans1=1e7;
        puts("");
    }
    return 0;
}


活动打卡代码 AcWing 90. 64位整数乘法

#include<iostream>
#define ll long long
using namespace std;
//思想:类似快速幂,将a*b转为 加法
//例如:3*7
//7的二进制为111
//3*7=3*1+3*2+3*4 
ll mul(ll a,ll b,ll p){
    ll sum=0;
    while(b){
        if(b&1) sum=(sum+a)%p;
        a=a*2%p;
        b>>=1;
    } 
    return sum;
}
int main(){
    ll a,b,p;
    cin>>a>>b>>p;
    cout<<mul(a,b,p);
    return 0;
}




活动打卡代码 AcWing 1018. 最低通行费

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define INF 0x3f3f3f3f
#define ll long long

using namespace std;
const int N=1e2+5;
int a[N][N],f[N][N];
int T,n,m;
int main() {
        cin>>n;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++){
                cin>>a[i][j];
                f[i][j]=1e8;//方便后面更新最小值
            }

        f[1][1]=a[1][1];
        for(int i=2;i<=n;i++){
            f[1][i]=f[1][i-1]+a[1][i];
            f[i][1]=f[i-1][1]+a[i][1];
        }
        for(int i=2; i<=n; i++) 
            for(int j=2; j<=n; j++){

            //从上走到(i,j)
            f[i][j]=min(f[i][j],f[i-1][j]+a[i][j]);
            //从左走到(i,j)
            f[i][j]=min(f[i][j],f[i][j-1]+a[i][j]);
//          cout<<i<<","<<j<<"="<<a[i][j]<<"  "<<f[i][j]<<endl;
        }
        cout<<f[n][n]<<endl;

    return 0;
}




活动打卡代码 AcWing 1015. 摘花生

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define INF 0x3f3f3f3f
#define ll long long

using namespace std;
const int N=1e2+5;
int a[N][N],f[N][N];
int T,n,m;
int main() {
    cin>>T;
    while(T--) {
        memset(a,0,sizeof a);
        memset(f,0,sizeof f);
        cin>>n>>m;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                cin>>a[i][j];
        f[1][1]=a[1][1];
        for(int i=1; i<=n; i++) 
            for(int j=1; j<=m; j++){
                //(i,j)往下走
            f[i+1][j]=max(f[i+1][j],f[i][j]+a[i+1][j]);
            //(i,j)往右走
            f[i][j+1]=max(f[i][j+1],f[i][j]+a[i][j+1]);
        }
        cout<<f[n][m]<<endl;
    }
    return 0;
}



活动打卡代码 AcWing 198. 反素数

#include<iostream>
#include<cstring>
// #include<cstdio>由于这个题目的读入量很小,所以我们完全可以用cin来读
#include<algorithm>

using namespace std;

int primes[9]={2,3,5,7,11,13,17,19,23};//primes的话一共是有9个对吧

typedef long long LL;//当然这里要加一个long long 啊

int maxd;//比方说我们的约数个数可以记为我们的maxd

int number;//然后数本身的话可以记成number

int n;//然后还有一个n对吧,这是我们读入的这个数

void dfs(int u,int last,int p,int s)//好,那我们dfs一下,上一个的次数,上一个数,以及我们的约数个数
{
    //好,然后如果我们当前的约数个数是大于我们的最大约数个数了
    //或者是等于等于最大约数个数并且p小于number的话
    if(s>maxd||s==maxd&&p<number)
    {
        maxd=s;//我们就要更新一下
        number=p;//然后number等于p,对吧
    }
    //好,接下来的话就去枚举一下啊
    //当然这里我们要判断一下啊,如果u已经的等于9了,表示已经枚举了所有情况了,那么我们就可以直接return了
    if(u==9)return;
    //然后接下来去枚举一下次数
    //次数的话咱们从一次开始枚举,一直枚举到第,last次对吧,不能比上一次多
    for(int i=1;i<=last;i++)
    {
        if((LL)p*primes[u]>n)//那每次都先算一下我们这个这个,p乘上一个我们当前的质数,看一下是不是已经大于n了
        break;//大于n的话那就直接break就可以了对吧
        //好,然后否则的的话,咱们就让p就乘上一个primes[u]
        p*=primes[u];
        //好然后再dfs下一次
        dfs(u+1,i,p,s*(i+1));//u+1,然后是这个i,对吧,p,还有这个s*(i+1);
        //好,然后我们来调试一下
    }
}

int main()
{
    cin>>n;
    dfs(0,30,1,1);
    cout<<number<<endl;
    return 0;
}



题目描述

题目要求我们计算指定区间和,题意很简单。我们只需要使用前缀和即可。
此题问题是区间的下标过大,−109≤l≤r≤109,为保证数组下标>=0,需要2e9大小,明显不可取。
正解为离散化。
何为离散化?当一组数据很大,而其绝对大小不会影响问题求解,只受相对大小影响时,我们可以把数据“缩小”同时维护其相对大小。
举例:一组数 0 12324 34355549,我们需要求大于0的数据个数时候,我们只需要维护后面的数据比前面大就可以了,至于具体大多少,我们不用管,因为不用求。
故离散化后可为:0 1 2
这样我们把数据规模给降下来了。

离散化3步:
1) 去重。及去除重复元素,可以使用STL中的unique函数。也可以手动实现
n=unique(a,a+n)-a;//n更新为去重后的长度
2)排序。既然要维护相对大小,排序是必不可少的。直接使用STL中sort即可。
sort(a,a+n);
3)离散。也就是说,给一个值,找到离散化后的值。这个其实很简单,我们前面已经把他们排好序了,那么他们的相对大小,不就是他们排序后所在下标吗。直接使用二分查找即可。

//如前面排好序后: 0 12324 34355549,传入x=34355549,返回2,也就是说34355549离散化后值为2
int query(int x) {
    return lower_bound(a, a + n, x) - a;
}

此题还需要注意的就是,我们需要先把要加上值的点先存起来,这样才能拿到需要离散化的数据,待离散化后再加上c。还有一些处理细节可看代码。

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 5;
struct node {
    int x, c;
} a[N];
int b[N], c[N];
int n, m, k;
//x离散后的值,其实就是下标
int query(int x) {
    return lower_bound(b, b + k, x) - b;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].c;
        b[i] = a[i].x;
    }
    k = unique(b, b + n) - b;//k是离散后的总数
    sort(b, b + k);
    for (int i = 0; i < n; i++) {
        int t = query(a[i].x);
        c[t] += a[i].c;
    }
    //前缀和
    for (int i = 1; i <=n; i++)
        c[i] += c[i - 1];
    while (m--) {
        int l, r, sum = 0;
        scanf("%d%d", &l, &r);
        int L = query(l), R = query(r); //L,R对应离散化后的区间
        //举个例子,离散前是400 500,现在来了个450。但是query(450)返回值是0,
        //不进行特判的话,会把400所在值加上。
        while(l>b[L]&&L<k)  L++;
        while(r<b[R]&&R>=0) R--;
        //R>=L保证是有效区间
        printf("%d\n",R>=L?c[R]-c[L-1]:0);
    }
    return 0;
}



#include<iostream>

using namespace std;
const int N=1e5+5;
int a[N],c[N];
int n,m;
int lowbit(int x){
    return x&(-x);
}
//第x个整数加上v 
void update(int x,int v){
    for(int i=x;i<=n;i+=lowbit(i))
        c[i]+=v;
}
//返回1~x的和 
int query(int x){
    int sum=0;
    for(int i=x;i>0;i-=lowbit(i))
        sum+=c[i];
    return sum; 
} 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    int last=0;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        update(i,t-last);
        last=t;
    }
    while(m--){
        char op;

        cin>>op;
        if(op=='Q'){
            int x;
            cin>>x;
            cout<<query(x)<<endl;
        }else{
            int l,r,d;
            cin>>l>>r>>d;
            update(l,d);
            update(r+1,-d);
        }
    }
    return 0;
}





#include <bits/stdc++.h>
using namespace std;
const int N=500000<<2;
struct line_tree {
    int lmax,rmax,sum,dat,l,r;
} t[N];
int n,m,a[N>>2];
int build(int p,int l,int r) {
    t[p].l=l;
    t[p].r=r;
    if(t[p].l==t[p].r) {
        t[p].dat=t[p].sum=t[p].lmax=t[p].rmax=a[l];
        return 0;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p*2+1,mid+1,r);
    t[p].sum=t[p<<1].sum+t[p*2+1].sum;
    t[p].lmax=max(t[p<<1].lmax,t[p<<1].sum+t[p*2+1].lmax);//本身,以及左边前缀和加上右边前缀最大子段和
    t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p<<1].rmax);//本身,以及右边前缀和加上左边后缀最大子段和.
    t[p].dat=max(max(t[p<<1].dat,t[p*2+1].dat),t[p<<1].rmax+t[p*2+1].lmax);
}
int change(int p,int x,int v) {
    if (t[p].l==t[p].r) {
        t[p].dat=v;
        t[p].sum=v;
        t[p].lmax=v;
        t[p].rmax=v;
        return 0;
    }
    int mid=(t[p].l+t[p].r)>>1;
    if (x<=mid)
        change(p<<1,x,v);
    else
        change(p*2+1,x,v);
    t[p].sum=t[p<<1].sum+t[p*2+1].sum;
    t[p].lmax=max(t[p<<1].lmax,t[p<<1].sum+t[p*2+1].lmax);
    t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p<<1].rmax);
    t[p].dat=max(max(t[p<<1].dat,t[p*2+1].dat),t[p<<1].rmax+t[p*2+1].lmax);
}
line_tree ask(int p,int l,int r) {
    if (l<=t[p].l && r>=t[p].r)
        return t[p];
    int mid=(t[p].l+t[p].r)>>1,val=-(1<<30);
    line_tree a,b,c;
    a.dat=a.sum=a.lmax=a.rmax=val;
    b.dat=b.sum=b.lmax=b.rmax=val;
    c.sum=0;
    if (l<=mid) {
        a=ask(p<<1,l,r);
        c.sum+=a.sum;
    }
    if (r>mid) {
        b=ask(p*2+1,l,r);
        c.sum+=b.sum;
    }
    c.dat=max(max(a.dat,b.dat),a.rmax+b.lmax);
    c.lmax=max(a.lmax,b.lmax+a.sum);
    if (l>mid)
        c.lmax=max(c.lmax,b.lmax);
    c.rmax=max(b.rmax,b.sum+a.rmax);
    if (r<=mid)
        c.rmax=max(c.rmax,a.rmax);
    return c;
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    build(1,1,n);
    while(m--) {
        int k,x,y;
        cin>>k>>x>>y;
        if (k==1) {
            if (x>y)
                swap(x,y);
            cout<<ask(1,x,y).dat<<endl;
        }
        if (k==2)
            change(1,x,y);
    }
    return 0;
}



活动打卡代码 AcWing 238. 银河英雄传说

#include<iostream>
#include<cmath> 
using namespace std;
const int N=30005,n=30000;
int T;
int f[N],d[N],num[N];
int find(int x) {
    if(x==f[x]) return x;
    int root=find(f[x]);
    d[x]+=d[f[x]];
    return f[x]=root;
}
void merge(int a,int b) {
    a=find(a),b=find(b);
//  if(a!=b) {
        f[a]=b;
        d[a]=num[b];
        num[b]+=num[a];
//  }
}
int main() {
    cin>>T;
    for(int i=1; i<=n; i++) {
        f[i]=i;
        num[i]=1;//所在集合只有他自己
    }

    while(T--) {
        char ch;
        int a,b;
        cin>>ch>>a>>b;
        if(ch=='M') {
            merge(a,b);
        } else {
            //这里不能a=find(a),b=find(b)
            //否则,后面d[a]=d[b]肯定是0,因为都是根了 
            int A=find(a),B=find(b);
            if(A!=B)    cout<<"-1"<<endl;
            else    cout<<max(0,abs(d[a]-d[b])-1)<<endl;
        }
    }
    return 0;
}




活动打卡代码 AcWing 237. 程序自动分析

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
using namespace std;
int t,n,f[1000007],book[1000007*3];  //t表示t组数据,n表示有n个操作,f[]是我们并查集的数字,book[]是离散化的数组
struct node {
    int x,y,e;
} a[1000001];
bool cmp(node a,node b) {
    return a.e>b.e;
}//排 序将e==1的放在前面
inline void first(int kkk) {
    for(int i=1; i<=kkk; i++)  f[i]=i;
}//初 始 化
int get(int x) {
    if(x==f[x]) return x;
    return f[x]=get(f[x]);
}
int main() {
    scanf("%d",&t);
    while(t--) {
        int tot=-1;
        memset(book,0,sizeof(book));
        memset(a,0,sizeof(a));
        memset(f,0,sizeof(f));
        int flag=1;
        scanf("%d",&n);

        for(int i=1; i<=n; i++) {
            scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].e);
            book[++tot]=a[i].x;
            book[++tot]=a[i].y;
        }
        sort(book,book+tot);//排序
        int reu=unique(book,book+tot)-book;  //去重
        //离散化 
        for(int i=1; i<=n; ++i) {
            a[i].x=lower_bound(book,book+reu,a[i].x)-book;
            a[i].y=lower_bound(book,book+reu,a[i].y)-book;
        }
        first(reu);   //初始化
        sort(a+1,a+n+1,cmp);  //按e排序
        for(int i=1; i<=n; i++) {
            int r1=get(a[i].x);
            int r2=get(a[i].y);
            if(a[i].e) {
                f[r1]=r2;  //就是我们的merge操作
            } else if(r1==r2) {
                printf("NO\n");
                flag=0;  //如果不满足条件,标记为否
                break;
            }
        }
        if(flag)    printf("YES\n");   //都满足条件了
    }
    return 0;
}