FZU月赛20160416 ABEF

Problem A ABCDEFG

Accept: 302    Submit: 442
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

表弟今天的英语作业是练习书写前7个英文字母。勤奋的他写了一页、一页、又一页……

Yellowstar想知道表弟总共写了多少笔划。

（附：英文字母标准手写体教程：

）

 Input

输入第一行为一个正整数T。

接下去T行，每行为前七个英文字母的大小写形式组成的非空字符串，表示一份作业。

T<=20,每行长度<=100。

 Output

对于每份作业，输出一行，表示其中的笔划总数。

 Sample Input

2

ABCDEFG

abcdefg

 Sample Output

15

9

思路：比赛简单

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + ;
int r1[] = {, , , , , , };
int r2[] = {, , , , , , };
int main() {
   // freopen("in", "r", stdin);
   int _; scanf("%d", &_);
   while(_ --) {
        int ans = ;
        char s[];
        scanf("%s", s);
        int ls = strlen(s);
        for(int i = ; i < ls; ++i) {
            if(s[i] >= 'A' && s[i] <= 'Z') ans += r1[ s[i] - 'A' ];
            else ans += r2[ s[i] - 'a' ];
        }
        printf("%d\n", ans);
   }
   return ;
}

Problem B 神奇的计算器

Accept: 14    Submit: 362
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

为了帮助正在学习除法的表弟，Yellowstar想制作一个计算器，它能给出整数除法的完整结果。

具体来说，给出两个整数m、n：

如果m/n是整数或有限小数，那么直接输出它的值。

如果m/n是无限小数，那么输出小数点后到第一个最小循环节为止，并用”()”把最小循环节括起来。

 Input

输入第一行为一个正整数T，表示有T组测试数据。

接下去T行，每行为一组数据。每行两个正整数m、n，含义如上。

T<=15,1<=m,n<=2^31-1。

 Output

每个样例一行，输出答案。

注意计算器的屏幕最多能输出1 000 000个字符（包括小数点和括号，不包括结尾的换行），如果某组数据的结果超过了这个长度，那么该组数据输出”Too long”而不是原答案。

 Sample Input

4

4 2

1 5

123 765

2 1380779

 Sample Output

2

0.2

0.1(6078431372549019)

Too long

思路：题目要求的是最先出现的最小循环节，模拟除法，容易发现就是某个余数再次出现时会形成循环节。那么就是要记录余数是否出现过，用map或set会tle，那么就考虑hash

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const int N = 2e6 + ;
const int mod = ;
char dig[N];
struct hashmap
{
    int key[N], p[N];
    int head[mod], nx[N], tot;
    void init()
    {
        memset(head, -, sizeof head);
        tot = ;
    }
    void ins(int x, int pos)
    {
        int h = x % mod;
        key[tot] = x;
        p[tot] = pos;
        nx[tot] = head[h];
        head[h] = tot++;
    }
    int query(int x)
    {
        int h = x % mod;
        for(int i = head[h]; ~i; i = nx[i])
        {
            if(key[i] == x) return p[i];
        }
        return -;
    }
};
hashmap myhash;
void solve(int x, int y)
{
    int num = , px, py;
    int qeu = x / y;
    sprintf(dig, "%d", qeu);
    num = strlen(dig);
    int rem = x - qeu * y;
    int flag = ;
    if(rem == ) puts(dig);
    else
    {
        myhash.init();
        myhash.ins(rem, num + );
        dig[num++] = '.';
        while(num < 1e6 + )
        {
            qeu = (ll)rem *  / y;
            rem = (ll)rem *  - qeu * y;
            dig[num++] = qeu + ;
            if(rem == ) break;
            int v = myhash.query(rem);
            if(v != -)
            {
                px = v;
                flag = ;
                break;
            }
            myhash.ins(rem, num);
        }
        dig[num] = ;
        if(num >= 1e6) puts("Too long");
        else if(flag == ) {
            puts(dig);
        }else {
            for(int i = ; i < num; ++i) {
                if(i == px) printf("(");
                printf("%c", dig[i]);
            }
            puts(")");
        }
    }
}
int main()
{
    int _;
    scanf("%d", &_);
    while(_ --)
    {
        int m, n;
        scanf("%d%d", &m, &n);
        solve(m, n);
    }
}

Problem E 信心题

Accept: 37    Submit: 600
Time Limit: 2000 mSec    Memory Limit : 32768 KB

 Problem Description

给定一个含有n个数字的数列，每个数字都有一个值a[i]（下标从1开始）。定义第i个数字和第j个数字间的距离dis(i,j)=abs(i-j)。

接下来给出q个询问，每次询问一个区间[l,r]，要求求出一对数字(i,j)(l<=i<=j<=r),使得a[i]=a[j]并且dis(i,j)最大，由于这样的数对可能有多个，因此答案只要输出dis。

 Input

题目包含多组数据

每组数据第一行一个数n

第二行n个数字，表示数列a

第三行一个数字q，表示询问个数

接下来q行，每行两个数l,r,表示询问

N<=10^5

Q<=10^4

1<=a[i]<=10^3

1<=l<=r<=n

 Output

每个询问输出一个数组dis

 Sample Input

5

1 2 3 1 2

3

3 3

2 5

1 5

 Sample Output

0 3 3

思路：容易想到的做法是把所有的数分组后，对于每一个查询二分，复杂度为nmlog，会tle。对于nm的做法是离线处理，把所有的数分组后，设L[k]和R[k]分别为第k个查询对应的区间[l,r]中数ai最左端的位置和最右端的位置，那么ai对于第k个查询贡献的答案为R[k]-L[k]

L[k]只要分别对所有的查询按左端点排序然后依次分配编号即可，R[k]同理

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
const int N = 1e5 + ;
struct Query {
    int l, r, id;
    Query() {}
    Query(int l, int r, int id) : l(l), r(r), id(id) {}
};
vector<int> V[];
Query sl[N], sr[N], Q[N];
int n, q;
int a[N], L[N], R[N], ans[N];
void read() {
    for(int i = ; i < n; ++i) scanf("%d", &a[i]);
        scanf("%d", &q);
        int l, r;
        for(int i = ; i < q; ++i) {
            scanf("%d%d", &l, &r);
            --l; --r;
            Q[i] = Query(l, r, i);
            sl[i] = sr[i] = Q[i];
        }
}
int cmp1(Query a, Query b) { return a.l < b.l; }
int cmp2(Query a, Query b) { return a.r > b.r; }
void init() {
    for(int i = ; i <= ; ++i) V[i].clear();
    memset(ans, , sizeof ans);
    sort(sl, sl + q, cmp1);
    sort(sr, sr + q, cmp2);
    for(int i = ; i < n; ++i) V[ a[i] ].push_back(i);
}

void solve() {
    for(int i = ; i <= ; ++i) {
        int k1 = , k2 = , k;
        int sx = V[i].size();
        if(sx == ) continue;

        for(int j = ; j < sx; ++j)
        {
            int p = V[i][j];
            for(k = k1; k1 < q && k < q; ++k) if(p >= sl[k].l) L[ sl[k].id ] = p; else break;
            k1 = k;
        }
        for(int j = sx-; j >= ; --j)
        {
            int p = V[i][j];
            for(k = k2; k2 < q && k < q; ++k) if(p <= sr[k].r) R[ sr[k].id ] = p; else break;
            k2 = k;
        }
        for(int k = k1; k < q; ++k) L[ sl[k].id ] = n;
        for(int k = k2; k < q; ++k) R[ sr[k].id ] = ;

        for(int k = ; k < q; ++k) if(L[k] >= Q[k].l && L[k] <= Q[k].r && R[k] >= Q[k].l && R[k] <= Q[k].r)
            ans[k] = max(ans[k], R[k] - L[k]);
    }
}
int main() {
   // freopen("in.txt", "r", stdin);
    while(~scanf("%d", &n)) {
        read();
        init();
        solve();
        for(int i = ; i < q; ++i) printf("%d\n", ans[i]);
    }
    return ;
}

Problem F 邮票

Accept: 113    Submit: 523
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

一天Bob收到一封信。Bob知道瓦罗兰大陆的邮局从A城市送信到B城市，乐意使用从A城市到B城市的邮票（A, B）,或者使用从B城市到A城市的邮票（A, B），但是由于瓦罗兰大陆的城市繁多，所以并不是所有城市之间都能直接发送接收信件，换句话说，某两个城市想要通行邮件必须经过其他城市才行，但是邮局发送一次邮件的路途中从不会通过一座城市两次。

现在在Bob的信封上有N个邮票，Bob想知道这封信件是如何周转到达他手中的。

 Input

题目有多组数据。

每组数据第一行包含一个整数，N ( 2 <= N <= 1e5)，代表信件上的N封邮票。

接下有N行数据。第 i 行数据包含两个整数 ui，vi，代表从城市ui发送到城市vi的邮票，ui代表城市的编号，每个城市的编号互不相同，(ui != vi ，1 <= ui, vi <= 1e9)。

输入数据保证有解。

 Output

每组样例的结果输出为一行， 每行包括N+1个被空格隔开的整数，代表着信件依次经过的城市编号。

若有多组可行答案，输出字典序最小的那组答案。

 Sample Input

2

1 100

100 2

3

3 1

100 2

3 2

 Sample Output

1 100 2

1 3 2 100

题意：给出n条边，其中每个点的度要么为2要么为1，度为1的点只有两个，即起点或终点。要求输出从起点到终点的一条字典序最小的路径，每个点只经过一次。就两种情况，选起点小的输出就可以了。由于点的编号比较大，要离散化。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + ;
int a[N], U[N], V[N];
int vis[N];
vector<int> g[N << ];
int main() {
   // freopen("in", "r", stdin);
   int n;
   while(~scanf("%d", &n)) {
       memset(vis, , sizeof vis);
       for(int i = ; i <= n; ++i) g[i].clear();

       int tot = ;
       for(int i = ; i < n; ++i) {
        scanf("%d%d", &U[i], &V[i]);
        a[tot++] = U[i];
        a[tot++] = V[i];
       }
       sort(a, a + tot);
       tot = unique(a, a + tot) - a;
       for(int i = ; i < n; ++i) {
        int u = lower_bound(a, a + tot, U[i]) - a, v = lower_bound(a, a + tot, V[i]) - a;
        g[u].push_back(v);
        g[v].push_back(u);
       }
       int x = -, y = -;
       for(int i = ; i < tot; ++i) {
        if(g[i].size() == ) {
            if(x == -) x = i;
            else y = i;
        }
       }
       if(a[x] > a[y]) swap(x, y);
       printf("%d ", a[x]);
       vis[x] = ;
       x = g[x][];
       for(int i = ; i < n - ; ++i) {
           printf("%d ", a[x]);
           vis[x] = ;
            int u = g[x][];
            int v = g[x][];
            if(vis[u]) x = v;
            else x = u;
       }
       printf("%d\n", a[x]);
   }
   return ;
}