> 文档中心 > 【Educational Codeforces Round 129 (Rated for Div. 2)】【题解A~D】

【Educational Codeforces Round 129 (Rated for Div. 2)】【题解A~D】

文章目录

  • 题目:A. Game with Cards
  • 题目:B. Card Trick
    • 题目大意:
    • 题解:
  • 题目:C. Double Sort
    • 题目大意:
    • 题解:
  • 题目:D. Required Length
    • 题目大意:
    • 题解:

题目:A. Game with Cards

题目大意:

两个人打牌,只要A出的牌,B没有比A大的,则A胜利,反之B胜利。

inputCopy41626 841 3 3 724 2150225 50101 2 3 4 5 6 7 8 9 1025 15outputCopyBobBobAliceAliceAliceBobBobBob

题解:

比较A,B牌中的最大值,谁大谁赢,一样大,谁先出谁赢。

#includeusing namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> pii;typedef vector<int> vi;#define all(a) a.begin(), a.end()#define nl '\n'const int inf=0x3f3f3f3f;const int maxn=1e6+5;void solve(){    int n, m;    int a[100] = {0}, b[100] = {0};    cin >> n;    for (int i = 0;i<n;i++){ cin >> a[i];    }    cin >> m;    for (int i = 0; i < m;i++){ cin >> b[i];    }    sort(a, a + n);    sort(b, b + m);    int n1 = a[n - 1];    int m1 = b[m - 1];    if(n1<m1){ cout << "Bob" << nl; cout << "Bob" << nl;    }else if(n1==m1){ cout << "Alice" << nl; cout << "Bob" << nl;    }else{ cout << "Alice" << nl; cout << "Alice" << nl;    }}int main(){    ios::sync_with_stdio(0);    int t = 1;    cin>>t;    while(t--) solve();    return 0;}

题目:B. Card Trick

题目大意:

让你洗牌 m 次。 在第 j 次洗牌时,你应该拿 bj 最上面的牌并将它们移动到剩余的 (n−bj) 牌下面,而不改变内部顺序。

问最顶部的牌的数字?

inputCopy321 231 1 143 1 4 223 152 1 5 4 353 2 1 2 1outputCopy233

题解:

因为只是移动一整塌牌,所以可以理解为循环队列,所以只需要对操作数求和 s u m sum sum 和牌数 n n n 进行取余运算 ,得到操作 s u m sum sum 次后顶部牌的下标,进而知道顶部牌的数字。

#includeusing namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> pii;typedef vector<int> vi;#define all(a) a.begin(), a.end()#define nl '\n'const int inf=0x3f3f3f3f;const int maxn=2e5+5;void solve(){    int n;    cin>>n;    int a[maxn] = {0}, b[maxn] = {0};    long long sum = 0;//不开ll就没了    for (int i = 0; i < n;i++){ cin >> a[i];    }    int m;    cin>>m;    for (int i = 0;i<m;i++){ cin >> b[i]; sum += b[i];    }    sum %= n;    cout << a[sum] << nl;}int main(){    ios::sync_with_stdio(0);    int t = 1;    cin>>t;    while(t--) solve();    return 0;}

题目:C. Double Sort

题目大意:

给定两个数组 a 和 b,均由 n 个整数组成。

在一个步骤中,您可以选择两个索引 i 和 j (1≤i,j≤n; i≠j) 并将 ai 与 aj 和 bi 与 bj 交换。 您必须在两个阵列中执行交换。

你可以让两个数组最后都按非递减顺序排序吗?
如果可以,请打印任何使两个数组都排序的移动序列。
不可以打印-1。

inputCopy321 21 222 11 242 3 1 22 3 2 3outputCopy0-133 13 24 3

题解:

采用冒泡排序,模拟题意,记录每部操作的下标,最后验证排完的两个数组是否有序,输出答案即可。

#includeusing namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> pii;typedef vector<int> vi;typedef vector<pair<int,int>> vpii;#define all(a) a.begin(), a.end()#define nl '\n'const int inf=0x3f3f3f3f;const int maxn=1e6+5;void solve(){    int n;    cin >> n;    vi a(n), b(n);    for (int i = 0;i<n;i++){ cin >> a[i];    }    for (int i = 0;i<n;i++){ cin >> b[i];    }    vpii ans;    for (int i = 0; i < n - 1;i++){ for (int j = i + 1;j<n;j++){     if(a[i]>a[j]||(a[i]==a[j]&&b[i]>b[j])){  swap(a[i], a[j]);  swap(b[i], b[j]);  ans.push_back({i, j});     } }    }    int flag = 1;    for (int i = 1; i < n && flag;i++){ if(a[i]<a[i-1]||b[i]<b[i-1])     flag = 0;    }    if(!flag){ cout << -1 << nl;    }else{ cout << ans.size() << nl; for(auto i:ans){     cout << i.first + 1 << " " << i.second + 1 << nl; }    }}int main(){    ios::sync_with_stdio(0);    int t = 1;    cin>>t;    while(t--) solve();    return 0;}

题目:D. Required Length

题目大意:

给你两个整数,n 和 x。 您可以使用整数 x 执行多个操作。

您执行的每个操作如下:选择出现在 x 的十进制表示中的任何数字 y 至少一次,并将 x 替换为 x⋅y。

您想让 x(不带前导零)的十进制表示的长度等于 n。 执行此操作所需的最少操作数是多少?

inputCopy2 1outputCopy-1inputCopy3 2outputCopy4inputCopy13 42outputCopy12

题解:

  1. n = 3 , x = 2 ;
    (1) x = 2 * 2 = 4 ;
    (2) x = 4 * 4 = 16 ;
    (3) x = 16 * 6 = 96 ;
    (4) x = 96 * 9 =864 ;
    即答案为: 4
  2. n = 5 , x = 403 ;
    (1) x = 403 * 4 = 1612 ;
    (2) x = 1612 * 6 = 9672 ;
    (3) x = 9672 * 9 = 87048 ;
    但这并不是最优解,最优解为:
    (1) x = 403 * 3 = 1209 ;
    (2) x = 1209 * 9 = 10881 ;

所以,每次只考虑最大的数字显然是不完全正确的,所以考虑用 BFS 对所有结果进行搜索,直到找到第一个长为 n 的数字出现退出。

#includeusing namespace std;typedef long long ll;typedef long double ld;typedef pair<int,int> pii;typedef vector<int> vi;typedef vector<pair<int,int>> vpii;#define all(a) a.begin(), a.end()#define nl '\n'const int inf=0x3f3f3f3f;const int maxn=1e6+5;void solve(){    int n;    cin >> n;    ll v;    cin >> v;    queue<ll> q;    map<ll, int> dist; // dist[a] = b; x数字共操作了b步得到的a    dist[v] = 0;    //cout << v << " ";    q.push(v);    int flag = 1;    while(!q.empty()){ ll k = q.front(); q.pop(); string s = to_string(k); if(s.size() == n){     //cout << nl << k << " ";     cout << dist[k] << nl;     flag = 0;     break; } for(auto x : s){     if(x == '0') continue;     ll w = k * int(x - '0');     if(!dist.count(w))     {  dist[w] = dist[k] + 1;  q.push(w);  //cout << w << " ";     } }    }    if(flag) cout << -1 << nl;}int main(){    ios::sync_with_stdio(0);    int t = 1;    //cin>>t;    while(t--) solve();    return 0;}