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