2019 Multi-University Training Contest 1

Posted on | Post modified:

2019 Multi-University Training Contest 1（待更新）

Problem 1002

Operation

题意：

一个长度为$n$的字符串$a$,执行下面的操作

$1$ $l$ $r$查询区间内异或的最大值

$0$ $x$ 将$x$放到数组最后一位

输入和输出是强制在线的。。。

思路：

考虑维护一个前缀线性基$f_{ij}$,同时贪心的使线性基的位置尽可能的往右，对于每次的$[l,r]$，查询$[1,r]$的线性基中的位置是否大于等于$l$，然后再贪心的异或得到最大值。

代码:

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<bits/stdc++.h>

using namespace std;
const int N = 1e6+100;
int f[N][36];
int a[N];
int pos[N][36];//[1-i]的第j位的线性基最右边的位置
void Add(int x,int num){
    int now=x;
    for(int j=0;j<=31;j++){//维护前缀
        f[x][j]=f[x-1][j];
        pos[x][j]=pos[x-1][j];
    }
    for(int j=31;j>=0;j--){
        if(num>>j){
            if(f[x][j]){
                if(pos[x][j]<now){
                    swap(pos[x][j],now);
                    swap(f[x][j],num);
                }
                num^=f[x][j];
            }
            else{
                f[x][j]=num;
                pos[x][j]=now;
                break;
            }
        }
    }
}
int main(){
   //freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),Add(i,a[i]);
        int op,l,r,num;
          int ans=0;
        while(m--){
            scanf("%d",&op);
            if(op==0){
                scanf("%d %d",&l,&r);
                l=(l^ans)%n+1;
                r=(r^ans)%n+1;
                if(l>r) swap(l,r);
                ans=0;
                for(int j=31;j>=0;j--){
                    if(pos[r][j]>=l&&ans<(ans^f[r][j])) ans^=f[r][j];
                }
                printf("%d\n",ans);
            }
            else{
                scanf("%d",&num); 
                a[++n]=num;
                a[n]^=ans;
                Add(n,a[n]);
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=0;j<=31;j++){
                f[i][j]=pos[i][j]=0;
            }
        }
    }
    return 0;
}

Problem 1004

Vacation

题意：

有$n$辆车，已知每个车头距离终点的长度和车身长度以及最大速度，计算最后一辆车通过终点的最少时间。

思路：

考虑二分时间$t$，对于每次的时间$t$，计算出如果第$i$辆车没有阻拦的情况下到达的位置，然后由于前面车的限制，递推的计算出$t$时间后最后一辆车的位置。

代码:

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
#include<bits/stdc++.h>

using namespace std;
const int N = 1e6+100;
const double eps=1e-9;
int n;
double l[N],s[N],v[N];
double pos[N];
bool check(double t){
    double p=-100000000;
    for(int i=1;i<=n+1;i++){
        pos[i]=(s[i]+l[i]-t*v[i]);
    }
    for(int i=n+1;i>=2;i--){
        if(pos[i-1]-l[i-1]<pos[i]) pos[i-1]=pos[i]+l[i-1];
    }
    return pos[1]<l[1];
}
int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n+1;i++) scanf("%lf",&l[i]);
        for(int i=1;i<=n+1;i++) scanf("%lf",&s[i]);
        for(int i=1;i<=n+1;i++) scanf("%lf",&v[i]);
        double l=0,r=9999999999;
        for(int i=1;i<=70;i++){
            double mid=(l+r)*0.5;
            if(check(mid)){
                r=mid;
            }
            else l=mid;
        }
        printf("%.6lf\n",r);
    }
    return 0;
}

Problem 1005

Path

题意：

一个有向图，你需要删除边权和最小的一些边使得从$1-n$的最短路增大，求这个边权和

思路：

将所有最短路通过的边建成一个新图$G(V,E)$,然后求$G(V,E)$的最小割

代码：

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include<bits/stdc++.h>

using namespace std;
const long long N = 1e4+100;
const long long INF = 0x3f3f33f3f3f3ff3f;
typedef long long ll;
int n,m;
long long dis[N];
bool vis[N];
vector<pair<int,long long> > Gs[N];
vector<pair<int,long long> > pre[N];
struct MaxFlow{
    const static ll MAX_V = 10002;
    int V;
    struct edge{
        ll to, cap, rev;
    };
    vector<edge> G[MAX_V];
    int level[MAX_V]; 
    int iter[MAX_V];

    void add_edge(ll from, ll to, ll cap){
        G[from].push_back((edge){to, cap, (ll)G[to].size()});
        G[to].push_back((edge){from, 0, (ll)G[from].size()-1});
    } 

    void bfs(int s){
        fill(level, level + V, -1);
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while (!que.empty()){
            int v = que.front();
            que.pop();
            for (int i=0; i< G[v].size(); i++){
                edge& e = G[v][i];
                if (e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }

    ll dfs(int v, int t, ll f){
        if (v == t)
            return f;
        for (int &i = iter[v]; i < G[v].size(); i++){
            edge& e = G[v][i];
            if (e.cap > 0 && level[v] < level[e.to]){
                ll d = dfs(e.to, t, min(f, e.cap));
                if (d > 0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    ll max_flow(ll s, ll t){
        ll flow = 0;
        for (;;){
            bfs(s);
            if(level[t] < 0)
                return flow;
            fill(iter, iter + V, 0);
            ll f;
            while ((f = dfs(s, t, INF)) > 0){
                flow += f;
            }
        }
    }

    void init(int n = 0){
        for (int i = 0; i <= V; i++){
            G[i].clear();
        }
        V = n;
    }
}mf;
struct node{
    int id;
    long long dis;
};
bool operator<(node a,node b){
    return a.dis>b.dis;
}
void dij(int s){
    priority_queue<node> q;
    for(int i=0;i<=n;i++){
        dis[i]=INF;
        vis[i]=0;
    }
    dis[s]=0;
    q.push({s,0});
    while(!q.empty()){
        node rt=q.top();q.pop();
        int u=rt.id;
        if(u==n) return ;
        if(vis[u]) continue;
        vis[u]=1;
        for(auto nxt:Gs[u]){
            int v=nxt.first;
            long long w=nxt.second;
            q.push({v,dis[v]});
            if(dis[v]==dis[u]+w){
                q.push({v,dis[v]});
                pre[v].push_back({u,w});
            }
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({v,dis[v]});
                pre[v].clear();
                pre[v].push_back({u,w});
            }
        }
    }
}
bool check[N];
void dfs(int now){
    if(check[now]) return ;
    if(now==1){
        return ;
    }
    check[now]=1;
    for(auto p:pre[now]){
        int u=p.first;
        long long w=p.second;
        mf.add_edge(u-1,now-1,w);
        dfs(u);
    }
}
int main(){
    //freopen("1.in","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++) check[i]=0;
        mf.init();
        mf.V=n;
        for(int i=1;i<=n;i++) Gs[i].clear(),pre[i].clear();
        int u,v,w;
        for(int i=1;i<=m;i++){
            scanf("%d %d %d",&u,&v,&w);
            Gs[u].push_back({v,w});
        }
        dij(1);
        if(dis[n]==INF){
            puts("0");
        }
        else{
            dfs(n);
            printf("%lld\n",mf.max_flow(0,n-1));
        }
    }
    return 0;
}

Problem 1009

String

题意：

给定一个字符串$S$和$26$个限制条件$[L_i,R_i]$,求一个长度为$k$的子串$t$使得$t$中的第$i$种字母出现的次数都在$[L_i,R_i]$内。

思路：

对字符串$S$构造序列自动机，对于每一位都从’a’到’z’枚举，只要满足条件就加上即可。

代码：

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
#include<bits/stdc++.h>

using namespace std;
const int N = 1e6+100;
const int INF  = 0x3f3f3f3f;
string s;int n,m;int nxt[N][27],sum[N][27];
int num[27];
string ans;
int L[27],R[27];
bool check(int p){
    int nowk=(int)ans.size();//该选第nowk个了
    if(num[s[p]-'a']+1>R[s[p]-'a']) return 0;
    int all=0;
    //num[s[p]-'a']++;//假设可以
    for(int i=0;i<26;i++){
        if(L[i]>num[i]){
            all+=L[i]-num[i];
        }
    }
    if(L[s[p]-'a']>num[s[p]-'a']) all--;
    //cout<<"checking: "<<p<<' '<<all<<' '<<m-nowk<<' '<<ans<<endl;
    if(all>m-nowk-1){
        return 0;
    }
    for(int i=0;i<26;i++){
        if(sum[p][i]+num[i]<L[i]){
            return 0;
        }
    }
    return 1;
}
int main(){
    while(cin>>s>>m){
        n=s.length();
        ans.clear();
        memset(num,0,sizeof(num));
        for(int i=0;i<26;i++) nxt[n][i]=INF,sum[n][i]=0;
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<26;j++){
                nxt[i][j]=nxt[i+1][j];
                sum[i][j]=sum[i+1][j];
            }
            nxt[i][s[i]-'a']=i;
            sum[i][s[i]-'a']++;
        }
        for(int i=0;i<26;i++) cin>>L[i]>>R[i];
        int pos=-1;
        while(ans.size()<=m){
            bool flag=0;
            for(int i=0;i<26;i++){
                if(nxt[pos+1][i]!=INF){//下一个还能选
                    if(check(nxt[pos+1][i])){
                        flag=1;
                        ans+=('a'+i);
                        num[i]++;
                        pos=nxt[pos+1][i];
                        break;
                    }
                }
            }
            if(!flag){
                break;
            }
        }
        if(ans.length()==m){
            cout<<ans<<endl;
        }
        else{
            cout<<-1<<endl;
        }
    }
    return 0;
}