題目1
題目鏈接
題目大意：
給出一個整數(shù)n，現(xiàn)在可以對整數(shù)執(zhí)行一個操作：
選擇整數(shù)上兩個不同位數(shù)的數(shù)字交換位置，然后移除整數(shù)最右邊一位的數(shù)字；
重復(fù)這個過程，直到整數(shù)只剩下1位；
現(xiàn)在想知道這個剩下的數(shù)字最小可能為多少。
輸入：
第一行，整數(shù)?? 表示t個樣例 ?? (1≤??≤10000)
每個樣例倆行，第一行 整數(shù) ?? (10≤??≤1e9)
輸出：
每個樣例一行，剩下最小的數(shù)字；
Examples
input
3
12
132
487456398
output
2
1
3
題目解析：
右邊第二位是必勝位，每次都選擇其他位數(shù)的數(shù)字進行交換，在只剩下2位數(shù)字的時候，將第一位和第二位交換，然后會去掉右邊的數(shù)字，剩下原來右邊第二位的數(shù)字；
也就是說，當(dāng)時數(shù)字位數(shù)大于等于3的時候，可以選擇整數(shù)上最小的數(shù)字，將這個數(shù)字放在右邊第二位，再采用上面的策略必然可以留下來；
當(dāng)數(shù)字位數(shù)只有2位時，留下來的數(shù)字必然是最右邊的數(shù)字；
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;
題目2
題目鏈接
題目大意：
給出整數(shù)a，b，c，滿足a<b<c；
構(gòu)造三個整數(shù)x，y，z，滿足：
x mod y = a;
y mod z = b;
z mod x = c;
輸入：
第一行，整數(shù)?? 表示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的大小關(guān)系，那么如果要滿足x%y = a，最簡單的做法就是x=a，并且滿足x<y；
同理，可以得到y(tǒng)%z=b，會有y=b，并且滿足y<z；
但是在z%x=c，假如我們令z=c，滿足z<x則會出現(xiàn)異常，因為由前面兩個已經(jīng)可以遞推得到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;
題目3
題目鏈接
題目大意：
給出n x m的矩陣a，a[i][j]是一個整數(shù)；
現(xiàn)在需要選擇任意兩列進行交換，現(xiàn)在想知道是否存在一種交換方式，滿足：
交換之后，每一行的元素，從左到右都是非遞減的；
輸入：
第一行，整數(shù)?? 表示t個樣例 ?? (1≤??≤100)
每個樣例第一行是整數(shù)?? and ?? (1≤??,??≤2?1e5)
接下來會有n行m列的整數(shù) ??[??,??] (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
題目解析：
先考慮一維的情況，給出一個數(shù)組，交換任意兩個數(shù)字，然后將數(shù)組變成非遞減；
由于每次只能選擇交換相同位置或者兩個位置，也就是說要么影響2個數(shù)字，要么不影響，那么可以先計算一遍最長非遞減的子序列得到長度k；
根據(jù)k和n的區(qū)別，如果n-k>2，那么就是必然無解；
但是由于k可以等于n、n-1、這幾種情況是比較難以決策如何選擇出來兩個位置；
考慮到只有一次交換（2個位置），那么假如將數(shù)組直接排序，是不是也可以通過這個來對比得到這個位置？
假如排序之后，將有序數(shù)組和原數(shù)組對比，得到若干個不匹配的位置，如果不同數(shù)大于2則無解，如果不同數(shù)為2則就是交換的兩個位置，如果不同數(shù)為0則不需要交換；（這里不存在不同數(shù)位1的情況）
基于上面一維的分析，我們可以推導(dǎo)到二維數(shù)組的情況。
當(dāng)我們從上到下去遍歷每一行元素時，當(dāng)我們第一次找到存在2個位置不同的時候，我們就將這位置作為最終的交換位置；
將整個矩陣相應(yīng)列進行交換，最后判斷結(jié)果是否符合要求。
注意：如果某一行完全匹配（不同數(shù)為0），此時應(yīng)該先忽略，去找不同位置為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;
題目4
題目鏈接
題目大意：
在一個n x m的方格矩陣中，小明要從左上角（1，1）到右下角（n，m），小紅要從左下角（n，1）到右上角（1，m）；
每個相鄰格子的行動代價是1；
小紅先出發(fā)，沿路中每個經(jīng)過格子都會放下一個傳送器，這個不需要代價；
小明晚出發(fā)，小明如果站在某個有傳送器的格子，那么可以花費1代價，傳送到另外一個有傳送器的格子；
問小紅和小明到達目的，總的代價最小為多少；
輸入：
第一行，整數(shù)?? 表示t個樣例?? (1≤??≤1000)
每個樣例第一行 整數(shù) ??, ?? ( (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；
假設(shè)小紅不考慮小明，按照最短路徑到達，總代價是n+m；然后小明借助小紅的路徑，理論上能節(jié)省的最大路徑是max(n, m)-1，總的代價就是n+m+max(n, m)-1；
此時路徑應(yīng)該就是小紅先走到(1, 1)，再走到(1, m）；
有沒有可能小紅為了讓小明能夠盡可能傳送，特意繞路？不會，因為小紅要走過的路才能讓小明傳送；所以一旦遠離小紅的最優(yōu)路徑n+m，所有給小明節(jié)省的代價，其實都是不劃算的.
注意：邊界情況要考慮，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;
題目5
題目鏈接
題目大意：
給出包括n個非負整數(shù)的數(shù)組a，我們可以計算這個數(shù)組的beauty值：
將數(shù)組每個元素除以k，向下取整得到這個元素的beauty值，數(shù)組的beauty值等于所有元素的beauty值總和；
現(xiàn)在給出n、k、數(shù)組beauty值b和數(shù)組元素累加和s，求是否能夠構(gòu)造數(shù)組a；
輸入：
第一行，整數(shù)?? 表示t個樣例?? (1≤??≤1000)
每個樣例第一行 整數(shù) ??, ??, ??, ?? (1≤??≤1e5, 1≤??≤1e9, 0≤??≤1e9, 0≤??≤1e18).
輸出：
每個樣例一行，如果無解輸出-1；如果有解則輸出n個整數(shù)；??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
題目解析：
為了方便思考，我們先考慮數(shù)組只有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；
滿足這里的條件就有解。
思考：
如何證明正確性？假設(shè)a1/k + a2/k，a2需要大于k，那么將a2-k，并將a1+k是等價的；
注意：
超過int32，不過樣例已經(jīng)覆蓋了這樣的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;
