COCI 2015、2016 1st round 题解（官方）

官方题解：

官方代码：

Code-KARTE:

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

const int MAXB = 5;

const int MAXN = 20;

bool bio[MAXB][MAXN];

int getColor(char chr) {

  if (chr == 'P') return 0;

  if (chr == 'K') return 1;

  if (chr == 'H') return 2;

  if (chr == 'T') return 3;

}

int main(void) {

  string s;

  cin >> s;

  for (int i = 0; i < s.size(); i += 3) {

    int b = getColor(s[i]);

    int x = (s[i + 1] - '0') * 10 + s[i + 2] - '0';

    if (bio[b][x]) {

      printf("GRESKA\n");

      return 0;

    }

    bio[b][x] = true;

  }

  for (int i = 0; i < 4; ++i) {

    int cnt = 0;

    for (int j = 1; j <= 13; ++j)

      if (bio[i][j])

	++cnt;

    printf("%d ",13 - cnt);

  }

  printf("\n");

  return 0;

}

Code-AKCIJA:

#include <cstdio>

#include <algorithm>

using namespace std;

#define MAXN 100000

typedef long long llint;

int C[MAXN];

bool cmp(int a, int b) {

  return a > b;

}

int main(void) {

  int n; scanf ("%d", &n);

  for (int i = 0; i < n; i++) {

    scanf ("%d", &C[i]);

  }

  sort(C, C+n, cmp);

  llint sol = 0;

  for (int i = 0; i < n; i++) {

    if (i % 3 == 2) {

      continue;

    }

    sol += C[i];

  }

  printf ("%lld\n", sol);

  return 0;

}

Code-BALONI:

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <set>

using namespace std;

const int MAXN = 1 << 20;

int n;

set <int> S[MAXN];

int find (int pos, int v) {

  set<int>::iterator it = S[v].lower_bound(pos);

  if (it == S[v].end()) return -1;

  return *it;

}

int v[MAXN];

int main (void){

  scanf("%d", &n);

  for (int i = 0; i < n; ++i) {

    scanf("%d", &v[i]);

    S[v[i]].insert(i);

  }

  int ans = 0;

  for (int i = 0; i < n; ++i) {

   if (S[v[i]].count(i) == 0) continue;

   int pos = i;

   ++ans;

   while (pos >= 0) {

      S[v[pos]].erase(pos);

      pos = find(pos, v[pos] - 1);

   }

  }

  printf("%d\n", ans);

  return 0;

}

Code-TOPOVI:

#include <cstdio>

#include <iostream>

#include <map>

using namespace std;

int n, k, q;

long long sol;

map <int, int> rcnt, ccnt;

map <int, int> rxor, cxor;

map <pair<int, int>, int> rook;

void moveRook(int r, int c, int val) {

  sol -= n - ccnt[rxor[r]];

  sol -= n - rcnt[cxor[c]];

  if (rxor[r] != cxor[c])

    sol += 1;

  --rcnt[rxor[r]];

  rxor[r] ^= val;

  ++rcnt[rxor[r]];

  --ccnt[cxor[c]];

  cxor[c] ^= val;

  ++ccnt[cxor[c]];

  sol += n - ccnt[rxor[r]];

  sol += n - rcnt[cxor[c]];

  if (rxor[r] != cxor[c])

    sol -= 1;

  rook[make_pair(r, c)] ^= val;

}

void init(void) {

  scanf("%d %d %d",&n,&k,&q);

  rcnt[0] = ccnt[0] = n;

  for (int i = 0; i < k; ++i) {

    int r, c, val;

    scanf("%d %d %d",&r,&c,&val);

    --r;

    --c;

    moveRook(r, c, val);

  }

}

void solve(void) {

  while (q-- > 0) {

    int r1, c1, r2, c2;

    scanf("%d %d %d %d",&r1,&c1,&r2,&c2);

    --r1; --c1;

    --r2; --c2;

    int rookValue = rook[make_pair(r1, c1)];

    moveRook(r1, c1, rookValue);

    moveRook(r2, c2, rookValue);

    printf("%lld\n",sol);

  }

}

int main(void) {

  init();

  solve();

  return 0;

}

Code-RELATIVNOST:

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

typedef unsigned int uint;

const int MAXN = 100005;

const int MAXC = 21;

const int mod = 10007;

int n, c, q;

int a[MAXN];

int b[MAXN];

int T[2 * MAXN][MAXC];

void update(int x) {

  for (int i = 0; i <= c; ++i) T[x][i] = 0;

  for (int i = 0; i <= c; ++i)

    for (int j = 0; j <= c; ++j)

      T[x][min(i + j, c)] += (T[x * 2][i] * T[x * 2 + 1][j]) % mod;

  for (int i = 0; i <= c; ++i) T[x][i] %= mod;

}

void change(int x) {

  x += n;

  memset(T[x], 0, sizeof T[x]);

  T[x][1] = a[x - n] % mod;

  T[x][0] = b[x - n] % mod;

  for (x /= 2; x > 0; x /= 2) update(x);

}

int main(void) {

  scanf("%d%d", &n, &c);

  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

  for (int i = 0; i < n; ++i) scanf("%d", &b[i]);

  for (int i = 0; i < n; ++i) {

    T[i + n][0] = b[i] % mod;

    T[i + n][1] = a[i] % mod;

  }

  for (int i = n-1; i >= 1; --i)

    update(i);

  scanf("%d", &q);

  for (int i = 0; i < q; ++i) {

    int p;

    scanf("%d", &p); --p;

    scanf("%d%d", &a[p], &b[p]);

    change(p);

    printf("%d\n", T[1][c]);

  }

  return 0;

}

Code-UZASTOPNI:

#include <cstdio>

#include <iostream>

#include <cstring>

#include <bitset>

#include <vector>

#define lo first

#define hi second

using namespace std;

using interval = pair<int, int>;

const int MAXN = 10010;

const int MAXK = 110;

int n, v[MAXN];

vector<int> e[MAXN];

vector<interval> s[MAXN];

vector<int> q[MAXK];

bitset<MAXK> flag[MAXN][MAXK];

void dfs(int x) {

  for (auto y : e[x])

    dfs(y);

  for (int i = 0; i < MAXK; ++i)

    q[i].clear();

  for (auto y : e[x]) {

    for (auto it : s[y])

      q[it.lo].push_back(it.hi);

  }

  for (int lo = MAXK - 1; lo >= 1; --lo) {

    if (lo == v[x]) {

      flag[x][lo] |= flag[x][lo + 1];

      flag[x][lo].set(lo);

    } else {

      for (auto hi : q[lo]) {

      	if (hi < v[x] || lo > v[x]) {

      	  flag[x][lo] |= flag[x][hi + 1];

      	  flag[x][lo].set(hi);

      	}

      }

    }

    for (int hi = MAXK - 1; hi >= lo; --hi)

      if (flag[x][lo].test(hi) && v[x] >= lo && v[x] <= hi) {

    	s[x].emplace_back(lo, hi);

      }

  }

}

void init(void) {

  scanf("%d",&n);

  for (int i = 0; i < n; ++i)

    scanf("%d",&v[i]);

  for (int i = 0; i < n - 1; ++i) {

    int a, b;

    scanf("%d %d",&a,&b);

    --a;

    --b;

    e[a].push_back(b);

  }

}

void solve(void) {

  dfs(0);

  printf("%d\n",s[0].size());

}

int main(void) {

  init();

  solve();

  return 0;

}

巴特西

COCI 2015、2016 1st round 题解（官方）

官方题解：

官方代码：

最新文章

热门文章