【SHOI2017】解题报告

  • 本文为博主原创，未经许可不得转载

期末考试

我们发现最终的答案之和课程结束的最晚时间有关

所以朴素的思路就是枚举课程结束的最晚时间，然后计算答案

计算答案时，如果B<=A，则全部用B，否则尽量多地用A

至于满分做法，把枚举换成三分就行了

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
#include<bits/stdc++.h>
#define FILE "exam"
#define INF 1e18
#define MAXN 100100
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b) 
using namespace std;
typedef long long ll;
ll A,B,C,n,m,ans,a[MAXN],b[MAXN];
inline ll read(){
    ll x=0,f=1;  char ch=getchar();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
    while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
    return x*f;
}
ll get(ll mid){
    ll ret=0,temp=0;
    for(ll i=1;i<=n;++i)if(a[i]<mid)ret+=(mid-a[i])*C;
    if(B<=A){
        for(ll i=1;i<=m;++i)if(b[i]>mid)ret+=(b[i]-mid)*B;
        return ret;
    }
    for(ll i=1;i<=m;++i){
        if(b[i]<mid)temp+=mid-b[i];
        else{
            ll last=b[i]-mid,t=min(temp,last);
            ret+=t*A;
            temp-=t; last-=t;
            ret+=last*B;
        }
    }
    return ret;
}
int main(){
    //freopen(FILE".in","r",stdin);
    //freopen(FILE".out","w",stdout);
    A=read();  B=read();  C=read();
    n=read();  m=read();  ans=INF;
    for(ll i=1;i<=n;++i)  a[i]=read();
    for(ll i=1;i<=m;++i)  b[i]=read();
    sort(b+1,b+m+1); sort(a+1,a+n+1);
    ll l=1,r=b[m]; if(C==1e16) r=a[1];
    while(l+10<r){
        ll mid1=(r-l)/3+l,mid2=(r-l)*2/3+l;
        if(get(mid1)<=get(mid2))  r=mid2;
        else l=mid1;
    }
    for(ll i=l;i<=r;++i)  cmin(ans,get(i));
    printf("%lld\n",ans);
    return 0;
}

　　

　　

相逢是问候

首先介绍扩展欧拉定理：$a^b mod p=a^{b mod \phi(p) +\phi(p)} mod p$

然后我们发现一个数$p$，不断取欧拉函数，我们设取了$cnt$次之后变成了$1$

可以证明$cnt<=\log p$

所以我们用线段树维护即可，如果当前结点被修改的次数已经大于了$cnt$，就无需再访问了

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 50010
using namespace std;
typedef long long ll;
int n,m,c,cnt,mod[35],Time[MAXN<<2],check[MAXN<<2];
ll tr[MAXN<<2],a[MAXN];
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline ll read(){
    ll x=0,f=1;  char ch=getc();
    while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getc();}
    while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getc();}
    return x*f;
}
int mul(int a,int b,int p){
    if((ll)a*b<p) return a*b;
    else return (ll)a*b%p+p;
}
int fast(int a,int b,int p){
    int ret(1);
    for(;b;b>>=1,a=mul(a,a,p))
        if(b&1) ret=mul(ret,a,p);
    return ret;
}
int phi(int x){
    int ret=x;
    for(int i=2;i*i<=x;++i){
        if(x%i==0) ret-=ret/i;
        while(x%i==0)  x/=i;
    }
    if(x>1)  ret-=ret/x;
    return ret;
}
void relord(int p){
    check[p]|=(check[p<<1]&&check[p<<1|1]);
    tr[p]=(tr[p<<1]+tr[p<<1|1])%mod[0];
}
void build(int p,int l,int r){
    if(l==r) {tr[p]=a[l]; return;}
    int mid=(l+r)>>1;
    build(p<<1,l,mid); build(p<<1|1,mid+1,r);
    relord(p);
}
void updata(int p,int l,int r,int x,int y){
    if(check[p])  return;
    if(x>r||y<l)  return;
    if(l==r){
        Time[l]++;  if(Time[l]==cnt) check[p]=1;
        int temp=a[l];
        for(int i=Time[l]-1;i>=0;--i) temp=fast(c,temp,mod[i]);
        tr[p]=temp; return;
    }
    int mid=(l+r)>>1;
    updata(p<<1,l,mid,x,y); 
    updata(p<<1|1,mid+1,r,x,y);
    relord(p);
}
ll query(int p,int l,int r,int x,int y){
    if(x>r||y<l)  return 0;
    if(x<=l&&y>=r)  return tr[p];
    int mid=(l+r)>>1;
    return (query(p<<1,l,mid,x,y)+query(p<<1|1,mid+1,r,x,y))%mod[0];
}
int main(){
    //freopen(FILE".in","r",stdin);
    //freopen(FILE".out","w",stdout);
    n=read();  m=read();  mod[0]=read();  c=read();
    while(mod[cnt]!=1) mod[++cnt]=phi(mod[cnt-1]); mod[++cnt]=1;
    for(int i=1;i<=n;++i)  a[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;++i){
        int opt=read(),l=read(),r=read();
        if(opt==0) updata(1,1,n,l,r);
        else printf("%lld\n",query(1,1,n,l,r));
    }
    return 0;
}

　　

　　

组合数问题

首先暴力算组合数给了$60$分，出题人好良心啊

我们考虑这个和式的组合意义：在$nk$个物品中取出数量为模$k$等于$r$的物品的方案数

那么我们设$f[i][j]$表示前i个物品中选出模$k$等于$j$的数量的物品的方案数

则$f[i][j]=f[i-1][j]+f[i-1][j-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
#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
typedef long long ll;
int n,p,K,r;
ll c[55][55];
inline int read(){
    int x=0,f=1;  char ch=getchar();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
    while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
    return x*f;
}
struct node{
    ll a[55][55];
    node(){memset(a,0,sizeof(a));}
}ret,ans;
node operator *(node &a,node &b){
    node c;
    for(int i=0;i<K;++i)
        for(int j=0;j<K;++j)
            for(int k=0;k<K;++k)
                c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%p)%p;
    return c;
}
void pre(){
    for(int i=0;i<=K;++i){
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;++j)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
    }
}
int main(){
    freopen(FILE".in","r",stdin);
    freopen(FILE".out","w",stdout);
    n=read(); p=read(); K=read(); r=read(); pre();
    for(int i=0;i<K;++i)ans.a[i][i]=1;
    for(int i=0;i<K;++i)for(int j=0;j<=K;++j)(ret.a[i][(i+j)%K]+=c[K][j])%=p;
    for(int b=n;b;b>>=1,ret=ret*ret)if(b&1)ans=ans*ret;
    printf("%lld\n",ans.a[0][r]);
    return 0;
}

　　

　　

摧毁“树状图”

这是我写过的最恶心的树形dp

我很想知道出题人是怎么想出来的

随便写了一发，在bzoj上拿到了rank1，23333

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 500010
#define cmin(a,b)  a=min(a,b)
#define cmax(a,b)  a=max(a,b)
using namespace std;
struct node{int y,next;}e[MAXN<<1];
int T,opt,n,len,ans,Link[MAXN],mx[5],mxf[5],suf[MAXN],pre[MAXN],a[MAXN],f[MAXN][5];
char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read(){
    int x=0,f=1;  char ch=getc();
    while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getc();}
    while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getc();}
    return x*f;
}
void insert(int x,int y){e[++len].next=Link[x];Link[x]=len;e[len].y=y;}
void dp(int x,int fa){
    int degree=0,top=0,ret=0;
    for(int i=Link[x];i;i=e[i].next)if(e[i].y!=fa)dp(e[i].y,x),++degree;
    memset(mx,0,sizeof(mx));
    memset(mxf,0,sizeof(mxf));
    for(int i=Link[x];i;i=e[i].next)if(e[i].y!=fa){
        int y=e[i].y;
        if(f[y][0]>mx[1])        mx[4]=mx[3],mx[3]=mx[2],mx[2]=mx[1],mx[1]=f[y][0];
        else if(f[y][0]>mx[2])  mx[4]=mx[3],mx[3]=mx[2],mx[2]=f[y][0];
        else if(f[y][0]>mx[3])  mx[4]=mx[3],mx[3]=f[y][0];
        else if(f[y][0]>mx[4])  mx[4]=f[y][0];
        a[++top]=f[y][0];
        cmax(f[x][2],f[y][2]);
        cmax(f[x][2],f[y][1]+1);
        cmax(f[x][3],f[y][3]+degree-1);
        cmax(f[x][4],f[y][4]+degree-1);
        cmax(f[x][3],f[y][1]+degree-1);
        cmax(f[x][3],f[y][2]+degree-1);
        cmax(f[x][3],f[y][1]+mxf[0]+degree-2);
        cmax(f[x][3],f[y][2]+mxf[0]+degree-2);
        cmax(f[x][3],f[y][0]+mxf[1]+degree-2);
        cmax(f[x][3],f[y][0]+mxf[2]+degree-2);
        cmax(mxf[0],f[y][0]);
        cmax(mxf[1],f[y][1]);
        cmax(mxf[2],f[y][2]);
    }
    cmax(f[x][0],degree);
    cmax(f[x][0],mx[1]+degree-1);
    cmax(f[x][1],f[x][0]);
    cmax(f[x][1],mx[1]+mx[2]+degree-2);
    cmax(f[x][4],mx[1]+mx[2]+mx[3]+degree-3);
    cmax(f[x][4],mx[1]+mx[2]+degree-2);
    cmax(f[x][4],mx[1]+degree-1);
    pre[0]=suf[top+1]=0;
    for(int i=1;i<=top;++i)pre[i]=max(pre[i-1],a[i]);
    for(int i=top;i>=1;--i)suf[i]=max(suf[i+1],a[i]);
    cmax(ret,f[x][1]);
    cmax(ret,f[x][3]);
    cmax(ret,f[x][4]);
    cmax(ret,mx[1]+degree-1);
    cmax(ret,mx[1]+mx[2]+degree-2);
    cmax(ret,mx[1]+mx[2]+mx[3]+degree-3);
    cmax(ret,mx[1]+mx[2]+mx[3]+mx[4]+degree-4);
    memset(mx,0,sizeof(mx));
    memset(mxf,0,sizeof(mxf));
    for(int i=Link[x],j=1;i;i=e[i].next)if(e[i].y!=fa){
        int y=e[i].y;
        cmax(ret,f[y][0]+mxf[3]+degree-2);
        cmax(ret,f[y][3]+mx[1]+degree-2);
        cmax(ret,max(f[y][1],f[y][2])+mx[1]+mx[2]+degree-3);
        cmax(ret,f[y][0]+max(mxf[1],mxf[2])+suf[j+1]+degree-3);
        cmax(ret,max(f[y][1],f[y][2])+pre[j-1]+suf[j+1]+degree-3);
        cmax(ret,f[y][1]+mxf[1]+1-(fa?1:0));
        cmax(ret,f[y][1]+mxf[2]-(fa?1:0));
        cmax(ret,f[y][2]+mxf[1]-(fa?1:0));
        cmax(ret,f[y][2]+mxf[2]-1-(fa?1:0));
        cmax(ret,f[y][4]+mx[1]+degree-2);
        cmax(ret,f[y][0]+mxf[4]+degree-2);
        if(f[y][0]>mx[1])  mx[2]=mx[1],mx[1]=f[y][0];
        else if(f[y][0]>mx[2])  mx[2]=f[y][0];
        cmax(mxf[1],f[y][1]);
        cmax(mxf[2],f[y][2]);
        cmax(mxf[3],f[y][3]);
        cmax(mxf[4],f[y][4]);
        ++j;
    }
    cmax(ans,ret+(fa?1:0));
}
void solve(){
    n=read(); for(int i=1;i<=opt;++i) read(),read();
    for(int i=1;i<n;++i){int x=read(),y=read();insert(x,y);insert(y,x);}
    dp(1,0);  printf("%d\n",ans);
    len=ans=0;for(int i=1;i<=n;++i)Link[i]=0;
    for(int i=1;i<=n;++i)for(int j=0;j<=4;++j)f[i][j]=0;
}
int main(){
    //freopen(FILE".in","r",stdin);
    //freopen(FILE".out","w",stdout);
    T=read();  opt=read();
    while(T--) solve();
    return 0;
}

　　

　　

分手是祝愿

出这种题目名称，还赋予这种含义，出题人应该被打死

我发现我对概率与期望还是不熟悉

首先有一个结论：当前亮着的编号最大的灯，只能由自己熄灭

所以我们可以模拟一遍，算出当前必须摁灭的开关的数量$cnt$，我们称这$cnt$个操作是正确的

我们设$f[i]$表示使i个正确操作变成$i-1$个正确操作的期望步数

则$f[i]=\frac{n}{i}+1-\frac{n}{i}(f[i]+f[i+1]+1)$

整理一下得到递推式：$f[i]=\frac{(n-i)f[i+1]+n}{i}$

至于k的限制，我们特判一下就行了

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
#include<bits/stdc++.h>
#define FILE "trennen"
#define MAXN 100100
using namespace std;
typedef long long ll;
const ll mod=100003;
ll n,k,cnt,ans,f[MAXN],a[MAXN],inv[MAXN];
inline ll read(){
    ll x=0,f=1;  char ch=getchar();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
    while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
    return x*f;
}
int main(){
    //freopen(FILE".in","r",stdin);
    //freopen(FILE".out","w",stdout);
    n=read();  k=read();
    for(ll i=1;i<=n;++i) a[i]=read();
    for(ll i=n;i;--i)if(a[i]){
        for(ll j=1;j*j<=i;++j)if(i%j==0){
            a[j]^=1;  a[i/j]^=1;
            if(j*j==i) a[j]^=1;
        }
        ++cnt;
    }
    inv[1]=1;for(ll i=2;i<=n;++i)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(ll i=n;i;--i)f[i]=((n-i)*f[i+1]%mod+n)%mod*inv[i]%mod;
    if(k>cnt) ans=cnt;
    else{
        for(ll i=cnt;i>k;--i)ans=(ans+f[i])%mod;
        ans=(ans+k)%mod;
    }           
    for(ll i=1;i<=n;++i)ans=ans*i%mod;
    printf("%lld\n",ans);
    return 0;
}

　　

　　

寿司餐厅

我们注意到如果选一个区间，就必须选这个区间的子区间

选择一个区间的收益可正可负，那么这就是最大权闭合图的模型

建图上也很容易，不再详述了

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 50010
#define INF 1e9
using namespace std;
struct node{int y,next,v;}e[MAXN<<1];
int n,m,S,T,ans,cnt,len(1),Link[MAXN],level[MAXN],a[MAXN],id[MAXN],Id[110][110],v[110][110];
queue<int>q;
inline int read(){
    int x=0,f=1;  char ch=getchar();
    while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
    while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
    return x*f;
}
void insert(int x,int y,int v){
    e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;
    e[++len].next=Link[y];Link[y]=len;e[len].y=x;e[len].v=0;
}
bool bfs(){
    memset(level,-1,sizeof(level));
    q.push(S);  level[S]=0;
    while(!q.empty()){
        int x=q.front(); q.pop();
        for(int i=Link[x];i;i=e[i].next)if(level[e[i].y]==-1&&e[i].v)
            q.push(e[i].y),level[e[i].y]=level[x]+1;
    }
    return level[T]>=0;
}
int MAXFLOW(int x,int flow){
    if(x==T)  return flow;
    int d=0,maxflow=0;
    for(int i=Link[x];i&&maxflow<flow;i=e[i].next)
        if(level[e[i].y]==level[x]+1&&e[i].v)
            if(d=MAXFLOW(e[i].y,min(e[i].v,flow-maxflow)))
                e[i].v-=d,e[i^1].v+=d,maxflow+=d;
    if(!maxflow)  level[x]=-1;
    return maxflow;
}
int main(){
    //freopen(FILE".in","r",stdin);
    //freopen(FILE".out","w",stdout);
    n=read();  m=read();  S=0;  T=++cnt;
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)for(int j=i;j<=n;++j)v[i][j]=read();
    for(int i=1;i<=n;++i){
        v[i][i]-=a[i];  Id[i][i]=++cnt;
        if(!id[a[i]])  id[a[i]]=++cnt,insert(id[a[i]],T,a[i]*a[i]*m);
        insert(Id[i][i],id[a[i]],INF);
        if(v[i][i]<0)  insert(Id[i][i],T,-v[i][i]);
        else insert(S,Id[i][i],v[i][i]),ans+=v[i][i];
    }
    for(int len=2;len<=n;++len)for(int i=1;i<=n;++i){
        int j=i+len-1;
        Id[i][j]=++cnt;
        insert(Id[i][j],Id[i][j-1],INF);
        insert(Id[i][j],Id[i+1][j],INF);
        if(v[i][j]<0)  insert(Id[i][j],T,-v[i][j]);
        else insert(S,Id[i][j],v[i][j]),ans+=v[i][j];
    }
    int d=0;
    while(bfs()) while(d=MAXFLOW(S,INF)) ans-=d;
    printf("%d\n",ans);
    return 0;
}

　　

　　

总结

这场比赛我拿到了182分，分别是10+40+65+52+0+15

如果这是我省省选，我现在应该就已经退役了

考试中有不少遗憾，比如：

T1的70分暴力没有拿到

T2和T3和T4的暴力分拿的很足不说了

T5爆零十分遗憾，因为直接输出最小步数就有80分

T6我想出了最大权闭合图的模型，但是不会做最大权闭合图

如何尽量避免这些问题？

我想只能靠平时的查漏补缺了

本文标题:【SHOI2017】解题报告

文章作者:chty

发布时间:2017年05月02日 - 21时37分

最后更新:2017年05月04日 - 15时00分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
  1. 1. 期末考试
  2. 2. 相逢是问候
  3. 3. 组合数问题
  4. 4. 摧毁“树状图”
  5. 5. 分手是祝愿
  6. 6. 寿司餐厅
  7. 7. 总结
,