题解：CF39F Pacifist frogs

ljk8886 · 2025-01-12 09:41:16 · 题解

题目分析

这道题肯定可以用桶做，但 1 \le n \le 10^9，存不下，得再换一种方法。

观察题目，可以发现每只青蛙的跳跃的长度是固定的。所以，我们只需要判断每只蚊子所在的位置是不是青蛙的跳跃的长度，如果是，就加到这只青蛙吃蚊子的数量中。最后再算一下最小值和最小值的个数。时间复杂度 O(mk)。

代码

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
inline ll read()
{
    ll res = 0, f = 1;
    char ch = gc();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
    while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
    return res * f;
}
inline void write(ll x)
{
    if (x < 0) x = -x, pc('-');
    if (x > 9) write(x / 10);
    pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 1e2 + 5;
int n = read(), m = read(), k = read();
int d[N], p[N], ans[N], minn = INT_MAX, cnt;
int main()
{
    for (int i = 1; i <= m; i++) d[i] = read();
    for (int i = 1; i <= k; i++) p[i] = read();
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= k; j++)
            if (p[j] % d[i] == 0) ans[i]++; //是否是跳跃长度的倍数 
        if (ans[i] == minn) cnt++; // 统计最小值的个数 
        else if (ans[i] < minn) minn = ans[i], cnt = 1; // 更新最小值 
    }
    writech(cnt, '\n');
    for (int i = 1; i <= m; i++)
        if (ans[i] == minn) writech(i, ' ');
    return 0;
}