2018 Multi-University Training Contest 10

Problem E. TeaTree

题意：

　　给出一颗树每个节点的value值，对于每个节点询问它和它的子节点中任意两个节点u，v的最大gcd（value【u】，value【v】）值。

分析：

　　对于每个节点都建立一颗线段树，然后从下而上合并父亲节点和子节点的线段树即可。因为对于每个节点的线段树，线段树中的每个节点代表的区间都是一样的，那么我们存储每个区间的最大因子值。如果两个线段树在相同的区间的最大值不一样，那么我们取其中的最大值作为新线段树的最大因子值（小的值会被存储在更小的区间内），如果一个为空则取非空的那个。如果两个线段树在相同区间的最大因子值一样，那么可以认为这两个节点的value值都含有这个因子，取所有公共因子的最大值就是答案。

　　参考博客：大佬博客

代码：

#include <queue>
#include <vector>
#include <math.h>
#include <string>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;
#define ll long long
#define ull unsigned long long
#define cls(x) memset(x,0,sizeof(x))
#define clslow(x) memset(x,-1,sizeof(x))

const int maxv=1e5+100;
const int maxn=1e5+100;

int n,tot;

vector<int>fac[maxv];
int ans[maxn],head[maxn],root[maxn];

struct Edge {
    int v,nex;
};
Edge e[maxn];

void getfac()
{
    fac[1].push_back(1);
    for(int i=2;i<maxv;i++){
        fac[i].push_back(1);
        fac[i].push_back(i);
        for(int j=i+i;j<maxv;j+=i){
            fac[j].push_back(i);
        }
    }
}

inline void addEdge(int u,int v)
{
    e[tot].v=v;
    e[tot].nex=head[u];
    head[u]=tot++;
}

namespace IntervalTree {
    #define maxm maxv*400
    #define lson l,m,ls[rt]
    #define rson m+1,r,rs[rt]

    int rear;
    int ls[maxm],rs[maxm],maxx[maxm];

    inline void PushUp(int rt)
    {
        if(ls[rt]&&rs[rt])  maxx[rt]=max(maxx[ls[rt]],maxx[rs[rt]]);
        else if(ls[rt])     maxx[rt]=maxx[ls[rt]];
        else if(rs[rt])     maxx[rt]=maxx[rs[rt]];
    }
    inline void update(int p,int l,int r,int& rt)
    {
        if(rt==0)   rt=++rear;
        if(l==r){
            maxx[rt]=p;
            return;
        }
        int m=(l+r)>>1;
        if(p<=m)    update(p,lson);
        else        update(p,rson);
        PushUp(rt);
    }
    inline int merge(int frt,int srt,int& ans)
    {
        if(frt==0||srt==0)  return frt^srt;
        if(maxx[frt]==maxx[srt])    ans=max(ans,maxx[frt]);
        if(ls[frt]||ls[srt])    ls[frt]=merge(ls[frt],ls[srt],ans);
        if(rs[frt]||rs[srt])    rs[frt]=merge(rs[frt],rs[srt],ans);
        PushUp(frt);
        return frt;
    }
}

void init()
{
    tot=0;
    clslow(head);
    IntervalTree::rear=0;
}

void dfs(int u)
{
    ans[u]=-1;
    for(int i=head[u];~i;i=e[i].nex){
        dfs(e[i].v);
        root[u]=IntervalTree::merge(root[u],root[e[i].v],ans[u]);
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif // ONLINE_JUDGE
    getfac();
    while(scanf("%d",&n)!=EOF)
    {
        init();
        for(int i=2;i<=n;i++){
            int fa;
            scanf("%d",&fa);
            addEdge(fa,i);
        }
        for(int i=1;i<=n;i++){
            int x,sz,divisor;
            scanf("%d",&x);
            root[i]=0;
            sz=fac[x].size();
            for(int j=0;j<sz;j++){
                divisor=fac[x][j];
                IntervalTree::update(divisor,1,maxv,root[i]);
            }
        }

        dfs(1);
        for(int i=1;i<=n;i++){
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}

Problem G. Cyclic

题意：

　　用1~n的所有数组成一个环满足环中相邻的元素不为连续的子序列 i，（i+1）%n，问满足上述条件的环的个数？

分析：

　　考虑使用容斥原理进行计数. 
　　包含至少一个形如 [i, i + 1] 或 [n, 1] 这样的子串的环排列个数是 C(n,1)(n − 2)! 个; 
　　可以推广为包含至少 k(0 ≤ k < n) 个的环排列个数是 C(n,k)(n − k − 1)!, 
　　同时注意到,包含 n 个的环排列个数一定是 1 个. 
　　所以最终答案就是 
　　(−1)^n +∑(k=0,k=n−1)(−1)^k*C(n,k)(n − k − 1)!

　　参考博客：大佬博客

代码：

#include <stack>
#include <queue>
#include <vector>
#include <math.h>
#include <string>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;
#define ll long long
#define ull unsigned long long
#define cls(x) memset(x,0,sizeof(x))
#define clslow(x) memset(x,-1,sizeof(x))

const int maxn=1e5+100;
const int mod=998244353;

int n,T;

ll fac[maxn],inv[maxn];

ll poww(ll a,int k)
{
    ll res=1;
    while(k)
    {
        if(k&1) res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res;
}

void init()
{
    fac[0]=fac[1]=1;
    for(int i=2;i<maxn;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    inv[maxn-1]=poww(fac[maxn-1],mod-2);
    for(int i=maxn-2;i>=0;i--){
        inv[i]=inv[i+1]*(i+1)%mod;
    }
}

ll C(int n,int m)
{
    return fac[n]*inv[n-m]%mod*inv[m]%mod;
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif // ONLINE_JUDGE
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int sign=-1;
        ll ans=fac[n-1];
        for(int i=1;i<=n;i++){
            ans=(ans+sign*C(n,i)*fac[n-i-1]%mod+mod)%mod;
            sign=-sign;
        }
        if(n&1) ans--;
        else    ans++;
        printf("%lld\n",(ans+mod)%mod);
    }
    return 0;
}

Problem H. Pow

题意：

　　n个数的子集的个数（包括空集）。

分析：

　　直接输出2^n即可。

代码：

#include <stack>
#include <queue>
#include <vector>
#include <math.h>
#include <string>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;
#define ll long long
#define ull unsigned long long
#define cls(x) memset(x,0,sizeof(x))
#define clslow(x) memset(x,-1,sizeof(x))
#define clshigh(x) memset(x,0x3f3f3f3f,sizeof(x))

const int maxn=1e5+100;
const int inf=0x3f3f3f3f;

int n,T;

const int L=1000;
string mul(string a,string b)
{
    string s;
    int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();
    fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);
    for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';
    for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';
    for(int i=1;i<=La;i++)
        for(int j=1;j<=Lb;j++)
        nc[i+j-1]+=na[i]*nb[j];
    for(int i=1;i<=La+Lb;i++)
        nc[i+1]+=nc[i]/10,nc[i]%=10;
    if(nc[La+Lb]) s+=nc[La+Lb]+'0';
    for(int i=La+Lb-1;i>=1;i--)
        s+=nc[i]+'0';
    return s;
}


int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif // ONLINE_JUDGE
    cin>>T;
    while(T--)
    {
        cin>>n;
        string a="1",b="2";
        for(int i=1;i<=n;i++){
            a=mul(a,b);
        }
        cout<<a<<endl;
    }
    return 0;
}

Problem I. Count

题意：

　　求的值。

分析：

　　根据题意我们要找对于i满足a+b=2*i且a，b互质的对数。这时我们需要一个规律：a与b互质，那么 a，b 分别与 （a+b）互质，这样的话我们求满足上述条件的对数的时候，只要求 phi[ 2*i ] (欧拉函数)  ÷   2  就好了，，求ans的话就是求前缀和。

证明： 若a与b互质，那么 a，b 分别与 （a+b）互质 ：

先假设 a 与 (a+b) 不互质，那么令他们的gcd = t，  a=t*x, (a+b) = t*y

那么 b = t*y - t*x = t * (y-x) ,这样 a，b就会有公因子 t ，矛盾，所以 a 与 (a+b) 互质

　　参考博客：大佬博客

代码：

#include <queue>
#include <vector>
#include <math.h>
#include <string>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;
#define ll long long
#define ull unsigned long long
#define cls(x) memset(x,0,sizeof(x))
#define clslow(x) memset(x,-1,sizeof(x))

const int maxn=4e7+100;

int n,T;

ll ans[maxn];
bool vis[maxn];
int phi[maxn],prime[maxn];

void getphi(int n)
{
    cls(vis);
    int cnt=0;
    for(int i=2;i<n;i++){
        if(!vis[i]){
            prime[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<cnt&&i*prime[j]<n;j++){
            ll k=i*prime[j];
            vis[k]=1;
            if(i%prime[j]==0){
                phi[k]=phi[i]*prime[j];
                break;
            }
            else{
                phi[k]=phi[i]*(prime[j]-1);
            }
        }
    }
}

void init()
{
    ans[1]=0;
    getphi(maxn);
    for(int i=2;i<maxn;i++){
        ans[i]=ans[i-1]+phi[2*i]/2;
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif // ONLINE_JUDGE
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%lld\n",ans[n]);
    }
    return 0;
}

Problem J. CSGO

题意：

　　现在有n个主武器和m个副武器，每个武器都有一个初始分数和k个属性值，问挑选一把主武器和服务器的得到的最大评估值是多少？（评估值计算公式为题目中所给公式）

分析：

　　首先我们知道|a-b|=max（a-b，b-a），所以公式可以化简为Smw+Ssw+∑max（Xmw【i】-Xsw【i】，Xsw【i】-Xmw【i】）。不难看出对于主武器的每个属性值要么加上要么减去且主武器和副武器相同的属性的加减状态相反。考虑枚举主武器属性的加减状态，因为对于上面的式子，我们所求的是主武器每种属性不同状态的最大值，所以对于总体我们求出在所有情况下的评估值，取其中的最大值即是算出的评估值。

　　对于所有的枚举状态，我们算出n件主武器和m件副武器在当前状态下属性对应加减的和中的最大值和最小值，用主武器的最大值减去副武器的最小值或者副武器的最大值减去主武器的最小值（用减是为了保证相同属性的加减状态相反），两者的最大值即是在当前状态下所求的最大评估值，取所有状态的最大值即是结果。对于主武器和副武器的初始分数，将他们分别作为第k+1，k+2个属性，并且让对应的相同属性的值取0即可。

　　参考博客：大佬博客

代码：

#include <queue>
#include <vector>
#include <math.h>
#include <string>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;
#define ll long long
#define ull unsigned long long
#define cls(x) memset(x,0,sizeof(x))
#define clslow(x) memset(x,-1,sizeof(x))

const ll inf=1e18;
const int maxk=10;
const int maxn=1e5+100;

int n,m,k,T;

int mw[maxn][maxk],sw[maxn][maxk];

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif // ONLINE_JUDGE
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d %d",&n,&m,&k);
        for(int i=1;i<=n;i++){
            scanf("%d",&mw[i][0]);
            for(int j=1;j<=k;j++){
                scanf("%d",&mw[i][j+1]);
            }
        }
        for(int i=1;i<=m;i++){
            scanf("%d",&sw[i][1]);
            for(int j=1;j<=k;j++){
                scanf("%d",&sw[i][j+1]);
            }
        }

        ll ans=-inf;
        int up=1<<(k+2);
        for(int i=0;i<up;i++){
            ll minv1=inf,maxv1=-inf;
            ll minv2=inf,maxv2=-inf;
            for(int j=1;j<=n;j++){
                ll value=0;
                for(int t=0;t<=k+1;t++){
                    if(i&(1<<t))    value+=mw[j][t];
                    else            value-=mw[j][t];
                }
                minv1=min(minv1,value);
                maxv1=max(maxv1,value);
            }

            for(int j=1;j<=m;j++){
                ll value=0;
                for(int t=0;t<=k+1;t++){
                    if(i&(1<<t))    value+=sw[j][t];
                    else            value-=sw[j][t];
                }
                minv2=min(minv2,value);
                maxv2=max(maxv2,value);
            }

            ans=max(ans,maxv1-minv2);
            ans=max(ans,maxv2-minv1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Problem L.Videos

题意：

　　每部影片有开始时间，结束时间，影片类型和开心值四种属性。现在k个人去看m部影片，一个人一次只能看一部影片，一部影片只能被一个人看，看完一部影片后会得到影片对应的开心值，如果一个人连续两次所看的影片类型相同，则减去W开心值，问所能得到的最大开心值是多少？

分析：

　　最优解肯定是使用更多的人（因为可以调控所看的影片类型，尽量不让一个人连续看到两部类型相同的影片），考虑最大费用最大流。对于电影进行拆点，建立一条容量为1，费用为-w【i】的边，对于没有时间冲突的电影之间根据类型是否相同建立一条容量为1，费用为W或0的边，最后建立一个汇点和源点跑一个最小费用最大流即可。

　　参考博客：大佬博客

代码：

#include <stack>
#include <queue>
#include <vector>
#include <math.h>
#include <string>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;
#define ll long long
#define ull unsigned long long
#define cls(x) memset(x,0,sizeof(x))
#define clslow(x) memset(x,-1,sizeof(x))
#define clshigh(x) memset(x,0x3f3f3f3f,sizeof(x))

const int maxn=1e5+100;
const int inf=0x3f3f3f3f;

int n,m,k,W,T;

int source,sink,edgenum;
bool vis[maxn];
int head[maxn],pre[maxn],dist[maxn];
struct Edge{
    int from, to, cap, flow, cost, next;
};
Edge edge[maxn];
void init()
{
    edgenum = 0;
    clslow(head);
}
void addEdge(int u, int v, int w, int c)
{
    Edge E1 = {u, v, w, 0, c, head[u]};
    edge[edgenum] = E1;
    head[u] = edgenum++;
    Edge E2 = {v, u, 0, 0, -c, head[v]};
    edge[edgenum] = E2;
    head[v] = edgenum++;
}
bool SPFA(int s, int t)
{
    cls(vis);
    clslow(pre);
    clshigh(dist);

    queue<int> Q;
    dist[s] = 0;
    vis[s] = true;
    Q.push(s);
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        vis[u] = false;
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            Edge E = edge[i];
            if(dist[E.to] > dist[u] + E.cost && E.cap > E.flow)
            {
                dist[E.to] = dist[u] + E.cost;
                pre[E.to] = i;
                if(!vis[E.to])
                {
                    vis[E.to] = true;
                    Q.push(E.to);
                }
            }
        }
    }
    return pre[t] != -1;
}
void MCMF(int s, int t, int &cost, int &flow)
{
    flow = 0;
    cost = 0;
    while(SPFA(s, t))
    {
        int Min = inf;
        for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
        {
            Edge E = edge[i];
            Min = min(Min, E.cap - E.flow);
        }
        for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
        {
            edge[i].flow += Min;
            edge[i^1].flow -= Min;
            cost += edge[i].cost * Min;
        }
        flow += Min;
    }
}

struct Movie {
    int s,t,w,op;
};
Movie movie[300];

void getMap()
{
    scanf("%d %d %d %d",&n,&m,&k,&W);
    for(int i=1;i<=m;i++){
        scanf("%d %d %d %d",&movie[i].s,&movie[i].t,&movie[i].w,&movie[i].op);
    }
    source=0;sink=k+2*m+1;
    for(int i=1;i<=m;i++){
        addEdge(i,i+m,1,-movie[i].w);
        addEdge(i+m,sink,1,0);
        for(int j=1;j<=m;j++){
            if(movie[i].t<=movie[j].s){
                if(movie[i].op==movie[j].op)    addEdge(i+m,j,1,W);
                else                            addEdge(i+m,j,1,0);
            }
        }
    }
    for(int i=1;i<=k;i++){
        addEdge(source,i+2*m,1,0);
        for(int j=1;j<=m;j++){
            addEdge(i+2*m,j,1,0);
        }
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif // ONLINE_JUDGE
    scanf("%d",&T);
    while(T--)
    {
        init();
        getMap();
        int cost, flow;
        MCMF(source, sink, cost, flow);
        printf("%d\n", -cost);
    }
    return 0;
}