@KirinBill
2017-10-23T16:19:43.000000Z
字数 6548
阅读 1163
题解
套题
目录
#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
string in=file+".in",out=file+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
int pm=1; char c;
do{
c=getchar();
if(c=='-') pm=-1;
}while(!isdigit(c));
x=c^'0';
while(c=getchar(),isdigit(c))
x=x*10+(c^'0');
x*=pm;
}
template<typename type>
void write(type x,char c=0){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10|'0');
if(c) putchar(c);
}
#include <algorithm>
#include <cstring>
using std::max;
using std::min;
using std::upper_bound;
const int MAXN=350;
int t,A,B,C,D,len,last,first;
int a[MAXN*MAXN],pos[MAXN];
long long n;
inline void prod_seq(){
a[1]=t;
pos[t]=1;
for(int i=2;;++i){
t=(A*t*t%D+B*t%D+C)%D;
if(pos[t]){
first=pos[t];
last=t;
len=i-1;
return;
}
pos[t]=i;
a[i]=t;
}
}
inline long long DP(){
static int dp[MAXN*MAXN];
int nocir=first-1;
int cir=len-nocir;
int pre=len;
len+=cir*(cir-1)-nocir;
long long now=nocir+len+(n-len-nocir)%len;
if(now>n) now=n;
for(int i=pre+1;i<=now;++i)
a[i]=a[i-cir];
long long rest= (n-len-nocir)/len>0 ? (n-len-nocir)/len:0;
rest*=cir;
memset(dp,0x7f,sizeof(dp));
long long ret=0,tmp;
for(int i=1;i<=now;++i){
tmp=upper_bound(dp+1,dp+now+1,a[i])-dp;
dp[tmp]=min(dp[tmp],a[i]);
if(i>nocir) tmp+=rest;
ret=max(ret,tmp);
}
return ret;
}
int main(){
setIO("lis");
read(n);
read(t),read(A),read(B),read(C),read(D);
prod_seq();
write(DP());
return 0;
}
#include <cstdio>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <queue>
using std::sort;
using std::min;
using std::queue;
const int MAXN=55;
int n,l,c;
long long w[MAXN];
namespace solve1{
const int MAXW=3000005;
int dp[MAXW];
inline void DP(){
static queue<int> que;
memset(dp,0x7f,sizeof(dp));
dp[0]=0;
que.push(0);
int u,v;
while(que.size()){
u=que.front();
que.pop();
if(dp[u]>=c) continue;
for(int i=1,d;i<=n;++i){
v=u+w[i],d=dp[u]+1;
if(dp[v]>d){
dp[v]=d;
que.push(v);
}
}
}
}
inline bool jud(long long v){return v<=MAXW && dp[v]<=c;}
}
namespace solve2{
const int MAXC=35,MAXW=20005;
long long dp[MAXC][MAXW];
struct node{
int c;
long long w;
};
inline void DP(){
static bool inQ[MAXC][MAXW];
static queue<node> que;
memset(dp,0x7f,sizeof(dp));
dp[0][0]=0;
que.push((node){0,0});
inQ[0][0]=true;
node u,v;
while(que.size()){
u=que.front();
que.pop();
inQ[u.c][u.w%w[1]]=false;
for(int i=1,d;i<=n;++i){
v.w=u.w+w[i];
v.c=u.c;
if(w[i]>=l) ++v.c;
if(v.c>c) continue;
else if(dp[v.c][v.w%w[1]]>v.w){
dp[v.c][v.w%w[1]]=v.w;
if(!inQ[v.c][v.w%w[1]]){
que.push(v);
inQ[v.c][v.w%w[1]]=true;
}
}
}
}
for(int i=1;i<=c;++i){
for(int j=0;j<w[1];++j)
dp[i][j]=min(dp[i][j],dp[i-1][j]);
}
}
inline bool jud(long long v){return dp[c][v%w[1]]<=v;}
}
int main(){
freopen("bag.in","r",stdin);
freopen("bag.out","w",stdout);
int m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%lld",&w[i]);
scanf("%d%d",&l,&c);
sort(w+1,w+n+1);
bool (*jud)(long long);
if(w[1]>=l){
solve1::DP();
jud=solve1::jud;
}
else{
solve2::DP();
jud=solve2::jud;
}
long long v;
for(int i=1;i<=m;++i){
scanf("%lld",&v);
if(jud(v)) puts("Yes");
else puts("No");
}
return 0;
}
考试时直接写了个树剖。。。
#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
string in=file+".in",out=file+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
int pm=1; char c;
do{
c=getchar();
if(c=='-') pm=-1;
}while(!isdigit(c));
x=c^'0';
while(c=getchar(),isdigit(c))
x=x*10+(c^'0');
x*=pm;
}
template<typename type>
void write(type x,char c=0){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10|'0');
if(c) putchar(c);
}
#include <algorithm>
using std::max;
const int MAXN=100005;
int n;
class segT{
private:
struct node{int ls,rs,l,r,max;}d[MAXN<<2];
int new_nd(){
static int cnt=1;
return ++cnt;
}
void push_d(int u){
int ls=d[u].ls,rs=d[u].rs;
int &tag=d[u].max;
d[ls].max=max(d[ls].max,tag);
d[rs].max=max(d[rs].max,tag);
}
void mdf(int u,int lp,int rp,int x){
if(lp<=d[u].l && d[u].r<=rp){
d[u].max=max(d[u].max,x);
return;
}
push_d(u);
int mid=d[u].l+d[u].r>>1;
if(lp<=mid) mdf(d[u].ls,lp,rp,x);
if(rp>mid) mdf(d[u].rs,lp,rp,x);
}
int qry(int u,int pos){
if(d[u].l==d[u].r) return d[u].max;
push_d(u);
int mid=d[u].l+d[u].r>>1;
if(pos<=mid) return qry(d[u].ls,pos);
else return qry(d[u].rs,pos);
}
void build(int u,int l,int r){
d[u].max=-1;
d[u].l=l,d[u].r=r;
if(l==r) return;
int mid=l+r>>1;
d[u].ls=new_nd();
build(d[u].ls,l,mid);
d[u].rs=new_nd();
build(d[u].rs,mid+1,r);
}
public:
void build(){build(1,1,n);}
void mdf(int lp,int rp,int x){
if(lp>rp) return;
mdf(1,lp,rp,x);
}
int qry(int pos){return qry(1,pos);}
};
class TP{
private:
struct node{
int w,he,fa,top,id,sz,hson,lpos;
bool blk,mdf;
}d[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
segT T;
void addE(int u,int v){
static int cnt;
ed[++cnt]=(line){v,d[u].he};
d[u].he=cnt;
}
void DFS(int u,int fa){
d[u].sz=1;
for(int i=d[u].he,v,&hson=d[u].hson;i;i=ed[i].nex){
v=ed[i].to;
if(v!=fa){
d[v].fa=u;
DFS(v,u);
d[u].sz+=d[v].sz;
if(d[v].sz>d[hson].sz) hson=v;
}
}
}
void link(int u,int fa){
static int cnt;
d[u].id=++cnt;
d[u].top= d[fa].hson==u ? d[fa].top:u;
int hson=d[u].hson;
if(hson) link(hson,u);
for(int i=d[u].he,v;i;i=ed[i].nex){
v=ed[i].to;
if(v!=fa && v!=hson) link(v,u);
}
d[u].lpos=cnt;
}
public:
void init(){
for(int i=1;i<=n;++i)
read(d[i].w);
for(int i=1,u,v;i<n;++i){
read(u),read(v);
addE(u,v),addE(v,u);
}
}
void build(){
DFS(1,0);
link(1,0);
T.build();
}
void mdf(int u){
if(d[u].blk) return;
T.mdf(d[u].id,d[u].lpos,d[u].w);
d[u].blk=true;
int fa;
while(d[u].fa){
fa=d[u].fa;
T.mdf(d[fa].id,d[u].id-1,d[fa].w);
T.mdf(d[u].lpos+1,d[fa].lpos,d[fa].w);
if(d[fa].mdf) break;
d[fa].mdf=true;
u=fa;
}
}
int qry(int u){return T.qry(d[u].id);}
}T;
int main(){
setIO("lca");
int m;
read(n),read(m);
T.init();
T.build();
char cmd[10];
for(int i=1,v;i<=m;++i){
scanf("%s%d",cmd,&v);
if(cmd[0]=='Q') write(T.qry(v),'\n');
else T.mdf(v);
}
return 0;
}