Codeforces Round #538 (Div. 2) (CF1114)
8583 ワード
Codeforces Round #538 (Div. 2) (CF1114)
今日の昨夜のcfはとても惨めだった(淮中最低レベルを代表しているだけだ.
まずゆっくりとAがB、Cを落としてから、鉄棒Dを始めます.そこでO(n^2)の線形dpを書き出し、wa 6にして終了にします.終わった後、完全に2つの言葉を見落としたことに気づいた.ああ、スタート地点!!!
それから自分がこの試合で+0になる可能性があると計算して、どうせ0ぐらいです.終わってからDを書き始め、ついでにFを考えます.结局Dを书き终わってAがどのようにfstを発见して、それから..似たような文をコピーして貼るのに慣れているので、変えていないものもあります.3つの文はすべて-a!!!(これはまだptを過ぎることができますか?
Fを考えたついでに見てみました.どうしてBもfstになったの??同じ数を考えるのを忘れたような気がする..
まだCにはfstがありません.だから多くないかもしれませんが、前の試合で上がった点数を差し引くことができます.
もwph先輩が言ったほうがいいです.これらは血で変えた教訓ですね.(でも問題を間違えたのは本当にいけません.これはNOIPで犯した間違いですね.
A. Got Any Grapes?
この問題は直接やって、明らかにできるだけAndrewを供給して、それからDmitryで、最後にMichalです.
私が犯した過ちを犯さないでほしい.(後で似たような内容をコピーして貼り付けるときは、修正すべきものをすべて修正するように注意しましょう)
B. Yet Another Array Partitioning Task
CF上のB題は一般的に大胆に結論を当てる問題である.
直接結論を当てる:必ず前(mcdot k)の大きい数をそろえることができる.そして分けるときは前の(mcdot k)の大きな数の中の数を揃えるだけで、1枚切ることができます.
注意して(私のfstの原因でもあります)、前(mcdot k)の中で最小の数が全部選ばれていない場合は、その数が何個選ばれたのか、足りない場合は計算しないように注意してください.
C. Trailing Loves (or L'oeufs?)
(b)進数の末尾に(k)個の0があるので、説明する
\[\quad b ^ k | n!\]
そこで我々は(b)分解素因数[(p_1^{k_1}cdot p_2^{k_2}cdotcdotcdots)^k|n!]cdots}] に至っては(log_p{n!})どのように求めて、これは普及グループの知識であるべきです.[\log_p n!=\sum_{i = 1}\lfloor\frac n {p ^ i}\rfloor\]
D. Flood Fill
この問題は最初から始まりのブロックというものが見えず、ずっとwa 6だった.
開始点があれば区間dpテンプレートです.
設定(dp[i][j])は(i..j)を表すこの区間がすべて1色の代価になる.[ dp[i][j] =\left\{\begin{align*} &dp[i+1][j-1] &&c[i] = c[j]\\&\min\{dp[i][j-1], dp[i][j+1]\} + 1 &&c[i] eq c[j]\end{align*}\right.\]
E. Arithmetic Progression
インタラクティブな問題は心身を娯楽する.
私たちは2点で最大値を喜んで求めることができるのは明らかです.
次に,任意の2つの数の差が公差の倍数であるべきであることが分かった.そこで私たちはランダムにいくつかの位置を多くして、前の2分が過ぎたため、後で最大30回ぐらい(もちろん前の30個を直接聞くことができなくて、毒腫がカードを防ぐことができます)、位置の値と最大値の差を計算して、それでは公差はきっとそれらの約数で、大きな概率は(gcd)です.
ジルコニアは正確率を証明しない.
F. Please, another Queries on Array?
Euler関数の式をレビューします.[varphi(n)=nsum_{ptext{はい}ntext{素因数}}1-frac 1 p]
最初はbitsetを使うつもりでしたが、(300)以内の質量数は(62)個しかなく、少なくなく、直接
注意区间乘积,乘标记在区间上算贡献要以幂的形式算上去,而不是像求区间和那样直接乘.最初は気づかなかったが、死んでも生きられない.また
転載先:https://www.cnblogs.com/hankeke/p/CF1114.html
今日の昨夜のcfはとても惨めだった(淮中最低レベルを代表しているだけだ.
まずゆっくりとAがB、Cを落としてから、鉄棒Dを始めます.そこでO(n^2)の線形dpを書き出し、wa 6にして終了にします.終わった後、完全に2つの言葉を見落としたことに気づいた.ああ、スタート地点!!!
それから自分がこの試合で+0になる可能性があると計算して、どうせ0ぐらいです.終わってからDを書き始め、ついでにFを考えます.结局Dを书き终わってAがどのようにfstを発见して、それから..似たような文をコピーして貼るのに慣れているので、変えていないものもあります.3つの文はすべて-a!!!(これはまだptを過ぎることができますか?
Fを考えたついでに見てみました.どうしてBもfstになったの??同じ数を考えるのを忘れたような気がする..
まだCにはfstがありません.だから多くないかもしれませんが、前の試合で上がった点数を差し引くことができます.
もwph先輩が言ったほうがいいです.これらは血で変えた教訓ですね.(でも問題を間違えたのは本当にいけません.これはNOIPで犯した間違いですね.
A. Got Any Grapes?
この問題は直接やって、明らかにできるだけAndrewを供給して、それからDmitryで、最後にMichalです.
私が犯した過ちを犯さないでほしい.(後で似たような内容をコピーして貼り付けるときは、修正すべきものをすべて修正するように注意しましょう)
int x, y, z, a, b, c;
inline void End() {puts("NO"); exit(0);}
int main() {
read(a), read(b), read(c);
read(x), read(y), read(z);
if (x < a) End(); else x -= a;
y += x;
if (y < b) End(); else y -= b;
z += y;
if (z < c) End(); else z -= c;
puts("YES");
}B. Yet Another Array Partitioning Task
CF上のB題は一般的に大胆に結論を当てる問題である.
直接結論を当てる:必ず前(mcdot k)の大きい数をそろえることができる.そして分けるときは前の(mcdot k)の大きな数の中の数を揃えるだけで、1枚切ることができます.
注意して(私のfstの原因でもあります)、前(mcdot k)の中で最小の数が全部選ばれていない場合は、その数が何個選ばれたのか、足りない場合は計算しないように注意してください.
const int N = 2e5 + 7;
int n, m, k, p, a[N], b[N];
ll ans;
std::map mp;
int main() {
read(n), read(m), read(k); p = m * k; --k;
for (int i = 1; i <= n; ++i) read(a[i]), b[i] = a[i];
std::sort(b + 1, b + n + 1);
for (int i = n - p + 1; i <= n; ++i) ans += b[i], mp[b[i]]++;
printf("%I64d
", ans);
for (int i = 1, cnt = 0; i <= n; ++i) {
if (mp.count(a[i]) && mp[a[i]]) ++cnt, --mp[a[i]];
if (cnt == m) --k, printf("%d%c", i, "
"[k == 0]), cnt = 0;
if (!k) return 0;
}
} C. Trailing Loves (or L'oeufs?)
(b)進数の末尾に(k)個の0があるので、説明する
\[\quad b ^ k | n!\]
そこで我々は(b)分解素因数[(p_1^{k_1}cdot p_2^{k_2}cdotcdotcdots)^k|n!]cdots}] に至っては(log_p{n!})どのように求めて、これは普及グループの知識であるべきです.[\log_p n!=\sum_{i = 1}\lfloor\frac n {p ^ i}\rfloor\]
const int N = 1e6 + 7;
ll n, m, ans = 0x7fffffffffffffff;
int np[N], p[N], prt, cnt[N];
inline void Make_Prime(int n ){
np[0] = np[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!np[i]) p[++prt] = i;
for (int j = 1; j <= prt && i * p[j] <= n; ++j) {
np[i * p[j]] = 1;
if (i % p[j]) break;
}
}
}
inline ll GetNum(ll n, ll x) {
ll ans = 0;
while (n) ans += n /= x;
return ans;
}
int main() {
read(n), read(m);
Make_Prime(sqrt(m));
ll hkk = m;
for (int i = 1; i <= prt; ++i)
while (hkk % p[i] == 0) hkk /= p[i], ++cnt[i];
for (int i = 1; i <= prt; ++i) if (cnt[i]) SMIN(ans, GetNum(n, p[i]) / cnt[i]);
if (hkk > 1) SMIN(ans, GetNum(n, hkk));
printf("%I64d
", ans);
}D. Flood Fill
この問題は最初から始まりのブロックというものが見えず、ずっとwa 6だった.
開始点があれば区間dpテンプレートです.
設定(dp[i][j])は(i..j)を表すこの区間がすべて1色の代価になる.[ dp[i][j] =\left\{\begin{align*} &dp[i+1][j-1] &&c[i] = c[j]\\&\min\{dp[i][j-1], dp[i][j+1]\} + 1 &&c[i] eq c[j]\end{align*}\right.\]
const int N = 5000 + 7;
const int INF = 0x3f3f3f3f;
int n, m, c[N], dp[N][N];
int main() {
read(n);
for (int i = 1; i <= n; ++i) read(c[i]), SMAX(m, c[i]);
n = std::unique(c + 1, c + n +1) - c - 1;
for (int i = n; i; --i)
for (int j = i + 1; j <= n; ++j)
if(c[i] == c[j]) dp[i][j] = dp[i + 1][j - 1] + 1;
else dp[i][j] = std::min(dp[i][j - 1], dp[i + 1][j]) + 1;
printf("%d
", dp[1][n]);
}E. Arithmetic Progression
インタラクティブな問題は心身を娯楽する.
私たちは2点で最大値を喜んで求めることができるのは明らかです.
次に,任意の2つの数の差が公差の倍数であるべきであることが分かった.そこで私たちはランダムにいくつかの位置を多くして、前の2分が過ぎたため、後で最大30回ぐらい(もちろん前の30個を直接聞くことができなくて、毒腫がカードを防ぐことができます)、位置の値と最大値の差を計算して、それでは公差はきっとそれらの約数で、大きな概率は(gcd)です.
ジルコニアは正確率を証明しない.
const int N = 1e6 + 7;
int n, L, R, stp, used[N];
int main() {
read(n); srand(time(0));
int l = 0, r = 1e9;
while (l < r) {
int mid = (l + r) >> 1, get;
printf("> %d
", mid); fflush(stdout);
read(get);
if(get) l = mid + 1;
else r = mid;
}
R = l;
for (int i = 1, get = 0; i <= 30 && i <= n; ++i) {
int pos = rand() % n + 1;
while(used[pos]) pos = rand() % n + 1;
used[pos] = 1;
printf("? %d
", pos); fflush(stdout);
read(get);
stp = std::__gcd(stp, R - get);
}
printf("! %d %d
", R - (n - 1) * stp, stp);
fflush(stdout);
}F. Please, another Queries on Array?
Euler関数の式をレビューします.[varphi(n)=nsum_{ptext{はい}ntext{素因数}}1-frac 1 p]
最初はbitsetを使うつもりでしたが、(300)以内の質量数は(62)個しかなく、少なくなく、直接
ullで保存できることがわかりました.llくらいで十分です.注意区间乘积,乘标记在区间上算贡献要以幂的形式算上去,而不是像求区间和那样直接乘.最初は気づかなかったが、死んでも生きられない.また
ullで圧位されている場合は、注意して集合を計算するときに1 << iを1ull << iと書く.#define lc o << 1
#define rc o << 1 | 1
typedef std::pair pli;
const int N = 4e5 + 7;
const int M = 300 + 7;
const int P = 1e9 + 7;
int n, m, x, y, z, a[N];
char opt[15];
int prt, p[M], np[M], inv[N], id[N];
inline void Make_Prime(int n) {
np[0] = np[1] = inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (ll)(P - P / i) * inv[P % i] % P;
if (!np[i]) p[++prt] = i, id[i] = prt;
for (int j = 1; j <= prt && i * p[j] <= n; ++j){
np[i * p[j]] = j;
if (i % p[j] == 0) break;
}
}
}
inline pli operator + (const pli &a, const pli &b) {return pli(a.fi | b.fi, (ll)a.se * b.se % P);}
inline int fpow(int x, int y) {
int ans = 1;
for (; y; y >>= 1, x= (ll)x * x % P) if(y & 1) ans = (ll)ans * x % P;
return ans;
}
struct Node {
ull val, add;
int mul, tag;
} t[N << 2];
inline void Build(int o, int L, int R) {
t[o].tag = 1;
if (L == R) {
int x = a[L]; t[o].mul = a[L];
while (x > 1 && np[x]) t[o].val |= 1ull << (np[x] - 1), x /= p[np[x]];
if (x > 1) t[o].val |= 1ull << (id[x] - 1); return;
}
int M = (L + R) >> 1;
Build(lc, L, M); Build(rc, M + 1, R);
t[o].val = t[lc].val | t[rc].val; t[o].mul = (ll)t[lc].mul * t[rc].mul % P;
}
inline void Mul(int o, int L, int R, int l, int r, int x, ull y) {
if (l <= L && R <= r) {
t[o].tag = (ll)t[o].tag * x % P;
t[o].mul = (ll)t[o].mul * fpow(x, R - L + 1) % P;
t[o].add |= y; t[o].val |= t[o].add; return;
}
int M = (L + R) >> 1;
if (l <= M) Mul(lc, L, M, l, r, x, y);
if (r > M) Mul(rc, M + 1, R, l, r, x, y);
t[o].val = t[lc].val | t[rc].val | t[o].add;
t[o].mul = (ll)t[lc].mul * t[rc].mul % P *fpow(t[o].tag, R - L + 1) % P;
}
inline pli Get(int o, int L, int R, int l, int r, pli add = pli(0, 1)) {
if (l <= L && R <= r) return pli(t[o].val, t[o].mul) + pli(add.fi, fpow(add.se, R - L + 1));
int M = (L + R) >> 1; pli hkk = add + pli(t[o].add, t[o].tag);
if (r <= M) return Get(lc, L, M, l, r, hkk);
if (l > M) return Get(rc, M + 1, R, l, r, hkk);
return Get(lc, L, M, l, r, hkk) + Get(rc, M + 1, R, l, r, hkk);
}
inline int GetAns(pli x) {
int ans = x.se; ull S = x.fi;
for (int i = 1; i <= prt; ++i)
if((S >> (i - 1)) & 1) ans = (ll)ans * inv[p[i]] % P * (p[i] - 1) % P;
return ans;
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
read(n), read(m); Make_Prime(300);
for (int i = 1; i <= n; ++i) read(a[i]);
Build(1, 1, n);
for (int i = 1; i <= m; ++i) {
scanf("%s", opt); read(x), read(y);
if (*opt == 'M') {
read(z); ull hkk = 0; int r = z;
while (r > 1 && np[r]) hkk |= 1ull << (np[r] - 1), r /= p[np[r]];
if (r > 1) hkk |= 1ull << (id[r] - 1);
Mul(1, 1, n, x, y, z, hkk);
}
else printf("%d
", GetAns(Get(1, 1, n, x, y)));
}
} 転載先:https://www.cnblogs.com/hankeke/p/CF1114.html