NOIP2018训练题集
1. CZday3C
给定有m个数的集合，从其中任选一个子集满足全部&后不为零，问方案数。
考虑对二进制位容斥，问题转化为求包含某个二进制位集合的数的个数，通过类似FMT的DP求解。
#include<bits/stdc++.h>
#define mo 1000000007
#define ll long long
using namespace std;
ll m,n,k,f[],g[],x,ans;
ll po(ll x,ll y){ll z=;while (y){if (y%==)z=(x*z)%mo;x=(x*x)%mo;y/=;}return z;}
int main(){
freopen("loneliness.in","r",stdin);
freopen("loneliness.out","w",stdout);
cin>>n;
cin>>n>>m>>k;
for (int i=;i<=m;i++){scanf("%d",&x);g[x]++;}
f[]=-;
for (int i=;i<(<<n);i++)
for (int j=;j<(<<n);j*=)
if ((i&j)==)f[i+j]=f[i]*(-);
for (int i=;i<(<<n);i*=)
for (int j=;j<(<<n);j++)
if ((i&j)!=) g[j-i]+=g[j];
for (int i=;i<(<<n);i++)ans=(ans+f[i]*po(g[i],k)+mo)%mo;
cout<<ans<<endl;
return ;
}
2.CZday6C
在线修改，查询第一个比前面所有数之和大的数。
类似FRBSUM，如果一个数不是答案，则下一个答案必然不小于从头一直加到这个数的和，这样倍增查询每次至少翻倍，线段树支持即可。
#include<bits/stdc++.h>
#define maxn 200010
#define N 800010
#define ll long long
using namespace std;
int value[maxn], mx[N];
ll sum[N];
void build(int now, int l, int r)
{
if (l == r)
{
mx[now] = sum[now] = value[l];
return;
}
int mid = (l + r) / ;
build(now * , l, mid);
build(now * + , mid + , r);
mx[now] = max(mx[now * ], mx[now * + ]);
sum[now] = sum[now * ] + sum[now * + ];
}
void modify(int now, int l, int r, int x, int y)
{
if (l == r)
{
mx[now] = sum[now] = value[l];
return;
}
int mid = (l + r) / ;
if (x <= mid) modify(now * , l, mid, x, y);
else modify(now * + , mid + , r, x, y);
mx[now] = max(mx[now * ], mx[now * + ]);
sum[now] = sum[now * ] + sum[now * + ];
}
ll query_sum(int now, int l, int r, int left, int right)
{
if (l == left && r == right) return sum[now];
int mid = (l + r) / ; ll ans = ;
if (left <= mid) ans = query_sum(now * , l, mid, left, min(right, mid));
if (right >= mid + ) ans += query_sum(now * + , mid + , r, max(left, mid + ), right);
return ans;
}
int query(int now, int l, int r, int left, int right, ll x)
{
int mid = (l + r) / ;
if (l == left && r == right)
{
if (mx[now] < x) return -;
if (l == r) return l;
if (mx[now * ] >= x) return query(now * , l, mid, l, mid, x);
else return query(now * + , mid + , r, mid + , r, x);
}
int ans = -;
if (left <= mid) ans = query(now * , l, mid, left, min(right, mid), x);
if (ans != -) return ans;
else return query(now * + , mid + , r, max(left, mid + ), right, x);
}
int main()
{
freopen("challenge.in", "r", stdin);
freopen("challenge.out", "w", stdout);
int n, q;
scanf("%d%d", &n, &q);
for (int i = ; i <= n; i++)
scanf("%d", &value[i]);
build(, , n);
for (int i = ; i <= q; i++)
{
int x, y;
scanf("%d%d", &x, &y);
value[x] = y;
modify(, , n, x, y);
int cur = , res = -; ll pre = ;
while (cur < n)
{
int tmp = query(, , n, cur + , n, pre);
if (tmp == -) break;
cur = tmp; pre = query_sum(, , n, , tmp);
if (pre - value[cur] == value[cur]) {res = tmp; break;}
}
printf("%d\n", res);
}
return ;
}
3.ACday3C
n个数，m个等级(m<=10)，某个数不小于某值ai就是i级。在线区间加，单点修改，询问区间所有数等级和。
线段树，Min[x]表示这个区间中最小的离下一级的距离。更新时如果Min[x]>0则退出，否则递归下去。均摊复杂度nmlogn。类似区间开方之类的线段树均摊操作。
#include<cstdio>
#include<algorithm>
#define ls (x<<1)
#define rs (ls|1)
#define lson ls,L,mid
#define rson rs,mid+1,R
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=;
int n,m,Q,op,x,y,k,a[],c[N],sm[N],mn[N],tag[N]; int chk(int v){ for (int i=m; ~i; i--) if (v>=a[i]) return i; return ; }
void upd(int x){ sm[x]=sm[ls]+sm[rs]; mn[x]=min(mn[ls],mn[rs]); } void push(int x){
if (!tag[x]) return;
mn[ls]+=tag[x]; tag[ls]+=tag[x];
mn[rs]+=tag[x]; tag[rs]+=tag[x];
tag[x]=;
} void build(int x,int L,int R){
if (L==R){ sm[x]=chk(c[L]); mn[x]=a[sm[x]+]-c[L]; return; }
int mid=(L+R)>>;
build(lson); build(rson); upd(x);
} void work(int x,int L,int R){
if (mn[x]>) return;
if (L==R){
while (mn[x]<=) sm[x]++,mn[x]=a[sm[x]+]-a[sm[x]]+mn[x];
return;
}
push(x); int mid=(L+R)>>;
work(lson); work(rson); upd(x);
} void add(int x,int L,int R,int l,int r,int k){
if (L==l && r==R){ mn[x]-=k; tag[x]-=k; work(x,L,R); return; }
push(x); int mid=(L+R)>>;
if (r<=mid) add(lson,l,r,k);
else if (l>mid) add(rson,l,r,k);
else add(lson,l,mid,k),add(rson,mid+,r,k);
upd(x);
} void mdf(int x,int L,int R,int pos,int k){
if (L==R){ sm[x]=chk(k); mn[x]=a[sm[x]+]-k; return; }
push(x); int mid=(L+R)>>;
if (pos<=mid) mdf(lson,pos,k); else mdf(rson,pos,k);
upd(x);
} int que(int x,int L,int R,int l,int r){
if (L==l && r==R) return sm[x];
push(x); int mid=(L+R)>>;
if (r<=mid) return que(lson,l,r);
else if (l>mid) return que(rson,l,r);
else return que(lson,l,mid)+que(rson,mid+,r);
} int main(){
scanf("%d%d%d",&n,&m,&Q);
rep(i,,m) scanf("%d",&a[i]);
a[]=-2e9; a[m+]=2e9;
rep(i,,n) scanf("%d",&c[i]);
build(,,n);
while (Q--){
scanf("%d%d%d",&op,&x,&y);
if (op==) scanf("%d",&k),add(,,n,x,y,k);
else if (op==) mdf(,,n,x,y);
else printf("%d\n",que(,,n,x,y));
}
return ;
}
4.ACday4C
一棵树和一些边，在线询问只取[L,R]中的边时，S到T的边权异或和最小的路径。
非常好的一道题，发现一条边的贡献一定是和树边组成的环的异或和，线性基加优化求解。
http://noi.ac/contest/13/problem/41
https://www.cnblogs.com/Gloid/p/9658421.html
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define For(i,x) for (int i=h[x],k; i; i=nxt[i])
using namespace std; const int N=;
struct Que{ int id,s,l,r; }q[N],q1[N];
int n,m,Q,u,v,w,S,T,l,r,cnt,dep[N],d[N],ans[N],h[N],to[N<<],val[N<<],nxt[N<<];
void add(int u,int v,int w){ to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; } struct B{
int d[];
B (){ memset(d,,sizeof(d)); }
void ins(int x){
for (int i=; ~i; i--)
if (x&(<<i)){
if (!d[i]) { d[i]=x; break; } else x^=d[i];
}
}
}suf[N],pre[N]; B operator +(const B &a,const B &b){
B c;
for (int i=; ~i; i--) c.d[i]=a.d[i];
rep(i,,) if (b.d[i]) c.ins(b.d[i]);
return c;
} void dfs(int x,int fa){
For(i,x) if ((k=to[i])!=fa) dep[k]=dep[x]^val[i],dfs(k,x);
} int work(int x,const B &a){ for (int i=; ~i; i--) x=min(x,x^a.d[i]); return x; } void solve(int l,int r,int low,int high){
if (l>r || low>high) return;
if (low==high){ rep(i,l,r) ans[q[i].id]=min(q[i].s,q[i].s^d[low]); return; }
int mid=(low+high)>>,st=l-,ed=r+;
for (int i=mid; i>=low; i--){
if (i==mid) pre[i]=pre[]; else pre[i]=pre[i+];
pre[i].ins(d[i]);
}
rep(i,mid,high){
if (i==mid+) suf[i]=suf[]; else suf[i]=suf[i-];
suf[i].ins(d[i]);
}
rep(i,l,r)
if (q[i].l<=mid && q[i].r>mid) ans[q[i].id]=work(q[i].s,pre[q[i].l]+suf[q[i].r]);
else if (q[i].r<=mid) q1[++st]=q[i]; else q1[--ed]=q[i];
rep(i,l,r) q[i]=q1[i];
solve(l,st,low,mid); solve(ed,r,mid+,high);
} int main(){
scanf("%d%d%d",&n,&m,&Q);
rep(i,,n) scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
dfs(,);
rep(i,,m) scanf("%d%d%d",&u,&v,&w),d[i]=dep[u]^dep[v]^w;
rep(i,,Q) scanf("%d%d%d%d",&S,&T,&l,&r),q[i]=(Que){i,dep[S]^dep[T],l,r};
solve(,Q,,m);
rep(i,,Q) printf("%d\n",ans[i]);
return ;
}
5.NOWday1C
一棵树一些路径，每次询问一个点vi的最远祖先u，满足uv之间的路径被至少ki条路径完全包含。
可以DFS化成二维数点问题主席树和倍增解决，也可以每个点记录子树内最远的一个是某个路径拐点(LCA)的祖先，线段树合并即可。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson ls[x],L,mid
#define rson rs[x],mid+1,R
#define rep(i,l,r) for (int i=l; i<=r; i++)
#define For(i,x) for (int i=h[x],k; i; i=nxt[i])
typedef long long ll;
using namespace std; const int N=;
int n,m,u,v,k,l,cnt,nd,Q,rt[N],fa[N][],dep[N];
int h[N],nxt[N<<],to[N<<],sz[N*],ls[N*],rs[N*];
void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } void dfs(int x){
dep[x]=dep[fa[x][]]+;
rep(i,,) fa[x][i]=fa[fa[x][i-]][i-];
For(i,x) if ((k=to[i])!=fa[x][]) fa[k][]=x,dfs(k);
} int lca(int u,int v){
if (dep[u]<dep[v]) swap(u,v);
int t=dep[u]-dep[v];
for (int i=; ~i; i--) if (t&(<<i)) u=fa[u][i];
if (u==v) return u;
for (int i=; ~i; i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][];
} void ins(int &x,int L,int R,int k){
if (!x) x=++nd; sz[x]++;
if (L==R) return;
int mid=(L+R)>>;
if (k<=mid) ins(lson,k); else ins(rson,k);
} int merge(int x,int y){
if (!x || !y) return x+y;
int p=++nd; sz[p]=sz[x]+sz[y];
ls[p]=merge(ls[x],ls[y]); rs[p]=merge(rs[x],rs[y]);
return p;
} void dfs2(int x){
For(i,x) if ((k=to[i])!=fa[x][]) dfs2(k),rt[x]=merge(rt[x],rt[k]);
} int que(int x,int L,int R,int k){
if (L==R) return L;
int mid=(L+R)>>;
if (k<=sz[ls[x]]) return que(lson,k); else return que(rson,k-sz[ls[x]]);
} int main(){
scanf("%d%d",&n,&m);
rep(i,,n) scanf("%d%d",&u,&v),add(u,v),add(v,u);
dfs();
rep(i,,m) scanf("%d%d",&u,&v),l=lca(u,v),ins(rt[v],,n,dep[l]),ins(rt[u],,n,dep[l]);
dfs2();
for (scanf("%d",&Q); Q--; ) scanf("%d%d",&v,&k),printf("%d\n",max(dep[v]-que(rt[v],,n,k),));
return ;
}
6.NOWday2B
给换上每个位置i一个[1,ai]中的整数，任意两个相邻位置数不相同，求方案数。
考虑容斥，到位置i时，枚举i与i-1,...,i-k+1都相等，转移为$f_i=\sum\limits_{j} f_j\times min(a_{j+1..i})\times (-1)^{i-j-1}$
单调队列优化，这里也比较巧妙，具体看代码。
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std; const int N=2e6+,mod=1e9+;
ll n,a[N],stk[N][],f[N],ans,tmp,mn; int main(){
scanf("%lld",&n); a[]=1e9+;
rep(i,,n){
scanf("%lld",&a[i]);a[i+n]=a[i];
if(a[i]<a[mn])mn=i;
}
rep(i,,n) a[i]=a[i+mn-];
f[]=n&?-:; int t=;
stk[][]=1e9+; stk[][]=f[];
rep(i,,n){
int sum=;
while(t&&a[i]<stk[t][])sum=(sum+stk[t--][])%mod;
f[i]=((f[i]-stk[t][]-1ll*sum*a[i]%mod)%mod+mod)%mod;
stk[++t][]=a[i];
stk[t][]=sum;
stk[t][]=(1ll*sum*a[i]+stk[t-][])%mod;
stk[++t][]=1e9+;
stk[t][]=f[i];
ans=(ans+f[i])%mod;
}
ans=(ans+(n&?-a[]:a[]))%mod;
printf("%lld",ans);
return ;
}
7.ACday5B
长度为n的序列A,从中删去恰好k个元素（右边的元素往左边移动），记cnt为新序列中Ai=i的元素个数（即权值与下标相同的元素的个数）。求cnt的最大值。
f[i]表示以i结尾的序列的最优答案，则有f[i]=max{f[j]+1} (i-j>=a[i]-a[j],a[i]>a[j])。
考虑按a从小到大的顺序DP，直接树状数组维护即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=;
int n,k,ans,f[N],a[N],c[N];
pair<int,int>b[N]; void add(int x,int d){ x++; for (; x<=n; x+=x&-x) c[x]=max(c[x],d); }
int que(int x){ x++; int res=; for (; x; x-=x&-x) res=max(res,c[x]); return res; } void work(int x){
if (a[x]>x) return;
f[x]=que(x-a[x])+; add(x-a[x],f[x]);
if (a[x]>=x-k && a[x]<=n-k) ans=max(ans,f[x]);
} int main(){
freopen("delete.in","r",stdin);
freopen("delete.out","w",stdout);
scanf("%d%d",&n,&k);
rep(i,,n) scanf("%d",&a[i]),b[i]=make_pair(a[i],-i);
sort(b+,b+n+);
rep(i,,n) work(-b[i].second);
printf("%d\n",ans);
return ;
}
8.ACday5C
一棵树，选定一个大小为k的连通块，将连通块中所有点编号拿出排序，最大化最长的连续自然数段的长度。
two pointers枚举所有相邻几个自然数，问题转化为求包含这些点的最小连通块大小。
这实际上就是求每个点到所有点的LCA的链并，也就是每两个DFS序相邻的点的路径长度和，用经典的DFS序+set维护。
#include<set>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std;
typedef set<int>::iterator It; const int N=;
set<int>S;
int n,k,u,v,sm,cnt,tot,dep[N],dfn[N],b[N],fa[N][],h[N],nxt[N<<],to[N<<]; void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } void dfs(int x){
dfn[x]=++tot; b[tot]=x;
rep(i,,) fa[x][i]=fa[fa[x][i-]][i-];
for (int i=h[x],k; i; i=nxt[i])
if ((k=to[i])!=fa[x][]) fa[k][]=x,dep[k]=dep[x]+,dfs(k);
} int lca(int u,int v){
if (dep[u]<dep[v]) swap(u,v);
int t=dep[u]-dep[v];
for (int i=; ~i; i--) if (t&(<<i)) u=fa[u][i];
if (u==v) return u;
for (int i=; ~i; i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][];
} int dis(int u,int v){ return dep[u]+dep[v]-*dep[lca(u,v)]; } void ins(int u){
It it2=S.lower_bound(dfn[u]);
if (it2==S.end()) it2=S.begin();
It it1=it2;
if (it1==S.begin()) it1=S.end(),it1--; else it1--;
int x=b[*it1],y=b[*it2];
sm+=dis(x,u)+dis(u,y)-dis(x,y);
S.insert(dfn[u]);
} void era(int u){
It it=S.lower_bound(dfn[u]),it1=it;
if (it1==S.begin()) it1=S.end(),--it1; else --it1;
It it2=it; ++it2;
if (it2==S.end()) it2=S.begin();
int x=b[*it1],y=b[*it2];
sm-=dis(x,u)+dis(u,y)-dis(x,y); S.erase(dfn[u]);
} int main(){
freopen("power.in","r",stdin);
freopen("power.out","w",stdout);
scanf("%d%d",&n,&k);
rep(i,,n) scanf("%d%d",&u,&v),add(u,v),add(v,u);
dfs();
int st=,ans=; S.insert(dfn[]);
rep(i,,n){
ins(i);
if (sm/+>k) era(st++);
ans=max(ans,i-st+);
}
printf("%d\n",ans);
return ;
}
9.NOWday3A
n*m的矩阵，每个格子都有pij的概率为黑，每次矩形边界上的格子和所有与黑格子相邻的格子都会变黑，求每个格子期望在第几次变黑。
各个事件的独立性会影响概率方程的正确性，所以列的式子尽量不要包含别的概率。
一个思路是，由于最多会在max(n,m)次内变黑，所以求出每个格子在第i次变黑的概率即可。
但这样仍然不好求，考虑“每个格子至少i次才能变黑”的概率。
容易发现，“每个格子至少i次才能变黑”，当且仅当所有离它曼哈顿距离不超过i的格子全是白格子。
于是问题转化为求以每个格子为中心的菱形的概率积，直接求解即可。
最后期望就是“至少一次才能变黑的概率”+“至少两次”+“至少三次”+...
或者根据“至少”得到“恰好”，乘以曼哈顿距离为i+1的点不全为白点的概率即可。
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=,mod=1e9+;
int n,m,x,y,v[N][N],ans[N][N],f1[N][N],f2[N][N]; int ksm(int a,int b){
int res=;
for (; b; a=1ll*a*a%mod,b>>=)
if (b & ) res=1ll*res*a%mod;
return res;
} int main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d%d",&n,&m);
rep(i,,n) rep(j,,m)
scanf("%d%d",&x,&y),ans[i][j]=v[i][j]=1ll*x*ksm(y,mod-)%mod;
rep(j,,m){
rep(i,,n){
int s=v[i][j]; f1[i][]=v[i][j];
rep(k,,max(n,m)){
if (j-k< || j+k>m) break;
s=1ll*s*v[i][j-k]%mod*v[i][j+k]%mod;
f1[i][k]=1ll*f1[i-][k-]*s%mod;
}
}
for (int i=n; i; i--){
int s=v[i][j]; f2[i][]=v[i][j];
rep(k,,max(n,m)){
if (j-k< || j+k>m) break;
s=1ll*s*v[i][j-k]%mod*v[i][j+k]%mod;
f2[i][k]=1ll*f2[i+][k-]*s%mod;
}
}
rep(i,,n) rep(k,,max(n,m)){
if (j-k< || j+k>m) break;
ans[i][j]=(ans[i][j]+1ll*f1[i][k]*f2[i+][k-]%mod)%mod;
}
}
rep(i,,n){ rep(j,,m) printf("%d ",ans[i][j]); puts(""); }
return ;
}
10.NOWday3B
在一张有向无权图(n<=5000)上找到最小的交错环并输出（即环上的边的方向交错），可以有重点但不能有重边。
考虑拆点，每条边从u出点连向v入点，问题立刻转化为在无向（二分）图上找最小环，暴力从每个点开始BFS即可。
因为可以证明：如果一个无向图的平均度数至少是8,那么它一定包含一个环。所以bfs时只要搜索最多5000*8条边,一定会找到环并退出。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=,M=;
bool vis[N];
int n,m,u,v,q[N],cnt,res[N],Ans[N],h[N],to[M],nxt[M],fa[N]; void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }
void init(){ cnt=; memset(h,,sizeof(h)); } int main(){
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
scanf("%*d");
while (){
scanf("%d%d",&n,&m); init();
if (n==) break;
rep(i,,m) scanf("%d%d",&u,&v),add(u,v+n),add(v+n,u);
int ans=-;
rep(i,,n){
memset(vis,,sizeof(vis));
memset(fa,,sizeof(fa));
q[]=i; vis[i]=;
int tot=; bool flag=;
for (int st=,ed=; st<ed; ){
if (flag) break;
int x=q[++st];
for (int p=h[x],k; p; p=nxt[p]){
if (vis[k=to[p]] && k!=fa[x]){
while (x!=i) res[++tot]=x,x=fa[x];
res[++tot]=i; reverse(res+,res+tot+);
while (k!=i) res[++tot]=k,k=fa[k];
flag=; break;
}
if (!vis[k]) vis[k]=,fa[k]=x,q[++ed]=k;
}
}
if (tot && (ans==- || tot<ans)) ans=tot,swap(Ans,res);
}
printf("%d\n",ans);
if (ans==-) continue;
rep(i,,ans) printf("%d ",(Ans[i]-)%n+);
puts("");
}
return ;
}
11.NOWday3C
有一堆石子,先手可取任意数量的石子但是无法直接全部取走，此后每个人可取前一个人取走的k倍以内任意数量的石子(不能不取)，取走最后一个石子的赢，问先手是否必胜。
部分分：容易得到kn的DP算法，并发现k=2时所有必败态都在fibonacci数点上。
结论：若先手在n=n0时输，那么找到[n0/k,n0)中最小的m0使先手输，则先手在n=n0+m0时同样必败（而在(n0,n0+m0)中均必胜）。
由此可以直接找到所有必败点。
证明：若n在(n0,n0+m0)中，则先手将石子数变为n0即可。n=n0+m0时，先手无法取m0（太大），则后手可以取m0到必胜态。得证。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std; ll m,n,i,j,T,nw[]; int main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
for (scanf("%lld",&T); T--; ){
scanf("%lld%lld",&m,&n);
if(n<=m+){ puts("DOG"); continue; }
for (i=; i<=m+; ++i) nw[i]=i;
j=;
while (nw[i-]<n){
while ((nw[i-]-)/nw[j]>=m) ++j;
nw[i]=nw[i-]+nw[j]; ++i;
}
puts(nw[i-]==n?"DOG":"GOD");
}
return ;
}
12.ACday6B
四个梯子，n层每层只有一个梯子在这层有木块，问有多少种方案，满足存在一个梯子，任意两个有木块的层之间距离不超过d（第一块要小于等于d，最后一块要大于等于n-d）。(n<=1000,d<=30)
容易想到f[i][x][y][z][w]的DP，若一个梯子存在间隔超过d的层则直接记为d层，故状态数是nd^4的。
考虑去掉一维，对于当前正在考虑的这层所放的梯子，只需要管它是死是活即可。状态变为f[i][0/1][x][y][z]，DP之间的转移要考虑清楚。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=,mod=1e9+;
int n,h,f[][][N][N][N],u,ans; int cal(int x){ return min(x+,h); }
void inc(int &x,int y){ x+=y; if (x>=mod) x-=mod; } int main(){
freopen("ladder.in","r",stdin);
freopen("ladder.out","w",stdout);
scanf("%d%d",&n,&h); f[u=][][][][]=;
rep(p,,n){
u^=; memset(f[u],,sizeof(f[u]));
rep(i,,h) rep(j,,h) rep(k,,h){
int t=f[u^][][i][j][k];
inc(f[u][i<h][h][cal(j)][cal(k)],t);
inc(f[u][j<h][cal(i)][h][cal(k)],t);
inc(f[u][k<h][cal(i)][cal(j)][h],t);
inc(f[u][][cal(i)][cal(j)][cal(k)],t);
t=f[u^][][i][j][k];
inc(f[u][i<h][][cal(j)][cal(k)],t);
inc(f[u][j<h][cal(i)][][cal(k)],t);
inc(f[u][k<h][cal(i)][cal(j)][],t);
inc(f[u][][cal(i)][cal(j)][cal(k)],t);
}
}
rep(i,,h) rep(j,,h) rep(k,,h)
inc(ans,f[u][][i][j][k]),inc(ans,f[u][][i][j][k]);
inc(ans,mod-f[u][][h][h][h]);
printf("%lld\n",4ll*ans%mod);
return ;
}
13.NOWday5A
求x在[0,n]，y在[0,m]且(x^y)%m=0的(x,y)个数，n,m<=1e18。
见代码。
ll solve(ll a,ll b){
ll ans=; a++; b++;
rep(i,,) if (a&(1ll<<i))
rep(j,,) if (b&(1ll<<j)){
int k=max(i,j);
ll l=((a^(1ll<<i))^(b^(1ll<<j)))&(~((1ll<<k)-)),r=l+(1ll<<k)-;
ans=(ans+(r/m-l/m+(l%m==))%mod*((1ll<<min(i,j))%mod))%mod;
}
return ans;
}
14.NOWday5C
求有多少对01串S,T，满足：
1. S有a个0，b个1
2. T有c个0，d个1
3. T是S的子序列。
a,b,c,d<=2000
当T确定时，考虑往T上加a-c个0和b-d个1得到S。为了避免重复，规定T一定要是S的第一个长这样的子序列。
于是每个0就只能加在T中某个1的前面，或T的末尾。1同理。
枚举有多少个0和1不加在末尾，组合数求解，最后乘上C(c+d,c)即可。特判c=0或d=0。
rep(i,0,b) rep(j,0,a) ans+=C(c+i-1,c-1)*C(d+j-1,d-1)*C(a-c+b-d-i-j,b-d-i);
15.WHday1
5个大小为200的集合，要求从5个集合中各选一个使和为0，求方案数。
分成2+2+1的形式，枚举1的那200个数，将另外两个排序双指针扫一下即可。
16.WHday2
n棵树，每棵树有a[i]个桃子，掉落的速度是每天d[i]个。接下来k天，每天可以将一棵树上的桃子摘光，求最大摘桃数。(n,k<=1000)
显然最优解中是按d从大到小摘的，那么我们将所有数按d排序后直接DP即可。
17.WHday3T1
n个点，每个点有两个值s和l，当i<j且|si-sj|<=li+lj时，从i到j连一条长度为(j-i)^2的边，求1到n的最短路。
乱搞做法：每一次从i到j显然是j-i越小越好，那么每次只考虑从i跳到i+1,i+2,...,i+12，可得90分。
正解：显然DP，发现每个点可以抽象成一个[si-li,si+li]的区间，两区间有交即可连边。于是用set维护一个区间集合。容易证明，若两个区间有交，则交的部分一定取编号较大的一个，于是set中存的区间都是互不相交的。每次加入新的区间时，先找到set中与它相交的区间进行转移，再用这个区间覆盖别的区间，复杂度O(nlogn)。
18.WHday3T2
支持两种操作:区间覆盖成某种颜色，区间查询共有多少种不同的颜色。颜色数<=30
如果是单点修改，就是经典原题，记录每个位置的lst（即上个和它颜色相同的位置），则询问就是求lst<l的位置的个数。
但这个题不要陷入惯性思维，由颜色数入手，使用线段树，用二进制记录每个区间有哪些颜色，支持区间覆盖和或运算即可。
19.WHday6T1
n个数，每次询问有多少种子集选法，使子集和为m倍数，相等数算不同选法。n<=1e5，Q<=30，m<=100。
O(nmQ)的不难想到，70分。发现每个数x和x%m是完全等价的，于是考虑将复杂度优化成O(Q(nm+m^3))。
首先用桶记录0~m-1每个数出现的次数，然后f[i][j]表示前i个数凑成j的方案数。
显然有f[i][j]=f[i-1][j-k*a[i]]*C(n,k)，状态数只有O(n^2)，考虑去掉k对复杂度的影响。
预处理p[i][j]记录数i对凑成j的方案数C的影响（也就是C之和），转移时直接枚举f[i-1][l]*p[i][i-l]即可。
20.WHday6T2
平面上n个点，用K个边长为L的正方形覆盖所有点，最小化L。n<=1e5,K<=3。
K=1直接求解。
K=2找到覆盖所有点的最小矩形，则两个正方形一定分别在矩形的两个对角上，答案为max{min(max(xi-x0,yi-y0),max(x1-xi,y1-yi))}。
K=3肯定有至少一个正方形在矩形的一个角上，讨论在哪个角上并二分这个正方形的边长，问题转化为K=2的情况。
21.WHday6T3
在一张有向图上随便走（步数可无限），第i步走到的点x的贡献为x*r^i，求能走出的最大收益，保留一位小数。n<=100,0<r<0.999999。
先将有限情况直接算出，步数不可能超过n步。
无限情况显然不可能精确算出，但如果能考虑往后走2^30步的最大收益，精度上就几乎没有误差了。
套路：f[i][j][p]表示从i走2^p步到j的最大收益，转移枚举走2^(p-1)步时到的点k，则f[i][j][p]=f[i][k][p-1]+f[k][j][p-1]*(w^(2^(p-1)))。
22.NOWday5T1
一张有向图上，每个点有一个字符，求从每个点出发的字典序最小的最长路。
方法一：难点主要在于比较两条路径的字典序，而比较只会发生在离终点距离相等的点之间，所以只要在拓扑时用优先队列，保证同层点之间的大小关系即可。
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=,mod=;
int n,m,u,v,w,cnt,tot,ind[N],ans[N],rk[N],fr[N],pre[N],dis[N],h[N],to[N],nxt[N],val[N];
void add(int u,int v,int w){ to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; } struct P{ int x,dis,pre,rk; };
bool operator <(const P &a,const P &b){
return (a.dis==b.dis) ? ((a.pre==b.pre) ? a.rk>b.rk : a.pre>b.pre) : a.dis>b.dis;
}
priority_queue<P>Q; void Top(){
rep(i,,n) if (!ind[i]) Q.push((P){i,,,}),ans[i]=;
while (!Q.empty()){
int x=Q.top().x; Q.pop(); rk[x]=++tot;
if (ans[x]==-) ans[x]=29ll*(ans[fr[x]]+pre[x])%mod;
for (int i=h[x]; i; i=nxt[i]){
int k=to[i];
if ((dis[k]<dis[x]+) || ((dis[k]==dis[x]+) && ((val[i]<pre[k]) || (val[i]==pre[k] && rk[fr[k]]>rk[x]))))
dis[k]=dis[x]+,pre[k]=val[i],fr[k]=x;
if (!--ind[k]) Q.push((P){k,dis[k],pre[k],rk[fr[k]]});
}
}
} int main(){
scanf("%d%d",&n,&m);
rep(i,,m) scanf("%d%d%d",&u,&v,&w),add(v,u,w),ind[u]++;
memset(ans,-,sizeof(ans)); Top();
rep(i,,n) if (ans[i]==-) puts("Infinity"); else printf("%d\n",ans[i]);
return ;
}
方法二：hash+倍增。找出第一个不同的位置比较。
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; typedef long long ll; const int mod=,P1=,P2=;
const int N=;
int n,m,u,v,w,cnt,ans[N],dis[N],ind[N],pw[N],q[N],f[N][],g[N][],h[N],to[N],val[N],nxt[N];
void add(int u,int v,int w){ to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; } bool Cmp(int x,int y){
for (int i=; ~i; i--)
if (f[x][i] && f[y][i] && g[x][i]==g[y][i]) x=f[x][i],y=f[y][i];
return g[x][]>g[y][];
} int main(){
scanf("%d%d",&n,&m);
rep(i,,m) scanf("%d%d%d",&u,&v,&w),add(v,u,w),ind[u]++;
pw[]=P1; rep(i,,) pw[i]=1ll*pw[i-]*pw[i-]%P2;
int st=,ed=;
rep(i,,n) if (!ind[i]) q[++ed]=i;
while (st<ed){
int x=q[++st];
rep(i,,) f[x][i]=f[f[x][i-]][i-],g[x][i]=(1ll*g[x][i-]*pw[i-]%mod+g[f[x][i-]][i-])%mod;
for (int i=h[x]; i; i=nxt[i]){
int k=to[i];
if (dis[x]+>dis[k] || (dis[x]+==dis[k] && (g[k][]>val[i] || (g[k][]==val[i] && Cmp(f[k][],x)))))
g[k][]=val[i],f[k][]=x,ans[k]=29ll*(ans[x]+val[i])%mod,dis[k]=dis[x]+;
if (!--ind[k]) q[++ed]=k;
}
}
rep(i,,n) if (ind[i]) puts("Infinity"); else printf("%d\n",ans[i]);
return ;
}
23.求a+b<=n且a+b|ab的数对(a,b)数量，n<=1e12。
设d=gcd(a,b),a'=a/d,b'=b/d，则有(a'+b')d|a'b'd^2。
因为若a与b互质，则a+b与ab互质，故有a'+b'|d。
由a'+b'<=d且(a'+b')d<=n，得到a'+b'<=sqrt(n)。
枚举k=a'+b'，则对于每个k有n/k^2个d(a'+b'|d且d<=n/(a'+b'))，和phi(k)个a。
24.给定数列a，多次询问(l,r,k)，回答a[l~r]中模k最大的数。n，k<=1e5。
发现对于每个k，[ak,(a+1)k)之间的最大值一定是这些数%k的最大值，这样的区间一共klogk个。
分块，预处理ans[i][j]表示第i块模j的最大值。块的大小设为sqrt(klogk)。
考虑如何计算ans，对每块开个桶记录不大于某个数的最大的数，然后klogk枚举所有区间更新。
25.(1)[ACday9A][BZOJ4773]一张有向带权图，找边数最少的负环，输出边数。(n<=300)
首先发现，floyd可以看作类似矩阵乘法的操作，而矩阵乘法是可以快速幂加速的，于是这个题的思路就比较清晰了。
f[l][i][j]表示从i走2^l以内步到j，能走出的最小边权和，通过枚举中间点转移，然后用类似倍增LCA的方法求出答案。
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=,inf=1e9;
int n,m,ans,u,v,w,f[][N][N],now[N][N],tmp[N][N]; void mul(int a[N][N],int b[N][N],int c[N][N]){
rep(i,,n) rep(j,,n) c[i][j]=inf;
rep(k,,n) rep(i,,n) rep(j,,n)
if (a[i][k]!=inf && b[k][j]!=inf) c[i][j]=min(c[i][j],a[i][k]+b[k][j]);
} int main(){
freopen("bzoj4773.in","r",stdin);
freopen("bzoj4773.out","w",stdout);
scanf("%d%d",&n,&m);
rep(k,,) rep(i,,n) rep(j,,n) f[k][i][j]=inf;
rep(i,,n) rep(j,,n) now[i][j]=inf;
rep(i,,n) f[][i][i]=now[i][i]=;
rep(i,,m) scanf("%d%d%d",&u,&v,&w),f[][u][v]=w;
rep(i,,) mul(f[i-],f[i-],f[i]);
for (int i=; ~i; i--){
mul(now,f[i],tmp); bool flag=;
rep(j,,n) if (tmp[j][j]<) flag=;
if (!flag){
ans|=<<i;
rep(j,,n) rep(k,,n) now[j][k]=tmp[j][k];
}
}
if (ans>n) puts(""); else printf("%d\n",ans+);
return ;
}
(2)[NOW7day7C]一张有向图无权图，每次询问ui到vi是否存在长度为li的路径。(n<=100,l<=1e9)
类似的想法，f[l][i][j]表示i走2^l以内步能否到达j，每次将li二进制拆分，更新能到达的状态集合，使用bitset优化O(n^3logn/64)。
#include<bitset>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define For(i,x) for (int i=h[x]; i; i=nxt[i])
typedef long long ll;
using namespace std; const int N=;
int n,m,u,v,Q,l;
bitset<N>f[][N],to[]; int main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d%d",&n,&m);
rep(i,,m) scanf("%d%d",&u,&v),f[][u][v]=;
rep(j,,) rep(i,,n) rep(k,,n) if (f[j-][i][k]) f[j][i]|=f[j-][k];
for (scanf("%d",&Q); Q--; ){
scanf("%d%d%d",&l,&u,&v);
int p=,q=;
to[].reset(); to[].reset(); to[][u]=;
rep(j,,) if (l&(<<j)){
p^=; q^=; to[q].reset();
rep(i,,n) if (to[p][i]) to[q]|=f[j][i];
}
puts((to[q][v])?"YES":"NO");
}
return ;
}
26.经典问题：一张无向带权连通图，每次询问ui到vi是否存在一条路径（可以走环）异或和为wi。(n<=1e5)
先求出图的一棵生成树，非树边的权值全部由val变为val^s[u][lca]^s[v][lca]，其中s[i][j]为i到j的路径异或和。
对非树边建线性基，每次将询问扔进线性基查询即可。
27.NOWday8C
双人博弈，轮流操作，每次从数列两端共选k个数删去(k|n-1)，A要使最后留下的数最大，B要使最小。A先手，求最终剩下的数。线性。
实际上要求游戏的纳什均衡点。先考虑最后一步A取的情况。
考虑到若对A来说均衡点在最中间k个数中，则A一定能通过模仿B的操作（即B首选了x个，尾y个，则A反之）从而保证最后未删的点就是这个数。而若不在最中间的k个数中，B一定能通过模仿A从而删掉这个数打破平衡。故最终答案只要在最中间的k个数中取max即可。
若最后一步B取，则B也同理会在最中间的k个数中选出最小的，则A的最后一步决策一定是在最中间的连续2k个数中找最小值最大的一个长度为k的区间。
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=;
int T,a[N],n,k,P,q[N];
char s[N]; int main(){
for (scanf("%d",&T); T--; ){
scanf("%s",s); scanf("%d%d",&n,&k);
if (s[]=='w') rep(i,,n) scanf("%d",&a[i]);
else{
scanf("%d%d",&a[],&P);
rep(i,,n) a[i]=(2333ll*a[i-]+)%P;
}
if ((n-)/k&){
int ans=,mid1=(n-k+)/, mid2=k+(n-k+)/;
rep(i,mid1,mid2) ans=max(ans,a[i]);
printf("%d\n", ans);
}
else{
int ans=,mid1=(n-*k+)/,mid2=*k+(n-*k+)/,l=,r=;
rep(i,mid1,mid2){
while (l<=r && q[l]<i-k) l++;
while (l<=r && a[q[r]]>a[i]) r--;
q[++r]=i;
if (i>=mid1+k) ans=max(ans,a[q[l]]);
}
printf("%d\n", ans);
}
}
return ;
}
最新文章
- 测试函数用Return 返回值和用函数名返回值的区别
- [LintCode] Majority Number 求众数
- HTML5学习总结-01 开发环境和历史
- linux系统下yum源的搭建
- 2016 - 1 - 24 CSS初步
- Android之EditText
- Java 关于中文乱码处理的经验总结【转载】
- Android自动化测试之Monkey工具
- 【爬虫问题】爬取tv.sohu.com的页面, 提取视频相关信息
- Web Api 2(Cors)Ajax跨域访问
- PNPOLY - Point Inclusion in Polygon Test
- Form表单提交，Ajax请求，$http请求的区别
- 测者的测试技术手册：揭开java method的一个秘密--巨型函数
- MVC 添加JS，CSS等版本标签
- 关于UITableView的一些老是忘记的小杂碎
- 【LeetCode每天一题】Container With Most Water(容器中最多的水)
- Myeclipse项目中Source、Projects、Libraries、Order and export含义
- Postman-断言和Runner
- rabbitmq windows 安装，更改配置文件路径的问题（管理页面不显示的问题）
- Flutter 控件之 AppBar 和 SliverAppBar