2019 Multi-University Training Conteest 4
59398 ワード
13分で08切ったらすごい自信をくれましたが、07年はまた私の頭に立ってくれました.1001 AND MinimSpanning Tree.
すべての数に対して、私たちは2進法の下で一番右側の0を探してもいいです.
解法:n/kを偶数と仮定して、例を挙げます.1 2 4 5、6、k=3とすると、明らかに1と6は1セット、2と5セット、3と4セット、n/kが奇数なら、どう置きますか?詳しく分析してもいけません.例を挙げてみます.1 2、4、6、8、10、14は6、4とセットで、12は7、5とセットでいいです.あなたも法則を発見できると思います.
解法:まず、持久化された線分樹を作成し、二分答案ansを作成し、線分樹から[p-ans,p+ans]の区間とk以上を調べてください.
解法:各数nに対して、10000以内の素数を列挙して、nを素数に分解します.nが1でないと、4つの場合があります.nは一つの素数の4乗、nは一つの素数の3乗、nは一つの素数の2乗、nは一つまたは複数の異なる素数を掛け合わせて、それぞれ判断すればいいです.
すべての数に対して、私たちは2進法の下で一番右側の0を探してもいいです.
#include
using namespace std;
const int maxn = 1e6 + 10;
int ans[maxn];
int main() {
int T;
cin>>T;
while (T--) {
int n;
cin>>n;
for (int i = 1; i <= n; i++)
p[i] = i;
int res = 0;
for (int i = 1; i <= n; i++) {
int flag = -1;
for (int j = 0; (1 << j) <= n; j++)
if (!(i >> j & 1)) {
flag = (1 << j);
break;
}
if (flag == -1)
ans[i] = 1, res += 1;
else
ans[i] = flag;
}
printf("%d
", res);
for (int i = 2; i <= n; i++)
printf("%d%c", ans[i], (i == n) ? '
' : ' ');
}
}
1003 Divide the Stors解法:n/kを偶数と仮定して、例を挙げます.1 2 4 5、6、k=3とすると、明らかに1と6は1セット、2と5セット、3と4セット、n/kが奇数なら、どう置きますか?詳しく分析してもいけません.例を挙げてみます.1 2、4、6、8、10、14は6、4とセットで、12は7、5とセットでいいです.あなたも法則を発見できると思います.
#include
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
vector<int> G[maxn];
int main() {
int Cas;
scanf("%d", &Cas);
while (Cas--) {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= k; i++)
G[i].clear();
if (k == 1) {
puts("yes");
for (int i = 1; i <= n; i++)
printf("%d%c", i, (i == n) ? '
' : ' ');
continue;
}
int m = n / k;
if ((n / k) % 2 == 0) {
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= k; j++) {
int v = (i - 1) * k + j;
int cur = j;
if (i % 2 == 0)
cur = k + 1 - j;
G[cur].push_back(v);
}
}
puts("yes");
for (int i = 1; i <= k; i++)
for (int j = 0; j < G[i].size(); j++)
printf("%d%c", G[i][j], (j == G[i].size() - 1) ? '
' : ' ');
continue;
}
int ok = 1;
for (int i = 4; i <= m; i++) {
for (int j = 1; j <= k; j++) {
int v = (i - 1) * k + j;
int cur = j;
if (i % 2 == 0)
cur = k + 1 - j;
G[cur].push_back(v);
}
}
ll T = 1ll * (1 + 3 * k) * (3 * k) / 2;
if (T % k)
ok = 0;
if (ok) {
T /= k;
for (int i = 3 * k; i > 2 * k; i--) {
int cur = i % k;
if (!cur)
cur = k;
cur = k - cur + 1;
G[cur].push_back(i);
ll tmp = T - i;
if (cur % 2) {
int tmp2 = cur / 2;
G[cur].push_back(tmp2 + 1);
G[cur].push_back(tmp - tmp2 - 1);
}
else {
int tmp2 = cur / 2 + k;
G[cur].push_back(tmp2);
G[cur].push_back(tmp - tmp2);
}
}
}
if (!ok)
puts("no");
else {
puts("yes");
for (int i = 1; i <= k; i++)
for (int j = 0; j < G[i].size(); j++)
printf("%d%c", G[i][j], (j == G[i].size() - 1) ? '
' : ' ');
}
}
}
1006 Horseが1007 Just an Old Pzleを追加します.この問題の難易度はこんなに多くの人がacをするべきではないです.1008 K-th Cloosest Distance.解法:まず、持久化された線分樹を作成し、二分答案ansを作成し、線分樹から[p-ans,p+ans]の区間とk以上を調べてください.
#include
using namespace std;
const int maxn = 1e5 + 10, N = 1e6;
int rt[maxn], ls[maxn * 22], rs[maxn * 22], sum[maxn * 22], cnt;
#define m (l + r) / 2
void up(int &o, int pre, int l, int r, int k) {
o = ++cnt;
sum[o] = sum[pre] + 1;
ls[o] = ls[pre];
rs[o] = rs[pre];
if (l == r)
return;
if (k <= m)
up(ls[o], ls[pre], l, m, k);
else
up(rs[o], rs[pre], m + 1, r, k);
}
int qu(int o, int pre, int l, int r, int ql, int qr) {
if (l >= ql && r <= qr)
return sum[o] - sum[pre];
int res = 0;
if (ql <= m)
res += qu(ls[o], ls[pre], l, m, ql, qr);
if (qr > m)
res += qu(rs[o], rs[pre], m + 1, r, ql, qr);
return res;
}
int gao(int x, int len, int l, int r) {
int L = max(x - len, 1);
int R = min(x + len, N);
return qu(rt[r], rt[l - 1], 1, N, L, R);
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, q, x, l, r, p, k, ans = 0;
cnt = 0;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
up(rt[i], rt[i - 1], 1, N, x);
}
while (q--) {
scanf("%d%d%d%d", &l, &r, &p, &k);
l ^= ans, r ^= ans, p ^= ans, k ^= ans;
int L = 0, R = 1e6;
while (L < R) {
int mid = (L + R) / 2;
if (gao(p, mid, l, r) < k)
L = mid + 1;
else
R = mid;
}
printf("%d
", ans = L);
}
}
}
1010 Minimal Power of Prime解法:各数nに対して、10000以内の素数を列挙して、nを素数に分解します.nが1でないと、4つの場合があります.nは一つの素数の4乗、nは一つの素数の3乗、nは一つの素数の2乗、nは一つまたは複数の異なる素数を掛け合わせて、それぞれ判断すればいいです.
#include
#define ll long long
using namespace std;
const int maxn = 1e4 + 100;
int vis[maxn], pri[maxn], cnt;
void init(int n) {
for (int i = 2; i <= n; i++) {
if (!vis[i])
pri[++cnt] = i;
for (int j = 1; j <= cnt && pri[j] * i <= n; j++) {
vis[i * pri[j]] = 1;
if (i % pri[j] == 0)
break;
}
}
}
ll gao(ll x, int y) {
ll res = 1;
while (y) {
res *= x;
y--;
}
return res;
}
int main() {
int T;
scanf("%d", &T);
init(maxn - 1);
while (T--) {
ll n;
scanf("%lld", &n);
int ans = 199;
for (int i = 1; i <= cnt && pri[i] <= n; i++)
if (n % pri[i] == 0) {
int res = 0;
while (n % pri[i] == 0)
res++, n /= pri[i];
ans = min(ans, res);
}
if (n == 1) {
printf("%d
", ans);
continue;
}
int x = pow(n, 1.0 / 4);
if (gao(x, 4) == n || gao(x + 1, 4) == n || gao(x - 1, 4) == n)
ans = min(ans, 4);
else {
x = pow(n, 1.0 / 3);
if (gao(x, 3) == n || gao(x + 1, 3) == n || gao(x - 1, 3) == n)
ans = min(ans, 3);
else {
int x = pow(n, 0.5);
if (gao(x, 2) == n || gao(x + 1, 2) == n || gao(x - 1, 2) == n)
ans = min(ans, 2);
else
ans = 1;
}
}
printf("%d
", ans);
}
}