题目大意:
一个十进制数字(不含0),各个位上的和为n(n<=1000),且相邻位没有相同的数字,问这个数字最大可以是多少。
思路:
显然要使这个数字最大的话,只能包含1和2。由于最后的数字会非常大,所以只能用字符串来存储。
有两种做法,一种是直接构造,一种是dp。
1.直接构造:
最后的数字形式一定是中间有一大串12,根据n%3的结果决定在开头加2还是在结尾加1或是不加。
2.dp做法:
dp[i][j]
表示各位和为i
,最后一位数字为j
时的最大数字,状态转移方程为:
dp[i+k][3-j] = max(dp[i][j] + k, dp[i+k][3-j])
dp代码:
#include
const int N = 1e3 + 50;
using namespace std;
string dp[N][3];
string digit[3] = {"0", "1", "2"};
string smax(string a, string b) //自定义字符串比较函数
{
if (a.size() != b.size())
return a.size() > b.size() ? a : b;
return max(a, b);
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
for (int i = 0; i <= 1000; i++)
{
for (int j = 0; j <= 2; j++)
{
if (j > i) break;
for (int k = 1; k <= 2; k++)
{
if (k == j) continue;
dp[i + k][k] = smax(dp[i][j] + digit[k], dp[i + k][k]);
}
}
}
int T;
cin >> T;
while (T--)
{
int n;
string ans;
cin >> n;
for (int i = 1; i <= 2; i++)
ans = smax(ans, dp[n][i]);
cout << ans << "\n";
}
return 0;
}
题目大意:
题目给了了 elegant矩形 的定义,就是一个矩形周围如果都是白色的块或是没有块,那么这个矩形就是elegant矩形,现在给定一个图,问图中所有的黑色矩形是否都是elegant矩形。1代表黑色,0代表白色。
思路:
知道了elegant矩形的定义后去判断就很容易了,对一个黑色的块进行bfs,记录行坐标和列坐标最大最小值,然后扫描整个矩形区域,看区域内是否有白色的块即可。如果不是elegant矩形,那么一定是在矩形的旁边有突出的黑色块,那么就会使得后面扫描的矩形区域扩大,扫描时就会出现白色块。
AC代码:
#include
const int N = 105;
using namespace std;
int n, m;
int dir[2][4] = {{0, 0, 1, -1}, {1, -1, 0, 0}};
char color[N][N];
bool vis[N][N];
bool check(int x, int y)
{
queue<int> qx, qy;
int max_x = x, max_y = y, min_x = x, min_y = y;
qx.push(x);
qy.push(y);
vis[x][y] = 1;
while (qx.size())
{
x = qx.front();
y = qy.front();
qx.pop();
qy.pop();
for (int i = 0; i < 4; i++)
{
int xx = x + dir[0][i];
int yy = y + dir[1][i];
if (color[xx][yy] == '0' || vis[xx][yy] || xx < 1 || xx > n || yy < 1 || yy > m) continue;
vis[xx][yy] = 1;
qx.push(xx);
qy.push(yy);
max_x = max(xx, max_x);
max_y = max(yy, max_y);
min_x = min(xx, min_x);
min_y = min(yy, min_y);
}
}
for (int i = min_x; i <= max_x; i++)
for (int j = min_y; j <= max_y; j++)
if (color[i][j] == '0') return 0;
return 1;
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> color[i] + 1;
for (int j = 1; j <= m; j++)
vis[i][j] = 0;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (vis[i][j] || color[i][j] == '0') continue;
if (!check(i, j))
{
cout << "NO\n";
return;
}
}
}
cout << "YES\n";
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
题目大意:
给定一个染色后的格子图,只有黑白两种颜色。现在只能以国际象棋棋盘的方式涂色,也就是左上角为白色,然后黑白相间这么涂,问是否能把全白的格子图涂成给定的格子图。
如果能涂,输出每次涂色的区域。
思路:
可以把涂色的方式拆分成横向涂色和竖向涂色,只要左侧或上方有白色的块,就能涂。所以只要整个棋盘左上角的格子是白色的,就一定有涂色的方案。为了避免白色将已经涂好的格子覆盖掉,可以从后往前涂。
所以先涂除了第一行和第一列的格子(为了给左侧和上方留白),最后再涂第一行和第一列的格子即可(因为左上角是白色,一定可以涂完)。
AC代码:
#include
const int N = 105;
using namespace std;
struct option
{
int x1, y1, x2, y2;
};
int n, m;
char color[N][N];
vector<option> ans;
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> color[i] + 1;
if (color[1][1] == '1')
{
cout << "-1\n";
return;
}
ans.clear();
for (int i = 2; i <= n; i++)
{
for (int j = m; j >= 2; j--)
{
if (color[i][j] == '1')
{
ans.push_back({i, j - 1, i, j});
}
}
}
for (int i = m; i >= 2; i--)
if (color[1][i] == '1') ans.push_back({1, i - 1, 1, i});
for (int i = n; i >= 2; i--)
if (color[i][1] == '1') ans.push_back({i - 1, 1, i, 1});
cout << ans.size() << "\n";
for (auto op : ans)
cout << op.x1 << " " << op.y1 << " " << op.x2 << " " << op.y2 << "\n";
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
题目大意:
给定一个数字d,定义good number为d的倍数,定义beautiful number为不能表示成两个good number乘积形式的good number。
给定一个数x,问x是否能表示成若干个beautiful number的乘积,如果有两种以上的表示方式,输出YES,否则输出NO。如果x本身就是beautiful number,也算一种方案。
思路:
beautiful number其实就是good number中那些不是d2倍数的数字。
为了求x能用beautiful number乘积表示的方案数,我们很自然的能想到先找出x的所有因数。然后问题就变成了从这些因数中选择若干个为beautiful number的因数进行相乘得到x,且每个因数可以选择的次数不限,有多少种方案。每个因数选择的次数不限,这有点像完全背包问题。
考虑dp,dp[i][j]
表示在前i
个因数中选择若干个相乘乘积为j
的方案数。
状态转移方程和完全背包问题也比较像,假设当前为第i+1
个因数k
:
dp[i+1][j*k] += dp[i][j]
因为因数的乘积比较大,而因数的数量比较少,且因数的乘积也还会是因数,否则无法整除,因此将因数映射成排序后的下标,这样就能开得下了。有一个技巧是小于105的因数用一个数组来存储下标,大于105的因数将其变成成对的那个因数后用另一个数组存下标。
由于状态转移方程只有加法,所以可以优化掉第一维。
AC代码:
#include
#define mem(a, v) memset(a, v, sizeof(a))
const int N = 1e5 + 5;
using namespace std;
// dp[i]表示乘积为i对应的映射值时的方案数
int dp[1500], id1[N], id2[N], x, d;
vector<int> fac;
inline int getid(int num) //由于数字范围过大,将数值映射成对应的下标
{
if (num < N) return id1[num];
return id2[x / num];
}
void solve()
{
cin >> x >> d;
fac.clear();
for (int i = 1; i * i <= x; i++) //因数分解
{
if (x % i == 0)
{
fac.push_back(i);
if (i * i != x) fac.push_back(x / i);
}
}
sort(fac.begin(), fac.end());
for (int i = 0; i < fac.size(); i++) //小于N的用id1数组记录下标,大于N的用id2数组记录下标
{
if (fac[i] < N)
id1[fac[i]] = i;
else
id2[x / fac[i]] = i;
}
mem(dp, 0);
dp[0] = 1;
//完全背包问题
for (int i = 0; i < fac.size(); i++) //选择前i+1个因数
{
if (fac[i] % d != 0 || fac[i] / d % d == 0) continue; //当前因数必须是beautiful数
for (int j = 0; j < fac.size(); j++) //当前的乘积为fac[j] * fac[i],向后推状态
{
if (x / fac[j] % fac[i] != 0) continue;
if (x / fac[j] < fac[i]) break;
dp[getid(fac[j] * fac[i])] += dp[getid(fac[j])];
}
if (dp[fac.size() - 1] >= 2) break; //已经确定有两组以上解了,提前退出循环
}
// dp[fac.size() - 1]表示乘积为x的方案数
if (dp[fac.size() - 1] >= 2)
cout << "YES\n";
else
cout << "NO\n";
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
solve();
return 0;
}