Codeforces 777D Cloud of Hashtags(贪心)

题目链接 Cloud of Hashtags

题目还是比较简单的,直接贪心,但是因为我有两个细节没注意,所以FST了:

1、用了cin读入,但是没有加 std::ios::sync_with_stdio(false); 这条语句;

2、开了太多string。

也算是经验教训吧。

 1 #include <bits/stdc++.h>
 2
 3 using namespace std;
 4
 5 #define rep(i, a, b)              for(int i(a); i <= (b); ++i)
 6 #define dec(i, a, b)              for(int i(a); i >= (b); --i)
 7
 8 const int N     =    500000      +       10;
 9 int n;
10 string s[N], c[N];
11
12 int main(){
13
14     std::ios::sync_with_stdio(false);
15     cin >> n;
16     rep(i, 1, n) cin >> s[i];
17     c[n] = s[n];
18     dec(i, n - 1, 1){
19         int j = i + 1;
20         if (s[i] <= c[j]){
21             c[i] = s[i];
22             continue;
23         }
24         int l1 = s[i].length(), l2 = c[j].length();
25         int p;
26         rep(k, 1, l1 - 1){
27             if (s[i][k] > c[j][k] || k > l2 - 1){
28                 p = k - 1;
29                 break;
30             }
31         }
32
33         c[i] = "";
34         rep(k, 0, p) c[i] = c[i] + s[i][k];
35     }
36
37     rep(i, 1, n) cout << c[i] << endl;
38
39
40     return 0;
41
42 }
时间: 02-24

Codeforces 777D Cloud of Hashtags(贪心)的相关文章

Codeforces Round #401 (Div. 2) D. Cloud of Hashtags

题目链接:D. Cloud of Hashtags 题意: 给你n个字符串,让你删后缀,使得这些字符串按字典序排列,要求是删除的后缀最少 题解: 由于n比较大,我们可以将全部的字符串存在一个数组里面,然后记录一下每个字符串的开始位置和长度,然后从下面往上对比. 如果str[i][j]<str[i+1][j],直接退出,因为这里已经成为字典序. 如果str[i][j]>str[i+1][j],那么就把str[i][j]=0,表示从这里开始的后缀全部删掉. str[i][j]==str[i+1][

Codeforces 442B Andrey and Problem(贪心)

题目链接:Codeforces 442B Andrey and Problem 题目大意:Andrey有一个问题,想要朋友们为自己出一道题,现在他有n个朋友,每个朋友想出题目的概率为pi,但是他可以同时向多个人寻求帮助,不过他只能要一道题,也就是如果他向两个人寻求帮助,如果两个人都成功出题,也是不可以的. 解题思路:贪心,从概率最大的人开始考虑,如果询问他使得概率变大,则要询问. #include <cstdio> #include <cstring> #include <a

Codeforces Round #300-Tourist&#39;s Notes(贪心)

Tourist's Notes Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u Submit Status Description A tourist hiked along the mountain range. The hike lasted for n days, during each day the tourist noted height above the sea level

Codeforces 432E Square Tiling(构造+贪心)

我们通常这么写 using (SqlDataReader drm = sqlComm.ExecuteReader()) { drm.Read();//以下把数据库中读出的Image流在图片框中显示出来. MemoryStream ms = new MemoryStream((byte[])drm["Logo"]); Image img = Image.FromStream(ms); this.pictureBox1.Image = img; } 我的写数据 private void b

Codeforces 777D:Cloud of Hashtags(水题)

http://codeforces.com/problemset/problem/777/D 题意:给出n道字符串,删除最少的字符使得s[i] <= s[i+1]. 思路:感觉比C水好多啊,大概是题目比较难看懂吧.直接从后面往前扫,用后面的答案更新前面的答案.考虑如果后面的字符串比前面的大,那么直接保存当前的字符串,否则暴力扫一遍,前面的字符串大于后面的字符串的那一位直接跳出. 1 #include <bits/stdc++.h> 2 using namespace std; 3 str

【贪心】Codeforces Round #401 (Div. 2) D. Cloud of Hashtags

从后向前枚举字符串,然后从左向右枚举位. 如果该串的某位比之前的串的该位小,那么将之前的那串截断. 如果该串的某位比之前的串的该位大,那么之前那串可以直接保留全长度. 具体看代码. #include<cstdio> #include<iostream> #include<string> using namespace std; string a[500010]; int n,lens[500010],b[500010]; int main() { // freopen(

Codeforces 798D Mike and distribution - 贪心

Mike has always been thinking about the harshness of social inequality. He's so obsessed with it that sometimes it even affects him while solving problems. At the moment, Mike has two sequences of positive integers A = [a1, a2, ..., an] and B = [b1, 

codeforces 349B Color the Fence 贪心,思维

1.codeforces 349B    Color the Fence 2.链接:http://codeforces.com/problemset/problem/349/B 3.总结: 刷栅栏.1-9每个字母分别要ai升油漆,问最多可画多大的数字. 贪心,也有点考思维. #include<bits/stdc++.h> using namespace std; #define LL long long #define INF 0x3f3f3f3f int main() { int v,a[1

codeforces 343C Read Time 二分 + 贪心

http://codeforces.com/problemset/problem/343/C 题意: 有一些磁头,给出了起始的位置,给出了一些磁盘中需要访问的地点.求这些磁头移动的最小的次数. 思路: 二分找出满足要求的最小的时间,对于当前尝试的时间进行贪心判断是否可用.对于贪心,因为每一个磁头都需要读到还没有人读过的最左边的地方.如果这个都不能满足,那么这个时间是不可以的. 在这基础上,对于同样的这么多时间,尽可能的让这个磁头读到能读到的最右边,这样就可以将还没有读过的地方尽可能的往右推. 如