广州二中NOI2018模拟赛（三十八）
A.预言家
什么狗屎题，还要用NFA（非确定状态自动机）
构造思想还是比较好理解的，就是将某个结点能转移到的所有点用二进制状压表示出来，然后再用Floyd的思想将某个结点能间接转移到的点也搞出来
然后再这台自动机上瞎搞，然后就莫名其妙地AC了……
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
char s[50];
int stk[50],top=0;
int nxt[50],len;
int num[50];
map<int,LL> f[20][2];
map<int,LL>::iterator it;
void Build()
{
len=strlen(s+1);
for(int i=0;i<=len;i++) nxt[i]=(1<<i);
for(int i=1;i<=len;i++)
{
if(s[i]=='*') nxt[i-1]|=(1<<i);
if(s[i]=='(') nxt[i-1]|=(1<<i),stk[++top]=i;
if(s[i]==')')
{
nxt[i-1]|=(1<<i);
if(s[i+1]=='*')
nxt[i]|=(1<<stk[top]),
nxt[stk[top]]|=(1<<i);
else
for(;top&&s[stk[top]]!='(';top--)
nxt[stk[top]-1]|=(1<<i),
nxt[stk[top-1]]|=(1<<stk[top]);
top--;
}
if(s[i]=='|') stk[++top]=i;
}
for(int d=0;d<=len;d++)
for(int i=0;i<=len;i++)
if(nxt[i]&(1<<d)) nxt[i]|=nxt[d];
}
int trans(int state,int num)
{
int res=0;
for(int i=0;i<=len;i++)
if((state&(1<<i))&&s[i+1]-'0'==num)
res|=nxt[i+1];
return res;
}
LL gao(LL x)
{
int cnt=0;LL ans=0;
while(x) num[++cnt]=x%10,x/=10;
reverse(num+1,num+1+cnt);
for(int i=1;i<=cnt;i++)
{
for(int j=0;j<20;j++)
for(int k=0;k<2;k++)
f[j][k].clear();
f[0][i==cnt][nxt[0]]=1;
for(int j=1;j<=i;j++)
for(int k=0;k<2;k++)
for(it=f[j-1][k].begin();it!=f[j-1][k].end();it++)
{
int ed=(k==1)?num[j]:9;
for(int l=(j==1);l<=ed;l++)
f[j][k&&l==num[j]][trans(it->first,l)]+=it->second;
}
for(int k=0;k<2;k++)
for(it=f[i][k].begin();it!=f[i][k].end();it++)
if(it->first&(1<<len)) ans+=it->second;
}
return ans;
}
void print(int x)
{
while(x) printf("%d",x&1),x>>=1;
printf("\n");
}
int main()
{
int T;LL l,r;
for(scanf("%d",&T);T;T--)
{
scanf("%lld%lld%s",&l,&r,s+1);
Build();
printf("%lld\n",gao(r)-gao(l-1));
}
return 0;
}
B.地理学家
70分做法非常简单
首先不难想到，总和最大，肯定是每个格子都尽可能地取到了最大值
考虑每个给定点，会对其它所有格子造成影响，使得它们不能超过某个值
一定会有一个给定点，对某个格子影响最大，那么这个格子就不能超过那个给定点限制的值，也就是要等于那个值
这就是一个最短路模型。每个格子向周围的4个点连上长度为D的边，然后将给定点的距离预设好，其它点的距离设为无穷大。所有给顶点视为源点，跑一遍多源最短路。假如某个给定点在跑完最短路后不等于原来的值了，说明它受到了不超过某个值的限定，而这个限定值小于它本身，于是无解。
假如有解，跑完最短路后，将所有点的距离加起来就是答案了
#include<bits/stdc++.h>
#define ha 1000000007
using namespace std;
typedef long long LL;
const LL LINF=(1ll<<60);
struct Edge{int to,next,capa;} e[4000010];
int r,c,n,d,h[40010],sum;
LL dis[40010];
int mp[210][210];
bool vis[40010];
void add_edge(int u,int v,int c)
{
e[++sum].to=v;
e[sum].capa=c;
e[sum].next=h[u];
h[u]=sum;
}
int get(int x,int y){return (x-1)*c+y;}
int SPFA()
{
memset(mp,0,sizeof(mp));
memset(vis,0,sizeof(vis));
for(int i=1;i<=r*c;i++)
dis[i]=LINF;
int x,y,k;
queue<int> q;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&k);
mp[x][y]=k;
q.push(get(x,y));
vis[get(x,y)]=1;
dis[get(x,y)]=k;
}
while(!q.empty())
{
int u=q.front();
for(int tmp=h[u];tmp;tmp=e[tmp].next)
{
int v=e[tmp].to;
if(dis[u]+(LL)e[tmp].capa<dis[v])
{
dis[v]=dis[u]+(LL)e[tmp].capa;
if(!vis[v]) q.push(v),vis[v]=1;
}
}
q.pop();vis[u]=0;
}
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
if(mp[i][j]&&dis[get(i,j)]!=mp[i][j])
return -1;
int ans=0;
for(int i=1;i<=r*c;i++)
ans=(ans+dis[i]%ha)%ha;
return ans;
}
int main()
{
int T;
for(scanf("%d",&T);T;T--)
{
scanf("%d%d%d%d",&r,&c,&n,&d);
memset(h,0,sizeof(h));sum=0;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
if(i>1) add_edge(get(i,j),get(i-1,j),d);
if(j>1) add_edge(get(i,j),get(i,j-1),d);
if(i<r) add_edge(get(i,j),get(i+1,j),d);
if(j<c) add_edge(get(i,j),get(i,j+1),d);
}
int ans=SPFA();
if(ans==-1) puts("IMPOSSIBLE");
else printf("%d\n",ans);
}
return 0;
}
100分做法比较难想，而且难写（某个巨佬推求和公式推了两小时）。
反正我不会
C.哲学家
首先要想到一个结论：假如我们把三个点对应的向量给编号1、2、3，那么逆时针方向上，1到2、2到3、3到1均不能超过180度。然后你要想到这很不好实现，于是就有一个正难则反的想法。
其实这题并没有强制在线，题目中说到的强制在线是假的，我们可以考虑离线做法
考虑建一个线段树。线段树的所有结点要包含我们查询要用到的所有点
查询一个点(x,y)的答案，必定要有一个查询(-x,-y)的过程，于是我们要把反点也加上去
事实上，在代码实现过程中，我们并不是把点看做结点，而是把某个方向上的一条射线看做结点，这个结点包含了这条射线经过的所有点的信息。
我们求出所有点的射线，以及反点的射线，然后离散去重，弄出一棵线段树
然后查询某个点时，分别考虑逆时针方向到达反点、顺时针方向到达反点所经过的所有点对答案的贡献。边界情况非常麻烦，尤其是处理重复，一不小心没写好就会WA掉。这种狗屎细节还是看代码吧
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace IO
{
const int S=1<<16;
//Input Correlation
char buf[S],*H,*T;
inline char Get()
{
if(H==T) T=(H=buf)+fread(buf,1,S,stdin);
if(H==T) return -1;return *H++;
}
inline LL read()
{
LL x=0;char c=Get();bool fg=0;
while(!isdigit(c)) fg=(c=='-'),c=Get();
while(isdigit(c)) x=x*10+c-'0',c=Get();
return fg?-x:x;
}
//Output Correlation
char obuf[S],*oS=obuf,*oT=oS+S-1,c,qu[55];int qr;
inline void flush()
{
fwrite(obuf,1,oS-obuf,stdout);
oS=obuf;
}
inline void putc(char x)
{
*oS++ =x;
if(oS==oT) flush();
}
inline void print(LL x)
{
if(!x) putc('0');
while(x) qu[++ qr]=x%10+'0',x/=10;
while(qr) putc(qu[qr--]);
putc('\n');
}
}
using namespace IO;
const int N=400010;
struct Point
{
LL x,y;
Point(LL a=0,LL b=0):x(a),y(b){}
bool chk() const{return y>0||(y==0&&x>0);}
friend LL Cross(const Point &a,const Point &b){return a.x*b.y-a.y*b.x;}
inline bool operator <(const Point &a) const
{
bool t1=chk(),t2=a.chk();
return (t1!=t2)?t1:(Cross(*this,a)>0);
}
} jzm[N],xjp[N<<1];
Point operator - (const Point &a){return Point(-a.x,-a.y);}
bool operator == (Point &a,Point &b){return a.chk()==b.chk()&&Cross(a,b)==0;}
LL cnt[N<<3];
int sum[N<<3],tag[N<<3];
map<Point,int> Hash;
int nl,nr,k,tot;
bool ty;
LL x;
inline void maintain(int o){sum[o]=sum[o<<1]+sum[o<<1|1];cnt[o]=cnt[o<<1]+cnt[o<<1|1];}
inline void pushdown(int o)
{
if(!tag[o]) return;
cnt[o<<1]+=tag[o]*sum[o<<1];
tag[o<<1]+=tag[o];
cnt[o<<1|1]+=tag[o]*sum[o<<1|1];
tag[o<<1|1]+=tag[o];
tag[o]=0;
}
void gao1(int o,int l,int r)
{
if(l>=nl&&r<=nr){cnt[o]+=sum[o];tag[o]++;return;}
pushdown(o);
int mid=(l+r)/2;
if(nl<=mid) gao1(o<<1,l,mid);
if(nr>mid) gao1(o<<1|1,mid+1,r);
maintain(o);
}
void gao2(int o,int l,int r)
{
if(l==r){cnt[o]+=x+sum[o];sum[o]++;return;}
pushdown(o);
int mid=(l+r)/2;
if(k<=mid) gao2(o<<1,l,mid);
else gao2(o<<1|1,mid+1,r);
maintain(o);
}
LL query(int o,int l,int r)
{
if(l>=nl&&r<=nr){return ty?sum[o]:cnt[o];}
pushdown(o);
int mid=(l+r)/2;LL res=0;
if(nl<=mid) res+=query(o<<1,l,mid);
if(nr>mid) res+=query(o<<1|1,mid+1,r);
return res;
}
LL Query(int a,int b,bool c){nl=a;nr=b;ty=c;return query(1,1,tot);}
void gao1(int l,int r){nl=l;nr=r;gao1(1,1,tot);}
void gao2(int a,LL b){k=a;x=b;gao2(1,1,tot);}
int main()
{
freopen("data.in","r",stdin);
freopen("my.out","w",stdout);
int n=read();tot=n<<1;
for(int i=1;i<=n;i++)
jzm[i].x=read(),jzm[i].y=read();
for(int i=1;i<=n;i++)
xjp[(i<<1)-1]=jzm[i],xjp[i<<1]=-jzm[i];
sort(xjp+1,xjp+1+tot);
tot=unique(xjp+1,xjp+1+tot)-(xjp+1);
for(int i=1;i<=tot;i++) Hash[xjp[i]]=i;
LL falun,dafa,good=0;
for(int i=1;i<=n;i++)
{
int pos1=Hash[jzm[i]],pos2=Hash[-jzm[i]];
if(!jzm[i].chk()) falun=Query(pos2,pos1,0);
else falun=Query(1,pos1,0)+Query(pos2,tot,0);
LL frog=Query(pos2,pos2,1);
falun-=Query(pos1,pos1,1)*frog;
falun-=frog*(frog-1)/2;
if(jzm[i].chk()) dafa=Query(pos1+1,pos2,1);
else
{
int p1=pos1,p2=pos2;
dafa=Query(1,p2,1);
if(p1<tot) dafa+=Query(p1+1,tot,1);
}
good+=falun+dafa*(dafa-1)/2;
if(!jzm[i].chk()) gao1(pos2,pos1-1);
else
{
if(pos1>1) gao1(1,pos1-1);
gao1(pos2,tot);
}
gao2(pos1,dafa);
print(1ll*i*(i-1)*(i-2)/6ll-good);
}
flush();
return 0;
}