您的位置: 首页  >  IT文章  >  《2018 Multi-University Training Contest 10部分题解》 Problem E. TeaTree： Problem H. Pow： Problem I. Count： Problem J. CSGO: Problem L.Videos：

《2018 Multi-University Training Contest 10部分题解》 Problem E. TeaTree： Problem H. Pow： Problem I. Count： Problem J. CSGO: Problem L.Videos：

分类: IT文章 • 2023-11-08 17:18:20

折磨折磨折磨。

这题让我重新认识了dsu on tree，现在算是理解了dsu on tree的内核了，一开始做的时候已经在考虑可能是dsu on tree了。但是看了下通过率觉得应该是有技巧的。

结果还真是dsu on tree。当然也可以线段树合并。

这里最主要的一点，就是怎么处理gcd的问题。

首先，1e5之内的数的因子最多只有100多个，所以我们可以暴力便利每个点的因子。

然后判断子树中是否出现过这个因子。

这里只有两种情况：根和子树，子树和另外一个子树。

一开始写dsu on tree的时候，一直想边加入边统计答案，但是这样可能导致子树中的子树的答案更新到u上。

所以后面想了下，搜一遍先统计答案，再搜一遍加入贡献就行了。

注意的是，因为重儿子贡献没有删去，并且它不会再被solve统计，所以我们先判断重儿子和根的因子关系，然后再加入根的因子。

然后再去先去统计当前已经合并到根里的因子和一棵子树的关系，然后再去加入一棵子树的贡献，这样就不会出现错误的情况。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> pii;
const int N = 1e5 + 5;
const int M = 2000 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e18
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO {
    inline LL read() {
        LL x = 0, f = 1;
        char c = getchar();
        while (c < '0' || c > '9') {
            if (c == '-')
                f = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9') {
            x = (x << 1) + (x << 3) + (c ^ 48);
            c = getchar();
        }
        return x * f;
    }
}
using namespace FASTIO;

int n,val[N],sz[N],son[N],num[N],Son = 0,ans[N];
vector<int> G[N],vec[N];
void init() {
    for(int i = 1;i < N;++i) 
        for(int j = i;j < N;j += i) vec[j].push_back(i); 
}
void dfs(int u,int fa) {
    sz[u] = 1;
    for(auto v : G[u]) {
        if(v == fa) continue;
        dfs(v,u);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}
int solve(int u,int fa) {
    int mxx = -1;
    for(auto v : vec[val[u]]) {
        if(num[v] > 0) mxx = max(mxx,v);
    }
    for(auto v : G[u]) {
        if(v == fa || v == Son) continue;
        mxx = max(mxx,solve(v,u));
    }
    return mxx;
}
void add(int u,int fa) {
    for(auto v : vec[val[u]]) {
        num[v]++;
    }
    for(auto v : G[u]) {
        if(v == fa || v == Son) continue;
        add(v,u);
    }
} 
void del(int u,int fa) {
    for(auto v : vec[val[u]]) {
        num[v]--;
    }
    for(auto v : G[u]) {
        if(v == fa || v == Son) continue;
        del(v,u);
    }
}
void dfs1(int u,int fa,int opt) {
    for(auto v : G[u]) {
        if(v == fa || v == son[u]) continue;
        dfs1(v,u,0);
    }
    if(son[u] != 0) dfs1(son[u],u,1),Son = son[u];
    ans[u] = -1;
    for(auto v : vec[val[u]]) {
        if(num[v] > 0) ans[u] = max(ans[u],v);
        num[v]++;
    }
    for(auto v : G[u]) {
        if(v == fa || v == Son) continue;
        ans[u] = max(ans[u],solve(v,u));
        add(v,u);
    }
    Son = 0;
    if(opt == 0) del(u,fa);
}
int main() {
    memset(ans,-1,sizeof(ans));
    init();
    n = read();
    for(int i = 2;i <= n;++i) {
        int x;x = read();
        G[x].push_back(i);
        G[i].push_back(x);
    }
    for(int i = 1;i <= n;++i) val[i] = read();
    dfs(1,0);
    dfs1(1,0,0);
    for(int i = 1;i <= n;++i) printf("%d
",ans[i]);
   // system("pause");
    return 0;
}
/*
10
1 2 3 4 5 6 7 8 9
2 4 6 8 2 4 1 5 6 8 

*/
View Code

Problem H. Pow：

看了下样例，显然是2^n，然后高精度乘法就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> pii;
const int N = 1e5 + 5;
const int M = 2000 + 5;
const LL Mod = 998244353;
#define pi acos(-1)
#define INF 1e18
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO {
inline LL read() {
    LL x = 0, f = 1;
    char c = getchar();

    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;

        c = getchar();
    }

    while (c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }

    return x * f;
}
}
using namespace FASTIO;

int ans[N],len = 0;

void mul() {
    int ma = 0;
    for(int i = 1;i <= len;++i) {
        int jw = (ans[i] * 2 + ma) / 10;
        ans[i] = (ans[i] * 2 + ma) % 10;
        ma = jw;
    }
    while(ma != 0) {
        ans[++len] = ma % 10;
        ma /= 10;
    }
}
int main() {
    int ca;ca = read();
    while(ca--) {
        memset(ans,0,sizeof(ans));
        int n;n = read();
        len = 1;
        ans[1] = 1;
        for(int i = 1;i <= n;++i) mul();
        for(int i = len;i >= 1;--i) printf("%d",ans[i]);
        printf("
");
    }


   // system("pause");
    return 0;
}
View Code

Problem I. Count：

也是非常有意思的一个题目。

先打了个表：
当i为质数时：贡献就是i / 2;

当i不为质数时：

当i为偶数时，那么假设gcd(i + j,i - j) = k

那么可以猜测：i = xk,j = yk，i + j = (x + y) k ,i - j = (x - y) k

所以，i的贡献就是1 ~ i - 1中与i互质的数。也就是$varphi (i)$

当i为奇数时：

如果j也为奇数，那么i + j,i - j都是偶数，最少也是2。

所以贡献就是1 ~ i -1中的偶数且与i互质，看了下表，发现这个值= $frac{varphi (i)}{2}$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> pii;
const int N = 2e7 + 5;
const int M = 2000 + 5;
const LL Mod = 998244353;
#define pi acos(-1)
#define INF 1e18
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO {
inline LL read() {
    LL x = 0, f = 1;
    char c = getchar();

    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;

        c = getchar();
    }

    while (c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }

    return x * f;
}
}
using namespace FASTIO;

int phi[N],prime[N],tot = 0;
bool vis[N];
LL ans[N];
void init() {
    for(int i = 2;i < N;++i) {
        if(!vis[i]) {
            prime[++tot] = i;
            phi[i] = i - 1;
        }
        for(int j = 1;j <= tot && prime[j] * i < N;++j) {
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else {
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            }
        }
    }
    ans[1] = 0;
    for(int i = 2;i < N;++i) {
        ans[i] = ans[i - 1];
        if(!vis[i]) ans[i] += i / 2;
        else {
            if(i % 2 == 0) ans[i] += phi[i];
            else ans[i] += phi[i] / 2;
        }
    }

}
int main() {
    init();
    int ca;ca = read();
    while(ca--) {
        int n;n = read();
        /*for(int i = 1;i <= n;++i) {
            int ma = 0;
        //  printf("phi[%d] is %d sum[%d] is %d
",i,phi[i],i,sum[i]);
            for(int j = 1;j < i;++j) {
                printf("%d %d gcd(%d,%d) is %d
",i,j,i + j,i - j,__gcd(i + j,i - j));
            }
        } */   
        printf("%lld
",ans[n]);
    }

    //system("pause");
    return 0;
}
View Code

Problem J. CSGO:

这题的思路很巧妙。

因为是|x - y|那么对于每一对x,y去掉绝对值之后肯定只有两种状态x - y,-x + y。

所以只需要状压所有状态(1 << k)即可。

然后很显然的是如果主武器状态为s,那么服务器这一位的状态肯定是s ^ 1。（因为是去掉绝对值）

最后加上最大的两个即可。

这里很显然会存在一些不合法的状态，即无法产生的状态，但是这些状态加入是不会对答案产生影响的，因为答案肯定会合法的状态的最值  > 不合法的状态的最值

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> pii;
const int N = 1e5 + 5;
const int M = 2000 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e18
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO {
    inline LL read() {
        LL x = 0, f = 1;
        char c = getchar();
        while (c < '0' || c > '9') {
            if (c == '-')
                f = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9') {
            x = (x << 1) + (x << 3) + (c ^ 48);
            c = getchar();
        }
        return x * f;
    }
}
using namespace FASTIO;

LL a[N],b[N],s[N],ss[N],mx[N][10],fx[N][10];
int n,m,k;
LL solve(int state) {//主武器状态
    for(int i = 1;i <= n;++i) {
        a[i] = s[i];
        for(int j = 1;j <= k;++j) {
            int g = (state >> (j - 1)) & 1;
            if(g == 0) {
                a[i] -= mx[i][j];
            }
            else a[i] += mx[i][j];
        }
    }
    sort(a + 1,a + n + 1);
    for(int i = 1;i <= m;++i) {
        b[i] = ss[i];
        for(int j = 1;j <= k;++j) {
            int g = (state >> (j - 1)) & 1;
            if(g == 0) {
                b[i] += fx[i][j];
            }
            else b[i] -= fx[i][j];
        }
    }
    sort(b + 1,b + m + 1);
    return a[n] + b[m];
}
int main() {
    int ca;ca = read();
    while(ca--) {
        n = read(),m = read(),k = read();
        for(int i = 1;i <= n;++i) {
            s[i] = read();
            for(int j = 1;j <= k;++j) mx[i][j] = read();
        }
        for(int i = 1;i <= m;++i) {
            ss[i] = read();
            for(int j = 1;j <= k;++j) fx[i][j] = read();
        }
        LL ans = 0;
        for(int i = 0;i < (1 << k);++i) {
            ans = max(ans,solve(i));
        }
        printf("%lld
",ans);
    }

    //system("pause");
    return 0;
}
View Code

Problem L.Videos：

好家伙，写题解的时候发现题意读错了。

这题的题意是：

多个人可以在重叠的时间段看不同的video。

做的时候一直以为一个时间内只能放一部video。

看到的第一眼就觉得是费用流，结果建图一直建不对。

一直纠结于对时间拆点。

其实这里不需要对时间进行拆点。

建图思路：

首先很显然video之间可以建立边，注意计算一直费用即可。

直接每个video向汇点连容量为1的点。

然后时间点的限制就用来video之间连边。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int N = 1e3 + 5;
const int M = 1e4 + 5;
const LL Mod = 998244353;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO {
inline LL read() {
    LL x = 0, f = 1;
    char c = getchar();

    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;

        c = getchar();
    }

    while (c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }

    return x * f;
}
}
using namespace FASTIO;

int n,m,s,t,cnt = -1,maxflow = 0,mincost = 0;
int head[N],pre[N],cal[N],dis[N],vis[N];//pre记录前驱,cal记录最短增广路上的最小流量,dis记录最短路
struct Node{int to,dis,flow,next;}e[M<<1];
int u[N],v[N],w[N],op[N];
inline void add(int u,int v,int w,int flow)//费用,容量
{
    e[++cnt].to = v,e[cnt].dis = w,e[cnt].flow = flow,e[cnt].next = head[u],head[u] = cnt;
    e[++cnt].to = u,e[cnt].dis = -w,e[cnt].flow = 0,e[cnt].next = head[v],head[v] = cnt;
}
bool spfa()
{
    memset(vis,0,sizeof(vis));
    for(int i = 0;i <= t;++i) dis[i] = INF;
    queue<int> Q;
    Q.push(s);
    dis[s] = 0,vis[s] = 1,cal[s] = INF;
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        vis[u] = 0;//spfa标准操作,清除标记
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v = e[i].to,d = e[i].dis,flow = e[i].flow;
            if(flow <= 0) continue;//没有剩余流量可流
            if(dis[v] > dis[u]+d)
            {
                dis[v] = dis[u]+d;
                cal[v] = min(cal[u],flow);//更新增广路上的最小流量
                pre[v] = i;//前驱记录i,因为是链式前向星
                if(!vis[v]) vis[v] = 1,Q.push(v);
            }
        }
    }
    if(dis[t] == INF) return false;
    return true;
}
void MCMF()
{
    while(spfa())
    {
        int x = t;
        maxflow += cal[t];
        mincost += dis[t]*cal[t];
        while(x!=s)
        {
            int i = pre[x];
            e[i].flow -= cal[t];
            e[i^1].flow += cal[t];
            x = e[i^1].to;
        }
    }
}
/*
超级源点 - 次源点,
video - video,video - tim
tim - 超级汇点
s = 0;
ss = 1;
video st : [2 + i,2 * n] to : [2 * n + i,2 * n + m]
t = 2 * n + m + 1
*/
int main() {
    int ca;ca = read();
    while(ca--) {
        int k,W;
        n = read(),m = read(),k = read(),W = read();
        memset(head,-1,sizeof(head));
        cnt = -1,maxflow = 0,mincost = 0;
        s = 0,t = 2 * n + m + 1;
        int ss = 1;
        add(s,ss,0,k);
        for(int i = 1;i <= m;++i) {
            u[i] = read(),v[i] = read(),w[i] = read(),op[i] = read();
            add(ss,2 + i,0,1);//ss - video
            add(2 + i,2 * n + i,-w[i],1);//video - video
            add(2 * n + i,t,0,1);
        }
        for(int i = 1;i <= m;++i) {
            for(int j = 1;j <= m;++j) {
                if(v[i] <= u[j]) {
                    add(2 * n + i,2 + j,(op[i] == op[j]) * W,1);//video - video
                }
            }
        }
        MCMF();
        printf("%d
",abs(mincost));
    }


   // system("pause");
    return 0;
}
View Code

相关推荐