源代码:ACM/OpenjudgeNow/Codeforces at master · abmcar/ACM (github.com)
更好的阅读体验: 折跃坐标
碎碎念:不亏是俄罗斯场+二次元出题人,只能说头像越粉出题越狠
A. Madoka and Math Dad 题目大意: 思路:我们可以发现对于没有连续的数当中, 21212121 是和最小且最大的数,我们可以把21分为一组,问题转变为剩余部分
对于 n m o d 3 = = 0 n~mod~3 == 0 n mod 3==0 的情况 直接 21212121即可对于 n m o d 3 = = 1 n~mod~3 == 1 n mod 3==1 的情况 把1放到开头, 121212121对于 n m o d 3 = = 2 n~mod~3 == 2 n mod 3==2 的情况 把2放到末尾, 212121212 代码:
void solution()
{
cin >> n;
int tt = n;
if (n <= 2)
{
cout << n << endl;
return;
}
int fir;
if (n % 3 == 0)
fir = 2;
if (n % 3 == 1)
fir = 1;
if (n % 3 == 2)
fir = 2;
while (n > 0)
{
cout << fir;
n = n - fir;
if (fir == 1)
fir = 2;
else
fir = 1;
}
cout << endl;
}
B. Madoka and the Elegant Gift
题目大意:
思路:
可以发现如果存在相交情况,必定存在在一共2*2的方格内,有3个黑1个白的情况
因为枚举每一个2*2的方格,判断时候存在这种情况
代码:void solution()
{
cin >> n >> m;
vector bd(n + 2);
vector nums[Maxn];
for (int i = 1; i <= n; i++)
{
nums[i].resize(n + 2);
cin >> bd[i];
bd[i] = '-' + bd[i];
}
bool ok = true;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (bd[i][j] == '1')
{
if (i + 1 <= n && j + 1 <= m)
if (bd[i][j + 1] == '1' && bd[i + 1][j] == '1' && bd[i + 1][j + 1] == '0')
ok = false;
if (i + 1 <= n && j + 1 <= m)
if (bd[i][j + 1] == '1' && bd[i + 1][j] == '0' && bd[i + 1][j + 1] == '1')
ok = false;
if (i + 1 <= n && j + 1 <= m)
if (bd[i][j + 1] == '0' && bd[i + 1][j] == '1' && bd[i + 1][j + 1] == '1')
ok = false;
}
else
{
if (i + 1 <= n && j + 1 <= m)
if (bd[i][j + 1] == '1' && bd[i + 1][j] == '1' && bd[i + 1][j + 1] == '1')
ok = false;
}
}
}
if (ok)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
C. Madoka and Childish Pranks
题目大意:
思路:
发现题目没有要求使用最小次数,且次数小于n*m,因此我们可以对于每一个黑块,选择他和他上边或者左边的方块作为一共操作
只需要保证他上边和左边的方块在他之后被染色即可
因为倒着枚举每一个方块,进行染色, 由于是倒着染色, 黑色方块的左边和上边一定是白色
最后判断一下是否还存在黑色方块即可
代码:void solution()
{
cin >> n >> m;
vector bd(n + 1);
vector> newBd(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> bd[i];
newBd[i].resize(m + 1);
bd[i] = '-' + bd[i];
}
vector> opt1, opt2;
for (int i = n; i >= 1; i--)
for (int j = m; j >= 1; j--)
{
if (bd[i][j] == '1')
{
if (j - 1 >= 1 && newBd[i][j - 1] == 0)
{
opt1.push_back({i, j - 1});
opt2.push_back({i, j});
newBd[i][j] = 1;
bd[i][j] = '0';
}
else if (i - 1 >= 1 && newBd[i - 1][j] == 0)
{
opt1.push_back({i - 1, j});
opt2.push_back({i, j});
newBd[i][j] = 1;
bd[i][j] = '0';
}
}
}
bool ok = true;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (bd[i][j] == '1')
ok = false;
if (!ok)
{
cout << "-1" << endl;
return;
}
cout << opt1.size() << endl;
for (int i = 0; i < opt1.size(); i++)
cout << opt1[i].first << " " << opt1[i].second << " " << opt2[i].first << " " << opt2[i].second << endl;
}
D. Madoka and the Best School in Russia
题目大意:
思路:
这里采用分类讨论的方法
我们可以知道对于 good 数 $ g = k_1 * d$
对于beatiful 数 $b = k_2*d^2 且 k_2 modd neq 0 $
对于答案所求的数 x = b 1 ∗ b 2 ∗ b 3 ∗ . . . ∗ b n = k ∗ d p x = b_1*b_2*b_3*...*b_n = k * d^p x=b1∗b2∗b3∗...∗bn=k∗dp
我们分情况讨论:
如果 p < = 1 p <= 1 p<=1 不可能有2种情况 直接排除
如果 k 不是质数, 则有 x = ( a ∗ d ) ∗ ( b ∗ d ) ∗ d p − 2 = k ∗ d p x = (a*d)*(b*d)*d^{p-2} = k*d^p x=(a∗d)∗(b∗d)∗dp−2=k∗dp 由两种情况 满足
如果 k 是质数
如果 d 是质数,则不可再分 不满足如果 d 不是质数
如果 p = = 2 p == 2 p==2 不可再分如果 p = = 3 p == 3 p==3
如果 d = a ∗ b 且 ( k ∗ a m o d d ≠ 0 或 k ∗ b m o d d ≠ 0 ) d = a*b 且 (k*a~mod~dneq0 或 k*b~mod~dneq0) d=a∗b且(k∗a mod d=0或k∗b mod d=0) 则可以额外分为 x = ( a ∗ k ∗ d ) ∗ ( b ∗ d ) x = (a*k*d)*(b*d) x=(a∗k∗d)∗(b∗d)否则 不可再分 如果 p > = 4 p >=4 p>=4 则可以额外分为 x = ( a ∗ d ) ∗ ( b ∗ d ) ∗ ( k ∗ d ) ∗ d p − 4 x = (a*d)*(b*d)*(k*d)*d^{p-4} x=(a∗d)∗(b∗d)∗(k∗d)∗dp−4
由此,我们进行分情况判断即可
代码:void solution()
{
cin >> n >> d;
int cnt = 0;
while (n % d == 0)
{
cnt++;
n = n / d;
}
bool ok = false;
if (cnt >= 2)
{
if (!isPrime(n))
ok = true;
else
{
if (!isPrime(d))
if (cnt >= 4)
ok = true;
if (cnt == 3)
{
for (int i = 2; i * i <= d; i++)
{
if (d % i)
continue;
int t1 = i;
int t2 = d / i;
if (n * t1 % d || n * t2 % d)
ok = true;
}
}
}
}
if (ok)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
