WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
2018 Multi-University Training Contest 2
2018 Multi-University Training Contest 2

HDU 6311 Cover

题意:给定一个无向图,求用最少的若干条不相交的路径覆盖图的所有边。

一个欧拉回路的图可以一笔画,所以一定可以只使用一条路径不重不漏覆盖所有边,如果不是欧拉回路,那么一条路径一定可以消掉两个奇数度数的点。所以一个联通块,最少需要用min(\frac{Number of Odd Degree Points}{2},1)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

namespace UG_EulerPath{
    const int MAXN=100000+50;
    const int MAXM=500000+50;

    struct Edge{
        int v, nxt, idx;
        bool enbled;
        Edge(){}
        Edge(int v0, int n0, int i0){
            v=v0, nxt=n0, idx=i0;
            enbled=true;
        }
    }e[MAXM*2];
    int head[MAXN], nume;
    int deg[MAXN];

    inline void init(){
        memset(head, 0, sizeof(head));
        memset(deg, 0, sizeof(deg));
        nume=1;
    }

    inline void addEdge(int u, int v, int idx){
        e[++nume]=Edge(v, head[u], idx);
        head[u]=nume;
        e[++nume]=Edge(u, head[v], -idx);
        head[v]=nume;
        ++deg[u], ++deg[v];
    }

    vector<int> ansPath;
    void dfs(int x){
        for (int i=head[x]; i; i=e[i].nxt){
            if (!e[i].enbled) continue;
            e[i].enbled=e[i^1].enbled=false;
            dfs(e[i].v);
            ansPath.push_back(e[i].idx);
        }
    }

    inline bool solve(int n, int m){
        int cnt=0, st=-1;
        for (int i=1; i<=n; i++) {
            cnt+=(deg[i]&1);
            if ((deg[i]>0 && st==-1) || (deg[i]&1)) st=i;
        }
        if (!(cnt==0 || cnt==2)) return false;
        ansPath.clear();
        dfs(st);
        if (ansPath.size()!=m) return false;
        return true;
    }
}

namespace UFS{
    const int MAXN=1e5+50;

    int fa[MAXN];
    inline void init(int n){
        for (int i=0; i<=n; i++) fa[i]=i;
    }
    int getFather(int x){
        return fa[x]=(fa[x]==x?x:getFather(fa[x]));
    }
    inline bool mergeFather(int x, int y){
        int fx=getFather(x), fy=getFather(y);
        if (fx>fy){
            fa[fx]=fy;
        }else fa[fy]=fx;
    }
}

const int MAXN=100000+50;
const int MAXM=500000+50;

int siz[MAXN];
vector<int> oddVertex[MAXN];
vector<int> ansPath[MAXM];

inline void solve(int n, int m){
    for (int i=1; i<=m; i++) ansPath[i].clear();
    for (int i=1; i<=n; i++) oddVertex[i].clear(), siz[i]=0;
    int ans=0, lock=UG_EulerPath::nume;

    for (int x=1; x<=n; x++){
        siz[UFS::getFather(x)]++;
        if (UG_EulerPath::deg[x]&1) oddVertex[UFS::getFather(x)].push_back(x);
    }

    for (int x=1; x<=n; x++){
        int fx=UFS::getFather(x);
        if (siz[fx]<=1) continue; siz[fx]=0;
        //printf("x:%d\n", x, siz[fx]);
        for (int j=2; j<oddVertex[fx].size(); j+=2) UG_EulerPath::addEdge(oddVertex[fx][j], oddVertex[fx][j+1], 0);
        UG_EulerPath::ansPath.clear();
        if (oddVertex[fx].size()>0) UG_EulerPath::dfs(oddVertex[fx][0]); else UG_EulerPath::dfs(fx);
        //printf("#%d\n", UG_EulerPath::ansPath.size());
        ++ans;
        for (int j=0; j<UG_EulerPath::ansPath.size(); j++){
            int p=UG_EulerPath::ansPath[j];
            if (p==0) ++ans; else ansPath[ans].push_back(p);
        }
    }

    printf("%d\n", ans);
    for (int i=1; i<=ans; i++){
        printf("%d", ansPath[i].size());
        for (int j=0; j<ansPath[i].size(); j++) printf(" %d", -ansPath[i][j]);
        printf("\n");
    }
}

int main(){
    //freopen("in.txt", "r", stdin);
    int n, m;
    while(scanf("%d%d", &n, &m)!=EOF){
        UG_EulerPath::init();
        UFS::init(n);
        for (int i=1; i<=m; i++){
            int x, y; scanf("%d%d", &x, &y);
            UG_EulerPath::addEdge(x, y, i);
            UFS::mergeFather(x, y);
        }
        solve(n, m);
    }
    return 0;
}

HDU 6312

题意:1~n若干个数字,取x操作将取走x及其所有约数。很明显,1这个数字无论如何都会在第一轮被取走,所以如果2~n存在后手胜策略,先手只需要取1就可以获胜,否则先手按照2~n先手胜策略即可取胜,所以先手一定胜利。(巧克力博弈)

#include <cstdio>
using namespace std;
int main(){
    int n=0;
    while(scanf("%d", &n)!=EOF) puts("Yes");
    return 0;
}

HDU 6313 Hack it

题意:生成一个大小为n\cdot n的01矩阵,使得不存在四个顶点均为1的子矩阵。

如果n为质数,那么模n循环群有0-n-1n-1个生成元。按照这个原理生成每行的01位置,就不存在如题禁止矩阵了。

选定质数为47,生成一个大小为(47*47)^2的矩阵即可。

#include <cstdio>
using namespace std;

const int BASE=47;
const int MAXN=BASE*BASE+50;
const int MAXM=2000;

int matrix[MAXN][MAXN];
int main(){
    for (int i=1; i<=MAXN; i++){
        int now=(i-1)/BASE, step=(i-1)%BASE+1;
        for (int j=0; j<BASE; j++){
            now=(now+step-1)%BASE+1;
            matrix[i][j*BASE+now]=1;
        }
    }
    printf("%d\n", MAXM);
    for (int i=1; i<=MAXM; i++){
        for (int j=1; j<=MAXM; j++)
            putchar(matrix[i][j]+'0');
        puts("");
    }
    return 0;
}

HDU 6314 Matrix

题意:给一个n\cdot m的矩阵涂上黑白两色,问至少有ab列全都是黑色的方案数。

f[n][m]表示nm列的矩阵没有一行或一列全都是黑色的方案数。
容斥可以知道:

f[n][m] = \sum_{i=0}^n \sum_{j=0}^m C_n^i \cdot C_m^j \cdot 2^{(n-i)\cdot (m-j)}\cdot (-1)^{i+j}

那么nm列矩阵至少有ab列都是黑色的方案数为:

\sum_{i=a}^n \sum_{j=b}^m C_n^i\cdot C_m^j\cdot f[n-i][m-j]

合并两个式子并将求和符号提至最前可以得到:

\sum_{i=a}^n \sum_{j=b}^m \sum_{u=0}^{n-i} \sum_{v=0}^{m-j} C_n^i\cdot C_m^j\cdot C_{n-i}^u \cdot C_{m-j}^v \cdot 2^{(n-i-u)\cdot (m-j-v)}\cdot (-1)^{u+v}

我们令p=n-i-u, q=n-j-v,同时拆开组合数,那么原式变为:

\sum_{i=a}^n \sum_{j=b}^m \sum_{u=0}^{n-i} \sum_{v=0}^{m-j} \frac{n!}{i!}\frac{m!}{j!}\frac{1}{u!\cdot p!}\frac{1}{v!\cdot q!}\cdot 2^{p\cdot q}\cdot (-1)^{u+v}

将相关的项放在一起:

(n!\cdot m!) \cdot
\sum_{p=0}^{n-a} \sum_{q=0}^{m-b}[
(\frac{2^{p\cdot q}}{p!\cdot q!}) \cdot
(\sum_{u=0}^{n-p-a} \frac{(-1)^u}{i!\cdot u!})\cdot
(\sum_{v=0}^{m-q-b} \frac{(-1)^v}{j!\cdot v!})]

枚举p, q,那么有i+u=n-p, j+v=m-q且满足i\geq a, j\geq b
所以我们预处理pre[s][a],使得

pre[s][a] = \sum_{i=a}^s \frac{(-1)^{s-i}}{i!\cdot (s-i)!}
#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int MAXN=3000+5;
const int MOD=998244353;


int inv[MAXN], fac[MAXN], ifac[MAXN];
int bin[MAXN*MAXN];

int bPart[MAXN][MAXN];
int dPart[MAXN][MAXN];

inline void init(int n){
    bin[0]=1;
    for (int i=1, lim=n*n; i<=lim; ++i) {
        bin[i]=(bin[i-1]+bin[i-1])%MOD;
    }

    inv[1]=fac[0]=ifac[0]=1;
    for (int i=2; i<=n; i++) inv[i]=1LL*(MOD-MOD/i)*inv[MOD%i]%MOD;
    for (int i=1; i<=n; i++) fac[i]=1LL*fac[i-1]*i%MOD, ifac[i]=1LL*ifac[i-1]*inv[i]%MOD;

    for (int i=0; i<=n; i++){
        for (int j=0; j<=n; j++){
            bPart[i][j]=1LL*bin[i*j]*ifac[i]%MOD*ifac[j]%MOD;
        }
    }

    for (int i=0; i<=n; i++){
        for (int j=i; j>=0; j--){
            LL val=1LL*ifac[j]*ifac[i-j]%MOD;
            if ((i-j)&1) val=MOD-val;
            dPart[i][j]=(dPart[i][j+1]+val)%MOD;
        }
    }
}

int main(){
    //freopen("in.txt", "r", stdin);
    init(3001);

    int n, m, a, b;
    while(scanf("%d%d%d%d", &n, &m, &a, &b)!=EOF){
        LL ans=0;
        for (int i=0; i<=n-a; i++){
            for (int j=0; j<=m-b; j++){
                ans=ans+1LL*dPart[n-i][a]*dPart[m-j][b]%MOD*bPart[i][j];
                ans%=MOD;
            }
        }
        printf("%lld\n", ans*fac[n]%MOD*fac[m]%MOD);
    }
    return 0;
}

队友猜出了另一个公式,奈何LL太慢,改成int就过了。

#include <cstdio>
#define LL long long
using namespace std;

const int MAXN=3000+50;
const int MOD=998244353;


int bin[MAXN*MAXN], comb[MAXN][MAXN];
inline void init(int n){
    bin[0]=1; for (int i=1; i<=n*n; i++) bin[i]=(bin[i-1]<<1)%MOD;
    comb[0][0]=1;
    for (int i=1; i<=n; i++){
        comb[i][0]=comb[i][1]=1;
        for (int j=1; j<n; j++) comb[i][j]=(comb[i-1][j]+comb[i-1][j-1])%MOD;
    }
}

LL combA[MAXN], combB[MAXN];
int main(){
    freopen("in.txt", "r", stdin);
    init(3005);
    int n, m, a, b;
    while(scanf("%d%d%d%d", &n, &m, &a, &b)!=EOF){
        LL ans=0;
        for (int i=a; i<=n; i++) combA[i]=1LL*comb[n][i]*comb[i-1][a-1]%MOD;
        for (int j=b; j<=m; j++) combB[j]=1LL*comb[m][j]*comb[j-1][b-1]%MOD;
        for (int i=a; i<=n; i++){
            for (int j=b; j<=m; j++){
                LL tmp=1LL*bin[(n-i)*(m-j)]*combA[i]%MOD*combB[j]%MOD;
                if ((i+j-a-b)&1) tmp=-tmp;
                ans+=tmp;
            }
        }
        ans=ans%MOD+MOD; ans%=MOD;
        printf("%lld\n", ans);
    }
    return 0;
}

HDU 6315 Naive Operations

题意:给定排列B_{1\cdots n},操作允许对A_{l\cdots r}增加一,询问要求\sum_{i=l}^r \lfloor \frac{A_i}{B_i}\rfloor

我们维护答案序列C_i= \lfloor \frac{A_i}{B_i}\rfloor因为B_{1\cdots n}是一个排列,所以我们修改次数为调和级数,是M log M级别的,所以我们只需要给B_{1\cdots n}维护一棵线段树,区间加操作相当于在线段树上区间-1,如果发现线段树上存在位置等于0,则对目标序列C的对应位置+1,并将B为0位置恢复即可。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define PII pair<int, int>
#define mp(x, y) make_pair(x, y)
#define LL long long
using namespace std;

const int MAXN=100000+50;

int n, Q;
int num[MAXN];
LL sum[MAXN];

inline int lowbit(int x){return x&-x;}
inline void add(int x, int v){
    for (int i=x; i<=n; i+=lowbit(i)) sum[i]+=v;
}
inline LL get(int x){
    LL ret=0;
    for (int i=x; i; i-=lowbit(i)) ret+=sum[i];
    return ret;
}

struct Tree{
    int min, tag, idx;
    int left, right;
}tree[MAXN*4];


inline void update(int x){
    if (tree[x].left==tree[x].right) return;
    if (tree[x*2].min<tree[x*2+1].min){
        tree[x].min=tree[x*2].min;
        tree[x].idx=tree[x*2].idx;
    }else{
        tree[x].min=tree[x*2+1].min;
        tree[x].idx=tree[x*2+1].idx;
    }
}

inline void clean(int x){
    if (tree[x].left==tree[x].right) return;
    if (tree[x].tag==0) return;
    int tag=tree[x].tag; tree[x].tag=0;
    tree[x*2].min+=tag; tree[x*2+1].min+=tag;
    tree[x*2].tag+=tag; tree[x*2+1].tag+=tag;
}

void build(int x, int left, int right){
    tree[x].min=tree[x].tag=0;
    tree[x].left=left; tree[x].right=right;
    if (left==right){
        tree[x].min=num[left];
        tree[x].idx=left;
    }else{
        int mid=(left+right)/2;
        build(x*2, left, mid);
        build(x*2+1, mid+1, right);
        update(x);
    }
}

void modify(int x, int left, int right, int v){
    clean(x);
    if (left<=tree[x].left && tree[x].right<=right){
        tree[x].min+=v;
        tree[x].tag+=v;
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        if (left<=mid) modify(x*2, left, right, v);
        if (mid+1<=right) modify(x*2+1, left, right, v);
        update(x);
    }
}

PII query(int x, int left, int right){
    clean(x);
    if (left<=tree[x].left && tree[x].right<=right){
        return mp(tree[x].min, tree[x].idx);
    }else{
        int mid=(tree[x].left+tree[x].right)/2;
        if (right<=mid)
            return query(x*2, left, right);
        else if (mid+1<=left)
            return query(x*2+1, left, right);
        else{
            PII l=query(x*2, left, right), r=query(x*2+1, left, right);
            if (l.first<=r.first) return l; else return r;
        }
    }
}

char op[10];
inline void solve(){
    memset(sum, 0, sizeof(sum));
    build(1, 1, n);
    for (int i=1, l, r; i<=Q; i++){
        scanf("%s%d%d", op, &l, &r);
        if (op[0]=='a'){
            modify(1, l, r, -1);
            PII q=query(1, 1, n);
            while(q.first==0){
                int v=q.first, p=q.second;
                //printf("%d %d\n", v, p);
                add(p, 1); // Add
                modify(1, p, p, num[p]-v); // Recovery
                q=query(1, 1, n); // Query
            }
        }else printf("%lld\n", get(r)-get(l-1));
    }
}

int main(){
    //freopen("in.txt", "r", stdin);
    while(scanf("%d%d", &n, &Q)!=EOF){
        for (int i=1; i<=n; i++) scanf("%d", &num[i]);
        solve();
    }
    return 0;
}

HDU 6318 Swaps and Inversions

题意:有一个序列,你需要对其每个逆序对付出x的代价,也可以花费y的代价修改相邻两个数字的顺序,求最小花费。

因为逆序对数量等于交换相邻两个元素将序列排序的次数,所以答案就是 逆序对数量 \times \min(x, y)

#include <iostream>
#include <cstdio>
#define LL long long

using namespace std;

const int MAXN = 100010;
int a[MAXN], tmp[MAXN];
LL ans;

void Merge(int l,int m,int r)
{
    int i = l;
    int j = m + 1;
    int k = l;
    while(i <= m && j <= r)
    {
        if(a[i] > a[j])
        {
            tmp[k++] = a[j++];
            ans += 1LL*(m - i + 1);
        }
        else
        {
            tmp[k++] = a[i++];
        }
    }
    while(i <= m) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    for(int i=l;i<=r;i++)
        a[i] = tmp[i];
}

void mergesort(int l,int r)
{
    if(l < r)
    {
        int m = (l + r) >> 1;
        mergesort(l,m);
        mergesort(m+1,r);
        Merge(l,m,r);
    }
}

int main() {
    int n, x, y;
    while(scanf("%d%d%d", &n, &x, &y) != EOF) {
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        ans = 0;
        mergesort(1, n);
        printf("%lld\n", 1LL*ans*min(x, y));
    }
}

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

2018 Multi-University Training Contest 2
HDU 6311 Cover 题意:给定一个无向图,求用最少的若干条不相交的路径覆盖图的所有边。 一个欧拉回路的图可以一笔画,所以一定可以只使用一条路径不重不漏覆盖所有边,如果不是欧拉回路…
扫描二维码继续阅读
2018-07-26
<--! http2https -->