FZU月赛20160416 ABEF

时间:2023-12-29 22:06:08
Problem A ABCDEFG

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

FZU月赛20160416 ABEF Problem Description

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

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

(附:英文字母标准手写体教程:

FZU月赛20160416 ABEF

FZU月赛20160416 ABEF Input

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

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

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

FZU月赛20160416 ABEF Output

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

FZU月赛20160416 ABEF Sample Input

2
ABCDEFG
abcdefg

FZU月赛20160416 ABEF 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

FZU月赛20160416 ABEF Problem Description

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

具体来说,给出两个整数m、n:

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

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

FZU月赛20160416 ABEF Input

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

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

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

FZU月赛20160416 ABEF Output

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

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

FZU月赛20160416 ABEF Sample Input

4
4 2
1 5
123 765
2 1380779

FZU月赛20160416 ABEF 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

FZU月赛20160416 ABEF 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。

FZU月赛20160416 ABEF Input

题目包含多组数据

每组数据第一行一个数n

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

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

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

N<=10^5

Q<=10^4

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

1<=l<=r<=n

FZU月赛20160416 ABEF Output

每个询问输出一个数组dis

FZU月赛20160416 ABEF Sample Input

5
1 2 3 1 2
3
3 3
2 5
1 5

FZU月赛20160416 ABEF 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

FZU月赛20160416 ABEF Problem Description

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

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

FZU月赛20160416 ABEF Input

题目有多组数据。

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

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

输入数据保证有解。

FZU月赛20160416 ABEF Output

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

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

FZU月赛20160416 ABEF Sample Input

2
1 100
100 2
3
3 1
100 2
3 2

FZU月赛20160416 ABEF 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 ;
}