字节跳动杯_2018中国大学生程序设计竞赛-女生专场

1002. 口算训练

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6287

Problem Description
小Q非常喜欢数学，但是他的口算能力非常弱。因此他找到了小T，给了小T一个长度为n的正整数序列a1,a2,…,an，要求小T抛出m个问题以训练他的口算能力。
每个问题给出三个正整数l,r,d，小Q需要通过口算快速判断al×al+1×…×ar−1×ar是不是d的倍数。
小Q迅速地回答了出来，但是小T并不知道正确答案是什么，请写一个程序帮助小T计算这些问题的正确答案。

Input
第一行包含一个正整数T(1≤T≤10)，表示测试数据的组数。
每组数据第一行包含两个正整数n,m(1≤n,m≤100000)，分别表示序列长度以及问题个数。
第二行包含n个正整数a1,a2,…,an(1≤ai≤100000)，表示序列中的每个数。
接下来m行，每行三个正整数l,r,d(1≤l≤r≤n,1≤d≤100000)，表示每个问题。

Output
对于每个问题输出一行，若是倍数，输出Yes，否则输出No。

Solution

将输入的每个数分解质因数并记录，对d分解质因数并判断每个质因数在数组中是否有足够的因数。

[l, r] 中每个数相乘的结果是d的倍数，只需要 [l, r] 之间每个数的因数选择一些乘起来是 d 或 d 的倍数即可。但是暴力的储存查找会超时，所以可以通过用 vector 存因子 x 出现的所有坐标 i，然后再利用二分查找当前范围内由多少个因数。

注意，分解的时候要注意当前数是素数的情况。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdlib>
#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MaxN = 1e5 + 5;
 
vector<int> G[MaxN];
 
int query(int l, int r, int x) 
{
    return upper_bound(G[x].begin(), G[x].end(), r) - lower_bound(G[x].begin(), G[x].end(), l);
}
 
bool check(int l, int r, int d) 
{
    for(int i = 2; i * i <= d; i++) {
        if(d % i == 0) { //对d分解质因数
            int cnt = 0;
            while(d % i == 0) {
                cnt++;
                d /= i;
            }
            if(query(l, r, i) < cnt) return 0;
        }
    }
    if(d > 1 && query(l, r, d) < 1) return 0; //如果当前数是素数
    return 1;
}
 
int main () 
{
    int t; scanf("%d", &t);
    while(t--) {
        for(int i = 1; i <= MaxN; i++) G[i].clear();
        int n, m;
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i++) {
            int x; scanf("%d", &x);
            for(int j = 2; j * j <= x; j++) { //对数组中的数分解质因数
                while(x % j == 0) {
                    x /= j;
                    G[j].push_back(i); //对于每次当前的质因数都存储坐标i
                }
            }
            if(x > 1) G[x].push_back(i); //当前数是素数
        }
        while(m--) {
            int l, r, d;
            scanf("%d %d %d", &l, &r, &d);
            if(check(l, r, d)) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

1003. 缺失的数据范围

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6288

Problem Description
著名出题人小Q出过非常多的题目，在这个漫长的过程中他发现，确定题目的数据范围是非常痛苦的一件事。
每当思考完一道题目的时间效率，小Q就需要结合时限以及评测机配置来设置合理的数据范围。
因为确定数据范围是一件痛苦的事，小Q出了非常多的题目之后，都没有它们设置数据范围。对于一道题目，小Q会告诉你他的算法的时间复杂度为O(nalogbn)，且蕴含在这个大O记号下的常数为1。同时，小Q还会告诉你评测机在规定时限内可以执行k条指令。小Q认为只要na(⌈log2n⌉)b不超过k，那么就是合理的数据范围。其中，⌈x⌉表示最小的不小于x的正整数，即x上取整。
自然，小Q希望题目的数据范围n越大越好，他希望你写一个程序帮助他设置最大的数据范围。

Input
第一行包含一个正整数T(1≤T≤1000)，表示测试数据的组数。
每组数据包含一行三个正整数a,b,k(1≤a,b≤10,106≤k≤1018)，分别描述时间复杂度以及允许的指令数。

Output
对于每组数据，输出一行一个正整数n，即最大可能的n。

Description

给出a、b、k，对于公式找出最大的n。

Range

1 ≤ a, b ≤ 10
1e6 ≤ k ≤ 1e18

Solution

二分查找可行解。
把公式分为 $n^{a}$ 和 $(\left \lceil log_{2}^{n} \right \rceil)^{_{b}}$ 两部分分别进行判断。

需要注意的两点是：

乘法可能溢出，需要将乘法转换为除法
求 ⌈log2 n⌉ 时不能使用实数计算，会带来误差，应当使用整数计算。

Code

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define fi first
#define se second
#define mst(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;
const int Mod = 1e9 + 7;
const int MaxN = 1e5 + 5;
 
int a, b;
LL k;
 
LL log2(LL mid)
{
	for(int i = 0; i <= 64; i++) {
		if(pow(2LL, i) >= mid) return i;
	}
}
 
bool check(LL mid) 
{
	LL pre = 1LL;
	for(int i = 1; i <= a; i++) { //判断前面部分
		if(pre <= k / mid) pre *= mid;  //防止乘法溢出
		else return false;  //当前的结果大于k说明不合法
	}
	LL base = log2(mid);
	LL suf = 1LL;
	if(suf == 0) return true;  //否则会在下面的除法中出现RE
	for(int i = 1; i <= b; i++) {  //判断后面部分
		if(suf <= k / mid) suf *= base;
		else return false;
	}
	if(pre <= k / suf) return true;  //将两部分合起来判断一次
	return false;
}
 
int main()
{
    //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    int t; scanf("%d", &t);
    while(t--) {
    	scanf("%d %d %lld", &a, &b, &k);
    	LL l = 0LL, r = 1e18, ans = 0LL;
    	while(l <= r) {
			LL mid = (l + r) / 2;
			if(check(mid)) l = mid + 1, ans = mid;
			else r = mid - 1;
		}
		cout << ans << endl;
	}
    
    return 0;
}

1004. 寻宝游戏

题目传送门

Problem Description
小Q最近迷上了一款寻宝游戏，这款游戏中每局都会生成一个n×m的网格地图，从上往下依次编号为第1行到第n行，从左往右依次编号为第1列到第m列。每个格子上都有不同数量的金币，第i行第j列的格子上的金币数量为ai,j。
小Q一开始位于(1,1)，每次他可以往右或者往下走，每当他经过某个格子时，他就可以拿走这个格子上的所有金币。小Q不能走出这个地图，当小Q不能再行动时，游戏结束。显然当且仅当小Q位于(n,m)时，游戏才会结束。
一轮游戏的得分为这一轮中收集到的金币总量，而在游戏开始前，因为小Q是超级VIP用户，所以他有k次机会交换某两个格子中的金币数。这k次机会不一定要用完，请写一个程序帮助小Q在一轮内拿到尽可能多的金币。

Input

第一行包含一个正整数T(1≤T≤10)，表示测试数据的组数。
每组数据第一行包含三个整数n,m,k(2≤n,m≤50,0≤k≤20)，分别表示地图的长宽以及交换的次数。
接下来n行，每行m个整数ai,j(0≤ai,j≤106)，依次表示每个格子中金币的数量。

Output

对于每组数据，输出一行一个整数，即能收集到的金币数量的最大可能值。

Description

对于 n*m 的矩阵每个点都有一个权值。从 (1, 1) 开始每次只能向下或向右走，求到达 (n, m) 时可以获得的最大值，其中你有k次交换机会交换任意两点上的权值。

Solution

假设已经选定了一条路线，那么不考虑具体交换方案，考虑选定一个 t(t ≤ k)，经过的格子里要有 t 个格子的权值不计入得分，而不经过的格子里要有 t 个格子的权值计入总分。那么每一种交换方案都可以对应这样一个转化。
设 $f_{i,j,x,y}$ 表示从 (1, 1) 出发来到 (i, j)，考虑完前 i − 1 行所有格子以及第 i 行前 j 个格子时，有 x 个经过的格子不计分，y 个不经过的格子计分的情况下，总分的最大值是多少。那么有两种状态转移：

往右走一格，直接转移到 $f_{i,j+1,{x}’,{y}’}$;
往下走一格，转移到$f_{i+1,j,{x}’,{y}’}$，需要枚举这一行有多少个不经过的格子计分。显然这些格子一定按照权值从大到小贪心选择。

最终答案即为$max(f_{n,m,t,t})$ (0 ≤ t ≤ k)

时间复杂度$O(n^{2}k^{2})$。