T1
给一个01矩阵，求一个最大子矩阵，矩阵内的和不超过k
$k leq n^2$
$n leq 500$
sol：$O(n^4)$枚举左上角和右下角，发现后两维有单调性，可以用一个滑窗来搞
但其实非常优秀的枚举3个坐标然后二分第四个坐标的$O(n^3logn)$做法是能过的...本地1.3s
T2
给n个点的坐标和势力范围，每个点向势力范围内每个点连长度为$t_i$的边，求最短路
$n leq 150000$
sol：线段树优化建图！感觉自己押到题了 qwq
线段树上从上往下连长度为$0$的边，每个点向区间连边，直接最短路即可
T3
一棵树，第$i$个点可以花$a_i$的代价变成关键点，定义这个树的代价为建立关键点的代价 + 非关键点到他最近的关键点距离之和
求最小代价
$n leq 2500$
sol：
有点难
先考虑30分的brute force（$n leq 10$）
枚举全排列即可
然后我们考虑另外40分的dp（树是一条链）
我们的状态是dp[i]表示最后一个关键点建在$i$的最小代价
转移的时候枚举下一个关键点建在哪，可以发现这两个点之间的所有点，坐标小于等于$avg$（这两个关键点的平均值）的往左走，剩下的往右走
这样就可以转移了
需要注意的是，如果没有建过关键点，代价就是这个点建关键点的代价 + 1~i全走到它的代价
正解非常的CF
我们考虑放宽限制，用$f_{(i,j)}$表示$i$的子树里，钦定所有点走到$j$的最小代价
$g[i]$表示$i$子树的最小代价
为什么这样是对的呢，我们可以想一下，最小的答案里，所有点必然不会绕路走到一个比较远的点
转移就考虑子树里的点是走到$j$还是“另起炉灶”自己搞一个关键点出来
$f_{(i,j)} = a_j + dis(i,j) + sum (MINg[to],f_{(to,j)} - a_j)$
#include<bits/stdc++.h> #define LL long long using namespace std; inline int read() { int x = 0,f = 1;char ch = getchar(); for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f; for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0'; return x * f; } int n,k; int a[510][510],s[510][510]; inline int check(int stx,int sty,int edx,int edy) { return (s[edx][edy] - s[stx - 1][edy] - s[edx][sty - 1] + s[stx - 1][sty - 1] <= k); } int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); int ans = 0; n = read(),k = read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)a[i][j] = read(); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++)s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int t=i,tmp,st=n;t<=n;t++) { tmp=s[t][st]-s[i-1][st]-s[t][j-1]+s[i-1][j-1]; while(tmp>k&&st>j) st--,tmp=s[t][st]-s[i-1][st]-s[t][j-1]+s[i-1][j-1]; ans=max(ans,(t-i+1)*(st-j+1)); } cout<<ans; }
#include<cstdio> #include<cstring> #include<cctype> #include<cmath> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int maxn=2610; int n,cost[maxn],first[maxn],nxt[maxn<<1],to[maxn<<1],dis[maxn<<1],e; void AddEdge(int u,int v,int w) { to[++e]=v;dis[e]=w;nxt[e]=first[u];first[u]=e; to[++e]=u;dis[e]=w;nxt[e]=first[v];first[v]=e; } int dist[maxn][maxn]; void dfs(int x,int fa,int s) { for(int i=first[x];i;i=nxt[i]) if(to[i]!=fa) dist[s][to[i]]=dist[s][x]+dis[i],dfs(to[i],x,s); } int f[maxn][maxn],g[maxn]; void dp(int x,int fa) { for(int i=first[x];i;i=nxt[i]) if(to[i]!=fa) dp(to[i],x); rep(j,1,n) { f[x][j]=cost[j]+dist[x][j]; for(int i=first[x];i;i=nxt[i]) if(to[i]!=fa) f[x][j]+=min(g[to[i]],f[to[i]][j]-cost[j]); } g[x]=f[x][1]; rep(i,2,n) g[x]=min(g[x],f[x][i]); } int main() { freopen("design.in","r",stdin); freopen("design.out","w",stdout); n=read(); rep(i,1,n) cost[i]=read(); rep(i,1,n-1) { int u=read(),v=read(),w=read(); AddEdge(u,v,w); } rep(i,1,n) dfs(i,0,i); dp(1,0); printf("%d ",g[1]); return 0; }
#include<bits/stdc++.h> #define LL long long using namespace std; inline int read() { int x = 0,f = 1;char ch = getchar(); for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f; for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0'; return x * f; } const int maxn = 160000; int n,S,T; int x[maxn],w[maxn],t[maxn]; int first[maxn * 20],to[maxn * 30],nx[maxn * 30],val[maxn * 30],cnt; inline void add(int u,int v,int w) { to[++cnt] = v; nx[cnt] = first[u]; first[u] = cnt; val[cnt] = w; } #define ls (x << 1) #define rs ((x << 1) | 1) int lb[maxn],rb[maxn]; inline int getpos(int x){return 1+ n + x;} inline void build(int x,int l,int r) { if(l == r) { add(getpos(x),l,0); return; } int mid = (l + r) >> 1; build(ls,l,mid);build(rs,mid + 1,r); add(getpos(x),getpos(ls),0); add(getpos(x),getpos(rs),0); } int get_left(int pos) { int l = 1,r = pos,mid,ans = r; while(l <= r) { mid = (l + r) >> 1; if(x[pos] - w[pos] <= x[mid])ans = mid,r = mid - 1; else l = mid + 1; } return ans; } int get_right(int pos) { int l = pos,r = n,mid,ans = l; while(l <= r) { mid = (l + r) >> 1; if(x[pos] + w[pos] >= x[mid])ans = mid,l = mid + 1; else r = mid - 1; } return ans; } inline void update(int x,int l,int r,int L,int R,int np,int nv) { if(L <= l && r <= R) { add(np,getpos(x),nv); //cout<<np<<" "<<getpos(x)<<" "<<nv<<endl; return; } int mid = (l + r) >> 1; if(L <= mid)update(ls,l,mid,L,R,np,nv); if(R > mid)update(rs,mid + 1,r,L,R,np,nv); } #define pa pair<LL,int> priority_queue<pa,vector<pa>,greater<pa> > q; LL dis[maxn << 4]; int vis[maxn << 4]; inline void dij() { q.push(make_pair(0LL,S)); memset(dis,63,sizeof(dis));dis[S] = 0; while(!q.empty()) { int now = q.top().second;q.pop(); //cout<<now<<" "<<dis[now]<<endl; if(vis[now])continue; vis[now] = 1; for(int i=first[now];i;i=nx[i]) { if(dis[to[i]] > dis[now] + val[i]) { dis[to[i]] = dis[now] + val[i]; q.push(make_pair(dis[to[i]],to[i])); } } } } int main() { freopen("trip.in","r",stdin); freopen("trip.out","w",stdout); n = read(),S = read(),T = read(); for(int i=1;i<=n;i++)x[i] = read(); for(int i=1;i<=n;i++)w[i] = read(); for(int i=1;i<=n;i++)t[i] = read(); for(int i=1;i<=n;i++) { lb[i] = get_left(i); rb[i] = get_right(i); //cout<<lb[i]<<" "<<rb[i]<<endl; } build(1,1,n); for(int i=1;i<=n;i++)update(1,1,n,lb[i],rb[i],i,t[i]); dij(); cout<<dis[T]; } /* 7 3 7 -1 0 1 2 3 5 10 11 0 1 1 4 10 2 3 1 1 1 2 4 5 */