首页 > 其他 > 详细

2017.8.7离线赛题解

时间：2020-02-22 21:57:18      阅读：65      评论：0      收藏：0      [点我收藏+]

总结

一定程度上被出题组误导了。既然说是要报复社会，题目肯定难得变态。

第二题浪费了大量时间，看了第三题没怎么想认为比第二题更难，so…

时间还是要有固定的分配啊，就目前而看反正联赛应该没这么难。

第一题$30-60min$

第二题$60-90min$

第三题$60-90min$

具体自己调整，第二题和第三题已经不一定谁更难了，但最小时间肯定要达到，这几次爆$0$基本都是第三题基本在$30min$以下（上上场前两题很顺，留了时间还对拍了，所以没爆$0$）。

务农政策

显然就是求$min(sum(i,k,i-a+1,k-b+1)$ $-$ $tallest(i,k,i-a+1,k-b+1) times a times b)$。维护的重点也就是二维的区间最大值。

如果直接枚举，可以发现对于枚举的$k$，每次扫描的二维区间是从上向下滑动的。可以用双端队列维护。

70分 用上述思路，然后每次查询区间$[k,k-b+1]$用线段树，复杂度是$nmlog(n)T$,常数太大，直接爆炸。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<algorithm>
#include<string.h>
#include<ctype.h>
#define M 1005
#define LL long long
#define oo 2000000000
using namespace std;
void (int &res){
    char c;
    res=0;
    while(c=getchar(),!isdigit(c));
    do{
        res=(res<<3)+(res<<1)+(c^'0');
    }while(c=getchar(),isdigit(c));
}
int mp[M][M],m,n;
LL sum[M][M];
struct node{
    int a[M<<2],pos;
    void build(int L,int R,int p){
        if(L==R){
            a[p]=mp[pos][L];
            return;
        }
        int mid=L+R>>1;
        build(L,mid,p<<1);
        build(mid+1,R,p<<1|1);
        a[p]=max(a[p<<1],a[p<<1|1]);
    }
    int query(int l,int r,int L,int R,int p){
        if(l==L&&r==R)return a[p];
        int mid=L+R>>1;
        if(r<=mid)return query(l,r,L,mid,p<<1);
        else if(l>mid)return query(l,r,mid+1,R,p<<1|1);
        else return max(query(l,mid,L,mid,p<<1),query(mid+1,r,mid+1,R,p<<1|1));
    }
}T[M];
LL calc(int x,int y,int a,int b){
    return sum[x][y]-sum[x-a][y]-sum[x][y-b]+sum[x-a][y-b];
}
int dui[M],val[M];
LL solve(int a,int b){
    LL re=1ll*oo*oo;
    for(int k=b;k<=m;k++){
        int l=0,r=-1;
        for(int i=1;i<=a;i++){
            val[i]=T[i].query(k-b+1,k,1,m,1);
            while(l<=r&&val[dui[r]]<val[i])r--;
            dui[++r]=i;
        }
        re=min(re,1ll*val[dui[l]]*a*b-calc(a,k,a,b));
        for(int i=a+1;i<=n;i++){
            while(l<=r&&i-dui[l]>=a)l++;
            val[i]=T[i].query(k-b+1,k,1,m,1);
            while(l<=r&&val[dui[r]]<val[i])r--;
            dui[++r]=i;
            re=min(re,1ll*val[dui[l]]*a*b-calc(i,k,a,b));
        }
    }
    return re;
}
int main(){
//  freopen("policy.in","r",stdin);
//  freopen("policy.out","w",stdout);
    int i,k,j;
    Rd(n),Rd(m);
    for(i=1;i<=n;i++){
        for(k=1;k<=m;k++){
            Rd(mp[i][k]);
            sum[i][k]+=mp[i][k];
        }
    }
    for(i=1;i<=n;i++){
        for(k=1;k<=m;k++)sum[i][k]+=sum[i-1][k]+sum[i][k-1]-sum[i-1][k-1];
    }
    for(i=1;i<=n;i++)T[i].pos=i,T[i].build(1,m,1);
    int q;
    Rd(q);
    for(i=1;i<=q;i++){
        int a,b;
        Rd(a),Rd(b);
        printf("%lldn",solve(a,b));
    }
    return 0;
}

又发现$k$从b到n枚举，每次查询的$[k,k-b+1]$是从左向右滑动的，也可以用双端队列维护。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<algorithm>
#include<string.h>
#include<ctype.h>
#define M 1005
#define LL long long
#define oo 2000000000
using namespace std;
void (int &res){
    char c;
    res=0;
    while(c=getchar(),!isdigit(c));
    do{
        res=(res<<3)+(res<<1)+(c^'0');
    }while(c=getchar(),isdigit(c));
}
int mp[M][M],m,n;
LL sum[M][M];
struct node{
    int a[M<<2],pos;
    void build(int L,int R,int p){
        if(L==R){
            a[p]=mp[pos][L];
            return;
        }
        int mid=L+R>>1;
        build(L,mid,p<<1);
        build(mid+1,R,p<<1|1);
        a[p]=max(a[p<<1],a[p<<1|1]);
    }
    int query(int l,int r,int L,int R,int p){
        if(l==L&&r==R)return a[p];
        int mid=L+R>>1;
        if(r<=mid)return query(l,r,L,mid,p<<1);
        else if(l>mid)return query(l,r,mid+1,R,p<<1|1);
        else return max(query(l,mid,L,mid,p<<1),query(mid+1,r,mid+1,R,p<<1|1));
    }
}T[M];
LL calc(int x,int y,int a,int b){
    return sum[x][y]-sum[x-a][y]-sum[x][y-b]+sum[x-a][y-b];
}
int dui[M],val[M];
int dui1[M][M],l[M],r[M];
LL solve(int a,int b){
    LL re=1ll*oo*oo;
    memset(l,0,sizeof(l));
    memset(r,-1,sizeof(r));
    for(int k=1;k<b;k++){
        for(int i=1;i<=n;i++){
            while(l[i]<=r[i]&&mp[i][dui1[i][r[i]]]<=mp[i][k])r[i]--;
            dui1[i][++r[i]]=k;
        }
    }
    for(int k=b;k<=m;k++){
        for(int i=1;i<=n;i++){
            while(l[i]<=r[i]&&k-dui1[i][l[i]]>=b)l[i]++;
            while(l[i]<=r[i]&&mp[i][dui1[i][r[i]]]<=mp[i][k])r[i]--;
            dui1[i][++r[i]]=k;
        }
        int L=0,R=-1;
        for(int i=1;i<=a;i++){
            val[i]=mp[i][dui1[i][l[i]]];
            while(L<=R&&val[dui[R]]<val[i])R--;
            dui[++R]=i;
        }
        re=min(re,1ll*val[dui[L]]*a*b-calc(a,k,a,b));
        for(int i=a+1;i<=n;i++){
            while(L<=R&&i-dui[L]>=a)L++;
            val[i]=mp[i][dui1[i][l[i]]];
            while(L<=R&&val[dui[R]]<val[i])R--;
            dui[++R]=i;
            re=min(re,1ll*val[dui[L]]*a*b-calc(i,k,a,b));
        }
    }
    return re;
}
int main(){
//  freopen("policy.in","r",stdin);
//  freopen("policy.out","w",stdout);
    int i,k,j;
    Rd(n),Rd(m);
    for(i=1;i<=n;i++){
        for(k=1;k<=m;k++){
            Rd(mp[i][k]);
            sum[i][k]+=mp[i][k];
        }
    }
    for(i=1;i<=n;i++){
        for(k=1;k<=m;k++)sum[i][k]+=sum[i-1][k]+sum[i][k-1]-sum[i-1][k-1];
    }
    for(i=1;i<=n;i++)T[i].pos=i,T[i].build(1,m,1);
    int q;
    Rd(q);
    for(i=1;i<=q;i++){
        int a,b;
        Rd(a),Rd(b);
        printf("%lldn",solve(a,b));
    }
    return 0;
}

后来跟yahong再讨论时，突然发现$st表$也可以，而且速度比大多数单调队列要快。实现方法跟线段树基本一样，只是询问复杂度变成$O(1)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<algorithm>
#include<string.h>
#include<ctype.h>
#define M 1005
#define LL long long
#define oo 2000000000
using namespace std;
void (int &res){
    char c;
    res=0;
    while(c=getchar(),!isdigit(c));
    do{
        res=(res<<3)+(res<<1)+(c^'0');
    }while(c=getchar(),isdigit(c));
}
int mp[M][M],m,n;
LL sum[M][M];
int st[M],S=10;
struct ST{
	int a[11][M],pos;
	ST(){
		memset(a,0,sizeof(a));
	}
	void build(){
		for(int i=1;i<=m;i++)a[0][i]=mp[pos][i];
		for(int i=1;i<=S;i++){
			for(int k=1;k<=m;k++){
				a[i][k]=max(a[i-1][k],a[i-1][min(m,k+(1大专栏  2017.8.7离线赛题解pan><<i-1))]);
			}
		}
	}
	int query(int l,int r){
		int p=st[r-l+1];
		return max(a[p][l],a[p][r-(1<<p)+1]);
	}
}T[M];
LL calc(int x,int y,int a,int b){
    return sum[x][y]-sum[x-a][y]-sum[x][y-b]+sum[x-a][y-b];
}
int dui[M],val[M];
LL solve(int a,int b){
    LL re=1ll*oo*oo;
    for(int k=b;k<=m;k++){
        int l=0,r=-1;
        for(int i=1;i<=a;i++){
            val[i]=T[i].query(k-b+1,k);
            while(l<=r&&val[dui[r]]<val[i])r--;
            dui[++r]=i;
        }
        re=min(re,1ll*val[dui[l]]*a*b-calc(a,k,a,b));
        for(int i=a+1;i<=n;i++){
            while(l<=r&&i-dui[l]>=a)l++;
            val[i]=T[i].query(k-b+1,k);
            while(l<=r&&val[dui[r]]<val[i])r--;
            dui[++r]=i;
            re=min(re,1ll*val[dui[l]]*a*b-calc(i,k,a,b));
        }
    }
    return re;
}
int main(){
//  freopen("policy0.in","r",stdin);
//  freopen("policy.out","w",stdout);
    int i,k,j;
    Rd(n),Rd(m);
    st[1]=0;
    for(i=1;i<=S;i++){
    	for(k=(1<<(i-1))+1;k<=(1<<i);k++)st[k]=i-1;
        //st[k]=i-1而不是i，被坑了好久。
    }
    for(i=1;i<=n;i++){
        for(k=1;k<=m;k++){
            Rd(mp[i][k]);
            sum[i][k]+=mp[i][k];
        }
    }
    for(i=1;i<=n;i++){
        for(k=1;k<=m;k++)sum[i][k]+=sum[i-1][k]+sum[i][k-1]-sum[i-1][k-1];
    }
    for(i=1;i<=n;i++)T[i].pos=i,T[i].build();
    int q;
    Rd(q);
    for(i=1;i<=q;i++){
        int a,b;
        Rd(a),Rd(b);
        printf("%lldn",solve(a,b));
    }
    return 0;
}

刷副本

求累乘就不用说了，主要是求首位数字。

对于最终数字$w$，可以表示为$w=a*10^b$,其中$ain[0,10)$。$pp=log_{10}w$，$a=10^{{pp}}$,$a$就是最终答案。用对数公式$log_{x}{ab}=log_xa+log_xb$将求法转为$log_{10}a$的累加。说起来思路比较简单，但是谁能想到用这种数学公式化简？询问时$O(1)$，更新时更新所有是$x-1$因子的$R$,对于$x=1$要更新所有，所以可以在查询时加入。

值得一提，正解其实可能被卡掉，仔细观察的话，发现用高精是从后往前求首位，正解则从前往后，是不能省略数字的，我是说正解的double保存位数有限，所以经多次加法，可能使得被省去的位数也对答案造成影响，理论上存在问题，但是double的精度还是很高，所以在实际中精度误差几乎被忽略

所以正解可以理解为从前往后，忽略低位对于答案的影响。

分块决策会更快。当R大于$sqrt n$时直接爆力，小于时在更新是维护。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#define M 200005
#define P 1000000007
#define db double
#define lowbit 0.000000000001
using namespace std;
vector<int>p[M];
int n,a[M],q;
db ans1[M];
int ans2[M];
int fast(int x,int t){
    int re=1;
    while(t){
        if(t&1)re=1ll*re*x%P;
        x=1ll*x*x%P;
        t>>=1;
    }
    return re;
}
int get(db x){
    int re=(pow(10,x-(int)x)+lowbit);
    if(re==10)re=1;
    return re;
}
int main(){
//  freopen("instance16.in","r",stdin);
//  freopen("p.out","w",stdout);
    int i,k,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&a[i]),ans2[i]=1;
    for(i=1;i<=n;i++){
        for(k=i;k<=n;k+=i)p[k].push_back(i);
    }
    for(i=1;i<=n;i++){
        for(k=1+i;k<=n;k+=i){
            ans2[i]=1ll*ans2[i]*a[k]%P;
            db b=log10(a[k]);
            ans1[i]+=b;
        }
    }
    scanf("%d",&q);
    for(i=1;i<=q;i++){
        int id,x,y;
        scanf("%d",&id);
        if(id==1){
            scanf("%d%d",&x,&y);
            if(x==1){
                a[1]=y;
                continue;
            }
            int f=fast(a[x],P-2);
            db l=log10(a[x]),ly=log10(y);
            for(k=0;k<p[x-1].size();k++){
                int pp=p[x-1][k];
                ans2[pp]=1ll*ans2[pp]*f%P;
                ans2[pp]=1ll*ans2[pp]*y%P;
                ans1[pp]-=l,ans1[pp]+=ly;
            }
            a[x]=y;
        }
        else {
            scanf("%d",&x);
            db tt=ans1[x]+log10(a[1]);
            printf("%d %dn",get(tt),1ll*ans2[x]*a[1]%P);
        }
    }
    return 0;
}

圣杯战争

答案是一条边应该是比较显然的。

所以可以把图改成生成树，并以$1$为根。为了方便维护，把一条边对答案的贡献放到边上深度小的点上。然后对于每一个节点，建一棵关于儿子颜色的线段树。每次询问$max(query(1,c[i]-1),query(c[i]+1,K))$,并且由于颜色会改变，所以同一颜色的点都要被记录，每次弹出最小的，可以用multiset维护。直接开线段树是开不下的，所以是动态线段树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<iostream>
#include<algorithm>
#include<string.h>
#include<ctype.h>
#include<set>
#define M 200005
#define oo 2000000000
using namespace std;
void (int &res){
    char c;
    res=0;
    while(c=getchar(),!isdigit(c));
    do{
        res=(res<<3)+(res<<1)+(c^'0');
    }while(c=getchar(),isdigit(c));
}
struct node{
    int to,v,nxt;
}edge[M<<1];
int head[M],cnt=0;
multiset<int>mul[M<<2],ans;
int SS=0;
int fa[M],f[M],vf[M],C[M],res[M];
int n,m,q,K;
int rt[M*40],ls[M*40],rs[M*40],val[M*40],id[M*40],S=0;
struct nodt{
    int x,y,v;
    bool operator <(const nodt &p)const{
        return v<p.v;
    }
}e[M<<1];
int getfa(int x){
    if(x==fa[x])return x;
    return fa[x]=getfa(fa[x]);
}
void add(int x,int y,int v){
    edge[++cnt]=(node){y,v,head[x]};
    head[x]=cnt;
}
void up(int p){
    val[p]=min(val[ls[p]],val[rs[p]]);
}
void update(int x,int v,bool f,int L,int R,int &p){
    if(!p)p=++S,val[p]=oo;
    if(L==R){
        if(!id[p])id[p]=++SS;
        if(f)mul[id[p]].insert(v);
        else mul[id[p]].erase(mul[id[p]].find(v));
        if(mul[id[p]].size())val[p]=*(mul[id[p]].begin());
        else val[p]=oo;
        return;
    }
    int mid=L+R>>1;
    if(x<=mid)update(x,v,f,L,mid,ls[p]);
    else update(x,v,f,mid+1,R,rs[p]);
    up(p);
}
int query(int l,int r,int L,int R,int &p){
    if(!p||l>r)return oo;
    if(l==L&&r==R)return val[p];
    int mid=L+R>>1;
    if(r<=mid)return query(l,r,L,mid,ls[p]);
    else if(l>mid)return query(l,r,mid+1,R,rs[p]);
    else return min(query(l,mid,L,mid,ls[p]),query(mid+1,r,mid+1,R,rs[p]));
}
void dfs(int now,int las){
    f[now]=las;
    for(int i=head[now];i;i=edge[i].nxt){
        node p=edge[i];
        if(p.to==las)continue;
        dfs(p.to,now);
        vf[p.to]=p.v;
        update(C[p.to],p.v,1,1,K,rt[now]);
    }
    if(rt[now]){
        res[now]=min(query(1,C[now]-1,1,K,rt[now]),query(C[now]+1,K,1,K,rt[now]));
        ans.insert(res[now]);
    }
}
int main(){
//  freopen("hack0.in","r",stdin);
//  freopen("p.out","w",stdout);
    int i,k,j;
    Rd(n),Rd(m),Rd(K),Rd(q);
    for(i=1;i<=n;i++)fa[i]=i;
    for(i=1;i<=m;i++)Rd(e[i].x),Rd(e[i].y),Rd(e[i].v);
    for(i=1;i<=n;i++)Rd(C[i]);
    sort(e+1,e+1+m);
    for(i=1;i<=m;i++){
        int x=e[i].x,y=e[i].y;
        int a=getfa(x),b=getfa(y);
        if(a==b)continue;
        fa[a]=b;
        add(x,y,e[i].v);
        add(y,x,e[i].v);
    }
    val[0]=oo;
    dfs(1,0);
    for(int i=1;i<=q;i++){
        int x,y;
        Rd(x),Rd(y);
        if(C[x]!=y){
            if(rt[x]){
                ans.erase(ans.find(res[x]));
                res[x]=min(query(1,y-1,1,K,rt[x]),query(y+1,K,1,K,rt[x]));
                ans.insert(res[x]);
            }
            if(x!=1){ 
                int ff=f[x];
                ans.erase(ans.find(res[ff]));
                update(C[x],vf[x],0,1,K,rt[ff]);
                update(y,vf[x],1,1,K,rt[ff]);
                res[ff]=min(query(1,C[ff]-1,1,K,rt[ff]),query(C[ff]+1,K,1,K,rt[ff]));
                ans.insert(res[ff]);
            }
            C[x]=y;
        }
        printf("%dn",*(ans.begin()));
    }
    return 0;
}

2017.8.7离线赛题解

原文：https://www.cnblogs.com/lijianming180/p/12347340.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！