2018 Multi-University Training Contest 1

King

A - Maximum Multiple

推一下式子暴力判断即可，范围不会太大。

Code

#include<bits/stdc++.h>
typedef long long ll;
typedef double db;
using namespace std;
int a[15][3]{
        {2,3,6},
        {2,4,4},
        {2,6,3},
        {3,2,6},
        {3,3,3},
        {3,6,2},
        {4,2,4},
        {4,4,2},
        {6,2,3},
        {6,3,2}
};
int t,n;
int main(){
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        cin>>n;
        ll ans=-1;
        for(int i=0;i<10;i++){
            if(n%a[i][0]==0 && n%a[i][1]==0 && n%a[i][2]==0){
                ans = max(ans,(ll)(n/a[i][0])*(n/a[i][1])*(n/a[i][2]));
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

知识兔

B - Balanced Sequence

题意：
给出$n$个串，现在定义“好串”：

空串；
若$A,B$为“好串”，那么$AB$会“好串”；
若$A$为“好串”，那么$(A)$为“好串”。

现在可以对$n$个串的顺序任意排列之后拼接起来，问最长“好串”子序列的长度。

思路：

对于每个串，先处理出合法括号序列记入答案，那么最后每个串都形如$"))))((("$的形式，我们将其记为$(L,R)$，表示左括号和右括号分别有多少个。
接下来考虑怎么安排顺序使得答案最优。
考虑两个的情况，那么答案为$min(L_1,R_2)$及$min(R_1,L_2)$，这时我们按照$min(L_1,R_2)<min(R_1,L_2)$的顺序放置即可。
为什么？

口胡一下自己的理解

对于两个而言，这样肯定最优；假设对于$k$个这样最优，考虑第$k+1$个加进来，此时放在最后面，根据排序规则有，我们假设从后面往前面匹配，假设最后两个多出$($则不用管，否则多出$)$可能会对前面产生贡献；若没有放在最后，而在中间某个位置，它多出来的一些$)$则会对更少的一段产生贡献，并且显然，此时多处来的$)$数目只可能更多，显然不优。

注意一下当$min(L_1,R_2)=min(R_1,L_2)$时，我们要按照$L$从大到小排序，这可以让更多的$L$对后面产生贡献。

详见代码：

Code

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5;

int n;
char s[N];
int sta[N], top;

struct Point{
    int L, R;
    bool operator < (const Point &A)const {
        int p = min(R, A.L), q = min(L, A.R);
        if(p == q) return L > A.L;
        return p < q;
    }
}p[N];

void run() {
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        cin >> s + 1;
        int len = strlen(s + 1);
        int l = 0, r = 0;
        top = 0;
        for(int j = 1; j <= len; j++) {
            if(top && s[sta[top]] == '(' && s[j] == ')') --top, ++ans;
            else sta[++top] = j;
        }
        for(int j = 1; j <= top; j++) {
            if(s[sta[j]] == '(') ++l;
            else ++r;
        }
        p[i] = {l, r};
    }
    sort(p + 1, p + n + 1);
    int l = 0, r = 0;
    for(int i = 1; i <= n; i++) {
        int now = min(l, p[i].R);
        ans += now;
        l = l - now + p[i].L;
    }
    cout << ans * 2 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
#ifdef Local
    freopen("../input.in", "r", stdin);
    freopen("../output.out", "w", stdout);
#endif
    int T; cin >> T;
    while(T--) run();
    return 0;
}

知识兔

C - Triangle Partition

排序每次选左边的就行。

Code

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 3e3 + 5;

struct Point{
    int x, y, id;
    bool operator < (const Point &A) const {
        return x < A.x;
    }
}p[N];
int n;

void run() {
    cin >> n;
    for(int i = 1; i <= 3 * n; i++) {
        cin >> p[i].x >> p[i].y;
        p[i].id = i;
    }
    sort(p + 1, p + 3 * n + 1);
    for(int i = 1; i <= 3 * n; i += 3) {
        cout << p[i].id << ' ' << p[i + 1].id << ' ' << p[i + 2].id << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
#ifdef Local
    freopen("../input.in", "r", stdin);
    freopen("../output.out", "w", stdout);
#endif
    int T; cin >> T;
    while(T--) run();
    return 0;
}

知识兔

D - Distinct Values

题意：
构造字典序最小的序列，满足在给出的区间中数字各不重复。

思路：

对于每个位置，能影响它的区间显然从左端点最远起。
发现随着位置的不断增加，最远位置具有单调性。
那么利用$set$随便搞搞就行了，$set$里面的就插入可以用的数，每次取最小的就行。

比赛的时候写了个权值线段树求区间$mex$的做法，维护所有权值最后出现的最小值就行，然后贪心选权值。还是搞复杂了= =思维还是不够灵活。

Code

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int MAXN = 1e5+5,MAXM = 1e6+5,MOD = 100003,INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const db eps = 1e-9;
#define lson o<<1,l,m
#define rson o<<1|1,m+1,r
#define mid l + ((r-l)>>1)
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define pii pair<int,int>
#define vii vector<pii>
#define vi vector<int>
using namespace std;
struct line{
    int l,r;
    bool operator <(const line &rhs)const{
        return l==rhs.l?r>rhs.r:l<rhs.l;
    }
}a[MAXN];
int t,n,m,ans[MAXN],mn[MAXN<<2];
void build(int o,int l,int r){
    mn[o]=0;
    if(l==r)return ;
    int m=mid;
    build(lson);build(rson);
}
int ask(int o,int l,int r,int L){
    if(l==r)return l;
    int m=mid;
    if(mn[o<<1]<L)return ask(lson,L);
    return ask(rson,L);
}
inline void pushUp(int o){
    mn[o]=min(mn[o<<1],mn[o<<1|1]);
}
void upd(int o,int l,int r,int v,int p){
    if(l==r){
        mn[o]=p;
        return ;
    }
    int m=mid;
    if(v<=m)upd(lson,v,p);
    else upd(rson,v,p);
    pushUp(o);
}
int main(){
    ios::sync_with_stdio(false);
    //freopen("../A.in","r",stdin);
    //freopen("../A.out","w",stdout);
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=m;i++)cin>>a[i].l>>a[i].r;
        sort(a+1,a+1+m);
        build(1,1,n);
        int pre=0;
        for(int i=1;i<=n;i++)ans[i]=1;
        for(int i=1;i<=m;i++){
            if(a[i].r <= pre)continue;
            for(int j=pre+1;j<=a[i].r;j++){
                ans[j] = ask(1,1,n,a[i].l);
                upd(1,1,n,ans[j],j);
            }
            pre=a[i].r;
        }
        for(int i=1;i<=n;i++)cout<<ans[i]<<" \n"[i==n];
    }
    return 0;
}

知识兔

G - Chiaki Sequence Revisited

题意：
定义：
\[a_n=\left\{\begin{aligned}&1&n=1,2\\&a_{n-a_{n-1}}+a_{n-1-{a_{n-2}}}&n > 2\end{aligned}\right.\]
先求$\sum_{i=1}^n{a_i}$，$n\leq 10^{18}$。

思路：
懒得写啦，有博客写得很好：传送门。
找规律的时候想到二进制基本规律就出来了，核心就是找到出现次数的规律就行。
代码有些细节，因为根据规律，$1$只会出现一次，但实际上会出现两次，所以我们将$n$偏移一下即可。另外注意我们找$x$的时候，要找$f(x)\leq a_n$的最大$x$，这里有个等于是为了方便处理数据较小时的情况。
详见代码：

Code

#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5, MOD = 1e9 + 7, inv2 = (MOD + 1) / 2;

ll n;

ll calc(ll k) {
    if(k <= 1) return k;
    return calc(k / 2) + k;
}

void run() {
    cin >> n; --n;
    ll l = n / 2 - 50, r = n / 2 + 50, mid;
    while(l < r) {
        mid = (l + r) >> 1;
        if(calc(mid) > n) r = mid;
        else l = mid + 1;
    }
    ll p = r - 1;
    ll res = (n - calc(p)) % MOD;
    ll ans = 0;
    for(ll d = 1, c = 1; ; d <<= 1, ++c) {
        if(d > p) break;
        ll s = d % MOD;
        ll k = ((p - d) / (2 * d) + 1) % MOD;
        ll e = (s + (k - 1) * 2ll % MOD * d % MOD) % MOD;
        ans = (ans + c * (s + e) % MOD * k % MOD * inv2 % MOD) % MOD;
    }
    ans += (res * ((p + 1) % MOD) % MOD + 1) % MOD;
    ans %= MOD;
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
#ifdef Local
    freopen("../input.in", "r", stdin);
    freopen("../output.out", "w", stdout);
#endif
    int T; cin >> T;
    while(T--) run();
    return 0;
}

知识兔

K - Time Zone

模拟。

Code

#include <bits/stdc++.h>
using namespace std;

template <class T, int z>
struct A{
    T data[z];
    int n;
    A():n(0) {}
    T& operator[](int q) {return data[q];}
    inline void push(T x) {data[n++]=x;}
    inline T& pop() {return data[--n];}
};
char x[10];
int main() {
    int T; scanf("%d", &T);
    while(0<T--) {
        int a,b; scanf("%d%d", &a, &b);
        scanf("%s",x);
        double d; sscanf(x+3,"%lf", &d);
        a-=8; int e=(int)round(d*60);

        a+=e/60,b+=e-(e/60*60);

        while(b>=60) {
            a++,b-=60;
        }
        while(b<0) {
            b+=60,a--;
        }

        while(a>=24) a-=24;
        while(a<0) a+=24;
        printf("%02d:%02d\n", a,b);
    }
    return 0;
}

知识兔

计算机

2022年2月04日

2018 Multi-University Training Contest 1

A - Maximum Multiple

B - Balanced Sequence

C - Triangle Partition

D - Distinct Values

G - Chiaki Sequence Revisited

K - Time Zone

热门标签

最新文章