951

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个月前

算法

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个月前

题目描述

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


算法思路：

分块+广度优先搜索

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;
}


8个月前

#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个月前

#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;
}


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个月前

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;

}



8个月前

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;

}