Codeforces Round #167 (Div. 2)
今日は鉄緑会という塾の校内模試がありました.
鬱になったので出れなかった回のを解きました.
solved5outof5になると緑になるらしくて達成感が少し
a. やる
int n, s, ret; int main(){ cin >> n; rep(i, n){ int tmp; cin >> tmp; s += tmp; } FOR(i, 1, 6) if((s + i) % (n + 1) != 1) ++ret; cout << ret << endl; }
b. 眺めるとbitcountだ!!!となって適当に処理.
int n, seq[100010]; ll ans; int de[50]; int main(){ cin >> n; rep(i, n) cin >> seq[i]; rep(i, n) ++de[__builtin_popcount(seq[i])]; rep(i, 50) if(de[i]) ans += (ll)(de[i]) * (ll)(de[i] - 1) / 2LL; cout << ans << endl; return 0; }
c. 図を見る. 劣化テトリスやん. 要らないのになぜかsegtreeを書く
#define sz (1 << 17) int n, m; int a[100010]; struct segtree{ ll dat[1 << 18]; void init(){ rep(i, sz * 2 - 1) dat[i] = 0; } void update(int k, ll x){ k += sz - 1; dat[k] = x; while(k > 0){ k = (k - 1) / 2; dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2]); } } ll query(int a, int b, int k = 0, int l = 0, int r = sz){ if(r <= a || b <= l) return 0; if(a <= l && r <= b) return dat[k]; return max(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r)); } }seg; int main(){ cin >> n; seg.init(); rep(i, n){ cin >> a[i]; seg.update(i, (ll)a[i]); } cin >> m; rep(i, m){ int w, h; cin >> w >> h; ll mi = seg.query(0, w); cout << mi << endl; seg.update(0, mi + (ll)h); } return 0; }
d. Cです. 見るとx座標はsortされた状態になるので、適当に組み合わせを計算
int n; P a[200010]; ll comb[200010][3]; ll m; ll ret = 1LL; vector<int> xs; map<int, int> una; map<int, int> cnt[200010]; int main(){ cin >> n; rep(i, n) a[i].se = a[n + i].se = i; rep(i, n){ cin >> a[i].fi; xs.pb(a[i].fi); } rep(i, n){ cin >> a[n + i].fi; xs.pb(a[n + i].fi); } cin >> m; sort(ALL(xs)); xs.erase(unique(ALL(xs)), xs.end()); rep(i, xs.size()) una[xs[i]] = i; rep(i, n * 2) cnt[una[a[i].fi]][a[i].se]++; rep(i, 200010){ comb[i][0] = 1LL; comb[i][1] = (ll)i % m; comb[i+1][2] = (comb[i][2] + comb[i][1]) % m; } rep(i, xs.size()){ int sum = 0; foreach(cnt[i], itr) sum += itr->second; foreach(cnt[i], itr){ ret = ret * comb[sum][itr->second] % m; sum -= itr->second; } } cout << ret << endl; return 0; }
e. アカン頂点を順番に処理すればそのうち完成. -1実はならないんだよね
int n, m; vector<int> g[300010]; bool col[300010]; vector<int> que; inline bool ct(int v){ int ret = 0; rep(i, g[v].size()) if(col[v] == col[g[v][i]]) ++ret; return ret >= 2; } int main(){ cin >> n >> m; rep(i, m){ int a, b; cin >> a >> b; --a; --b; g[a].pb(b); g[b].pb(a); } while(true){ bool flag = false; rep(i, n){ if(ct(i)){ col[i] ^= 1; flag = true; } } if(!flag){ rep(i, n) cout << col[i] ? '0' : '1'; cout << endl; return 0; } } return 0; }