头像

抱元守一




离线:3个月前


最近来访(0)

活动打卡代码 AcWing 9. 分组背包问题

抱元守一
3个月前
#include<stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))
int v[101][101];
int w[101][101];
int s[101];
int dp[101];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        for(int j=1;j<=s[i];j++){
            scanf("%d%d",&w[i][j],&v[i][j]);
        }   
    }
    for( int i=1;i<=n;i++){
        for(int k=m;k>=0;k--){
            for(int j=1;j<=s[i];j++){
                if(w[i][j]<=k)
                dp[k] = max(dp[k],dp[k-w[i][j]]+v[i][j]);
            }
        }
    }

    return 0;
}




抱元守一
7个月前

算法

(二分搜索+分治) $O(log^2n)$

沿着对角线利用二分查找算法查找大于等于target且最小值位置,根据该位置把二维数组分成四份,排除左上角全部小于target,排除右下角全部大于target,还剩下左下角和右上角需要考虑。用相同方法处理子问题。

时间复杂度

一共可以分解为logn个子问题,每个子问题又需要logn来处理,所以时间复杂度$O(log^2n)$

C++ 代码

附上时间对比代码,理论与实践相结合~

#include<cstdio>
#include<Windows.h> 
#include <stdlib.h>
const int N =15500;
bool _searchArray(long long array[N][N],int sr,int sc,int er,int ec,int target)
{

    //printf("起始行列:%d %d,终止行列:%d %d\n",sr,sc,er,ec);
    //if(sr > er || sc > ec) return 0;
    int cl = sc ,cr = ec, rl = sr, rr = er;
    while ((cl <= cr && rl < rr) || (cl < cr && rl <= rr) )
    {
        int midc = (cl+cr)>>1,midr = (rl+rr)>>1;
        if(cl==cr && rl < rr)
            if(array[midr][midc]>=target) rr =  midr;else rl = midr+1;
        else if(rl == rr && cl < cr)
            if(array[midr][midc]>=target) cr =  midc;else cl = midc+1;
        else
            if (array[midr][midc] >= target) {cr = midc,rr = midr;}
            else {cl=midc+1,rl=midr+1;}
    }

    //printf("%d %dvalue:%d,target:%d\n",rl,cl,array[rl][cl],target);
    if(array[rl][cl]==target) return 1;
    else if(array[rl][cl] < target) return 0;
    //答案在rl~n行的0~cl-1列,或cl~m列的0~rl-1行
    bool ans1 = false,ans2=false;
    if(sc <=cl-1)
        ans1 = _searchArray(array,rl,sc,er,cl-1,target);
    if (ans1) return ans1;
    if (sr <=rl-1)
        ans2 = _searchArray(array,sr,cl,rl-1,ec,target);
    return ans2;
}
bool searchArray(long long array[N][N], int arrayRowSize, int arrayColSize, int target) {
    int cl = 0 ,cr = arrayColSize - 1, rl = 0, rr = arrayRowSize - 1;
    if (arrayColSize == 0 || arrayRowSize==0 ) return false;
    return _searchArray(array,rl,cl,rr,cr,target);

}
long long array[N][N];

bool otherSearch(long long array[N][N], int arrayRowSize, int arrayColSize, int target){

      int i = 0, j = arrayColSize - 1;
        while (i < arrayRowSize && j >= 0) {
            if (array[i][j] == target) return true;
            if (array[i][j] > target) j -- ;
            else i ++ ;
        }
        return false;
}
#include<time.h>
int main()
{
    long long k = 0;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) array[i][j] = k++;
    srand((unsigned)time(NULL)); 
    int s = rand();
    s*=s/5;
    printf("searching %d in %d*%d\n",s,N,N);
    if(searchArray(array,N,N,s) == otherSearch(array,N,N,s))
        printf("Two method result is equal~\n");
    clock_t start = clock();
    for (int i=0;i<=100000;i++)
    searchArray(array,N,N,s); 
    clock_t end = clock();
    printf("method1 call 100000 times cost:%fs\n",(double)(end-start)/CLOCKS_PER_SEC);
    start = clock(); 
    for (int i=0;i<=100000;i++)
    otherSearch(array,N,N,s);
    end = clock();
    printf("method2 call 100000 times cost:%fs\n",(double)(end-start)/CLOCKS_PER_SEC);

}




抱元守一
7个月前

题目描述

在一片广袤无垠的原野上,散落着N块磁石。每个磁石的性质可以用一个五元组(x,y,m,p,r)描述,其中x,y表示其坐标,m是磁石的质量,p是磁力,r是吸引半径。若磁石A与磁石B的距离不大于磁石A的吸引半径,并且磁石B的质量不大于磁石A的磁力,那么A可以吸引B。小取酒带着一块自己的磁石L来到了这片原野的(x0,y0)处,我们可以视磁石L的坐标为(x0,y0)。
小取酒手持磁石L并保持原地不动,所有可以被L吸引的磁石将会被吸引过来。在每个时刻,他可以选择更换任意一块自己已经获得的磁石(当然也可以是自己最初携带的L磁石)在(x0,y0)处吸引更多的磁石。
小取酒想知道,他最多能获得多少块磁石呢?
输入格式
第一行五个整数x0,y0,pL,rL,N,表示小取酒所在的位置,磁石L磁力、吸引半径和原野上散落磁石的个数。
接下来N行每行五个整数x,y,m,p,r,描述一块磁石的性质。
输出格式
输出一个整数,表示最多可以获得的散落磁石个数(不包含最初携带的磁石L)。
数据范围
1≤N≤250000,−10^9≤x,y≤10^9,1≤m,p,r≤10^9

样例

输入样例:

0 0 5 10 5
5 4 7 11 5
-7 1 4 7 8
0 2 13 5 6
2 -3 9 3 4
13 5 1 9 9

输出样例:

3

算法思路:

分块+广度优先搜索

思路书上写得很清楚,其他题解也有讲,就不重复造轮子了,就是广度优先搜索加分块。
我对代码进行了两处优化,把总时间控制再900ms左右。
1,对于需要使用朴素算法处理的块,使用二分搜索算法过滤掉区间内无需处理的磁力块(块内距离排序,故过滤掉距离不合适的磁力块),为了不破坏区间的顺序并且更新区间左端点,采用从后向前的方式遍历区间。
2,由于一直站在同一个点,所以我们可以直接过滤掉很多垃圾的磁力石,即磁力和磁力范围均很低的磁力块。记录一下当前的双属性最佳磁力块,对于一切磁力和磁力范围都小于双属性最佳磁力块则无需加入到队列中。
这两处优化,原理是二分和剪枝

时间复杂度

$O(n\sqrt{n})$

参考文献

算法竞赛进阶指南

C++ 代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 250010;
struct magnet
{
    long long d;
    long long r;
    int m;
    int p;
};

bool cmpMass(const magnet& a, const magnet& b)
{
    return a.m < b.m;
}
bool cmpDist(const magnet& a,const magnet& b)
{
    return a.d < b.d;
}
int block,t,n;
magnet input[N];
int L[1000],R[1000],MIN[1000],MAX[1000];//左端点,右端点,区间m的最小值,区间m的最大值
queue<magnet> m_que;

int find(int mass)
{
    int l=1,r=t;
    while(l < r)
    {
        int mid = (l+r+1)>>1;
        if (MIN[mid]<= mass) l = mid; else r = mid - 1;

    }
    //1~l-1段所有磁石的质量都小于mass
    //l段有些磁石质量小于等于mass
    return l;
}

int find(int l,int r,long long dist)
{
    while(l < r)
    {
        int mid = (l+r+1)>>1;
        if(input[mid].d <= dist) l = mid; else r = mid - 1;
    }
    return l;
}

void build()
{
    t = sqrt(n);
    block = max(1,t);

    for(int i=1;i<=t;i++) L[i]=(i-1)*block+1,R[i]=i*block,MIN[i]=input[L[i]].m,MAX[i]=input[R[i]].m;
    if(R[t]<n) t++, L[t]=R[t-1]+1, R[t]=n,MIN[t]=input[L[t]].m,MAX[t]=input[R[t]].m;
    for(int i=1;i<=t;i++) sort(input+L[i],input+R[i]+1,cmpDist);

}
int main()
{
    long long xl,yl,rl,pl;
    cin >> xl >> yl >> pl >> rl >> n;
    magnet init{0LL,rl*rl,0,pl};
    for(int i=1;i<=n;i++) 
    {
        long long x,y,m,p,r;
        scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&p,&r);
        input[i].r = r*r;
        input[i].d = (x-xl)*(x-xl)+(y-yl)*(y-yl);
        input[i].m = m;
        input[i].p = p;
    }

    sort(input+1,input+n+1,cmpMass);
    build();
    m_que.push(init);
    int ans = 0;
    long long max_p=init.p,max_r=init.r;
    while (!m_que.empty())
    {
        magnet now = m_que.front();
        int k = find(now.p);
        int q = now.p >= MAX[k]?k:k-1;
        for(int i=1;i<=q;i++){

            while(L[i] <= R[i] && input[L[i]].d<=now.r)
            { 
                //优化2,剪枝
                if(input[L[i]].r>max_r || input[L[i]].p>max_p){
                    m_que.push(input[L[i]]);
                    if(input[L[i]].r>max_r && input[L[i]].p>max_p)
                        max_p = input[L[i]].p,max_r = input[L[i]].r;
                }
                L[i]++;
                ans++;
            }

        }

        if (k > q && input[L[k]].d < now.r )
        {
            //优化1,二分查找
            int rs = find(L[k],R[k],now.r);
            for(int j=rs;j>=L[k];j--)
            {

                if(input[j].m <= now.p)
                {
                    //优化2,剪枝
                    if(input[j].r>max_r || input[j].p>max_p)
                    {
                        m_que.push(input[j]);
                        if(input[j].r>max_r && input[j].p>max_p)
                            max_p = input[j].p,max_r = input[j].r;
                    }
                    ans++;
                }else
                {   
                    if(j < rs) input[rs] = input[j];
                    rs--;
                }
            }

            L[k] = rs+1;
        }
        m_que.pop();
    }
    cout << ans <<endl;
    return 0;
}




抱元守一
7个月前
#include<iostream>
using namespace std;

int main()
{
 int n;
 cin >> n;
 for(int i=1;i<=n;i++)
 {
     int t,c=0;
     cin >> t;
     for(int j=0;j<30;j++)
        if((t&1<<j)!=0) c++;
     cout << c <<" ";
 }
 cout<<endl;
 return 0;
}



抱元守一
8个月前
#include<iostream>
using namespace std;
const int N=100010;
int a[N],s[N];
int res = 1;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int i=1,j=1;
    s[a[j]]++;
    while(j<=n)
    {

        if(s[a[j]] > 1) {
            s[a[i]]--; i++;

        }
        else {
            if(j-i+1 > res) res = j-i+1;
            j++,s[a[j]]++;

        }

    }
    printf("%d",res);
    return 0;
}


活动打卡代码 AcWing 2816. 判断子序列

抱元守一
8个月前

挑战模式,第二次提交成功,第一次搞反了n,m时间紧迫没来得及调试

#include<iostream>
using namespace std;
const int N=100010;
int a[N];
int b[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++) scanf("%d",&b[i]);

    int i=1,j=1;
    while(i<=n && j<=m)
    {
        if(a[i]!=b[j]) j++;
        else i++,j++;
    }
    if(i==n+1) printf("Yes");
    else printf("No");
    return 0;
}




抱元守一
8个月前

很开心,写完直接提交就AC了!~

#include<iostream>
using namespace std;
const int N = 100010;
int a[N];
int b[N];

int main()
{
    int n,m,x;
    scanf("%d%d%d",&n,&m,&x);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++) scanf("%d",&b[i]);
    int i=n-1;
    int j=0;
    while(i>=0 && j<n)
    {
        if(a[i]+b[j]>x) i--;
        else if(a[i]+b[j]<x) j++;
        else {printf("%d %d",i,j);break;}
    }
    return 0;
}


活动打卡代码 AcWing 798. 差分矩阵

抱元守一
8个月前
#include<iostream>
using namespace std;
const int N = 1010;
int a[N][N];
int d[N][N];
//S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
void insert(int x1,int y1,int x2,int y2,int c)
{
    d[x1][y1]+=c;    //(x1,y1)右方及下方的点受到影响
    d[x2+1][y1]-=c;  //排除y1列超过x2行的影响
    d[x1][y2+1]-=c;  //排除x1行超过y2列的影响
    d[x2+1][y2+1]+=c;//保持不变


}
int main()
{
    int n,m,q,tmp;
    scanf("%d%d%d",&n,&m,&q);
    //首先直接建立二维差分数组
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&tmp);
            insert(i,j,i,j,tmp);
        }
    //更新二维差分数组 
    while(q--)
    {
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        insert(x1,y1,x2,y2,c);
    }
    //通过差分数组求前缀和
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            a[i][j]=a[i-1][j]+ a[i][j-1] -a[i-1][j-1] +d[i][j];
        }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }

    return 0;
}



抱元守一
8个月前

众所周知,唐老师特别喜欢挑战难度很高的电子游戏,有一天他挑战了一款回合对战游戏,唐老师的阵地有N个哨塔,编号由1到N,且初始时每个哨塔有自己的血量,游戏开始后,敌军会对唐老师的阵地发起M轮进攻,每轮进攻都会对一些哨塔产生等量的伤害。且满足第i轮进攻会对编号Li到Ri的哨塔造成等量伤害Di,M轮进攻结束后,唐老师需要快速对血量最低的K座哨塔进行修补,若存在与第K座哨塔相同血量仍需要输出,输出的哨塔编号个数可能多余K个,由于哨塔特别多,所以请帮忙设计程序帮助唐老师快速的找出需要修补的哨塔的编号,输出编号按从小到大顺序。

输入格式:
第一行包含两个三整数N,M,K。
第二行包含N个正整数,表示编号1到N哨塔的血量。
接下来M行,每行包含三个整数L,R,D,表示一轮进攻对编号L到R的哨塔造成了D点伤害。
输出格式:
共一行,包含K个正整数,以空格分隔,表示需要修补的哨塔编号。

数据范围:
1≤N,M≤100000,
1≤L≤R≤N,
1≤K≤N,
1≤D≤1000,
1≤哨塔血量≤21亿,且M轮进攻后不存在哨塔血量小于等于0的情况。

输入样例:
7 3 6
500 500 500 500 500 500 500
1 7 100
2 3 50
3 5 200
输出样例:
1 2 3 4 5 6 7

#include<iostream>
using namespace std;
const int N = 100010;

typedef struct Tower
{
    int idx;
    int hp;
}tower;

tower a[N];
int d[N];
bool ans[N];

inline void insert(int l,int r,int c)
{
    d[l]+=c;
    d[r+1]-=c;
}

int part(tower q[],int l,int r,int k)
{
    if(l == r) return q[l].hp;
    int key = q[l+r>>1].hp;
    int i=l-1,j=r+1;
    while (i < j)
    {
        do i++; while(q[i].hp<key);
        do j--; while(q[j].hp>key);
        if (i < j)
            swap(q[i],q[j]);
    }
    int llen = j-l+1;
    if( k<=llen)
        part(q,l,j,k);
    else
        part(q,j+1,r,k-llen);


}


int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) 
    {
        a[i].idx = i;
        scanf("%d",&a[i].hp);
        insert(i,i,a[i].hp);
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,d;
        scanf("%d%d%d",&l,&r,&d);
        insert(l,r,-d);
    }
    for(int i=1;i<=n;i++){
        a[i].hp = a[i-1].hp+d[i];
        //printf("%d ",a[i].hp);
    }
    //printf("\n");
    int khp = part(a,1,n,k);
    for(int i=1;i<=n;i++)
        if (a[i].hp <= khp)
            ans[a[i].idx] = true;
    for(int i=1;i<=n;i++)
        if(ans[i]) 
            printf("%d ",i);

    return 0;

}

暂时没有制作非常准确大数据,不能完全确定代码的正确性,如果有感兴趣的同学,可以自行研究一下~

作者:抱元守一
链接:https://www.acwing.com/activity/content/code/content/593593/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



活动打卡代码 AcWing 797. 差分

抱元守一
8个月前

突发奇想,打算创造出一道差分和快排分区算法的题~
众所周知,唐老师特别喜欢挑战难度很高的电子游戏,有一天他挑战了一款回合对战游戏,唐老师的阵地有N个哨塔,编号由1到N,且初始时每个哨塔有自己的血量,游戏开始后,敌军会对唐老师的阵地发起M轮进攻,每轮进攻都会对一些哨塔产生等量的伤害。且满足第i轮进攻会对编号Li到Ri的哨塔造成等量伤害Di,M轮进攻结束后,唐老师需要快速对血量最低的K座哨塔进行修补,若存在与第K座哨塔相同血量仍需要输出,输出的哨塔编号个数可能多余K个,由于哨塔特别多,所以请帮忙设计程序帮助唐老师快速的找出需要修补的哨塔的编号,输出编号按从小到大顺序

输入格式:
第一行包含两个三整数N,M,K。
第二行包含N个正整数,表示编号1到N哨塔的血量。
接下来M行,每行包含三个整数L,R,D,表示一轮进攻对编号L到R的哨塔造成了D点伤害。
输出格式:
共一行,包含K个正整数,以空格分隔,表示需要修补的哨塔编号。

数据范围:
1≤N,M≤100000,
1≤L≤R≤N,
1≤K≤N,
1≤D≤1000,
1≤哨塔血量≤10000,且M轮进攻后不存在哨塔血量小于等于0的情况。

输入样例:
7 3 6
500 500 500 500 500 500 500
1 7 100
2 3 50
3 5 200
输出样例:
1 2 3 4 5 6 7

#include<iostream>
using namespace std;
const int N = 100010;

typedef struct Tower
{
    int idx;
    int hp;
}tower;

tower a[N];
int d[N];
bool ans[N];

inline void insert(int l,int r,int c)
{
    d[l]+=c;
    d[r+1]-=c;
}

int part(tower q[],int l,int r,int k)
{
    if(l == r) return q[l].hp;
    int key = q[l+r>>1].hp;
    int i=l-1,j=r+1;
    while (i < j)
    {
        do i++; while(q[i].hp<key);
        do j--; while(q[j].hp>key);
        if (i < j)
            swap(q[i],q[j]);
    }
    int llen = j-l+1;
    if( k<=llen)
        part(q,l,j,k);
    else
        part(q,j+1,r,k-llen);


}


int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) 
    {
        a[i].idx = i;
        scanf("%d",&a[i].hp);
        insert(i,i,a[i].hp);
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,d;
        scanf("%d%d%d",&l,&r,&d);
        insert(l,r,-d);
    }
    for(int i=1;i<=n;i++){
        a[i].hp = a[i-1].hp+d[i];
        //printf("%d ",a[i].hp);
    }
    //printf("\n");
    int khp = part(a,1,n,k);
    for(int i=1;i<=n;i++)
        if (a[i].hp <= khp)
            ans[a[i].idx] = true;
    for(int i=1;i<=n;i++)
        if(ans[i]) 
            printf("%d ",i);

    return 0;

}


暂时没有制作非常准确大数据,如果有感兴趣的同学,可以帮忙做一下大数据,并发给我,谢谢啦