8.27

规定Ci,j=Ai×BjC_{i,j}=A_i\times B_jCi,j?=Ai?×Bj?。
现在你需要求出这个矩阵的最大子矩阵的和（即该子矩阵的权值和是所有子矩阵里面最大的）。
D 矩阵

题解

对于10%，很明显是个O(n^6 )的算法..那么直接暴力枚举两个端点，然后暴力统计和取max即可。

对于30%，注意到这个矩阵的生成方式有点特别，把它写出来，就会发现一个矩阵的和是一段Ai乘上一段Bj，那么便可以省去统计两重循环，复杂度O(n^4)

对于50%，考虑优化30分的做法，30分的统计就是一个前缀和相乘的形式，那么要让它最大无非3种情况:

• 正数最大×正数最大;
• 负数最小×负数最小;
• 正数最小×负数最大，第三种又可以分为正数最小在A中，正数最小在B中两种情况，于是维护前缀max?和前缀min?，分类讨论一下，就可以O(n^2)解决了。
  对于100%，既然是一段Ai乘上一段Bj，那么分别统计最大子段和和最小子段和即可。
  复杂度O(n)
  至于怎么算最小子段和？全部取反求最大子段和再重新取反即可。

#define N 1000010
#define M 

int f[N],a[N],b[N],ans,tmp1,tmp2,tmp3,tmp4;
int n,m;

int solve(int a[],int n){
    int res=-2e18;
    rep(i,1,n)f[i]=max(a[i],f[i-1]+a[i]);
    rep(i,1,n)res=max(res,f[i]);
    return res;
}

#undef int
int main() {
#define int long long
    rd(n),rd(m);ans=-2e18;
    rep(i,1,n)rd(a[i]); 
    tmp1=solve(a,n);
    rep(i,1,m)rd(b[i]); 
    tmp2=solve(b,m);
    rep(i,1,n)a[i]=-a[i]; 
    tmp3=-solve(a,n);
    rep(i,1,m)b[i]=-b[i];  
    tmp4=-solve(b,m);
    ans=max(tmp1*tmp2,ans);
    ans=max(tmp1*tmp4,ans);
    ans=max(tmp2*tmp3,ans);
    ans=max(tmp4*tmp3,ans);
    printf("%lld",ans);
}

C 丢失的题面

首先这种残缺的std根本就不是std，所以我们的目的是看懂这个std在干什么，然后用一种时间复杂度更优的算法完成它

对于10%直接copy代码然后完善一下头文件什么的就行了。

考虑这个dp是在干什么，其实就是求对于每个位置往前的前k大的数的和。

那么对于40%,直接删掉第三重循环（考虑如果不选这个数，可以直接直接从f[i?1][j]转移，所以第三重循环完全多余）

对于100%,用一个数据结构动态维护前k大即可。（这里用set或者小根堆，都行）
复杂度O(nlog?n)

#define N 1000010 
#define mod 1000000007 

int ans,sum,n,m,cnt;

priority_queue<int,vector<int>,greater<int> >q;
#undef int
int main(){
#define int long long
    freopen("timian.txt","r",stdin);
    rd(n),rd(m);
    rep(i,1,n){
        int x;rd(x);
        sum+=x;
        q.push(x);
        if(i>m){
            sum-=q.top();
            q.pop();
        }
        if(i>=m)
            ans=(ans+sum)%mod;
    }
    printf("%lld",ans%mod);
    return 0;
} 
/*
5 3
1 2 3 4 5
*/
//27

bfs判二分图

queue<pair<int,int> >q;
inline bool bfs(){
    col[1]=1;
    q.push(make_pair(1,1));
    while(!q.empty()){
        int u=q.front().first;
        int color=q.front().second;
        q.pop();
        ee(i,u){
            int v=e[i].v;
            if(col[v]==-1){
                col[v]=~color;/////////////////
                q.push(make_pair(v,col[v]));
            }
            else if(col[v]==col[u])return 0;
        }
    }
    return 1;
}
int main(){
    rd(n),rd(m);
    rep(i,1,m){
        int u,v;rd(u),rd(v);
        add(u,v),add(v,u);
    }
    mem(col,-1);////////////////////////
    if(bfs())printf("Yes\n");
    else printf("No\n");
    return 0;
} 
/*
4 4
1 3
1 4
2 3
2 4
*/
//Yes

有边数限制的最短路

#define N 510
#define M 10010

int n,m,k;
int dis[N],backup[N];
//使用backup数组的目的是为了防止松弛的次数大于k

struct Edge{
    int u, v, w;
}e[M];

inline int bellman_ford(){
    mem(dis,0x3f);
    dis[1]=0;
    rep(i,1,k){
        memcpy(backup,dis,sizeof(dis));
        rep(j,1,m){
            int u=e[j].u,v=e[j].v,w=e[j].w;
            if(backup[u]!=0x3f3f3f3f && dis[v]>backup[u]+w){
                dis[v]=backup[u]+w;
            }
        }
    }
    if(dis[n]==0x3f3f3f3f)return -1;
    else return dis[n];
}

int main(){
    rd(n),rd(m),rd(k);
    rep(i,1,m){
        rd(e[i].u),rd(e[i].v),rd(e[i].w);
    }
    int t=bellman_ford();
    if (t==-1) puts("impossible");
    else printf("%d\n", t);
    return 0;
}
/*
3 3 1
1 2 1
2 3 1
1 3 3
*/

8.27

原文：https://www.cnblogs.com/sjsjsj-minus-Si/p/11634783.html