第三题%SWH大神
目录
Divisors
暴力拆因数+数组离散化
要不是不知道一个数最多有几个因数就A了，怕开不下。。。
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXM=205,MAXN=600005;
int a[MAXM],brk[MAXN],ans[MAXM];
inline int read();
inline void div(const int &now){
for(int i=1;i*i<=a[now];++i){
if(a[now]%i==0){
brk[++brk[0]]=i;
if(i*i!=a[now])
brk[++brk[0]]=a[now]/i;
}
}
}
int main(){
freopen("div.in","r",stdin);
freopen("div.out","w",stdout);
int n=read(),m=read();
for(int i=1;i<=m;++i){
a[i]=read();
div(i);
}
brk[++brk[0]]=~0U>>1;
sort(brk+1,brk+brk[0]+1);
int tot=0;
for(int i=1,cnt=1;i<brk[0] && brk[i]<=n;++i){
if(brk[i]==brk[i+1]) ++cnt;
else{
++ans[cnt];
++tot;
cnt=1;
}
}
ans[0]=n-tot;
for(int i=0;i<=m;++i)
printf("%d\n",ans[i]);
fclose(stdin);
fclose(stdout);
return 0;
}
inline int read(){
char c; int x;
while(c=getchar(),c<'0' || '9'<c);
x=c-'0';
while(c=getchar(),'0'<=c && c<='9')
x=x*10+c-'0';
return x;
}Market
dp，dp，啊。。。先离线处理一下时间顺序就A了。。。
#include <cstdio>
#include <algorithm>
using namespace std;
#define min(a,b) (a<b ? a:b)
#define max(a,b) (a>b ? a:b)
const int MAXN=305,MAXM=100005;
const long long INF=~0ULL>>2;
long long dp[MAXM];
int n,m,lim,ans[MAXN];
struct shop{
int c,v,t;
}d[MAXN];
bool cmp1(const shop &a,const shop &b){
if(a.t!=b.t) return a.t<b.t;
if(a.c!=b.c) return a.c<b.c;
return a.v>b.v;
}
struct plan{
int no,t,m,pos;
}q[MAXM];
bool cmp2(const plan &a,const plan &b){
if(a.pos!=b.pos) return a.pos<b.pos;
if(a.m!=b.m) return a.m>b.m;
if(a.t!=b.t) return a.t<b.t;
return a.no<b.no;
}
inline int read();
inline int find(const int &i){
int l=1,r=n,mid,rt=0;
while(r>=l){
mid=(l+r)>>1;
if(d[mid].t>q[i].t)
r=mid-1;
else{
rt=max(rt,mid);
l=mid+1;
}
}
return rt;
}
int main(){
freopen("market.in","r",stdin);
freopen("market.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;++i){
d[i].c=read();
d[i].v=read();
d[i].t=read();
lim+=d[i].v;
}
sort(d+1,d+n+1,cmp1);
for(int i=1;i<=m;++i){
q[i].t=read();
q[i].m=read();
q[i].no=i;
q[i].pos=find(i);
}
sort(q+1,q+m+1,cmp2);
for(int i=1;i<=lim;++i)
dp[i]=INF;
int k=1;
while(!q[k].pos && k<=m) ++k;
for(int i=1;i<=n;++i){
for(int j=lim;j>=d[i].v;--j)
dp[j]=min(dp[j],dp[j-d[i].v]+d[i].c);
for(int j=lim;q[k].pos==i && k<=m;++k){
for(;j>=1;--j){
if(dp[j]<=q[k].m){
ans[q[k].no]=j;
break;
}
}
}
}
for(int i=1;i<=m;++i)
printf("%d\n",ans[i]);
fclose(stdin);
fclose(stdout);
return 0;
}
inline int read(){
char c; int x;
while(c=getchar(),c<'0' || '9'<c);
x=c-'0';
while(c=getchar(),'0'<=c && c<='9')
x=x*10+c-'0';
return x;
}Dash Speed
%%%SWH大神，生成树+按秩合并+线段树上的CDQ分治
#include <cstdio>
#include <cmath>
#include <stack>
using namespace std;
#define min(a,b) ((a)^(((a)^(b))&(-((a)>(b)))))
#define max(a,b) ((a)^(((a)^(b))&(-((a)<(b)))))
inline int read();
inline void swap(int &a,int &b);
const int MAXN=70005,MAXM=140005;
int n,m;
int he[MAXN],de[MAXN],ans[MAXN];
int rank[MAXN],fa[MAXN]; //union-find set
int st[MAXN][20]; //with dfn[],pos[], used for RMQ_LCA
int dfn[MAXM]; //the inorder list
int pos[MAXN]; //node NO.u's first pos in dfn
int cnt;
stack<int> s;
struct line{
int u,v,nex;
}ed[MAXM];
struct node{
int ls,rs,lp,rp;
};
struct chain{
int u,v; //lp,rp
}ln[MAXM];
//ln[i]: the longest chain the line NO.i in
struct change{
int pre_u,pre_v,u,v,sz;
}opt[MAXM];
int find(const int &x){
return fa[x] ? x:find(fa[x]);
}
inline void add(int he[],line ed[],int &cnt,const int &u,const int &v){
ed[++cnt].nex=he[u];
he[u]=cnt;
ed[cnt].u=u;
ed[cnt].v=v;
}
struct segT{
int cnt,he[MAXM],tot;
node d[MAXM];
line ed[MAXM];
segT(){cnt=1;}
void build(const int &u,int l,int r){
d[u].lp=l,d[u].rp=r;
if(l==r) return;
int mid=(l+r)>>1;
d[u].ls=++cnt;
build(d[u].ls,l,mid);
d[u].rs=++cnt;
build(d[u].rs,mid+1,r);
}
void ist(const int &u,const int &l,const int &r){
if(l<=d[u].lp && d[u].rp<=r){
add(he,ed,tot,l,r);
return;
}
int mid=(d[u].lp+d[u].rp)>>1;
if(r<=mid) ist(d[u].ls,l,r);
if(l>mid) ist(d[u].rs,l,r);
}
}T;
void dfs(const int &u,const int &fa){
dfn[++dfn[0]]=u;
de[u]=de[fa]+1;
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].v;
if(v!=fa){
dfs(v,u);
dfn[++dfn[0]]=u;
}
}
}
inline void st_load(){
for(int i=1;i<=dfn[0];++i)
st[i][0]=i;
for(int i=1;i<20;++i){
for(int j=1;j+(1<<i)-1<=cnt;++j){
if(de[dfn[st[j][i-1]]]<de[dfn[st[j+(1<<(i-1))][i-1]]])
st[j][i]=st[j][i-1];
else st[j][i]=st[j+(1<<(i-1))][i-1];
}
}
}
inline int get_len(const int &u,const int &v){
int posu=pos[u],posv=pos[v];
if(posu>posv) swap(posu,posv);
int k=log(posv-posu+1)/log(2);
return de[u]+de[v]-(min(de[dfn[st[posu][k]]],de[dfn[st[posv-(1<<k)+1][k]]]<<1));
}
int max_len(const int &now){
int fu=find(T.ed[now].u),fv=find(T.ed[now].v);
chain tmp;
int lenu=get_len(ln[fu].u,ln[fv].v);
int lenv=get_len(ln[fv].u,ln[fv].v);
int len;
if(lenu>lenv){
len=lenu;
tmp=ln[fu];
}
else{
len=lenv;
tmp=ln[fv];
}
//circumstances in which the two chain get together
int len_uv;
len_uv=get_len(ln[fu].u,ln[fv].u);
if(len_uv>len){
len=len_uv;
tmp.u=ln[fu].u;
tmp.v=ln[fv].u;
}
len_uv=get_len(ln[fu].u,ln[fv].v);
if(len_uv>len){
len=len_uv;
tmp.u=ln[fu].u;
tmp.v=ln[fv].v;
}
len_uv=get_len(ln[fu].v,ln[fv].u);
if(len_uv>len){
len=len_uv;
tmp.u=ln[fu].v;
tmp.v=ln[fv].u;
}
len_uv=get_len(ln[fu].v,ln[fv].v);
if(len_uv>len){
len=len_uv;
tmp.u=ln[fu].v;
tmp.v=ln[fv].v;
}
if(rank[fu]>rank[fv]){
opt[now].u=fv;
opt[now].v=fu;
opt[now].pre_u=ln[fu].u;
opt[now].pre_v=ln[fu].v;
fa[fv]=fu;
}
else{
opt[now].u=fu;
opt[now].v=fv;
opt[now].pre_u=ln[fv].u;
opt[now].pre_v=ln[fv].v;
fa[fu]=fv;
if(rank[fu]==rank[fv]){
++rank[fv];
opt[now].sz=1;
}
}
return len;
}
//reset the option
inline void reset(const int &now){
for(int i=T.he[now];i;i=T.ed[i].nex)
s.push(i);
while(s.size()){
ln[opt[s.top()].v].u=opt[s.top()].pre_u;
ln[opt[s.top()].u].v=opt[s.top()].pre_v;
fa[opt[s.top()].v]=0;
rank[opt[s.top()].v]-=opt[s.top()].sz;
s.pop();
}
}
//divid and conquer
void solve(const int &u,int s){
for(int i=T.he[u];i;i=T.ed[i].nex)
s=max(s,max_len(i));
if(T.d[u].lp==T.d[u].rp){
ans[T.d[u].lp]=s;
reset(u);
return;
}
solve(T.d[u].ls,s);
solve(T.d[u].rs,s);
reset(u);
}
int main(){
freopen("speed.in","r",stdin);
freopen("speed.out","W",stdout);
n=read(),m=read();
T.build(1,1,n);
for(int i=1,u,v,l,r;i<n;++i){
u=read(),v=read();
add(he,ed,cnt,u,v),add(he,ed,cnt,v,u);
l=read(),r=read();
T.ist(1,l,r);
}
dfs(1,0);
st_load();
for(int i=1;i<=n;++i)
ln[i].u=ln[i].v=i; //what?
solve(1,0);
for(int i=1,q;i<=m;++i){
q=read();
printf("%d\n",ans[q]);
}
fclose(stdin);
fclose(stdout);
return 0;
}
inline int read(){
char c; int x;
while(c=getchar(),c<'0' || '9'<c);
x=c-'0';
while(c=getchar(),'0'<=c && c<='9')
x=x*10+c-'0';
return x;
}
inline void swap(int &a,int &b){
a^=b,b^=a,a^=b;
}