分类: cf1500 - CheaSim Blog
发表更新cf15003 分钟读完 (大约522个字)

Codeforces Round #499 (Div. 2)

Codeforces Round #499 (Div. 2)](http://codeforces.com/contest/1011)

A. Stages

题意

给定一段序列，每个字母代表这一个权值，比如$a$代表$1$。之后问从中挑选出一个序列，要求$a[i]$和$a[i+1]$之间相隔一个字母，问从任意顺序选择$k$个字母，最少可以有多少权值。

题解

贪心，其实如果取最大值的话， 我就有点不会了。但是取最小值可以贪心的对所有位置都取能取的最小值。

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
#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 = 60;
char s[maxn];
int a[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&k);
    scanf("%s",s);
    int len = strlen(s);
    rep(i,0,n) a[i] = s[i] -'a'+1;
    sort(a,a+len);
    int ans = 0;int t = 0;int si = -3;
    rep(i,0,len){
        if(si<a[i]-1 && t<k){
            ans +=a[i];
            t++;
            si = a[i];
        }
    }
    if(t==k){
        printf("%d\n",ans);
    }else{
        puts("-1");
    }
    return 0;
}

B. Planning The Expedition

题意

每个人每天都要吃一个特定种类(由你分配)的食物，你现在有$k$种食物，每个食物都有对应的数量，问怎么分配可以在当前食物下过存活尽量多的天数。

题解

二分枚举答案(坑爹cf，$m<100$二分都不用)。因为答案是递减的。

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 m,n;
const int maxn = 110;
int a[maxn],b[maxn];
bool cmp(int a,int b){
    return a>b;
}
int cnt,ans;
void dfs(int day,int idx,int p){
    if(p <= 0){
        ans = max(ans,day);
        return;
    }
    if(idx ==cnt) return;
    for(int i=1;i<=a[idx];i++){
        if(a[idx] / i < day) continue;
        dfs(day,idx+1,p-i);
    }
}
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,1,m+1){
        int x;scanf("%d",&x);
        a[x]++;
    }
    ans = 0;
    sort(a+1,a+m+1,cmp);
    rep(i,1,101) if(a[i]==0) {cnt = i;break;}
    for(ans = 1;ans<=100;ans++){
        int peo = 0;
        rep(i,1,10){
            peo += a[i]/ans;
        }
        if(peo <n){
            break;
        }
    }
    printf("%d\n",ans-1);
    return 0;
}

C.Fly

题意

每次降落和出发都需要消耗燃料，问最少带多少燃料可以来一次旅行。

题解

小学奥数题，反向做即可。

AC代码

1

D. Rocket

题意

猜数字，你问至多$60$次数字，他给出你问的数字是大了还是笑了，他有一个循环答题方案，比如第一次打错，第二次答对，循环少于$30$次。让你问出答案。

题解

循环至多$30$次暗示了你可以故意说一些已知的问题来试他。比如问-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
46
47
48
49
#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;
bool vis[100];
int query(int x){
    int y;
    cout<<x<<endl;
    fflush(stdout);
    cin>>y;
    return y;
}
int main(){
#ifdef LOCAL
    //freopen("4.in","r",stdin);
#endif
    scanf("%d%d",&m,&n);
    rep(i,0,n){
        int x = query(1);
        if(x == 0){
            cout<<1<<endl;
            return 0;
        }
        if(x<0) vis[i] = 1;
    }
    int mid = 0;int cnt = 0;
    int l,r;
    l = 1,r = m;
    while(l<=r){
        mid = (l+r)>>1;
        int y = query(mid);
        if(vis[cnt]) y = -y;
        if(y==1) l = mid+1;
        else if(y==-1)r = mid-1;
        else{
            cout<<mid<<endl;
            return 0;
        }
        cnt = (cnt+1)%n;
    }
    return 0;
}
发表更新cf15004 分钟读完 (大约530个字)

codeforcesPoints

codeforcesPoints

题意

给出几个点，让你求出在某个点的右边和上面最接近他的点是哪一个点。

题解

线段树+set应用

对$x$进行离散化处理，对于每一个$x$进行建一个set，用线段树维护$x$之间的$y$的最大值。对于给出点的右上点，我们可以用二分来set搜索，还有在线段树中优先搜索左边靠近给出点的点。

这是我第一次看到离散化的线段树应用。哭泣

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
#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
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
inline int Max(int a,int b){return a>b?a:b;}
//head
const int maxn = 2e5 + 20;
int maxy[maxn<<2],mark[maxn],x[maxn],y[maxn];
set<int> s[maxn];
int n,m;
char op[20];
vector<int> v;
void build(int l,int r,int rt){
    if(l==r){
        maxy[rt] = -1;
        return;
    }else{
        int mid = (l+r)>>1;
        build(lson);
        build(rson);
    }
}
void pushup(int rt){
    maxy[rt] = Max(maxy[rt<<1],maxy[rt<<1|1]);
}
void update(int pos,int val,int l,int r,int rt){
    if(l==r){
        maxy[rt] = val;
        return;
    }
    int mid = (l+r)>>1;
    if(pos <= mid) update(pos,val,lson);
    else update(pos,val,rson);
    pushup(rt);
}
int query(int L,int R,int val,int l,int r,int rt){
    if(maxy[rt] <= val) return -1;
    if(l==r) return l;
    int mid = (l+r)>>1;
    int ans = -1;
    if(L <= mid && maxy[rt<<1] > val){
        ans = query(L,R,val,lson);
        if(ans != -1) return ans;
    }
    if(R > mid && maxy[rt<<1|1] > val)
        ans = query(L,R,val,rson);
    return ans;
}
int main(){
#ifdef LOCAL
    freopen("points.in","r",stdin);
#endif
    scanf("%d",&n);
    rep(i,0,n){
        scanf("%s%d%d",op,&x[i],&y[i]);
        if(op[0] == 'a') mark[i] = 1;
        else if(op[0] == 'r') mark[i] = 2;
        else mark[i] = 3;
        if(op[0] == 'a') v.push_back(x[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    m = v.size();
    rep(i,0,n){
        if(mark[i] == 1 || mark[i] == 2){
            int pos = lower_bound(v.begin(),v.end(),x[i]) - v.begin()+1;
            if(mark[i] == 1) s[pos].insert(y[i]);
            else s[pos].erase(y[i]);
            int val;
            if(s[pos].empty()) val = -INF;
            else val = *(--s[pos].end());
            update(pos,val,1,m,1);
        }else{
            int pos = upper_bound(v.begin(),v.end(),x[i]) - v.begin()+1;
            int z = query(pos,m,y[i],1,m,1);
            if(z == -1 || pos == m+1){
                puts("-1"); continue;
            }
            int ans = *(s[z].upper_bound(y[i]));
            printf("%d %d\n",v[z-1],ans);
        }
    }
    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.
×