纸钱晚风送，谁家又添新痛。

AtCoder Beginner Contest 184

A

B

两个签到

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+100;
int a[N];
int main()
{
       int a,b,c,d;
       cin>>a>>b>>c>>d;
       cout<<a*d-b*c; 
    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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+100;
int a[N];
int main()
{
    ll n,x;
    string s;
    cin>>n>>x;
    cin>>s;
    for(int i=0;i<=s.length()-1;i++)
    {
if(s[i]=='o')
{
    x++;
}
else
{
    if(x>0)
    x--;
}

    }
    cout<<x;
    return 0;
}

C

总共可以走一步，二步，三步，我觉得三步之后一定能够走完，因此可以直接进行判断

如果是0就是重合

如果是1就是题意得情况进行模拟

如果是2，它可以是斜着走加短距离，斜着走加斜着走，短距离加短距离，赛时短距离加短距离忘想了，但还是冲过去了。

剩下的三步即可。

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>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= ni--)
const int N = 1e5 + 100;

int main()
{
int a,b,c,d;
cin>>a>>b>>c>>d;
if(a==c&&b==d)
{
    cout<<0;
    return 0;
}
if(a+b==c+d||a-b==c-d||abs(a-c)+abs(b-d)<=3)
{
    cout<<1;
    return 0;
}
if(((d-c)&1)==((b-a)&1))
{
    cout<<2;
    return 0;
}
if(abs(c+d-a-b)<=3)
{
    cout<<2;
    return 0;
}
if(abs(abs(a-b)-abs(c-d))<=3)
{
    cout<<2;
    return 0;
}
if(abs(a-c)+abs(b-d)<=6)
{
    cout<<2;
    return 0;
}
cout<<3;
return 0;
}

D

期望dp，直接定义dp[a][b][c]为到结果得步数，然后逆推走期望dp即可。

非常典型得期望dp，直接从结果推回来即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
double dp[110][110][110];
int a,b,c;
int main()
{
cin>>a>>b>>c;
dp[100][100][100]=0;
for(int i=99;i>=a;i--)
{
    for(int j=99;j>=b;j--)
    {
        for(int k=99;k>=c;k--)
        {
            dp[i][j][k]+=((dp[i+1][j][k]+1.0)*(i*1.0)+(dp[i][j+1][k]+1.0)*j*1.0+(dp[i][j][k+1]+1.0)*k*1.0)/(i+j+k);
        }
    }
}
printf("%.9lf",dp[a][b][c]);

return 0;
}

E

考验基本功的bfs，主要就是有一个点，就是一个字母之前跳过了以后就没必要跳了，这样其实复杂度和普通的bfs是没有太大去别的。

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
#include <bits/stdc++.h>
using namespace std;
const int N=2001;
char a[N][N];
bool vis[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
queue<pair<int,int> >q;
//还需要开一个东西去存这个字母
vector<pair<int,int> >p[50];
int dp[2020][2020];
int vvis[N];
//整体思路应该就是直接bfs
//有一个需要优化的点就是只要传送门走过一次了，就绝对不会再走这个传送门了
//因为他不是强制传送
//因此直接这样即可

int main()
{
int h,w;
cin>>h>>w;
int mx,my;
for(int i=1;i<=h;i++)
{
    for(int j=1;j<=w;j++)
    {
        cin>>a[i][j];
        if(a[i][j]=='S')
        {
            q.push({i,j});
            vis[i][j]=1;
        }
        if(a[i][j]>='a'&&a[i][j]<='z')
        {
            p[a[i][j]-'a'].push_back({i,j});
        }
        if(a[i][j]=='G')
        {
            mx=i;
            my=j;
        }
    }
}
while(!q.empty())
{
pair<int,int>c=q.front();
q.pop();
int x=c.first;
int y=c.second;
if(dp[mx][my])
{
    break;
}
for(int i=0;i<4;i++)
{
int tx=x+dx[i];
int ty=y+dy[i];
if(a[tx][ty]=='#'||vis[tx][ty]||tx<1||ty<1||tx>h||ty>w)
{
continue;
}
q.push({tx,ty});
vis[tx][ty]=1;
dp[tx][ty]=dp[x][y]+1;
//广搜步数+1
}
if(a[x][y]>='a'&&a[x][y]<='z')
{
    char cc=a[x][y];
    if(vvis[cc-'a'])
    {
        continue;
    }
    vvis[cc-'a']=1;
    for(int i=0;i<p[cc-'a'].size();i++)
    {
        int tx=p[cc-'a'][i].first;
        int ty=p[cc-'a'][i].second;
        if(vis[tx][ty])
        {
            continue;
        }
        vis[tx][ty]=1;
        q.push({tx,ty});
        dp[tx][ty]=dp[x][y]+1;
    }


}
}

if(dp[mx][my]==0)
{
    cout<<-1;
    return 0;
}
cout<<dp[mx][my];



return 0;
}

F

由于N<=40，直接进行折半，然后直接进行状压，枚举出一部分，再用二分去弄另一部分

本题学会了状压来枚举所有状态值得纪念。

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
#include <bits/stdc++.h>
using namespace std;
const int N=45;
using ll=long long;
ll t,a[N],b[N],c[N];
ll ans;
ll d[2200000];
int cnt;
int main()
{
    int n;
cin>>n>>t;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
}
int x=n/2;
int y=n-n/2;
for(int i=1;i<=x;i++)
{
    b[i]=a[i];
}
for(int i=1;i<=y;i++)
{
    c[i]=a[n-i+1];
}
for(int i=0;i<=(1<<x)-1;i++)
{
//进行状压
cnt++;
for(int j=1;j<=x;j++)
{
    if((1<<(j-1))&i)
    {
        d[cnt]+=b[j];
    }
}
}
sort(d+1,d+1+cnt);
for(int i=0;i<=(1<<y)-1;i++)
{
    ll now=0;
    for(int j=1;j<=y;j++)
    {
if(1<<(j-1)&i)
{
    now+=c[j];
}
    }
    if(now>t)
    {
        continue;
    }
    int pos=upper_bound(d+1,d+1+cnt,t-now)-d;
    pos--;
    ans=max(ans,now+d[pos]);
}
cout<<ans;
return 0;
}