Codeforces Round #837 (Div. 2)
A. Hossam and Combinatorics
知识点:简单题
复杂度:\(O(nlogn)\)
很明显能看出,该题与数据的位置无关,只与大小有关
所以我们可直接排序,判断最大与最小元素个数即可
注意特判所有元素均相等情况
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define pll pair<ll,ll>
#define pii pair<int,int>
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T> >;
const int N = 1e5 + 5;
ll n, m, k;
int a[N];
void solve()
{
cin >> n;
rep(i, 1, n) cin >> a[i];
sort(a + 1, a + n + 1);
if (a[1] == a[n]) cout << n * (n - 1) << endl;
else
{
ll x(0), y(0);
rep(i, 1, n) if (a[i] == a[1]) x++;
rep(i, 1, n) if (a[i] == a[n]) y++;
cout << x * y * 2 << endl;
}
}
B. Hossam and Friends
知识点:计数,思维题
复杂度:\(O(nlogn)\)
很明显能观察出当一段区间内有一对互不相认的人时,该区间不合法
所以我们可以枚举区间左端点,找到每一对中不相认的较大编号的人的最小值,即可得到合法个数
显然当一对不相认的人的较小编号在我们枚举的区间左端点左边时,该较大编号对我们没影响,可以删去
分别用vector和multiset实现即可
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define pll pair<ll,ll>
#define pii pair<int,int>
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T> >;
const int N = 1e5 + 5;
int n, m, k;
vc<int> h[N];
void solve()
{
cin >> n >> m;
rep(i, 1, n) h[i].clear();
multiset<int> s;
s.insert(n + 1);
rep(i, 1, m)
{
int x, y; cin >> x >> y;
if (x > y) swap(x, y);
h[x].pb(y);
s.insert(y);
}
ll ans(0);
rep(i, 1, n)
{
ans += *s.begin() - i;
for (auto x : h[i]) s.erase(s.find(x));
}
cout << ans << endl;
}
C. Hossam and Trainees
知识点:质因数分解,线性筛
复杂度:\(O(n^2logn)\)
fst了,1e3*1e3==1e9,我可真是大聪明
显然我们可以用一个set存储所有数的质因数,如果有两个数有相同的质因数时,输出YES
如果直接暴力筛质因数,复杂度为\(O(1e5*\sqrt{1e9}*log(1e5*10))\),复杂度爆炸
(1e9大小的数最多有10个不同的质因子)
但是如果我们先筛出\(\sqrt{1e9}\)内的质数,
那么负责度就降为\(O(1e5*\frac{\sqrt{1e9}}{ln\sqrt{1e9}}*log(1e6)+\sqrt{1e9})\),大约为\(O(1e6*log(1e6))\)
#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define pll pair<ll,ll>
#define pii pair<int,int>
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T> >;
const int N = 1e5 + 5;
int n, m, k;
int a[N];
const int M = 4e4 + 5;
bool prime[M];
int p[M], pn = 0;
void get_prime(int n)
{
fill(prime + 2, prime + n + 1, true);
for (int i = 2; i <= n; i++)
{
if (prime[i]) p[++pn] = i;
for (int j = 1; p[j] * i <= n; j++)
{
prime[i * p[j]] = false;
if (i % p[j] == 0) break;
}
}
}
void solve()
{
cin >> n;
rep(i, 1, n) cin >> a[i];
set<int> s;
rep(i, 1, n)
{
for (int j = 1; j <= pn && p[j] <= a[i] / p[j]; j++)
{
if (a[i] % p[j] == 0)
{
if (s.count(p[j]))
{
YES;
return;
}
s.insert(p[j]);
while (a[i] % p[j] == 0) a[i] /= p[j];
}
}
if (a[i] > 1)
{
if (s.count(a[i]))
{
YES;
return;
}
s.insert(a[i]);
}
}
NO;
}
void init()
{
cin >> T_T;
get_prime(40000);
}
D. Hossam and (sub-)palindromic tree
知识点:不知道
复杂度:\(O(不知道)\)
没做出来,有时间就补
标签:vc,837,int,rep,补题,1e9,using,Div,define From: https://www.cnblogs.com/lunasama/p/16975809.html