牛客练习赛25
程序员文章站
2022-04-02 18:22:56
...
因数个数和
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
q次询问，每次给一个x，问1到x的因数个数的和。
输入描述:
第一行一个正整数q ；
接下来q行，每行一个正整数 x
输出描述:
共q行，每行一个正整数表示答案
示例1
输入
复制
4
1
2
3
10
输出
复制
1
3
5
27
说明
1的因数有1
2的因数有1,2
3的因数有1,3
以此类推
备注:
1<=q<=10 ,1<= x<=109
整出分块，求因数的个数和就是求每个数有几个倍数在范围内，转化成求倍数个数和，i倍数的个数就是n//i，那整除分块的最后一个值就是n//（n//i），那么一个分块的值就是(r-l+1)*(n//i)。
#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 400010
#define M 3645
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1);
#define fi first
#define se second
#define L o<<1
#define R o<<1|1
#define tl tree[o].l
#define tr tree[o].r
#define tw tree[o].w
#define to tree[o].ok
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
ll n, ans = 0;
int q;
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
cin >> q;
while(q--) {
scanf("%lld", &n);
ans = 0;
for (ll i = 1, j; i <= n; i = j + 1){
j = n / (n / i);
ans += (n / i) * (j - i + 1);
}
printf("%lld\n", ans);
}
return 0;
}
最长区间
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给你一个长度为 n 的序列 a ，求最长的连续的严格上升区间的长度。
同时会进行 m 次修改，给定 x , y ，表示将 ax 修改为 y ,每次修改之后都要求输出答案。
输入描述:
第一行 2 个数 n,m，表示序列长度，修改次数；
接下来一行 n 个数表示 ；
接下来 m 行，每行 2 个数 x , y ，描述一次修改。
输出描述:
第一行 1 个数表示最初的答案；
接下来 m 行，第 i 行 1 个数表示第 i 次修改后的答案。
示例1
输入
复制
4 3
1 2 3 4
3 1
2 5
3 7
输出
复制
4
2
2
3
说明
序列变换如下：
1 2 3 4
1 2 1 4
1 5 1 4
1 5 7 4
备注:
n,m ≤ 100000,1 ≤ x ≤ n，1 ≤ ai,y ≤ 100
以为是最长上升子序列吓得没敢写当时Orz读错题狗。解法是维护每种长度的cnt数组(天晓得为什么只有最长100)。
#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 100010
#define M 3645
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1);
#define fi first
#define se second
#define L o<<1
#define R o<<1|1
#define tl tree[o].l
#define tr tree[o].r
#define tw tree[o].w
#define to tree[o].ok
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
int n, m, x, y, ans;
int a[N], cnt[N], tmp;
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
while(~scanf("%d%d", &n, &m)) {
rep(i, 1, n) scanf("%d", &a[i]);
a[1] = 0; a[n + 1] = 101;
memset(cnt, 0, sizeof cnt);
tmp = 1;
ans = -1;
rep(i, 2, n)
if(a[i] > a[i - 1]) tmp++;//cout <<"tmp " << tmp <<' ' << i <<endl;
else {
cnt[tmp]++;
ans = max(ans, tmp);
tmp = 1;
}
cnt[tmp]++;
ans = max(ans, tmp);
printf("%d\n", ans);
while(m--) {
scanf("%d%d", &x, &y);
int l = 1, r = 1;
if(x == 1) l = 0;
if(x == n) r = 0;
for(int i = x - 1; i - 1 >= 1 && a[i] > a[i - 1]; i--, l++);
for(int i = x + 1; i + 1 <= n && a[i + 1] > a[i]; i++, r++);
if(a[x] > a[x - 1] && a[x + 1] > a[x]) cnt[l + r + 1]--;
else if(a[x] > a[x - 1]) cnt[l + 1]--, cnt[r]--;
else if(a[x + 1] > a[x]) cnt[r + 1]--, cnt[l]--;
else cnt[1]--, cnt[l]--, cnt[r]--;
a[x] = y;
if(a[x] > a[x - 1] && a[x + 1] > a[x]) cnt[l + r + 1]++;
else if(a[x] > a[x - 1]) cnt[l + 1]++, cnt[r]++;
else if(a[x + 1] > a[x]) cnt[r + 1]++, cnt[l]++;
else cnt[1]++, cnt[l]++, cnt[r]++;
for(int i = 100; i >= 1; i--)
if(cnt[i]) {
printf("%d\n", i);
break;
}
}
}
return 0;
}
还有线段树的写法，这个正常多了。。。
#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 100010
#define M 3645
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1);
#define fi first
#define se second
#define L o<<1
#define R o<<1|1
#define tl tree[o].l
#define tr tree[o].r
#define tlw tree[o].lw
#define trw tree[o].rw
#define tmw tree[o].mw
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
struct Node {
int l, r, lw, rw, mw;
}tree[N * 4];
int n, m, a[N];
void up(int o)
{
tlw = tree[L].lw;
trw = tree[R].rw;
tmw = max(tree[L].mw, tree[R].mw);
if(a[tree[L].r] < a[tree[R].l]) {
if(tree[L].r - tree[L].l + 1 == tree[L].lw) {
tlw += tree[R].lw;
tmw = max(tlw, tmw);
}
if(tree[R].r - tree[R].l + 1 == tree[R].rw) {
trw += tree[L].rw;
tmw = max(tmw, trw);
}
tmw = max(tmw, tree[L].rw + tree[R].lw);
}
}
void build(int o, int l, int r)
{
tl = l; tr = r;
if(l == r) {
tlw = trw = tmw = 1;
return;
}
int mid = (l + r) >> 1;
build(L, l, mid);
build(R, 1 + mid, r);
up(o);
}
void change(int o, int x)
{
if(tl == tr) return;
int mid = (tl + tr) >> 1;
if(x <= mid) change(L, x);
else if(x > mid) change(R, x);
up(o);
}
int query(int o, int l, int r)
{
if(tl == l && tr == r) return tmw;
int mid = (tl + tr) >> 1;
if(r <= mid) return query(L, l, r);
else if(l > mid) return query(R, l, r);
int lw = query(L, l, mid);
int rw = query(R, 1 + mid, r);
if(a[mid] < a[mid + 1]) {
int llw = min(tree[L].rw, mid - tl + 1);
int rrw = min(tree[R].lw, tr - mid);
return max(llw + rrw, max(lw, rw));
}
return max(lw, rw);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
while(~scanf("%d%d", &n, &m)) {
rep(i, 1, n) scanf("%d", &a[i]);
build(1, 1, n);
printf("%d\n", query(1, 1, n));
while(m--) {
int x, y;
scanf("%d%d", &x, &y);
a[x] = y;
change(1, x);
printf("%d\n", query(1, 1, n));
}
}
return 0;
}
再编号
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
n 个人，每个人有一个编号 ai 。
定义对 a 的再编号为 a' ，满足 。
现在有 m 次询问，每次给定 x,t ，表示询问经过 t 次再编号后第 x 个人的编号。
由于答案可能很大，所以对 109+7 取模。
输入描述:
第一行 2 个数 n,m ，表示人数和询问次数； 接下来一行 n 个数，表示 ai ； 接下来 m 行，每行 2 个数 x,t ，描述一次询问。
输出描述:
m 行，第 i 行 1 个数表示第 i 次询问的答案对 109+7 取模的结果。
示例1
输入
4 3 1 2 3 4 1 0 2 2 4 1
输出
1 22 6
说明
初始编号：1 2 3 4 1 次再编号后：9 8 7 6 2 次再编号后：21 22 23 24
备注:
n ≤ 100000 , m ≤ 10000 , t ≤ 100000 , 1 ≤ ai ≤ 109
推公式推公式
#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
typedef long long LL;
#define N 100010
#define M 3645
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1);
const int mod = 1e9 + 7;
#define fi first
#define se second
#define L o<<1
#define R o<<1|1
#define tl tree[o].l
#define tr tree[o].r
#define tw tree[o].w
#define to tree[o].ok
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
int n, m, x, t, a[N];
ll sum0;
ll power(ll a, ll b)
{
ll ans = 1;
while(b) {
if(b & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
scanf("%d%d", &n, &m);
sum0 = 0;
rep(i, 1, n) {
scanf("%d", &a[i]);
sum0 = (sum0 + a[i]) % mod;;
}
while(m--) {
scanf("%d%d", &x, &t);
if(t == 0) {
printf("%d\n", a[x]);
continue;
}
ll tmp = power(n - 1, t);
if(t & 1) {
ll ans = ((1 + tmp) * sum0) % mod;
ans = (ans * power(n, mod - 2)) % mod;
ans = ((ans - a[x]) % mod + mod) % mod;
printf("%lld\n", ans);
}
else {
ll ans = (-sum0 * (1 - tmp)) % mod;
ans = (ans * power(n, mod - 2)) % mod;
ans = (ans + a[x]) % mod;
printf("%lld\n", ans);
}
}
return 0;
}a-贝利福斯数
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
将所有形如ax+1的数称为a-贝利福斯数，其中x是正整数。
一个a-贝利福斯数是a-贝利福斯素数，当且仅当它不能被分解成两个a-贝利福斯数的积。
现在给出a,n，问有多少个 ≤ n的a-贝利福斯数可以被分解成两个a-贝利福斯素数的积。
输入描述:
一行两个数a,n
输出描述:
一行一个数表示答案
示例1
输入
复制
4 25
输出
复制
1
说明
≤ 25 的 4-贝利福斯数有5,9,13,17,21,25。
其中4-贝利福斯素数有5,9,13,17,21，
可以被分解成两个a-贝利福斯素数的积只有25。
备注:
1 ≤ a ≤ 10,1 ≤ n ≤ 2 x 107 x a
线性筛的考察，其实就是从自然数里抽出一个子群跑线性筛，不是很懂素数有多少个是怎么估计的。
#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <bitset>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 20000001
#define M 3645
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1);
#define fi first
#define se second
#define L o<<1
#define R o<<1|1
#define tl tree[o].l
#define tr tree[o].r
#define tw tree[o].w
#define to tree[o].ok
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
int a, n;
int q[N], l;
int prime[13000000], cnt;
bitset<N * 10> vis;
ll ans;
void init(int m)
{
rep(i, 1, m) {
if(!vis[q[i]]) prime[++cnt] = q[i];
for(int j = 1; j <= cnt && 1ll * prime[j] * q[i] <= n; j++) {
vis[q[i] * prime[j]] = true;
if(q[i] % prime[j] == 0) break;
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
scanf("%d%d", &a, &n);
for(int i = 1 + a; i <= n; i += a) q[++l] = i;
init(l);
ans = 0;
rep(i, 1, cnt) rep(j, 1, cnt) {
if(1ll * prime[i] * prime[j] > n) break;
if(vis[prime[i] * prime[j]]) {
vis[prime[i] * prime[j]] = false;
ans++;
}
}
printf("%lld\n", ans);
return 0;
}
定向
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld
题目描述
给一张无向图，你需要将边定向，使得定向后的有向图强连通。
输入描述:
第一行两个数n,m，表示点数和边数。 接下来m行，每个两个数x,y，表示x和y之间有条边。
输出描述:
如果不存在可行方案输出一行"impossible" ； 否则，输出一个长度为m的01串，描述你的方案， 第i个字符为1表示输入的第i条边定向为从x到y，为0表示从y到x。
示例1
输入
3 3 1 2 1 3 2 3
输出
101
说明
1->2->3->1，形成一个环 ，是强连通的。
备注:
1 ≤ n,m ≤ 106 ，保证无重边自环
emmmmTarjan跑出来的图一定是强连通的（如果没有桥的话），所以跑Tarjan的时候记录一下有没有桥，然后记录下无向图中跑的哪条边就行。
#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
typedef long long LL;
#define N 1000010
#define M 2000010
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1);
const int mod = 1e9 + 7;
#define fi first
#define se second
#define L o<<1
#define R o<<1|1
#define tl tree[o].l
#define tr tree[o].r
#define tw tree[o].w
#define to tree[o].ok
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
int Head[N], Next[M], E[M];
int dfn[N], low[N];
bool ans[M];
int n, m, dfn_cnt, ecnt;
bool flag;
void addedge(int u, int v)
{
Next[ecnt] = Head[u];
E[ecnt] = v;
Head[u] = ecnt++;
Next[ecnt] = Head[v];
E[ecnt] = u;
Head[v] = ecnt++;
}
void Tarjan(int u, int fa)
{
dfn[u] = low[u] = ++dfn_cnt;
for(int i = Head[u]; ~i; i = Next[i]) {
if(!(i ^ fa ^ 1)) continue;
int v = E[i];
if(!dfn[v]) {
ans[i] = true;
Tarjan(v, i);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u]) flag = false;
}
else {
low[u] = min(low[u], dfn[v]);
if(dfn[v] < dfn[u]) ans[i] = true;
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
flag = true;
scanf("%d%d", &n, &m);
memset(Head, -1, sizeof Head);
rep(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
addedge(u, v);
}
Tarjan(1, -1);
if(!flag) puts("impossible");
else rep(i, 0, m - 1) putchar('0' + ans[i << 1]);
return 0;
}
青蛙
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
一条河流上有 m+2 块石头，其中最左的石头坐标为 1 ，最右的为 n 。
现在在起点 1 有无数只青蛙，每个青蛙一步可以跳 ≤ d 的任意长度，每个石头(除了起点，终点)只能被跳一次，问最多有多少只青蛙可以跳到终点 n 。
有多组数据。
输入描述:
第一行 1 个数 t 表示数据组数。
接下来 t 组数据。
每组数据的第一行 3 个数表示 n,m,d ，第二行 m+2 个数表示石头坐标，保证递增。
输出描述:
t 行，第 i 行一个数表示第 i 组数据的答案。
示例1
输入
复制
1
10 3 3
1 4 6 8 10
输出
复制
1
说明
对于一只青蛙，1 4 6 8 10依次跳即可。
对于两只及以上的青蛙，可以证明是不可能的。
备注:
t ≤ 10 ，1 ≤ m ≤ 300000 ， 3 ≤ n,d ≤ 109 ，m+2 块石头坐标互不相同，保证答案有限。
题解说
第一，考虑每块石头，这块石头一定可以被用（不用可以跳短点用上）。
第二，考虑每块石头，每块石头都能成为某个阶段的最左边一个石头（当一个石头在中间的时候能让它后面的青蛙往前跳）。
所以就是一段一段的，看最短的一段就行了。
#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
#define N 400010
#define M 300645
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1);
#define fi first
#define se second
#define L o<<1
#define R o<<1|1
#define tl tree[o].l
#define tr tree[o].r
#define tw tree[o].w
#define to tree[o].ok
#define rep(i, lll, nnn) for(int i = (lll); i <= (nnn); i++)
int t;
int n, m, d;
int a[M];
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
#endif
scanf("%d", &t);
while(t--) {
scanf("%d%d%d", &n, &m, &d);
m++; m++;
rep(i, 1, m) scanf("%d", &a[i]);
int tmp = 1, ans = n;
rep(i, 1, m) {
while(tmp <= m && a[tmp] - a[i] <= d) tmp++;
ans = min(ans, tmp - i - 1);
if(tmp == m + 1) break;
}
printf("%d\n", ans);
}
return 0;
}
下一篇： 2018华为校招笔试题