持续更新（题库搜索“考研”）
短除法+高精度除法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
bool not_zero(vector<int> x)
{
for(auto a : x)
{
if(a > 0) return 1;
}
return 0 ;
}
vector<int> div(vector<int> x , int &r)
{
vector<int> C ;
for(int i = x.size() -1 ; i >= 0 ; i --)
{
r = r * 10 + x[i] ;
C.pb(r / 2) ;
r %= 2 ;
}
reverse(C.begin() , C.end()) ;
while(C.size() > 1 && C.back() == 0) C.pop_back() ;
return C ;
}
void convert(vector<int> x)
{
string ans ;
while(not_zero(x))
{
int r = 0 ;
x = div(x , r) ;
ans += r + '0' ;
}
reverse(ans.begin() , ans.end()) ;
cout << ans << endl ;
}
int main()
{
string raw ;
while(cin >> raw)
{
if(raw == "0")
{
puts("0") ;
continue ;
}
vector<int> origin ;
for(int i = raw.length() -1 ; i >= 0 ; i --)
{
origin.push_back(raw[i] - '0') ;
}
convert(origin) ;
}
return 0 ;
}
排序
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1100 ;
typedef struct info
{
int id ;
string name ;
int score ;
};
info stu[N] ;
int n ;
int order ;
bool cmp_z(info a , info b) // 从高到低
{
if (a.score != b.score)
{
return a.score > b.score ;
}else
{
return a.id < b.id ;
}
}
bool cmp_o(info a , info b)
{
if (a.score != b.score)
{
return a.score < b.score ;
}else
{
return a.id < b.id ;
}
}
int main()
{
cin >> n >> order ;
for(int i = 0 ; i < n ; i ++)
{
stu[i].id = i ;
cin >> stu[i].name >> stu[i].score ;
}
if(order)
sort(stu , stu+ n , cmp_o) ;
else
sort(stu , stu+ n , cmp_z) ;
for(int i = 0 ; i < n ; i ++)
{
cout<< stu[i].name << " " << stu[i].score << endl ;
}
return 0 ;
}
数约数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1100;
int n ;
int a[N] ;
void count(int n)
{
int ans = 0 ;
for(int i = 1 ; i <= n / i ; i ++)
{
if(n % i == 0) ans +=2 ;
if(i * i == n)
{
ans -- ;
break;
}
}
printf("%d\n" , ans) ;
}
int main()
{
cin >> n ;
for(int i = 0 ; i < n ; i ++ )
{
cin >> a[i] ;
}
for(int i = 0 ; i < n ; i ++ )
{
count(a[i]) ;
}
return 0 ;
}
字符串翻转
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
string s ;
while(cin >> s )
{
reverse(s.begin() , s.end()) ;
cout << s << endl;
}
return 0 ;
}
先序变中序
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string pre ;
void build(int &depth)
{
if(depth > pre.size()) return ;
char c = pre[depth] ;
if(c == '#') return ;
depth ++ ;
build(depth) ;
cout << c << " " ;
depth ++ ;
build(depth) ;
}
int main()
{
cin >> pre ;
int depth = 0 ;
build(depth) ;
return 0 ;
}
按位乘法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 11 ;
typedef long long LL;
LL a , b ;
int A[N] , B[N] ;
int main()
{
cin >> a >> b ;
int cnta = 0 ;
while(a)
{
A[cnta++] = a % 10 ;
a /= 10 ;
}
int cntb = 0 ;
while(b)
{
B[cntb++] = b % 10 ;
b /=10 ;
}
int ans = 0 ;
for(int i = 0 ; i < cnta ; i ++)
{
for(int j = 0 ; j < cntb ; j ++)
{
ans += A[i] * B[j] ;
}
}
cout << ans << endl;
return 0 ;
}
二叉树的公共祖先
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
int a ,b ;
set<int> s;
int main()
{
cin >> a >> b ;
while(a)
{
s.insert(a) ;
a /=2 ;
}
while(b)
{
if(s.count(b))
{
cout << b<< endl;
return 0;
}
b /=2 ;
}
return 0 ;
}
2022.6.25
3381 手机键盘
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
map<char,int> T; // 定义字符-时间
map<char,int> group ; // 定义字符组
int main()
{
for(int i = 0 ; i < 8 ; i ++ )
{
if(i == 5)
{
for(int j = 0 ; j < 4 ; j ++)
{
char c = 'a' + i*3 + j ;
// cout << c<< endl;
T.insert({c,j+1});
group.insert({c,i});
}
}
else if(i == 6)
{
for(int j = 0 ; j < 3 ; j ++)
{
char c = 'a' + i*3 +1 + j ;
// cout << c<< endl;
T.insert({c,j+1});
group.insert({c,i});
}
}else if(i == 7)
{
for(int j = 0 ; j < 4 ; j ++)
{
char c = 'a' + i*3 +1 + j ;
// cout << c<< endl;
T.insert({c,j+1});
group.insert({c,i});
}
}else
{
for(int j = 0 ; j < 3 ; j ++)
{
char c = 'a' + i*3 + j ;
// cout << c<< endl;
T.insert({c,j+1});
group.insert({c,i});
}
}
}
// for(auto c : T)
// {
// cout << c.first << " " << c.second << endl;
// }
string str ;
while(cin >> str)
{
int ans = 0 ;
for(int i = 0 ; i < str.size() ; i ++ )
{
char c = str[i] ;
if(!i) ans += T[c] ;
else
{
if(group[str[i-1]] == group[c]) // 同组，等待2
{
ans += 2 + T[c] ;
}
else
{
ans += T[c] ;
}
}
}
cout << ans << endl;
}
return 0;
}
3397 众数
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
const int N = 1e5+10 ;
int n , m ;
int ori[N] ;
int main()
{
cin >> n >> m ;
for(int i = 0 ; i < n ; i++)
{
scanf("%d",&ori[i]) ;
}
for(int i = 0 ; i < m ; i ++)
{
int count[10] ;
memset(count , 0 , sizeof count) ;
for(int j = 0 ; j < n ; j ++)
{
int d = i? (ori[j] / (int)pow(10,i)) % 10:ori[j] % 10 ;
count[d] ++ ;
}
int ans = 0 ;
for(int j = 1 ; j <= 9 ; j++ )
{
if(count[ans] < count[j])
{
ans = j ;
}
}
cout << ans << endl;
}
return 0 ;
}
6.27
3388 求root
这个题本身我觉得还是比较难的，没那么容易看出来，需要动笔算算。
这里定义一个序列N。
N用k的幂次表示，${a_n}$是系数。
N’被定义为${a_n}$的累加和。
然后(N-N’)%(k-1) = 0
然后N’表示成k的幂次，${b_n}$是其系数。
定义N’‘ 是${b_n}$的累加和。
(N’ - N’‘ ) % (k-1) 也一定是0
那这个N序列一直定义下去。
$N^{r-1} - N^{r} $ % (k-1) = 0
$N^{r}$ 刚好小于K。此时这是我们找的答案。
这时候我们把上面的式子左右分别相加。
$N - N^{r} $ % (k-1) = 0
然后$N^{r} $= N % (k-1)
求X^Y 的时候对K-1取模就行啦。
最后就是，这里的答案要求大于0，显然如果N%(k-1)得0，那么正好对应着$N$=k-1的时候，这时候特判输出k-1就行
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
int x , y , z ;
int qmi(int a, int b)
{
int res = 1 ;
while(b)
{
if(b&1) res = res * a % (z-1) ;
a = a *a %(z-1) ;
b >>= 1 ;
}
return res ;
}
signed main()
{
while(~scanf("%d%d%d",&x,&y,&z))
{
int res = qmi(x,y) ;
if(res) cout << res << endl ;
else printf("%d\n",z-1) ;
}
return 0 ;
}
求最大最小
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 11000 ;
int n ;
int a[N] ;
int main()
{
while(~scanf("%d",&n))
{
for(int i = 0 ; i < n ; i ++)
{
scanf("%d" , &a[i]) ;
}
sort(a , a + n ) ;
printf("%d %d\n" , a[n-1] , a[0]) ;
}
return 0;
}
6.28
极值点下标
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110 ;
int n ;
int a[N] ;
int main()
{
cin >> n ;
for(int i = 0 ; i < n ; i ++ )
{
cin >> a[i] ;
}
for(int i = 0 ; i < n ; i ++ )
{
if(!i)
{
if(a[0] != a[1])
{
printf("0 " ) ;
}
}else if(i == n -1)
{
if(a[n-2] != a[n-1])
{
printf("%d " , n-1) ;
}
}else
{
if( 0 < (a[i] - a[i-1]) * (a[i] - a[i+1]))
{
printf("%d " , i) ;
}
}
}
return 0 ;
}
3434 与7无关的数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110 ;
int n ;
bool a[N] ;
bool judge(int x)
{
if(x %7 == 0 ) return 1 ;
while(x)
{
int d = x % 10 ;
if(d == 7) return 1 ;
x /= 10 ;
}
return 0 ;
}
void init()
{
for(int i = 1 ; i < N ; i ++ )
{
if(!judge(i))
{
a[i] = 1 ;
}
}
}
int main()
{
init() ;
cin >> n ;
int ans = 0 ;
for(int i = 1 ; i <= n ; i ++ )
{
if(a[i])
{
ans += i * i ;
}
}
cout << ans << endl;
return 0 ;
}
3435 位操作练习
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define us unsigned short
us a , b ;
void change(us &x)
{
int d = x >> 15 ;
x <<= 1 ;
x += d ;
}
int main()
{
while(cin >> a >> b )
{
if(a > b ) swap(a,b) ;
if(a == b )
{
puts("YES") ;
continue ;
}
int cnt = 0 ;
while(cnt < 17)
{
change(a) ;
if(a == b)
{
puts("YES") ;
break ;
}
cnt ++ ;
}
if(cnt == 17) puts("NO") ; // 多移动一次，避免附加多余条件
}
return 0 ;
}
