您的位置: 首页  >  IT文章  >  BZOJ 4868-4873 题解

BZOJ 4868-4873 题解

分类: IT文章 • 2023-03-24 19:00:30

BZOJ4868

每个结束位置的最优值很显然具有单调性,三分,再讨论一下就好了.

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define FILE "exam"
 5 #define up(i,j,n) for(int i=j;i<=n;i++)
 6 #define db long double 
 7 #define pii pair<int,int>
 8 #define pb push_back
 9 template<class T> inline bool cmin(T& a,T b){return a>b?a=b,true:false;}
10 template<class T> inline bool cmax(T& a,T b){return a<b?a=b,true:false;}
11 template<class T> inline T squ(T a){return a*a;}
12 const int maxn=105000+10,inf=1e9+10,mod=201314;
13 ll read(){
14     ll x=0,f=1,ch=getchar();
15     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
16     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
17     return x*f;
18 }
19 db A,B,C;
20 ll a[maxn],b[maxn],d[maxn],n,m;
21 db check(ll s){
22     db ans=0;
23     memcpy(d,b,sizeof(d));
24     if(A<B){
25         int l=1,r=m;
26         while(l<r){
27             if(d[r]<s||d[l]>s)break;
28             if(d[r]-s>s-d[l])ans+=A*(s-d[l]),d[r]-=s-d[l],d[l]=s,l++;
29             else ans+=A*(d[r]-s),d[l]+=d[r]-s,d[r]=s,r--;
30         }
31         for(int i=m;i>=1;i--)
32             if(d[i]>s)ans+=B*(d[i]-s);
33         for(int i=1;i<=n;i++)
34             if(a[i]<s)ans+=C*(s-a[i]);
35         return ans;
36     }
37     else {
38         for(int i=1;i<=m;i++)if(d[i]>s)ans+=B*(d[i]-s);
39         for(int i=1;i<=n;i++)
40             if(a[i]<s)ans+=C*(s-a[i]);
41         return ans;
42     }
43 }
44 int main(){
45     freopen(FILE".in","r",stdin);
46     freopen(FILE".out","w",stdout);
47     A=read(),B=read(),C=read();
48     n=read(),m=read();
49     ll left=inf,right=-inf;
50     up(i,1,n)a[i]=read(),cmin(left,a[i]);
51     up(i,1,m)b[i]=read(),cmax(right,b[i]);
52     sort(b+1,b+m+1);
53     sort(a+1,a+n+1);
54     while(right-left>3){
55         int mid1=(left+left+right)/3;
56         int mid2=(left+right+right)/3;
57         if(check(mid1)>check(mid2))left=mid1;
58         else right=mid2;
59     }
60     db Ans=(ll)1e18;
61     for(int i=left;i<=right;i++)
62         cmin(Ans,check(i));
63     printf("%.0Lf
",Ans);
64     return 0;
65 }
View Code

BZOJ4869

看到这道题后我想到了某道同样是一堆幂的神题,尽管我没写过...

正确做法是EX欧拉定理+线段树,我会欧拉定理,但我不知道什么是EX欧拉定理.

请自行百度,(尽管你baidu不到).

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define int long long
  4 #define FILE "verbinden"
  5 #define up(i,j,n) for(int i=j;i<=n;++i)
  6 #define db long double 
  7 #define pii pair<int,int>
  8 #define pb push_back
  9 template<class T> inline bool cmin(T& a,T b){return a>b?a=b,true:false;}
 10 template<class T> inline bool cmax(T& a,T b){return a<b?a=b,true:false;}
 11 template<class T> inline T squ(T a){return a*a;}
 12 const int maxn=210000+10,inf=1e9+10;
 13 int read(){
 14     int x=0,f=1,ch=getchar();
 15     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 16     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
 17     return x*f;
 18 }
 19 int n,m,mod,C;
 20 int a[maxn];
 21 int op[maxn],x[maxn],y[maxn];
 22 int fi[maxn];
 23 int getfi(int n){
 24     int m=sqrt(n*1.0)+1,ans=1;
 25     if(n==1)return 1;
 26     for(int i=2;i<=m;i++){
 27         if(n%i==0)ans=ans*(i-1),n/=i;
 28         while(n%i==0){
 29             ans=ans*(i);
 30             n/=i;
 31         }
 32         if(n==1)break;
 33     }
 34     if(n!=1)ans=ans*(n-1);
 35     return ans;
 36 }
 37 int sum[maxn],siz[maxn],ci[maxn],tot=0;
 38 void updata(int o){
 39     sum[o]=(sum[o<<1]+sum[o<<1|1])%mod;
 40     siz[o]=siz[o<<1]+siz[o<<1|1];
 41 }
 42 void build(int l,int r,int o){
 43     if(l==r){
 44         sum[o]=a[l];
 45         siz[o]=1;
 46         return;
 47     }
 48     int mid=(l+r)>>1;
 49     build(l,mid,o<<1);
 50     build(mid+1,r,o<<1|1);
 51     updata(o);
 52 }
 53 bool flag=0;
 54 int qpow(int a,int b,int mod){
 55     int ans=1;
 56     bool f0=0;
 57     while(b){
 58         if(b&1){
 59             if(ans*a>=mod||f0)flag=1;
 60             ans=ans*a%mod;
 61         }
 62         if(squ(a)>=mod)f0=1;
 63         a=squ(a)%mod;
 64         b>>=1;
 65     }
 66     return ans;
 67 }
 68 int k(int a,int mod){
 69     if(a>=mod)return a%mod+mod;
 70     else return a;
 71 }
 72 void change(int l,int r,int L,int R,int o){
 73     if(l>R||r<L)return ;
 74     if(l==r){
 75         if(siz[o]){
 76             ci[l]++;
 77             sum[o]=k(a[l],fi[ci[l]]);
 78             for(int j=ci[l]-1;j>=0;j--){
 79                 flag=0;
 80                 sum[o]=qpow(C,sum[o],fi[j]);
 81                 if(flag)sum[o]+=fi[j];
 82             }
 83             if(ci[l]==tot)siz[o]=0;
 84         }
 85         return;
 86     }
 87     int mid=(l+r)>>1;
 88     if(l>=L&&r<=R){
 89         if(siz[o<<1])change(l,mid,L,R,o<<1);
 90         if(siz[o<<1|1])change(mid+1,r,L,R,o<<1|1);
 91         updata(o);
 92         return;
 93     }
 94     change(l,mid,L,R,o<<1);
 95     change(mid+1,r,L,R,o<<1|1);
 96     updata(o);
 97 }
 98 int query(int l,int r,int L,int R,int o){
 99     if(l>R||r<L)return 0;
100     if(l>=L&&r<=R)return sum[o];
101     int mid=(l+r)>>1;
102     return (query(l,mid,L,R,o<<1)+query(mid+1,r,L,R,o<<1|1))%mod;
103 }
104 main(){
105     freopen(FILE".in","r",stdin);
106     freopen(FILE".out","w",stdout);
107     n=read(),m=read(),mod=read(),C=read();
108     up(i,1,n)a[i]=read();
109     up(i,1,m)op[i]=read(),x[i]=read(),y[i]=read();
110     build(1,n,1);
111     fi[0]=mod;
112     for(int i=1;i<=m;i++){
113         fi[i]=getfi(fi[i-1]);
114         if(fi[i]==1){
115             fi[i+1]=1;
116             tot=i+1;
117             break;
118         }
119     }
120     up(i,1,m){
121         if(op[i]==0)change(1,n,x[i],y[i],1);
122         if(op[i]==1)printf("%d
",query(1,n,x[i],y[i],1));
123     }
124     return 0;
125 }
View Code

BZOJ4870

搞出DP方程,然后DP快速幂,或者矩阵快速幂任你挑.(这题可以搞NTT优化).

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define FILE "problem"
 5 #define up(i,j,n) for(int i=j;i<=n;i++)
 6 #define db long double 
 7 #define pii pair<int,int>
 8 #define pb push_back
 9 template<class T> inline bool cmin(T& a,T b){return a>b?a=b,true:false;}
10 template<class T> inline bool cmax(T& a,T b){return a<b?a=b,true:false;}
11 template<class T> inline T squ(T a){return a*a;}
12 const int maxn=110000+10,inf=1e9+10;
13 int read(){
14     int x=0,f=1,ch=getchar();
15     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
16     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
17     return x*f;
18 }
19 ll mod,n,K,r;
20 void getmod(ll& a){if(a>mod)a-=mod;}
21 struct Matrix{
22     ll num[52][52];
23     Matrix(){memset(num,0,sizeof(num));}
24     Matrix(ll a){
25         memset(num,0,sizeof(num));
26         for(int i=0;i<K;i++)
27             num[i][i]=a;
28     }
29     Matrix operator*(const Matrix& b){
30         Matrix c;
31         for(int i=0;i<K;i++)
32             for(int j=0;j<K;j++)
33                 for(int k=0;k<K;k++)
34                     getmod(c.num[i][j]+=num[i][k]*b.num[k][j]%mod);
35         return c;
36     }
37 }b,a;
38 
39 int main(){
40     freopen(FILE".in","r",stdin);
41     freopen(FILE".out","w",stdout);
42     n=read(),mod=read(),K=read(),r=read();
43     for(int i=0;i<K;i++)
44         b.num[i][(i+1)%K]++,b.num[i][i]++;
45     Matrix ans(1);
46     n=n*K;
47     while(n){
48         if(n&1)ans=ans*b;
49         b=b*b;
50         n>>=1;
51     }
52     printf("%lld
",ans.num[0][r]);
53     return 0;
54 }
View Code

BZOJ 4871

一道状态有些复杂的树形DP.

状态自行baidu.

注:此方法已被HACK,请自行找不会被卡的方法.

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define ll long long
 6 #define FILE "treediagram"
 7 #define up(i,j,n) for(int i=j;i<=n;i++)
 8 #define db long double 
 9 #define pii pair<int,int>
10 #define pb push_back
11 #define mem(a,L) memset(a,0,sizeof(int)*(L+1))
12 template<class T> inline bool cmin(T& a,T b){return a>b?a=b,true:false;}
13 template<class T> inline bool cmax(T& a,T b){return a<b?a=b,true:false;}
14 template<class T> inline T squ(T a){return a*a;}
15 const int maxn=210000+10,inf=1e9+10,mod=10003;
16 int read(){
17     int x=0,f=1,ch=getchar();
18     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
19     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
20     return x*f;
21 }
22 struct node{
23     int x,y,next;
24 }e[maxn];
25 int len,linkk[maxn],T,ch,p0,h0,p1,h1,n;
26 int vis[maxn],de[maxn],h[maxn],f[maxn],g[maxn],d[maxn];
27 void insert(int x,int y){e[++len].y=y;e[len].x=x;e[len].next=linkk[x];linkk[x]=len;}
28 struct Node{
29     int a,b;
30     Node(){a=b=0;}
31 };
32 void dp(int p){
33     if(vis[p])return;vis[p]=1;
34     int x=e[p].y,child=0;
35     Node t;
36     for(int i=linkk[x];i;i=e[i].next) if(i!=(p^1)){
37         child++;
38         dp(i);
39         cmax(d[p],d[i]);
40         if(f[i]>=t.a)t.b=t.a,t.a=f[i];
41         else if(f[i]>t.b)t.b=f[i];
42     }
43     f[p]=max(t.a,1)+child-1;
44     g[p]=max(t.a,1)+max(t.b,1)+child-2;
45     cmax(d[p],g[p]);
46 }
47 int a[5],b[3];
48 bool cmp(const int& a,const int& b){return a>b;}
49 void solve(){
50     int ans=0;
51     for(int i=2;i<=len;i++)dp(i),dp(i^1),cmax(ans,d[i]+d[i^1]);
52     for(int x=1;x<=n;x++){
53         memset(a,0,sizeof(a));
54         memset(b,0,sizeof(b));
55         for(int i=linkk[x];i;i=e[i].next){
56             a[4]=f[i];sort(a,a+5,cmp);
57             b[2]=d[i];sort(b,b+3,cmp);
58         }
59         cmax(ans,b[0]+b[1]+1);
60         cmax(ans,a[0]+a[1]+a[2]+de[x]-3);
61         cmax(ans,a[0]+a[1]+a[2]+a[3]+de[x]-4);
62     }
63     printf("%d
",ans);
64 }
65 int main(){
66     freopen(FILE".in","r",stdin);
67     freopen(FILE".out","w",stdout);
68     int T=read(),ch=read();
69     while(T--){
70         n=read();
71         if(ch)p0=read(),p1=read();
72         if(ch>1)h0=read(),h1=read();
73         if(n==1){puts("0");continue;}
74         len=1;mem(linkk,n);mem(de,n);
75         up(i,2,n){int x=read(),y=read();insert(x,y);insert(y,x);de[x]++,de[y]++;}
76         up(i,2,len)vis[i]=0,f[i]=g[i]=d[i]=0;
77         solve();
78     }
79     return 0;
80 }
View Code

BZOJ 4872

概率DP.

给个我能理解的讲解的链接:http://www.cnblogs.com/GXZlegend/p/6764969.html

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define FILE "trennen"
 5 #define up(i,j,n) for(ll i=j;i<=n;i++)
 6 #define db long double 
 7 #define pii pair<ll,ll>
 8 #define pb push_back
 9 template<class T> inline bool cmin(T& a,T b){return a>b?a=b,true:false;}
10 template<class T> inline bool cmax(T& a,T b){return a<b?a=b,true:false;}
11 template<class T> inline T squ(T a){return a*a;}
12 const ll maxn=210000+10,inf=1e9+10,mod=100003;
13 ll read(){
14     ll x=0,f=1,ch=getchar();
15     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
16     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
17     return x*f;
18 }
19 ll n,k;
20 ll a[maxn],ans=0;
21 ll fac[maxn];
22 ll qpow(ll a,ll b){
23     ll ans=1;
24     while(b){
25         if(b&1)ans=ans*a%mod;
26         a=squ(a)%mod;
27         b>>=1;
28     }
29     return ans;
30 }
31 ll vis[maxn];
32 int main(){
33     freopen(FILE".in","r",stdin);
34     freopen(FILE".out","w",stdout);
35     n=read(),k=read();
36     up(i,1,n)a[i]=read();
37     for(ll i=n;i>=1;i--){
38         ll x=a[i];
39         for(ll j=2;j*i<=n;j++)
40             x^=vis[j*i];
41         if(x)ans++,vis[i]=1;
42     }
43     fac[0]=1;for(ll i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
44     printf("%lld
",(ll)ans*fac[n]%mod);
45     return 0;
46 }
View Code

BZOJ 4873

最简单的那种最大权闭合子图.

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define ll long long
 6 #define FILE "sushi"
 7 #define up(i,j,n) for(int i=j;i<=n;i++)
 8 #define db long double 
 9 #define pii pair<int,int>
10 #define pb push_back
11 template<class T> inline bool cmin(T& a,T b){return a>b?a=b,true:false;}
12 template<class T> inline bool cmax(T& a,T b){return a<b?a=b,true:false;}
13 template<class T> inline T squ(T a){return a*a;}
14 const int maxn=510000+10,inf=1e8+10,mod=100003;
15 int read(){
16     int x=0,f=1,ch=getchar();
17     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
18     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
19     return x*f;
20 }
21 int S,T,n,m,cnt;
22 struct node{
23     int y,next,flow,rev;
24     node(int y=0,int next=0,int flow=0,int rev=0):y(y),next(next),flow(flow),rev(rev){}
25 }e[maxn];int len,linkk[maxn];
26 int v[330][330];
27 void insert(int x,int y,int flow){
28     e[++len].y=y;e[len].next=linkk[x];linkk[x]=len;e[len].flow=flow;e[len].rev=len+1;
29     e[++len].y=x;e[len].next=linkk[y];linkk[y]=len;e[len].flow=0;e[len].rev=len-1;
30 }
31 int q[maxn],d[maxn],head,tail;
32 bool makelevel(){
33     memset(d,-1,sizeof(int)*(cnt+1));
34     d[S]=0;head=tail=0;q[++tail]=S;
35     while(++head<=tail){
36         int x=q[head];
37         for(int i=linkk[x];i;i=e[i].next){
38             int y=e[i].y;
39             if(d[y]==-1&&e[i].flow)
40                 q[++tail]=y,d[y]=d[x]+1;
41         }
42     }
43     return d[T]!=-1;
44 }
45 int makeflow(int x,int flow){
46     if(x==T||!flow)return flow;
47     int maxflow=0,dis=0;
48     for(int i=linkk[x];i&&maxflow<flow;i=e[i].next){
49         int y=e[i].y;
50         if(d[y]==d[x]+1&&e[i].flow)
51             if(dis=makeflow(y,min(flow-maxflow,e[i].flow))){
52                 e[i].flow-=dis;
53                 e[e[i].rev].flow+=dis;
54                 maxflow+=dis;
55             }
56     }
57     if(!maxflow)d[x]=-1;
58     return maxflow;
59 }
60 int dinic(){
61     int ans=0,d;
62     while(makelevel())
63         while(d=makeflow(S,inf))
64             ans+=d;
65     return ans;
66 }
67 int ID1[330][330],ID2[maxn],a[maxn];
68 int main(){
69     freopen(FILE".in","r",stdin);
70     freopen(FILE".out","w",stdout);
71     n=read();m=read();
72     up(i,1,n)a[i]=read();
73     up(i,1,n)up(j,i,n){
74         v[i][j]=read();if(i==j)v[i][j]-=a[i];
75         ID1[i][j]=++cnt;
76     }
77     up(i,1,n)up(j,i,n)if(i!=j)insert(ID1[i][j],ID1[i][j-1],inf),insert(ID1[i][j],ID1[i+1][j],inf);
78     S=++cnt,T=++cnt;
79     if(m==1)up(i,1,n){
80         if(!ID2[a[i]]){
81             ID2[a[i]]=++cnt;
82             insert(ID2[a[i]],T,squ(a[i]));
83         }
84         insert(ID1[i][i],ID2[a[i]],inf);
85     }
86     int Sum=0;
87     up(i,1,n)up(j,i,n){
88         if(v[i][j]>0)insert(S,ID1[i][j],v[i][j]),Sum+=v[i][j];
89         else if(v[i][j]<0)insert(ID1[i][j],T,-v[i][j]);
90     }
91     int ans=dinic();
92     printf("%d
",Sum-ans);
93     return 0;
94 }
View Code

我们用这套题考了两天.

我的考试结果并不是很理想.

考完发现全是傻逼题.

发现了两点很不好的地方是:

1.考试时不敢想正解.(出题人语文水平高超)

2.很容易被前面的引导.(容易被出题人引导)　

考试时题面的长度不一定与难度成反比.

很多题目打暴力的难度比打正解大.

因为正解的模型我可能建过很多次,但暴力的模型我第一次建.

但有些时候打暴力比打正解划算,因为你不会正解...

所以说了这么多,你需要做的是:

考试时摆脱前面题目不会的心理负担,全力分析这道题,争取AC,当然不能AC就只能暴力了.

蛤蛤,其实我说了一堆废话.

相关推荐