[常州市赛 2025] 压缩

Luogu
IDLGB4392
Time1000ms
Memory512MB
DifficultyP4
字符串2025江苏枚举科创活动小学活动
小 Y 开发了一种名为“别重复”的新型数据压缩策略。“别重复”作用于字符串,若字符串中存在两个连续相同的子串,则会删除其中一个。例如,在字符串 $\tt alfalfaseeds$ 中,“别重复”可删除 $\tt seeds$ 中的一个 $\tt e$和 $\tt alfalfa$ 中的一个 $\tt lfa$,得到 $\tt alfaseds$。 “别重复”还能利用先前的删除效果,例如在 $\tt seventeenth\ baggage$ 中,先删除重复的 $\tt e$ 和 $\tt g$ 得到 $\tt sevententh\ bagage$,再删除重复的 $\tt ent$ 和 $\tt ag$,最终得到 $\tt seventh\ bage$。 当存在多个重复子串可删除时,最优的“别重复”会选择使最终字符串最短的方式。例如,在 $\tt ABBCDCABCDCD$ 中,优先删除开头的 $\tt B$ 再删除 $\tt ABCDC$ 可压缩为 $\tt ABCD$,而若先删除末尾的 $\tt CD$ 再删除 $\tt B$ 则最终只能得到 $\tt ABCDCABCD$。最优的“别重复”会选择先删除 $\tt B$ 再删除 $\tt ABCDC$ 的方式。 小 Y 要求为带通配符的二进制字符串(仅含 $\tt 0,1,\#$,$\tt\#$ 为通配符)实现最优的“别重复”算法。你需要在进行“别重复”压缩算法前为通配符进行赋值,值为 $\tt 0$ 或者 $\tt 1$,使得赋值之后的二进制字符串通过应用最优的“别重复”能得到最短的字符串。 ## Input 一行一个带通配符的二进制字符串。 ## Output 一行一个字符串表示应用最优的“别重复”能得到的最短字符串。数据保证应用最优的“别重复”能得到的最短字符串有且只有一种唯一情况。 [samples] ## Background 搬运自 <http://czoj.com.cn/p/1409>。数据为民间数据。 ## Note 本任务共有 $10$ 个数据。 对于全部数据:保证字符串长度不超过 $10^5$,数据保证应用最优的“别重复”能得到的最短字符串有且只有一种唯一情况。 |测试点编号|特殊性质| |:-:|:-:| |$1\sim2$|字符串长度不超过 $3$| |$3\sim4$|字符串中不包含 $\tt0$| |$5\sim8$|字符串中不包含 $\tt\#$| |$9\sim10$|无|
Samples
Input #1
111#
Output #1
1
Input #2
10#
Output #2
10
Input #3
10##1
Output #3
101
API Response (JSON)
{
  "problem": {
    "name": "[常州市赛 2025] 压缩",
    "description": {
      "content": "小 Y 开发了一种名为“别重复”的新型数据压缩策略。“别重复”作用于字符串,若字符串中存在两个连续相同的子串,则会删除其中一个。例如,在字符串 $\\tt alfalfaseeds$ 中,“别重复”可删除 $\\tt seeds$ 中的一个 $\\tt e$和 $\\tt alfalfa$ 中的一个 $\\tt lfa$,得到 $\\tt alfaseds$。 “别重复”还能利用先前的删除效果,例如在 $\\t",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4392"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 Y 开发了一种名为“别重复”的新型数据压缩策略。“别重复”作用于字符串,若字符串中存在两个连续相同的子串,则会删除其中一个。例如,在字符串 $\\tt alfalfaseeds$ 中,“别重复”可删除 $\\tt seeds$ 中的一个 $\\tt e$和 $\\tt alfalfa$ 中的一个 $\\tt lfa$,得到 $\\tt alfaseds$。 “别重复”还能利用先前的删除效果,例如在 $\\t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments