抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

[原创]Codeforces Round #401 (Div. 2) 【结题报告】

Tabris

CSDNcodeforces思维套题

发布于：2017年3月27日

次浏览

[原创]Codeforces Round #401 (Div. 2) 【结题报告】

2017-03-27 00:47:49 Tabris_ 阅读数：300

博客爬取于 2020-06-14 22:41:05
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/66652353

总结下，
看题慢，读错题，代码能力渣，思维不敏捷，菜的一逼。

Shell Game

————————————————————————————————————————————

傻逼题，，
明确题意
枚举下所有情况 就能 AC 了。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main(){
    int n,x;
    scanf("%d",&n);
    scanf("%d",&x);
    n%=6;
    if(x==0){
     if(n== 5|| n==0 ) puts("0");
     if(n== 2|| n==1 ) puts("1");
     if(n== 4|| n==3 ) puts("2");
    }
    if(x==1){
     if(n== 1|| n==4 ) puts("0");
     if(n== 5|| n==2 ) puts("2");
     if(n== 3|| n==0 ) puts("1");
    }
    if(x==2){
     if(n== 3|| n==2 ) puts("0");
     if(n== 5|| n==4 ) puts("1");
     if(n== 1|| n==0 ) puts("2");
    }
    return 0;
}

Game of Credit Cards

————————————————————————————————————————————
贪心题
先对两个序列排序，
对于两个问题要分开考虑，
但是大同小异 ,
第一个就是尽量抗伤害
第二个就是尽量输出，类似田忌赛马

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
# include <bits/stdc++.h>

typedef long long int LL ;
using namespace std;
const int N   = 100000+7;
const int MOD = 1000000007;
/*******************************************************/

# define all(x) x.begin(),x.end()

int main() {
    int n;
    cin >>n;
    string a,b;
    cin>>a>>b;

    sort(all(a));
    sort(all(b));

    int ans1 = n;
    for (int i=0,j=0; i<n; ++i) {
        if (b[i] >= a[j]) {
            ans1--;
            j++;
        }
    }

    int ans2 = 0;
    for (int i=0,j; i<n; ++i) {
        if (b[i] > a[j]) {
            ans2++;
            j++;
        }
    }
    cout <<ans1 <<endl <<ans2 <<endl;
}

Alyona and Spreadsheet

————————————————————————————————————————————
给你一个 N*M 的方阵，每个方阵有一个值，有 Q 次询问，
问你第 x 行到第 y 行中存不存在一列是单调不减的 存在 yes 否则 no

其实很简单，我预处理出来到每一行的最长的那个列就好了，

然后询问的时候就能做到 O(1)

详看代码吧

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
# include <bits/stdc++.h>

typedef long long int LL ;
using namespace std;
const int N   = 1e5+7;
const int MOD = 1000000007;
/*******************************************************/

vector<int >a[100005];
vector<int >b[100005];
int h[100005];
int main(){
    int n,m,x;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++){
        a[i].clear();
        a[i].push_back(0);
        b[i].push_back(0);
        for(int j=1;j<=m;j++){
            scanf("%d",&x);
            a[i].push_back(x);
            b[i].push_back(0);
        }
    }

    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]<a[i-1][j]){
                a[i-1][j]=0;
            }
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(0!=a[i][j]) a[i][j]=1;
        }
    }
    for(int j=1;j<=m;j++)b[1][j]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++){
            b[i][j]=1+b[i-1][j];
            if(a[i-1][j]==0) b[i][j]=1;
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            h[i]=max(h[i],b[i][j]);
        }
    }
    int q,l,r;
    scanf("%d",&q);
    while(q--){
        scanf("%d%d",&l,&r);
        if(h[r]>=r-l+1) puts("Yes");
        else            puts("No");
    }
    return 0;
}

Cloud of Hashtags

————————————————————————————————————————————
给你一堆字符串 对于每个字符串只能删除后缀， 删除最少的字符 使得这些字符串字典序单调不减

正着考虑 很明显 无法解决，
但是因为只能删后缀，那么从后向前考虑就没有问题了
只要使得 s[i-1]的字典序依次小于 s[i]就行了

自己的代码太丑了
献上巨巨优美的代码

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
# include <bits/stdc++.h>

typedef long long int LL ;
using namespace std;
const int N   = 1e5+7;
const int MOD = 1000000007;
/*******************************************************/
int n, l[500005]; string s[500005];
void solve(int x, int y) {
    int len = min(l[x], l[y]);
    for(int i=0;i<=len-1;i++) {
        if (s[x][i] < s[y][i]) return ;
        if (s[x][i] > s[y][i]) {
            l[x] = i;
            return ;
        }
    }
    if (l[x] <= l[y]) return; else l[x] = len;
}
int main() {
    scanf("%d", &n);
    for(int i=1;i<=n;i++) cin >> s[i], l[i] = s[i].length();
    for (int i = n; i > 1; -- i) solve(i - 1, i);
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=l[i]-1;j++) printf("%c", s[i][j]);
        printf("\n");
    }
    return 0;
}

Hanoi Factory

————————————————————————————————————————————
给你一堆圆圈，有内半径和外半径 还有厚度，，现在让你将其摞在一起 ,
外半径大的不能再外半径小的上面，
不能从内半径中掉出去
问你能摞成的厚度最大是多少

很简单，先对外半径升序排相等的使内半径升序
然后从前开始找，能摞在这个圆圈上的厚度最大的为多少，
维护个最大值就行了

用线段树维护半径就行了，注意要离散化。

（后看到有人使用树状数组维护的因为维护的是前缀最大，所以没毛病，当时可能脑袋有点浑，并没有看太清晰就写了。。

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
# include <bits/stdc++.h>

typedef long long int LL ;
using namespace std;
const int N   = 1e5+7;
const int MOD = 1000000007;
/*******************************************************/

struct node{
    int l,r; //节点的区间
    LL  mx; //节点的值
    int m(){return (l+r)>>1;}
    int len(){return r-l+1;}
}tree[N<<3];
# define ll  (rt<<1)
# define rr  (rt<<1|1)
# define mid (tree[rt].m())
void pushup(int rt)  {
    tree[rt].mx=max(tree[ll].mx,tree[rr].mx);
}
void build(int rt,int l,int r){
    tree[rt].l=l,tree[rt].r=r,tree[rt].mx=0;;
    if(l==r)  return ;
    build(ll,l,mid);
    build(rr,mid+1,r);
}
void update(int rt,int pos,LL mx){
    if(tree[rt].l==tree[rt].r){
        tree[rt].mx=mx;
        return;
    }
    if(pos<=mid)  update(ll,pos,mx);
    else          update(rr,pos,mx);
    pushup(rt);
}
LL query(int rt,int L,int R){
//    printf("%d %d\n",tree[rt].l,tree[rt].r);
    if(L<=tree[rt].l&&tree[rt].r<=R)
        return tree[rt].mx;
    LL a=0,b=0;
    if(L<=mid)    a=query(ll,L,R);
    if(R> mid)    b=query(rr,L,R);
    return max(a,b);
}

/*******************************/

struct node2 {
    int a,b,h;
}r[100005];
int p[200005];
bool cmp(node2 A,node2 B){
    if(A.b==B.b) return A.a<B.a;
    return A.b<B.b;
}
LL dp[100005];
int n,sz;

int ls(int x){
    return lower_bound(p+1,p+sz+1,x)-p;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&r[i].a,&r[i].b,&r[i].h);
        p[i]=r[i].a,p[i+n]=r[i].b;
    }


    sort(r+1,r+n+1,cmp);
    sort(p+1,p+1+n*2);
    sz = unique(p+1,p+1+n*2)-(p+1);
    build(1,1,sz);
//    for(int i=1;i<=n;i++){
//        printf("%d %d %d\n",r[i].a,r[i].b,r[i].h);
//    }
    LL mx = 0;
    for(int i=1;i<=n;i++){
        dp[i]=r[i].h;
        dp[i]+=query(1,ls(r[i].a+1),ls(r[i].b));
    //   printf("%lld\n",query(1,ls(r[i].a+1),ls(r[i].b)));
        update(1,ls(r[i].b),dp[i]);
        mx = max(mx,dp[i]);
    }

    printf("%lld\n",mx);
    return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://blog.tabris.top/acm/2017-03-27-66652353/

本页文档最后更新于：2021年5月16日

CSDN

codeforces

评论