我的微軟輸入法莫名其妙變成繁體了，你們有什麽頭緒嗎
| 狀態 | 題目 |
|---|---|
| 20 Time Exceeded | A 最短路 |
| 25 Time Exceeded | B 方格取数 |
| 0 Time Exceeded | C 数组 |
| 70 Time Exceeded | D 树 |
A.最短路
我赛时想了想，会不会 DIJ 不是很对，因为这个题在打的时候觉得，在跑最短路的时候沿途加上点权有点草率了，但是后面没写完，所以也没回来想
有点像
我四十分的物理卷子
（内心）：你做的这个对吗
我：管它呢，先画个圈，一会回来想，要不写不完了
（内心）：你本来也写不完，要不再看看这题
（在想起一些不好的回忆
（因为太磨叽挂了五十分）之后，还是毅然地跳了）
（过了一会）
（内心）：跳了这么多，你这不也没写完
我：我草我前面还有题没想
所以这个题还是用 Floyed，为啥要点权从小到大排序，其实这么一听觉得真是太对了，但是我懒得想了，所以还是三遍 Floyed 来得实在（只需要保证完全更新就行了）
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f3f3f3f3f;
int mp[301][301];
int dis[301][301];
int w[301];
int n,m,q;
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int p=mp[i][k]+mp[k][j]+max(dis[i][k],dis[k][j]);
if((p<mp[i][j]+dis[i][j])&&mp[i][k]<inf&&mp[k][j]<inf){
mp[i][j]=mp[i][k]+mp[k][j];
dis[i][j]=max(dis[i][k],dis[k][j]);
}
}
}
}
}
signed main(){
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
cin>>w[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) mp[i][j]=0;
else mp[i][j]=inf;
}
}
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
if(mp[x][y]>z){
mp[x][y]=z;
mp[y][x]=z;
dis[x][y]=max(w[x],w[y]);
dis[y][x]=max(w[x],w[y]);
}
}
floyd();floyd();floyd();
for(int i=1;i<=q;i++){
int x,y;
cin>>x>>y;
int res=mp[x][y]+dis[x][y];
cout<<(res>=0x3f3f3f3f3f3f3f3f?-1:res)<<endl;
}
}
B. 方格取数
这个题的 \(n^4\) 挺好想的，我因为没什么头绪打的也是 \(n^4\) 暴力，没想到还能拿点分
如果有一个点大于等于 \(k\) 且小于等于 \(2k\) ，那么我们直接输出这个点即可
如果有一个点大于 \(2k\) ，那么我们一定不可以选这个点，和包括它的矩形
那么现在这个矩阵上只剩下不能选的点和权值小于 \(k\) 的点了，否则跑不到这里就输出答案了.
因此我们现在在这个简化的矩阵上考虑答案
我们可以考虑先找出一个最大的矩阵，即使它的权值大于 \(2k\)，在我们一点点减少的过程中，因为所有节点都小于 \(k\)，一定会在 \([k,2k]\) 内出现一次，因此直接大力删就行了. 删下来以后（其实就是切开了）要判一下哪边比较大（或者直接合法了，那更好）
洛谷上过了，咱们题库上 \(n\) 和 \(k\) 居然是反的，答案坐标也是反的 ，题库上莫名其妙 T 了， \(40\) 分，懒得改了，这并不是 AC 代码
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 2001
int k,n;
long long a[N][N];
long long sum[N][N];
int up[N][N],leftt[N],rightt[N];
long long ask(int lx,int ly,int ux,int uy){
return sum[ux][uy]-sum[lx-1][uy]-sum[ux][ly-1]+sum[lx-1][ly-1];
}
long long sumx;
int mat_sx,mat_sy,mat_ex,mat_ey;
void cutline(int x,int l,int r){
sumx=ask(x,l,x,r);
for(int i=r;i>=l;--i){
sumx-=a[x][i];
if(sumx>=k and sumx<=(k<<1)){
printf("%d %d %d %d",x,l,x,i-1);
exit(0);
}
}
}
void update(int lx,int ly,int ux,int uy){
long long t=ask(lx,ly,ux,uy);
if(t>=k and t<=(k<<1)){
printf("%d %d %d %d",lx,ly,ux,uy);
exit(0);
}
if(t>sumx){
sumx=t;
mat_sx=lx,mat_sy=ly,mat_ex=ux,mat_ey=uy;
}
}
stack<int>st;
signed main(){
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
cin>>a[i][j];
sum[i][j]=sum[i][j-1]+a[i][j];
if(a[i][j]>=k and a[i][j]<=(k<<1)){
printf("%d %d %d %d",i,j,i,j);
return 0;
}
}
for(int j=1;j<=n;++j){
sum[i][j]+=sum[i-1][j];
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(a[i][j]<k){
up[i][j]=up[i-1][j]+1;
}
}
while(!st.empty()) st.pop();
st.push(0);
up[i][0]=-1;
for(int j=1;j<=n;++j){
while(!st.empty() and up[i][st.top()]>=up[i][j]) st.pop();
leftt[j]=st.top()+1;
st.push(j);
}
while(!st.empty()) st.pop();
st.push(n+1);
up[i][n+1]=-1;
for(int j=n;j>=1;--j){
while(!st.empty() and up[i][st.top()]>=up[i][j]) st.pop();
rightt[j]=st.top()-1;
st.push(j);
if(up[i][j]) update(i-up[i][j]+1,leftt[j],i,rightt[j]);
}
}
if(sumx<k){
printf("-1\n");
return 0;
}
for(int i=mat_ex;i>=mat_sx;--i){
long long t=ask(i,mat_sy,i,mat_ey);
if(t>=k and t<=(k<<1)){
printf("%d %d %d %d",i,mat_sy,i,mat_ey);
return 0;
}
else if(t>(k<<1)){
cutline(i,mat_sy,mat_ey);
}
else{
sumx-=t;
if(sumx>=k and sumx<=(k<<1)){
printf("%d %d %d %d",mat_sx,mat_sy,i-1,mat_ey);
return 0;
}
}
}
}
C.数组
没想到搞了半天，线段树写对了，状压写对了，\(tag\) 写对了（其实是没写对，但是差不多对了），但是求 \(\phi\) 的时候寄了
标签：mat,val,lazyP,int,提高,long,st,CSP,模拟 From： https://www.cnblogs.com/HaneDaCafe/p/18298646