标签: 贪心 - CheaSim Blog
发表更新cf7 分钟读完 (大约1009个字)

[Codeforces Round #546 (Div. 2)题解]

Codeforces Round #546 (Div. 2)

D题题目读错把爷给整自闭了，此篇题解除了D都只有代码了

A. Nastya Is Reading a Book

做法

暴力

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

int n;
vector<int> ve;
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d",&n);
    rep(i,0,n){
        int l,r;scanf("%d%d",&l,&r);
        ve.push_back(r);
    }
    int page; scanf("%d",&page);
    int idx = lower_bound(ve.begin(),ve.end(),page) - ve.begin();
    printf("%d\n",n-idx);

    return 0;
}

B. Nastya Is Playing Computer Games

题解

找规律。 两个一组要六次。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    int n,a;
    scanf("%d%d",&n,&a);
    int ans = 0;
    if(n&1) ans+=3,ans += (n-1)*3;
    else ans += n*3;
    int mmin = min(n-a,a-1);
    ans += mmin;
    printf("%d\n",ans);


    return 0;
}

C. Nastya Is Transposing Matrices

题解

只有从左下到右上的有用。找规律。

我写得坐标变换有点绕。

ac代码

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 per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

int n,m;
const int maxn = 5e2+10;
int mx1[maxn][maxn], mx2[maxn][maxn];
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,0,n) rep(j,0,m) scanf("%d",mx1[i]+j);
    rep(i,0,n) rep(j,0,m) scanf("%d",mx2[i]+j);
    bool ans = true;
    n = max(n,m);
    rep(i,0,n){
        map<int,int>mmp;
        rep(j,0,i+1){
            mmp[mx1[i-j][j]]++;
        }
        rep(j,0,i+1){
            mmp[mx2[i-j][j]]--;
            if(mmp[mx2[i-j][j]] == 0) mmp.erase(mx2[i-j][j]);
        }
        if(mmp.size()>0) ans = false;
        if(!ans) break;
    }
    rep(i,0,n){
        map<int,int>mmp;
        rep(j,0,n-i){
            mmp[mx1[n-j][i+j]]++;
        }
        rep(j,0,n-i){
            mmp[mx2[n-j][i+j]]--;
            if(mmp[mx2[n-j][i+j]] == 0) mmp.erase(mx2[n-j][i+j]);
        }
        if(mmp.size()>0) ans = false;
        if(!ans) break;
    }

    if(ans) puts("YES");
    else puts("NO");
    return 0;
}

D. Nastya Is Buying Lunch

题意

Nastya去排队，队伍中有这样一个规律。

  • 已知有$m$对$(i,j)$，他们如果是相邻的话，并且$i$在$j$的前面，那么他们就可以调换位置。

问Nastya能够往前调换多少次位置，已知Nastya在最后一名。

题解

一开始我是看错题意，以为是可以隔空调换，直接想着用图论找一个环或者是找一个树来做。没有想到必须要相邻才能换，那么我们就可以这样想，我们的答案最多就只有$Nastya能够往前交换的人的数量$。之后我们尽可能的就是将不能交换的人往前面移动，能交换的人往后面移动。之后由于是一个一个相邻的同学移动，所以如果从前开始尽量往后移动的话，有可能会有的同学到达不到Nasyta的范围了。从后往前交换，那么我们就是将不可换的同学尽量地想前面推，之后如果前面的同学先交换到后面，那么对河Nasyta可以到达的来说，他也是一定能交换到Nasyta到达的点的。

举个栗子:

4 4

1 2 3 4

2 4

1 4

1 2

1 3

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

int n,m;
const int maxn = 3e5+10;
int idx[maxn];
set<int> st[maxn];
int a[maxn];
int vis[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,1,n+1){
        int x; scanf("%d",&x);
        a[i] = x; idx[x] = i;
    }
    rep(i,0,m){
        int x,y; scanf("%d%d",&x,&y);
        st[x].insert(y);
        if(y == a[n]) vis[x] = 1;
    }
    per(i,1,n-1){
        if(vis[a[i]] == 0) continue;
        int t = i;
        while(t<n-1 && st[a[t]].find(a[t+1]) != st[a[t]].end()){
            swap(a[t],a[t+1]);
            t++;
        }
    }
    int ans = 0;
    per(i,1,n){
        if(vis[a[i]] == 0) break;
        ans++;
    }
    printf("%d",ans);
    return 0;
}
发表更新acm3 分钟读完 (大约376个字)

[hdoj5881]Tea

Tea

题意

题意有点复杂。给你一壶茶，容量范围为$[L,R]$。之后给你两个杯子。让你从茶壶中往杯子里加茶。结果有以下要求。

  • 经过$ans$次加水,$ans$最小
  • 两个杯子的茶水量相差不超过$1$
  • 茶壶中茶水量最终不超过$1$

题解

贪心。

贪心很好想，就是细节很多。

记录茶杯1为a,茶杯2为b。

  1. 我们首先向a添加$L/2+0.5$的茶水，之后茶壶中还剩下的范围为$[L/2-0.5,R-L/2-0.5]$。如果满足要求，那么$ans$就是$1$。

  2. 之后我们往b添加$L/2-0.5$的茶水，之后茶壶中剩下的范围为$[0,R-L-2]$。如果满足要求，$ans$就是$2$。

  3. 之后我们循环往每个茶杯中加入$2$的水，直到满足要求。

需要注意的是，如果$L=0$的话要特判，还有如果$R<=1$那么就直接满足条件，如果$R<=2$的话只要添加一次。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

ll l,r;
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>l>>r){
        if(r<=1) puts("0");
        else if(r<=2) puts("1");
        else if(l==0) printf("%lld\n",(r-1)/2+1);
        else {
            ll temp = r-l-3;
            temp = max(0ll,temp);
            ll ans = temp/2;
            if(ans*2<temp) ans++;
            printf("%lld\n",ans+2);
        }
    }

    return 0;
}
发表更新acm2 分钟读完 (大约289个字)

[cf-767b]The Queue

The Queue

题意

题意有点复杂，懒得写了。

题解

贪心。

注意的点就是，可以在还没有开始就进入队列进行排队，所以计算的时候虽然是一样的，但还是要注意一下。

特殊情况就是对于在ed以后的人来说，他们就不算了，不算人。

+1 p数组 忘记开long long了。

+1 如果加入时间超过进入时间了就不行了。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
ll st,ed,t;
int n;
const int maxn = 1e5+10;
ll p[maxn];
int main(){
#ifdef LOCAL
    freopen("4.in","r",stdin);
#endif
    scanf("%lld%lld%lld",&st,&ed,&t);
    scanf("%d",&n);
    rep(i,0,n) scanf("%lld",p+i),p[i]-=st;
    ed -= st;
    ll ans = 1e13;
    ll wait = 1e14;
    int cnt = 0;
    rep(i,0,n){
        if( (ll)(i+1)*t>ed || p[i]+t>ed) break;
        cnt++;
        if(p[i] > (ll)(i)*t && p[i]+t<=ed){
            ans = p[i]-1;
            cout<<ans+st<<'\n';
            return 0;
        }else{
            ll temp = (ll)(i)*t - p[i];
            if(wait > temp){
                wait = temp;
                ans = p[i]-1ll;
            }
        }
    }
    ll temp = (ll)(cnt+1)*t; if(temp<=ed) ans = temp-t;
    printf("%lld\n",ans+st);

    return 0;
}
发表更新acm2 分钟读完 (大约370个字)

[cf-767D]Cartons of milk

Cartons of milk

题意

每天喝$k$瓶牛奶，每瓶牛奶都有$s$的保质日期，现在我有$n$瓶牛奶，去商场最多可以买多少瓶牛奶。

条件是每天都要喝$k$瓶牛奶，在最有情况下所有牛奶都不会过期。

题解

贪心，反正所有牛奶的贡献都是1，所以保质期越后面的越好。

计算能买多少瓶就是从第一天开始遍历，能买到就买对应的期限的牛奶。

+1： 中间一个变量爆了int

+1: 有两个变量$n,m$，sort的时候用了$n$，应该用$m$。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,m,k;
const int maxn = 1e6+10;
const int maxm = 1e7+10;
int vis[maxm];
int mx[maxm];
struct node{
    int id;
    int val;
    bool operator<(const node &x)const{
        return val>x.val;
    }
}a[maxn];
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    scanf("%d%d%d",&n,&m,&k);
    bool flag = false;
    rep(i,0,n){
        int x;scanf("%d",&x);
        vis[x]++;
    }
    rep(i,0,m){
        int x;scanf("%d",&x);
        mx[x]++;
        a[i].val = x; a[i].id = i+1;
    }
    sort(a,a+m);
    int ans = 0;
    ll  now = k;
    rep(i,0,maxm){
        if(vis[i] > now){
            flag = true;
            break;
        }else{
            int temp = min(now-vis[i],(ll)mx[i]);
            int t = vis[i] + temp;
            ans += temp;
            now += k-t;
        }
    }
    if(flag) puts("-1");
    else{
        printf("%d\n",ans);
        rep(i,0,ans){
            printf("%d ",a[i].id);
        }
        puts("");
    }
    
    return 0;
}
发表更新acm几秒读完 (大约102个字)

[77c Beavermuncher-0xFF树形dp+贪心

C. Beavermuncher-0xFF

题意

给你一颗树，树上的每个节点有$n$个海狸。现在你在节点$root$上你前往下一个节点的条件是下一个节点上面至少有一个海狸，之后你到这个节点之后，你就会吃掉这个海狸。问最多能吃掉多少只海狸。

题解

贪心+树形dp

ac代码

发表更新acm3 分钟读完 (大约398个字)

[hdoj6376]度度熊剪纸条

度度熊剪纸条

题意

将一段01的序列分成$k$段，将他们重新拼接，问拼接成的纸条中前导0最多有多少个。

  • 拼接不可以改变方向。

题解

我模拟下来就是我们可以将这段序列分成三部分，

比如

11111/0/111/0/1111/0/11111

最前方的1部分和最后方的1部分和中间的1部分。

如果想将中间的1放在前面就必须剪两次，前方和后方的只需要1次。

模拟的话。

  • 我们首先如果第一段不剪，那么就是从后面的中间1和后方1选择，中间1需要剪两次，后方1只要剪一次。

  • 如果第一段剪掉，那么就是选择最大的，在他前面切一刀，把它当做最后的处理，其余的是前面的和后面的剪一刀和中间的剪两刀。

如果$k==0$特殊处理一下。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,k;
const int maxn = 1e4+100;
char s[maxn];
int ve[maxn];
int solve(){
    bool flag = 0;
    int cnt = 0;
    int l = 0,r = 0;
    int ans = 0;
    int j = 0;
    int st = 0,ed = n-1;
    while(s[st]==1&&st<n)st++;
    l = st;
    while(s[ed]==1&&st<=ed) ed--;
    r = n-ed-1;
    rep(i,st,ed+1){
        if(s[i] == 1) cnt++;
        if(s[i] == 0 && cnt){
            ve[++j] = cnt;
            cnt = 0;
        }
    }
    if(k==0) return l;
    sort(ve+1,ve+j+1);
    while(k>2 && j>=1){
        ans += ve[j--];
        k-=2;
    }
    if(k==1){
        ans += max(l+r,ve[j]);
    }else{
        ans += max(l+r,max(l+ve[j],r+ve[j]));
    }
    return ans;
}
char temp[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    while(~scanf("%d%d",&n,&k)){
        scanf("%s",s);
        rep(i,0,n) s[i] -= '0';
        printf("%d\n",solve());
    }

    return 0;
}
发表更新acm2 分钟读完 (大约267个字)

[hdoj6438]Buy and Resell

[hdoj6438]Buy and Resell

题意

给定$n$个城市和无限制的初始金钱你可以在每个城市里

  • 以$a_i$的价格买个商品
  • 以$a_i$的价格卖出商品
  • 啥都不做

问最多能赚多少钱？

题解

贪心 + 数据结构

假设每个城市都卖出商品。那么之前买入的最便宜的商品来卖。对于买卖次数就将假设买入的商品记录为两种

  • $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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int T,n;
ll ans = 0;
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--){
        priority_queue<pII>pq; ans = 0;int cnt = 0;
        scanf("%d",&n);
        rep(i,0,n){
            int x;scanf("%d",&x);
            pq.push(make_pair(-x,1));
            pq.push(make_pair(-x,2));
            ll temp = x + pq.top().fi;
            if(pq.top().se == 1)  cnt+=2;
            ans += temp;
            pq.pop();
        }
        printf("%lld %d\n",ans,cnt);
    }
    return 0;
}

关注我

链接

分类

最新文章

归档

标签

AI2
LCA1
Linux1
QA1
acm13
ac自动机1
ajax1
bert1
bilstm1
cf8
colab1
crf1
css1
dfs3
dgl1
dp5
dptree1
echarts1
gnn1
graph1
greedy1
hash2
hdoj1
html1
js1
jsp1
lca1
linux1
math1
matrix1
nlp2
pat2
pytorch1
re1
struts21
tokenizer1
web1
专题1
二分1
人生1
保研1
八数码1
图论1
字符串1
字符串hash1
学习笔记6
学习计划1
小技巧1
开发3
抽取1
数学1
数据结构1
最大子段和1
构造1
树形dp5
树状数组2
树状数组，hdoj1
树链剖分1
概率dp1
模拟1
模板1
爆搜1
牛客网1
状压dp1
线段树6
组合数学1
细节1
缩点1
网络1
网络赛3
考研2
范围1
蓝桥杯2
补题1
规律1
计划1
计算几何1
论解2
贪心7
递归1
配置1
随性1
预处理1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.
×