img

Codeforces Round 935 Div3

A

Setting up Camp

思路很简洁

就是看他们两个对3取余是不是大于自由人个数

然后分组，就是自由人和乐观人分一组

多出的进行计算即可

这里复杂了

还写了几个if，其实没必要

直接(b+c+2)/3即可

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
#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 >= n; i--)
#define ll long long
const int N=1e6+100;
int a[N];
void solve()
{
ll a,b,c;
cin>>a>>b>>c;
if(((b+c)%3)-c>0)
{
    cout<<-1<<'\n';
}
else
{
    if((b+c)%3)
    cout<<a+(b+c)/3+1<<'\n';
    else
    cout<<a+(b+c)/3<<'\n';
}

}
int main()
{
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

B

Fireworks

规律题？大概就是这样

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;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
#define ll long long
const int N = 1e6 + 100;
void solve()
{
 ll a,b,m;
 cin>>a>>b>>m;
 cout<<m/a+m/b+2<<'\n';
}
int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

C

Left and Right Houses

二分调不出来，还是暴力为好

记录一个前缀和

然后直接*2硬判

有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
44
45
46
47
48
49
50
#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 >= n; i--)
#define ll long long
const int N = 1e6 + 100;
int n;
void solve()
{
    int ans = 1e9;
    string s;
    cin >> n >> s;
    s = " " + s;
    vector<int> sum(n +1);
    rep(i, 1, n)
    {
        if (s[i] == '1')
        {
            sum[i] = sum[i - 1] + 1;
        }
        else
        {
            sum[i] = sum[i - 1];
        }
}
rep(i,0,n)
{
    if((i-sum[i])*2>=i&&(sum[n]-sum[i])*2>=(n-i))
    {
if(abs(2*i-n)<abs(2*ans-n))
{
ans=i;
}
    }
}


cout<<ans<<'\n';

}
int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

D

Seraphim the Owl

dp[i]=dp[j]+sum[i+1]+a[i]-sum[j]

这里sum[i+1]和a[i]都是确定的

要最小只需要让

dp[j]-sum[j]最小

进行判断即可

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
#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 >= n; i--)
#define ll long long
const int N=2e5+100;
ll a[N];
ll b[N];
ll sum[N];
ll dp[N];
void solve()
{
    memset(dp,0,sizeof(dp));
    memset(sum,0,sizeof(sum));
    ll ans=0;
ll  n,m;
cin>>n>>m;
rep(i,1,n)
{
    cin>>a[i];
}
rep(i,1,n)
{
    cin>>b[i];
}
frep(i,n,1)
{
sum[i]=sum[i+1]+b[i];
}
frep(i,n,1)
{
    dp[i]=ans+a[i]+sum[i+1];
    //之前究竟是选择A好还是B好
    //应该需要记录
    ans=min(ans,dp[i]-sum[i]);
}
ll x=1e18;
rep(i,1,m)
{
    x=min(dp[i],x);
}
cout<<x<<'\n';
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

E

Binary Search

按照题目枚举一下，如果找到x的话就是0次

不然的话找到的数和x的位置换一下就是答案

实际上只需要1次或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
#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 >= n; i--)
#define ll long long
void solve()
{
    int n,x;
    cin>>n>>x;
    int cnt;
    vector<int>a(n+1);
    rep(i,1,n)
    {
        cin>>a[i];
        if(a[i]==x)
        {
            cnt=i;
        }
    }
    int l=1;
    int r=n+1;
    while(l+1!=r)
    {
int mid=(l+r)/2;
if(a[mid]<=x)
{
    l=mid;
}
else
{
    r=mid;
}
    }
    if(a[l]==x)
    {
        cout<<0<<'\n';
    }
    else
    {
        cout<<1<<'\n';
        cout<<cnt<<' '<<l<<'\n';
    }
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
            }
}

F

Kirill and Mushrooms

见注释

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
#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 >= n; i--)
#define ll long long
const int N=2e5+100;
struct node
{
    int pos;//下标
    int val;//值
}a[N];
int n;
int b[N];//排列
int vis[N];//是否加入
int vis0[N];//是否变0
bool cmp(node a,node b)
{
    return a.val>b.val;
}//排序
void solve()
{
    memset(vis0,0,sizeof vis0);
    memset(vis,0,sizeof vis);
    //多测清0
cin>>n;
rep(i,1,n)
{
cin>>a[i].val;
a[i].pos=i;
}
sort(a+1,a+1+n,cmp);
ll ans=0;//答案
ll cnt=n;//个数
ll coun=0;//中间计数
ll minn=1e18;//最小魔力
rep(i,1,n)
{
    cin>>b[i];
}
rep(i,1,n)
{
if(vis0[a[i].pos]||b[coun]==a[i].pos)
    //如果已经变成0了或者已经要变成0了
{
    continue;
}
coun++;
minn=a[i].val;
    //最小，排序保证了
vis[a[i].pos]=1;
    //加入（贪心）
if(vis[b[coun-1]])
{
vis[b[coun-1]]=0;
coun--;
    //去除变0部分
}
vis0[b[coun-1]]=1;
    //记录变0
if(ans<minn*coun)
{
    ans=minn*coun;
    cnt=coun;
}
else if(ans==minn*coun)
{
    cnt=min(cnt,coun);
}
}
    //答案枚举
cout<<ans<<' '<<cnt<<'\n';

}
int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}