南邮
1.求一堆输入的最值
先开一个动态数组，然后输入，排序，取arr数组的头和尾。
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main(){ int n; while(cin>>n){ vector<int> arr(n); for(int i =0 ;i<n;i++){ cin>>arr[i]; } sort(arr.begin(),arr.end()); cout<<arr[n-1]<<" "<<arr[0]<<endl; } }2.素数+回文数
#include<iostream> using namespace std; bool isPrime(long long x){//素数：只能1和他本身作为因子 if(x<=1) return false; if(x == 2)return true; if(x%2==0)return false;//奇偶数加速，后面只判断奇数 for(long long i = 3;i*i<=x;i++){ if(x%i == 0)return false; } return true; } bool isPalindrome(long long x){//判断回文数 long long ori = x,rev = 0; while(x>0){ rev = rev * 10 + x % 10; x /=10; } if(ori == rev) return true; else return false; } int main(){ int n; cin>>n; for(int i = 0;i<n;i++){ long long a; cin>>a; if(a<99999 && isPrime(a) && isPalindrome(a))cout<<"Yes"<<endl; else cout<<"No"<<endl; } }字符串判断回文数
bool isPalindrome(long long x){ string s = to_string(x); int l = 0, r = s.size()-1; while(l < r){ if(s[l] != s[r]) return false; l++; r--; } return true; }3.十进制转任意进制
#include<iostream> #include<string> #include<algorithm> using namespace std; char getChar(int x){ if(x<10)return '0'+x; else return 'A'+(x-10); } string convert(int N,int R){ string res; bool neg = false; if(N<0){ neg = true; N = -N; } if(N == 0){ return "0"; } while(N>0){ int rem = N % R; res += getChar(rem); N = N/R; } reverse(res.begin(),res.end()); if(neg) res = "-"+res; return res; } int main(){ int T; cin>>T; while(T--){ int N,R; cin>>N>>R; cout<<convert(N,R)<<endl; } return 0; }也可以用map存映射关系
#include<unordered_map> unordered_map<int, char> mp = { {0, '0'}, {1, '1'}, {2, '2'}, {3, '3'}, {4, '4'}, {5, '5'}, {6, '6'}, {7, '7'}, {8, '8'}, {9, '9'}, {10, 'A'}, {11, 'B'}, {12, 'C'}, {13, 'D'}, {14, 'E'}, {15, 'F'} }; char getChar(int x){ return mp[x]; }4.涂色问题
先看每一列：
有两种方案，aba和abc
aba：第一个格子3种颜色可选，第二个格子2种，第三个格子跟第一个一样：3×2 = 6
abc：第一个格子3种颜色可选，第二个格子2种，第三个格子1种：3×2×1 = 6
然后假设第 i-1 列确定了，看第 i 列有几种方案：
得到：
a[i]=2*a[i-1]+2*b[i-1] b[i]=2*a[i-1]+3*b[i-1]当前状态的可能性，与上一列是aba还是abc相关
#include<iostream> using namespace std; const long long MOD = 1e9+7; int main(){ int n; cin>>n; long long a[n],b[n]; a[0]=6; b[0]=6; for(int i = 1;i<n;i++){ a[i] = (2*a[i-1]+2*b[i-1])%MOD; b[i] = (2*a[i-1]+3*b[i-1])%MOD; } cout<<(a[n-1]+b[n-1])%MOD<<endl; return 0; }可以优化，把数组空间去掉
#include<iostream> using namespace std; const long long MOD = 1e9+7; int main(){ int n; cin>>n; long long a = 6; long long b = 6; for(int i = 1;i<n;i++){ long long na = (2*a + 2*b)%MOD; long long nb = (2*a + 3*b)%MOD; a = na; b = nb; } cout<<(a+b)%MOD<<endl; return 0; }5.最大公约数和最小公倍数
求最大公约数gcd：
最小公倍数lcm：
#include<iostream> using namespace std; int gcd(int a,int b){ while(b!=0){ int t = a%b; a = b; b = t; } return a; } int main(){ int A,B; cin>>A>>B; int g = gcd(A,B); int l = A/g * B;//防止溢出 cout<<g<<" "<<l<<endl; return 0; }6.斐波那契数列
#include<iostream> using namespace std; int Fibonacci(int n){ if(n==0)return 0; if(n==1 || n==2)return 1; return Fibonacci(n-1) + Fibonacci(n-2); } int main(){ int n; cin>>n; cout<<Fibonacci(n); return 0; }7.回文数
#include<iostream> #include<string> using namespace std; bool isPalindrome(string s){ int l =0; int r = s.size() - 1; while(l<r){ if(s[l] != s[r] &&s[l]-32 != s[r]&&s[l] != s[r]-32){//不区分大小写 return false; } l++; r--; } return true; } int main(){ string s; cin>>s; if(isPalindrome(s))cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }8.级数求和
注意用double类型，除法的时候写1.0
#include<iostream> using namespace std; int main(){ int k; cin>>k; long long n = 1; double sn = 0; while(k>sn){ sn+=(1.0/n); if(sn > k) break; n++; } cout<<n; }9.可乐瓶换可乐
#include<iostream> using namespace std; int main(){ int n,k; cin>>n>>k; long long total = n; long long empty = n; while(empty >= k){ long long get = empty/k; long long rem = empty%k; total += get; empty = get + rem; } cout<<total<<endl; return 0 ; }定义get和rem，然后循环
10.周天子分封（sort排序）
这个题目就是我刚开始用的 int arr[n]；
然后后面使用sort排序 ,sort(arr.begin(),arr.end());
报错了，原来是原生数组要传首地址、尾后地址（原生数组没有.begin .end方法）：
sort(arr , arr + n);
而且int arr[n]不是标准cpp写法，最好写成int arr[1005]或者使用vector
还有就是输入的地方我写的有点简陋，但是不知道怎么写的优雅一点：
for(int i = 0;i<n;i++){ int p; cin>>p; arr[i] = p; }问问豆包：
for(int i = 0;i<n;i++){ cin>>arr[i]; }#include<iostream> #include<algorithm> using namespace std; int main(){ int n; cin>>n; int arr[1005]; for(int i = 0;i<n;i++){ int p; cin>>p; arr[i] = p; } sort(arr,arr + n); cout<<arr[n-1]+arr[n-2]+arr[n-3]; }10.矩阵变换（把某行列改为0）
这个题用vector创建二维数组
二维 vector 本质：vector< vector<int> >，外层是行，内层是每一行的一维 vector
// n行 m列，默认值 0 vector<vector<int>> arr(n, vector<int>(m));然后这个题的坑：
不能记录完，然后遍历数组，看看谁是1，然后再循环把这个数的纵横两条线的数字置零。
因为有可能这条线上有1，代表这边也需要把纵横置零，没提前记录就把它改了，就找不到了
应该先设置2个bool数组，记录col和row，如果输入的数字是1，那就把这行和这列设置为true，
后续改数字的时候，就看如果col是true or row是true，就置零。
#include<iostream> #include<vector> using namespace std; int main(){ int n,m; cin>>n>>m; vector<vector<int>> arr(n,vector<int>(m)); vector<bool> row(n); vector<bool> col(m); for(int i = 0;i<n;i++){ for(int j =0 ;j<m;j++){ cin>>arr[i][j]; if(arr[i][j] == 1){ row[i] = true; col[j] = true; } } } for(int i = 0;i<n;i++){ for(int j = 0;j<m;j++){ if(row[i] || col[j]){ arr[i][j] = 0; } } } for(int i = 0;i<n;i++){ for(int j = 0;j<m;j++){ cout<<arr[i][j]<<" "; } cout<<endl; } return 0; }11.公路上的树，修路占用
这个题要注意开辟的数组的大小，因为树是从数轴的0开始栽，到 L 一共L+1棵树
#include<iostream> #include<vector> using namespace std; int main(){ int l,m; cin>>l>>m; vector<bool> arr(l+1,true); for(int i = 0;i<m;i++){ int u,v; cin>>u>>v; for(int j = u;j<=v;j++){ if(arr[j]){ arr[j] = false; } } } int count = 0; for(int i = 0;i<=l;i++){ if(arr[i]){ count++; } } cout<<count; return 0; }12.算分环节
这道题用到了accumulate，保留两位小数输出
#include<iostream> #include<vector> #include<numeric> #include<algorithm> #include<iomanip> using namespace std; int main(){ int n,m; cin>>n>>m; vector<vector<int>> arr(n,vector<int>(m)); vector<double> avgs(n); for(int i = 0;i<n;i++){ for(int j = 0;j<m;j++){ cin>>arr[i][j]; } } for(int i = 0;i<n;i++){ sort(arr[i].begin(),arr[i].end()); int sum = accumulate(arr[i].begin(), arr[i].end(), 0); double avg = (sum - arr[i].front() - arr[i].back())*1.0 / (m-2); avgs[i] = avg; } sort(avgs.begin(),avgs.end()); cout<<fixed<<setprecision(2)<<avgs.back()<<endl; }13.输入年和天，输出几月几日
#include<iostream> using namespace std; bool isRunNian(int y){ if(y % 100 == 0){ if(y % 400 == 0){ return true; } return false; } else if(y % 4 == 0){ return true; } return false; } int main(){ int Y,n; cin>>Y>>n; int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31,30,31}; if(isRunNian(Y)){ days[2] = 29; } int month = 1; while(n>days[month]){ n-=days[month]; month++; } cout<<month<<" "<<n; return 0; }14.子串统计（kmp算法）
#include<iostream> #include<vector> #define FAST ios::sync_with_stdio(false) ,cin.tie(0), cout.tie(0); using namespace std; vector<int> getNext(string &q){ int m = q.size(); vector<int> next(m,0); for(int i = 1,j = 0;i<m;i++){ while(j>0 && q[i] != q[j]){ j = next[j-1]; } if(q[i] == q[j]){ j++; } next[i] = j; } return next; } int kmp(string &s,string &q,vector<int> &next){ int ans = 0; for(int i = 0,j = 0;i<s.size();i++){ while(j>0 && s[i] != q[j]){ j = next[j-1]; } if(s[i] == q[j]){ j++; } if(j == q.size()){ ans++; j = next[j-1]; } } return ans; } int main(){ FAST; int n; cin>>n; while(n--){ string s,q; cin>>s>>q; vector<int> next = getNext(q); int ans = kmp(s,q,next); cout<<ans<<endl; } return 0; }关闭同步 + 解绑，cin 速度几乎追上scanf，时间够用直接通过。
没写这句的时候没有通过：
#define FAST ios::sync_with_stdio(false) ,cin.tie(0), cout.tie(0);
15.社交网络
这个题刚开始想用vector开二维数组，然后输入的用户代码id当做数组下标，结果发现开的数组是arr[n]，但是id能达到10^9，
段错误，发生越界
得用哈希map，键存id，值是一个vector数组，添加对应的好友
#include<iostream> #include<vector> #include<unordered_map> using namespace std; int main(){ int n; cin>>n; unordered_map<int,vector<int>> map; for(int i = 0;i<n;i++){ int a,b; cin>>a>>b; map[a].push_back(b); map[b].push_back(a); } int max = 0; for(auto &p : map){ if(p.second.size() > max){ max = p.second.size(); } } cout<<max; return 0; }
