为什么HN今年风格也这么诡异呀。
先给个Achen的题解链接：http://www.cnblogs.com/Achenchen/p/8921650.html，我的题解太简略了。
D1T1
我觉得这是一道很有趣的题呀
如果第i个数之前的运算符是and，则这一位设为1，否则为0，得到的二进制数记为xx。
对每一位分别考虑，对于第i位，如果第j个数是1，那么这一位设为1，否则为0，得到的二进制数记为$b_i$。
以左边为最低位，按前缀归纳容易证明，第i位的结果为1，当且仅当$x < b_i$
我们将b从大到小排序，结果设为c，那么答案不为零仅当在c的顺序下，r中没有任何0在1的前面。
找到r中第一个0的位置，假设是k，那么解x要满足$c_k≤x<c_{k–1}$，于是答案是$c_{k – 1} – c_k$
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=5000+7;
const ll mod=1e9+7;
int n,m,q,p[maxn],id[maxn];
ll mi[maxn],num[maxn];
bool G[maxn][maxn];
char cc; ll ff;
template<typename T>void read(T& aa) {
aa=0;cc=getchar();ff=1;
while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
if(cc=='-') ff=-1,cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
aa*=ff;
}
bool cmp(const int a,const int b) {
Rep(i,n,1) {
if(G[a][i]<G[b][i]) return 1;
if(G[a][i]>G[b][i]) return 0;
}
}
int main() {
freopen("hunt.in","r",stdin);
freopen("hunt.out","w",stdout);
read(n); read(m); read(q);
int x;
mi[0]=1;
For(i,1,n) {
mi[i]=mi[i-1]*2%mod;
For(j,1,m) {
scanf("%1d",&x);
if(x==1) {
G[j][i]=1;
num[j]=(num[j]+mi[i-1])%mod;
}
}
}
For(i,1,m) p[i]=i;
sort(p+1,p+m+1,cmp);
For(i,1,m) id[p[i]]=i;
p[m+1]=m+1; num[m+1]=mi[n];
int l,r;
For(i,1,q) {
l=0; r=m+1;
For(j,1,m) {
scanf("%1d",&x);
if(x==1) r=min(r,id[j]);
else l=max(l,id[j]);
}
if(l>r) printf("0
");
else printf("%lld
",(num[p[r]]-num[p[l]]+mod)%mod);
}
return 0;
}
D1T2
场上我一直在想，把环剖成链，倍长，线段树上第i个位置维护$T_i + 2 imes n - i$
于是我死在不知道怎么维护线段树上了，因为我假设$i$是最后取的点，那么我需要$i-n+1$到$i$的最大值。
但是如果在线段树上第$i$个位置维护$p_i =T_i - i$，那么对于一个位置$i$，假设$i$是第一个取的点，那么我们需要$i+1$到$2 imes n$的最大值就可以了。
对于线段树上的一个点所对应区间[l,r]，我们维护一个$p_i$的最大值和$min limits_{i in [l,mid]}{i+ max limits_{i le j le r}p_j}$
维护的方法和bzoj2957楼房重建这道题一样。
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=2e5+7,INF=1e8;
int n,m,O,a[maxn],lastans;
char cc; ll ff;
template<typename T>void read(T& aa) {
aa=0;cc=getchar();ff=1;
while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
if(cc=='-') ff=-1,cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
aa*=ff;
}
int maxnum[4*maxn],p[4*maxn],qpos,qx;
int find(int pos,int l,int r,int x) {
if(x>=maxnum[pos]) return x+l+n;
if(l==r) return p[pos];
int mid=(l+r)>>1,rs=INF;
rs=min(rs,find(pos<<1|1,mid+1,r,x));
if(x>maxnum[pos<<1|1]) rs=min(rs,find(pos<<1,l,mid,x));
else rs=min(rs,p[pos<<1]);
return rs;
}
void bld(int pos,int l,int r) {
if(l==r) {
p[pos]=a[l]+l+n;
maxnum[pos]=a[l];
return;
}
int mid=(l+r)>>1;
bld(pos<<1,l,mid);
bld(pos<<1|1,mid+1,r);
maxnum[pos]=max(maxnum[pos<<1],maxnum[pos<<1|1]);
p[pos]=min(p[pos<<1|1],lastans=p[pos<<1]=find(pos<<1,l,mid,maxnum[pos<<1|1]));
}
void chge(int pos,int l,int r) {
if(l==r) {
p[pos]=qx+l+n;
maxnum[pos]=qx;
return;
}
int mid=(l+r)>>1;
if(qpos<=mid) chge(pos<<1,l,mid);
else chge(pos<<1|1,mid+1,r);
maxnum[pos]=max(maxnum[pos<<1],maxnum[pos<<1|1]);
p[pos]=min(p[pos<<1|1],lastans=p[pos<<1]=find(pos<<1,l,mid,maxnum[pos<<1|1]));
}
int main() {
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
read(n); read(m); read(O);
For(i,1,n) {
read(a[i]);
a[i+n]=a[i];
a[i]-=i;
a[i+n]-=i+n;
}
bld(1,1,2*n);
int x,y;
printf("%d
",--lastans);
For(i,1,m) {
read(x); read(y);
if(O) x^=lastans,y^=lastans;
qpos=x; qx=y-x;
chge(1,1,2*n);
qpos=x+n; qx=y-x-n;
chge(1,1,2*n);
printf("%d
",--lastans);
}
return 0;
}
D1T3
对于非树边的那些边所连的点，建虚树。
如果我们把在虚树里面的点叫关键点，我们对每个关键点预处理g[i][0/1][0/1]表示从他到他虚树上的父亲的转移贡献。初始g[i][0][0]=g[i][1][1]=1
对于每个点预处理p[i][0/1]表示没有关键点的子树的贡献。
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=2e5+7;
const ll mod=998244353;
ll n,m,f[maxn],ct[maxn],g[maxn][2][2],p[maxn][2],dp[maxn][2],ans;
int id[maxn],sum,ok[maxn];
char cc; ll ff;
template<typename T>void read(T& aa) {
aa=0;cc=getchar();ff=1;
while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
if(cc=='-') ff=-1,cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
aa*=ff;
}
int find(int x){return f[x]==x? x:f[x]=find(f[x]);}
int fir[maxn],nxt[2*maxn],to[2*maxn],e=0;
void add(int x,int y) {
to[++e]=y;nxt[e]=fir[x];fir[x]=e;
to[++e]=x;nxt[e]=fir[y];fir[y]=e;
}
int FIR[maxn],NXT[2*maxn],TO[2*maxn],E=0;
void ADD(int x,int y) {
// printf("ADD: %d -> %d
",x,y);
TO[++E]=y;NXT[E]=FIR[x];FIR[x]=E;
}
struct HC{
int x,y;
HC(int x=0.,int y=0.):x(x),y(y){}
}hc[maxn];
int tothc;
void s(int pos,int f) {
int y,z,t,o=0;
p[pos][0]=p[pos][1]=1;
for(y=fir[pos];y;y=nxt[y]) {
if((z=to[y])==f) continue;
s(z,pos);
if(ct[z]) ++o;
else {
p[pos][0]=p[pos][0]*(p[z][0]+p[z][1])%mod;
p[pos][1]=p[pos][1]*p[z][0]%mod;
}
}
g[pos][0][0]=g[pos][1][1]=1;
if(o>1) ct[pos]=pos;
ll x00,x01,x10,x11;
for(y=fir[pos];y;y=nxt[y]) {
if((z=to[y])==f) continue;
if((t=ct[z])!=0) {
x00=g[t][0][0]; x01=g[t][0][1]; x10=g[t][1][0]; x11=g[t][1][1];
if(ct[pos]) {
ADD(pos,ct[z]);
g[t][0][0]=(x00+x01)%mod; g[t][0][1]=x00;
g[t][1][0]=(x10+x11)%mod; g[t][1][1]=x10;
}
else {
g[t][0][0]=(x00+x01)*p[pos][0]%mod;
g[t][0][1]=x00*p[pos][1]%mod;
g[t][1][0]=(x10+x11)*p[pos][0]%mod;
g[t][1][1]=x10*p[pos][1]%mod;
}
}
}
for(y=fir[pos];y&&!ct[pos];y=nxt[y]) {
if((z=to[y])==f) continue;
ct[pos]=ct[z];
}
}
void DP(int pos) {
int y,z;
if(ok[pos]!=2) dp[pos][0]=p[pos][0]; else dp[pos][0]=0;
if(ok[pos]!=1) dp[pos][1]=p[pos][1]; else dp[pos][1]=0;
for(y=FIR[pos];y;y=NXT[y]) {
DP(z=TO[y]);
dp[pos][0]=dp[pos][0]*(dp[z][0]*g[z][0][0]%mod+dp[z][1]*g[z][1][0]%mod)%mod;
dp[pos][1]=dp[pos][1]*(dp[z][0]*g[z][0][1]%mod+dp[z][1]*g[z][1][1]%mod)%mod;
}
}
ll get_dp() {
// printf("get_dp:
");
// For(i,1,n) printf("%d ",ok[i]);
// printf("
");
DP(1);
// For(i,1,n) printf("(%lld,%lld) , ",dp[i][0],dp[i][1]);
// printf("
");
// printf("%lld
",dp[1][0]+dp[1][1]);
return dp[1][0]+dp[1][1];
}
int bel[maxn];
void dfs(int pos) {
if(pos>sum) {
ans=(ans+get_dp())%mod;
return;
}
if(ok[id[pos]]) dfs(pos+1);
else {
ok[id[pos]]=1; dfs(pos+1);//not choose
ok[id[pos]]=2;
For(i,1,tothc) {
if(hc[i].x==id[pos]&&(!ok[hc[i].y])) ok[hc[i].y]=1,bel[hc[i].y]=pos;
if(hc[i].y==id[pos]&&(!ok[hc[i].x])) ok[hc[i].x]=1,bel[hc[i].x]=pos;
}
if(ok[id[pos]]==2) dfs(pos+1);
For(i,1,tothc) {
if(bel[hc[i].y]==pos) ok[hc[i].y]=0;
if(bel[hc[i].x]==pos) ok[hc[i].x]=0;
}
ok[id[pos]]=0;
}
}
int main() {
freopen("duliu.in","r",stdin);
freopen("duliu.out","w",stdout);
int x,y;
read(n); read(m);
For(i,1,n) f[i]=i;
For(i,1,m) {
read(x); read(y);
if(find(x)!=find(y)) {
add(x,y);
f[find(x)]=find(y);
}
else {
hc[++tothc]=HC(x,y);
ct[x]=x; ct[y]=y;
}
}
For(i,1,n) if(ct[i]) id[++sum]=i;
ct[1]=1;
s(1,0);
dfs(1);
printf("%lld
",ans);
return 0;
}
D2T1
这是啥子题哟，骗分？
把带锁的门看作有向边，其他部分可以缩点，然后可以按照拓扑序做。
场上写了一个带log的st表二分，后来证明了一下复杂度。
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=1e6+7,maxt=23,W=20,INF=0x3f3f3f3f;
int n,m,Q,a[maxn],last[maxn],next[maxn],st[maxn][maxt];
int ld[maxn],rd[maxn];
char cc; ll ff;
template<typename T>void read(T& aa) {
aa=0;cc=getchar();ff=1;
while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
if(cc=='-') ff=-1,cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
aa*=ff;
}
int get_rch(int p,int rs) {
Rep(i,W,0) if(st[rs][i]>=p) rs+=(1<<i);
return rs;
}
int main() {
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
read(n); read(m); read(Q);
int x,y;
For(i,1,m) {
read(x); read(y);
a[x]=y;
}
For(i,1,n) if(!a[i]) a[i]=INF;
x=1;
For(i,1,n) {
last[i]=x;
if(a[i]!=INF&&a[i]<=i) x=i+1;
}
x=n;
Rep(i,n,1) {
next[i]=x;
if(a[i-1]!=INF&&a[i-1]>=i) x=i-1;
}
For(i,1,n) st[i][0]=a[i];
For(r,1,W) For(i,1,n-(1<<r)+1)
st[i][r]=min(st[i][r-1],st[i+(1<<r-1)][r-1]);
For(i,1,n) {
ld[i]=rd[i]=i;
if(a[i-1]==INF) { //both side road
ld[i]=ld[i-1];
rd[i]=rd[i-1];
continue;
}
rd[i]=min(next[i],get_rch(i,i));//ef
if(last[i]==i||rd[i]<a[i-1]) continue;//cannot reach i-1
while(ld[i]>last[i]||rd[i]<next[i]) {
if(ld[i]>last[i]&&a[ld[i]-1]<=rd[i]) ld[i]=ld[ld[i]-1];
else if(rd[i]<next[i]&&a[rd[i]]>=ld[i]) //include a[rd[i]]==INF
rd[i]=min(next[i],get_rch(ld[i],rd[i]+1));
else break;
}
}
For(i,1,Q) {
read(x); read(y);
if(y>=ld[x]&&y<=rd[x]) printf("YES
");
else printf("NO
");
}
// cerr<<clock()<<"
";
return 0;
}
D2T2
明显先建树，然后直接根据平均数贪心跟父亲合并，用STL里面的set或者priority_queue。发现priority_queue的push快，但是pop慢。
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
#define ll long long
#define db long double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=1e6+7;
const db eps=1e-7;
ll n,fa[maxn],w[maxn],root;db sum[maxn],p[maxn];
int R[maxn],NXT[maxn];
char cc; ll ff;
template<typename T>void read(T& aa) {
aa=0;cc=getchar();ff=1;
while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
if(cc=='-') ff=-1,cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
aa*=ff;
}
int dcmp(db x) {return fabs(x)<eps? 0:(x>0? 1:-1);}
int f[maxn];
int find(int x){return x==f[x]? x:f[x]=find(f[x]);}
int fir[maxn],nxt[maxn],to[maxn],e=0;
void add(int x,int y) {
to[++e]=y;nxt[e]=fir[x];fir[x]=e;
}
bool vis[maxn];
inline bool s(int pos) {
if(vis[pos]) return 1;
vis[pos]=1;
for(int y=fir[pos];y;y=nxt[y])
if(s(to[y])) return 1;
return 0;
}
struct Node{
int pos;db w;
Node(int pos,db w):pos(pos),w(w){}
bool operator < (const Node& b) const{return w<b.w;}
};
multiset<Node>G;
multiset<Node>::iterator it;
ll solve() {
if(s(0)) return -1;
For(i,1,n) if(!vis[i]) return -1;
For(i,1,n) G.insert(Node(i,sum[i]=w[i]));
int x,y;db now;
For(i,1,n) {
do {
it=G.begin();
x=it->pos; now=it->w;
G.erase(it);
}while(find(x)!=x||dcmp(now-sum[x]/p[x]));//
y=find(fa[x]);
sum[y]+=sum[x];
p[y]+=p[x];
f[x]=y;
NXT[R[y]]=x; R[y]=R[x];
if(y) G.insert(Node(y,sum[y]/p[y]));
}
// cerr<<clock()<<"
";
int pos=0; ll rs=0;
For(i,1,n) {
pos=NXT[pos];
rs+=w[pos]*(ll)i;
}
return rs;
}
int main() {
freopen("perm.in","r",stdin);
freopen("perm.out","w",stdout);
read(n);
For(i,1,n) p[i]=1,f[i]=R[i]=i;
For(i,1,n) read(fa[i]),add(fa[i],i);
For(i,1,n) read(w[i]);
printf("%lld
",solve());
return 0;
}
D2T3
dp水题，但是要爆int/卡空间
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define lc son[pos][0]
#define rc son[pos][1]
const int maxn=40000+3,maxt=41;
ll n,A[maxn],B[maxn],C[maxn],son[maxn][2];
map<int,ll>dp[maxn];
char cc; ll ff;
template<typename T>void read(T& aa) {
aa=0;cc=getchar();ff=1;
while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
if(cc=='-') ff=-1,cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
aa*=ff;
}
int T(int x,int y) {return x*100+y;}
void s(int pos,int l1,int l2) {
if(pos>=n) {
For(i,0,l1) For(j,0,l2) dp[pos][T(i,j)]=C[pos]*(A[pos]+i)*(B[pos]+j);
return;
}
s(lc,l1+1,l2); s(rc,l1,l2+1);
For(i,0,l1) For(j,0,l2)
dp[pos][T(i,j)]=
min(dp[lc][T(i,j)] + dp[rc][T(i,j+1)],
dp[lc][T(i+1,j)]+ dp[rc][T(i,j)]);
}
int main() {
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
read(n); int x,y;
For(i,1,n-1) {
read(x); read(y);
if(x<0) x=n-1-x;
if(y<0) y=n-1-y;
son[i][0]=x; son[i][1]=y;
}
For(i,1,n) {
read(A[i+n-1]);
read(B[i+n-1]);
read(C[i+n-1]);
}
s(1,0,0);
printf("%lld
",dp[1][0]);
return 0;
}