multi-university contest1

ACM

多校第一场

dls’s codes

sscanf的用法

相当于一个正则表达式，

1002 balanced sequence

题解

先预处理每一个串，然后贪心的去取就行了
感觉每一次都不能有巧妙的方法去预处理一些东西简化问题
题解

定义比较函数的时候遇到了坑。
注意不要添加多余的等号。
a == b return false, 不是return true;
然后注意减少比较的状态，否则会超时

ac code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
string raw[maxn];
int n;
struct Node{
    int l, r;
}node[maxn];
bool cmp(Node a, Node b){
    if(a.l>=a.r&&b.l<b.r) return true;
    if(a.l<a.r&&b.l>=b.r) return false;
    if(a.l>=a.r&&b.l>=b.r) return a.r<b.r;
    return a.l>b.l;
}
int main()
{
    int t;
    ios::sync_with_stdio(false);
    //freopen("1002.in", "r", stdin);
    //freopen("1002.out", "w", stdout);
    cin>>t;
    while(t--){
        cin>>n;
        int ans = 0;
        //for(int i=0; i<n; i++) raw[i].clear();
        for(int i=0; i<n; i++) cin>>raw[i];
        for(int i=0; i<n; i++){
            stack<char> s;
            while(!s.empty()) s.pop();
            for(int j=0; j<raw[i].length(); j++){
                if(raw[i][j] == ')'){
                    if(!s.empty()&&s.top() == '('){
                        ans += 2;
                        s.pop();
                    }
                    else s.push(raw[i][j]);
                }
                else s.push('(');
            }
            int r, l;
            l = r = 0;
            while(!s.empty()){
                char  temp;
                temp = s.top(), s.pop();
                if(temp == ')') r++;
                else l++;
            }
            node[i].l = l, node[i].r = r;
        }
        sort(node, node+n, cmp);
        int nl = 0;
        for(int i=0; i<n; i++){
            if(nl<=node[i].r){
                ans += 2*nl;
                nl = 0;
                nl += node[i].l;
            }
            else{
                ans += 2*node[i].r;
                nl -= node[i].r;
                nl += node[i].l;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

1004

一类区间覆盖问题，quality说他做了10遍以上？看来经验还是不够啊qaq

题解

神仙怎么做的都有，，，类似于一类求mex的问题， mex可以用set, pq来维护

这个转移写的有点巧妙啊，一开始没有被覆盖的地方用长为1的区间来覆盖orz

ac code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int n, m;
typedef pair<int, int> pii;
typedef long long ll;
int ans[maxn];
#define mp make_pair
bool cmp(pii a, pii b){
    if(a.first!=b.first) return a.first<b.first;
    else return a.second<b.second;
}
int main(){
    ios::sync_with_stdio(false);
    //freopen("1004.in", "r", stdin);
    //freopen("10041.out", "w", stdout);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        vector<pii> a;
        int u, v;
        for(int i=0; i<m; i++){
            cin>>u>>v;
            a.push_back(mp(u, v));
        }
        for(int i=1; i<=n; i++) a.push_back(mp(i, i));
        int l=1, r=1;
        priority_queue<int, vector<int>, greater<int> >pq;
        for(int i=1; i<=n; i++) pq.push(i);
        int sz = a.size();
        sort(a.begin(), a.end(), cmp);
        for(int i=0; i<a.size(); i++){
            while(l<a[i].first){
                pq.push(ans[l++]);
            }
            while(r<=a[i].second) ans[r++]=pq.top(), pq.pop();
        }
        for(int i=1; i<n; i++){
            if(ans[i])
                cout<<ans[i]<<" ";
            else cout<<1<<" ";
        }
        cout<< (ans[n]==0?1:ans[n]) <<endl;
    }
    return 0;
}
/*
4
8 3
1 3
3 6
4 8
*/

1007

题解

(1, 3, 5, 7 …)·1
(2, 6, 10, 14 …)·2
(4, 12, 20, 28 …)·3
(8, 24, 40, 56 …)·4
…

题解
就是这样分块的去求就行了
我好想不擅长做这样的题目，智商不够啊emmm

ac code

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
#include<stdio.h>
#include<iostream>
using namespace std;
#define mod 1000000007
typedef long long ll;
ll a[105],f[105];
int main()
{
    ll T;
    scanf("%lld",&T);
    a[0]=f[0]=1;
    for(ll i=1;i<=62;i++)a[i]=a[i-1]*2+1,f[i]=f[i-1]*2;
    //2的逆元,后面等差数列求和要用
    ll inv=(mod+1)/2;
    while(T--)
    {
        ll pos=0,n,m,ma=-1,ans=0;
        scanf("%lld",&n);
        m=n;
        for(ll i=62;i>=0;i--)
            if(m-a[i]>=0)
                m-=a[i],pos=pos+(1ll<<i);
        pos+=(m>0);
        //cout<<pos<<endl;
        ll now=pos-1,num=0;
        //cout<<now<<endl;
        //分块求和
        for(ll i=1;f[i-1]<=now;i++)
        {
            ll s=f[i-1],step=(now-s)/f[i]+1,e=(step-1)*f[i]+s;
            ll haha=(s+e)%mod*(step%mod)%mod*inv%mod;
            ans=(ans+haha*i%mod)%mod;
            num+=step*i;
        }
        //cout<<ans<<endl;
        //最后剩下的数字肯定是同一个数
        ans=(ans+1+(n-num-1)%mod*(pos%mod)%mod)%mod;
        //cout<<n-num-1<<" "<<pos<<endl;
        printf("%lld\n",ans);
    }
}

1011 time zone

转化成分钟来做比较的简单，我又直接来做，导致问题复杂化了

RMQ similar sequence

学习一种新的数据结构–笛卡尔树

它有如下的性质：
1.树中的元素满足二叉搜索树性质，要求按照中序遍历得到的序列为原数组序列(左儿子的key值小于自己，右儿子的key值大于自己)。

2.树中节点满足堆性质，节点的val值要大于其左右子节点的val值。

题解

题解链接

ac code

因为有除法，所以要求逆元

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
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX = 1e6+10;
const ll mod = 1e9+7;
int l[MAX], r[MAX], vis[MAX], stk[MAX], inv[MAX], siz[MAX];
int n;
ll a[MAX];
 //建笛卡尔树模板，返回的是树的根节点下标
int build() {
    int top = 0;
    for(int i=1;i<=n;i++) l[i] = r[i] = vis[i] = 0;
    for(int i=1;i<=n;i++){
        int k = top;
        while(k > 0 && a[stk[k - 1]] < a[i]) --k;
        if(k) r[stk[k-1]] = i;
        if(k<top) l[i] = stk[k];
        stk[k++] = i;
        top = k;
    }
    for(int i=1;i<=n;i++) vis[l[i]] = vis[r[i]] = 1;
    int ret = 0;
    for(int i=1;i<=n;i++) if(vis[i] == 0) ret = i;
    return ret;
}
void dfs(int root)
{
    siz[root]=1;
    if(l[root]){
        dfs(l[root]);
        siz[root]+=siz[l[root]];
    }
    if(r[root]){
        dfs(r[root]);
        siz[root]+=siz[r[root]];
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    //求逆元模板
    inv[1]=1;
    for(int i=2;i<MAX;i++)
        inv[i] = 1LL * inv[mod%i]*(mod-mod/i)%mod;
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        int root=build();
        for(int i=0;i<=n;i++)
            siz[i]=0;
        dfs(root);
        ll ans=1;
        for(int i=1;i<=n;i++)
            ans=ans*inv[siz[i]]%mod;
        ans=(ans*n)%mod*inv[2]%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

未解决的问题

本文标题:multi-university contest1

文章作者:Babydragon

发布时间:2018-07-23, 18:25:00

最后更新:2018-08-05, 11:58:19

原始链接:http://baolintian.github.io/2018/07/23/multi-university-contest1/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. sscanf的用法
  2. 2. 1002 balanced sequence
    1. 2.1. 题解
    2. 2.2. ac code
  3. 3. 1004
    1. 3.1. 题解
    2. 3.2. ac code
  4. 4. 1007
    1. 4.1. 题解
    2. 4.2. ac code
  5. 5. 1011 time zone
  6. 6. RMQ similar sequence
    1. 6.1. 题解
    2. 6.2. ac code
  7. 7. 未解决的问题
{{ live2d() }}