题面：https://www.cnblogs.com/Juve/articles/11569010.html
Tourist Attractions：
暴力当然是dfs四层
优化一下，固定两个点，答案就是这两个点的度数减一相乘，在枚举第三点，减去三元环的情况
三元环可以用bitset优化
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<bitset>
#define re register
#define int long long
using namespace std;
const int MAXN=1505;
int n,ans=0,du[MAXN];
bool mp[MAXN][MAXN];
char ch[MAXN];
bitset<MAXN>b[MAXN],t;
signed main(){
scanf("%lld",&n);
for(re int i=1;i<=n;++i){
b[i].reset();
scanf("%s",ch+1);
for(re int j=1;j<=n;++j){
if(ch[j]=='1'){
b[i].set(j,1);
mp[i][j]=1;
++du[i];
}
}
}
t.reset();
for(int x=1;x<=n;++x){
for(int y=1;y<=n;++y){
if(y==x) continue;
if(mp[x][y]!=1) continue;
ans+=(du[x]-1)*(du[y]-1);
t=b[x]&b[y];
ans-=t.count();
}
}
printf("%lld
",ans);
return 0;
}
养花：
考场上只有暴力了。。。
考虑到k只有1e5，我们考虑预处理出每一个k时的情况
我们考虑分块，预处理出每一个块内%k的最大值，查询时大段直接统计块内的，小段暴力
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int block=1e3;
const int MAXN=1e5+5;
const int N=1e5+2;
const int MAXM=1e2+5;
int n,m,a[MAXN],f[MAXN],blo[MAXN],num,mx[MAXM][MAXN];
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),blo[i]=(i-1)/block;
num=(n-1)/block;
for(int i=0;i<=num;++i){
memset(f,0,sizeof(f));
int l=i*block+1,r=min(n,(i+1)*block);
for(int j=l;j<=r;++j) f[a[j]]=a[j];
for(int j=1;j<=N;++j) f[j]=max(f[j],f[j-1]);
for(int j=1;j<=N;++j){
for(int k=0;k<=N;k+=j){
mx[i][j]=max(mx[i][j],f[min(k+j-1,N)]-k);
}
}
}
while(m--){
int l,r,k,ans=0;
scanf("%d%d%d",&l,&r,&k);
for(int i=blo[l]+1;i<blo[r];++i) ans=max(ans,mx[i][k]);
for(int i=l;i<=min(r,(blo[l]+1)*block);++i) ans=max(ans,a[i]%k);
for(int i=max(l,blo[r]*block+1);i<=r;++i) ans=max(ans,a[i]%k);
printf("%d
",ans);
}
return 0;
}
画作：
有一个性质：在画的时候每次修改的点都是上一次修改的点的子集
不难证明猜到一个这样的结论: 存在一种最优方案使得每次操作的区
域是上一次的子集且颜色与上一次相反.
考虑归纳证明, 记 S 为当前所有操作区域的并, T 为接下来一步的操作
区域, 我们有:
1. T 与 S 有交的情况一定可以转化成 T 被 S 包含的情况.
2. T 与 S 交集为空时, 可以找一个连接 S 和 T 的集合 M 并操作 S ∪
T ∪ M , 并将之前的所有操作连接到更外的层以及外层的连接部分同时
操作, 特殊处理最外层和第二层的情况.
3. T 被 S 包含时, T 落在某个完整区域内时等价于情况二, 否则一定连
接若干个同色块, 这些块可以同时处理, 步数一定不会更劣.
知道这个结论就比较好做了, 我们可以枚举最后被修改的区域, 这时答
案就是将同色边边权当作 0, 异色边边权当作 1 后距离这个点最远的黑色点
的距离, 对所有点取最小值即可.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n,m,mp[55][55],ans=0x7fffffff;
char ch[55];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int calc(int i,int j){return (i-1)*m+j;}
bool vis[55*55];
int dis[55*55];
priority_queue< pair< pair<int,int>,pair<int,int> > >pq;
inline int dij(int st,int pp,int qq){
memset(dis,0x3f,sizeof(dis));
dis[st]=0;
memset(vis,0,sizeof(vis));
pq.push(make_pair(make_pair(-dis[st],st),make_pair(pp,qq)));
while(!pq.empty()){
pair< pair<int,int>,pair<int,int> > pa=pq.top();
pq.pop();
if(vis[pa.first.second]) continue;
vis[pa.first.second]=1;
int x=pa.second.first,y=pa.second.second;
for(int i=0;i<4;++i){
int p=x+dx[i],q=y+dy[i];
if(p<1||p>n||q<1||q>m) continue;
int w=!(mp[x][y]==mp[p][q]);
int v=calc(p,q);
if(dis[v]>dis[pa.first.second]+w){
dis[v]=dis[pa.first.second]+w;
pq.push(make_pair(make_pair(-dis[v],v),make_pair(p,q)));
}
}
}
int res=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(mp[i][j]==1) res=max(res,dis[calc(i,j)]);
}
}
return res;
}
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%s",ch+1);
for(int j=1;j<=m;++j){
mp[i][j]=ch[j]-'0';
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
ans=min(ans,dij(calc(i,j),i,j));
}
}
printf("%d
",ans+1);
return 0;
}