题目链接:uva 1385 - Billing Tables
题目大意:给定n个电话前缀,每个前缀是一个区域的前缀,现在要生成一个新的电话单,即对于每个电话号码,从旧的电话单上从前向后遍历,如果出现前缀匹配,则该电话号码对应的即为当前的区号,要求生成的新电话单尽量小。
解题思路:用dfs建立字典树,在区间范围内的点对应均为对应的区号,注意如果70、71、72、...79都为SB的话,那么可以合并成7,并且对应区号为SB。
注意合并的条件为区号相同即可,并不是说对应旧电话单匹配位置相同。
注意这组数据:0 - 9 all
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
const int sigma_size = 10;
typedef pair<string, string> pii;
struct Node {
int val;
Node* next[sigma_size];
Node() {
val = 0;
memset(next, 0, sizeof(next));
}
};
void clear(Node* &p);
void insert (Node* &p, int d, int L, int R, int tig);
void dfs(Node* p, string str);
int pushup(Node* &p, int tig);
map<string, int> g;
int n, m;
string l, r, name[105];
Node* root = NULL;
vector<pii> vec;
void init () {
vec.clear();
g.clear();
string tmp;
for (int i = 1; i <= m; i++) {
cin >> l >> tmp >> r >> name[i];
tmp = "";
int d = l.length() - r.length();
for (int i = 0; i < d; i++)
tmp += l[i];
tmp += r;
r = tmp;
if (l > r)
continue;
int k = i;
if (g.count(name[i]))
k = g[name[i]];
else
g[name[i]] = i;
insert(root, 0, 1, 1, k);
}
}
int main () {
int cas = 0;
while (cin >> m) {
if (cas++)
cout << endl;
init();
pushup(root, m+1);
dfs(root, "");
clear(root);
printf("%lu\n", vec.size());
for (int i = 0; i < vec.size(); i++)
cout << vec[i].first << " " << vec[i].second << endl;
}
return 0;
}
int pushup (Node* &p, int tig) {
if (p == NULL) {
p = new Node;
return p->val = tig;
}
if (p->val)
tig = p->val;
int k = pushup(p->next[0], tig);
for (int i = 1; i < sigma_size; i++) {
if (k != pushup(p->next[i], tig))
k = 0;
}
return p->val = k;
}
void dfs (Node* p, string str) {
if (p != root && p->val) {
if (p->val <= m && name[p->val] != "invalid")
vec.push_back(make_pair(str, name[p->val]));
return ;
}
for (int i = 0; i < sigma_size; i++) {
if (p->next[i] != NULL) {
char ch = '0' + i;
dfs(p->next[i], str + ch);
}
}
}
void insert (Node* &p, int d, int L, int R, int tig) {
if (p == NULL)
p = new Node;
if (p->val)
tig = p->val;
if (d >= l.length()) {
p->val = tig;
return;
}
if (L == 0 && R == 0) {
p->val = tig;
return;
} else if (L == 0) {
insert(p->next[r[d]-'0'], d + 1, 0, 1, tig);
for (int i = 0; '0' + i < r[d]; i++)
insert(p->next[i], d + 1, 0, 0, tig);
} else if (R == 0) {
insert(p->next[l[d]-'0'], d + 1, 1, 0, tig);
for (int i = l[d] - '0' + 1; i < sigma_size; i++)
insert(p->next[i], d + 1, 0, 0, tig);
} else if (r[d] == l[d]) {
insert(p->next[l[d]-'0'], d + 1, 1, 1, tig);
} else {
insert(p->next[l[d]-'0'], d + 1, 1, 0, tig);
insert(p->next[r[d]-'0'], d + 1, 0, 1, tig);
for (int i = l[d] + 1; i < r[d]; i++)
insert(p->next[i-'0'], d + 1, 0, 0, tig);
}
}
void clear(Node* &p) {
for (int i = 0; i < sigma_size; i++) {
if (p->next[i] != NULL)
clear(p->next[i]);
}
delete p;
p = NULL;
}
分享到:
相关推荐
资源来自pypi官网。 资源全名:django-aws-billing-0.1.3.tar.gz
react-native-billing, 在Android上,将本地桥反应到InApp计费 用于 Android 的InApp计费 本机计费 为 InApp Billing提供一个易于使用的界面,它通过包装anjlab计费库的 InApp来完成。const InAppBilling = require...
Reactive Billing for Android Cut the hassle when implementing in-app purchases on Android. Reactive Billing is a lightweight reactive wrapper around In App Billing API v3 for Android. Features ...
android-billing-services将模块连接到项目1.将子模块添加到项目存储库git submodule add https://github.com/LimeHD/android-billing-services.git2.将模块导入项目文件->新建->导入模块... 指定模块的路径,然后...
google-billing-4.0.0.jar
Android In-App Billing v3 Library This is a simple, straight-forward implementation of the Android v3 In-app billing API. It supports: In-App Product Purchases (both non-consumable and consumable) ...
sd - billing plan (sd-bil-iv)
android-play-billing-master.zip源码对你学习android会有帮助
Laravel开发-laravel-billing Laravel 5的账单套餐。
Laravel开发-billing .zip
python库。 资源全名:tencentcloud-sdk-python-billing-3.0.467.tar.gz
资源来自pypi官网。 资源全名:google-cloud-billing-0.1.0.tar.gz
资源来自pypi官网。 资源全名:django-customer-billing-1.2.0.tar.gz
资源来自pypi官网。 资源全名:tencentcloud-sdk-python-billing-3.0.357.tar.gz
Laravel开发-billing 为Laravel5 SaaS应用程序优化的条带通用接口。
资源分类:Python库 所属语言:Python 资源全名:django-customer-billing-1.7.8.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
资源分类:Python库 所属语言:Python 资源全名:django-customer-billing-1.7.17.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
指标此插件公开的指标是: aws billing total - 到目前为止,AWS 在此计费周期内收取的总金额aws billing estimated monthly total - 滚动 30 天的总成本估计对于每个product ,它将公开以下指标: a