Educational Codeforces Round 17

A
水题

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,k;
int main(){
	cin>>n>>k;
	vector<LL>fac;
	for(LL i=1;i*i<=n;i++){
		if(n%i==0){
			fac.push_back(i);
			if(i*i!=n)
				fac.push_back(n/i);
		}
	}
	sort(fac.begin(),fac.end());
	if(k<=fac.size())
		cout<<fac[k-1]<<endl;
	else cout<<-1<<endl
		else cout<<-1<<endl;;
	return 0;
}

B
嗯……贪心

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
int a,b,c,m;
int u[maxn],p[maxn];
int main(){
	scanf("%d%d%d%d",&a,&b,&c,&m);
	for(int i=1;i<=m;i++){
		int x;
		char s[66];
		scanf("%d%s",&x,s);
		if(s[0]=='U'){
			u[++u[0]]=x;
		}else{
			p[++p[0]]=x;
		}
	}

	sort(u+1,u+1+u[0]);
	sort(p+1,p+1+p[0]);

	int cnt=0;
	long long sum=0;

	int cura=0,curb=0;

	while(cura<u[0]&&a>0){
		cnt++;
		sum+=u[++cura];
		a--;
	}

	while(curb<p[0]&&b>0){
		cnt++;
		sum+=p[++curb];
		b--;
	}

	vector<int>vec;
	for(int i=cura+1;i<=u[0];i++)vec.push_back(u[i]);
	for(int i=curb+1;i<=p[0];i++)vec.push_back(p[i]);
	sort(vec.begin(),vec.end());

	for(int i=0;i<c&&i<vec.size();i++){
		cnt++;
		sum+=vec[i];
	}
	cout<<cnt<<" "<<sum<<endl;
	return 0;
}

C
题意:给定两个串,在第二个串中删除尽量短的一个子串,使得剩余串是第一个串的一个子序列
题解:正反序贪心预处理子序列匹配处,枚举删除的右端点,二分找个最大的

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
char s1[maxn],s2[maxn];
int n,m;
int a[maxn],b[maxn];
vector<int>vec[256];
int main(){
	scanf("%s%s",s1+1,s2+1);
	n=strlen(s1+1);
	m=strlen(s2+1);

	for(int i=1;i<=n;i++){
		vec[s1[i]].push_back(i);
	}
	for(int i=1;i<=m;i++){
		int p=upper_bound(vec[s2[i]].begin(),vec[s2[i]].end(),a[i-1])-vec[s2[i]].begin();
		if(p==vec[s2[i]].size())a[i]=n+1;
		else a[i]=vec[s2[i]][p];
	}

//	for(int i=1;i<=m;i++)
//		cout<<a[i]<<" \n"[i==m]; if(a[m]!=n+1){ puts(s2+1); return 0; } b[m+1]=n+1; for(int i=m;i>=1;i--){
		int p=lower_bound(vec[s2[i]].begin(),vec[s2[i]].end(),b[i+1])-vec[s2[i]].begin()-1;
		if(p<0)b[i]=0;
		else b[i]=vec[s2[i]][p];
	}
//	for(int i=1;i<=m;i++)
//		cout<<b[i]<<" \n"[i==m]; int l=1,r=m; for(int i=m+1;i>=1;i--){
		int p=lower_bound(a+1,a+i,b[i])-a-1,nl,nr;
		if(p<=0){
			if(b[i]!=0)
				nl=1,nr=i-1;
			else continue;
		}else{
			nl=p+1,nr=i-1;
		}
	//	cout<<p<<" "<<nl<<" "<<nr<<endl;
			if(nl<=nr&&nr-nl<r-l){
				r=nr;
				l=nl;
			}
	}

	if(l==1&&r==m)puts("-");
	else{
		for(int i=1;i<=m;i++)if(!(l<=i&&i<=r))
			putchar(s2[i]);
		puts("");
	}
	return 0;
}

D
题意:给定一个3xn的网格图,求一个从左上到右下最大的简单路径
题解:注意到如果往回走,存在一种最优情况,使得它最多向右走一格,(因为我们可以上下晃一下来减少两个)
所以可以用一种简单的插头dp,压记录一下右边三个插头,转移转移即可

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
LL dp[maxn][6];
int n;
LL a[4][maxn];
void up(LL& x,LL y){
	if(x<y)x=y;
}
int main(){
	scanf("%d",&n);
	for(int j=1;j<=3;j++)
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[j][i]);
		}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=6;j++)
			dp[i][j]=-(1LL<<61);
	}

	dp[1][1]=a[1][1];
	dp[1][2]=a[1][1]+a[2][1];
	dp[1][3]=a[1][1]+a[2][1]+a[3][1];
	dp[1][4]=a[1][1]+a[2][1]+a[3][1];
	for(int i=1;i<n;i++){
		up(dp[i+1][1],dp[i][1]+a[1][i+1]);	
		up(dp[i+1][2],dp[i][1]+a[1][i+1]+a[2][i+1]);
		up(dp[i+1][3],dp[i][1]+a[1][i+1]+a[2][i+1]+a[3][i+1]);
		up(dp[i+1][4],dp[i][1]+a[1][i+1]+a[2][i+1]+a[3][i+1]);

		up(dp[i+1][1],dp[i][2]+a[1][i+1]+a[2][i+1]);
		up(dp[i+1][2],dp[i][2]+a[2][i+1]);
		up(dp[i+1][3],dp[i][2]+a[2][i+1]+a[3][i+1]);

		up(dp[i+1][1],dp[i][3]+a[1][i+1]+a[2][i+1]+a[3][i+1]);
		up(dp[i+1][2],dp[i][3]+a[2][i+1]+a[3][i+1]);
		up(dp[i+1][3],dp[i][3]+a[3][i+1]);
		up(dp[i+1][4],dp[i][3]+a[1][i+1]+a[2][i+1]+a[3][i+1]);

		up(dp[i+1][1],dp[i][4]+a[1][i+1]+a[2][i+1]+a[3][i+1]);
		up(dp[i+1][3],dp[i][4]+a[1][i+1]+a[2][i+1]+a[3][i+1]);
		
	}

	for(int i=1;i<=n;i++){
//		for(int j=1;j<=5;j++)
//			printf("%d ",dp[i][j]);
//		puts("");
	}
	cout<<dp[n][3]<<endl;
	return 0;
}

E
替罪羊重构的kdtree可以直接上

#include<bits/stdc++.h>
using namespace std;
int lans=0;
const int maxn=1e5+5;
int in(){
	int x;scanf("%d",&x);
	return x;
    int r=0;char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))r=r*10+c-'0',c=getchar();
    return r;
}
int n;
struct point{
    int x,y,val;
    int& operator[](const int s){return s==0?x:y;}
	point(){val=1;}
	point(int _x,int _y):x(_x),y(_y){val=1;}
}p[maxn];
struct rec{
    int x[2],y[2];
    rec(){}
	rec(point a,point b){
		x[0]=a.x;
		x[1]=b.x;
		y[0]=a.y;
		y[1]=b.y;
	}
    rec(point p){x[0]=x[1]=p.x;y[0]=y[1]=p.y;}
};
bool operator==(const point &A,const point &B){
    return A.x==B.x&&A.y==B.y;
}
inline rec operator+(const rec &ls,const rec &rs){
    static rec R;R=ls;
    R.x[0]=min(R.x[0],rs.x[0]);
    R.x[1]=max(R.x[1],rs.x[1]);
    R.y[0]=min(R.y[0],rs.y[0]);
    R.y[1]=max(R.y[1],rs.y[1]);
    return R;
}
inline bool operator*(const point &p,const rec &R){
    return R.x[0]<=p.x&&p.x<=R.x[1]&&R.y[0]<=p.y&&p.y<=R.y[1];
}
inline bool In(const rec &A,const rec &B){
    return B.x[0]<=A.x[0]&&A.x[1]<=B.x[1]&&B.y[0]<=A.y[0]&&A.y[1]<=B.y[1]; } inline bool Out(const rec &A,const rec &B){ return B.x[0]>A.x[1]||A.x[0]>B.x[1]||B.y[0]>A.y[1]||A.y[0]>B.y[1];
}
struct node{
    rec R;point p;
    int sum,siz;
    node *c[2];
    node *rz(){
        sum=p.val;R=rec(p);siz=1;
        if(c[0])sum+=c[0]->sum,R=R+c[0]->R,siz+=c[0]->siz;
        if(c[1])sum+=c[1]->sum,R=R+c[1]->R,siz+=c[1]->siz;
        return this;
    }
    node(){sum=0;siz=1;c[0]=c[1]=0;}
}*root,*re,pool[maxn],*cur=pool;
node *sta[maxn];
int D,si;
bool cmp(const point &A,const point &B){
    if(D)return A.x<B.x||(A.x==B.x&&A.y<B.y);
    return A.y<B.y||(A.y==B.y&&A.x<B.x); } int top; node *newnode(){ if(si)return sta[si--]; return cur++; } node* build(int l,int r,int d){ int mid=(l+r)>>1;D=d;
    nth_element(p+l,p+mid,p+r+1,cmp);
    node *t=newnode();t->p=p[mid];
    if(l<=mid-1)t->c[0]=build(l,mid-1,d^1);
    if(mid+1<=r)t->c[1]=build(mid+1,r,d^1);
    return t->rz();
}
void dfs(node *&t){
    if(t->c[0])dfs(t->c[0]);
    p[++top]=t->p;
    if(t->c[1])dfs(t->c[1]);
    sta[++si]=t;*t=node();
    //delete t;
}
node* rebuild(node *&t){
    if(!t)return 0;
    top=0;dfs(t);
    return build(1,top,0);
}
#define siz(x) (x?x->siz:0)
void Add(node *&t,point p){
    D^=1;
    if(!t){t=newnode(),t->p=p;t->rz();return;}
    if(t->p==p){t->p.val+=p.val;t->rz();return;}
    if(p[D]<t->p[D])Add(t->c[0],p);
    else Add(t->c[1],p);t->rz();
    if(max(siz(t->c[0]),siz(t->c[1]))>0.7*t->siz)
        re=t;
}
int Qans;
void Q(const node *t,const rec &R){
    if(Out(t->R,R))return ;
    if(In(t->R,R)){Qans+=t->sum;return;}
    if(t->p*R)Qans+=t->p.val;
    if(t->c[0])Q(t->c[0],R);
    if(t->c[1])Q(t->c[1],R);
}
int k;
tuple<int,int,int> a[maxn];
int main(){
	n=in();k=in();
	for(int i=1;i<=n;i++){
		get<1>(a[i])=in();
		get<0>(a[i])=in();
		get<2>(a[i])=in();
	}
	sort(a+1,a+1+n);
	long long ans=0;
	for(int i=n;i>=1;i--){
		int r=get<0>(a[i]);
		int x=get<1>(a[i]);
		int f=get<2>(a[i]);
	//	cerr<<r<<" "<<x<<" "<<f<<endl;
		int res=0;

		Qans=0;
		if(i!=n)Q(root,rec(point(x-r,f-k),point(x+r,f+k)));
		res+=Qans;
		//cerr<<res<<endl;
		re=0;D=1;
		Add(root,point(x,f));
		if(re)rebuild(re);
		ans+=res;
	}
	cout<<ans<<endl;

	return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注