A. Removing Columns
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given ann×mrectangular table consisting of lower case English letters. In one operation you can completely remove one column from the table. The remaining parts are combined forming a new table. For example, after removing the second column from the table
abcdedfghijk
we obtain the table:
acdefghjk
A table is calledgoodif its rows are ordered from top to bottom lexicographically, i.e. each row is lexicographically no larger than the following one. Determine the minimum number of operations of removing a column needed to make a given table good.
Input
The first line contains two integers —nandm(1≤n,m≤100).
Nextnlines containmsmall English letters each— the characters of the table.
Output
Print a single number— the minimum number of columns that you need to remove in order to make the table good.
Sample test(s)
input
1 10codeforces
output
0
input
4 4casecaretestcode
output
2
input
5 4codeforcescodeforces
output
4
Note
In the first sample the table is already good.
In the second sample you may remove the first and third column.
In the third sample you have to remove all the columns (note that the table where all rows are empty is considered good by definition).
Let stringssandthave equal length. Then,sislexicographically largerthantif they are not equal and the character following the largest common prefix ofsandt(the prefix may be empty) insis alphabetically larger than the corresponding character oft.
贪心。
我们可以发现从左往右扫，当前能取的列就一定要取，取了不会更差，只会更好。
什么是能取的列？
在之前所有取好的列中，如果每一列这一行，下一行。。。都相同，那么当前这列的这几行必须满足不减性质，否则任意。
#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <string>#define mp make_pair#define f first#define s secondusing namespace std;pair<int,int> q[10000],qq[10000];int n,m,f[105],cnt;string s[105];int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)cin>>s[i];int ans=0;cnt=1;q[1]=mp(1,n);for (int i=0;i<m;i++){int ok=1;for (int j=1;j<=cnt;j++){for (int k=q[j].f+1;k<=q[j].s;k++)if (s[k][i]<s[k-1][i]) ok=0;if (!ok) break;}if (ok) {ans++;for (int j=1;j<=cnt;j++)qq[j]=q[j];int c=0;for (int j=1;j<=cnt;j++){int l=qq[j].f;for (int k=qq[j].f+1;k<=qq[j].s;k++){if (s[k][i]!=s[k-1][i]){if (k!=l+1){q[++c]=mp(l,k-1);}l=k;}}if (l!=qq[j].s)q[++c]=mp(l,qq[j].s);}cnt=c;}}cout<<m-ans<<endl;return 0;}
B. Tennis Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Petya and Gena love playing table tennis. A single match is played according to the following rules: a match consists of multiple sets, each set consists of multiple serves. Each serve is won by one of the players, this player scores one point. As soon as one of the players scorestpoints, he wins the set; then the next set starts and scores of both players are being set to 0. As soon as one of the players wins the total ofssets, he wins the match and the match is over. Heresandtare some positive integer numbers.
To spice it up, Petya and Gena choose new numberssandtbefore every match. Besides, for the sake of history they keep a record of each match: that is, for each serve they write down the winner. Serve winners are recorded in the chronological order. In a record the set is over as soon as one of the players scorestpoints and the match is over as soon as one of the players winsssets.
Petya and Gena have found a record of an old match. Unfortunately, the sequence of serves in the record isn’t divided into sets and numberssandtfor the given match are also lost. The players now wonder what values ofsandtmight be. Can you determine all the possible options?
Input
The first line contains a single integern— the length of the sequence of games (1≤n≤105).
曾经一直想让别人知道自己的心情，那些沉重，
