【Kickstart】2018 Round (Practice ~ C)

Practice Round

Problem A GBus count (9pt/15pt) （2019年1月14日，kickstart群每日一题）

题意：有一条笔直的大路，上面有城市编号从 1 开始从左到右一次排列。上面有 N 个 GBuses， 每一个 bus[i] 连接 A[i]  到 B[i] 两个地点（包含这两个地方）。我们想要求 P 个城市，每个城市经过的公交车数量。

输入输出 和 数据规模 如下:

There exist some cities that are built along a straight road. The cities are numbered 1, 2, 3... from left to right.
There are N GBuses that operate along this road. For each GBus, we know the range of cities that it serves: the i-th gBus serves the cities with numbers between Ai and Bi, inclusive.
We are interested in a particular subset of P cities. For each of those cities, we need to find out how many GBuses serve that particular city.
Input
The first line of the input gives the number of test cases, T. Then, T test cases follow; each case is separated from the next by one blank line. (Notice that this is unusual for Kickstart data sets.)

In each test case:
The first line contains one integer N: the number of GBuses.
The second line contains 2N integers representing the ranges of cities that the buses serve, in the form A1 B1 A2 B2 A3 B3 ... AN BN. That is, the first GBus serves the cities numbered from A1 to B1 (inclusive), and so on.
The third line contains one integer P: the number of cities we are interested in, as described above. (Note that this is not necessarily the same as the total number of cities in the problem, which is not given.)
Finally, there are P more lines; the i-th of these contains the number Ci of a city we are interested in.

Output
For each test case, output one line containing Case #x: y, where x is the number of the test case (starting from 1), and y is a list of P integers, in which the i-th integer is the number of GBuses that serve city Ci.

Limits
1 ≤ T ≤ 10.
Small dataset
1 ≤ N ≤ 50 
1 ≤ Ai ≤ 500, for all i.
1 ≤ Bi ≤ 500, for all i.
1 ≤ Ci ≤ 500, for all i.
1 ≤ P ≤ 50.
Large dataset
1 ≤ N ≤ 500.
1 ≤ Ai ≤ 5000, for all i.
1 ≤ Bi ≤ 5000, for all i.
1 ≤ Ci ≤ 5000, for all i.
1 ≤ P ≤ 500.

题解：我们只需要把每个bus的起点和终点读进来，然后对于每一个城市，都去每个bus的区间里面查这个城市是不是在这个bus区间里面，是的话就加一。

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>

using namespace std;

void print(vector<pair<int, int>>& bus) {
  for (int i = 0; i < bus.size(); ++i) {
    printf("%d -> %d 
", bus[i].first, bus[i].second);
  }
}
void solve(const int id) {
  int n, p;
  cin >> n;
  vector<pair<int, int>> bus(n);
  for (int i = 0; i < n; ++i) {
    int s, e;
    cin >> s >> e;
    if (s > e) { 
      swap(s, e); 
    }
    bus[i] = make_pair(s, e);
  }
// print(bus);
  cin >> p;
  vector<int> ans(p, 0);
  for (int i = 0; i < p; ++i) {
    int city;
    cin >> city;
    for (auto b : bus) {
      if (city >= b.first && city <= b.second) {
        ans[i]++;
      }
    }
  }
  printf("Case #%d:", id);
  for (auto e : ans) {
    printf(" %d", e);
  }
  printf("
");
  return;
}
int main () {
  int t;
  cin >> t;
  for (int idx = 1; idx <= t; ++idx) {
    solve(idx);
  }
  return 0;
}

 总监说线段树，我下周学习一下线段树==

Problem B Googol String (7pt/12pt) (2019年1月15日， kickstart群每日一题)

给了一个非常长的字符串，有一定的生成规则，问字符串的第 K 个字母是啥。

A "0/1 string" is a string in which every character is either 0 or 1. There are two operations that can be performed on a 0/1 string:

• switch: Every 0 becomes 1 and every 1 becomes 0. For example, "100" becomes "011".
• reverse: The string is reversed. For example, "100" becomes "001".

Consider this infinite sequence of 0/1 strings:
S₀ = ""
S₁ = "0"
S₂ = "001"
S₃ = "0010011"
S₄ = "001001100011011"
...
S_N = S_N-1 + "0" + switch(reverse(S_N-1)).
You need to figure out the Kth character of Sgoogol, where googol = 10^100.
Input
The first line of the input gives the number of test cases, T. Each of the next T lines contains a number K.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the Kth character of S_googol.
Limits
1 ≤ T ≤ 100.
Small dataset
1 ≤ K ≤ 10^5.
Large dataset
1 ≤ K ≤ 10^18.

题解：小数据暴力可以解出来，大数据不行。大数据看了下答案学习了一下。整个字符串呈中心对称（字符串数组 1-based），2^k 的位置肯定是 0， 左右子串中心对称，并且需要 switch 0,1. 代码怎么写需要复习，一开始还没搞明白怎么写。明天复习。

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>

using namespace std;
typedef long long ll;

int bst(ll k, int x);
int solve() {
  ll k;
  scanf("%lld", &k);
  return bst(k, 60); //2^60 > 1e18
}
// string is 1-based.
int bst(ll k, int x) {
  ll sz = 1LL << x;
  if (k == sz) { return 0; }
  if (k < sz) {  //left substr
    return bst(k, x-1);
  }
  if (k > sz) { // right substr
    return 1 ^ bst(sz - (k - sz), x-1); //return 1 - bst(sz - (k - sz), x-1);
  }
  return -1;
}
int main () {
  int t;
  cin >> t;
  for (int idx = 1; idx <= t; ++idx) {
    int ret = solve();
    printf("Case #%d: %d
", idx, ret);
  }
  return 0;
}

Problem C Sort a scarmbled itinerary (11pt/15pt)

Problem D Sums of Sums (8pt/28pt)

 

Round A

Problem A Even Digits (8pt/15pt)

Problem B Lucky Dip (10pt/19pt) (2019年1月23日，kickstart群每日一题)

https://code.google.com/codejam/contest/9234486/dashboard#s=p1&a=1

袋子里面有 N 个物品，每个物品都有它的价值，每次从袋子里面取一个物品出来，有 K 次往回丢的机会。我们的目标是最大化物品价值的期望值。求最大期望。

Input

The input starts with one line containing one integer T: the number of test cases. T test cases follow.

Each test case consists of two lines. The first line consists of two integers N and K: the number of items in the bag, and the maximum number of times you may redip. The second line consists of N integers V_i, each representing the value of the i-th item.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the expected value described above. Your answer will be considered correct if it is within an absolute or relative error of 10^-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

Limits

1 ≤ T ≤ 100.
1 ≤ V_i ≤ 10⁹.
1 ≤ N ≤ 20000.

Small dataset

0 ≤ K ≤ 1.

Large dataset

0 ≤ K ≤ 50000.

Input                         
5
4 0
1 2 3 4
3 1
1 10 1
3 15
80000 80000 80000
1 1
10
5 3
16 11 7 4 1

Output

Case #1: 2.500000
Case #2: 6.000000
Case #3: 80000.000000
Case #4: 10.000000
Case #5: 12.358400

题解：如果 k == 0， 那么期望值就是所有物品价值的平均值。如果 k > 0， 我们可以想像一下，对于第 i 次我们取出来的物品，如果当前物品的价值大于 i - 1 次的期望值，那么就就留下，如果小于第 i - 1次的期望值，那么就扔回去。

所以，期望的计算公式是 E[0] = sigma(vi), E[i] = sigma(Max(vi, E[i-1]))/N， 返回 E[k]. 暴力算法的时间复杂度是 O(NK)

本题可以用二分优化，先对物品价值进行排序，每次二分出来比E[i-1]大的区间，然后累加。

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>

using namespace std;

void solve(int id) {
    double res = 0.0;
    int n, k;
    cin >> n >> k;
    int number; long long total = 0;
    unordered_map<int, int> freq;
    for (int i = 0; i < n; ++i) {
      cin >> number;
      total += (long long)number;
      freq[number]++;
    }
    vector<double> e(k+1, 0.0);
    e[0] = (double)total / n;
    double t = 0;
    for (int i = 1; i <= k; ++i) {
        double t = 0.0;
        for (auto p : freq) {
          t += max((double)p.first, (double)e[i-1]) * (double)p.second;
        }
        e[i] = t / (double)n;
    }
    res = e[k];
    printf("Case #%d: %lf
", id, res);
}
int main () {
  int t;
  cin >> t;
  for (int idx = 1; idx <= t; ++idx) {
    solve(idx);
  }
  return 0;
}

Problem C Scrambled Words (18pt/30pt)

 

Round B

Problem A No Line (7pt/13pt)

Problem B Sherlock and Bit Strings (11pt/26pt)

Problem C King's Circle (16pt/27pt)

 

Round C

链接：https://code.google.com/codejam/contest/4384486/dashboard

Problem A Planet Distance (10pt/15pt) （2019年1月29日，打卡群）

题意是说，给了一个无向图， 里面有个环，要求返回一个距离数组，环上的点在距离数组上都是 0， 不在环上的点，在距离数组上都是距离环的距离。

题解：如何找到一个无向图的环。用kahn算法的思想，bfs解法。先读入边，然后用邻接链表来存储，然后计算每个节点的度（无向图，度就是结点上的边数）。找到所有度为 1 的结点，把这些结点放进队列。然后把结点pop出队列的时候，相当于在图上把这个结点给删除了。所以，和这个结点相邻的结点的度也应该减一。遍历所有跟当前结点相邻的结点。如果相邻结点的边数还剩下一条并且它没有被访问过的话，就把这个相邻的结点也放进队列（变成要删除的的结点，相当于放进一个删除的缓冲区）。bfs的完毕之后，我们找到所有度不为0的结点，那么就是环上的结点了。

如何求剩下的结点距离环的距离。把所有环上的结点放进队列。然后遍历相邻结点计算距离（还是bfs，这个我会==）

时间复杂度是 O(N) 的。此外还有一个实现上的小问题，就是如果变量搞成全局变量的话，每次读新的test case，要注意清空啊==

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <unordered_set>
#include <unordered_map>

using namespace std;

int v;
unordered_map<int, vector<int>> edges;
vector<int> degree;
void getInput() {
  edges.clear();
  degree.clear();
  cin >> v;
  degree = vector<int>(v + 1, 0);
  for (int i = 0; i < v; ++i) {
    int s, e;
    cin >> s >> e;
    edges[s].push_back(e);
    degree[s]++;
    edges[e].push_back(s);
    degree[e]++;
  }
}

vector<int> planetDistance() {
  queue<int> que;
  vector<int> visited(v+1, 0);
  for (int i = 1; i <= v; ++i) {
    if (degree[i] == 1) {
      que.push(i);
      degree[i]--;
      visited[i] = 1; //i has been visited
    }
  }
  while (!que.empty()) {
    int curNode = que.front(); que.pop();
    for (auto adjNode : edges[curNode]) {
      if (visited[adjNode] == 0 && --degree[adjNode] == 1) {
        que.push(adjNode);
        degree[adjNode]--;
        visited[adjNode] = 1;
      }
    }
  }
  vector<int> ret(v+1, v+1);
  que = queue<int>(); //clear queue
  for (int i = 1; i <= v; ++i) {
    if (degree[i] != 0) {
      que.push(i);
      ret[i] = 0; //node i is in the circle.
    }
  }
  while (!que.empty()) {
    int curNode = que.front(); que.pop();
    for (auto adjNode : edges[curNode]) {
      if (visited[adjNode] == 1) {
        ret[adjNode] = ret[curNode] + 1;
        visited[adjNode] = 0;
        que.push(adjNode);
      }
    }
  }
  vector<int> res(ret.begin() + 1, ret.end());
  return res;
}

void solve(const int id) {
  getInput();
  vector<int> res = planetDistance();
  printf("Case #%d:", id);
  for (auto r : res) {
    cout << " " << r ;
  }
  cout << endl;
}
int main () {
int t;
cin >> t;
  for (int idx = 1; idx <= t; ++idx) {
    solve(idx);
  }
  return 0;
}

Problem B Fairies and Witches (15pt/21pt)

Problem C Kickstart Alarm (13pt/26pt)