GXOI/GZOI2019题解
P5300 [GXOI/GZOI2019]与或和
一眼题。。
显然枚举每个二进制位，答案就变成了全1子矩阵数量。
这个xjb推推，单调栈一下就行了。
#include<bits/stdc++.h>
#define il inline
#define vd void
#define mod 1000000007
typedef long long ll;
il ll gi(){
ll x=0,f=1;
char ch=getchar();
while(!isdigit(ch))f^=ch=='-',ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,A[1010][1010],f[1010][1010];
bool B[1010][1010];
int stk[1010],stkp[1010],tp;
il int calc(bool p){
for(int i=1;i<=n;++i)
for(int j=n;j;--j)
if(B[i][j]^p)f[i][j]=f[i][j+1]+1;
else f[i][j]=0;
int ret=0,res=0;
for(int j=1;j<=n;++j){
stkp[tp=0]=n+1;res=0;
for(int i=n;i;--i){
while(tp&&stk[tp]>=f[i][j])res=(res-1ll*(stkp[tp-1]-stkp[tp])*stk[tp]%mod+mod)%mod,--tp;
stk[++tp]=f[i][j];stkp[tp]=i;
res=(res+1ll*(stkp[tp-1]-stkp[tp])*stk[tp])%mod;
ret=(ret+res)%mod;
}
}
return ret;
}
int main(){
#ifdef XZZSB
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
n=gi();
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)A[i][j]=gi();
int ans1=0,ans2=0,total=0;
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)total=(total+i*j)%mod;
for(int o=0;o<32;++o){
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)B[i][j]=(A[i][j]>>o)&1;
ans1=(ans1+(calc(0)*1ll<<o))%mod;
ans2=(ans2+((1ll*(total-calc(1)+mod)%mod)*1ll<<o))%mod;
}
printf("%d %d\n",ans1,ans2);
return 0;
}
P5301 [GXOI/GZOI2019]宝牌一大堆
牛皮！
国士无双显然可以暴力，7对子显然可以贪心，18张牌的胡牌显然没有用，可以用17张替代。
剩下的情况可以直接dp，设\(f[i][j]\)表示出完了前i种牌，有j个杠子k个面子l个雀头，而且有p个i-1,i,i+1的面子，q个i,i+1,i+2的面子的最大乘积。转移的时候枚举是否组成杠子/刻子/雀头，以及面子i+1,i+2,i+3的数量暴力转移即可。
#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il ll gi(){
ll x=0,f=1;
char ch=getchar();
while(!isdigit(ch))f^=ch=='-',ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
std::map<std::string,int>id;
int cnt[38],m,multi[38];
int C[5][5],p2[]={1,2,4,8,16};
ll f[36][4][5][2][3][3];
il vd chkmx(ll&a,ll b){if(b>a)a=b;}
int yes[40]={0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1};
//f[i][j][k][l][p][q] 出完了前i种牌 有j个杠子 k个面子 l个雀头 p个i-1,i,i+1的面子 q个i,i+1,i+2的面子
int main(){
#ifdef XZZSB
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
C[0][0]=1;for(int i=1;i<5;++i){C[i][0]=1;for(int j=1;j<=i;++j)C[i][j]=C[i-1][j-1]+C[i-1][j];}
for(int i=1;i<10;++i)id[(char)(i+'0')+std::string("m")]=++m;
for(int i=1;i<10;++i)id[(char)(i+'0')+std::string("p")]=++m;
for(int i=1;i<10;++i)id[(char)(i+'0')+std::string("s")]=++m;
id["E"]=++m;id["S"]=++m;id["W"]=++m;id["N"]=++m;
id["Z"]=++m;id["B"]=++m;id["F"]=++m;
int orzyyb=gi();
while(orzyyb--){
memset(multi,0,sizeof multi);
for(int i=1;i<=m;++i)cnt[i]=4;
ll ans=0;
std::string s;
while(std::cin>>s,s!="0")--cnt[id[s]];
while(std::cin>>s,s!="0")++multi[id[s]];
/* 国士无双 直接枚举多的一张牌 */
{ int prz[]={1,9,10,18,19,27,28,29,30,31,32,33,34};
ll res=1;
for(int i=0;i<13;++i){
if(multi[prz[i]])res*=2;
res*=cnt[prz[i]];
}
if(res)
for(int i=0;i<13;++i)
chkmx(ans,res/cnt[prz[i]]*C[cnt[prz[i]]][2]*(multi[prz[i]]?2:1)*13);
}
/* 7对子 直接贪心选最好的7个 */
{ std::vector<ll>s;
for(int i=1;i<=m;++i)s.push_back(C[cnt[i]][2]*(multi[i]?4:1));
std::sort(s.begin(),s.end(),std::greater<int>());
ll res=1;for(int i=0;i<7;++i)res*=s[i];
chkmx(ans,res*7);
}
//剩下的情况，dp
//18张牌没有用，显然把一个杠子换成面子不会更坏
memset(f,0,sizeof f);
f[0][0][0][0][0][0]=1;
for(int i=1;i<=m;++i)
for(int j=0;j<4;++j)
for(int k=0;k<5-j;++k)
for(int l=0;l<2;++l)
for(int p=0;p<3;++p)
for(int q=0;q<3-p;++q){
if(!f[i-1][j][k][l][p][q])continue;
const ll nowf=f[i-1][j][k][l][p][q];
if(cnt[i]==4&&j!=3&&!p&&!q)chkmx(f[i][j+1][k][l][q][0],nowf*(multi[i]?16:1));//组成一个杠子
for(int s3=0;s3<2;++s3){//是否组成一个刻子
for(int s2=0;s2<2-s3;++s2){//是否组成一个雀头
for(int r=0;r<3;++r){//枚举顺子i,i+1,i+2的数量
int total=s3*3+s2*2+r+p+q;
if(cnt[i]<total)continue;
if(k+s3+r>4-j)continue;
if(cnt[i+1]<q+r)continue;
if(cnt[i+2]<r)continue;
if(l+s2>1)continue;
if(r&&!yes[i])continue;//ctmd 顺子要求相同种类
chkmx(f[i][j][k+s3+r][l+s2][q][r],nowf*C[cnt[i]][total]*(multi[i]?p2[total]:1));
}
}
}
}
chkmx(ans,f[m][0][4][1][0][0]);
chkmx(ans,f[m][1][3][1][0][0]);
chkmx(ans,f[m][2][2][1][0][0]);
chkmx(ans,f[m][3][1][1][0][0]);
printf("%lld\n",ans);
}
return 0;
}
P5302 [GXOI/GZOI2019]特技飞行
二合一可还行
显然\(a,b\)的系数和\(c\)的系数是两个独立的问题，\(c\)的系数直接将坐标系转45度就变成sb扫描线了。
算\(a,b\)的系数是显然全都对向交换是一种合法的极端情况，还有一种极端情况就是尽量多的擦肩而过。
这个因为zsy博客里是这么写的，所以问题就是交换任意两个元素的排序使得交换次数最小。
#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il ll gi(){
ll x=0,f=1;
char ch=getchar();
while(!isdigit(ch))f^=ch=='-',ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,a,b,c,xst,xed,k;
int Y0[100010],Y1[100010];
int p[100010],q[100010],r[100010];
double lk[100010],lb[100010];
int Y[100010],_Y0[100010],_Y1[100010];
std::vector<std::pair<double,double>>nodes;
il std::pair<double,double>cross(int x,int y){
double k1=lk[x],b1=lb[x],k2=lk[y],b2=lb[y];
double X=(b1-b2)/(k2-k1),Y=k1*X+b1;
return{X,Y};
}
namespace solve1{
int t[100010];
std::vector<int>vec[100010];
il vd update(int x,int i){while(x<=n)t[x]++,vec[x].push_back(i),x+=x&-x;}
il int query(int x,int i){
int r=0;
while(x){
for(auto j:vec[x])nodes.push_back(cross(i,j));
r+=t[x];x-=x&-x;
}
return r;
}
il int work(){
int ans=0;
for(int i=1;i<=n;++i)Y[i]=std::lower_bound(_Y1+1,_Y1+n+1,Y1[i])-_Y1;
for(int i=1;i<=n;++i)ans+=query(n-Y[i]+1,i),update(n-Y[i]+1,i);
return ans;
}
}
namespace solve2{
bool vis[100010];
int yy[100010];
il int work(){
for(int i=1;i<=n;++i)yy[Y[i]]=i;
int ret=n;
for(int i=1;i<=n;++i){
if(vis[i])continue;
for(int j=yy[i];!vis[j];j=yy[j])vis[j]=1;
--ret;
}
return ret;
}
}
namespace solve3{
struct update{double x,l,r,d;}s[200010];
struct query{double x,y;}qu[500010];
int M,Q;
double yy[400010];int sy,N;
int t[800010];
il vd _update(int x,int d){while(x<=N)t[x]+=d,x+=x&-x;}
il int _query(int x){
int r=0;
while(x)r+=t[x],x-=x&-x;
return r;
}
template<class T>il vd trans(T&a,T&b){
T _a=a,_b=b;
a=_a+_b,b=_a-_b;
}
il int work(){
for(int i=1;i<=k;++i){
double x1=p[i],y1=q[i]-r[i],x2=p[i],y2=q[i]+r[i];
trans(x1,y1);trans(x2,y2);
if(x1>x2)std::swap(x1,x2);
if(y1>y2)std::swap(y1,y2);
y1-=1e-7,y2+=1e-7;
s[++M]={x1,y1,y2,1},s[++M]={x2+1e-7,y1,y2,-1};
yy[++sy]=y1;yy[++sy]=y2;
}
std::sort(yy+1,yy+sy+1);sy=std::unique(yy+1,yy+sy+1)-yy-1;
N=sy*2+2;
for(int i=1;i<=M;++i)s[i].l=std::lower_bound(yy+1,yy+sy+1,s[i].l)-yy;
for(int i=1;i<=M;++i)s[i].r=std::lower_bound(yy+1,yy+sy+1,s[i].r)-yy;
for(auto i:nodes){double x=i.first,y=i.second;trans(x,y);qu[++Q]={x,y};}
std::sort(s+1,s+M+1,[](const update&a,const update&b){return a.x<b.x;});
std::sort(qu+1,qu+Q+1,[](const query&a,const query&b){return a.x<b.x;});
int i=1,j=1,ret=0;
while(i<=M||j<=Q)
if((s[i].x<qu[j].x+1e-7&&(i<=M))||(j>Q))_update(s[i].l*2,s[i].d),_update(s[i].r*2+1,-s[i].d),++i;
else{
int p=std::lower_bound(yy+1,yy+sy+1,qu[j].y)-yy;
if(fabs(qu[j].y-yy[p])<1e-7)p*=2;
else p=p*2-1;
if(_query(p))++ret;
++j;
}
return ret;
}
}
int main(){
#ifdef XZZSB
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
n=gi(),a=gi(),b=gi(),c=gi(),xst=gi(),xed=gi();
for(int i=1;i<=n;++i)Y0[i]=gi();
for(int i=1;i<=n;++i)Y1[i]=gi();
for(int i=1;i<=n;++i)lk[i]=1.0*(Y0[i]-Y1[i])/(xst-xed),lb[i]=Y1[i]-xed*lk[i];
k=gi();
for(int i=1;i<=k;++i)p[i]=gi(),q[i]=gi(),r[i]=gi();
for(int i=1;i<=n;++i)_Y0[i]=Y0[i],_Y1[i]=Y1[i];
std::sort(_Y0+1,_Y0+n+1);std::sort(_Y1+1,_Y1+n+1);
std::unique(_Y0+1,_Y0+n+1),std::unique(_Y1+1,_Y1+n+1);
ll ans1,ans2;ans1=ans2=solve1::work();ans1=1ll*ans1*a;
ans2=1ll*a*ans2+1ll*(b-a)*(ans2-solve2::work());
if(ans1>ans2)std::swap(ans1,ans2);
ll ans3=1ll*solve3::work()*c;
printf("%lld %lld\n",ans1+ans3,ans2+ans3);
return 0;
}
P5303 [GXOI/GZOI2019]逼死强迫症
设\(f_n\)表示\(n\)列的答案，那么考虑在左边放些什么东西。可以放一个\(1\times 2\)的竖块或者两个\(2\times 1\)的横块，或者放\(1\times 1\)的块。
如果放\(1\times 1\)的块，显然就要考虑另一个放哪。显然第\(1\)列不行，第\(2\)列也不行，不过第\(3\)到\(n\)列都可以找到一个地方可以（根据奇偶而定），而且如果放好了另一个，那么这两个块中间的\(1\times 2\)放法是确定的，只要考虑右边这一块的方案数，右边这一块显然是个斐波那契数。所以转移方程是\(f_n=f_{n-1}+f_{n-2}+\sum_{i=0}^{n-3}fib_i(fib_0=fib_1=1)\)。\(\sum fib\)在矩阵快速幂的时候顺便记一下就好了。
#include<bits/stdc++.h>
#define il inline
#define vd void
#define mod 1000000007
typedef long long ll;
il ll gi(){
ll x=0,f=1;
char ch=getchar();
while(!isdigit(ch))f^=ch=='-',ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
struct matrix{int s[5][5];matrix(){memset(s,0,sizeof s);}}I,F,begin;
il matrix operator*(const matrix&a,const matrix&b){
matrix ret;
for(int j=0;j<5;++j)
for(int i=0;i<5;++i)
for(int k=0;k<5;++k)
ret.s[i][k]=(ret.s[i][k]+1ll*a.s[i][j]*b.s[j][k])%mod;
return ret;
}
il matrix operator^(matrix a,int b){
matrix ret=I;
while(b){
if(b&1)ret=ret*a;
a=a*a;b>>=1;
}
return ret;
}
struct ques{int n,i;}q[510];
int ans[510];
int main(){
#ifdef XZZSB
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
I.s[0][0]=I.s[1][1]=I.s[2][2]=I.s[3][3]=I.s[4][4]=1;
F.s[0][1]=1;
F.s[1][0]=F.s[1][1]=1;
F.s[2][3]=F.s[2][4]=1;
F.s[3][2]=F.s[3][3]=F.s[3][4]=1;
F.s[4][1]=F.s[4][4]=1;
begin.s[0][2]=1;
int n=gi();
for(int i=1;i<=n;++i)q[i].n=gi(),q[i].i=i;
std::sort(q+1,q+n+1,[](const ques&a,const ques&b){return a.n<b.n;});
matrix now=begin;
q[0].n=1;for(int i=1;i<=n;++i)now=now*(F^(q[i].n-q[i-1].n)),ans[q[i].i]=now.s[0][1]*2%mod;
for(int i=1;i<=n;++i)printf("%d\n",ans[i]);
return 0;
}
P5304 [GXOI/GZOI2019]旅行者
一开始看见这题想到了cf1146c，可以用那种方法分治得到任意两个的最短路，复杂度\(O(n\log^2n)\)。
然后翻了一下提交记录好像他们都跑的飞快+代码巨短就去膜题解了。
stm。。。每一个点记录最近的关键点\(dist_i\)和反图上最近的关键点\(dist2_i\)，然后枚举每一条边直接算就行了。对于\((u,v,w)\)就一定存在一条\(dist2_u+dist_v+w\)的路径。
如果一条边两个点最近的关键点相同就不能计入答案。所以我不知道这个方法为啥对，但确实是对的，也叉不掉。
#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il ll gi(){
ll x=0,f=1;
char ch=getchar();
while(!isdigit(ch))f^=ch=='-',ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
int fir[100010],dis[1000010],nxt[1000010],w[1000010],id;
il vd link(int a,int b,int c){nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;}
ll dist[100010];int d[100010];
ll dist2[100010];int d2[100010];
bool vis[100010];
std::priority_queue<std::pair<ll,int>>que;
int main(){
#ifdef XZZSB
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
int T=gi();
while(T--){
id=0;memset(fir,0,sizeof fir);
int n=gi(),m=gi(),k=gi(),a,b,c;
memset(dist+1,63,8*n);memset(dist2+1,63,8*n);
while(m--)a=gi(),b=gi(),c=gi(),link(a,b,c),link(b,a,c);
while(k--)a=gi(),dist[a]=dist2[a]=0,d[a]=d2[a]=a,que.push({0,a});
memset(vis,0,sizeof vis);
while(!que.empty()){
int x=que.top().second;que.pop();
if(vis[x])continue;vis[x]=1;
for(int i=fir[x];i;i=nxt[i])
if((i&1)&&dist[dis[i]]>dist[x]+w[i]){
dist[dis[i]]=dist[x]+w[i];d[dis[i]]=d[x];
que.push({-dist[dis[i]],dis[i]});
}
}
for(int i=1;i<=n;++i)if(!dist[i])que.push({0,i});
memset(vis,0,sizeof vis);
while(!que.empty()){
int x=que.top().second;que.pop();
if(vis[x])continue;vis[x]=1;
for(int i=fir[x];i;i=nxt[i])
if(!(i&1)&&dist2[dis[i]]>dist2[x]+w[i]){
dist2[dis[i]]=dist2[x]+w[i];d2[dis[i]]=d2[x];
que.push({-dist2[dis[i]],dis[i]});
}
}
ll ans=1e18;
for(int i=1;i<=n;++i)
for(int j=fir[i];j;j=nxt[j])
if((j&1)&&d[i]!=d2[dis[j]])ans=std::min(ans,w[j]+dist[i]+dist2[dis[j]]);
printf("%lld\n",ans);
}
return 0;
}
P5305 [GXOI/GZOI2019]旧词
[LNOI]LCA
[HNOI]开店
#include<bits/stdc++.h>
#define il inline
#define vd void
#define mod 998244353
typedef long long ll;
il ll gi(){
ll x=0,f=1;
char ch=getchar();
while(!isdigit(ch))f^=ch=='-',ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
il int pow(int x,int y){
int ret=1;
while(y){
if(y&1)ret=1ll*ret*x%mod;
x=1ll*x*x%mod;y>>=1;
}
return ret;
}
int fir[50010],dis[50010],nxt[50010],id;
il vd link(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}
struct ques{int x,y,i;}s[50010];
il bool operator<(const ques&a,const ques&b){return a.x<b.x;}
int pk[50010],dfn[50010],dep[50010],son[50010],siz[50010],top[50010],dep_dfn[50010];
il vd dfs(int x){
siz[x]=1;
for(int i=fir[x];i;i=nxt[i]){
dep[dis[i]]=dep[x]+1,dfs(dis[i]);
siz[x]+=siz[dis[i]];
if(siz[son[x]]<siz[dis[i]])son[x]=dis[i];
}
}
il vd dfs(int x,int tp){
top[x]=tp;dfn[x]=++dfn[0];dep_dfn[dfn[x]]=dep[x];
if(son[x])dfs(son[x],tp);
for(int i=fir[x];i;i=nxt[i])if(dis[i]!=son[x])dfs(dis[i],dis[i]);
}
int ans[50010];
#define mid ((l+r)>>1)
int sum[200010],val[200010],lz[200010],fa[200010];
il vd build(int x,int l,int r){
if(l==r){val[x]=(pk[dep_dfn[l]]-pk[dep_dfn[l]-1]+mod)%mod;return;}
build(x<<1,l,mid),build(x<<1|1,mid+1,r);
val[x]=(val[x<<1]+val[x<<1|1])%mod;
}
il vd upd(int x,int d){lz[x]+=d;sum[x]=(sum[x]+1ll*d*val[x])%mod;}
il vd down(int x){if(lz[x])upd(x<<1,lz[x]),upd(x<<1|1,lz[x]),lz[x]=0;}
il vd update(int x,int l,int r,const int&L,const int&R){
if(L<=l&&r<=R)return upd(x,1);
down(x);
if(L<=mid)update(x<<1,l,mid,L,R);
if(mid<R)update(x<<1|1,mid+1,r,L,R);
sum[x]=(sum[x<<1]+sum[x<<1|1])%mod;
}
il int query(int x,int l,int r,const int&L,const int&R){
if(L<=l&&r<=R)return sum[x];
down(x);
if(L<=mid)
if(mid<R)return(query(x<<1,l,mid,L,R)+query(x<<1|1,mid+1,r,L,R))%mod;
else return query(x<<1,l,mid,L,R);
else return query(x<<1|1,mid+1,r,L,R);
}
#undef mid
int main(){
#ifdef XZZSB
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
int n=gi(),Q=gi(),k=gi();
for(int i=1;i<=n;++i)pk[i]=pow(i,k);
for(int i=2;i<=n;++i)link(fa[i]=gi(),i);
for(int i=1;i<=Q;++i)s[i].x=gi(),s[i].y=gi(),s[i].i=i;
std::sort(s+1,s+Q+1);
dep[1]=1;dfs(1);dfs(1,1);
build(1,1,n);
for(int i=1,p=1;i<=Q;++i){
while(p<=s[i].x){
for(int x=p;x;x=fa[top[x]])update(1,1,n,dfn[top[x]],dfn[x]);
++p;
}
for(int x=s[i].y;x;x=fa[top[x]])ans[s[i].i]=(ans[s[i].i]+query(1,1,n,dfn[top[x]],dfn[x]))%mod;
}
for(int i=1;i<=Q;++i)printf("%d\n",ans[i]);
return 0;
}