zoj2661.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdlib>
using namespace std;

char s[20200][210];
int n;

int page[20200];
int pageNum = 0;
int m;


void div(){
    int p = 0;
    bool update;
    pageNum = 0;
    
    while (1){
        while (p < n && s[p][0] == 0) ++p;
        if (p >= n) return;
        ++pageNum;
        int j = p + m - 1;
        update = true;
        while (update){
            update = false;
            if (s[j][0] && s[j + 1][0] && s[j - 1][0] == 0){
                --j;
                update = true;
            }
            if (s[j][0] && s[j + 1][0] && s[j + 2][0] == 0){
                --j;
                update = true;
            }
        }
      
        for (int i = p; i <= j; i++) page[i] = pageNum;
        p = j + 1;
    }
}

vector <int> ini;
map <string, vector <int> > w_map;
map <string, vector <int> >::iterator ite;

inline bool isChar(char c){
    return( (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') );
}

inline void upChar(char* s){
    int i;
    for (i=0; s[i]; i++)
        if (s[i] >= 'a' && s[i] <= 'z')
            s[i] += 'A' - 'a';
}

void inmap(){
    int p;
    char temp[210];
    string str;
    w_map.clear();
    for (int i = 0; i < n; i++)
        if (s[i][0]){
            int j = 0;
            while (s[i][j]){
                while (s[i][j] && !isChar(s[i][j])) ++j;
                if (s[i][j] == 0) break;
            
                for (p = 0; isChar(s[i][j + p]); p++) temp[p] = s[i][j + p];
                temp[p] = 0;
                upChar(temp);
                str = temp;
            
                ite = w_map.find(str);
                if (ite != w_map.end()){
                    if (ite->second[ ite->second.size() - 1 ] != page[i])
                        ite->second.push_back(page[i]);
                }
                else{
                    w_map[str] = ini;
                    ite = w_map.find(str);
                    ite->second.clear();
                    ite->second.push_back(page[i]);
                }
            
                j += p;
            }
        }
}

void output(){
    vector <int> *now;
    int i, j;
    bool out;
    for (ite = w_map.begin(); ite != w_map.end(); ite++){
        now = &ite->second;
        printf("%s ", ite->first.c_str());
        bool first = false;
        for (int i = 0; i < (*now).size(); i++){
            if (first) printf(","); else first = true;
            for (j=i+1; j < (*now).size() && (*now)[j] == (*now)[j - 1] + 1; j++);
            if (j - i >= 3) printf("%d-%d", (*now)[i], (*now)[j - 1]);
            else if (j - i == 1) printf("%d", (*now)[i]);
            else printf("%d,%d", (*now)[i], (*now)[i + 1]);
            i = j - 1;
        }
        printf("\n");
    }
}

bool isdigit(char x){
    return (x >= '0' && x <= '9');
}

bool isnum(char *s){
    if (!s[0]) return false;
    for (int i = 0; s[i]; i++)
        if (!isdigit(s[i])) return false;
    return true;
}

int tonum(char *s){
    int ret = 0;
    for (int i = 0; s[i]; i++)
        ret = ret * 10 + s[i] - '0';
    return ret;
}

int main(){
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    char tts[1000]; 
    bool finish = false;
    int tm;
    scanf("%d", &m);
    getchar();
    while (1){
        n = 0; memset(s, 0, sizeof(s));
        while (1){
            if (!gets(tts)) { finish = true; break; }
            if (isnum(tts)) { tm = tonum(tts); break; }
            strcpy(s[n++], tts);
        };
        div();
        inmap();
        output();
        if (finish) break;
        m = tm;
    }
    return(0);
}