[原创]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;
}