2018 Multi-University Training Contest 10
前言
多校的题目好可怕 QAQ
从多校的题目中真的学到了很多东西
听Arteezy大佬说B站有题解
- GCD性质
https://zhidao.baidu.com/question/875968392336023812.html - 交换求和次序
http://tieba.baidu.com/p/2993628451 - 欧拉函数的性质
https://blog.csdn.net/YxuanwKeith/article/details/52387873 - 线段树合并
https://blog.csdn.net/Dale_zero/article/details/82027470 - 最远曼哈顿距离
https://www.cnblogs.com/lmnx/articles/2479747.html
Problem H. Pow - HDU - 6433
题意
求3^0, 3^1, 3^2, …, 3^n选取若干个数相加得到的和的种类数
思路
签到题
将其作为三进制数，那么就是01串了，视为向量的话是线性无关的，所以就是2^n
不过要开大数
import java.math.BigInteger;
import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner cin = new Scanner(System.in);
int t = cin.nextInt();
for(int i = 0; i < t; i++){
int num = cin.nextInt();
BigInteger res = new BigInteger("2").pow(num);
System.out.println(res);
}
}
}
Problem G. Cyclic - HDU - 6432
题意
求包含1到n各一次的序列的可能种类数
思路
直接OEIS查，按递推公式写 = =||
听说正解是容斥原理，以后有学到会作为题目做的
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int N = 1e5 + 15;
typedef long long ll;
const ll MOD = 998244353;
//a(n) = (n-2) * a(n-1) + (n-1) * a(n-2) - (-1)^n,
ll a[N] {1, 0, 0};
int main(){
for(int i = 3; i < N; i++){
a[i] = ((i - 2) * a[i - 1]%MOD + (i - 1) * a[i - 2]%MOD)%MOD;
if(i&1) a[i] = (a[i] + 1)%MOD;
else a[i] = (a[i] - 1 + MOD)%MOD;
}
int t;
scanf("%d", &t);
while(t--){
int n;
scanf("%d", &n);
printf("%lld\n", a[n]);
}
}
Problem I. Count HDU - 6434
思路 —— 欧拉函数 + GCD性质
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <random>
using namespace std;
const int N = 2e7 + 15;
typedef long long ll;
int prime[N], phi[N];
int prime_tot;
bool used[N];
ll sum[N];
void euler(){
memset(used, true, sizeof(used));
prime_tot = 0;
phi[1] = 1;
for(int i = 2; i < N; i++){
if(used[i]){
prime[prime_tot++] = i;
phi[i] = i - 1;
}
for(int j = 0; i*prime[j] < N; j++){
used[i*prime[j]] = false;
if(i%prime[j] == 0){
phi[i*prime[j]] = phi[i] * prime[j];
break;
}else{
phi[i*prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
sum[0] = 0;
for(int i = 1; i < N; i++){
if(i&1) sum[i] = sum[i - 1] + phi[i] / 2LL;
else sum[i] = sum[i - 1] + phi[i];
}
}
int main(){
euler();
int t;
scanf("%d", &t);
while(t--){
int n;
scanf("%d", &n);
printf("%lld\n", sum[n]);
}
}
Problem E. TeaTree - HDU - 6430
题意
对于某个节点，求以该节点为LCA的节点的权值GCD最大值，对于每个节点都输出改值，不存在输出-1
思路 —— 权值线段树动态开点 + 线段树合并 + 拓扑排序
学习了一下线段树合并
对于每个节点开一棵权值线段树，以因子作为权值插入线段树中，然后对其进行拓扑排序，以拓扑排序逆序进行线段树合并，合并时同时统计答案，若两棵树同时存在某个权值，那就是可能的GCD最大值，否则就只合并不更新答案
在这其中，线段树维护的是某个权值的存在性（即有或无）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e5 + 3;
#define lson l, m
#define rson m + 1, r
struct edge{
int v, nxt;
};
edge e[N];
int head[N], etot;
int root[N], ls[N*400], rs[N*400], ft[N];
int tot;
int ans[N];
vector<int> vec[N];
inline int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
} while('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
} return x * f;
}
inline void init(){
tot = 1;
etot = 0;
memset(ans, -1, sizeof(ans));
memset(head, -1, sizeof(head));
}
inline void addEdge(int u, int v){
e[etot] = edge{v, head[u]};
head[u] = etot++;
}
inline void newNode(int& o){
o = tot++;
ls[o] = rs[o] = 0;
}
void push(int& o, int val, int l, int r){
if(!o) newNode(o);
if(l == r) return;
int m = (l + r) >> 1;
if(val <= m) push(ls[o], val, lson);
else push(rs[o], val, rson);
}
int merge(int o1, int o2, int fa, int l, int r){
if(o1 == 0 || o2 == 0) return o1 ^ o2;
if(l == r){
ans[fa] = max(ans[fa], l);
return o1;
}
int m = (l + r) >> 1;
ls[o1] = merge(ls[o1], ls[o2], fa, lson);
rs[o1] = merge(rs[o1], rs[o2], fa, rson);
return o1;
}
void dfs(int u){ //DFS式拓扑排序
for(int i = head[u]; ~i; i = e[i].nxt){
dfs(e[i].v);
}
if(u == 1) return;
root[ft[u]] = merge(root[ft[u]], root[u], ft[u], 1, (int)1e5);
}
int main(){
for(int i = 1; i < N; i++){ //初始化记录每个数的因子
for(int j = 1; i*j < N; j++){
vec[i*j].push_back(i);
}
}
int n;
while(~scanf("%d", &n)){
init();
for(int u = 2; u <= n; u++){
ft[u] = read();
addEdge(ft[u], u);
}
for(int u = 1; u <= n; u++){
int w = read();
newNode(root[u]);
for(int j = 0; j < vec[w].size(); j++){
push(root[u], vec[w][j], 1, (int)1e5);
}
}
dfs(1);
for(int u = 1; u <= n; u++){
printf("%d\n", ans[u]);
}
}
}
Problem J. CSGO - HDU - 6435
题意
给定n + m个点，每个点给定si和坐标，求n点集合和m点集合中各取一点的 si + sj + 曼哈顿距离 的最大值
思路 —— 最远曼哈顿距离
没想到是结论题 QAQ
枚举01串，0为负，1为正，对于在n个点集合的点i和m个点集合的点j，其曼哈顿距离必定满足01串之和为111…，可以利用这一特点枚举，虽然有非法的情况（比如01串之和为111…，但是原式不会得到那个结果），但是合法的曼哈顿距离必定是最大的那一个
所以预处理一下n个点集合的，再用m个点集合的更新答案
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e5 + 3;
const ll inf = 1LL << 60;
ll sav[N];
int x[7];
inline void init(){
fill(sav, sav + N, -inf);
}
int main(){
int t;
scanf("%d", &t);
while(t--){
init();
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for(int i = 0; i < n; i++){
int s;
scanf("%d", &s);
for(int j = 0; j < k; j++){
scanf("%d", &x[j]);
}
for(int p = 0; p < (1 << k); p++){
ll sum = s;
for(int j = 0; j < k; j++){
if((p >> j) & 1) sum += x[k - j - 1];
else sum -= x[k - j - 1];
}
sav[p] = max(sav[p], sum);
}
}
ll ans = 0;
for(int i = 0; i < m; i++){
int s;
scanf("%d", &s);
for(int j = 0; j < k; j++){
scanf("%d", &x[j]);
}
for(int p = 0; p < (1 << k); p++){
if(sav[(1 << k) - p - 1] == -inf) continue;
ll sum = s;
for(int j = 0; j < k; j++){
if((p >> j) & 1) sum += x[k - j - 1];
else sum -= x[k - j - 1];
}
ans = max(ans, sum + sav[(1 << k) - p - 1]);
}
}
printf("%lld\n", ans);
}
}
Problem L.Videos - HDU - 6437
题意
有m个视频，k个人，每个视频的价值为val[i]，类型为A或B，播放时间为[l, r]，且只能被一个人看，某个人看视频必须完整的看完，一个视频看完可以立刻看别的视频，即可以看[a,b]和[b,c]，若一个人看视频而相邻视频类型相同，则每相邻一对会损失w价值，问k个人看视频所能获得的价值最大值是多少
思路 —— 最大费用最大流
以视频建点，如图所示
根据[l,r]确定每个点可以接下去看视频的点，建边
为了避免同一个视频被看两次，因此复制多一个点再建边，可以发现这样子能避免
（蒟蒻表示这样子建图应该是有优化的空间的）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 400 + 15;
const int M = 2e5 + 15;
const int inf = 0x3f3f3f3f;
struct edge{
int v, val, cost, next;
};
edge e[M << 2];
int tot, head[N], pre[N], d[N], cur[N];
bool inq[N];
queue<int> que;
int l[N], r[N], val[N], type[N];
inline int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
} while('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
} return x * f;
}
inline void init(){
memset(head, -1, sizeof(head));
tot = 0;
}
inline void addEdge(int u, int v, int val, int cost){
e[tot] = edge{v, val, cost, head[u]};
head[u] = tot++;
e[tot] = edge{u, 0, -cost, head[v]};
head[v] = tot++;
}
bool spfa(int src, int des){
fill(d, d + N, -inf);
memset(inq, false, sizeof(inq));
d[src] = 0, pre[src] = src;
que.push(src);
inq[src] = true;
while(!que.empty()){
int u = que.front();
que.pop();
inq[u] = false;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].v;
if(d[v] < d[u] + e[i].cost && e[i].val){
d[v] = d[u] + e[i].cost;
pre[v] = u;
cur[v] = i;
if(!inq[v]){
que.push(v);
inq[v] = true;
}
}
}
}
return d[des] != -inf;
}
int solve(int src, int des){
int ans = 0;
while(spfa(src, des)){
int aug = inf;
for(int v = des; v != src; v = pre[v]) aug = min(aug, e[cur[v]].val);
for(int v = des; v != src; v = pre[v]){
e[cur[v]].val -= aug;
e[cur[v]^1].val += aug;
}
ans += d[des] * aug;
}
return ans;
}
int main(){
int t = read();
while(t--){
init();
int n = read(), m = read(), k = read(), w = read();
int ss = 0, s = 2*m + 1, t = 2*m + 2;
for(int i = 1; i <= m; i++){
l[i] = read(), r[i] = read(), val[i] = read(), type[i] = read();
}
addEdge(ss, s, k, 0);
for(int i = 1; i <= m; i++){
addEdge(s, i, 1, val[i]);
addEdge(i, i + m, 1, 0);
addEdge(i + m, t, 1, 0);
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
if(i == j) continue;
if(r[i] <= l[j]){
if(type[i]^type[j]) addEdge(i + m, j, 1, val[j]);
else addEdge(i + m, j, 1, val[j] - w);
}
}
}
printf("%d\n", solve(ss, t));
}
return 0;
}
