ACM/ICPC 之 暴力打表-编码

///找到一个数字序列包含所有n位数(连续)一次且仅一次
///暴力打表
///Time:141Ms    Memory:2260k
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

#define MAX 1000010

bool v[MAX];
char num[6][MAX];

int main()
{
    //freopen("in.txt", "r", stdin);
    for(int t = 1; t <= 6; t++)
    {
        //初始化
        memset(v, false, sizeof(v));
        int len = t-1, mod = 1;
        for(int i = 1; i <= t; i++)
            mod *= 10;  //mod:取模数
        len += mod; //输出总数
        for(int i = 0; i < t; i++)
            num[t-1][i] = ‘0‘;

        int cur = 0;
        v[cur] = true;
        for(int i = t; i < len; i++)
        {
            int j = 0;  //向后一位试探0-9
            for(; j < 10; j++)
            {
                int last = (cur * 10 + j) % mod;
                if(!v[last]){   //标识
                    cur = last;
                    v[cur] = true;
                    break;
                }
            }
            if(j == 10){    //试探未果
                num[t-1][--i]++;    //回推一位+1
                v[cur] = false;     //取消已有标识
                while(num[t-1][i] == ‘0‘ + 10 || v[cur+1])  //超出十进制或已标识
                {
                    if(num[t-1][i] != ‘0‘ + 10 && v[cur + 1]){  //仅仅已标识
                        num[t-1][i]++;
                        cur++;
                        continue;
                    }
                    i--;    //否则继续回推+1
                    cur = ((num[t-1][i-t+1] - ‘0‘) * mod + cur)/10;
                    v[cur] = false;
                    num[t-1][i]++;
                }
                cur++;
                continue;
            }
            else num[t-1][i] = ‘0‘ + j;
        }
    }

    int n;
    while(scanf("%d", &n), n)
        printf("%s\n", num[n-1]);
    return 0;
}
时间: 07-21

ACM/ICPC 之 暴力打表-编码的相关文章

ACM/ICPC 之 数据结构-邻接表+BFS(TshingHua OJ-无线广播Broadcast)

这道题中若能够构成互不干扰的区域,其构成的图其实就是汉密尔顿路(Hamilton road),因此如果能够观察出来可以直接转化为汉密尔顿路的存在性证明,即便不能观察,我相信ACMer也能转化为BFS问题,这道题是一道很好的图论问题,对考察自己图论的基本功很有帮助. 无线广播(Broadcast) 描述 某广播公司要在一个地区架设无线广播发射装置.该地区共有n个小镇,每个小镇都要安装一台发射机并播放各自的节目. 不过,该公司只获得了FM104.2和FM98.6两个波段的授权,而使用同一波段的发射机

ACM/ICPC 之 数据结构-邻接表+DP+队列+拓扑排序(TshingHua OJ-旅行商TSP)

做这道题感觉异常激动,因为在下第一次接触拓扑排序啊= =,而且看了看解释,猛然发现此题可以用DP优化,然后一次A掉所有样例,整个人激动坏了,哇咔咔咔咔咔咔咔~ 咔咔~哎呀,笑岔了- -|| 旅行商(TSP) Description Shrek is a postman working in the mountain, whose routine work is sending mail to n villages. Unfortunately, road between villages is

【ZOJ】3785 What day is that day? ——浅谈KMP应用之ACM竞赛中的暴力打表找规律

首先声明一下,这里的规律指的是循环,即找到最小循环周期.这么一说大家心里肯定有数了吧,“不就是next数组性质的应用嘛”. 先来看一道题 ZOJ 3785 What day is that day? Time Limit: 2 Seconds      Memory Limit: 65536 KB It's Saturday today, what day is it after 11 + 22 + 33 + ... + NN days? Input There are multiple tes

2016 ACM/ICPC Asia Regional Qingdao Online 1001/HDU5878 打表二分

I Count Two Three Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 782    Accepted Submission(s): 406 Problem Description I will show you the most popular board game in the Shanghai Ingress Resis

ACM ICPC 2008–2009 NEERC MSC A, B, C, G, L

这套题是我上周日, 就是前天打得一场组队赛, 题目不太好找 题目链接:http://codeforces.com/gym/100861 在virtual judge 上也可以提交哦! A ACM ICPC Rules: 题目大意: 有很多所高校参加预选赛, 并在预选赛取得了排名, 但是对于每所学校, 除了MSU有4个名额之外其他大学只有两个名额( 也就是说, 只有每个大学的前2名进决赛(MSU前四名)&& 最多有10个队伍进入决赛), 高中队伍不能进入决赛. 给出预选赛的排名, 输出可以进

2016年acm icpc 青岛站(中国石油大学(华东))总结

2016年acm icpc 青岛站(中国石油大学(华东))总结 2016年11月11日,在这个传说中所谓的单身节,我们出发了,做了整整一天的车来到了青岛.不得不提一下,作为一个身处华中沿海地区的童鞋,这是我人生第一次坐了这么久的高铁(真的无聊,无聊,无聊),然后到了青岛是晚上了(挤公交车真的是一件很刺激的事情). 海风那个吹, 海水那个涌, 冻得萌新瑟瑟发抖. 也许是知道我们要来挖石油的缘故吧, 老天爷特意给了我们三天晴天. 晚上也没啥事,就这么洗洗睡了,不对还有传说中学长带领学弟剁手呢! 第二

HDU 1012 u Calculate e【暴力打表,水】

u Calculate e Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 46844    Accepted Submission(s): 21489 Problem Description A simple mathematical formula for e is where n is allowed to go to infini

【转】[email&#160;protected]&#183;ACM/ICPC 回忆录

转自:http://hi.baidu.com/ordeder/item/2a342a7fe7cb9e336dc37c89 2009年09月06日 星期日 21:55 初识ACM最早听说ACM/ICPC这项赛事是在大三上的算法课上张老师提到的,当时我们学校的组织参加这项活动才刚刚起步,我也没太在意,总觉得那是非常遥远的事,事实上当时我也从未相当如今我们能获得现在的成绩.真正踏入ACM/ICPC这个神奇的世界,不得不提到2004那一年我们学校的参赛队伍xmutank,正是听了pipo师兄的精彩演讲以

【题解】 2015 ACM/ICPC Asia Regional Shenyang Online

[1006] FangFang (暴力枚举) Fang Fang Time Limit: 1500/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 871    Accepted Submission(s): 364 Problem Description Fang Fang says she wants to be remembered. I promise her.