codeforces Round #259(div2) D解題報(bào)告
Jun 07, 2016 pm 03:18 PM
D. Little Pony and Harmony Chest time limit per test 4 seconds memory limit per test 256 megabytes input standard input output standard output Princess Twilight went to Celestia and Luna's old castle to research the chest from the Elements
D. Little Pony and Harmony Chest
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Princess Twilight went to Celestia and Luna's old castle to research the chest from the Elements of Harmony.
A sequence of positive integers?bi?is harmony if and only if for every two elements of the sequence their greatest common divisor equals 1. According to an ancient book, the key of the chest is a harmony sequence?bi?which minimizes the following expression:
You are given sequence?ai, help Princess Twilight to find the key.
Input
The first line contains an integer?n?(1?≤?n?≤?100) — the number of elements of the sequences?a?and?b. The next line contains?n?integersa1,?a2,?...,?an?(1?≤?ai?≤?30).
Output
Output the key — sequence?bi?that minimizes the sum described above. If there are multiple optimal sequences, you can output any of them.
Sample test(s)
input
5 1 1 1 1 1
output
1 1 1 1 1
input
5 1 6 4 2 8
output
1 5 3 1 8
題目大意：
給出N個(gè)數(shù)ai，求出另一個(gè)序列bi，要求sum |ai-bi|，最短，且所有的bi都互質(zhì)。
解法：
這里題目給了幾個(gè)很顯眼的條件，ai限制在了1~30之間，由于可以bi無限選1這個(gè)數(shù)，那么|ai-bi| 最大就是29了，意味著bi
要求所有的bi互質(zhì)，可以化為所有的bi分解出來的質(zhì)因數(shù)均不相同，bi
用s表示當(dāng)前階段用了哪些質(zhì)因數(shù)的狀態(tài)，例如 s = 3 = 11 代表目前狀態(tài)下使用了第一個(gè)和第二個(gè)質(zhì)因數(shù)。
很快我們就可以寫出狀態(tài)轉(zhuǎn)移方程：
? ? ? ?f[i][s] = min(f[i-1][s^c[k]] + abs(a[i] - k))。 ? ?其中c[k]表示數(shù)字k使用了哪些質(zhì)因數(shù)。
代碼：
#include <cstdio> #include <cmath> #include <cstring> #define M_max 60 #define N_max 123 #define inf 0x3f3f3f3f using namespace std; int p[N_max], c[M_max], a[N_max]; int f[N_max][1 </cstring></cmath></cstdio>
? AI ??
Undress AI Tool
??? ???? ??
Undresser.AI Undress
???? ?? ??? ??? ?? AI ?? ?
AI Clothes Remover
???? ?? ???? ??? AI ?????.
Clothoff.io
AI ? ???
Video Face Swap
??? ??? AI ?? ?? ??? ???? ?? ???? ??? ?? ????!
?? ??
??? ??
???++7.3.1
???? ?? ?? ?? ???
SublimeText3 ??? ??
??? ??, ???? ?? ????.
???? 13.0.1 ???
??? PHP ?? ?? ??
???? CS6
??? ? ?? ??
SublimeText3 Mac ??
? ??? ?? ?? ?????(SublimeText3)
MySQL?? ??? ?? ? ???? ??? ?????
Jul 08, 2025 am 02:51 AM
?? ?? ? ?? ?? ??? ??? ??? ?????? ?? ??? ??? ?????? ??? ?????? ?????? ??? ?????. ? ?? ?? ???? ????. ??, ??????, ??? ? ??? ?? ??? UTF8MB4? ???? ???? ShowCreatedAtabase/Table? ???? ? Alter ??? ??????. ??, ?????? ??? ? UTF8MB4 ?? ??? ???? ?? ?? ??? ????? SetNames? ??????. ??, ?? ??? ????? ???? UTF8MB4_UNICODE_CI? ???? ?? ? ????? ???? ???? ?????? ???? ?? ? ? ?? ?? ??? ????? ??????.
?? ? ?????? ???? MySQL ??????? ?????
Jul 07, 2025 am 01:50 AM
MySQL ??????? ???? ?? ???? ??? ?? ? ?????? ???? ????. ?? MySQL -U ??? ?? -P? ???? ????? ???? ???? ??? ?????? ??????. ?? ??????? ???? ?? ??? ??? ????? -h ?? ??? ???????. ??, mysql-u username-p database name ?? mysql-u username-p database name? ?? ??? ? ? ?? ??????? ?? ????? ??? ? ? SQL ??? ??? ? ????.
MySQL?? ???? ?? ? ?? ?? ??
Jul 08, 2025 am 02:50 AM
MySQL? ???? ??? ???? InnoDB ?? ??? ???? ??? ???? ???? ?????. 1. ????? ??? SQL ?? ????, ?? ?? ?? ?? ??? ?????. 2. ? ???? ???, ???, ?? ? ???? ?????. 3. ????? ???? ????? ??? STARTTRANSACTION, CONMING ? ROLLBACK???. 4. 4 ?? ?? ???? ?? ??, ?? ? ??, ?? ??? ?? ? ???? ?????. 5. ????? ???? ???? ?? ??? ??? ?? ??? ?? ?? ? ??? ????? ??????. ??? ????? ?? MySQL? ?? ???? ?? ??? ?? ? ? ????.
MySQL?? ??? ?? ? ???? ??
Jul 07, 2025 am 01:41 AM
MySQL? ?? ?? ? ???? ?? ??? ??? ??, ?? ?? ? ???? ??? ??? ? ?????. ??, ??? ??? UTF8MB4? ?? ?? ??? ?? ??? ?????. ?? ??? UTF8MB4_UNICODE_CI? ?? ?? ?? ??? ???? UTF8MB4_BIN? ?? ?????. ??, ?? ??? ?? ??? ??, ??????, ??? ? ??? ??? ? ????. ??? ??? ?? UTF8MB4 ? UTF8MB4_UNICODE_CI? ?? ? ???? ???? ?? ????. ??, ?? ??? ?? ??? ?? ???? ?? ??, ?? ?? ???? ??? ??? ?? ???? ???? ??? ???? ???? ???????. ?? ?? ??? ???? ?? ???? ? ??? ? ?? ??? ???????.
MySQL 8?? ?? ??? ??? (CTE)? ?????
Jul 12, 2025 am 02:23 AM
CTE? MySQL8.0?? ?? ? ???? ??? ??? ??? ? ?? ??? ??????. 1. CTE? ?? ?? ??? ?? ????? ???? ??? ??? ??? ?? ??? ?????. 2. ?? ??? ???? CTE? ? ?? ?? ??? ???? ????????. 3. ?? CTE? ?? ??? ?? ?? ? ???? ?? ? ? ?????, ?? ?? ?? ? ?? ??? ???????. 4. ?? ???? ?? ??, ?? ?? ??, ????? ?? ? ??? ??? ?????.
MySQL ?? ?? ??? ??
Jul 13, 2025 am 01:45 AM
MySQL ?? ?? ???? ???? ??? ??, SQL ?? ???, ??? ?? ?? ? ???? ??, ?? ? ???? ?? ??? ???? ?? ??? ???????. 1. ??? ?? ????? : ????? ???? ?? ???? ?? ??, ?? ??? ??? ???, ?? ? ??? ?????? ????, ??? ??? ?? ???? ???? ???, ?? ???? ?????. 2. SQL ?? ??? : ??*? ???, ???? ??? ???? ??, ?? ?? ??? ???, ??? ?? ??? ???????. 3. ??? ?? ?? ? ???? : ?? ? ?? ????? ?? ???? ?? ?? ??? ????, ??? ?? ??? ????, ????? ???? ????, ?? ???? ???? ????? ???? ???? ?????. 4. ?? ? ???? ?? : Redis ??? ???? ?????? ??? ??? ?? ??? ???????.
??? MySQL ?????? ?? ?? ??
Jul 08, 2025 am 02:45 AM
??? ??? MySQL ?? ???? ????? 1. ?? RTO ? RPO ???? ????? ????? ?? ??? ?? ?? ? ??? ?? ??? ???? ?? ?? ? ??? ??????. 2. ?? ?? ? ?? ??? ??? ???? ?? ?? ?? (? : MySQLDump), ??? ?? (? : PerconaxTrabackup) ? Binlog (Binlog) ? Binlog (Binlog)? ???? ????? ?? ??? ?????. 3. ??? ??? ???? ?? ??? ??? ??? ?? ????? ????? ???????. 4. ?? ??? ????, ??? ??, ?? ?? ?? ? ?? ?? ????? ??? ???? ?????? ??????.
MySQL?? ??? ?? ?? ???
Jul 09, 2025 am 01:26 AM
toptimizecomplexjoinoperationsinmysql, followfourkeysteps : 1) 1) ?? ComproperIndexingOnbothsidsidesofjoincolumns, ?? ComporIteIndexesFormulti-ColleumnJoinsandavoidinglargeVarCharIndexes; 2) ?? ? ?? ????
