Atcoder abc 233 题解_atcoder dfs 剪枝

Atcoder abc 233 题解

A 10yen Stamp

答案就是两个数字的差/10之后上取整
记得判断res=0的情况就可以了

c++代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

int main()
{
    int x,y;
    scanf("%d %d",&x,&y);
    if(x>=y)
    {
        puts("0");
        return 0;
    }
    else
    {
        int t=ceil(1.0*(y-x)/10);
        cout<<t<<endl;
        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

B - A Reverse

题意

第一行输入一个$L$, $R$
第二行输入一个字符串 $S$
输出将字符串$S$ 的第$L$到$R$的子串

c++代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1e5+10;
char s[N];

int main()
{
    int l,r;
    cin>>l>>r;
    cin>>s+1;
    string res;
    int n=strlen(s+1);
    int mid=(l+r)>>1;
    for(int i=1;i<=n;i++)
    {
        if(i>=l&&i<=mid) swap(s[i],s[l+r-i]);
    }
    cout<<(s+1)<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

C - Product

题意

有$N$个背包, 背包$i$里面装了$L_i$个球, 每个球的的质量为$a_i,j$, 问有多少种方式可以在每个包里面选择一个球使选择的球的质量的乘积为$N$

思路

根据题目给的数据范围可以知道所有包中的球数量的乘积最多是$10^5$,所以这一题用dfs
dfs的参数：选择到了第几组，现在的乘积是多少
剪枝：当乘积大于$X$需要剪枝
注意：需要开ll 要不然会爆掉

c++代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<unordered_map>

using namespace std;

typedef long long ll;


const int N=1e5+10;
vector<ll> a[N];
ll sum;
int n;
int res=0;

void dfs(ll pos,ll now)//选择到了第几个背包 现在背包的重量是多少
{
    if(pos==n)//递归出口 全部处理完
    {
        if(now==sum) res++;
        return ;
    }
    for(int i=0;i<a[pos].size();i++)//枚举这个背包里面选择哪一个
    {
        if((ll)a[pos][i]*now>sum) continue;//剪枝
        else 
        {
            dfs(pos+1,now*a[pos][i]);
        }
    }
}

int main()
{
    cin>>n>>sum;
    for(int i=0;i<n;i++)
    {
        int s;
        scanf("%d",&s);
        for(int j=0;j<s;j++)
        {
            int x;
            scanf("%d",&x);
            a[i].push_back(x);
        }
    }
    dfs(0,1);
    cout<<res<<endl;
}
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

D - Count Interval

题意

给一个数组$A$和一个整数$K$,计算有多少个$($$L$,$R$$)$满足数组A的[L,R]的和为K

思路

这是一道很简单的前缀和问题
设Sum[]是数组A的前缀和数组，数组A在[L,R]的和就是Sum[r]-Sum[L-1]
那么在这里我们只需要用map记录一下前缀和出现的次数然后进行计算就可以啦
注意：记得开long long 初始化mp[0]=1(选择的L为1的时候)

c++代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>

using namespace std;
typedef long long ll;

const int N=2e5+10;

ll a[N];
ll k;
int n;
unordered_map<ll,int> mp;

int main()
{
    cin>>n>>k;
    mp[0]=1;
    ll sum=0;
    ll res=0;
    for(int i=1;i<=n;i++)
    {
        ll x;
        scanf("%lld",&x);
        sum+=x;
        res+=mp[sum-k];
        mp[sum]++;
    }
    cout<<res<<endl;
}
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

E - Σ[k=0…10^{100]floor(X／10}k)

题意

计算题目所给出式子的值

思路

手动模拟一下可以得到这个

 123456
+ 12345.6
+  1234.56
+   123.3456
+    12.3456
+     1.3456
--------------
=137171

1
2
3
4
5
6
7
8
9

这么一看思路就很简单了
倒数第一位 = 1 + 2 + 3 + 4 + 5 + 6
倒数第二位 = 1 + 2 + 3 + 4 + 5
倒数第三位 = 1 + 2 + 3 + 4
倒数第四位 = 1 + 2 + 3
倒数第五位 = 1 + 2
倒数第六位 = 1
由于数据很大 所以需要用string存下来再进行计算

c++代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;
string x;
int n;

void print(vector<int> &res)
{
    for(auto t:res) cout<<t;
    cout<<endl;
}

int main()
{
    cin>>x;
    n=x.size();
    int sum=0;
    for(int i=0;i<n;i++)
    {
        sum+=x[i]-'0';
    }
    vector<int> res;
    int t=0;
    for(int i=n-1;i>=0;i--)
    {
        t+=sum;
        res.push_back(t%10);
        t/=10;
        sum-=(x[i]-'0');
    }
    if(t) res.push_back(t);
    reverse(res.begin(),res.end());
    print(res);
}
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

F - Swap and Sort

题意

给你一个全排列$P_i$，再给$M$种操作，第$i$种操作可以交换P中的$a_i$与$b_i$位置上的数字
问能否在$5\ast 10^5$个操作之内让P变为有序
如果可以输出顺序，不可以输出-1

思路

这一题其实是AcWing4084号码牌的简化版
先来讲讲4084
其实这一题的算法很简单只不过思路难度中等偏上
我们将这个问题想象成一个图，将可达的两个点中间连一条边
那么最终的问题就转化成了能否通过交换操作使得每个点的a[i]变为i
那就很自然的就想到了并查集（联通块+可达问题），只要在一个联通块里面，那么a[i]就是可以通过交换操作变为i的。

c++代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=110;

int f[N],a[N],d[N];
int n;

int find(int x)
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}

void merge(int a,int b)
{
    a=find(a);
    b=find(b);
    f[a]=b;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=n;i++)
    {
        if(i-d[i]>=1) merge(i-d[i],i);
        if(i+d[i]<=n) merge(i+d[i],i);
    }
    for(int i=1;i<=n;i++)
    {
        int aa=find(i);
        int bb=find(a[i]);
        if(aa!=bb)
        {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
}
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

这一题与号码牌这一题不同的就是，我们的目的就是不仅要判断能否可以通过交换使a[i]=i同时要记录交换的路径
我们的思路就是：
1.找叶子结点(用一个结点来处理整个联通块)
2.对于每个叶子结点需要讲a[i]变为i需要从哪个点转换过来(dfs 就是通过加边要a[i]与i直接可达)
dfs(u,v,fa):u是目前所在的节点 目的:s[u]=v fa是父节点为了防止递归回去
当s[u]==v说明我们找到了这个节点return true
此时我们需要将s[u]与s[j]交换 并且将这条边加入ans

c++代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<queue>

using namespace std;

const int N=5e5+10,M=2*N;

int f[N],s[N];
int e[M],ne[M],h[N],id[N],idx;
bool st[N];
vector<int> ans;

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    id[idx]=c;
    h[a]=idx++;
}

int find(int x)
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}

bool merge(int a,int b)
{
    a=find(a);
    b=find(b);
    if(a!=b) 
    {
        f[a]=b;
        return true;
    }
    return false;
}

bool dfs(int u,int v,int fa)//将s[u]改为v
{
    if(s[u]==v) return true;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        if(dfs(j,v,u))
        {
            swap(s[u],s[j]);
            ans.push_back(id[i]);
            return true;
        }
    }
    return false;
}

void leaf(int u)
{
    st[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(st[j])continue;
        leaf(j);
    }
    dfs(u,u,-1);
}

int main()
{
    memset(h,-1,sizeof h);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=n;i++) scanf("%d",&s[i]);
    int m;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        if(merge(a,b))
        {
            add(a,b,i);
            add(b,a,i);
        }
    }
    //当(st[i],i)在一个联通块里面就可以交换--->构造生成树
    for(int i=1;i<=n;i++)
    {
        int a=find(s[i]);
        int b=find(i);
        if(a!=b)
        {
            puts("-1");
            return 0;
        }
    }
    //1.找到叶子结点
    for(int i=1;i<=n;i++)
    {
        if(!st[i]) 
        {
            leaf(i);
            // cout<<"i = "<<i<<endl;
        }
    }
    cout<<ans.size()<<endl;
    for(auto t:ans) cout<<t<<" ";
    cout<<endl;
}

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

G - Strongest Takahashi

题意

现在有一个NxN的方格，由‘#’与‘.’组成，现在需要消灭里面所有的‘#’，每次可以每次选择一个正整数D每次消灭D*D的矩阵中的‘#’，花费为D，求消灭所有‘#’的最小花费

思路

算法：dp
dp[x1][y1][x2][y2]:消灭(x1,y1),(x2,y2)内所有的’#'所需要的最小操作次数
每次状态转移的方式有2种,一种横着切一刀一种竖着切一刀

因为我比较懒所以就用的记忆画搜索嘿嘿

c++代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=60;
int n;
char g[N][N];
int f[N][N][N][N];

int dp(int r1,int c1,int r2,int c2)
{
    if(f[r1][c1][r2][c2]!=-1) return f[r1][c1][r2][c2];
    if(r1==r2&&c1==c2) return g[r1][c1]=='#';
    f[r1][c1][r2][c2]=max(r2-r1+1,c2-c1+1);
    for(int i=r1;i<r2;i++) f[r1][c1][r2][c2]=min(f[r1][c1][r2][c2],
    dp(r1,c1,i,c2)+dp(i+1,c1,r2,c2));
    for(int i=c1;i<c2;i++) f[r1][c1][r2][c2]=min(f[r1][c1][r2][c2],
    dp(r1,c1,r2,i)+dp(r1,i+1,r2,c2));
    return f[r1][c1][r2][c2];
}

int main()
{
    memset(f,-1,sizeof f);
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%s",g[i]+1);
    cout<<dp(1,1,n,n)<<endl;
}
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

Ex - Manhattan Christmas Tree

题意

在二维坐标系下有N个圣诞树，每个圣诞树的坐标是($x_i$,$y_i$)
接下来有Q个询问
对于每个询问给出3个整数a,b,k 你要找出距离(这里的距离指的是曼哈顿距离)在(a,b)之间距离这个点第k近的圣诞树的距离

算法

(二分+树状数组)

首先引入知识点 曼哈顿距离与切比雪夫距离的转化
因为对于曼哈顿距离我们并不是很好求第k小的距离，所以在这里引入切比雪夫距离，这样就讲第k小的距离转换成为计算矩形中点的个数
首先将坐标点($x_i$,$y_i$)转化成($x_i$ + $y_i$, $x_i$ - $y_i$)
因为树状数字中不出现0 所以在这里我们将($x_i$,$y_i$)转化成($x_i$ + $y_i$ + 1, $x_i$ - $y_i$ + 1)
怎样计算矩形中点的个数呢？
在这里采用树状数组来存储每个转化后的x坐标对应的每个y
那样每次计算dis在(a,b)的个数就是寻找 大于b的所有点的数量-大于等于a的所有点的数量
我们知道怎么求矩形中点的个数就可以开始二分了，在这里我们二分的是距离
每次check(a,b,k,mid)
首先要把(a,b)转换为切比雪夫坐标再进行计算(xx-mid,xx+mid,yy-mid,yy+mid)这个矩形中点的个数
需要注意的是 因为在这里我们需要所有的tr[i]中的点是有序的，所以我们在这里需要将切比雪夫坐标系按照y排序在进行加入树状数组中

c++代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef pair<int,int> pii;
#define x first
#define y second
const int N=2e5+10;
pii a[N];
vector<int> tr[N];
int n;

int lowbit(int x)
{
    return x&(-x);
}

void add(int x,int y)
{
    for(int i=x;i<N;i+=lowbit(i))
        tr[i].push_back(y);
}

int sum(int x,int a,int b)
{
    int res=0;
    int i=x;
    for(;i;i-=lowbit(i))
    {
        res+=upper_bound(tr[i].begin(),tr[i].end(),b)-lower_bound(tr[i].begin(),tr[i].end(),a);
    }
    return res;
}

int query(int x,int y,int a,int b)
{
    x=max(x,1);
    y=max(y,0);
    x=min(x,N-1);
    y=min(y,N-1);
    return sum(y,a,b)-sum(x-1,a,b);
}

bool check(int x,int y,int k,int mid)
{
    int xx=x+y+1;
    int yy=x-y+1;
    return query(xx-mid,xx+mid,yy-mid,yy+mid)>=k;
}

static bool cmp(pii a,pii b)
{
    return a.y<b.y;
}

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        a[i]=make_pair(x+y+1,x-y+1);
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        add(a[i].x,a[i].y);
    }
    int q;
    cin>>q;
    while(q--)
    {
        int a,b,k;
        scanf("%d %d %d",&a,&b,&k);
        int l=0,r=2e5+10;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(check(a,b,k,mid)) r=mid;
            else l=mid+1;
        }
        printf("%d\n",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
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