A
素因数分解をしましょう。脳みそが常人の1%にも満たないから2回WAを出す。
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <map> #include <vector> #include <sstream> #include <typeinfo> #include <queue> #include <stack> #include <tuple> using namespace std; typedef long long ll; int main(int argc, char *argv[]) { int N; cin >> N; for (int i = 2; i*i <= N; i++) { if (N % i == 0) { printf("NO\n"); return 0; } } printf("YES\n"); return 0; }
B
一瞬詰まるよね。
今何個連続で上昇しているか、と、一個前の値
だけを持っていればよいです。
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <map> #include <vector> #include <sstream> #include <typeinfo> #include <queue> #include <stack> #include <tuple> using namespace std; const int INT_INF = (1 << 29); typedef long long ll; int main(int argc, char *argv[]) { int N, K; cin >> N >> K; int d1 = INT_INF, d2; int c = 0, r = 0; for (int i = 0; i < N; i++) { scanf("%d", &d2); if (d1 < d2) { c++; } else { c = 0; } d1 = d2; if (K <= c+1) r++; } printf("%d\n", r); return 0; }
C
半分全列挙?というやつですね
最初の16個が作れる値、65536個を全列挙。
次に後半16個が作れる値を全列挙します。
後半16個が作れる値それぞれについて(Dとする)、前半16個の作れる値のうちX-Dの個数を足していけばいいですね。
X-Dの個数を探すところでは二部探索をしましょう
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <map> #include <vector> #include <sstream> #include <typeinfo> #include <queue> #include <stack> #include <tuple> using namespace std; const int MAX_N = 33; typedef long long ll; ll d[MAX_N]; vector<int> ch; int main(int argc, char *argv[]) { int N; ll X; cin >> N >> X; for (int i = 0; i < N; i++) { cin >> d[i]; } if (N <= 16) { for (int i = 0; i < (1<<N); i++) { int i2 = i; ll d2 = 0; for (int j = 0; j < N; j++) { if (i2 & (1 << j)) { d2 += d[j]; } } ch.push_back(d2); } sort(ch.begin(), ch.end()); printf("%ld\n", upper_bound(ch.begin(), ch.end(), X) - lower_bound(ch.begin(), ch.end(), X)); } else { ll r = 0; for (int i = 0; i < (1<<16); i++) { int i2 = i; ll d2 = 0; for (int j = 0; j < 16; j++) { if (i2 & (1 << j)) { d2 += d[j]; } } ch.push_back(d2); } sort(ch.begin(), ch.end()); N -= 16; for (int i = 0; i < (1<<N); i++) { int i2 = i; ll d2 = 0; for (int j = 0; j < N; j++) { if (i2 & (1 << j)) { d2 += d[j+16]; } } r += upper_bound(ch.begin(), ch.end(), X - d2) - lower_bound(ch.begin(), ch.end(), X - d2); } printf("%lld\n", r); } return 0; }
D
部分点解法
値の更新は1個のみ。
これは普通にセグメントツリーを使いましょう。
それぞれ、自分の子のgcdを持つようにすれば更新、取得ともにO(logn)で出来ます。
満点解法
値の更新が区間になります。
これは部分点解法だと、更新がO(nlogn)になり、間に合いません。
区間更新でも、a[i]-a[i-1]が変わるiはたかだか2つしか無い事に注目しましょう。
差に注目すると、
gcd(a1, a2, a3, ..., an) = gcd(a1, a2-a1, a3-a2, a4-a3, ..., an-a(n-1))
に気づきます。これが等しい証明はユーグリッドの互除法の原理から明らかです。
あとはa2-a1, a3-a2, ..., an-a(n-1)のn-1要素を持つセグメントツリーを考えれば、
更新、取得ともにO(logn)で出来ます。
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <map> #include <vector> #include <sstream> #include <typeinfo> #include <queue> #include <stack> #include <tuple> using namespace std; typedef long long ll; ll gcd(ll a, ll b) { a = abs(a); b = abs(b); if (b==0) return a; return gcd(b, a%b); } const int SEG_SIZE = 1<<18; int seg[SEG_SIZE]; void seg_init() { for (int i = 0; i < SEG_SIZE; i++) { seg[i] = 0; } } void seg_set(int *seg, int i, int x) { i += SEG_SIZE/2 - 1; seg[i] = x; while (i) { i = (i - 1) / 2; int s1 = seg[i*2+1], s2 = seg[i*2+2]; seg[i] = gcd(s1, s2); } } int seg_get(int *seg, int a, int b, int k = 0, int l = 0, int r = SEG_SIZE/2) { if (a <= l && r <= b) return seg[k]; if (r <= a || b <= l) return 0; int vl = seg_get(seg, a, b, k*2+1, l, (l+r)/2); int vr = seg_get(seg, a, b, k*2+2, (l+r)/2, r); return gcd(vl, vr); } ll bit[SEG_SIZE] = {}; int bit_sum(ll *d, int add) { add++; ll s = 0; while (add > 0) { s += d[add-1]; add -= add & -add; } return s; } void bit_add(ll *d, int add, ll x) { add++; while (add <= SEG_SIZE) { d[add-1] += x; add += add & -add; } } int d[SEG_SIZE]; int getd(int i) { return bit_sum(bit, i) + d[i]; } int main(int argc, char *argv[]) { int N; cin >> N; seg_init(); for (int i = 0; i < N; i++) { scanf("%d", &d[i]); } for (int i = 0; i < N-1; i++) { seg_set(seg, i, d[i+1]-d[i]); } int M; cin >> M; for (int i = 0; i < M; i++) { int t, l, r; scanf("%d %d %d", &t, &l, &r); l--; if (t) { bit_add(bit, l, t); bit_add(bit, r, -t); if (l) { seg_set(seg, l-1, getd(l)-getd(l-1)); } if (r) { seg_set(seg, r-1, getd(r)-getd(r-1)); } } else { printf("%lld\n", gcd(getd(l), seg_get(seg, l, r-1))); } } return 0; }