A. Number Transformation(构造)
大意：
求是否存在a,b使得式子 ba = y / x 成立
思路：
当 y / x 为整数时 构造 a=1 b=y/x 即可
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 1e6+100; const int p = 1073741824; const double eps = 1e-8; int n; int xx,yy; int main() { cin>>n; while(n--) { cin>>xx>>yy; if(yy%xx!=0) { cout<<"0 0"<<endl; } else { cout<<"1"<<" "<<yy/xx<<endl; } } return 0; }
B. Dictionary
大意：
两个字母的字符串(不含相同字母)从 ab 到 zy 排序，给出字符串求符号
思路：
总共有 25 × 26 = 650 个序号，第一个字母所代表范围是(s[0]-'a')*25;
第二个字母判断它在第一个字母前后位置给出序号大小
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 1e6+100; const int p = 1073741824; const double eps = 1e-8; int n; int sum; string s; int main() { cin>>n; while(n--) { sum=0; cin>>s; sum+=(s[0]-'a')*25; if(s[1]>s[0]) { sum+=s[1]-'a'; } else { sum+=s[1]-'a'+1; } cout<<sum<<endl; } }
C. Infinite Replacement
大意：
两个串，s串 和 t串，s串全是字母a，t串任意，用t串替换s串中的字母a，问最后结果串有多少种；
思路：
分为四种情况
t 串只有一个字母为 a 显然答案为 1
t 串有一个字母不为 a 答案为 2s.size()
t 串有超过一个字母且t串含有字母a 答案为 -1
t 串有超过一个字母但t串不含有字母a 与情况2相同
注意开 long long ！！！
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 1e6+100; const int p = 1073741824; const double eps = 1e-8; ll n,len1,len2; string s,t; ll ans; int main() { cin>>n; while(n--) { cin>>s>>t; len1=s.size(); len2=t.size(); if(len2==1) { if(t=="a") ans=1; else { ans=(ll)pow(2,len1); } } else { if(count(t.begin(),t.end(),'a')==0) { ans=(ll)pow(2,len1); } else { ans=-1; } } cout<<ans<<endl; } }
D. A-B-C Sort
大意：
给出两个排序操作，三个数组
操作1.
A数组尾元素放到B数组中间，直到放空
操作2.
B数组中间元素放到C数组尾，直到放空
检查C数组是否是非降序数组(注意升序和非降序的区别)
思路
经过模拟，我们可以发现
数组下标从 1 开始
1.当数组长度为偶数时，模拟操作只能交换
ai 与 a i+1 i 为奇数
2.当数组长度为奇数时，模拟操作只能交换
ai 与 a i+1 i 为偶数
模拟完判断是否为非降序即可
通过与排序好的数组比较判断是否为非降序序列
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 2*1e5+100; const int p = 1073741824; const double eps = 1e-8; int t,n; int a[N]; int b[N]; bool flag; void solve() { scanf("%d",&t); while(t--) { scanf("%d",&n); flag=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } if(n%2==0) { for(int i=1;i<=n;i+=2) { if(a[i]>a[i+1]) swap(a[i],a[i+1]); } } else { for(int i=2;i<=n;i+=2) { if(a[i]>a[i+1]) swap(a[i],a[i+1]); } } sort(b+1,b+1+n); for(int i=1;i<=n;i++) { if(a[i]!=b[i]) { cout<<"NO"<<endl; flag=1; break; } } if(!flag) cout<<"YES"<<endl; } } int main() { solve(); return 0; }
后三题以后补
