o2o网站建设多少钱,成都注册公司核名网站,苏州做网页,电话卡免费申请好久不写博客了#xff0c;今天来水一篇
原题链接
初看此题在洛谷上的定位是黄题#xff0c;实际上也并不是很简单。
其实主要就用到了贪心的思想#xff0c;先说一下我在做题的时候是怎么想的吧。
先看了部分分#xff0c;10分是很好拿的#xff0c;再就分析题意今天来水一篇
原题链接
初看此题在洛谷上的定位是黄题实际上也并不是很简单。
其实主要就用到了贪心的思想先说一下我在做题的时候是怎么想的吧。
先看了部分分10分是很好拿的再就分析题意打暴力能拿60分已经还可以了60分主要用到了桶排序的思想桶排序是只会看是否存在不会重复记
60pts缺少了判断ij的情况
#includebits/stdc.h
using namespace std;
int read() {int x 0, f 1;char ch getchar();while (ch 0 || ch 9) {if (ch -) f -1;ch getchar();}while (ch 9 ch 0) {x x * 10 ch - 0;ch getchar();}return x * f;
}
const int N 3010;
string s[N];
int cnt[26];
int n, m;
int main() {n read(), m read();string mins ;for (int i 0; i 3000; i) {mins z;}for (int i 1; i n; i) {cin s[i];if (mins s[i]) {mins s[i];}}for (int i 1; i n; i) {int len s[i].length();for (int j 0; j len; j) {cnt[s[i][j] - a];}string t ;for (int j 0; j 26; j) { //桶排序while (cnt[j]) {t j a;cnt[j]--;}}if (t mins) {cout 1;} else cout 0;}return 0;
}
接下来就是正解直接把每个字符串wi都从小到大或者从大到小排一下记作aibi。如果bi小于除了i之外的所有ai说明可以否则不可以。求一个前后缀最大值即可。复杂度为O26nnm
100pts
#includebits/stdc.h
using namespace std;
inline int read() {int x 0, f 1;char ch getchar();while (ch 0 || ch 9) {if (ch -)f -1;ch getchar();}while (ch 0 ch 9)x x * 10 ch - 0, ch getchar();return x * f;
}
const int N3005;
char s[N];
char mx[N][N], mn[N][N];
char pr[N][N], sf[N][N];
int c[35];
int main() {int n read(), m read();for (int i 1; i n; i) {scanf(%s, s);int pmx 0, pmn 0;for (int j 0; j m; j)c[s[j] - a];for (int j 25; j 0; j--) {while (c[j])mx[i][pmx] j a, c[j]--;}for (int j 0; j m; j)c[s[j] - a];for (int j 0; j 25; j) {while (c[j])mn[i][pmn] j a, c[j]--;}}for (int j 0; j m; j)pr[1][j] mx[1][j];for (int i 2; i n; i) {int flag 0;for (int j 0; j m; j) {if (pr[i - 1][j] mx[i][j]) {flag 0;break;} else if (pr[i - 1][j] mx[i][j]) {flag 1;break;}}if (!flag) {for (int j 0; j m; j)pr[i][j] pr[i - 1][j];} else {for (int j 0; j m; j)pr[i][j] mx[i][j];}}for (int j 0; j m; j)sf[n][j] mx[n][j];for (int i n - 1; i 1; i--) {int flag 0;for (int j 0; j m; j) {if (sf[i 1][j] mx[i][j]) {flag 0;break;} else if (sf[i 1][j] mx[i][j]) {flag 1;break;}}if (!flag) {for (int j 0; j m; j)sf[i][j] sf[i 1][j];} else {for (int j 0; j m; j)sf[i][j] mx[i][j];}}for (int i 1; i n; i) {int flag 1;if (i 1) {int tag 0;for (int j 0; j m; j) {if (mn[i][j] pr[i - 1][j]) {tag 0;break;} else if (mn[i][j] pr[i - 1][j]) {tag 1;break;}}flag tag;}if (i n) {int tag 0;for (int j 0; j m; j) {if (mn[i][j] sf[i 1][j]) {tag 0;break;} else if (mn[i][j] sf[i 1][j]) {tag 1;break;}}flag tag;}if (flag)cout1;else cout0;}return 0;
}
