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

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

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

inputCopy
4
1
6
2
6 8
4
1 3 3 7
2
4 2
1
50
2
25 50
10
1 2 3 4 5 6 7 8 9 10
2
5 15
outputCopy
Bob
Bob
Alice
Alice
Alice
Bob
Bob
Bob

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

#include
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair pii;
typedef vector 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
        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
        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;
}

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

问最顶部的牌的数字？

inputCopy
3
2
1 2
3
1 1 1
4
3 1 4 2
2
3 1
5
2 1 5 4 3
5
3 2 1 2 1
outputCopy
2
3
3

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

#include
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair pii;
typedef vector 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
        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;
}

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

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

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

inputCopy
3
2
1 2
1 2
2
2 1
1 2
4
2 3 1 2
2 3 2 3
outputCopy
0
-1
3
3 1
3 2
4 3

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

#include
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair pii;
typedef vector vi;
typedef vector> 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
        cin >> a[i];
    }
    for (int i = 0;i
        cin >> b[i];
    }
    vpii ans;
    for (int i = 0; i < n - 1;i++){
        for (int j = i + 1;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]
        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;
}

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

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

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

inputCopy
2 1
outputCopy
-1

inputCopy
3 2
outputCopy
4

inputCopy
13 42
outputCopy
12

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 的数字出现退出。

#include
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair pii;
typedef vector vi;
typedef vector> 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 q;
    map 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;
}