fxq开场看了M，二分答案，读题读错细节wa，改了之后过了。
fxq写A，最开始考虑的是否有些探测器连起来可以把矩阵横向切开或者纵向切开，直接枚举所有探测器两次，写了个记忆化搜索，wa，后来发现少考虑了两种情况，从左边界出发到上边界，以及从下边界出发到右边界，加了之后过了。
lxy开场签了B，H，然后开始看L，读题后推了公式ans = ,然后打表找规律懵逼一万年后找到规律a掉，再去和hyk看D，卡了1h后lxy提出用两个优先队列一个记录叶子节点s另一个记录加入的答案q，每次从s中取出更新答案并标记路径，然后a掉，之后一起对着G发呆，lxy呆不下去了看到J过的挺多去看J，啊，是大模拟！！！终于再4：57压线a掉
fxq:FGIK
lxy:GI
hyk:暂未补题
乘积可以通过取对数操作转化成加法，进行带权二分图最优匹配，二分图左边个点代表行，右边个点代表列，每个数根据所在行列连边，跑一边KM算法，时间复杂度
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define ULL unsigned long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PLI pair<LL,int>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=110;
int n,a[maxn][maxn],match[maxn];
double g[maxn][maxn],ex1[maxn],ex2[maxn],slack[maxn];
bool vis1[maxn],vis2[maxn];
bool dfs(int x){
vis1[x]=true;
for(int y=1;y<=n;y++) {
if(vis2[y]) continue;
double gap=ex1[x]+ex2[y]-g[x][y];
if(gap<eps){
vis2[y]=true;
if(match[y]==-1 || dfs(match[y])){
match[y]=x;
return true;
}
}
else{
slack[y]=min(slack[y],gap);
}
}
return false;
}
void KM(){
memset(match,-1,sizeof(match));
for(int i=1;i<=n;i++) ex2[i]=0;
for(int i=1;i<=n;i++) {
ex1[i]=g[i][1];
for(int j=2;j<=n;j++) {
ex1[i]=max(ex1[i],g[i][j]);
}
}
for(int i=1;i<=n;i++) {
for(int i=1;i<=n;i++) slack[i]=1e9;
while(1){
for(int i=1;i<=n;i++) vis1[i]=vis2[i]=0;
if(dfs(i)) break;
double d=1e9;
for(int j=1;j<=n;j++)
if(!vis2[j]) d=min(d,slack[j]);
for(int j=1;j<=n;j++){
if(vis1[j]) ex1[j]-=d;
if(vis2[j]) ex2[j]+=d;
else slack[j]-=d;
}
}
}
for(int i=1;i<n;i++){
printf("%d ",match[i]);
}
printf("%d\n",match[n]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
double x=a[i][j];
g[i][j]=log(x);
}
}
KM();
}
如果从中间开始，那么只能先走完一边到垂直位置，再走完另一边。所以可以设置三个函数：
从矩阵的一个角开始走到垂直位置的方案数
从矩阵的一个角开始走完整个矩阵的方案数
从矩阵中间出发走完整个矩阵的方案数。分为两个部分：
先走完一边到出发点的垂直位置
走完另一边
最终结果为
所以讨论一下这三个函数的递推式
，边界点，
，边界点，
其中第一个2表示上下两行
第二个2表示先走左边再走右边和先走右边再走左边
第三个2表示走完一边到达垂直位置后，走另一边的起点位置有上下两行
然后就是找的递推式
所以，边界点，
所以有
矩阵快速幂处理
是边界条件，不能由递推式得到，初始矩阵为：
递推式仅对成立，所以需要特判的情况
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define ULL unsigned long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PLI pair<LL,int>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int mod=1e9+7;
int n;
struct Matrix{
LL mat[10][10];
int r,c;
Matrix(){
memset(mat,0,sizeof(mat));
}
};
Matrix mul(Matrix A,Matrix B){
int a=A.r,b=B.c,c=A.c;
Matrix res;
res.r=a;
res.c=b;
for(int i=0;i<a;i++){
for(int k=0;k<c;k++){
for(int j=0;j<b;j++){
res.mat[i][j]=(res.mat[i][j]+A.mat[i][k]*B.mat[k][j]%mod)%mod;
}
}
}
return res;
}
Matrix qp(Matrix A,int k){
int a=A.r;
Matrix res;
res.r=res.c=a;
for(int i=0;i<a;i++) res.mat[i][i]=1;
while(k){
if(k&1) res=mul(res,A);
A=mul(A,A);
k>>=1;
}
return res;
}
int main(){
scanf("%d",&n);
if(n==1){
printf("2\n");
exit(0);
}
Matrix matrix;
matrix.r=matrix.c=4;
matrix.mat[0][0]=2;
matrix.mat[0][2]=16;
matrix.mat[1][1]=2;
matrix.mat[1][2]=4;
matrix.mat[1][3]=2;
matrix.mat[2][1]=1;
matrix.mat[3][3]=2;
matrix=qp(matrix,n-2);
Matrix matrix2;
matrix2.r=4;
matrix2.c=1;
matrix2.mat[0][0]=0;
matrix2.mat[1][0]=6;
matrix2.mat[2][0]=1;
matrix2.mat[3][0]=2;
matrix2=mul(matrix,matrix2);
LL ans=(matrix2.mat[0][0]+4*matrix2.mat[1][0]%mod)%mod;
printf("%lld\n",ans);
}
离线floyd。
先将所有人按照只能经过最冷的个星球的星球个数从小到大排序，将星球逐个加入，通过floyd得到最短路。
再将所有人按照只能经过最热的个星球的星球个数从小到大排序，将星球逐个加入，通过floyd得到最短路。
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define ULL unsigned long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PLI pair<LL,int>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=410,maxm=160010,maxq=100010;
const LL inf=1e16+10;
int n,m,q;
LL g[maxn][maxn],dis[maxn][maxn];
struct Planet{
int id,temp;
}planet[maxn];
struct Person{
int id,u,v,k,t;
LL ans;
}person[maxq];
bool cmp_temp_cold(struct Planet p1,struct Planet p2){
return p1.temp<p2.temp;
}
bool cmp_temp_hot(struct Planet p1,struct Planet p2){
return p1.temp>p2.temp;
}
bool cmp_cold(struct Person p1,struct Person p2){
if(p1.t!=p2.t) return p1.t<p2.t;
return p1.k<p2.k;
}
bool cmp_hot(struct Person p1,struct Person p2){
if(p1.t!=p2.t) return p1.t>p2.t;
return p1.k<p2.k;
}
bool cmp_id(struct Person p1,struct Person p2){
return p1.id<p2.id;
}
void cold(){
sort(planet+1,planet+1+n,cmp_temp_cold);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=g[i][j];
}
}
sort(person+1,person+1+q,cmp_cold);
int cnt=1;
for(int i=1,j=1;i<=q;i++){
if(person[i].t==1) break;
while(person[i].k>=cnt){
while(j<=n){
int k=planet[j].id;
for(int ii=1;ii<=n;ii++){
for(int jj=1;jj<=n;jj++){
if(ii==k || ii==jj || jj==k) continue;
dis[ii][jj]=min(dis[ii][jj],dis[ii][k]+dis[k][jj]);
}
}
j++;
if(j>n || planet[j].temp!=planet[j-1].temp) break;
}
cnt++;
}
if(dis[person[i].u][person[i].v]==inf) person[i].ans=-1;
else person[i].ans=dis[person[i].u][person[i].v];
}
}
void hot(){
sort(planet+1,planet+1+n,cmp_temp_hot);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=g[i][j];
}
}
sort(person+1,person+1+q,cmp_hot);
int cnt=1;
for(int i=1,j=1;i<=q;i++){
if(person[i].t==0) break;
while(person[i].k>=cnt){
while(j<=n){
int k=planet[j].id;
for(int ii=1;ii<=n;ii++){
for(int jj=1;jj<=n;jj++){
if(ii==k || ii==jj || jj==k) continue;
dis[ii][jj]=min(dis[ii][jj],dis[ii][k]+dis[k][jj]);
}
}
j++;
if(j>n || planet[j].temp!=planet[j-1].temp) break;
}
cnt++;
}
if(dis[person[i].u][person[i].v]==inf) person[i].ans=-1;
else person[i].ans=dis[person[i].u][person[i].v];
}
}
void solve(){
cold();
hot();
sort(person+1,person+1+q,cmp_id);
for(int i=1;i<=q;i++){
printf("%lld\n",person[i].ans);
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&planet[i].temp);
planet[i].id=i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=inf;
}
g[i][i]=0;
}
for(int i=1;i<=m;i++){
int u,v,l;
scanf("%d %d %d",&u,&v,&l);
g[u][v]=g[v][u]=min(g[u][v],1ll*l);
}
scanf("%d",&q);
for(int i=1;i<=q;i++){
scanf("%d %d %d %d",&person[i].u,&person[i].v,&person[i].k,&person[i].t);
person[i].id=i;
}
solve();
}
二分答案，先将每个矩形和大矩形求交，之后计算所有矩形的面积并，判断是否符合条件。
线段树+扫描线计算面积并
按照坐标从小到大扫描，预处理每一个矩形，下边界加一，上边界减一，线段树中存储当前与轴平行的线上的情况，线段树开两个数组，存储区间答案和区间被覆盖了多少次，区间中的点代表这条边，左右儿子区间分别为和。更新的时候，如果当前区间被覆盖的次数大于，区间答案为区间长度，否则为左右儿子区间答案之和。
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define ULL unsigned long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PLI pair<LL,int>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=10010,maxm=100010;
int n,p;
LL area;
struct River{
int x1,x2,y1,y2;
}river[maxn];
struct Rect{
int x1,x2,y1,y2;
Rect(int x11=0,int x22=0,int y11=0,int y22=0){
x1=x11;
x2=x22;
y1=y11;
y2=y22;
}
void intersect(const Rect& f){
x1=max(x1,f.x1);
y1=max(y1,f.y1);
x2=min(x2,f.x2);
y2=min(y2,f.y2);
}
}forest;
vector<pair<pair<int,int>,int> > line[maxm];
int tree[4*maxm],cover[4*maxm];
void pushup(int o,int l,int r){
if(l+1==r){
if(cover[o]) tree[o]=1;
else tree[o]=0;
return;
}
if(cover[o]) tree[o]=r-l;
else tree[o]=tree[o<<1]+tree[o<<1|1];
}
void build(int o,int l,int r){
tree[o]=cover[o]=0;
if(l+1==r){
return;
}
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid,r);
}
void update(int o,int l,int r,int ql,int qr,int v){
if(l>=ql && r<=qr){
cover[o]+=v;
pushup(o,l,r);
return;
}
int mid=(l+r)>>1;
if(ql<mid) update(o<<1,l,mid,ql,qr,v);
if(qr>mid) update(o<<1|1,mid,r,ql,qr,v);
pushup(o,l,r);
}
bool check(int mid){
for(int i=forest.y1;i<=forest.y2;i++) line[i].clear();
for(int i=1;i<=n;i++){
Rect rect(river[i].x1-mid,river[i].x2+mid,river[i].y1-mid,river[i].y2+mid);
rect.intersect(forest);
line[rect.y1].push_back({{rect.x1,rect.x2},1});
line[rect.y2].push_back({{rect.x1,rect.x2},-1});
}
LL sum=0;
build(1,0,forest.x2+1);
for(int i=forest.y1;i<=forest.y2;i++){
sum+=tree[1];
for(auto u: line[i]){
update(1,0,forest.x2+1,u.first.first,u.first.second,u.second);
}
}
return sum*100>=area;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d %d %d",&river[i].x1,&river[i].y1,&river[i].x2,&river[i].y2);
if(river[i].x1>river[i].x2) swap(river[i].x1,river[i].x2);
if(river[i].y1>river[i].y2) swap(river[i].y1,river[i].y2);
}
scanf("%d",&p);
scanf("%d %d %d %d",&forest.x1,&forest.y1,&forest.x2,&forest.y2);
area=(1ll*forest.x2-forest.x1)*(forest.y2-forest.y1)*p;
int l=0,r=100005;
while(r>l){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",r);
}