NewOJ Week 5

NewOJ Week 5

C.E待补

A. 并行处理（前缀和）

思路：显然最短时间为$min(max({\sum }_{i=1}^j{a}_i,{\sum }_{i=j+1}^n{a}_i)$，$1\le j\le n$，前缀和处理一下
复杂度：$O(n)$

$Code:$

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
int n,a[N];
int main(){
    IOS;cin>>n;ll ans=1e18,ans1=0,sum=0;for(int i=1;i<=n;i++) {
    cin>>a[i];sum+=a[i];}for(int i=1;i<=n;i++){
    ans1+=a[i];ans=min(ans,max(ans1,sum-ans1));}cout<<ans<<endl;return 0;
}

B. 排列变换（思维）

思路：先考虑一个常见的问题：对于一个长度为$n$的排列$a$，每次选择一个数字往左移若干位，求将其变为递增序列需要的最小移动次数？
举个例子：$3,1,5,2,4$，显然我们需要移动$3$次，分别为$1,2,4$，我们发现移动的原因显然是：$3>1,5>2,5>4$，即：对于某个位置，如果它前面的序列的最大值大于它，它就需要移动位置
那对于这个问题，我们就把序列$b$的值映射到一个递增序列中，即可把问题转换为上述问题
复杂度：$O(n)$

$Code：$

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
int n,a[N],c[N],b[N];
map<int,int>mp;
int main(){
    IOS;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i],mp[b[i]]=i;for(int i=1;i<=n;i++) c[i]=mp[a[i]];int ans=0,pos=0;for(int i=1;i<n;i++){
    if(max(pos,c[i])>c[i+1]) {
    ans++;pos=max(pos,c[i]);}}cout<<ans<<endl;return 0;
}

D. 矩阵（数学+前缀和）

思路：对于矩阵乘法：$C_{i,j}=\sum _{k=1}^n{A}_{i,k}?B_{k,j}$，如果直接运算，复杂度$O(n^3)$肯定$TLE$
但对于每次询问$a,b,c,d$构成的子矩阵和时，我们通过和式变换：
$$\sum _{i=a}^c\sum _{j=b}^d{C}_{i,j}=\sum _{i=a}^c\sum _{j=b}^d\sum _{k=1}^n{A}_{i,k}?B_{k,j}=\sum _{k=1}^n\left[\right(\sum _{i=a}^c{A}_{i,k})?(\sum _{j=b}^d{B}_{k,j}\left)\right]$$
然后我们通过这个式子写出了如下$query$函数：

ll query(int a,int b,int c,int d){
    ll ans=0;for(int k=1;k<=n;k++){
    ll ans1=0,ans2=0;for(int i=1;i<=n;i++) ans1+=A[i][k];for(int i=1;i<=n;i++) ans2+=B[k][i];	ans+=ans1*ans2;}return ans;
}

然后就继续$TLE$，显然上述做法复杂度是$O(m?n^2)$，不可行
我们考虑对上述做法进行优化，我们发现通过预处理前缀和可以实现：
$$\sum _{i=a}^c{A}_{i,k}=su{m}_{c,k}?su{m}_{a?1,k}\sum _{j=b}^d{B}_{k,j}=su{m}_{k,d}?su{m}_{k,b?1}$$
将这个求和符号优化掉之后，复杂度为：$O(m?n)$，可行

$Code：$

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=2e3+10,mod=1e9+7;
int n,m,a,b,c,d,A[N][N],B[N][N],sum1[N][N],sum2[N][N];
template<class T>
void read(T &x){
    x=0; char c; int sign=1;do{
     c=getchar(); if(c=='-') sign=-1;}while(!isdigit(c));do{
     x=x*10+c-'0',c=getchar();}while(isdigit(c));x*=sign;
}
ll query(int a,int b,int c,int d){
    ll ans=0;for(int k=1;k<=n;k++){
    ll ans1=sum1[c][k]-sum1[a-1][k];ll ans2=sum2[k][d]-sum2[k][b-1];	ans+=ans1*ans2;}return ans;
}
int main(){
    read(n),read(m);for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
    read(A[i][j]);}}for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
    read(B[i][j]);}}for(int k=1;k<=n;k++){
    for(int i=1;i<=n;i++) sum1[i][k]=sum1[i-1][k]+A[i][k];for(int i=1;i<=n;i++) sum2[k][i]=sum2[k][i-1]+B[k][i];}while(m--){
    read(a),read(b),read(c),read(d);if(a>c)swap(a,c);if(b>d)swap(b,d);printf("%lld\n",query(a,b,c,d));}return 0;
}