题目链接 题目大意: 给出一个整数n,现在可以对整数执行一个操作: 选择整数上两个不同位数的数字交换位置,然后移除整数最右边一位的数字; 重复这个过程,直到整数只剩下1位; 现在想知道这个剩下的数字最小可能为多少。
输入: 第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例俩行,第一行 整数 𝑛 (10≤𝑛≤1e9)
输出: 每个样例一行,剩下最小的数字;
Examples input 3 12 132 487456398 output 2 1 3
题目解析: 右边第二位是必胜位,每次都选择其他位数的数字进行交换,在只剩下2位数字的时候,将第一位和第二位交换,然后会去掉右边的数字,剩下原来右边第二位的数字; 也就是说,当时数字位数大于等于3的时候,可以选择整数上最小的数字,将这个数字放在右边第二位,再采用上面的策略必然可以留下来; 当数字位数只有2位时,留下来的数字必然是最右边的数字;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
if (n < 99) {
cout << n % 10 << endl;
}
else {
int ans = 9;
while (n) {
ans = min(ans, n % 10);
n /= 10;
}
cout << ans << endl;
}
}
}
}
ac;
题目链接 题目大意: 给出整数a,b,c,满足a<b<c; 构造三个整数x,y,z,满足: x mod y = a; y mod z = b; z mod x = c;
输入: 第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例一行,𝑎 , 𝑏, 𝑐 (1≤𝑎<𝑏<𝑐≤1e8).
输出: 每个样例一行,输出满足的𝑥 , 𝑦, 𝑧 (1≤𝑥,𝑦,𝑧≤1e18)
Examples input 4 1 3 4 127 234 421 2 7 8 59 94 388 output 12 11 4 1063 234 1484 25 23 8 2221 94 2609
题目解析: 题目要求里面并没有包括x、y、z的大小关系,那么如果要满足x%y = a,最简单的做法就是x=a,并且满足x<y; 同理,可以得到y%z=b,会有y=b,并且满足y<z; 但是在z%x=c,假如我们令z=c,满足z<x则会出现异常,因为由前面两个已经可以递推得到x<y<z;并且由于a<c,x如果为a是无法得到c的;
由于a<c的约束,我们先考虑满足z%x=c的限制,即是令z=c,并且满足z<x; 接着是y%z=b,可以令y=b,由于b<c=z,所以这个也能够满足; 剩下的就是x%y=a,已知y=b,那么有x%b=a,即是x=b*k + a;
此时要满足x=bk + a,z<x,可以令k=c,那么有x=cb+a;
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
lld a, b, c;
cin >> a >> b >> c;
cout << (c * b + a) << " " << b << " " << c << endl;
}
}
}
ac;
题目链接 题目大意: 给出n x m的矩阵a,a[i][j]是一个整数; 现在需要选择任意两列进行交换,现在想知道是否存在一种交换方式,满足: 交换之后,每一行的元素,从左到右都是非递减的;
输入: 第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100) 每个样例第一行是整数𝑛 and 𝑚 (1≤𝑛,𝑚≤2⋅1e5) 接下来会有n行m列的整数 𝑎[𝑖,𝑗] (1≤𝑎[𝑖,𝑗]≤1e9);
输出: 每个样例一行,输出满足的交换位置;(可以交换相同位置) 如果无解则输出-1;
Examples input 5 2 3 1 2 3 1 1 1 2 2 4 1 2 3 2 2 2 1 1 1 2 3 6 2 1 5 4 3 2 1 1 2
output 1 1 -1 1 2 1 3 1 1
题目解析: 先考虑一维的情况,给出一个数组,交换任意两个数字,然后将数组变成非递减; 由于每次只能选择交换相同位置或者两个位置,也就是说要么影响2个数字,要么不影响,那么可以先计算一遍最长非递减的子序列得到长度k; 根据k和n的区别,如果n-k>2,那么就是必然无解; 但是由于k可以等于n、n-1、这几种情况是比较难以决策如何选择出来两个位置; 考虑到只有一次交换(2个位置),那么假如将数组直接排序,是不是也可以通过这个来对比得到这个位置? 假如排序之后,将有序数组和原数组对比,得到若干个不匹配的位置,如果不同数大于2则无解,如果不同数为2则就是交换的两个位置,如果不同数为0则不需要交换;(这里不存在不同数位1的情况)
基于上面一维的分析,我们可以推导到二维数组的情况。 当我们从上到下去遍历每一行元素时,当我们第一次找到存在2个位置不同的时候,我们就将这位置作为最终的交换位置; 将整个矩阵相应列进行交换,最后判断结果是否符合要求。
注意:如果某一行完全匹配(不同数为0),此时应该先忽略,去找不同位置为2的行;
class Solution {
static const int N = 201010;
vector<int> a[N];
vector<int> b[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
a[i].clear();
b[i].clear();
for (int j = 0; j < m; ++j) {
int x;
scanf("%d", &x);
a[i].push_back(x);
b[i].push_back(x);
}
}
vector<int> diff;
bool ans = true;
for (int i = 0; i < n; ++i) {
sort(a[i].begin(), a[i].end());
if (!diff.size()) {
for (int j = 0; j < m; ++j) {
if (a[i][j] != b[i][j]) {
diff.push_back(j);
}
}
}
}
if (diff.size() > 2) {
ans = false;
}
else if (!diff.size()){
diff.push_back(0);
diff.push_back(0);
}
else {
for (int i = 0; i < n; ++i) {
int x = diff[0], y = diff[1];
int tmp = b[i][x];
b[i][x] = b[i][y];
b[i][y] = tmp;
for (int j = 0; j < m; ++j) {
if (a[i][j] != b[i][j]) {
ans = false;
}
}
}
}
if (ans) {
cout << diff[0] + 1 << " " << diff[1] + 1 << endl;
}
else {
cout << (-1) << endl;
}
}
}
}
ac;
题目链接 题目大意: 在一个n x m的方格矩阵中,小明要从左上角(1,1)到右下角(n,m),小红要从左下角(n,1)到右上角(1,m); 每个相邻格子的行动代价是1; 小红先出发,沿路中每个经过格子都会放下一个传送器,这个不需要代价; 小明晚出发,小明如果站在某个有传送器的格子,那么可以花费1代价,传送到另外一个有传送器的格子; 问小红和小明到达目的,总的代价最小为多少;
输入: 第一行,整数𝑡 表示t个样例𝑡 (1≤𝑡≤1000) 每个样例第一行 整数 𝑛, 𝑚 ( (1≤𝑛,𝑚≤1e5)
输出: 每个样例一行,输出最小的总代价;
Examples input 7 7 5 5 7 1 1 100000 100000 57 228 1 5 5 1 output 15 15 0 299998 340 5 5
题目解析: 在没有传送器的情况下,小红和小明的路径总代价都是n+m; 假设小红不考虑小明,按照最短路径到达,总代价是n+m;然后小明借助小红的路径,理论上能节省的最大路径是max(n, m)-1,总的代价就是n+m+max(n, m)-1; 此时路径应该就是小红先走到(1, 1),再走到(1, m); 有没有可能小红为了让小明能够尽可能传送,特意绕路?不会,因为小红要走过的路才能让小明传送;所以一旦远离小红的最优路径n+m,所有给小明节省的代价,其实都是不划算的. 注意:边界情况要考虑,n=1 和 m=1。
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
if (n == 1 || m == 1) {
if (n == m) cout << 0 << endl;
else cout << max(n, m) << endl;
}
else cout << (n + m - 2) * 2 - max(n, m) + 2 << endl;
}
}
}
ac;
题目链接 题目大意: 给出包括n个非负整数的数组a,我们可以计算这个数组的beauty值: 将数组每个元素除以k,向下取整得到这个元素的beauty值,数组的beauty值等于所有元素的beauty值总和; 现在给出n、k、数组beauty值b和数组元素累加和s,求是否能够构造数组a;
输入: 第一行,整数𝑡 表示t个样例𝑡 (1≤𝑡≤1000) 每个样例第一行 整数 𝑛, 𝑘, 𝑏, 𝑠 (1≤𝑛≤1e5, 1≤𝑘≤1e9, 0≤𝑏≤1e9, 0≤𝑠≤1e18).
输出: 每个样例一行,如果无解输出-1;如果有解则输出n个整数;𝑎1,𝑎2,…,𝑎𝑛 (0≤𝑎𝑖≤1e18)
Examples input 8 1 6 3 100 3 6 3 12 3 6 3 19 5 4 7 38 5 4 7 80 99978 1000000000 100000000 1000000000000000000 1 1 0 0 4 1000000000 1000000000 1000000000000000000 output -1 -1 0 0 19 0 3 3 3 29 -1 -1 0 0 0 0 1000000000000000000
题目解析: 为了方便思考,我们先考虑数组只有3个元素的情况,那么有: a1 + a2 + a3 = s ; a1/k + a2/k + a3/k = b;
那么我们可以令a1=k * b,先保证条件b可以满足; 因为除以k的原因,接下来a1到a3,都可以增大k-1的大小而且不影响b的值; 那么s的上限就是k * b + n * (k - 1),下限就是k * b; 满足这里的条件就有解。
思考: 如何证明正确性?假设a1/k + a2/k,a2需要大于k,那么将a2-k,并将a1+k是等价的;
注意: 超过int32,不过样例已经覆盖了这样的case。
class Solution {
static const int N = 201010;
public:
void solve() {
lld t;
cin >> t;
while (t--) {
lld n, k, b, s;
cin >> n >> k >> b >> s;
lld maxSum = k * b + n * (k - 1);
if (maxSum < s || b * k > s) {
cout << -1 << endl;
}
else {
s -= b * k;
for (lld i = 0; i < n; ++i) {
lld tmp = min(k - 1, s);
s -= tmp;
if (i == 0) tmp += b*k;
cout << tmp << " ";
}
cout << endl;
}
}
}
}
ac;