GVKun编程网logo

Java Codility Training基因组范围查询（java基因序列个数）

8

对于想了解JavaCodilityTraining基因组范围查询的读者，本文将提供新的信息，我们将详细介绍java基因序列个数，并且为您提供关于2012Multi-UniversityTraining

对于想了解Java Codility Training基因组范围查询的读者，本文将提供新的信息，我们将详细介绍java基因序列个数，并且为您提供关于2012 Multi-University Training Contest 7、2017 Chinese Multi-University Training, BeihangU Contest、2018 Multi-University Training Contest 1、2018 Multi-University Training Contest 2的有价值信息。

本文目录一览：

Java Codility Training基因组范围查询（java基因序列个数）

Java Codility Training基因组范围查询（java基因序列个数）

任务是：

给出了一个非空的零索引字符串S。字符串S由N个大写英文字母A，C，G，T字符组成。

该字符串实际上代表DNA序列，大写字母代表单个核苷酸。

还为您提供了由M个整数组成的非空零索引数组P和Q。这些数组表示有关最小核苷酸的查询。我们将字符串S的字母表示为数组P和Q中的整数1、2、3、4，其中A =
1，C = 2，G = 3，T = 4，并假定A <C <G <T 。

查询K要求您从范围（P [K]，Q [K]）中找到最小的核苷酸，0≤P [i]≤Q [i] <N。

例如，考虑字符串S = GACACCATA和数组P，Q，使得：

P[0] = 0    Q[0] = 8P[1] = 0    Q[1] = 2P[2] = 4    Q[2] = 5P[3] = 7    Q[3] = 7

这些范围内的最小核苷酸如下：

    (0, 8) is A identified by 1,    (0, 2) is A identified by 1,    (4, 5) is C identified by 2,    (7, 7) is T identified by 4.

编写一个函数：

class Solution { public int[] solution(String S, int[] P, int[] Q); }

假设给定一个由N个字符组成的非空零索引字符串S和两个由M个整数组成的非空零索引数组P和Q，则返回一个由M个字符组成的数组，指定所有查询的连续答案。

该序列应返回为：

    a Results structure (in C), or    a vector of integers (in C++), or    a Results record (in Pascal), or    an array of integers (in any other programming language).

例如，给定字符串S = GACACCATA和数组P，Q，使得：

P[0] = 0    Q[0] = 8P[1] = 0    Q[1] = 2P[2] = 4    Q[2] = 5P[3] = 7    Q[3] = 7

该函数应返回值[1，1，2，4]，如上所述。

假使，假设：

    N is an integer within the range [1..100,000];    M is an integer within the range [1..50,000];    each element of array P, Q is an integer within the range [0..N − 1];    P[i] ≤ Q[i];    string S consists only of upper-case English letters A, C, G, T.

复杂：

    expected worst-case time complexity is O(N+M);    expected worst-case space complexity is O(N),          beyond input storage          (not counting the storage required for input arguments).

输入数组的元素可以修改。

我的解决方案是：

class Solution {    public int[] solution(String S, int[] P, int[] Q) {        final  char c[] = S.toCharArray();        final int answer[] = new int[P.length];        int tempAnswer;        char tempC;        for (int iii = 0; iii < P.length; iii++) {            tempAnswer = 4;            for (int zzz = P[iii]; zzz <= Q[iii]; zzz++) {                tempC = c[zzz];                if (tempC == ''A'') {                    tempAnswer = 1;                    break;                } else if (tempC == ''C'') {                    if (tempAnswer > 2) {                        tempAnswer = 2;                    }                } else if (tempC == ''G'') {                    if (tempAnswer > 3) {                        tempAnswer = 3;                    }                }            }            answer[iii] = tempAnswer;        }        return answer;    }}

这不是最佳选择，我相信应该在一个循环内完成，有什么提示我该如何实现？

您可以在此处检查解决方案的质量https://codility.com/train/测试名称为Genomic-
range-query。

答案1

小编典典

以下是在codility.com中获得100分之100的解决方案。请阅读有关前缀和的信息，以了解解决方案：

public static int[] solveGenomicRange(String S, int[] P, int[] Q) {        //used jagged array to hold the prefix sums of each A, C and G genoms        //we don''t need to get prefix sums of T, you will see why.        int[][] genoms = new int[3][S.length()+1];        //if the char is found in the index i, then we set it to be 1 else they are 0        //3 short values are needed for this reason        short a, c, g;        for (int i=0; i<S.length(); i++) {            a = 0; c = 0; g = 0;            if (''A'' == (S.charAt(i))) {                a=1;            }            if (''C'' == (S.charAt(i))) {                c=1;            }            if (''G'' == (S.charAt(i))) {                g=1;            }            //here we calculate prefix sums. To learn what''s prefix sums look at here https://codility.com/media/train/3-PrefixSums.pdf            genoms[0][i+1] = genoms[0][i] + a;            genoms[1][i+1] = genoms[1][i] + c;            genoms[2][i+1] = genoms[2][i] + g;        }        int[] result = new int[P.length];        //here we go through the provided P[] and Q[] arrays as intervals        for (int i=0; i<P.length; i++) {            int fromIndex = P[i];            //we need to add 1 to Q[i],             //because our genoms[0][0], genoms[1][0] and genoms[2][0]            //have 0 values by default, look above genoms[0][i+1] = genoms[0][i] + a;             int toIndex = Q[i]+1;            if (genoms[0][toIndex] - genoms[0][fromIndex] > 0) {                result[i] = 1;            } else if (genoms[1][toIndex] - genoms[1][fromIndex] > 0) {                result[i] = 2;            } else if (genoms[2][toIndex] - genoms[2][fromIndex] > 0) {                result[i] = 3;            } else {                result[i] = 4;            }        }        return result;    }

2012 Multi-University Training Contest 7

2012 Multi-University Training Contest 7

2012 Multi-University Training Contest 7

A.As long as Binbin loves Sangsang

B.Dead or alive

C.Dragon Ball

D.Draw and paint

E.Matrix operation

F.Palindrome graph

G.Successor

题意:给你一棵树，每个结点有两个属性值，1.能力值,2.忠诚度。然后m个询问，每次询问一个整数u，求u的子树中能力值大于u的且忠诚度最大的点的编号。

SOL:先按能力值排序，这样从大到小考虑就满足了条件１,然后从大到小依次在线段树里查询子树中忠诚度最大的点的编号，复杂度O(nlogn)。

分享图片

分享图片

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #define tl (p << 1)
  6 #define tr (p << 1 | 1)
  7 using namespace std;
  8 const int LEN = 1e5 + 5;
  9 int i,j,k,n,m,s,t,tot,Time;
 10 struct edge {
 11     int vet,next;
 12 } E[LEN * 2];
 13 struct node {
 14     int x,y,id;
 15 } a[LEN];
 16 bool cmp(const node &x,const node &y) {
 17     return x.x > y.x;
 18 };
 19 int head[LEN],size[LEN],tid[LEN],ans[LEN],pre[LEN],b[LEN];
 20 int to[1000005];
 21 int tmax[LEN * 4];
 22 void add(int u,int v) {
 23     E[++tot] = (edge){v,head[u]};
 24     head[u] = tot;
 25 }
 26 void dfs(int u) {
 27     size[u] = 1;
 28     tid[u] = ++Time;
 29     pre[Time] = u;
 30     for (int e = head[u]; e != -1; e = E[e].next) {
 31         int v = E[e].vet;
 32         dfs(v);
 33         size[u] += size[v];
 34     }
 35 }
 36 int ask(int l,int r,int x,int y,int p) {
 37     if (l == x && y == r) {
 38         return tmax[p];
 39     }
 40     int mid = (l + r) >> 1;
 41     if (mid >= y) {
 42         return ask(l,mid,x,tl);
 43     } else if (mid + 1 <= x) {
 44         return ask(mid + 1,r,tr);
 45     } else {
 46         return max(ask(l,tl),ask(mid + 1,mid + 1,tr));
 47     }
 48 }
 49 void update(int p) {
 50     tmax[p] = max(tmax[tl],tmax[tr]);
 51 }
 52 void modify(int l,const int &x,int p,const int &c) {
 53     if (l == r) {
 54         tmax[p] = c;
 55         return;
 56     }
 57     int mid = (l + r) >> 1;
 58     if (mid >= x) {
 59         modify(l,tl,c);
 60     } else {
 61         modify(mid + 1,tr,c);
 62     }
 63     update(p);
 64 }
 65 void build(int l,int p) {
 66     if (l == r) {
 67         tmax[p] = -1;
 68         return;
 69     }
 70     int mid = (l + r) >> 1;
 71     build(l,tl);
 72     build(mid + 1,tr);
 73     update(p);
 74 }
 75 int main() {
 76     int T;
 77     scanf("%d",&T);
 78     while (T--) {
 79         tot = Time = 0;
 80         scanf("%d %d",&n,&m);
 81         for (int i = 1; i <= n; i++) {
 82             head[i] = -1;
 83             size[i] = 0;
 84             tid[i] = 0;
 85         }
 86         a[1] = (node){1e9,0,1};
 87         for (int i = 2; i <= n; i++) {
 88             int fa,y;
 89             scanf("%d %d %d",&fa,&x,&y);
 90             x++,y++,fa++;
 91             swap(x,y);
 92             add(fa,i);
 93             a[i] = (node){x,i};
 94             to[y] = i;
 95         }
 96         dfs(1);
 97         build(1,1);
 98         sort(a + 1,a + 1 + n,cmp);
 99         int j = 1;
100         for (int i = 2; i <= n; i++) {
101             int x = a[i].id,t = ask(1,tid[x],tid[x] + size[x] - 1,1);
102             if (t == -1) {
103                 ans[x] = 0;
104             } else {
105                 ans[x] = to[t];
106             }
107             while (j + 1 <= i && a[j + 1].x > a[i + 1].x) {
108                 modify(1,tid[a[j + 1].id],1,a[j + 1].y);
109                 j++;
110             }
111         }
112         while (m--) {
113             int x;
114             scanf("%d",&x);
115             printf("%d\n",ans[x + 1] - 1);
116         }
117     }
118     return 0;
119 }
View Code

H.The war of virtual world

I.Water World I

J.Water World II

2017 Chinese Multi-University Training, BeihangU Contest

2017 Chinese Multi-University Training, BeihangU Contest

2017 Chinese Multi-University Training, BeihangU Contest

Add More Zero

思路：log10 (2^m) = m*log10 (2)

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb emplace_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<int, pii>
#define puu pair<ULL, ULL>
#define pdd pair<long double, long double>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head
 
int n, cs = 0;
int main() {
    while(~scanf("%d", &n)) {
        printf("Case #%d: %d\n", ++cs, (int)(n*log10(2.0)));
    }
    return 0;
}
View Code

Balala Power!

思路：大数比较大小

代码：

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define debug(x) cerr<<#x << " := " << x << endl;
#define bug cerr<<"-----------------------"<<endl;
#define FOR(a, b, c) for(int a = b; a <= c; ++ a)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int inf = 0x3f3f3f3f;
 
const int mod = 1e9+7;
 
/**********showtime************/
            const int maxn = 1e5+9;
            char str[maxn];
            string ss[maxn];
            vector<pii>vec[30];
            int a[30][maxn], mx[30];
            int id[30], vis[30];
            bool cmp(int &x, int &y) {
                if(mx[x] < mx[y]) return true;
                else if(mx[x] > mx[y]) return false;
                else {
                    for (int i = mx[x]-1; i >= 0; --i) {
                        if(a[x][i] > a[y][i]) return false;
                        else if(a[x][i] < a[y][i]) return true;
                    }
                }
                return false;
            }
int main(){
            int n, cas = 0;
            while(~scanf("%d", &n)) {
 
                for(int i=0; i<26; i++) vec[i].clear(), vis[i] = 0, mx[i] = 0;
                for(int i=0; i<26; i++) for(int j=0; j<maxn; j++) a[i][j]  = 0;
                for(int i=1; i<=n; i++) {
                    scanf("%s", str);
                    ss[i] = string(str);
                    vis[str[0] - ''a''] = 1;
                }
 
                for(int i=1; i<=n; i++) {
                    int len = ss[i].length();
                    for(int j=0; j<len; j++) {
                        a[ss[i][j] - ''a''][len - j - 1] ++;
                    }
                }
 
                for(int i=0; i<26; i++) {
                    int jin = 0;
                    for(int j=0; j<maxn-1; j++) {
                        a[i][j] += jin;
                        jin = a[i][j] / 26;
                        a[i][j] = a[i][j] % 26;
                        if(a[i][j] > 0) {
                            mx[i] = j+1;
                        }
                    }
                }
 
                for(int i=0; i<26; i++) id[i] = i;
 
                sort(id, id+26, cmp);
 
                int pos = 0;
                while(vis[id[pos]]) pos++;
                int pt = id[pos];
                for(int i=pos; i>=0; i--) id[i] = id[i-1];
                id[0] = pt;
                ll ans = 0;
                for(int i=0; i<26; i++) {
                    ll base = 1;
                    for(int j=0; j<maxn; j++) {
 
                        ans = (ans + 1ll*i * base *a[id[i]][j] % mod)%mod;
                        base = 1ll * base * 26 % mod;
                    }
                }
                ++cas;
                printf("Case #%d: %lld\n",cas,  ans);
            }
            return 0;
}
View Code

Colorful Tree

思路：容斥，考虑对于每种颜色删去后，分成的块中的点两两之间对于这种颜色没有贡献

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head

const int N = 2e5 + 5;
vector<int> g[N], stk[N];
int n, u, v, c[N], sz[N], blo[N], top[N];
bool vis[N];
void dfs(int u, int o) {
    sz[u] = 1;
    for (int v : g[u]) {
        if(v != o) {
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
    blo[u] = sz[u];
}
void DFS(int u, int o) {
    if(stk[c[u]].empty()) top[c[u]] -= sz[u];
    else blo[stk[c[u]].back()] -= sz[u];
    for (int v : g[u]){
        if(v != o) {
            stk[c[u]].pb(v);
            DFS(v, u);
            stk[c[u]].pop_back();
        }
    }
}
int cs = 0;
int main() {
    while(~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i) scanf("%d", &c[i]), vis[c[i]] = true;
        for (int i = 1; i < n; ++i) scanf("%d %d", &u, &v), g[u].pb(v), g[v].pb(u);
        dfs(1, 0);
        int cc = 0;
        for (int i = 1; i <= n; ++i) if(vis[i]) top[i] = n, ++cc; else top[i] = 0;
        DFS(1, 0);
        LL ans = n*1LL*(n-1)/2*cc;
        for (int i = 2; i <= n; ++i) ans -= blo[i]*1LL*(blo[i]-1)/2;
        for (int i = 1; i <= n; ++i) ans -= top[i]*1LL*(top[i]-1)/2;
        printf("Case #%d: %lld\n", ++cs, ans);
        for (int i = 1; i <= n; ++i) g[i].clear(), vis[i] = false;
    }
    return 0;
}
View Code

Division Game

Expectation of Division

Function

思路：a 的某个长度为 x 环可以和 b 中长度为 x 因子的环构成函数

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head
 
const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
int n, m, a[N], b[N], ca[N], cb[N];
LL ans[N];
bool vis[N], vv[N];
LL q_pow(LL n, LL k) {
    LL res = 1;
    while(k) {
        if(k&1) res = (res * n) % MOD;
        n = (n * n) % MOD;
        k >>= 1;
    }
    return res;
}
int main() {
    int cs = 0;
    while(~scanf("%d %d", &n, &m)) {
        for (int i = 0; i < n; ++i) vis[i] = false, ca[i+1] = 0, ans[i+1] = 0;
        for (int i = 0; i < m; ++i) vv[i] = false, cb[i+1] = 0;
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        for (int i = 0; i < m; ++i) scanf("%d", &b[i]);
        for (int i = 0; i < n; ++i) {
            if(!vis[i]) {
                int now = i, cc = 0;
                while(!vis[now]) {
                    vis[now] = true;
                    now = a[now];
                    ++cc;
                }
                ca[cc]++;
            }
        }
        for (int i = 0; i < m; ++i) {
            if(!vv[i]) {
                int now = i, cc = 0;
                while(!vv[now]) {
                    vv[now] = true;
                    now = b[now];
                    ++cc;
                }
                cb[cc] ++;
            }
        }
        LL res = 1;
        for (int i = 1; i <= m; ++i) {
            cb[i] = (cb[i]*1LL*i)%MOD;
            for (int j = i; j <= n; j += i) {
                ans[j] = (ans[j] + cb[i]) % MOD;
            }
        }
        for (int j = 1; j <= n; ++j) {
            if(ca[j]) {
                res = (res * q_pow(ans[j], ca[j])) % MOD;
            }
        }
        printf("Case #%d: %lld\n", ++cs, res);
    }
    return 0;
}
View Code

Gear Up

Hints of sd0061

思路：nth_element

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head
 
const int N = 1e7 + 5;
unsigned x, A, y, B, z, C;
int n, m, b[105], id[105];
unsigned a[N], ans[N];
inline unsigned rng61() {
    unsigned t;
    x = x ^ (x << 16);
    x = x ^ (x >> 5);
    x = x ^ (x << 1);
    t = x;
    x = y;
    y = z;
    z = (t ^ x) ^ y;
    return z;
}
int cs = 0;
int main() {
    while(~scanf("%d %d %u %u %u", &n, &m, &A, &B, &C)) {
        for (int i = 1; i <= m; ++i) scanf("%d", &b[i]);
        x = A, y = B, z = C;
        for (int i = 1; i <= n; ++i) a[i] = rng61();
        printf("Case #%d: ", ++cs);
        for (int i = 1; i <= m; ++i) id[i] = i;
        sort(id+1, id+1+m, [](int x, int y){
                return b[x] < b[y];
             });
        nth_element(a+1, a+b[id[m]]+1, a+n+1);
        ans[id[m]] = a[b[id[m]]+1];
        for (int i = m-1; i >= 1; --i) {
            nth_element(a+1, a+b[id[i]]+1, a+b[id[i+1]]+1);
            ans[id[i]] = a[b[id[i]]+1];
        }
        for (int i = 1; i <= m; ++i) printf("%u%c", ans[i], " \n"[i==m]);
    }
    return 0;
}
View Code

I Curse Myself

Journey with Knapsack

KazaQ''s Socks

思路：打表找规律

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb emplace_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<int, pii>
#define puu pair<ULL, ULL>
#define pdd pair<long double, long double>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head
 
LL n, k;
int main() {
    int cs = 0;
    while(~scanf("%lld %lld", &n, &k)) {
        LL res;
        if(n == 2) res = k%2 == 0? 2 : 1;
        else if(k <= n-1) res = k;
        else {
            if(k%(n-1) == 1) {
                --k;
                if((k/(n-1))%2) res = n;
                else res = n-1;
            }
            else {
                res = k%(n-1);
                if(res == 0) res = n-1;
                --res;
            }
        }
        printf("Case #%d: %lld\n", ++cs, res);
    }
    return 0;
}
View Code

Limited Permutation

 

2018 Multi-University Training Contest 1

2018 Multi-University Training Contest 1

1001：

 推出公式只需要 1/x+1/y+1/z=1 的整数解，有 2、4、4 和 3、3、3 和 2、3、6。但 2、3、6 得到答案比 3、3、3 小，故只判断前两种可能。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <string>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <map>
 7 #include <stack>
 8 #include <vector>
 9 #include <queue>
10 #include <set>
11 using namespace std;
12 
13 const int MAX=1e5+5;
14 long long t,n;
15 long long a,b;
16 
17 int main(){
18     scanf("%lld",&t);
19     while(t--){
20         a=b=0;
21         scanf("%lld",&n);
22         if(n%4==0){
23             a=n/2*n/4*n/4;
24         }
25         if(n%3==0)
26             b=n/3*n/3*n/3;
27         if(n%4&&n%3)
28             puts("-1");
29         else
30             printf("%lld\n",max(a,b));
31     }
32     
33     return 0;
34 }
View Code

 

1002：

把每个串能够匹配的处理掉，得到剩余的左括号和右括号数，再按贡献大小排序，最后合并成一个串。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;

const int MAX=1e5+5;
int t,n;
char str[MAX];
struct node{
    int l,r;
}p[MAX];
int ans;

int cmp(node a,node b){
    int tmpa,tmpb;
    tmpa=min(a.l,b.r);
    tmpb=min(a.r,b.l);
    if(tmpa==tmpb)
        return a.l>b.l;
    return tmpa>tmpb;
}

int main(){
    int i,j;
    
    //freopen("1002.in","r",stdin);
    //freopen("1003.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        ans=0;
        scanf("%d",&n);
        for(i=0;i<n;i++){
            scanf("%s",&str);
            int len=strlen(str);
            p[i].l=p[i].r=0;
            for(j=0;j<len;j++){
                if(str[j]==''('') p[i].l++;
                else{
                    if(p[i].l) p[i].l--,ans++;
                    else p[i].r++;        
                }
            }
        }
        sort(p,p+n,cmp);
        int l=0;
        for(i=0;i<n;i++){
            if(p[i].r>l){
                ans+=l;
                l=0;
            }
            else{
                ans+=p[i].r;
                l-=p[i].r;
            }
            l+=p[i].l;
        }
        printf("%d\n",ans*2); 
    }
    
    return 0;
}
View Code

 

1003：

贪心排一下序就行，先按 x 坐标再按 y 坐标，每次选三个即可

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;
struct point
{
    long long x,y;
    int id;
};
point po[4010];
int n;

void init()
{
    memset(po,0,sizeof(po));
}

bool cmp(const point &a,const point &b)
{
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}

int main()
{
    int i;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d",&n);
        for(i=1;i<=3*n;i++)
        {
            cout<<i<<endl;
            scanf("%lld%lld",&po[i].x,&po[i].y);
            po[i].id=i;
        }
        sort(po+1,po+1+3*n,cmp);
        int pos=1;
        for(i=1;i<=n;i++)
        {
            printf("%d %d %d\n",po[pos++].id,po[pos++].id,po[pos++].id);
        }
    }
    return 0;
}
View Code

 

1004：

 添加 n 条端点为 [i,i] 的长度为 1 的线段，将所有线段以左端点为第一关键字，线段长度为第二关键字排序，依次处理。设置 L，R 两个指针和一个小根堆（初始存了 1~n 的数字），每次处理一条线段时先将 L 到线段左端点的数字加入小根堆，再把 R 到线段右端的数字从小根堆中取数字更新。

 1 #include<queue>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 
 7 #define maxn 200000+5
 8 
 9 using namespace std;
10 
11 priority_queue <int,vector<int>,greater<int> > q;
12 
13 struct Data{
14     int l,r,len;
15     bool operator <(const Data &T)const{
16         if(l==T.l) return len>T.len;
17         else return l<T.l;
18     }
19 }t[maxn];
20 
21 int res[maxn];
22 int n,m;
23 
24 int main(){
25     int T;
26     scanf("%d",&T);
27     while(T--){
28         memset(res,0,sizeof(res));
29         scanf("%d%d",&n,&m);
30         while(!q.empty()) q.pop();
31         for(int i=1;i<=n;i++) q.push(i);
32         for(int i=1;i<=m;i++){
33             scanf("%d%d",&t[i].l,&t[i].r);
34             t[i].len=t[i].r-t[i].l+1;
35         }
36         for(int i=1;i<=n;i++) t[++m].l=i,t[m].r=i,t[m].len=1;
37         sort(t+1,t+1+m);
38         int L=1,R=0;
39         for(int i=1;i<=m;i++){
40             while(L<t[i].l) q.push(res[L]),L++;
41             while(R<t[i].r) res[++R]=q.top(),q.pop();
42         }
43         printf("%d",res[1]);
44         for(int i=2;i<=n;i++) printf(" %d",res[i]);
45         puts(""); 
46     }
47     return 0;
48 }
View Code

 

1005：

 

1007：

找规律，打表

首先把 a [] 序列打表出来：

将相同元素放到同一行发现这样的一个三角形

1 

1

2 2

3 

4 4 4

5

6 6

7

8 8 8 8

发现这个 a [] 中每个元素出现的次数刚好是因子中所含 2 的数量 + 1

然后就好做了，找一找这个三角形规律，注意打表，log*log 的复杂度过不了

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;
const long long mod=1e9+7;
const long long inv=500000004;
long long  num_2[100],mi[100],biao[100],biao_cnt[100];
long long n,num,sum;
long long ans;

void init()
{
    num=0;
    ans=0;
    sum=0;
}

long long fun(long long now,int i)
{
    long long pos=now;

    long long flag=(pos%mod)*((pos+1)%mod)%mod;
    flag=(flag*inv)%mod;
    long long tmp=flag;
    long long cnt=pos;
    long long t=flag;
    pos/=2;
    while(pos>0)
    {
        tmp=(tmp+((t+now/2)%mod)*inv)%mod;
        cnt+=pos;
        pos/=2;
        t=(((t+now/2)%mod)*inv)%mod;
    }
    tmp=(tmp+(sum%mod*cnt%mod)%mod)%mod;

    biao_cnt[i]=cnt;
    sum+=now;
    return (tmp%mod+mod)%mod;
}

int main()
{
    //freopen("123.in","r",stdin);
    //freopen("123.out","w",stdout);
    int i;
    num_2[0]=0;
    mi[0]=1;
    biao[0]=fun(mi[0],0);
    long long flag=1;
    for(i=1;i<=62;i++)
    {
        flag*=2;
        mi[i]=flag;
        num_2[i]=flag-1;
        sum=0;
        biao[i]=fun(mi[i],i);
   //     cout<<biao_cnt[i]<<endl;
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%lld",&n);
        long long tmp=n-1;
        for(i=62;i>0;i--)
        {
            if(tmp==0) break;
            if(num_2[i]>tmp) continue;
            num+=(num_2[i]+1)/2;
            tmp-=num_2[i];
        }

        long long cnt=num;
        long long pos=0;
        int xx=62;
        sum=0;
        while(cnt>0)
        {

           for(i=xx;i>=0;i--)
            {
                if(mi[i]<=cnt)
                {
                    pos=mi[i];
                    break;
                }
            }
            long long flag=biao[i];

            flag=(flag+(sum%mod)*(biao_cnt[i]%mod))%mod;
            ans=(ans+flag)%mod;
            cnt-=pos;
            sum+=pos;
        }
        ans=(ans+((num+1)%mod)*(tmp%mod)+1)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}
View Code

 

1008：

 MQ-Similar 实际上就是 A 和 B 的笛卡尔树一样，这样我们就有了一个二叉树，然后可以在树上分析了。

考虑到 B 中有元素相同的概率是 0 ，于是可以假设 BB 里面元素互不相同，也就是说可以假定是一个排列。

显然，符合笛卡尔树的排列就是这个树的拓扑序列个数，就是 n!/2∏sizei。然后显然每个排列期望的和是 n/2，于是答案就是 n/2∏sizei

由于我们只需要知道笛卡尔树的大小，所以可以不通过显性建树，用单调栈维护一下即可

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;
const long long mod=1e9+7;
int ai[3000010];
int n;
int st[3000010],head,sum_left[3000010],sum[3000010];
long long inv[1000010];

void init()
{
    head=0;
}

struct FastIO
{
    static const int S = 200;
    int wpos;
    char wbuf[S];
    FastIO() :wpos(0) {}
    inline int xchar()
    {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len) pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) exit(0);
        return buf[pos++];
    }
    inline int read()
    {
        int s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == ''-'') s = -1, c = xchar();
        for (; ''0'' <= c && c <= ''9''; c = xchar()) x = x * 10 + c - ''0'';
        return x * s;
    }
    ~FastIO()
    {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
}io;


int main()
{
    //freopen("1008.in","r",stdin);
    //freopen("text.out","w",stdout);
    int i,j;
    int t;
    inv[1]=1;
    for(i=2;i<=1000000;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    t=io.read();
    while(t--)
    {
        n=io.read();
        init();
        for(i=1;i<=n;i++)
        {
            ai[i]=io.read();
        }
        for(i=1;i<=n;i++)
        {
            sum[i]=0;
            sum_left[i]=0;
            while(head!=0&&ai[st[head]]<ai[i])
            {
                sum[st[head]]=i-sum_left[st[head]];
                head--;
            }
            if(head==0) sum_left[i]=1;
            else sum_left[i]=st[head]+1;
            st[++head]=i;
        }
        for(i=2;i<=head;i++) sum[st[i]]=n-sum_left[st[i]]+1;
        sum[st[1]]=n;
        long long ans=1;
        for(i=1;i<=n;i++)
        {
            ans=(ans*inv[sum[i]])%mod;
        }
        ans=(ans*n)%mod*inv[2]%mod;
        printf("%lld\n",ans);
    }
    return 0;
}
View Code

 

1011：

随便算算

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#include <set>
using namespace std;

const int MAX=1e5+5;
int a,b,x,y,t,flag,p;
char str[MAX];

int main(){
    int i;
    
    scanf("%d",&t);
    while(t--){
        x=y=flag=0;
        scanf("%d%d",&a,&b);
        scanf("%s",&str);
        for(i=0;i<strlen(str);i++){
            if(str[i]==''.'')
                flag=1;
            if(str[i]==''+'')
                p=1;
            if(str[i]==''-'')
                p=-1;
            if(flag&&str[i]>=''0''&&str[i]<=''9'')
                y=str[i]-''0'';
            if(!flag&&str[i]>=''0''&&str[i]<=''9''){
                x=str[i]-''0'';
                if(str[i+1]>=''0''&&str[i+1]<=''9''){
                    x*=10;
                    x+=str[i+1]-''0'';
                    i++;
                } 
            }
        }
        if(p==1){
            if(x<8){
                int h=8-x;
                a-=h;
                if(a<0) a+=24;
            }
            else{
                int h=x-8;
                a+=h;
                if(a>=24) a-=24;
            }
            int m=6*y;
            b+=m;
            if(b>=60){
                a++;
                if(a>=24) a-=24;
                b-=60;
            }
        }
        else{
            int h=x+8;
            a-=h;
            if(a<0) a+=24;
            int m=6*y;
            b-=m;
            if(b<0){
                a--;
                if(a<0) a+=24;
                b+=60;
            }
        }
        printf("%0.2d:%0.2d\n",a,b);
    }
    
    return 0;
}
View Code

 

2018 Multi-University Training Contest 2

2018 Multi-University Training Contest 2

<font size=3>

##2018 Multi-University Training Contest 2 题解 ###C - Cover 题目描述：给定一个图（不一定联通），用最少的的欧拉路径或欧拉回路覆盖，输出方案。

solution 一个个联通块处理，对于一个联通块（如果只有一个点，那就可以忽略了），一定有偶数个度数为奇数的点（设为 $k$ 个），将这些点每两个配对连边，走一次欧拉回路，然后将这些边删掉，就可以分成 $max (k/2, 1)$ 路径，而这就是最优的。

时间复杂度：$O (n)$

###D - Game 题目描述：在集合里有 $n$ 个元素（$1$~$n$），两个人玩游戏，每次从集合里面选一个数，然后将他的所有约数从集合里删掉，谁不能选数，谁就输。问先手是否必胜。

solution $1$ 是一个非常特殊的数，因为无论删什么数，都会删 $1$。如果先手不删 $1$ 有必胜策略，则必胜，如果必败，则删 $1$，把败局扔给后手，必胜，所以先手必胜。

时间复杂度：$O (1)$

###E - Hack It 题目描述：有一个 $n \times n$ 的方阵，每一个是 $0$ 或 $1$，现在有一个算法来判断这个方阵是否存在一个子矩阵，它的四个角都是 $1$，所在要构造一个 $n \leq 2000$ 的方阵，使得里面有至少 $85000$ 个 $1$，但满足条件的子矩阵不存在。

solution 令 $n=p^2，p$ 是质数，这里 $p=47$，然后这个方阵由 $p^2$ 个 $p^2$ 的方阵组成，现在要填数进去，使得任意两行至多只有一列都有 $1$。 对于 $k, b, i<p, a [kp+b][ip+(ki+b)% p]=1$ 设 $k_1 \neq k_2$, 假设 $ip+(k_1i+b)% p=ip+(k_2i+b)% p$(不可能左边是 $i$，右边是 $j$)，判断是否存在 $j$ 也满足等式，假设 $jp+(k_1i+b)% p=jp+(k_2i+b)% p$, 两式相减，则 $(i-j) k_1=(i-j) k_2 (modp)$，因为 $p$ 是质数，且 $k_1 \neq k_2$，因此等式不成立，所以不存在 $j$ 也满足等式，即没有两列同有 $1$。 因此这种构造是对的，只要取前 $2000 \times 2000$ 的矩阵即可。

时间复杂度：$O (p^4)$

###F - Matrix 题目描述：有一个 $n \times m$ 的矩阵，每个格子要么是黑色，要么白色，问有多少种方案使得至少有 $A$ 行黑色，$B$ 列黑色。

solution

这个题解说得挺详细的，但按着那里说的貌似答案不对。

###G - Naive Operations 题目描述：给定一个 $n$ 排列 $B$，有一个长度为 $n$ 的序列 $A$，初始全都为 $0$，现在有两种操作：1、给 $A$ 的一个区间全部加 $1$，2、询问一个区间的 $\left \lfloor \frac {a_i}{b_i} \right \rfloor$ 的和

solution 有两种做法： 1、用线段树维护对于区间 $[L, R]$，要加多少次 $1$ 才能使区间里的一个数的答案加 $1$, 一旦存在就从该点往下更新答案。

2、离线处理所有的加操作，按左端点从小到大排序，用线段树求出每个位置的数在哪里次加操作后答案加一，然后再按时间顺序进行正常操作。

时间复杂度：$O (nlog^2n)$

###J - Swaps and Inversions 题目描述：对一个序列进行操作，操作后的总花费为序列的逆序对个数乘 $x$，而进行一次操作需要花费 $y$，操作是交换相邻两个数。

solution 交换相邻两个数可以消除一个逆序对，因此答案等于逆序对个数乘 $min (x, y)$

时间复杂度：$O (nlogn)$

</font>

今天的关于Java Codility Training基因组范围查询和java基因序列个数的分享已经结束，谢谢您的关注，如果想了解更多关于2012 Multi-University Training Contest 7、2017 Chinese Multi-University Training, BeihangU Contest、2018 Multi-University Training Contest 1、2018 Multi-University Training Contest 2的相关知识，请在本站进行查询。

本文标签：

上一篇java.util.AbstractList.remove处的java.lang.UnsupportedOperationException（未知源）（java在源文件中未声明类）

下一篇等同于InputStream或Reader的Files.readAllLines（）？（等同于的英文短语）

相关文章