D1T1:与或和
对每位处理,问题变成所有内部不包含0/1的矩阵的个数,单调栈维护即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=,mod=1e9+;
int top,sum,sm,n,mx,a[N][N],b[N][N],st[N],sz[N],l[N][N]; int work(int w,int op){
rep(i,,n) rep(j,,n)
if((a[i][j]&(<<w))) b[i][j]=op; else b[i][j]=op^;
rep(i,,n){
l[i][n]=b[i][n];
for(int j=n-; j; j--)
if(!b[i][j]) l[i][j]=; else l[i][j]=l[i][j+]+;
}
int tmp=;
rep(j,,n){
top=,sum=;
rep(i,,n){
int now=;
while (top && st[top]>=l[i][j])
sum-=st[top]*sz[top],now+=sz[top],top--;
st[++top]=l[i][j]; sz[top]=now+;
sum+=st[top]*sz[top]; tmp=(tmp+sum)%mod;
}
}
return tmp;
} int main(){
freopen("andorsum.in","r",stdin);
freopen("andorsum.out","w",stdout);
scanf("%d",&n);
rep(i,,n) rep(j,,n) scanf("%d",&a[i][j]),mx=max(mx,a[i][j]);
rep(i,,n) rep(j,,n) sm=(sm+1ll*i*j)%mod;
int ans1=,ans2=;
rep(w,,){
if ((1ll<<w)>mx) break;
int t=(1ll<<w)%mod;
ans1=(ans1+1ll*t*work(w,)%mod)%mod;
ans2=(ans2+1ll*t*(sm-work(w,)+mod)%mod)%mod;
}
printf("%d %d\n",ans1,ans2);
return ;
}
andorsum
D1T3:特技飞行
被观察到的特技次数是固定的,先曼哈顿转切比雪夫然后KDT统计即可。
然后发现,若所有特技全部选择对向交换,一定是符合要求的,于是得到了两个极值中的一个。
接下来要让对向交换的次数尽量小,也就是给两个排列,让第一个经过最小的交换次数变成第二个。
找出置换环,答案就是n-置换环数。
#include<set>
#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; const int N=;
const double eps=1e-,inf=1e13;
ll A,B,C;
int n,T,tot,st,ed,x,y,rr,y0[N],y1[N],id[N],vis[N],b[N],cov[N];
set<pair<int,int> >S;
set<pair<int,int> >::iterator it; struct P{ double v[],mn[],mx[]; int ls,rs; }v[N],t;
bool cmpx(const P &a,const P &b){ return a.v[]<b.v[]; }
bool cmpy(const P &a,const P &b){ return a.v[]<b.v[]; }
bool cmp(int a,int b){ return y1[a]<y1[b]; } double Abs(double x){ return x< ? -x : x; } void upd(int x){
rep(i,,){
v[x].mn[i]=min(v[x].v[i],min(v[v[x].ls].mn[i],v[v[x].rs].mn[i]));
v[x].mx[i]=max(v[x].v[i],max(v[v[x].ls].mx[i],v[v[x].rs].mx[i]));
}
} int build(int L,int R,int k){
if (L>R) return ;
int mid=(L+R)>>,x=mid;
nth_element(v+L,v+mid,v+R+,k?cmpy:cmpx);
v[x].ls=build(L,mid-,k^); v[x].rs=build(mid+,R,k^);
upd(x); return x;
} void mdf(int x){
if (!x || b[x] || t.v[]+rr<v[x].mn[] || t.v[]-rr>v[x].mx[] || t.v[]+rr<v[x].mn[] || t.v[]-rr>v[x].mx[]) return;
double s=;
rep(i,,) s=max(s,max(Abs(t.v[i]-v[x].mn[i]),Abs(t.v[i]-v[x].mx[i])));
if (s-eps<rr){ b[x]=; return; }
if (!cov[x] && max(Abs(v[x].v[]-t.v[]),Abs(v[x].v[]-t.v[]))-eps<rr) cov[x]=;
mdf(v[x].ls); mdf(v[x].rs);
} int dfs(int x){
if (b[x]) cov[x]=cov[v[x].ls]=cov[v[x].rs]=b[v[x].ls]=b[v[x].rs]=;
int res=cov[x];
if (v[x].ls) res+=dfs(v[x].ls);
if (v[x].rs) res+=dfs(v[x].rs);
return res;
} int main(){
freopen("aerobatics.in","r",stdin);
freopen("aerobatics.out","w",stdout);
v[].mn[]=v[].mn[]=inf; v[].mx[]=v[].mx[]=-inf;
scanf("%d%lld%lld%lld%d%d",&n,&A,&B,&C,&st,&ed);
rep(i,,n) scanf("%d",&y0[i]);
rep(i,,n) scanf("%d",&y1[i]);
for (int i=n; i; i--){
for (it=S.begin(); it!=S.end() && (it->first<y1[i]); it++){
int j=it->second;
double t=(double)(y0[j]-y0[i])/(y1[i]-y1[j]);
double x=(t*ed+st)/(t+),y=(t*y1[j]+y0[j])/(t+);
v[++tot].v[]=x+y; v[tot].v[]=x-y;
}
S.insert(pair<int,int>(y1[i],i));
}
int rt=build(,tot,);
for (scanf("%d",&T); T--; )
scanf("%d%d%d",&x,&y,&rr),t.v[]=x+y,t.v[]=x-y,mdf(rt);
ll ans=dfs(rt)*C,ans1=ans+tot*A,ans2=ans+tot*A;
rep(i,,n) id[i]=i;
sort(id+,id+n+,cmp);
ll x=n;
rep(i,,n) if (!vis[i]){
x--;
for (int j=i; !vis[j]; j=id[j]) vis[j]=;
}
ans2+=(tot-x)*(B-A);
printf("%lld %lld\n",min(ans1,ans2),max(ans1,ans2));
return ;
}
aerobatics
D2T2:旅行者
方法一:二进制分组,对每个二进制位,将所有编号在这一位为0的关键点放在一边,为1的放在另一边跑最短路。这样任意两点间最短路都一定在某次中被考虑到。O(nlog^2n)
#include<queue>
#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=,inf=1e9;
int n,m,k,T,u,v,w,ans,cnt,s[N],b[N],dis[N],fr[N],h[N],to[N],nxt[N],val[N];
struct P{ int x,d; };
bool operator <(const P &a,const P &b){ return a.d>b.d; }
priority_queue<P>Q; void add(int u,int v,int w){ to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; } void dij(){
while (!Q.empty()){
int x=Q.top().x; Q.pop();
if (b[x]) continue;
b[x]=;
For(i,x) if (dis[k=to[i]]>dis[x]+val[i])
dis[k]=dis[x]+val[i],fr[k]=fr[x],Q.push((P){k,dis[k]});
}
} int main(){
freopen("tourist.in","r",stdin);
freopen("tourist.out","w",stdout);
for (scanf("%d",&T); T--; ){
cnt=; ans=inf; rep(i,,n) h[i]=;
scanf("%d%d%d",&n,&m,&k);
rep(i,,m) scanf("%d%d%d",&u,&v,&w),add(u,v,w);
rep(i,,k) scanf("%d",&s[i]);
for (int t=; t<=k; t<<=){
rep(i,,n) dis[i]=inf,b[i]=;
while (!Q.empty()) Q.pop();
rep(i,,k) if (i&t) dis[s[i]]=,Q.push((P){s[i],}),fr[s[i]]=s[i];
dij();
rep(i,,k) if (!(i&t)) ans=min(ans,dis[s[i]]);
rep(i,,n) dis[i]=inf,b[i]=;
while (!Q.empty()) Q.pop();
rep(i,,k) if (!(i&t)) dis[s[i]]=,Q.push((P){s[i],}),fr[s[i]]=s[i];
dij();
rep(i,,k) if (i&t) ans=min(ans,dis[s[i]]);
}
printf("%d\n",ans);
}
return ;
}
方法一
方法二:对于一条边,它对答案的贡献是a[u]+w+b[v],其中a是所有关键点到它的最短距离,b是它到所有关键点的最短距离。
注意若a和b来自同一个关键点的时候忽略这条边,显然任意两个关键点之间的最短路上总有一条边不会被忽略。O(nlogn)
#include<queue>
#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=,inf=1e9;
int n,m,k,T,u,v,w,ans,s[N],b[N];
struct P{ int x,d; };
bool operator <(const P &a,const P &b){ return a.d>b.d; }
priority_queue<P>Q;
struct E{ int u,v,w; }e[N]; struct Gr{
int cnt,dis[N],fr[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; } void dij(){
rep(i,,n) dis[i]=inf,b[i]=;
while (!Q.empty()) Q.pop();
rep(i,,k) dis[s[i]]=,Q.push((P){s[i],}),fr[s[i]]=s[i];
while (!Q.empty()){
int x=Q.top().x; Q.pop();
if (b[x]) continue;
b[x]=;
For(i,x) if (dis[k=to[i]]>dis[x]+val[i])
dis[k]=dis[x]+val[i],fr[k]=fr[x],Q.push((P){k,dis[k]});
}
}
}G1,G2; void init(){
G1.cnt=G2.cnt=; ans=inf;
memset(G1.h,,sizeof(G1.h)); memset(G2.h,,sizeof(G2.h));
} int main(){
freopen("tourist.in","r",stdin);
freopen("tourist.out","w",stdout);
for (scanf("%d",&T); T--; ){
init(); scanf("%d%d%d",&n,&m,&k);
rep(i,,m) scanf("%d%d%d",&u,&v,&w),G1.add(u,v,w),G2.add(v,u,w),e[i]=(E){u,v,w};
rep(i,,k) scanf("%d",&s[i]);
G1.dij(); G2.dij();
rep(i,,m) if (G1.fr[e[i].u]!=G2.fr[e[i].v]) ans=min(ans,G1.dis[e[i].u]+e[i].w+G2.dis[e[i].v]);
printf("%d\n",ans);
}
return ;
}
方法二
GXOI/GZOI2019部分题解的更多相关文章
-
GXOI/GZOI2019题解
GXOI/GZOI2019题解 P5300 [GXOI/GZOI2019]与或和 一眼题.. 显然枚举每个二进制位,答案就变成了全1子矩阵数量. 这个xjb推推,单调栈一下就行了. #include& ...
-
「GXOI / GZOI2019」简要题解
「GXOI / GZOI2019」简要题解 LOJ#3083. 「GXOI / GZOI2019」与或和 https://loj.ac/problem/3083 题意:求一个矩阵的所有子矩阵的与和 和 ...
-
题解-GXOI/GZOI2019 特技飞行
Problem loj3085 bzoj不放题面差评 题意概要:给出两条竖直直线,再给出 \(n\) 架飞机的初始航线:一条接通这两条直线的线段,保证航线交点不在两条直线上.现要求安排所有飞机在航线相 ...
-
【BZOJ5505】[GXOI/GZOI2019]逼死强迫症(矩阵快速幂)
[BZOJ5505][GXOI/GZOI2019]逼死强迫症(矩阵快速幂) 题面 BZOJ 洛谷 题解 如果没有那两个\(1*1\)的东西,答案就是斐波那契数,可以简单的用\(dp\)得到. 大概是设 ...
-
P5305 [GXOI/GZOI2019]旧词
题目地址:P5305 [GXOI/GZOI2019]旧词 这里是官方题解 \[\sum_{i \leq x}^{}\ depth(lca(i,y))^k\] \(k = 1\) 求的是 \(\sum_ ...
-
P5304 [GXOI/GZOI2019]旅行者
题目地址:P5304 [GXOI/GZOI2019]旅行者 这里是官方题解 一个图 \(n\) 点 \(m\) 条边,里面有 \(k\) 个特殊点,问这 \(k\) 个点之间两两最短路的最小值是多少? ...
-
P5303 [GXOI/GZOI2019]逼死强迫症
题目地址:P5303 [GXOI/GZOI2019]逼死强迫症 这里是官方题解 初步分析 从题目和数据范围很容易看出来这是一个递推 + 矩阵快速幂,那么主要问题在于递推的过程. 满足条件的答案一定是以 ...
-
P5302 [GXOI/GZOI2019]特技飞行
题目地址:P5302 [GXOI/GZOI2019]特技飞行 这里是官方题解(by lydrainbowcat) 题意 给 \(10^5\) 条直线,给 \(x = st\) 和 \(x = ed\) ...
-
P5301 [GXOI/GZOI2019]宝牌一大堆
题目地址:P5301 [GXOI/GZOI2019]宝牌一大堆 这里是官方题解(by lydrainbowcat) 部分分 直接搜索可以得到暴力分,因为所有和牌方案一共只有一千万左右,稍微优化一下数据 ...
随机推荐
-
Hibernate控制台显示创建数据库表语句
package cqvie.yjq.View; import org.hibernate.Session; import org.hibernate.Transaction; import org.h ...
-
Tomcat Server Configuration Automation Reinforcement
目录 . 引言 . 黑客针对WEB Server会有那些攻击面 . 针对Tomcat Server可以做的安全加固 . Managing Security Realms with JMX . 实现对T ...
-
北信源VRVEIS网管软件测试
650) this.width=650;" border="0" alt="" src="http://img1.51cto.com/att ...
-
一个简单的flask程序
初始化 所有Flask程序都必须创建一个程序实例. 程序实例是Flask类的对象,经常使用下述代码创建: from flask import Flask app = Flask(__name__) F ...
-
定时自动备份mysql数据库
新建备份文件并赋予可以执行的权限 mkdir -p /home/mysql_backup/ touch /home/mysql_backup/mysql_backup.sh chmod 551 /ho ...
-
常用的HTTP状态码如下
成功的状态码: – 服务器成功返回网页 – 未修改 失败的状态码: – 请求的网页不存在 – 服务器暂时不可用 – 服务器内部错误 下面的不是很常用,记住上面那几个就ok了,有bug了再补充 其他的状 ...
-
java中的equals()方法
大家都知道,在Java中,对于对象的比较,如果用“==”比较的是对象的引用,而equals才是比较的对象的内容. 一般我们在设计一个类时,需要重写父类的equals方法,在重写这个方法时,需要按照以下 ...
-
PAT (Advanced Level) 1060. Are They Equal (25)
模拟题.坑点较多. #include<iostream> #include<cstring> #include<cmath> #include<algorit ...
-
【转】前端的BFC、IFC、GFC和FFC
什么是BFC.IFC.GFC和FFC CSS2.1中只有BFC和IFC, CSS3中才有GFC和FFC. FC的全称是:Formatting Contexts,是W3C CSS2.1规范中的一个概念. ...
-
MySQL数据库初始
MySQL数据库 本节目录 一 数据库概述 二 MySQL介绍 三 MySQL的下载安装.简单应用及目录介绍 四 root用户密码设置及忘记密码的解决方案 五 修改字符集编码 六 初识sql语句 一 ...