秦皇島2020CCPC補題
秦皇島2020CCPC A,E,F,G,I,K
A. A Greeting from Qinhuangdao
知識點：簡單題
複雜度：\(O(logn)\)
#include<bits/stdc++.h>
using namespace std;
#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
template<class T> using vc = vector<T>;
void solve()
{
ll n, m;
cin >> n >> m;
ll f = n * (n - 1);
ll g = (m + n) * (m + n - 1);
ll gc = __gcd(f, g);
f /= gc;
g /= gc;
cout << f << '/' << g << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
rep(i, 1, T)
{
cout << "Case #" << i << ": ";
solve();
}
}
E. Exam Results
知識點：貪心
複雜度：\(O(nlogn+n)\)
這題我很快就有了思路，但是只是在腦海中過了一遍，其實少考慮了一些情況，所以直接WA了一發
然後debug時看到一個變數爆 \(int\) 了，以為是這裡錯了，又WA一發，
最後還是在隊友的幫助下考慮到了錯誤的情況，屬實不應該交的那麼快
我們將所有的分數和對應的人放在一起，按分數為權值排序，然後枚舉最大值，
此時我們能得到及格線 \(p\%*max\) 用雙指針就能快速得到有多少個人及格，
需要注意的是及格線 \(p\%*max\) 要上取整，並且枚舉的最大值要合法[1]
#include<bits/stdc++.h>
using namespace std;
#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 int ll
#define pii pair<int,int>
#define pll pair<ll,ll>
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T>>;
const int N = 2e5 + 5;
pll s[N * 2];
void solve()
{
int n, p;
cin >> n >> p;
vc<int> st(n + 1), st2(n + 1);
rep(i, 1, n)
{
ll a, b; cin >> a >> b;
s[i * 2 - 1] = { a,i };
s[i * 2] = { b,i };
}
sort(s + 1, s + n + n + 1);
int cnt = 0, ans = 0, tmp = 0;
ll L = 1, fx;
rep(i, 1, n * 2)
{
fx = s[i].fi * p;
if (st2[s[i].se]++ == 0) tmp++;
if (st[s[i].se]++ == 0) cnt++;
while (s[L].fi * 100 < fx)
{
if (--st[s[L].se] == 0) cnt--;
L++;
}
if(tmp == n) ans = max(ans, cnt);
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
rep(i, 1, T)
{
cout << "Case #" << i << ": ";
solve();
}
}
F. Friendly Group
知識點：並查集
複雜度：\(O(n)\)
這題是隊友A的，但是由於我少清空了w數組WA了一發
我真該死啊.jpg
我們觀察，當一個朋友關係連接兩個連通塊時，不看該邊時，這兩個連通塊至少是兩顆樹，所以當我讓這兩個連通塊連接時，重新選擇連通塊時，不會讓這兩個連通塊的答案更少[2]，所以每一條邊都必連，然後枚舉連通塊判讀是否選取即可
#include<bits/stdc++.h>
using namespace std;
#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 pii pair<int,int>
#define pll pair<ll,ll>
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T>>;
const int N = 3e5 + 5;
int f[N], w[N], sz[N];
void init(int n)
{
rep(i, 0, n) f[i] = i, sz[i] = 1, w[i] = 0;
}
int find(int u)
{
if (u == f[u]) return u;
return f[u] = find(f[u]);
}
void unite(int u, int v)
{
int fu = find(u), fv = find(v);
if (fu == fv) w[fu]++;
else
{
w[fv] += w[fu] + 1;
sz[fv] += sz[fu];
f[fu] = fv;
}
}
void solve()
{
int n, m;
cin >> n >> m;
init(n);
rep(i, 1, m)
{
int u, v;
cin >> u >> v;
unite(u, v);
}
ll ans = 0;
rep(i, 1, n) if (find(i) == i)
{
if (w[i] > sz[i]) ans += w[i] - sz[i];
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
rep(i, 1, T)
{
cout << "Case #" << i << ": ";
solve();
}
}
G. Good Number
知識點：簡單題
複雜度：\(O(log^2n)\)
這題有點小噁心，注意判斷邊界即可
#include<bits/stdc++.h>
using namespace std;
#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 int ll
#define pii pair<int,int>
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T>>;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
ll ksm(ll x, int n)
{
ll ret = 1;
while (n)
{
if (n & 1) ret = ret * x;
n >>= 1;
x = x * x % mod;
}
return ret;
}
void solve()
{
int n, k;
cin >> n >> k;
if (k == 1) cout << n << endl;
else
{
ll x = (ll)pow(2, log2(n) / k), ans = 0;
rep(i, 1, x)
{
if (i == x) ans += (n - ksm(i, k)) / i + 1;
else ans += (ksm(i + 1, k) - ksm(i, k) - 1) / i + 1;
}
cout << ans << endl;
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
rep(i, 1, T)
{
cout << "Case #" << i << ": ";
solve();
}
}
I. Interstellar Hunter
知識點：線性代數
複雜度：\(O(Qlog(x+y))\)
只要能想到題解中的 任意時刻，能到達的點集可使用兩個基向量表示，該題就很簡單了
簡單模擬下，亂搞就過了，可以讓其中一個基向量平行與x軸或者y軸，可以減少很多情況
#include<bits/stdc++.h>
using namespace std;
#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 pii pair<int,int>
#define pll pair<ll,ll>
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T>>;
void solve()
{
int n; cin >> n;
pll a = { 0,0 }, b = { 0,0 };
ll ans(0);
rep(i, 1, n)
{
ll op, x, y, w;
cin >> op >> x >> y;
if (op == 1) // 操作1
{
while (x)
{
ll d = a.fi / x;
a.fi -= d * x; a.se -= d * y;
swap(x, a.fi); swap(y, a.se);
}
if (y) b.se = __gcd(b.se, abs(y));
if (b.se) a.se %= b.se;
}
else // 操作2
{
cin >> w;
if (a.fi)
{
ll d = x / a.fi;
x -= d * a.fi; y -= d * a.se;
}
if (b.se) y %= b.se;
if (!x && !y) ans += w;
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
rep(i, 1, T)
{
cout << "Case #" << i << ": ";
solve();
}
}
K. Kingdom’s Power
知識點：樹形dp
複雜度：\(O(nlogn)\)
頭一次被卡常，2s時限，1800ms過的，一開始使用vector開空間有個小常數T了
對於每一個點來說，我們按照子樹的最大深度進行排序，
除了去第一顆子樹的士兵一定是從根節點來的，
否則我們需要考慮去當前子樹的士兵是從根節點來的還是上一顆子樹的最大深度來的
簡單的都不像樹形dp，有點像套著樹形dp的貪心
#include<bits/stdc++.h>
using namespace std;
#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 pii pair<int,int>
#define pll pair<ll,ll>
#define int ll
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T>>;
const int N = 1e6 + 5;
vc<int> h[N];
int len[N], d[N];
void dfs(int u)
{
for (auto v : h[u])
{
d[v] = d[u] + 1;
dfs(v);
len[u] = max(len[u], len[v] + 1);
}
}
bool cmp(int a, int b) { return len[a] < len[b]; }
ll ans = 0;
void dfs2(int u)
{
sort(h[u].begin(), h[u].end(), cmp);
int lim = h[u].size();
if (lim) dfs2(h[u][0]);
rep(i, 1, lim - 1)
{
ans += min(d[u], len[h[u][i - 1]] + 1);
dfs2(h[u][i]);
}
}
void solve()
{
int n; cin >> n;
rep(i, 1, n)
{
h[i].clear();
len[i] = d[i] = 0;
}
ans = n - 1;
rep(i, 2, n)
{
int f; cin >> f;
h[f].push_back(i);
}
dfs(1);
dfs2(1);
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
rep(i, 1, T)
{
cout << "Case #" << i << ": ";
solve();
}
}
