A - Problem A.Alkane
留坑。
B - Problem B. Beads
留坑。
C - Problem C. Calculate
留坑。
D - Problem D. Permutation
留坑。
E - Problem E. TeaTree
题意：每个点会存下任意两个以他为LCA的点对的GCD，求每个点存的GCD的最大值
思路：DSU on tree 用 set 维护子树中的因子，对于重儿子不要处理多次 每次查找的时候，枚举轻儿子中的因子
还有一种线段树合并的写法
#include <bits/stdc++.h>
using namespace std; #define N 100010 int n;
vector <int> G[N], num[N];
set <int> s;
int sz[N], son[N], cnt[N], cnt2[N], arr[N], ans[N], Max;
bool isbig[N]; void Init()
{
for (int i = ; i <= ; ++i)
{
int limit = sqrt(i);
for (int j = ; j < limit; ++j) if (i % j == )
{
num[i].push_back(j);
num[i].push_back(i / j);
}
if (i % limit == )
{
num[i].push_back(limit);
if (limit * limit != i) num[i].push_back(i / limit);
}
}
} void DFS(int u)
{
sz[u] = ;
for (auto v : G[u])
{
DFS(v); sz[u] += sz[v];
if (son[u] == - || sz[v] > sz[son[u]]) son[u] = v;
}
} void update(int u)
{
for (auto it : num[arr[u]]) ++cnt[it];
for (auto v : G[u]) if (!isbig[v]) update(v);
} void work(int u, int fa)
{
for (auto it : num[arr[u]]) s.insert(it);
for (auto v : G[u]) if (!isbig[v]) work(v, fa);
} void query(int u)
{
for (auto v : G[u]) if (!isbig[v])
{
s.clear();
work(v, u);
for (auto it : s) if (cnt[it] >= || cnt2[it] >= ) Max = max(Max, it);
for (auto it : s) ++cnt2[it];
}
for (auto it : num[arr[u]]) if (cnt[it] >= || cnt2[it] >= ) Max = max(Max, it);
} void clear(int u)
{
for (auto it : num[arr[u]]) cnt[it] = cnt2[it] = ;
for (auto v : G[u]) clear(v);
} void DSU(int u)
{
for (auto v : G[u]) if (v != son[u]) DSU(v);
if (son[u] != -) { isbig[son[u]] = ; DSU(son[u]); }
Max = -; query(u);
ans[u] = Max;
if (isbig[u]) update(u);
if (son[u] != -) isbig[son[u]] = ;
if (!isbig[u]) clear(u);
} int main()
{
Init();
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) G[i].clear();
memset(son, -, sizeof son);
memset(cnt, , sizeof cnt);
memset(cnt2, , sizeof cnt2);
Max = -; s.clear();
for (int i = , u; i <= n; ++i)
{
scanf("%d", &u);
G[u].push_back(i);
}
for (int i = ; i <= n; ++i) scanf("%d", arr + i);
DFS(); DSU();
for (int i = ; i <= n; ++i) printf("%d\n", ans[i]);
}
return ;
}
#include <bits/stdc++.h>
using namespace std; #define N 100010
vector <int> num[N], G[N]; int n;
int arr[N], rt[N], ans[N]; void Init()
{
for (int i = ; i <= ; ++i) for (int j = i; j <= ; j += i)
num[j].push_back(i);
} struct SEG
{
#define M N * 400
int lson[M], rson[M], c[M], cnt;
void init() { cnt = ; }
void pushup(int id) { c[id] = max(c[lson[id]], c[rson[id]]); }
void update(int &x, int l, int r, int pos)
{
if (!x) x = ++cnt;
if (l == r) { c[x] = pos; return; }
int mid = (l + r) >> ;
pos <= mid ? update(lson[x], l, mid, pos) : update(rson[x], mid + , r, pos);
pushup(x);
}
int merge(int u, int v, int &sum)
{
if (!u || !v) return u | v;
if (c[u] == c[v]) sum = max(sum, c[u]);
if (lson[u] | lson[v]) lson[u] = merge(lson[u], lson[v], sum);
if (rson[u] | rson[v]) rson[u] = merge(rson[u], rson[v], sum);
return u;
}
}seg; void DFS(int u)
{
ans[u] = -;
for (auto v : G[u])
{
DFS(v);
seg.merge(rt[u], rt[v], ans[u]);
}
} void Run()
{
Init();
while (scanf("%d", &n) != EOF)
{
seg.init();
for (int i = , u; i <= n; ++i)
{
scanf("%d", &u);
G[u].push_back(i);
}
for (int i = ; i <= n; ++i) scanf("%d", arr + i);
for (int i = ; i <= n; ++i) for (auto it : num[arr[i]]) seg.update(rt[i], , , it);
DFS();
for (int i = ; i <= n; ++i) printf("%d\n", ans[i]);
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ; }
F - Problem F. NewNippori
留坑。
G - Problem G. Cyclic
打表找规律即可
$F[n] = (n - 2) * F[n - 1] + (n - 1) * F[n - 2] + (i \& 1 ? 1 : -1)$
#include <bits/stdc++.h>
using namespace std; #define N 100010
#define ll long long const ll MOD = ; ll arr[N]; int main()
{
arr[] = , arr[] = ;
for (int i = ; i <= ; ++i) arr[i] = ((i - ) * arr[i - ] % MOD + (i - ) * arr[i - ] % MOD + ((i & ) ? : -) + MOD) % MOD;
int t; scanf("%d", &t);
while (t--)
{
int n;
scanf("%d", &n);
printf("%lld\n", arr[n]);
}
}
H - Problem H. Pow
水。
import java.util.Scanner;
import java.math.*; public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
while (t-- != 0)
{
int n = in.nextInt();
System.out.println(BigInteger.valueOf(2).pow(n));
}
}
}
I - Problem I. Count
题意：求$\sum_{i = 1} ^ {i = n} \sum_{j = 1} ^ {j = i - 1} [gcd(i + j, i - j) == 1]$
思路：找规律。如果是奇数就加上$\frac {\varphi(n)}{2} 否则加上 \varphi(n)$
#include <bits/stdc++.h> using namespace std; typedef long long ll;
const int MAXN = ;
bool check[MAXN + ]; ll ans[MAXN + ];
int phi[MAXN + ];
int prime[MAXN + ];
int tot; void phi_ans_prime_table() {
memset(check, false, sizeof check);
phi[] = ;
tot = ;
for(int i = ; i <= MAXN; ++i)
{
if(!check[i])
{
prime[tot++] = i;
phi[i] = i - ;
}
for(int j = ; j < tot; ++j)
{
if(i * prime[j] > MAXN) break;
check[i * prime[j]] = true;
if(i % prime[j] == )
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
{
phi[i * prime[j]] = phi[i] * (prime[j] - );
}
}
if(i & ) ans[i] = ans[i - ] + phi[i] / ;
else ans[i] = ans[i - ] + phi[i];
}
} int main() {
phi_ans_prime_table();
int t;
scanf("%d", &t);
while(t--)
{
int n;
scanf("%d", &n);
printf("%lld\n", ans[n]);
}
return ;
}
J - Problem J. CSGO
题意：有n把主武器和m把副武器，每把武器有k种属性，选取一把主武器和副武器，求题中式子最大值
思路：对于没种属性又有加减两种状态，枚举每把武器的每种属性的加减状态，求最大值
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5 + ; ll arr[maxn][], brr[maxn][];
ll crr[maxn]; int n, m, k; void RUN()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d %d %d", &n, &m, &k);
for (int i = ; i <= n; ++i) for (int j = ; j <= k; ++j) scanf("%lld", &arr[i][j]);
for (int i = ; i <= m; ++i) for (int j = ; j <= k; ++j) scanf("%lld", &brr[i][j]);
memset(crr, , sizeof crr);
ll ans = ;
int limit = ( << k);
for (int i = ; i <= n; ++i)
{
for (int S = ; S < limit; ++S)
{
ll tmp = arr[i][];
for (int j = ; j < k; ++j)
{
if (S & ( << j))
{
tmp += arr[i][j + ];
}
else
{
tmp -= arr[i][j + ];
}
}
crr[S] = max(crr[S], tmp);
}
} for (int i = ; i <= m; ++i)
{
for (int S = ; S < limit; ++S)
{
ll tmp = brr[i][];
for (int j = ; j < k; ++j)
{
if (S & ( << j))
{
tmp += brr[i][j + ];
}
else
{
tmp -= brr[i][j + ];
}
}
ans = max(ans, tmp + crr[limit - - S]);
}
}
printf("%lld\n", ans);
}
} int main()
{
#ifdef LOCAL_JUDGE
freopen("Text.txt", "r", stdin);
#endif // LOCAL_JUDGE RUN(); #ifdef LOCAL_JUDGE
fclose(stdin);
#endif // LOCAL_JUDGE
return ;
}
#include <bits/stdc++.h>
using namespace std; #define N 100010
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f int t, n, m, K; struct node
{
int x[];
void scan(int vis)
{
scanf("%d", x + vis);
for (int i = ; i <= K + ; ++i) scanf("%d", x + i);
}
}a[N], b[N]; void Run()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d%d", &n, &m, &K);
for (int i = ; i <= n; ++i) a[i].scan();
for (int i = ; i <= m; ++i) b[i].scan();
ll res = ;
for (int i = ; i < ( << (K + )); ++i)
{
bitset <> bit; bit = i;
ll Max[] = { -INF, -INF };
ll Min[] = { INF, INF };
for (int j = ; j <= n; ++j)
{
ll tmp = ;
for (int k = ; k <= K + ; ++k)
tmp += a[j].x[k] * (bit[k] ? : -);
Max[] = max(Max[], tmp);
Min[] = min(Min[], tmp);
}
for (int j = ; j <= m; ++j)
{
ll tmp = ;
for (int k = ; k <= K + ; ++k)
tmp += b[j].x[k] * (bit[k] ? : -);
Max[] = max(Max[], tmp);
Min[] = min(Min[], tmp);
}
res = max(res, max(Max[] - Min[], Max[] - Min[]));
}
printf("%lld\n", res);
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ; }
K - Problem K. Pow2
留坑。
L - Problem L.Videos
题意：每天有n个小时，有m部电影，k个人，每部电影只能被一个人看，得到w快乐值，电影种类有AB两种，同一人连着看同种电影要减去W快乐值，如何安排使得快乐值最大
思路：将一部电影拆成两个点 S 和 T 流为1，费用为-w, 电影与电影之间如果是可以连着看的，就连边，如果是同种类，费用就是W, 否则就是0，流为1，源点练出来加一个点，流量为k，限制为k个人
#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + ;
const int maxm = 1e5 + ; struct Edge{
int to, nxt, cap, flow, cost;
}edge[maxm]; int head[maxn], tot;
int pre[maxn], dis[maxn];
bool vis[maxn];
int N; void Init(int n)
{
N = n;
tot = ;
for(int i = ; i < n; ++i) head[i] = -;
} void addedge(int u, int v, int cap, int cost)
{
edge[tot].to = v;
edge[tot].cap = cap;
edge[tot].cost = cost;
edge[tot].flow = ;
edge[tot].nxt = head[u];
head[u] = tot++; edge[tot].to = u;
edge[tot].cap = ;
edge[tot].cost = -cost;
edge[tot].flow = ;
edge[tot].nxt = head[v];
head[v] = tot++;
} bool SPFA(int s,int t)
{
queue<int>q;
for(int i = ; i < N; ++i) dis[i] = INF, pre[i] = -, vis[i] = false;
dis[s] = ;
vis[s] = true;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost)
{
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
if(pre[t] == -) return false;
else return true;
} int minCostMaxflow(int s,int t, int &cost)
{
int flow = ;
cost = ;
while(SPFA(s, t))
{
int Min = INF;
for(int i = pre[t]; ~i; i = pre[edge[i ^ ].to])
{
if(Min > edge[i].cap - edge[i].flow)
{
Min = edge[i].cap - edge[i].flow;
}
}
for(int i = pre[t]; ~i; i = pre[edge[i ^ ].to])
{
edge[i].flow += Min;
edge[i ^ ].flow -= Min;
cost += edge[i].cost * Min;
}
flow += Min;
}
return flow;
} struct node{
int si, ti, wi, op;
}arr[maxn]; int n, m, K, W; int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d %d %d %d", &n, &m, &K, &W);
for(int i = ; i <= m; ++i) scanf("%d %d %d %d", &arr[i].si, &arr[i].ti, &arr[i].wi, &arr[i].op);
Init( * m + );
addedge(, * m + , K, );
for(int i = ; i <= m; ++i) addedge( * m + , * i - , , );
for(int i = ; i <= m; ++i) addedge( * i - , * i, , -arr[i].wi);
for(int i = ; i <= m; ++i) addedge( * i, * m + , , );
for(int i = ; i <= m; ++i)
{
for(int j = ; j <= m; ++j)
{
if(i == j) continue;
if(arr[i].ti <= arr[j].si)
{
if(arr[i].op == arr[j].op)
{
addedge( * i, * j - , , W);
}
else
{
addedge( * i, * j - , , );
}
}
}
}
int cost = ;
minCostMaxflow(, * m + , cost);
printf("%d\n", -cost);
}
return ;
}