惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

Attack and Defense Labs
Attack and Defense Labs
The GitHub Blog
The GitHub Blog
C
Check Point Blog
博客园_首页
MongoDB | Blog
MongoDB | Blog
N
Netflix TechBlog - Medium
F
Full Disclosure
Microsoft Security Blog
Microsoft Security Blog
爱范儿
爱范儿
Recent Announcements
Recent Announcements
阮一峰的网络日志
阮一峰的网络日志
G
GRAHAM CLULEY
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
T
Threat Research - Cisco Blogs
C
Cybersecurity and Infrastructure Security Agency CISA
V
Vulnerabilities – Threatpost
K
Kaspersky official blog
博客园 - 司徒正美
S
Schneier on Security
T
The Exploit Database - CXSecurity.com
Project Zero
Project Zero
云风的 BLOG
云风的 BLOG
Cisco Talos Blog
Cisco Talos Blog
Know Your Adversary
Know Your Adversary
雷峰网
雷峰网
V
V2EX - 技术
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
Spread Privacy
Spread Privacy
罗磊的独立博客
K
KPMG report finds enterprise disconnect between AI and its ROI | CIO
S
Security Affairs
SecWiki News
SecWiki News
Schneier on Security
Schneier on Security
O
OpenAI News
Jina AI
Jina AI
PCI Perspectives
PCI Perspectives
Cyberwarzone
Cyberwarzone
Y
Y Combinator Blog
Apple Machine Learning Research
Apple Machine Learning Research
B
Blog RSS Feed
I
InfoQ
D
Docker
P
Palo Alto Networks Blog
Recorded Future
Recorded Future
M
MIT News - Artificial intelligence
博客园 - Franky
B
Blog
Scott Helme
Scott Helme
博客园 - 叶小钗
D
DataBreaches.Net

博客园 - hoodlum1980

ZOJ 1004. Anagrams by Stack 解题报告 【Release】Photoshop ICO file format plug-in v3.0 (supports both x86 and x64) 【发布】Photoshop ICO 文件格式插件 3.0 (支持 x64) [发布] 一个测试 WebService 和数据库连接的高性能工具 - DBTest ZOJ 1095. Humble Numbers 去除搜狗输入法弹窗骚扰的一个简易方法 ZOL 3977. Pointers 高斯模糊算法的 C++ 实现 对象布局已知时 C++ 对象指针的转换时地址调整 采用栈数据结构的二叉树非递归遍历 “金山杯2007逆向分析挑战赛”第一阶段第二题 “金山杯2007逆向分析挑战赛”第一阶段第一题分析 对《神奇的C语言》文中例子 5 代码的分析讨论 对"QQGame-大家来找茬"的辅助工具的改进 memset 的实现分析 ZOJ 1958. Friends Dell笔记本刷回低版本bios的方法 [发布] Photoshop 绘制表格滤镜(DrawTable) 采用路径模型实现遍历二叉树的方法
ZOJ 3481. Expand Tab
hoodlum1980 · 2014-07-25 · via 博客园 - hoodlum1980

  题目:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4278 (已经失效。2025-10-30 注。)

  新的链接是:ZOJ 3481. Expand Tab  (--add on 2025-10-30)

  题意:

  给出一些文本片段,把文本中的 Tab 字符根据配置,替换成一定数量的空格。

  配置分为两种,一种是只提供一个 ts 值,则需要缩进到的位置是一个等比数列。另一种是提供一个 ts 的有限集合,指定一些给定 ts 值,在逻辑上这个集合是无限的,当列位置超出集合中的数字时,后续的 tabstop 位置为连续的以 1 个空格进行递增。

  即:

  { T } 在逻辑上相当于 { T, T * 2, T * 3, T * 4, ...... };

  { T1, T2, ..., Tk } 在逻辑上相当于 { T1, T2, ..., Tk, Tk + 1, Tk + 2, Tk + 3, ...... };

  分析:

  本题目本身是比较简单的。但是值得注意的是:

  (1)当给定一个 ts 序列时,ts 序列的数字无序且可能重复(如果去重,可能会导致数组中只剩下一个数字,这时候不能当做等比数列来处理。如果不去重就不必在意这个问题)。所以不能假设序列有序,可以对这个序列进行一次排序。

  (2)当只提供一个 ts 值,这时为等比数列。最开始我使用了类似图像的行对齐公式来计算 stop 位置,结果这在一些情况下,结果会多考虑一个 ts 值。实际上的索引为 iCol 的列的 tabstop 值,公式仅仅是 (iCol / ts + 1) * ts 即可。由于我在这里编码心态过急,犯下这个低级失误,导致我不断的 PE N 次,差点崩溃。回到家里我慢慢查看这些步骤才找到这个错误。

  代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct _TabStop {
    int count;
    int ts[500];
    char delimit[1024];
} TABSTOP, *LPTABSTOP;

//解析配置信息
void ParseTabStop(char *line, LPTABSTOP pTS);

//获取 tab stop 位置
int GetStopCol(int iCol, LPTABSTOP pTS);

//排序用的比较函数
int cmp(const void* p1, const void* p2);

TABSTOP g_TS;

int main() 
{
    int i, T, col, stopCol;
    char line[1024], *p;

    scanf("%ld\n", &T);
    for(i = 0; i < T; i++) {
        gets(line);
        memset(&g_TS, 0, sizeof(TABSTOP));
        ParseTabStop(line, &g_TS);

        while(true) {
            gets(line);

            if(strcmp(line, g_TS.delimit) == 0) {
                gets(line); /*case结尾的空行*/
                printf("\n");
                break;
            }

            col = 0;
            p = line;
            while(*p) {
                if(*p == '\t') {
                    stopCol = GetStopCol(col, &g_TS);
                    while(col < stopCol) {
                        printf(" ");
                        ++col;
                    }
                }
                else {
                    printf("%c", *p);
                    ++col;
                }

                ++p;
            }
            printf("\n");
        }
    }
    return 0;
}

//解析 tabstop 配置
void ParseTabStop(char *line, LPTABSTOP pTS)
{
    /*expand tab-stops-configuration <<delimiting-identifier*/

    char *p = line + 7;
    char ch;
    int index = 0;

    while(*p) {
        ch = *p; 

        if(ch >= '0' && ch <= '9')
            pTS->ts[index] = pTS->ts[index] * 10 + (*p - '0');
        else if(ch == ',')
            ++index;
        else if(ch == '<') {
            strcpy(pTS->delimit, p + 2);
            break;
        }
        ++p;
    }

    pTS->count = index + 1;
    qsort(pTS->ts, pTS->count, sizeof(int), cmp);
}

//获取当前列的 tabstop 位置
int GetStopCol(int iCol, LPTABSTOP pTS)
{
    int i;
    if(pTS->count == 1) {
        return (iCol / pTS->ts[0] + 1) * pTS->ts[0];
    }
    else {
        if(pTS->ts[pTS->count-1] <= iCol)
            return iCol + 1;

        for(i = 0; i < pTS->count; i++) {
            if(iCol < pTS->ts[i])
                return pTS->ts[i];
        }
    }
    return iCol + 1;
}

int cmp(const void* p1, const void* p2)
{
    int *pX1 = (int*)p1;
    int *pX2 = (int*)p2;
    return *pX1 - *pX2;
}

ZOJ_3481_cpp

  补充:

  当然,如果不对序列进行排序,也是可以的。区别只是在获取 tabstop 位置时,每次都要完整的线性遍历这个集合(在有序的情况下可以提前结束遍历,或者进一步的用二分查找快速定位),尝试找到满足条件 ts > iCol 的所有 ts 中的最小值即可。