2018 Multi-University Training hdu Contest 1

Posted on | In , | Visitors:

嚯嚯嚯！补题！

hdu多校总链接

补题： 7/11

  • 莫队
  • 线段树
  • 笛卡尔树
  • 精度
  • 优先队列
  • lowbit
  • __builtin_ctz(i)+1
  • __builtin_ffs(n)
  • __builtin_popcount(n)
  • _builtin_parity(n)

A. Maximum Multiple

找规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    int T;
    scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);
        if(n%3==0){
            printf("%lld\n",1LL*(n/3)*(n/3)*(n/3));
        }else if(n%4==0){
            printf("%lld\n",1LL*(n/4)*(n/4)*(n/2));
        }else{
            printf("-1\n");
        }
    }
    return 0;
}

B. Balanced Sequence

首先删除每一个子串中已经配对的，因为不管怎么排序，他们在计算的时候还可以凑对

这样，我们可以想象到，只剩下三种情况了

1
2
3
1. ((((((
2. ))))))
3. )))))(((((

很明显的，我们需要将1往左边放置，将2往右边放置

至于3的话，我们应该尽可能让其配对，假设有括号）有n个，左括号有m个

若左括号多于右括号，我们应该往左边放置，相当于丢弃右括号

若右括号多于左括号，我们应该往右边放置，相当于丢弃左括号

那在这些分类中的排序又是如何呢，首先我们应该少放弃括号，

所以对于第一种情况，m-n值小的，即右括号多的往右放

对于第二种情况，n-m值小的，即左括号多的往左放

综上所述

按照n-m的值按从小到大放置即可了

偷偷说一声，这主播的声音好好听呐！

这里如果用我们的n-m则会TLE，但若是分类讨论，则过了

是因为计算要先算出两边变量，然后再比较，所以即会浪费内存，又会浪费时间吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
char s[maxn];
int tot;
ll ans;
struct ty{
    int left,right;
    bool operator <(const ty& other) const{
        //TLE
        //return right-left<=other.right-other.left;
        if(left<=right&&other.left>other.right) return false;
        if(left>right&&other.left<=other.right) return true;
        if(right>=left&&other.right>=other.left) return left>other.left;
        return right<other.right;
    }
}Seq[maxn];
void init(){
    int len=strlen(s);
    int l=0,r=0;
    for(int i=0;i<len;i++){
        if(s[i]=='('){
            l++;
        }
        else{
            if(!l){
                r++;
            }
            else{
                l--; ans+=2;
            }
        }
    }
    Seq[tot].left=l;Seq[tot].right=r;
    tot++;
}
int main(){
    int T;scanf("%d",&T);
    int n;
    while(T--){
        scanf("%d",&n);
        tot=0;ans=0;
        for(int i=1;i<=n;i++){
            scanf("%s",s);
            init();
        }
        sort(Seq,Seq+tot);
//        for(int i=0;i<tot;i++){
//            cout<<Seq[i].left<<" "<<Seq[i].right<<endl;
//        }
        int l=0;
        for(int i=0;i<tot;i++){
            int tmp=Seq[i].right-l;
            if(tmp>=0){
                ans+=2*l;
                l=0;
            }else{
                ans+=2*Seq[i].right;
                l-=Seq[i].right;
            }
            l+=Seq[i].left;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

C.Triangle Partition

水题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct ty{
    int x,y,no;
}Node[3005];
bool cmp(ty a,ty b){
    return a.x<b.x;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);
        for(int i=0;i<3*n;i++){
            scanf("%d %d",&Node[i].x,&Node[i].y);
            Node[i].no=i+1;
        }
        sort(Node,Node+3*n,cmp);
        for(int i=0;i<3*n;i++){
            if(i%3==2){
                cout<<Node[i].no<<endl;
            }else{
                cout<<Node[i].no<<" ";
            }
        }
    }
    return 0;
}

D. Distinct Values

转换为求Mex(l,r) ，即求的是[l,r]区间内所有数的集合里没有出现过的最小的数字

网上对此求Mex有三种解法：

  • 莫队

假设cnt[]已经记录了[l , r]中每种数字出现的次数，mex已经记录了[l , r]的mex值。

  • 得到[l+1 ,r]或[l , r-1]的mex值。

    对于[l+1 , r]，如果A_l在[l+1 , r]出现过，那么mex不变。

    反之，mex变为mex 与Ai 的较小值。

  • 得到[l-1 ,r]或[l , r+1]的mex值。

    对于[l-1 , r]，如果A_(l-1) 在[l , r]出现过，那么mex不变。

    反之，暴力枚举比mex大的数，更新mex。[l , r+1]同理。

345,mex为1，如果新加的数是2，那么mex应该不会变

莫队还要再研究一下，到时候写一些题目，大概感觉一下

毕竟线段树不会写了！

  • 线段树

    提前计算 Mi = mex(1, i) , 1<=i<=n .

    通过 mex(l, r) 可以得到 mex(l+1, r)

    从被执行 mex 操作的 A[l, r] 中删去一个 A[l] 对整体的影响

    先算一下与 A[l] 相等的数在序列中的位置，记为 next[l] （如果没有这样的数则 next[l] = n+1）

    受影响的区间是 M[l+1, next[l]-1]

    对于其中任意一个下标 t

    M[t] < A[l] ,M[t]并不受影响

    M[t] > A[l] ,M[t]变为A[l]

    M[t] = A[l] ,显然不可能呀

    即M[t] = min(M[t], A[l])

  • dp

对于此题代码：

  • 类似于莫队的算法

    先对区间排序，应该是每一种算法必要的

    先将所有的数字放入，然后对于这个区间从set中拿数字（注意，set本质是红黑树，所以从头取出的数字就是最小的，然后将此元素剔除）；对于一个区间完成后，在进行下一区间的时候，先将不属于此区间，但是在上一区间的数放回到set中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <cstring>
using namespace std;
const int maxn=1e5+10;
struct ty{
    int l,r;
}Node[maxn];
bool cmp(ty a,ty b){
    if(a.l==b.l)
        return a.r>b.r;
    return a.l<b.l;
}
int a[maxn],n,m;
set<int>s;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        memset(a,0,sizeof(a));
        for(int i=1;i<=m;i++)
            scanf("%d%d",&Node[i].l,&Node[i].r);
        sort(Node+1, Node+1+m, cmp);
        s.clear();
        for(int i=1;i<=n;i++)
            s.insert(i);
        int l=1,r=0;
        for(int i=1;i<=m;i++){
            while(l<Node[i].l){
                if(a[l]!=0)
                    s.insert(a[l]);
                else a[l]=1;
                l++;
            }
            while(r<Node[i].r){
                r++;
                if(!a[r]){
                    a[r]=*s.begin();
                    s.erase(a[r]);
                }
            }
        }
        while(r<n) a[++r]=1;
        printf("%d",a[1]);
        for(int i=2;i<=n;i++)
            printf(" %d",a[i]);
        printf("\n");
    }
    return 0;
}
  • 优先队列

其实本质上来说是类似的，只不过存储的数据结构不同而已，下面代码是从网上找到的，据说优先队列比set的代码要快！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
int a[100005];
struct node
{
    int date;
    bool operator<(const node &aa)const
    {
        return date>aa.date;
    }
};
priority_queue<node>q;
struct line
{
    int u,to;
    bool operator<(const line &aa)
    {
        if(u!=aa.u)
            return u<aa.u;
        return to<aa.to;
    }
}v[200005];
int main()
{
    int t,i,j,str,n,m,l;
    node now;
    scanf("%d",&t);
    while(t--)
    {
        while(!q.empty())
        {
            q.pop();
        }
        scanf("%d%d",&n,&m);
        str=1;
        for(i=0;i<m;i++)
            scanf("%d%d",&v[i].u,&v[i].to);
        for(j=i,i=1;i<=n;i++,j++)
            v[j].u=v[j].to=i;
        m=j;
        sort(v,v+m);
        for(i=0,j=0,l=0;i<m&&j<n;i++)
        {
            // printf("aaaa %d %d\n",l,v[i].u);
            while(l<v[i].u-1)
            {
                now.date=a[l];
                q.push(now);
                l++;
            }
            while(j<v[i].to)
            {
                if(q.empty())
                {
                    //printf("ssss  %d %d\n",j,str);
                    a[j++]=str;
                    str++;
                }
                else
                {
                    //printf("ok  %d %d\n",j,str);
                    now=q.top();
                    a[j++]=now.date;
                    q.pop();
                }
            }
            
        }
        printf("%d",a[0]);
        for(i=1;i<n;i++)
            printf(" %d",a[i]);
        printf("\n");
        
    }
}

G.Chiaki Sequence Revisited

打表代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int>v;
int main(){
    v.push_back(-1);
    v.push_back(1);
    v.push_back(1);
    cout<<"1: 1"<<endl;
    cout<<"2: 1"<<endl;
    for(int i=3;i<=20;i++){
//        cout<<"     "<<v[i-1]<<" "<<i-v[i-1]<<" "<<v[i-v[i-1]]<<endl;
//        cout<<"     "<<v[i-2]<<" "<<i-1-v[i-2]<<" "<<v[i-1-v[i-2]]<<endl;
//        cout<<i<<": "<<i-v[i-1]<<" + "<<i-1-v[i-2]<<endl;
        v.push_back(v[i-v[i-1]]+v[i-1-v[i-2]]);
    }
    for(int i=1;i<=20;i++){
        cout<<i<<" "<<v[i]<<endl;
    }
    return 0;
}

出现的次数倒是挺有规律的

然后，不想想了，百度（嘿嘿！

除去1

出现1次的：3，5，7，9，11，13…… 公差为2的等差数列

出现2次的：2 ，6，10，14，18……. 公差为4的等差数列

出现3次的：4，12，20，28，36…… 公差为8的等差数列

出现4次的：8 ，24，40，56，72….. 公差为16的等差数列

可得出x出现的次数为2进制形式最后一个1在从右往左数第几位（偷偷嘟囔一句，可怕！

不不不，数学很牛！

所以x出现的次数是1+log2lowbit(x)次

lowbit(i) = max{k+1| 2^k|i}

__builtin_ctz(i)+1 该函数判断n的二进制末尾后面0的个数，当n为0时，和n的类型有关

__builtin_ffs(n)该函数判断n的二进制末尾最后一个1的位置，从一开始

__builtin_popcount(n)该函数时判断n的二进制中有多少个1

__builtin_parity(n) 该函数是判断n的二进制中1的个数的奇偶性，奇数个输出1

据说可以推导前缀和，我就不想推了，emmm……

然而官方题解，让我觉得我看的不是同一道题

考虑这个数列的差分数列，除了个别项，本质就是：1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,…。

可以观测到，这个序列可以这么生成：一开始只有一个1，1变成110，0保持不变。迭代无穷多次后就是这个差分序列。

知道差分序列，可以应用阿贝尔变换，把aa的前缀和搞成差分序列相关。不妨令差分序列是da，那么a的前缀和

$\displaystyle s(n)=(n-1)\sum^{n-2}_{i=0}da(i)-\sum^{n-2}_{i=0}da(i)i+1$

都是网上的代码！（看起来短的应该都很厉害吧！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
const int mod = 1e9+7;
const int N = 105;
ll a[N], f[N];
int main()
{
    int t;
    ll pos, ans, n, m, num, now;
    scanf("%d", &t);
    a[0] = f[0] = 1;///a[i]对应f[i],idx->val
    for(int i=1; i<=62; i++){///ll -> 2^64
        a[i] = a[i-1]*2+1;
        f[i] = f[i-1]*2;
    }
    ll inv = (mod+1)/2;///2的逆元
    while(t --){
        pos = ans = num = 0;
        scanf("%lld", &n);
        m = n;
        for(int i=62; i>=0; i--){
            if(m-a[i] >= 0){
                m -= a[i];
                pos += (1ll<<i);
            }
        }
        pos += (m>0);///当前这位数字是多少
        now = pos-1;///对当前数值之前的数处理,例pos=8,处理1~now这些数的和
        ll s, step, e, sum;
        for(int i=1; f[i-1]<=now; i++){
            s = f[i-1];
            step = (now-s)/f[i]+1;///项数
            e = (step-1)*f[i]+s;///f[i]公差
            sum = (s+e)%mod*(step%mod)%mod*inv%mod;///(start+end)*step/2
            ans = (ans+sum*i%mod)%mod;///i这些数出现了几次
            num += step*i;///算了多少个数
        }
        ans = (ans+1+(n-num-1)%mod*(pos%mod)%mod)%mod;///加上第一个数和其余未加的数
        printf("%lld\n", ans);
    }
}
/*
[HDU6304][数学] 
Chiaki Sequence Revisited
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 1e9+7;
const int inv2 = 500000004;
int T;
LL n;
LL calc(LL n) {
    if(n<=1) return n;
    else return calc(n/2)+n;
}
void solve() {
    LL l=n/2-30,r=n/2+30,m,p=-1;
    //需要预先估计上下界减少二分次数,否则会TLE.
    while(l<=r) {
        m = (l+r)/2;
        if(calc(m)>n) r=m-1;
        else l=m+1,p=m;
    }
    LL rest = ((n - calc(p))%MOD+MOD)%MOD;
    LL ans = 0, s, t, e, k, c=1, x, y;
    for(LL i=1;; i<<=1,c++) {
        if(i>p) break;
        x = i%MOD;
        y = 2*i%MOD;
        s = x;
        k = ((p-i)/(2*i)+1)%MOD;
        e = (y*(k-1)%MOD+i)%MOD;
        ans = (ans+c*(s+e)%MOD*k%MOD*inv2%MOD)%MOD;
    }
    ans = (ans + rest*((p+1)%MOD)%MOD)%MOD;
    printf("%lld\n",ans+1);
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%lld",&n);
        n--; //偏移一项
        solve();
    }
    return 0;
}

H. RMQ Similar Sequence

两种解法：

  • 分治

    • 如果询问的区间如果覆盖了最大数，那么rmq一定是确定的
    • 将所有的概率相乘，并乘以n/2，就是最后的期望。
    • 网上看到一个代码，自行验证

  • 笛卡尔树

    笛卡尔树是一棵二叉树，树的每个节点有两个值，一个为key，一个为value。光看key的话，笛卡尔树是一棵二叉搜索树，每个节点的左子树的key都比它小，右子树都比它大；光看value的话，笛卡尔树有点类似堆，根节点的value是最小（或者最大）的，每个节点的value都比它的子树要小（或者大）。

网上有很多笛卡尔树的模版，其实就是一个build函数

满足这个条件的概率是1/子树节点数，然后满足条件的前提下由于可以随机取，所以权重的期望都是n/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+10;
int a[maxn],l[maxn],r[maxn],size[maxn];
int n,root;
ll inv[maxn];
ll ans;
stack<int>s;
void dfs(int x){
    size[x]=1;
    if(l[x]){
        dfs(l[x]);
        size[x]+=size[l[x]];
    }
    if(r[x]){
        dfs(r[x]);
        size[x]+=size[r[x]];
    }
    ans*=inv[size[x]];ans%=mod;
}
void init(){
    inv[1]=1;
    for(int i=2;i<=1000000;i++){
        inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    }
}
void build(){
    for(int i=1;i<=n;i++){
            while(!s.empty()&&a[i]>a[s.top()]){
                l[i]=s.top();
                s.pop();
            }
            if(!s.empty()) r[s.top()]=i;
            s.push(i);
        }
}
int main(){
    init();
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        ans=n*inv[2]%mod;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            l[i]=r[i]=0;
        }
        build();
        
        while(!s.empty()){
            root=s.top();
            s.pop();
        }
        
        dfs(root);
        printf("%lld\n",ans);
    }
    return 0;
}

K. Time Zone

精度问题，很重要哦！！！但怎么看出来这里有精度问题的呢！

网上看到这样一段话

  • ICPC题目输出有个不成文的规定(有时也成文)，不要输出: -0.000

    那我们首先要弄清，什么时候按printf(“%.3lf\n”, a)输出会出现这个结果。

    直接给出结果好了：a∈(-0.000499999……, -0.000……1)

    所以，如果你发现a落在这个范围内，请直接输出0.000。更保险的做法是用sprintf直接判断输出结果是不是-0.000再予处理。

    典型案例:UVA746

  • unisgned long long输出是%llu

打算看看这个UVA 746

但是这里的还是很奇怪呢！！！！！

看直播说是读入小数就会有误差？？？！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//my
#include<cstdio>
#define eps 1e-10
int main(){
    int t,a,b;
    double d;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d UTC%lf",&a,&b,&d);
        int sum=a*60+b-8*60;
        if(d>0)
            sum+=(int)(d*60+eps);
        else
            sum+=(int)(d*60-eps);
        sum%=24*60;
        if(sum<0)
            sum+=24*60;
        printf("%02d:%02d\n",sum/60,sum%60);
    }
    return 0;
}
//这里的ssanf很重要
#include <bits/stdc++.h>
#define eps 1e-10
using namespace std;
double d;
int t, h, m, c, sign;
char s[20];
int main() {
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%s", &h, &m, s);
        h = h * 60 + m;
        sign = s[3] == '+' ? 1 : -1;
        sscanf(s + 4, "%lf", &d);
        c = (int)(d * 60+eps);//注意浮点误差
        c = sign * c- 8 * 60;
        h += c;
        h %= (24 * 60);
        if (h < 0) h += 24 * 60;
        printf("%02d:%02d\n", h / 60, h % 60);
    }
    return 0;
}

碎碎念

2018.08.07 日

当当当！

偷偷嘀咕一下，实验室里的聚聚们，好恐怖呀！

（幸好不熟 总有种遇到老师的感觉，哎！好像还是怕老师呢！

强大到让我无法吱声，（气场好可怕） 我还是对着我的小电脑，哼哧哼哧，补题吧！

幸好我近视，看不见他们，都是小南瓜！南瓜！

为什么学校的奶茶店都不关门呀！神奇！

2018.08.07 晚

唔……发现每场补的题好少啊！应该多学一点东西的，所以未完待续！果然，是累的，晚安！

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽