10.25
题单介绍
这场比较史。
$t1$ 简单题，$t2$ 数据分治，$t3$ 是非 **基础** 数学，$t4$ 最小割。
没什么推荐的题目。
### t1
给定 $n$ 行 $m$ 列的网格图，每格是障碍或者空地，只有空地可以通行。
每个白天你可以走**至多** $k$ 格，每个夜晚你可以使至多 $k$ 格障碍变成空地，求从给定起点到达网格图边界的最少天数。
发现第二天起就等价于没有障碍，所以第二天以后从某格走出网格图的最少天数可以 $O(1)$ 算。
dfs 或者 bfs 出第一天能到达的格子然后取其最少天数 $+1$ 即可。
特判初始就在网格图边界的情况。
```cpp
#include <cstdio>
#include <algorithm>
#include <cstdlib>
static char stkk[200];
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
typedef long long ll;
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
inline void ckmin(int &x,int y){x>y&&(x=y);}
inline int mini(int x,int y){return x<y?x:y;}
const int N = 2e3+10,nf = 2e9+10,dx[] = {0,0,-1,1},dy[] = {1,-1,0,0};
static int n,m,k,ans,sx,sy;
inline int cal(int x,int y){return mini((mini(x-1,n-x)+k-1)/k,(mini(y-1,m-y)+k-1)/k);};
static bool ok[N][N],vis[N][N];
static char s[N][N];
void dfs(int x,int y,int dep){
if(x<1||x>n||y<1||y>m||!ok[x][y]||vis[x][y]||dep>k)return;
vis[x][y] = 1;ckmin(ans,cal(x,y));
FOR(t,0,3)dfs(x+dx[t],y+dy[t],dep+1);
}
inline void solve(){
readx(n),readx(m),readx(k);
FOR(i,1,n)scanf(" %s",s[i]+1);
FOR(i,1,n)FOR(j,1,m){
vis[i][j] = 0;
if(s[i][j]=='S')sx = i,sy = j,ok[i][j] = 1;
else ok[i][j] = s[i][j]=='.';
}
if(sx==1||sx==n||sy==1||sy==m)return output(0),putchar(10),void();
ans = nf;
dfs(sx,sy,0);
output(ans+1),putchar(10);
}
signed main(){
freopen("escape.in","r",stdin);
freopen("escape.out","w",stdout);
int t;for(readx(t);t--;solve());
// puts("Yes");
return 0;
}
//1
//10 5
//1 2 3 3 3 4 3 3 2 4
```
### t2
交互题。
有一个长为 $n$ 的序列，每个位置有颜色，每次你可以询问区间 $[l,r]$ 中不同的颜色个数，求出这个序列的模样（颜色可以任意编号，只要原序列同色位置在你返回序列中仍然同色，异色位置仍然异色即可）。
至多询问 $Q$ 次。
一部分数据：$1 \leq n \leq 10^3,1 \leq Q \leq 10^4$。
一部分数据：$1 \leq n,Q \leq 10^3$，保证颜色段连续。
一部分数据：$1 \leq n \leq 10^4,1 \leq Q \leq 10^4$，保证至多有 $4$ 种不同的颜色 **或者** 至少也有 $n-1$ 种不同的颜色。
第一部分数据，从左往右扫，对于每个点二分出其之前第一个与其同色的点即可，至多询问 $O(n \log n)$ 次，可以通过。
第二部分数据直接双指针或者只判断与前一个数是否同色即可，至多询问 $O(n)$ 次，可以通过。
第三部分数据，对于颜色少的情况，之前不同色的点至多有 $4$ 种，可以只判断从左往右数第 $3$ 个点，然后根据询问情况决定询问第 $2$ 个点或者第 $4$ 个数，得出与其同色的点，至多询问 $2n$ 次；对于颜色多的情况，如果均异色随便做，如果有两个同色就直接二分存在点同色的最大左端点和最小右端点，然后就可以得出同色点对，至多询问 $2 \log n$ 次，可以通过。
```cpp
#include <bits/stdc++.h>
#include "generals.h"
using namespace std;
int query(int l, int r);
vector<int> getColor(int T, int N, int Q){
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
int ct[1010],c[1010],cct;
FOR(i,1,N)ct[i] = c[i] = 0;cct = 1;
c[1] = ct[1] = 1;
if(T>=9&&T<=15){
int j = 1;cct = 0;
for(int i = 2;i <= N;++i){
if(query(j,i)!=1){
++cct;
FOR(t,j,i-1)c[t] = cct;
j = i;
}
}
++cct;
FOR(t,j,N)c[t] = cct;
}
else if(T>=16&&T<=34){
bool vis[4];
FOR(i,2,N){
vis[1] = vis[2] = vis[3] = 0;
int t1 = -1,t2 = -1,t3 = -1,tans = -1;
REP(j,i-1,1){
if(!vis[c[j]]){
vis[c[j]] = 1;
if(t3==-1)t3 = j;
else if(t2==-1)t2 = j;
else {
t1 = j;break;
}
}
}
if(t2==-1){
if(query(t3,i)==1)tans = t3;
}
else{
int tmp0,tmp1;
if((tmp0=query(t2,i))==2){
if((tmp1=query(t3,i))==1)tans = t3;
else tans = t2;
}
else{
if(t1!=-1)tans = t1;
}
}
if(tans==-1){
FOR(j,1,i)++ct[j];
c[i] = ++cct;
}
else{
c[i] = c[tans];
FOR(j,tans+1,i)++ct[j];
}
}
}
else if(T>=35&&T<=48){
bool vis[5];
FOR(i,2,N){
vis[1] = vis[2] = vis[3] = vis[4] = 0;
int t1 = -1,t2 = -1,t3 = -1,t4 = -1,tans = -1;
REP(j,i-1,1){
if(!vis[c[j]]){
vis[c[j]] = 1;
if(t4==-1)t4 = j;
else if(t3==-1)t3 = j;
else if(t2==-1)t2 = j;
else {
t1 = j;break;
}
}
}
if(t3==-1){
if(query(t4,i)==1)tans = t4;
}
else if(query(t3,i)==2){
if(query(t4,i)==1)tans = t4;
else tans = t3;
}
else if(t2!=-1&&query(t2,i)==3){
tans = t2;
}
else if(t1!=-1)tans = t1;
if(tans==-1){
FOR(j,1,i)++ct[j];
c[i] = ++cct;
}
else{
c[i] = c[tans];
FOR(j,tans+1,i)++ct[j];
}
}
}
else if(T>=49&&T<=60){
int tot = query(1,N);
if(tot==N){
FOR(i,1,N)c[i] = i;
}
else{
int dl = 2,dr = N,mid,tans = -1;
while(dl<=dr){
mid = dl+dr>>1;
if(query(1,mid)==mid-1)tans = mid,dr = mid-1;
else dl = mid+1;
}
if(tans==-1)puts("?");
int R = tans;
dl = 1,dr = R-1,tans = -1;
while(dl<=dr){
mid = dl+dr>>1;
if(query(mid,R)==R-mid)tans = mid,dl = mid+1;
else dr = mid-1;
}
if(tans==-1)puts("?");
int L = tans;
c[L] = c[R] = ++cct;
FOR(i,1,N)if(!c[i])c[i] = ++cct;
}
}
else{
FOR(i,2,N){
// printf("i:%d\n",i);
// FOR(j,1,i-1)printf("%d ",ct[j]);putchar(10);
int dl = 1,dr = i-1,mid,tans = -1;
while(dl<=dr){
mid = dl+dr>>1;
if(query(mid,i)==ct[mid]+1)dr = mid-1;
else dl = mid+1,tans = mid;
}
// printf("tans:%d cct:%d\n",tans,cct);
if(tans==-1){
FOR(j,1,i)++ct[j];
c[i] = ++cct;
}
else{
c[i] = c[tans];
FOR(j,tans+1,i)++ct[j];
}
}
}
// FOR(i,1,N)printf("%d ",c[i]);putchar(10);
std::vector<int> ans;
FOR(i,1,N)ans.push_back(c[i]);
return ans;
#undef FOR
#undef REP
}
```
### t3
我还不会，我尽力了（）。
给定常数 $T$ 和 $n$ 个点的 $t_i$，其坐标为 $(\cos(\dfrac{2 \pi t_i}{T}),\sin(\dfrac{2 \pi t_i}{T}))$，求任取三点得到的三角形的内心期望横坐标和纵坐标，$t_i$ 严格不同。
记 $a_i = \dfrac{2 \pi t_i}{T}$，然后排序。
不妨设 $a_1 \lt a_2 \lt a_3$，则有内心横坐标为 $\cos(t_1+t_2)+\cos(t_2+t_3)-\cos(t_1+t_3)$，纵坐标为 $\sin(t_1+t_2)+\sin(t_2+t_3)-\sin(t_1+t_3)$（我觉得这个结论不显然，倒不如说我根本不理解这个结论awa）。
然后只考虑横坐标，可以考虑对形如 $\cos(t_i+t_j)$ 的形式统计贡献，则有 $\dfrac{1}{\binom{n}{3}}\sum_{i \lt j}{\cos(a_i+a_j)}(2i-2j+n)$。
然后你把上面那个东西拆开，然后直接维护 $i\cos(a_i)$，$i\sin(a_i)$ 和 $\cos(a_i)$，$\sin(a_i)$ 的后缀和即可。
总坐标同理。
时间复杂度 $O(n)$。
```cpp
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <vector>
static char stkk[200];
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
#define GO(x) for(int i = h[x],y = e[i];i;y = e[i=ne[i]])
#define up std::unordered_map
#define ve std::vector
#define ll long long
#define ld long double
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
const int N = 1e6+10;
const ld pi = acos(-1);
static int n,T;
static ld co[N],si[N],a[N],bco[N],bsi[N],dco[N],dsi[N];
signed main(){
freopen("geometry.in","r",stdin);
freopen("geometry.out","w",stdout);
readx(n),readx(T);
int t;FOR(i,1,n)readx(t),a[i] = pi*t/T,bco[i] = std::cos(a[i]),bsi[i] = std::sin(a[i]);
REP(i,n,1)co[i] = bco[i]+co[i+1],si[i] = bsi[i]+si[i+1],dco[i] = 2*i*bco[i]+dco[i+1],dsi[i] = 2*i*bsi[i]+dsi[i+1];
ld x = 0,y = 0;
FOR(i,1,n){
x += (2*i+n)*(bco[i]*co[i+1]-bsi[i]*si[i+1])-(bco[i]*dco[i+1]-bsi[i]*dsi[i+1]);
y += (2*i+n)*(bsi[i]*co[i+1]+bco[i]*si[i+1])-(bsi[i]*dco[i+1]+bco[i]*dsi[i+1]);
}
x = x*6/n/(n-1)/(n-2);
y = y*6/n/(n-1)/(n-2);
printf("%.15Lf %.15Lf",x,y);
return 0;
}
// 2 1
// 2 1
// 1 2 2
```
$t4$
给定 $n$ 个平面直角坐标系中的点 $(x_i,y_i)$ 及其点权 $v_i$。
定义横纵坐标均为偶数的点为 **重要的点**。
如果存在一个重要点，有三个与其切比雪夫距离不超过 $1$ 的点，与其构成了一个有一边平行于 $x$ 轴的平行四边形，那么这个局面是不合法的。
你可以删掉一些点，使得局面合法，最大化未被删除的点的点权和。
可以证明局面合法等价于不存在 $(奇,偶)$ -> $(偶，偶)$ -> $(偶，奇)$ -> $(奇，奇)$ 这样的路径，其中奇/偶 表示对应坐标的奇偶性， -> 表示两点相邻。
然后就拆点，每个点拆成 $in_i$，$ou_i$，将 $in_i$ 向 $ou_i$ 连 $w_i$ 的边。
然后将源点向 $(奇，偶)$ 点的 $in_i$ 连正无穷的边，将 $(奇，奇)$ 点的 $ou_i$ 向汇点连正无穷的边，对于满足上述路径的点对将他们的出点和入点对应连正无穷的边，跑最小割即可。
最后输出总点权和减去最小割。
```cpp
#include <cstdio>
#include <algorithm>
#include <queue>
#include <unordered_map>
static char stkk[200];
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
#define GO(x) for(int i = h[x],y = e[i];i;y = e[i=ne[i]])
#define GO1(x) for(int i = now[x],y = e[i];i;y = e[i=ne[i]])
#define up std::unordered_map
typedef long long ll;
template<typename T>inline void output(T x){
if(!x)return putchar('0'),void();
if(x<0)x = ~x+1,putchar('-');
int top = 0;
for(;x;stkk[++top]=x%10^48,x/=10);
for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
x = 0;int y = 1;char c = getchar();
for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
x *= y;
}
template<typename T1,typename T2>inline void ckmin(T1 &x,T2 y){x>y&&(x=y);}
const int N = 2e4+10,dx[] = {1,-1,0,0},dy[] = {0,0,1,-1};
const ll lnf = 1e18;
static int e[N*10],ne[N*10],from[N*10],h[N<<1],tot,n,x[N],y[N],v[N],s,t;
static ll w[N*10];
static up<int,up<int,int> > id;
inline void add(int x,int y,ll ww){e[++tot] = y,ne[tot] = h[x],h[x] = tot;from[tot] = x,w[tot] = ww;}
inline void link(int x,int y,ll w){add(x,y,w),add(y,x,0);}
// printf("x:%d y:%d w:%lld]\n",x,y,w);
static int dep[N<<1],gra[N<<1],pree[N<<1],now[N<<1];
struct node{int x,y;};
static node to[2][2];
inline ll isap(){
FOR(i,1,t)now[i] = h[i];
std::queue<int> q;dep[t] = 1;q.push(t);
while(!q.empty()){
int x = q.front();q.pop();
++gra[dep[x]];
GO(x)if(w[i^1]&&!dep[y])q.push(y),dep[y] = dep[x]+1;
}
ll ans = 0,mx;int x = s;
while(dep[s]<=t){
if(x==t){
mx = lnf;
for(int i;x!=s;x = from[i])ckmin(mx,w[i=pree[x]]);
x = t;ans+=mx;
for(int i;x!=s;x = from[i])i = pree[x],w[i]-=mx,w[i^1]+=mx;
}
bool ok = 0;
GO1(x)if(w[i]&&dep[y]+1==dep[x]){
ok = 1;pree[y] = now[x] = i;
x = y;
break;
}
if(!ok){
if(!--gra[dep[x]])break;now[x] = h[x];
int mii = t+10;
GO(x)if(w[i]&&mii>dep[y])mii = dep[y];
++gra[dep[x]=mii+1];
if(x!=s)x = from[pree[x]];
}
}
return ans;
}
signed main(){
freopen("mis.in","r",stdin);
freopen("mis.out","w",stdout);
readx(n);to[1][0] = {0,0};to[0][0] = {0,1},to[0][1] = {1,1},to[1][1] = {-1,-1};
s = 2*n+1,t = s+1;tot = 1;ll ans = 0;
FOR(i,1,n){
readx(x[i]),readx(y[i]),readx(v[i]),id[x[i]][y[i]] = i;
link(i,i+n,v[i]);ans+=v[i];
if((x[i]&1)&&!(y[i]&1))link(s,i,lnf);
else if(((x[i]&1))&&(y[i]&1))link(i+n,t,lnf);
}
node tmp;
FOR(i,1,n){
tmp = to[x[i]&1][y[i]&1];
FOR(k,0,3){
int tx = x[i]+dx[k],ty = y[i]+dy[k];
if(!id[tx][ty])continue;
if((tx&1)==tmp.x&&(ty&1)==tmp.y)link(i+n,id[tx][ty],lnf);
}
}
output(ans-isap());
return 0;
}
// 5
// 0 0 4
// 0 1 5
// 1 0 3
// 1 1 1
// -1 1 2
```