摘要：
本文是The 2018 ACM-ICPC Asia Qingdao Regional Contest（青岛现场赛）的部分解题报告，给出了出题率较高的几道题的题解，希望熟悉区域赛的题型，进而对其他区域赛的准备有借鉴意义。
题意
给出x和k，计算gk(x)。
解题思路
通过观察发现，g函数经过一定次数的递推一定会在0和1之间变换，所以循环内加判断提前结束递推即可。
易错分析
注意计算f(0)返回的是1的问题，下面的写法避免了这种错误。
代码实现
#include <cstdio>
using namespace std; typedef long long ll;
ll a[] = {,,,,,,,,,}; ll f(ll x) {
ll s = ;
while(x) {
s += a[x%];
x /= ;
}
return s;
}
ll g(ll x, ll k) {
ll g0 = x, g1;
for(ll i = ; i <= k; i++) {
if(g0 == ) {
if((k - i) & )
return ;
else
return ;
}
g1 = f(g0);
g0 = g1;
//printf("#%lld\n", g0);
}
return g0;
}
int main()
{
int T;
scanf("%d", &T);
ll x, k;
while(T--) {
scanf("%lld%lld", &x, &k);
printf("%lld\n", g(x, k));
}
return ;
}
题意
输入书的总本数和已经购买的书的本数以及每本书的价格
问按照他的购买策略这个人最多带了多少钱，购买策略就是从前往后只要手中的钱够买当前这本书就买，不够买就跳过。
解题思路
除去样例中给出的三个特例，分别是n == m，m == 0，k > m（其中k表示0的个数），剩下的就是一般情况，直接贪心不是正确的结果，因为有0的存在，所以需要仔细考虑，我们肯定要将价格为0的书先买走，然后从前往后买，买够m本书之后（sum），在剩下的书中选择一本最便宜的书买不起（也就是minx-1），最后总的钱数sum + minx - 1就是答案。
助解样例
5 2
0 0 2 3 0
7 4
0 0 2 3 4 2 0 0
4 2
0 0 1 1
代码
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + ;
const int inf = 1e9 + ;
ll a[maxn]; int main()
{
int T;
ll n, m;
scanf("%d", &T);
while(T--) {
scanf("%lld%lld", &n, &m);
ll k = ;
ll mi = inf;
int i;
for(i = ; i <= n; i++) {
scanf("%lld", &a[i]);
if(a[i] == )
k++;
if(mi > a[i])
mi = a[i];
} if(k > m) {
printf("Impossible\n");
continue;
}
if(n == m) {
printf("Richman\n");
continue;
}
if(m == ) {
printf("%lld\n", mi - );
continue;
} ll sum = ;
for(i = ; i <= n; i++) {
if(k == m)//易错
break;
if(a[i] != ) {
sum += a[i];
k++;
}
}
mi = inf;
for(; i <= n; i++) {
if(a[i] != )
mi = min(a[i], mi);
}
printf("%lld\n", sum + mi - );
}
return ;
}
题意
给出01串的长度和两个01串，一次操作（a1,a2, a3,a4）表示将第一个串对应位置的0或者1取反，具体操作区间是[a1,a2]和[a3,a4]。问将这两个串变为相同的操作有多少种不同的方法。
两种方法不同的规则是4个数的序列只要有一个不同即为不同。
解题思路
首先先将两个串不同的区间分成一段一段，然后*段数ds的不同我们可以分情况讨论：
1、ds > 2，不论如何区间操作，都不能使得两个串相同，故 ans = 0;
2、ds == 2，由题中样例3可知，分别操作 * 2 + 前一段带中间 + 后一段带中间 + 当成一段扣去中间 * 2，故ans = 6;
3、ds == 1，先考虑全不相同，也就是是一段不同的情况，只能是两个不相交区间的操作，所以就是2 * (段长 - 1)，再考虑有相同前缀和相同后缀的情况，有前缀可以从前缀中选一个位置带上这一段，再扣去这一段，所以需要加上前缀的长度即可，同理需要加上后缀的长度，ans = 2 * ( z - 1) + 2 * q + 2 * h = 2 * (n - 1);
4、ds == 0，易知 ans = n * (n + 1) / 2，注意可能超int范围。
代码实现
#include <cstdio> const int maxn = 1e6 + ;
char s[maxn], t[maxn];
struct Node {
int s, e;
}d[maxn];
int ds; int main()
{
int T;
int n;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
scanf("%s%s", s, t); ds = ;//记录段数，每段包含起点和终点
for(int i = ; i < n;) {
if(s[i] != t[i]) {
d[ds].s = i;
while(s[i] != t[i]) {
i++;
}
d[ds++].e = i - ;
}
else
i++;
} /*for(int i = 0; i < ds; i++) {
printf("%d %d\n", d[i].s, d[i].e);
}*/ if(ds > ) {
printf("0\n");
} else if(ds == ) {
printf("6\n");
} else if(ds == ) {
printf("%d\n", * (n - ));
} else if(ds == ) {
printf("%d\n", (long long)(n * (n + )) / );
}
}
return ;
}
题意
给出植物数n和机器人能走的步数m，给出每棵植物的生长速度，然后问这个花园的防御值最大是多少
这个花园的防御值是机器人走m步之后所有植物中防御值最小的那一个数值。
解题思路
最小值最大化问题，采用二分加验证的方法。
代码实现
#include<stdio.h>
const int N = 1e5 + ; long long n, m, a[N]; bool A(long long x)
{
long long b[N] = {};
long long i, k, z;
for(i = , k = m; i < n - ; i++)
{
if(b[i] >= x)
{
if(k > )
k--;
else
return ;
continue;
}
z = x - b[i];
if(z % a[i])
z = z / a[i] + ;
else
z = z / a[i]; if(k < z * - )
return false;
k -= z * - ;
b[i+] += (z-) * a[i+];
}
if(b[i] < x)
{
z = x - b[i];
if(z % a[i])
z = z / a[i] + ;
else
z = z / a[i];
if(k < z * - )
return false;
}
return true;
} int main()
{
long long t, i, x, r, l;
scanf("%lld", &t);
while(t--)
{
scanf("%lld%lld", &n, &m);
r = 1e17;
for(i = ; i < n; i++)
{
scanf("%lld", &a[i]);
if(r > a[i] * m)
r = a[i] * m;
}
l = ;
while(r - l > )
{
x = (r + l) / ;
if(A(x))
l = x;
else
r = x;
}
if(A(r))
printf("%lld\n", r);
else
printf("%lld\n", l);
}
return ；
}
之后的是另外一次练习的两道题
题意
给出5种比赛的票价，给出这个人看了几场比赛对应的比赛ID，问这个人看比赛花了多少钱
解题思路
水题，注意细节
代码实现
#include <stdio.h>
int f[]; int main()
{
int T, t = ;
scanf("%d", &T);
while(T--) {
int a, b, c, d, e;
scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
int i;
for(i = ; i <= ; i++)
f[i] = a;
for(i = ; i <= ; i++)
f[i] = b;
for(i = ; i <= ; i++)
f[i] = c;
for(i = ; i <= ; i++)
f[i] = d;
f[] = e; int n;
scanf("%d", &n);
long long ans = ;
int x;
for(i = ; i <= n; i++) {
scanf("%d", &x);
ans += f[x];
}
printf("Case #%d: %lld\n",t++, ans * );
}
return ;
}
题意
给出人数n和一个小组最少有多少人，问这些人能够组成多少个不同的小组
解题思路
很容易想到答案是C(n,k) + C(n,k+1) +...+ C(n,n)。由于数据量比较大，我们试着使用一种优化的算法，我们知道C(n,1) + C(n,k+1) +...+ C(n,n) = 2n ，由此可得ans = 2n - (C(n,0) + ..C(n,k -1))，前面一项我们使用整数快速幂（取模）计算，后一项使用递推公式计算它们的和（取模）。
递推形式如下：
C(n, k) = C(n, k - 1) * (n - k + 1) / k，所以迭代取模计算即可。
迭代过程中使用乘法逆元处理除法计算。提前打好每个数的逆元表。
代码如下
#include<stdio.h>
const int mod=;
long long inva[]; long long pow(long long a,long long b)
{
long long s=;
while(b)
{
if(b&)
s = s * a % mod;
a = a * a % mod;
b /= ;
}
return s;
}
long long inv(long long num)
{
return pow(num, mod-);
}
long long sum(long long n,long long k)
{
long long i,s = , cn0 = , cn1;
for(i = ; i <= k - ; i++)
{
//printf("%lld %lld\n",i, inv(i));
cn1 = (cn0%mod * (n - i + )%mod)%mod;
cn1 = (cn1%mod * inva[i] %mod)%mod;
s = (s%mod + cn1%mod)%mod;
cn0 = cn1;
}
return s;
} int main()
{
long long T,n,k,sum1,sum2,t;
for(long long i = ; i <= ; i++) {
inva[i] = inv(i);
//printf("%lld \n", inva[i]);
}
//puts(""); scanf("%lld",&T);
for(t=;t<=T;t++)
{
scanf("%lld%lld",&n,&k);
sum1=pow(,n);
sum2=sum(n,k);
//printf("%lld %lld\n", sum1, sum2);
printf("Case #%lld: %lld\n",t,(sum1 - sum2 + mod) % mod);
}
return ;
}