2018 多校1

苟有恒，何必三更眠五更起;最无益，莫过于一日曝十日寒

简介

虽然是去年打过的比赛了,但是由于自己太弱,再次重温一下,打算将过题人数超过100(以vj回放上的统计数据为准,即当场的比赛)的题目补一下.

1561446448117

A. Maximum Multiple

Problem Description

Given an integer n, Chiaki would like to find three positive integers x, y and z such that: n=x+y+z, x∣n, y∣n, z∣n and xyz is maximum.

Input

There are multiple test cases. The first line of input contains an integer T (1≤T≤10^6), indicating the number of test cases. For each test case: The first line contains an integer n (1≤n≤10^6).

Output

For each test case, output an integer denoting the maximum xyz. If there no such integers, output −1 instead.

Sample Input

Sample Output

-1
-1
1

解析

题意是说n=x+y+z, x∣n, y∣n, z∣n and xyz is maximum这题初看确实没有思路.

先设n = ax = by = cz ,然后xyz == (n^3 /(a*b*c)) 我们只需要求出a,,b,c即可.最开始做的时候思路就在这断了,然后经过题解的提示,打表了一下1/a +1/b + 1/c == 1,才发现,满足条件的整数a,b,c并没有很多!

打表过程略去不表,最后满足条件的只有三组2,4,4 3,3,3 2,3,6 .第一组对应的情况是n%4==0 第二种情况对应的是n%3==0 第三种情况对应的是n%6==0.

然后我们发现,如果第三种情况满足,则第二种情况也一定满足,然后对于相同的n来说,第二组数据得到的结果比第三组数据大(看前文xyz的表达式) ,所以第三组没有存在的必要了(其实这一步优化意义不大,并不会影响整体复杂度),我们只需要判断是否属于第一组和第二组即可.

问题就被简化成了:如果n%4==0 ,尝试一下第一种分组,如果n%3==0 ,尝试第二种分组,两者去最大值即可.

AC代码

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<long long,long long>
#define sc scanf
#define pr printf
using namespace std;

int main() {
    int t;
    sc("%d",&t);
    while(t--){
        ll n;
        sc("%lld",&n);
        if(n%3==0){
            pr("%lld",n*n*n/(27));
        }else if(n%4==0){
            pr("%lld",n*n*n/(32));
        }else{
            pr("-1");
        }
        puts("");
    }

    return 0;
}

B. Balanced Sequence(未完全理解)

Problem Description

Chiaki has n strings s1,s2,…,sn consisting of ‘(‘ and ‘)’. A string of this type is said to be balanced:

+ if it is the empty string + if A and B are balanced, AB is balanced, + if A is balanced, (A) is balanced.

Chiaki can reorder the strings and then concatenate them get a new string t. Let f(t) be the length of the longest balanced subsequence (not necessary continuous) of t. Chiaki would like to know the maximum value of f(t) for all possible t.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case: The first line contains an integer n (1≤n≤10^5) – the number of strings. Each of the next n lines contains a string si (1≤|si|≤10^5) consisting of (' and )’. It is guaranteed that the sum of all |si| does not exceeds 5×10^6.

Output

For each test case, output an integer denoting the answer.

Sample Input

2
1
)()(()(
2
)
)(

Sample Output

4
2

### 解析

简述一下题意: 给你n个括号序列,你不能改变他们内容,但是可以改变他们的次序,改变他们的次序,然后用它们拼成一个长串(必须所有的都要利用上) , 使得这个长串存在一个子序列,子序列是一个 balanced sequence ,输出这个子序列长度的最大值.

首先读题就可以发现,我们先对这些序列预处理,如果单个字符串内部有配对的,就将其直接加入答案,在原来的序列中删掉.这样的处理过后,所有的字符串一定是前面是连续的右括号(也可能没有),后面是连续的左括号(也可能没有).

然后我们的问题就转化成了如何处理这些字符串(顺便一提,这样的话就没必要存储字符串了,只需要存其左右括号的个数即可)

排序的原则就是使尽量多的括号配对,也就是左括号尽量向前聚集,右括号尽量向后聚集.但说归说,到底该以什么原则呢?

右括号少的在前,如果右括号一样多,则左括号多的在前: 反例:)) ))))(( 这是根据假设的排序方式,显然将其倒过来能够有更多配对

左括号多的在前,如果左括号一样多,则右括号少的在前: 反例:))))((( ( 同样也是,翻转之后,有更多配对.

那怎么办?

根据题解 , 我发现了这种排序方式: 先将刚才的字符串分类

左括号多于右括号
左括号等于右括号
左括号小于右括号

然后将他们内部排序之后,以这种顺序组合成最后的数组.能达到效果最大化. (虽然我觉得好有道理,但是确实不明白这样做一定是最优解的理由 = =)

(在网上搜索了这样排序的理由,大多也是玄学)

对于1,左括号全都多于右括号, 优先将右括号少的放在前面,如果右括号数量相同,则左括号多的放在前面.

对于2,左括号等于右括号,那就没有什么讲究了,反正不会影响什么(真的吗?)

对于3,左括号小于右括号,优先将左括号多的排在前面,相同的右括号少的排在后面

AC代码

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
// #define pii pair<long long,long long>
#define mp make_pair
#define sc scanf
#define pr printf
using namespace std;
struct mynode {
    int a,b; // a left
};
char str[100000+100];
mynode s[100000+100];
bool cmp(mynode &a,mynode &b) {
    if(a.b!=b.b) {
        return a.b<b.b;
    }
    return a.a>b.a;
}
bool cmp3(mynode &a,mynode &b) {
    if(a.a!=b.a) {
        return a.a>b.a;
    }
    return a.b<b.b;
}

vector<mynode> v1,v2,v3,v;
int main() {
    int t;
    sc("%d",&t);
    while(t--) {
        v1.clear(),v2.clear(),v3.clear(),v.clear();
        int n;
        sc("%d",&n);
        ll ans=0;
        for(int i=0; i<n; ++i) {
            sc("%s",str);
            int len = strlen(str);
            int l=0;
            int r=0;
            for(int i=0; i<len; ++i) {
                if(str[i]=='(') {
                    ++l;
                } else {
                    if(l>0) {
                        --l;
                        ans+=2;
                    } else {
                        ++r;
                    }
                }
            }
            mynode tmp;
            tmp.a=l,tmp.b=r;
            if(l>r) {
                v1.pb(tmp);
            } else if (l==r) {
                v2.pb(tmp);
            } else {
                v3.pb(tmp);
            }
        }
        sort(v1.begin(),v1.end(),cmp);
        sort(v2.begin(),v2.end(),cmp);
        sort(v3.begin(),v3.end(),cmp3);
        for(auto it: v1) {
            v.pb(it);
        }
        for(auto it: v2) {
            v.pb(it);
        }
        for(auto it: v3) {
            v.pb(it);
        }
        int left=0,right=0;
        for(int i=0; i<n; ++i) {
            int pipei=min(left,v[i].b);
            ans+=2*pipei;
            left-=pipei;
            left+=v[i].a;
        }
        pr("%lld\n",ans);
    }
    return 0;
}

C. Triangle Partition

Problem Description

Chiaki has 3n points p1,p2,…,p3n. It is guaranteed that no three points are collinear. Chiaki would like to construct n disjoint triangles where each vertex comes from the 3n points.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case: The first line contains an integer n (1≤n≤1000) – the number of triangle to construct. Each of the next 3n lines contains two integers xi and yi (−109≤xi,yi≤109). It is guaranteed that the sum of all n does not exceed 10000.

Output

For each test case, output n lines contain three integers ai,bi,ci (1≤ai,bi,ci≤3n) each denoting the indices of points the i-th triangle use. If there are multiple solutions, you can output any of them.

Sample Input

Sample Output

1 2 3

解析

此题非常简单.给你3*n个坐标,让你组成n个三角形,一个定点只能使用一次,且三角形不能相交.

把所有节点按照x轴排序,然后三个一组,三个一组输出即可.因为按照x轴排序,且不存在三点共线,那么这种方法弄出的三角形就一定不相交.

AC代码

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<long long,long long>
#define sc scanf
#define pr printf
using namespace std;
struct node {
    ll a,b,id; // a left
};
//char str[100000+100];
node s[10500];
bool cmp(node & a,node &b) { // 其实这里只用判断x坐标就可以了
    if(a.a!=b.a)
        return a.a<b.a;
    return a.b<b.b;
}
int main() {
    int t;
    sc("%d",&t);
    while(t--) {
        int n;
        sc("%d",&n);
        ll ans=0;
        for(int i=0; i<3*n; ++i) {
            sc("%lld%lld",&s[i].a,&s[i].b);
            s[i].id=i+1;
        }
        sort(s,s+3*n,cmp);
        for(int i=0; i<3*n; i+=3) {
            pr("%lld %lld %lld\n",s[i].id,s[i+1].id,s[i+2].id);
        }
    }

    return 0;
}

D. Distinct Values

Problem Description

Chiaki has an array of n positive integers. You are told some facts about the array: for every two elements ai and aj in the subarray al..r (l≤i<j≤r), ai≠ajholds. Chiaki would like to find a lexicographically minimal array which meets the facts.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains two integers n and m (1≤n,m≤10^5) – the length of the array and the number of facts. Each of the next m lines contains two integers li and ri (1≤li≤ri≤n).

It is guaranteed that neither the sum of all n nor the sum of all m exceeds 10^6.

Output

For each test case, output n integers denoting the lexicographically minimal array. Integers should be separated by a single space, and no extra spaces are allowed at the end of lines.

Sample Input

Sample Output

2
2 1 2
2 3 1 1

解析

题意就是说给你一些区间,要求区间内部的数字不能重复,且最后的数组的字典序最小.

我们采取这样的策略:一开始数组的所有数都初始化为0.我们先将给定的区间从小到大排序.用Set维护当前可以存放的数,从小到大,放入到区间中,就从set中将其删去,处理完这个区间之后,在处理下一个区间之前,再将Set恢复即可(此操作看代码).

AC代码

#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define scd(X) scanf("%d",&(X))
#define pr printf
#define mp make_pair
#define ll long long
#define fi first
#define se second
#define endl  '\n'

using namespace std;

int n,m;
vector<pii > P;
set<int> S; // 用以存储当前可以放的元素
int ans[100000+100];
int main() {
    int t;
    scd(t);
    while(t--) {
        scd(n);
        scd(m);
        S.clear();
        P.clear();
        for(int i=1;i<=n;++i){
            P.pb(mp(i,i)); // 很巧妙,其实相当于将原位置初始化为1
            S.insert(i); // 把1~n插入
        }
        for(int i=0; i<m; ++i) {
            int l,r;
            scd(l),scd(r);
            P.pb(mp(l,r)); // 插入待处理区间
        }
        sort(P.begin(),P.end()); // 排序
        int left=1,now=1;
        for(int i=0;i<n+m;++i){
            while(left<P[i].fi){ // 此处总共运行不超过n次,将在区间左端点之前的元素插入区间(实际上由于left的维护,是将上一个区间的左端点至本区间左端点里面的数插入set,表示这些数可以用)
                S.insert(ans[left++]);
            }
            for(auto it=S.begin();now<=P[i].se;){ // 直接依次填入set中最小的几个数,填入后即删除,注意迭代器,必须先自增,再删除前一位,否则会re
                ans[now++]=*it;
                auto rm=*it;
                ++it;
                S.erase(rm);
            }
        }
        bool sp=0;
        for(int i=1;i<=n;++i){
            sp?(cout<<" ",1):(cout<<"",sp=1);
            pr("%d",ans[i]);
        }
        pr("\n");
    }
    return 0;
}

K. Time Zone

Problem Description

Chiaki often participates in international competitive programming contests. The time zone becomes a big problem. Given a time in Beijing time (UTC +8), Chiaki would like to know the time in another time zone s.

Input

There are multiple test cases. The first line of input contains an integer T (1≤T≤106), indicating the number of test cases. For each test case: The first line contains two integers a, b (0≤a≤23,0≤b≤59) and a string s in the format of “UTC+X’’, “UTC-X’’, “UTC+X.Y’’, or “UTC-X.Y’’ (0≤X,X.Y≤14,0≤Y≤9).

Output

For each test, output the time in the format of hh:mm (24-hour clock).

Sample Input

3
11 UTC+8
12 UTC+9
23 UTC+0

Sample Output

11
12
23

解析

这题也是很简单,直接模拟即可,不过要注意中国在UTC+8,还有就是输入字符串的处理问题,比较细节.

AC代码

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<long long,long long>
#define sc scanf
#define pr printf
using namespace std;
char cmd[15];
int main() {
    int t;
    sc("%d",&t);
    while(t--) {
        int a,b;
        sc("%d%d",&a,&b);
        sc("%s",cmd);
        int len =strlen(cmd);
        int base=1;
        if(cmd[3]=='-') {
            base=-1;
        }
        int x=0,y=0;
        bool f=0;
        for(int i=4; i<len; ++i) {
            if(!f&&cmd[i]!='.') {
                x = x*10 + cmd[i]-'0';
            } else {
                f=1;
                if(cmd[i]!='.') {
                    y = y*10+cmd[i]-'0';
                }
            }
        }
        y*=base;
        x*=base;
        b+=y*6;
        if(b>=60) {
            a+=1;
            b-=60;
        } else if(b<0) {
            a-=1;
            b+=60;
        }
        a+= x-8 ;
        if(a>=24) {
            a-=24;
        } else if(a<0) {
            a+=24;
        }
        pr("%02d:%02d\n",a,b);
    }
    return 0;
}

总结

这一套多校刷下来,确实难度挺大,主要是思维上的难度比较大,并没有考特别高深的算法和数据结构,就是分析问题的思路和分析复杂度这方面.

另外..g题的规律实在是太不明显了,之后再补吧,感觉已经超乎我的理解范围和观察范围了.

2018 多校1

简介

A. Maximum Multiple

Problem Description

Input

Output

Sample Input

Sample Output

解析

AC代码

B. Balanced Sequence(未完全理解)

Problem Description

Input

Output

Sample Input

Sample Output

AC代码

C. Triangle Partition

Problem Description

Input

Output

Sample Input

Sample Output

解析

AC代码

D. Distinct Values

Problem Description

Input

Output

Sample Input

Sample Output

解析

AC代码

K. Time Zone

Problem Description

Input

Output

Sample Input

Sample Output

解析

AC代码

总结

CATALOG

FEATURED TAGS

FRIENDS