【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
题解:
- 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- 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;}