A. 身份证编码问题
简单模拟， 按说的做就行
代码:
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
ll n ;
ll arr[20005] = {} ;
map <int, char> mic ;
int mci[] = {7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2} ;
int main() {
ios::sync_with_stdio(false) ;
string s ;
cin >> s ;
mic[0] = '1' ;
mic[1] = '0' ;
mic[2] = 'X' ;
mic[3] = '9' ;
mic[4] = '8' ;
mic[5] = '7' ;
mic[6] = '6' ;
mic[7] = '5' ;
mic[8] = '4' ;
mic[9] = '3' ;
mic[10] = '2' ;
ll ans = 0 ;
for (int i = 0 ; i < 17 ; ++i) {
ans += mci[i] * (s[i]-'0') ;
}
cout << s.substr(6, 4) << "-" << s.substr(10, 2) << "-" << s.substr(12, 2) << endl ;
bool xb ;
if (!(s[16] % 2)) xb = true ;
else xb = false ;
cout << (!xb ? "male" : "female") << endl ;
if (mic[ans % 11] == s[17]) cout << "True" << endl ;
else cout << "False" << endl ;
return 0;
}
B.A变B
也是简单模拟，二进制比较一下就好，多余补0
代码：
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
ll wys(ll a,ll b){
int n=0;
while(a||b){
if(a%2!=b%2)n++;
a>>=1;
b>>=1;
}
return n;
}
int main()
{
long long a,b;
while(cin>>a>>b){
if(a==0&&b==0)break;
cout<<wys(a,b)<<endl;
}
}
c.R进制数排序
转成十进制比较，然后排序输出就好
代码
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
ll n ;
struct sz{
string z ;
int zh ;
sz() {}
sz(string x, int r) {
z = x ;
zh = 0 ;
ll p = 1 ;
for (int i = x.size()-1 ; i >= 0 ;i--){
zh += p*(x[i]-'0') ;
p *= r ;
}
}
bool operator <(const sz &b) const {
return zh < b.zh ;
}
}; //结构体存本来进制数和转化后的数字
sz arr[20005] = {} ;
int main() {
ios::sync_with_stdio(false) ;
int t ;
cin >> t ;
while (t--) {
cin >> n ;
int r ;
cin >> r ;
string x ;
for (int i = 1 ; i <= n ; i++) {
cin >> x ;
arr[i] = sz(x, r) ;
}
sort (arr+1, arr+n+1) ;
bool p = false;
for (int i = 1 ; i <= n ; i++) {
if (p) cout << " " ; p = true ;
cout << arr[i].z ;
} cout << endl ;
}
return 0;
}
D. 两个多项式的和
每个指数对应的系数相加然后按指数从大到小输出就好
代码：
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef pair<int, int> PII ;
map <ll, ll> mli ;
stack<PII> st ;
int main() {
ios::sync_with_stdio(false) ;
int a ;
cin >> a ;
ll x, z ;
for (int i = 1 ; i <= a ; ++i) {
cin >> x >> z ;
mli[z] += x ;
}
cin >> a ;
for (int i = 1 ; i <= a ; ++i) {
cin >> x >> z ;
mli[z] += x ;
}
for (auto i : mli) {//用栈把从小到大变成从大到小
st.push({i.second, i.first}) ;
}
bool p = false ;
while (!st.empty()) {
if (p) cout << " " ; p = true ;
cout << st.top().first << " " << st.top().second ;
st.pop() ;
} cout << endl;
return 0;
}
E.黑白棋子的移动
所有步骤都是固定，找到规律，比如说7的步骤是由6多了一步而来的
代码：
int main() {
string s ;
int n ;
cin >> n ;
cout << "step 0:" ;
for (int i = 0; i < n; ++i) {
cout << "o" ;
}
for (int i = 0; i < n; ++i) {
cout << "*" ;
}
cout << "--" << endl ;
for (int i = (n-1)*2-1; i > 0 ; --i) {
cout << "step " << (n-1)*2-i << ":" ;
if (i > 5) {
if (i & 1) {
for (int j = 1; j <= i/2+1; ++j) {
cout << "o" ;
}
cout << "--" ;
for (int j = 1; j <= i/2+1; ++j) {
cout << "*" ;
}
for (int j = 1; j <= n - i/2-1; ++j) {
cout << "o*" ;
}
} else {
for (int j = 1; j <= i/2+1; ++j) {
cout << "o" ;
}
for (int j = 1; j <= i/2+1; ++j) {
cout << "*" ;
}
cout << "--" ;
for (int j = 1; j <= n - i/2-1; ++j) {
cout << "o*" ;
}
} ce("") ;
} else {
if (i == 5) {
cout << "ooo--***o*" ;
for (int j = 0; j < n-i/2-2; ++j) {
cout << "o*" ;
} ce("") ;
} else if (i == 4) {
cout << "ooo*o**--*" ;
for (int j = 0; j < n-i/2-2; ++j) {
cout << "o*" ;
} ce("") ;
} else if (i == 3) {
cout << "o--*o**o" ;
for (int j = 0; j < n-i/2-2; ++j) {
cout << "o*" ;
} ce("") ;
} else if (i == 2) {
cout << "o*o*o*--" ;
for (int j = 0; j < n-i/2-2; ++j) {
cout << "o*" ;
} ce("") ;
} else if (i == 1) {
cout << "--" ;
for (int j = 0; j < n; ++j) {
cout << "o*" ;
} ce("") ;
}
}
}
return 0 ;
}
F.反素数
给定n，求n以内因子数最多的数。
一提到因子数，首先想到的就是把素因子分解。把n分解成
n=（p1的k1次方）*（p2的k2次方）**（p3的k3次方）
那么因子总数 ans=（k1+1）（k2+1）（k3+1）
考虑极端情况，n是某一个素数的k次幂，long long 为2的64次幂，所以我们最多就考虑到64层
当前因子大于我们想要的因子或正好为我们想要的因子或已经大于n我们就结束
ll primes[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
int maxd, maxval;
long long n;
//dp 为当前枚举第几个素数。 num为当前因子的数量
//temp为当前因子数位num的数值。up为上一个素数的幂，这次应该小于等于这个幂次
void dfs(int dp, ll temp, int num, int up) {
if ((num > maxd) || (num == maxd && maxval > temp)) {
//当前因子数>maxd or 因子数相同，取值小的
maxd = num;
maxval = temp;
}
if (dp == 16) return;
for (int i = 1; i <= up; i++) {
if (primes[dp] * temp > n) break;
temp *= primes[dp];
dfs(dp + 1, temp, num * (i + 1), i);
}
}
int main() {
cin >> n;
dfs(0, 1, 1, 60);
cout << maxval << endl;
}
G.乘积最大
基础dp 用字符串来进行各个数位的拆分
f[i][j]表示前j位添加了i个乘号时的最优解
template <typename T> T to_math(string s) {
stringstream ss(s) ;
T num ;
ss >> num ;
return num ;
} //字符串流转化为数字
string number ;
int dp[45][45] = {};
void in() {
int n, m ;
cin >> n >> m ;
cin >> number ;
For_(i, 1, n) {
dp[i][0] = to_math<int>(number.substr(0, i)) ;
For_(j, 1, m) {
For_(k, 1, i-1) {
dp[i][j] = max(dp[i][j], dp[k][j-1] * to_math<int>(number.substr(k, i-k))) ;
}
}
}
ce(dp[n][m]) ; // cout
}
int main() {
in();
}
H.桃子的二分
前缀和记录连续区间和， 用二分答案去遍历数组序列
int n;
int s[2000005];
bool check(int mid)
{
for(int i = 1; i <= n - mid + 1; i ++ )
{
if(s[i + mid - 1] - s[i - 1] > 0) return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false) ;
cin >> n ;
for(int i = 1; i <= n; i ++ ) cin >> s[i] , s[i] += s[i - 1];
int l = 0, r = n;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(check(mid)) l = mid; //如果当前区间和大于0了则可以再加长
else r = mid - 1;
}
ce(r) ;
return 0;
}
I.我要4444
注意同一天先处理报废的在处理申请的，记录已经使用了多少个车牌就好，如果超过了4444个就表示
已经取走4444号车牌了，除非报废的是4444车牌不然4444车牌一直没有
代码：
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef pair<int, int> PII ;
struct day {
int x, l;
char bz ;
bool operator <(const day &b) const {
if (x == b.x) return bz < b.bz ;
return x < b.x ;
} //可以用外部cmp替代
};
day sd[55] ;
int main() {
ios::sync_with_stdio(false) ;
int t ;
cin >> t ;
while (t--) {
int k, p ;
cin >> k >> p ;
for (int i = 0; i < p ; i++){
cin >> sd[i].x >> sd[i].bz >> sd[i].l ;
} sort(sd, sd+p) ;
bool yy = true ;
for (int i = 0; i < p ; i++) {
if (sd[i].bz == 'N') {
k += sd[i].l ;
if (k > 4444) yy = false ;
} else {
if (sd[i].l == 4444) yy = true ;
k -= 1 ;
} //报废了车牌使用-1
}
if (yy) cout << "Yes" << endl ;
else cout << "No" << endl ;
}
return 0;
}
