牛客练习赛111（A-D）
A
题意：给出一个整数A，求出最小的整数B使得A+B产生进位。
输入：
3
114514
1314520
100
输出：
6
80
900
根据样例，不难看出答案只跟最右边的非零数位有关。
点击查看代码
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define per(i, r, l) for(int i = r; i >= l; i--)
#define debug(tar, l, r) rep(ii, l, r) cout << tar[ii] << " \n"[ii==r]
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e5+5;
const int mod = 1e9+7;
int n;
void solve(){
int a;
cin >> a;
int ct = 0;
while(a%10 == 0){
ct++;
a /= 10;
}
int ans = (10-a%10)*pow(10, ct);
cout << ans << "\n";
}
int main(){
std::ios::sync_with_stdio(false);
int tt; cin >> tt; while(tt--)
solve();
return 0^0;
}
B
题意：
给出两个长度为\(n\)的字符串\(S_1和S_2\)，问能否通过交换\(S_1\)两个下标\((i,j)\)的字符，使得\(S_1 = S_2\)
输入
5
abcda
bacda
输出
5
abcda
bacda
YES的情况分为两种，
- 两个字符串刚好有两个位置不一样，且交换后它们就一样了。样例就是如此。
- 两个字符串完全一样，但是其中有两个相同的字符，那么交换这两个字符同样ok。例如aa
第二种容易忽略，导致我wa了一发。
点击查看代码
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define per(i, r, l) for(int i = r; i >= l; i--)
#define debug(tar, l, r) rep(ii, l, r) cout << tar[ii] << " \n"[ii==r]
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e5+5;
const int mod = 1e9+7;
int n;
char a[N], b[N];
vector <int> dif;
int ct[26];
void solve(){
cin >> n;
cin >> a+1;
cin >> b+1;
for(int i = 1; a[i]; i++){
if(a[i] != b[i]) dif.push_back(i);
ct[a[i]-'a']++;
}
if(dif.size() == 2){
if(a[dif[0]] == b[dif[1]] && a[dif[1]] == b[dif[0]]){
cout << "YES\n";
return ;
}
}
else if(dif.empty()){
rep(i, 0, 25) if(ct[i] > 1){
cout << "YES\n";
return ;
}
}
cout << "NO\n";
}
int main(){
std::ios::sync_with_stdio(false);
solve();
return 0^0;
}
C
题意：
给出\(m跟x\)，求对于所有整数\(k\)满足\(kx \leq m\)时，\(ky \le m, kx>m\)时，\(ky>m\) 的y的数量
输入
3
15 7
12 12
6 1
输出
2
6
1
不难发现所有满足条件的y是连续的，所以只要找出最值，就能够知道具体的数量。
首先看第一个条件：\(kx \le m\)时，\(ky \le m\)
通过前一个式子，我们能够推出满足前一个式子的k的最大值，显然是\(k_{max} = \lfloor \frac{m}{x} \rfloor\)，
那么对于后一个式子，具体要求就是:\(k \leq k_{max}\)时，\(ky \leq m\)
显然当\(k=k_{max}\)，\(y\)的值域被限制到最小，此时y在小于号左边，取的是最大值
即\(y_{max} = \lfloor \frac{m}{k_{max}} \rfloor\)，
相似的，根据第二个条件我们能得到
\(y_{min} = \lfloor \frac{m}{k_{max}+1} \rfloor + 1\)
点击查看代码
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define per(i, r, l) for(int i = r; i >= l; i--)
#define debug(tar, l, r) rep(ii, l, r) cout << tar[ii] << " \n"[ii==r]
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e5+5;
const int mod = 1e9+7;
int n;
int m, x;
void solve(){
cin >> m >> x;
int k = m/x;
int r = m/k;
k++;
int l = m/k+1;
cout << r-l+1 << "\n";
}
int main(){
std::ios::sync_with_stdio(false);
int tt; cin >> tt; while(tt--)
solve();
return 0^0;
}
D
题意：
给出\(a, b, n, L和R\),问是否存在正整数\(x和y\)，使得\(ax + by = n\)，其中\(L \le x \le R\)
输入
3
3 4 10 1 2
2 4 5 1 1
3 5 11 1 1
输出
YES
NO
NO
一眼顶真，鉴定为exgcd求通解，纯纯板子题，有个坑点是会爆int
点击查看代码
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define per(i, r, l) for(int i = r; i >= l; i--)
#define debug(tar, l, r) rep(ii, l, r) cout << tar[ii] << " \n"[ii==r]
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e5+5;
const int mod = 1e9+7;
#define int long long
int n, a, b, l, r;
// l <= x << r
// (n-x*a)%b == 0 -> x*a + y*b == n;
int ex_gcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int d = ex_gcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - a / b * y;
return d;
}
void solve(){
cin >> a >> b >> n >> l >> r;
int gcd = __gcd(a, b);
if(n%gcd){
cout << "NO\n";
return ;
}
int x0, y0;
int ans = ex_gcd(a, b, x0, y0);
int x1 = x0*n/ans, y1 = y0*n/ans;
int tx = b/ans, ty = a/ans;
if(x1 >= l){
int dif = x1-l;
int ct = dif/tx;
if(y1 + ct*ty >= 0 && x1-ct*tx <= r){
cout << "YES\n";
return ;
}
}
else{
int dif = l-x1;
int ct = (dif+tx-1)/tx;
if(y1 - ct*ty >= 0 && x1+ct*tx <= r){
cout << "YES\n";
return ;
}
}
cout << "NO\n";
}
signed main(){
std::ios::sync_with_stdio(false);
int tt; cin >> tt; while(tt--)
solve();
return 0^0;
}