常州day12

1

字符串处理,水

2

栈和贪心,自找规律,栈的先入后出符合区间不相交要求,引用:发现当前栈内元素与 a[i]不同时,首先退栈直到栈内元素值小于a[i]等于 ,随后加入一个修改操作补齐差值即可。

4

类安装雷达,考虑在排除两边山后的其他山遮挡

 

常州集训day13

T1.sifra

简单字符串,找到所有数字判断存在个数

T2.po

栈+贪心

手动模拟要做的事找到规律

我们可以用栈来维护一个修改操作的数值以及左端点进行扫描。由于区间之间互不相交或者互相包含,所以区间之间的出入关系满足栈的限制。发现当前栈内元素与 a[i]不同时,首先退栈直到栈内元素值小于a[i]等于 ,随后加入一个修改操作补齐差值即可。

T4.Planine

注意到,对于每一个山谷,存在一个 坐标的区间,在这个区间上放置精灵可以照亮这个山谷。

将每个山谷要被照到的精灵所在位求出来,会得出多个区间(注意会被山脉阻挡),然后就是区间覆盖问题。

。。。。。。见鬼的捆绑测试

CZOI-SCZ-DAY10

记录一下可能是这个月最后一篇BLOG。

DAY10的题只能补出来200pts了,T3、T4不是分治+双指针,就是线段树,T5的原理和代码长度令人不解。

[Patkic]

题意:给你一个地图,最开始时你可以向上下左右走一步,随后只能顺着洋流飘,问能否到达终点。

只需要最开始的时候暴力去判断,至于字典序的问题,我们可以按照东(E),北(N),南(S),西(W)来搜索就可以了。

具体的细节还是挺多的。


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
#include<bits/stdc++.h>
using namespace std;
int n,m,st[105][105];
char Map[105][105];
int dfs(int x,int y,int ans)
{
    if(x<0||x>=n||y<0||y>=m)return -1;
    if(Map[x][y]=='x')return ans;
    if(Map[x][y]=='o'||Map[x][y]=='.'||st[x][y])return -1;
    st[x][y]=1;
    if(Map[x][y]=='<')return dfs(x,y-1,ans+1);
    else if(Map[x][y]=='>')return dfs(x,y+1,ans+1);
    else if(Map[x][y]=='^')return dfs(x-1,y,ans+1);
    else if(Map[x][y]=='v')return dfs(x+1,y,ans+1);
}
int main()
{
    freopen("patkice.in","r",stdin);
    freopen("patkice.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=0;i<n;i++)
    {
        scanf("%s",Map[i]);
        for(int j=0;j<m;j++)
        {
            if(Map[i][j]=='o')
            {
                x=i;
                y=j;
                break;
            }
        }
    }
    vector<pair<int,char> >V;
    memset(st,0,sizeof st);
    int tmp=dfs(x,y+1,0);
    if(tmp!=-1)V.push_back({tmp,'E'});
    memset(st,0,sizeof st);
    tmp=dfs(x-1,y,0);
    if(tmp!=-1)V.push_back({tmp,'N'});
    memset(st,0,sizeof st);
    tmp=dfs(x+1,y,0);
    if(tmp!=-1)V.push_back({tmp,'S'});
    memset(st,0,sizeof st);
    tmp=dfs(x,y-1,0);
    if(tmp!=-1)V.push_back({tmp,'W'});
    if(!V.size())printf(":(");
    else
    {
        sort(V.begin(),V.end());
        printf(":)\n%c",V.front().second);
    }
    return 0;
}

[Bajka]

一个DP。

设f[i][j]表示我们位于不喜欢的串的第i个位置,下一个字符为喜欢的串的第j位的代价。

有f[i][j]=min(f[k][j-1]+c)(满足s[i]=s[k-1] or s[i]=s[k+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
#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int n,m,idx[N],f[N][N];
char a[N],b[N];
vector<int>pos[30];
int main()
{
    freopen("bajka.in","r",stdin);
    freopen("bajka.out","w",stdout);
    scanf("%d%d%s%s",&n,&m,a+1,b+1);
    for(int i=1;i<=n;i++)
    {
        pos[a[i]-'a'].push_back(i);
        idx[i]=pos[a[i]-'a'].size()-1;
    }
    if(!pos[a[1]-'a'].size())
    {
        puts("-1");
        return 0;
    }
    for(int i=2;i<=m;i++)
    {
        vector<int>&u=pos[b[i]-'a'];
        for(int j=0;j<u.size();j++)
        {
            f[i][j]=1e9;
            if(a[u[j]-1]==b[i-1])f[i][j]=min(f[i][j],f[i-1][idx[u[j]-1]]+1);
            if(a[u[j]+1]==b[i-1])f[i][j]=min(f[i][j],f[i-1][idx[u[j]+1]]+1);
        }
        for(int j=1;j<u.size();j++)f[i][j]=min(f[i][j],f[i][j-1]+u[j]-u[j-1]);
        for(int j=u.size()-2;~j;j--)f[i][j]=min(f[i][j],f[i][j+1]+u[j+1]-u[j]);
    }
    int res=1e9;
    for(int i=0;i<pos[b[m]-'a'].size();i++)res=min(res,f[m][i]);
    printf("%d",res==1e9?-1:res);
    return 0;
}

常州DAY10

附:T4随机化代码


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
#include<bits/stdc++.h>
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define drp(i,j,k) for(int i=(j);i>=(k);--i)
using namespace std;
inline int read(){
    int x=0,f=0;char ch;
    while(!isdigit(ch=getchar())) f|=ch=='-';
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return f?-x:x;

}
inline int max3(int x,int y,int z){return max(max(x,y),z);}
inline int min3(int x,int y,int z){return min(min(x,y),z);}
inline int jc3(int x,int y,int z){return max3(x,y,z)-min3(x,y,z);}
//------------------------------------------------------//
const int N=2e5+5;
int n,ans=N;
int fir[N],nex[N<<1],to[N<<1],pos;
void add(int x,int y){
    to[++pos]=y;nex[pos]=fir[x];fir[x]=pos;
    std::swap(x,y);
    to[++pos]=y;nex[pos]=fir[x];fir[x]=pos;
}

int siz[N],dep[N],fa[N][21];
int leaf[N],cnt;
void dfs1(int u,int f){
    dep[u]=dep[fa[u][0]=f]+1;siz[u]=1;
    for(int i=fir[u];i;i=nex[i]){
        int v=to[i];
        if(v==f) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
    }
    if(siz[u]==1) leaf[++cnt]=u;
}
int lca(int x,int y){
    if(dep[x]<dep[y]) std::swap(x,y);
    drp(i,17,0) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    drp(i,17,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return x==y?x:fa[x][0];
}
int w(int x,int y){
    int z=lca(x,y);
    if(x==z||y==z){
        if(dep[x]<dep[y]) std::swap(x,y);
        return jc3(siz[x],siz[z]-siz[x],n-siz[z]);
    }
    else return jc3(siz[x],siz[y],n-siz[x]-siz[y]);
}


void find(int root,int k){
    if(ans!=N&&n<=2000) return ;
    dfs1(root,0);
    rep(i,1,17) rep(u,1,n)
      fa[u][i]=fa[fa[u][i-1]][i-1];
    if(n<=2000){
        if(ans!=N) return;
        rep(i,1,n) rep(j,1,n)
          ans=std::min(ans,w(i,j));
        return ;
    }

    int tim=40;
    while(tim--){
        int x,y;
        if(tim&1) {
            x=leaf[rand()%cnt+1];
            y=leaf[rand()%cnt+1];
        }
        else {
            x=rand()%n+1;
            y=rand()%n+1;
        }  
        bool con=true;
        int now=w(x,y);
        while(con) {
            con=false;
            drp(i,k,0) if(fa[x][i]) {
                int ne=w(fa[x][i],y);
                if(ne>now) continue;
                x=fa[x][i]; now=ne;
                con=true;
            }
            if(!con) {
                std::swap(x,y);
                drp(i,0,0) if(fa[x][i]) {
                    int ne=w(fa[x][i],y);
                    if(ne>now) continue;
                    x=fa[x][i]; now=ne;
                    con=true;
                }
            }
            if(rand()&1)std::swap(x,y);
        }
        ans=std::min(ans,now);
    }
}

signed main(){
    srand(time(0));
    freopen("papricice.in","r",stdin);
    freopen("papricice.out","w",stdout);
    n=read();
    rep(i,1,n-1) add(read(),read());
    rep(i,1,5) find(rand()%n+1,i),cnt=0;
    printf("%lld\n",ans);
}

常州集训day11

T1.pizza
简单题,判断讨厌的配料是否出现出现就不要

T2.Vepar
数据范围n<=10^7
欧拉筛法可以过
但是数据范围太大
所以直接枚举a到b中各个数的质因子会炸
考虑优化:
枚举质因数
一个区间的质因数等于从一到区间末尾这个质数减去从一到这个区间起点减一
要求是每个质因数在被整除数的量更多
问题就解决了

T4.janjetina
15分:
暴力枚举每个起点,跑最短路,判断每两个点
100分:
点分治,线段树……##@!¥#¥#@不会

T5.Patkice II
看起来没看懂……
然后发现是01最短路
跑最短路
将需要变的情况当做边长为1
需要路径储存

长乐集训(眠)Day12

傻逼PKM,机惨了我的手机,发了一堆消息,以及某位大佬的照片

我们还是先了解一下DP最基本的概念

DP:

动态静态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果

——百度百科

其实DP中最重要的三个东西就是:初始状态转移方程还有目标状态,这三个东西有时确实让人抓狂,对于状态转移的设计和优化也很重要(不然就等着TLE吧)

 

今天学的是背包DP和区间DP,这俩玩意儿以前就学过,所以今天做题非常轻松共计11道,背包部分差点AK,算这几天里效率较高的一天,DP真简单

一下为正文:

背包DP:

一般分为两种:0/1背包完全背包,是DP中最简单的一类

0/1背包:

有N个物品和容量为M的背包,每个物品重Wi,价值为Vi,在不超过背包承载量的情况下,如何使状的物品价值最,大每个物品只可以选一次

思路:

设DP(i,j)表示考虑到第i个物品,背包称重量为j时的最大价值

方程如下:

DP(i,j)=max( DP(i,j) , DP(i-1,j-Wi)+Vi )

又因为每一次状态转移只与上一行有关系,滚动掉一维,变为:

DP(i)=max(DP(i),DP(i-Wi)+Vi)

初值DP(0)=0,其它为负无穷,目标max(DP(i))

代码如下:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
 
int main(){
   
    int n,c;
    cin>>c>>n;//读入背包称重量和物品个数
    int w[n+1],v[n+1],f[c+1];
    for(int i=1;i<=n;i++) cin>>w[i]>>v[i];//读入物品重量和价值
    memset(f,0,sizeof f);
   
    for(int i=1;i<=n;i++){
        for(int j=c;j>=w[i];j--){//为了滚动掉一维,要从后往前推就可以保留上一行状态
            f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
    }
   
    cout<<f[c];
    return 0;
   
}

完全背包:

有N个物品和容量为M的背包,每个物品重Wi,价值为Vi,在不超过背包承载量的情况下,如何使状的物品价值最大,每个物品可以选多次

DP(0,0)=0,其它为负无穷,目标max(DP(N,j))

方程:

DP(i,j)=max(DP(i-1),DP(i,j-Wi)+Vi)

同样可以滚动掉一维:

核心代码:


1
2
3
4
5
6
7
8
9
10
int f[c+1];// 商品编号从1开始及至n
for(int i=1;i<=n;i++)
{// 注意, 从左边开始计算
    for(int j=w[i];j<=c;j++)
    {
        f[j]=max(f[j],f[j-w[i]]+v[i]);
    }
}
// 最终(c条件下)
cout<<f[c];

另外,还衍生出了一种多重背包,题目一样,只不过改成每个物品最多可以取Ui次,我们可以吧这几个物品看成多个物品来当01背包,这里引入二进制优化,依据是二进制唯一分解定理所以Ui就可以表示为一串二的整次方这些也可以小于Ui的任意正整数

比如今天的T3


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 N 100100
#define M 200000
using namespace std;
int n,c,tot,v[N],w[N],dp[M];
int main()
{
    scanf("%d%d",&n,&c);
    int x,y,z;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        for(int j=1;j<=z;j<<=1)
        {
            tot++;
            v[tot]=x*j;
            w[tot]=y*j;
            z-=j;
        }
        if(z)
        {
            tot++;
            v[tot]=x*z;
            w[tot]=y*z;
        }
    }
    for(int i=1;i<=tot;i++)
    {
        for(int j=c;j>=w[i];j--)
        {
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    printf("%d",dp[c]);
    return 0;
}

还有有依赖背包,比如选了物品A就一定要选物品B,有时可以用树状DP来解决有时也可以用背包,比如今天T4:


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
#include<bits/stdc++.h>
#define N 110
#define M 100010
using namespace std;
int n,m,ans,a[N],c[N],cnt[M];
bool dp[M];
void Aha()
{
    scanf("%d%d",&n,&m);
    if(n==0&&m==0) exit(0);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    memset(dp,0,sizeof dp);
    dp[0]=true;
    for(int i=1;i<=n;i++)
    {
        memset(cnt,0,sizeof cnt);
        for(int j=a[i];j<=m;j++)
        {
            if(!dp[j]&&dp[j-a[i]]&&cnt[j-a[i]]+1<=c[i])
            {
                dp[j]=true;
                cnt[j]=cnt[j-a[i]]+1;
            }
        }
    }
    ans=0;
    for(int i=1;i<=m;i++)
    {
        if(dp[i]) ans++;
    }
    printf("%d\n",ans);
}
int main()
{
    while(true) Aha();
    return 0;
}

区间DP

在区间上DP,一区间长度划分阶段,记录两个端点坐标,依赖合并小区间来求解大区间,依赖于区间枚举分割点,复杂度一般为O(N^3),有点慢,可还是比dfs好

T1:

思路拆环成链,相当于把链拆开然后复制一个一样的链接在当前链的末尾,然后进行DP,DP(i,j)表示合并i-j区间的最小代价,初始DP(i,i)=1,目标DP(i,n)方程:

DP(i,j)=min(DP(l,k-1)+DP(k,r))+a(l)+a(l+1)……a(r)


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
#include<bits/stdc++.h>
#define N 100*2+10
using namespace std;
int n,r,a[N],dpmax[N][N],dpmin[N][N],sum[N];
//dp[i][j]:将i-j区间合并分数最大/小值
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[n+i]=a[i];
    }
    memset(dpmin,0x3f,sizeof dpmin);
    for(int i=1;i<=2*n;i++)
    {
        sum[i]=sum[i-1]+a[i];
        dpmin[i][i]=0;
    }
    for(int i=1;i<=n;i++)
    {      
        for(int l=1;l+i-1<=2*n;l++)
        {
            r=l+i-1;
            for(int k=l;k+1<=r;k++)
            {
                dpmax[l][r]=max(dpmax[l][r],dpmax[l][k]+dpmax[k+1][r]+sum[r]-sum[l-1]);
                dpmin[l][r]=min(dpmin[l][r],dpmin[l][k]+dpmin[k+1][r]+sum[r]-sum[l-1]);
            }
        }
    }
    int Min=INT_MAX,Max=INT_MIN;
    for(int i=1;i<=n;i++)
    {
        Min=min(Min,dpmin[i][i+n-1]);
        Max=max(Max,dpmax[i][i+n-1]);
    }
    printf("%d\n%d",Min,Max);
    return 0;
}

T2:

同理:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define N 55
using namespace std;
char s[N];
int n,dp[N][N];
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    memset(dp,0x7f,sizeof dp);
    for(int i=1;i<=n;i++) dp[i][i]=1;
    for(int le=2;le<=n;le++)
    {
        for(int l=1;l+le-1<=n;l++)
        {
            int r=l+le-1;
            if(s[l]==s[r]) dp[l][r]=min(dp[l][r-1],dp[l+1][r]);
            else for(int k=l+1;k<=r;k++) dp[l][r]=min(dp[l][r],dp[l][k-1]+dp[k][r]);
        }
    }
    printf("%d",dp[1][n]);
    return 0;
}

T3:

运用搜索多加一维,k表示合并后r节点后还有多少个相同的色块


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
#include<bits/stdc++.h>
#define N 201
using namespace std;
int cnt,n,tot,d[N],len[N],col[N],dp[N][N][N];
int dfs(int i,int j,int k)
{
    if(dp[i][j][k]) return dp[i][j][k];
    if(i==j) return (len[j]+k)*(len[j]+k);
    dp[i][j][k]=dfs(i,j-1,0)+(len[j]+k)*(len[j]+k);
    for(int l=i;l<j-1;l++)
    {
        if(col[l]==col[j]) dp[i][j][k]=max(dp[i][j][k],dfs(i,l,len[j]+k)+dfs(l+1,j-1,0));
    }
    return dp[i][j][k];
}
void Aha()
{
    memset(dp,0,sizeof dp);
    memset(col,0,sizeof col);
    memset(len,0,sizeof len);
    tot=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&d[i]);
        if(d[i]!=d[i-1])
        {
            tot++;
            col[tot]=d[i];
        }
        len[tot]++;
    }
    cnt++;
    printf("Case %d: %d\n",cnt,dfs(1,tot,0));  
}

signed main()
{
    int T;
    scanf("%d",&T);
    while(T--) Aha();
    return 0;
}

今天的博客又完了,明天要学习数位DP和树形DP,晚上就回泉州啦(我爱泉州一中)

 

都怪PKM