计蒜客 NOIP 提高组模拟竞赛第一试 补记
A. 广场车神
题目大意：
一个\(n\times m(n,m\le2000)\)的网格，初始时位于左下角的\((1,1)\)处，终点在右上角的\((n,m)\)。每次移动可以选择移动到自己右上方的某一方格，且横坐标和纵坐标的变化都不能超过\(k(k\le2000)\)。求一共有多少种移动方案？
思路：
\(f[i][j]\)表示走到\((i,j)\)的方案数，一边DP一边维护二维前缀和即可。
时间复杂度\(\mathcal O(nm)\)。
源代码：
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=2001,mod=998244353;
int f[N][N],g[N][N];
inline int sum(int x1,const int &x2,int y1,const int &y2) {
x1=std::max(x1-1,0);
y1=std::max(y1-1,0);
return (((g[x2][y2]+g[x1][y1])%mod-(g[x1][y2]+g[x2][y1])%mod)%mod+mod)%mod;
}
int main() {
freopen("racing.in","r",stdin);
freopen("racing.out","w",stdout);
const int n=getint(),m=getint(),k=getint();
f[1][1]=g[1][1]=1;
for(register int i=1;i<=n;i++) {
for(register int j=1;j<=m;j++) {
if(i==1&&j==1) continue;
g[i][j]=((g[i-1][j]+g[i][j-1]-g[i-1][j-1])%mod+mod)%mod;
f[i][j]=sum(i-k,i,j-k,j);
(g[i][j]+=f[i][j])%=mod;
}
}
printf("%d\n",f[n][m]);
return 0;
}
B. 敌对*
题目大意：
给定一棵\(n(n\le10^5)\)个结点的树，\(m(m\le10^5)\)次询问，每次询问路径\((a,b)\)和路径\((c,d)\)是否有交。
思路：
树链剖分后，有线段树在\((a,b)\)路径上+1，然后看一下\((c,d)\)路径上是否为\(0\)即可。
时间复杂度\(\mathcal O(m\log^2n)\)。
源代码：
#include<cstdio>
#include<cctype>
#include<vector>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=1e5+1;
std::vector<int> e[N];
inline void add_edge(const int &u,const int &v) {
e[u].push_back(v);
e[v].push_back(u);
}
int dep[N],par[N],size[N],son[N],top[N],dfn[N];
void dfs(const int &x,const int &par) {
size[x]=1;
::par[x]=par;
dep[x]=dep[par]+1;
for(auto &y:e[x]) {
if(y==par) continue;
dfs(y,x);
size[x]+=size[y];
if(size[y]>size[son[x]]) son[x]=y;
}
}
class SegmentTree {
#define _left <<1
#define _right <<1|1
#define mid ((b+e)>>1)
private:
bool val[N<<2],tag[N<<2];
public:
void modify(const int &p,const int &b,const int &e,const int &l,const int &r,const int &t) {
val[p]+=t;
if(b==l&&e==r) {
tag[p]+=t;
return;
}
if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r),t);
if(r>mid) modify(p _right,mid+1,e,std::max(mid+1,l),r,t);
}
bool query(const int &p,const int &b,const int &e,const int &l,const int &r) const {
if(tag[p]) return true;
if(b==l&&e==r) return val[p];
if(l<=mid&&query(p _left,b,mid,l,std::min(mid,r))) return true;
if(r>mid&&query(p _right,mid+1,e,std::max(mid+1,l),r)) return true;
return false;
}
#undef _left
#undef _right
#undef mid
};
SegmentTree sgt;
void dfs(const int &x) {
dfn[x]=++dfn[0];
top[x]=x==son[par[x]]?top[par[x]]:x;
if(son[x]) dfs(son[x]);
for(auto &y:e[x]) {
if(y==par[x]||y==son[x]) continue;
dfs(y);
}
}
inline void modify(int x,int y,const int &t) {
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) std::swap(x,y);
sgt.modify(1,1,dfn[0],dfn[top[x]],dfn[x],t);
x=par[top[x]];
}
if(dep[x]<dep[y]) std::swap(x,y);
sgt.modify(1,1,dfn[0],dfn[y],dfn[x],t);
}
inline bool query(int x,int y) {
bool ret=false;
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) std::swap(x,y);
ret|=sgt.query(1,1,dfn[0],dfn[top[x]],dfn[x]);
x=par[top[x]];
}
if(dep[x]<dep[y]) std::swap(x,y);
ret|=sgt.query(1,1,dfn[0],dfn[y],dfn[x]);
return ret;
}
int main() {
freopen("enemy.in","r",stdin);
freopen("enemy.out","w",stdout);
const int n=getint(),m=getint();
for(register int i=1;i<n;i++) {
add_edge(getint(),getint());
}
dfs(1,0);
dfs(1);
for(register int i=0;i<m;i++) {
const int a=getint(),b=getint(),c=getint(),d=getint();
modify(a,b,1);
puts(query(c,d)?"NO":"YES");
modify(a,b,-1);
}
return 0;
}
C. 提高水平
题目大意：
有\(n(n\le20)\)个东西，第\(i\)个东西放在第\(j\)个东西前可以获得\(a_{i,j}\)的收益。问如何排列这些东西使得收益最大？
思路：
状压DP。
时间复杂度\(\mathcal O(2^nn)\)。
源代码：
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=20;
int a[N][N],f[1<<N],w[N][1<<N];
inline int lowbit(const int &x) {
return x&-x;
}
inline int lg2(const float &x) {
return ((unsigned&)x>>23&255)-127;
}
int main() {
freopen("proficiency.in","r",stdin);
freopen("proficiency.out","w",stdout);
const int n=getint(),all=(1<<n)-1;
for(register int i=0;i<n;i++) {
for(register int j=0;j<n;j++) {
a[i][j]=getint();
}
}
for(register int i=0;i<n;i++) {
for(register int j=1;j<=all;j++) {
w[i][j]=w[i][j^lowbit(j)]+a[lg2(lowbit(j))][i];
}
}
for(register int i=1;i<=all;i++) {
for(register int j=0;j<n;j++) {
if((i>>j)&1) {
f[i]=std::max(f[i],f[i^(1<<j)]+w[j][i]);
}
}
}
printf("%d\n",f[all]);
return 0;
}