首页 > 代码库 > CodeForces Round #283 Div.2
CodeForces Round #283 Div.2
A. Minimum Difficulty
题意：
有一个递增序列a，现在要去掉除了第一项和最后一项元素外的某一项，使新数列中相邻元素之差的最大值最小。
分析：
先求出原序列a中，相邻两项元素之差的最大值m。
枚举去掉ai，则新序列相邻元素差的最大值为max{ m, ai+1 - ai }，然后记录最小值即可。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int maxn = 100 + 10; 6 int a[maxn]; 7 8 int main(void) 9 {10 int n;11 scanf("%d", &n);12 for(int i = 0; i < n; ++i) scanf("%d", &a[i]);13 int max1 = 0;14 for(int i = 0; i < n-1; ++i) max1 = max(max1, a[i+1]-a[i]);15 16 int ans = 10000;17 for(int i = 1; i < n-1; ++i) ans =min(ans, max(max1, a[i+1]-a[i-1]));18 19 printf("%d\n", ans);20 21 return 0;22 }
B. (贪心)Secret Combination
题意：
给出一个n(≤1000)位数字，有下面两种操作：
- 将每位数字都自增1，如果是9的话变为0.(注意，每个数位上的数字都是单独操作的互不影响，没有相互之间的进位)
- 将每位数字向右移一位，最右边的数字则移到最左边
求经过若干次操作，n能变为的最小数字。
分析：
首先我们想一下，最小的数字会有什么特点？那就是他前面会有很多前导0
可以把几个连续相同的数字通过操作1加上某个数使其全部变为0，然后通过操作2将其变为前导0
比如：325556，可以进行5次操作1变为870001，然后进行4次操作2，变为000187.
因此，可以预处理n，求出最长连续数字，如果对应有多个相同长度的连续数字，则记录下他们的长度和位置，方便在后面进行比较。
还要注意的是：由于操作2的特性，要考虑到首尾相接也可能出现相同连续的数字，所以我们可以对数组的索引模n取余或者将数字适当延长两倍或三倍。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = (1000 + 10)*3; 7 char s[maxn], s1[maxn], s2[maxn];//输入的数字，当前最小数字，要比较的数字 8 int n; 9 10 struct Queue11 {12 int pos, len;13 Queue(int p=0, int l=0):pos(p), len(l) {}14 }q[maxn]; //记录下连续相同数字的其实位置和个数15 16 bool lessthan(char* a, char* b)17 {//比较数字a是否小于b18 int i = 0;19 while(i < n && a[i] == b[i]) i++;20 if(i >= n) return false;21 return a[i] < b[i];22 }23 24 int main()25 {26 scanf("%d", &n);27 scanf("%s", s);28 strcpy(s1, s);29 for(int i = 0; i < n; ++i) s[i+n] = s[i+2*n] = s[i];30 int lx = 1, p = 0;31 for(int i = 0; i < 2*n; i++)32 {33 int st = i;34 int temp = 1;35 while(i < 2*n-1 && s[i] == s[i+1])36 {37 temp++;38 i++;39 }40 q[p++] = Queue(st, i+1-st);41 if(temp > lx)42 lx = temp; //记录最长相同数字43 }44 45 for(int i = 0; i < p; ++i)46 {47 if(q[i].len == lx)48 {49 int add = (‘9‘ + 1 - s[q[i].pos]) % 10;//将这些相同数字加上add然后全部变为前导050 for(int j = 0; j < n; ++j)51 {52 s2[j] = ‘0‘ + (s[q[i].pos+j]-‘0‘+add)%10;53 }54 if(lessthan(s2, s1))55 {56 for(int k = 0; k < n; ++k) s1[k] = s2[k];57 }58 }59 }60 61 for(int i = 0; i < n; ++i) printf("%c", s1[i]);62 printf("\n");63 64 return 0;65 }
C. (字符串、贪心)Removing Columns
题意：
给出n×m(n,m≤100)的字符矩阵，求最少去掉多少列，使得剩下的字符串从上到下是按字典序费递减排列的。
分析：
单独看一列：如果某个字母比它下面的字母要大，那么这一列一定不能作为最终字符串开头的一列。
从左往右扫，直到找到能作为最终字符串开头的一列c1为止。
则c1一定要保留，作为字符串的开头，贪心的理由是：
如果后面也有一列c2满足作为字符串的开头，则c1...c2...从上到下一定满足字典序的顺序，而且不会使去掉的列数变多。
选好字符串开头以后，继续往后扫描：
如果本来某一行的字符串小于下面的字符串，则后面无论接什么样的字符，这两个字符串大小关系不变。
如果原来某一行字符串等于下面一行的字符串，则后面接的字符也要满足大小关系。
1 #include <cstdio> 2 3 const int maxn = 100 + 10; 4 bool bad[maxn], equ[maxn];//equ标记当前字符串中相邻两行是否相等 5 //bad标记该列是否被去掉，作为答案的统计 6 7 char table[maxn][maxn]; 8 9 int main()10 {11 //freopen("in.txt", "r", stdin);12 13 int n, m;14 scanf("%d%d", &n, &m);15 for(int i = 0; i < n; ++i) scanf("%s", table[i]);16 17 if(n <= 1)18 {19 puts("0");20 return 0;21 }22 23 int st = 0;//找到字符串的开头24 for(; st < m; ++st)25 {26 int i;27 for(i = 0; i < n-1; ++i)28 if(table[i][st] > table[i+1][st])29 break;30 if(i == n-1) break;31 }32 if(st == m)33 {34 printf("%d\n", m);35 return 0;36 }37 38 int ans = st;39 for(int i = 0; i < n-1; ++i)40 {41 if(table[i][st] == table[i+1][st])42 equ[i] = true;43 }44 for(int i = st+1; i < m; ++i)45 {46 for(int j = 0; j < n-1; ++j)47 {48 if(equ[j] && table[j][i] > table[j+1][i])//只有原来字符串相等且后面接的字符不满足顺才去掉该列49 bad[i] = true;50 }51 if(bad[i])52 ans++;//统计被去掉的行数53 else54 {55 for(int j = 0; j < n-1; ++j)56 {57 if(equ[j] && table[j][i] < table[j+1][i])//更新equ58 equ[j] = false;59 }60 }61 }62 63 printf("%d\n", ans);64 65 return 0;66 }
CodeForces Round #283 Div.2