比赛地址

Vjudge

原2018杭电多校第二场

[C]Cover

题意

给出一个图，求最少需要几笔画。并给出方案。

题解

裸的欧拉路问题。由一笔画转化为几笔画需要一些，在奇数出度的点之间补上一条虚边。求完回路后再按照虚边断开就可以得到方案了。答案为Min(1,\lfloor\frac{cnt}{2}\rfloor)

cnt为奇数出度的点的数量。

代码

[D]Game

题意

给定一个从1到n的数字序列，两个人轮流选数，选中一个数后，把该数的所有因数删去。当一方没有数可选时，另一方获胜。求是否存在必胜策略。

题解

比赛时有人5sAC，震惊到了

假如存在后手必胜策略，则第一个人选1，交换先后手，先手必胜，矛盾。证毕。

代码

略

[G]Naive Operations

题意

给定一个1~n的排列b，维护一个序列a。a初始时全为0.有两种操作，一种是a序列区间加1，第二种是求

\sum_{i=l}^r\lfloor\frac{a_i}{b_i}\rfloor

题解

考虑到b是一个排列，则式子中答案更新总次数不超过nlnn

根据这一性质，可以使用线段树来维护。每个节点维护区间b的最小值，每次区间增加操作将最小值减1.当最小值变为0时说明有个位置对答案的贡献发生了改变，递归到叶子节点更新答案该点最小值变回初始的b值。询问操作直接按常规线段树处理即可。

总时间复杂度为O(qlnnlogn)

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define _ 0
#define N 200010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,q,i,l,r,Ans;
int b[N];
char c[10];

struct Tree{
    int l,r,d,lz,a,b;
}t[N*4];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Maketree(int x,int low,int high){
    int mid=(low+high)>>1;
    t[x].l=low; t[x].r=high;    t[x].d=0;
    if (low==high){
        t[x].b=b[low];  return;
    }
    Maketree(l(x),low,mid); Maketree(r(x),mid+1,high);
    t[x].b=Min(t[l(x)].b,t[r(x)].b);
}

inline void Push(int x){
    int p=t[x].lz;
    if (!p) return;
    t[l(x)].b-=p;   t[r(x)].b-=p;
    t[l(x)].lz+=p;  t[r(x)].lz+=p;
    t[x].lz=0;
}

inline void Add(int x,int low,int high){
    int mid=(t[x].l+t[x].r)>>1;
    if (t[x].l==t[x].r){
        t[x].b--;   if (!t[x].b)    t[x].d++,t[x].b=b[t[x].l];
        return;
    }
    if (t[x].lz)    Push(x);
    if (low==t[x].l&&high==t[x].r){
        t[x].b--;
        if (!t[x].b){
            Add(l(x),low,mid);  Add(r(x),mid+1,high);
            t[x].b=Min(t[l(x)].b,t[r(x)].b);    t[x].d=t[l(x)].d+t[r(x)].d;
        }   else t[x].lz++;
        return;
    }
    if (high<=mid)  Add(l(x),low,high);
    else if (low>mid)   Add(r(x),low,high);
    else Add(l(x),low,mid),Add(r(x),mid+1,high);
    t[x].b=Min(t[l(x)].b,t[r(x)].b);    t[x].d=t[l(x)].d+t[r(x)].d;
}

inline int Query(int x,int low,int high){
    int mid=(t[x].l+t[x].r)>>1;
    if (t[x].l==low&&t[x].r==high)  return t[x].d;
    if (high<=mid)  return Query(l(x),low,high);
    else if (low>mid)   return Query(r(x),low,high);
    else return Query(l(x),low,mid)+Query(r(x),mid+1,high);
}

int main(){
    while (~scanf("%d%d",&n,&q)){
        for (i=1;i<=n;i++)  scanf("%d",&b[i]);
        memset(t,0,sizeof(t));
        Maketree(1,1,n);
        while (q--){
            scanf("%s%d%d",&c,&l,&r);
            if (c[0]=='a')  Add(1,l,r);
            else printf("%d\n",Query(1,l,r));
        }
    }
    return (0^_^0);
}

[J]Swaps and Inversions

题意

有一个序列，每有一个逆序对需付出x代价，交换相邻两数需付出y代价。求一定次数交换后付出代价最小值。

题解

首先，冒泡排序的交换次数就是逆序对个数。所以，对于这个序列，要么不停交换至没有逆序对，要么不交换。答案为逆序对数乘以x,y的最小值。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define N 200010
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,i,a,b,be;
int c[N],d[N];
LL Ans,cnt;

inline int Abs(int x){return (x<0)?-x:x;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Merge(int low,int high){
    int mid=(low+high)>>1,l=0,r=0,e=0;
    if (low==high)  return;
    Merge(low,mid); Merge(mid+1,high);
    l=low;  r=mid+1;    e=low;
    while (l<=mid&&r<=high){
        if (c[l]<=c[r]) d[e++]=c[l++];
        else {
            Ans+=(mid-l+1); d[e++]=c[r++];
        }
    }
    while (l<=mid)  d[e++]=c[l++];
    while (r<=high) d[e++]=c[r++];
    for (i=low;i<=high;i++) c[i]=d[i];
}

int main(){
    while (~scanf("%d%d%d",&n,&a,&b)){
        if (n==1){
            cout<<"0"<<endl;
            continue;
        }
        for (i=1;i<=n;i++)  scanf("%d",&c[i]);
        Ans=0;  Merge(1,n); cnt=Min(a,b);
        cout<<(LL)Ans*cnt<<endl;
    }
    return 0;
}

总结&吐槽

这场比赛发挥不是很好，只做出来了D和J题，没有达到大众的三题(差了G)。G没有做出来的主要原因在我，在尝试使用线段树解决无果后决然转向其他算法，思考了分块，整体二分等等。。。思路越飘越远，没有想到还可以这么维护线段树。C题一开始就明确了一种写法，因为具体实现上的困难一直没有动手。事后想想由一笔画问题转为多笔画问题其实没有那么复杂，思维强度并不大，考场上应该可以想到的。E题是个构造问题，在队友尝试无果后，我给出了一种类似分块的做法。最后证明我的思路是正确的，当时应该调整策略集中想E题，把构造方法再优化一下。可能是暑期刚刚开始的问题，思维能力还没有完全恢复过来，对Ranklist利用也不够充分。希望在接下来的比赛中可以解决这一问题。

暑期集训的日程安排和996感觉没什么区别了QAQ

第一次训练的地点很不好，没有空调，桌子小到摆不下机械键盘，屋里热的不行，坐的久了椅子还黏。。。好在下一场开始集训地变为了新主楼，感谢教练。