A. Arpa’s hard exam and Mehrdad’s naive cheat
题意：统计1378^n的末尾数字
即统计8^n的末尾数字
n=0时为1
其他情况为{8，4，2，6}中的一个
#include <stdio.h>
const int ans[4] = { 6, 8, 4, 2 };
int main() {
static int n;
scanf("%d", &n);
if (n == 0) printf("1\n");
else printf("%d\n", ans[n % 4]);
return 0;
}
B. Arpa’s obvious problem and Mehrdad’s terrible solution
题意：给个数列a1...an和一个数x，问有多少对i，j（i < j）使 a[i] xor a[j] == x
记录每个每个数字出现在a数列中的次数，从而统计答案
注意开数组的范围
#include <stdio.h>
const int kMaxn = 200010;
int n, x, a[kMaxn], b[kMaxn];
long long ans;
int main() {
static int i;
scanf("%d%d", &n, &x);
memset(b, 0, sizeof(b));
for (i = 1; i <= n; ++i) {
scanf("%d", a + i);
++b[a[i]];
}
ans = 0;
for (i = 1; i <= n; ++i) {
if ((a[i] ^ x) == a[i])
ans += b[a[i]] - 1;
else
ans += b[a[i] ^ x];
}
printf("%I64d\n", ans >> 1);
return 0;
}
C. Vladik and flights
题意：在s[i] == s[j]时从i到j话费为0，否则为|i-j|，问从a到b最小花费
结果最大为1
s[a]==s[b]答案即为0，否则为1
#include <stdio.h>
const int kMaxn = 100010;
int n, a, b;
char s[kMaxn];
int main() {
static int i, ans;
scanf("%d%d%d", &n, &a, &b);
scanf(" %s", s + 1);
if (s[a] == s[b])
puts("0");
else
puts("1");
return 0;
}
D. Chloe and the sequence
题意：给你一个构造方案[1]->[1,2,1]->[1,2,1,3,1,2,1]->[1,2,1,3,1,2,1,4,1,2,1,3,1,2,1]......问操作n-1步后数列的第k个位置是什么数字
以[1,2,1,3,1,2,1,4,1,2,1,3,1,2,1]为例，
先判断k的位置在4上 ：输出结果
还是4左边：删掉4和4右边的数列
还是4右边：和左边是对称的，k=总长度减k，然后和左边一样处理
再类似判断3,2,1
#include <stdio.h>
int n;
long long k;
int main() {
static int i;
static long long tmp;
scanf("%d%I64d", &n, &k);
for (i = n; i >= 1; --i) {
tmp = (1LL << i);
//printf("%I64d %I64d\n", k, tmp);
if (k == tmp) {
printf("%d\n", i + 1);
return 0;
} else if (k > tmp)
k -= tmp;
}
printf("1\n");
return 0;
}
E. Vladik and fractions
题意：求构造2/n = 1/x + 1/y + 1/z，x，y，z为不一样的整数
n，n+1，n*（n+１）
#include <stdio.h>
long long n;
int main() {
static long long i, k, x, y, d;
scanf("%I64d", &n);
if (n == 1)
puts("-1");
else
printf("%I64d %I64d %I64d\n", n, n + 1, n * (n + 1));
return 0;
}
F. Compote
看懂题就能做出来。
#include <stdio.h>
int a, b, c;
int main() {
static int i;
scanf("%d%d%d", &a, &b, &c);
b /= 2;
c /= 4;
printf("%d\n", std::min(std::min(a, b), c) * 7);
return 0;
}
G. Decoding
题意：给个操作，每次去掉中间的字符，现有去掉字符的顺序，求原字符串
#include <stdio.h>
int n;
char s[2222], ans[2222];
int main() {
static int i, mid;
scanf("%d", &n);
scanf(" %s", s + 1);
mid = (n >> 1) + (n & 1);
ans[mid] = s[1];
for (i = 2; i <= n; ++i) {
if (n & 1)
ans[mid + (i & 1 ? (i >> 1) : -(i >> 1))] = s[i];
else
ans[mid + (i & 1 ? -(i >> 1) : (i >> 1))] = s[i];
}
for (i = 1; i <= n; ++i)
putchar(ans[i]);
return 0;
}
H. Tram
题意：有列车在一条直线上往返，已知列车的起始位置，方向，速度，人的初始位置，目标位置，步行速度，求人还要多久才能到达目的地
人要么走到目的地，要么坐车到目的地，比较车第一次经过人然后到目的地的时间与人直接走过去的时间，去较小者即可。
#include <stdio.h>
#include <algorithm>
int s, x1, x2, t1, t2, p, d, ans;
inline int myabs(int x) {
return x > 0 ? x : -x;
}
int main() {
static int i;
scanf("%d%d%d", &s, &x1, &x2);
scanf("%d%d", &t1, &t2);
scanf("%d%d", &p, &d);
if (t2 <= t1)
printf("%d\n", myabs(x2 - x1) * t2);
else {
ans = 0;
i = 0;
while (!i || p != x2) {
if (p == x1) i = 1;
p += d;
ans += t1;
if (p == 0 || p == s) d = -d;
}
ans = std::min(ans, myabs(x2 - x1) * t2);
printf("%d\n", ans);
}
return 0;
}
I. Green and Black Tea
题意：给G的个数，B的个数，G与B最长连续不能长于k，求构造方案
把G与B较小的找到，把较多的字母分为（较小的数的个数+1）段，每段尽量平均。
#include <stdio.h>
#include <algorithm>
int n, k, a, b, m;
char op;
inline int myabs(int x) {
return x > 0 ? x : -x;
}
int main() {
static int i, j;
scanf("%d%d%d%d", &n, &k, &a, &b);
op = 1;
if (a < b) {
op = 0;
std::swap(a, b);
}
m = a / (b + 1);
a %= (b + 1);
if (m + (a > 0) > k)
puts("NO");
else {
for (j = 1; j <= m + (a > 0); ++j)
putchar(op ? 'G' : 'B');
--a;
for (i = 1; i <= b; ++i) {
putchar(op ? 'B' : 'G');
for (j = 1; j <= m + (a > 0); ++j)
putchar(op ? 'G' : 'B');
--a;
}
}
return 0;
}