本博客只含比赛的最后三题

7-6 随机输一次 (20分)

#include <bits/stdc++.h> using namespace std; int main() { int n;cin >> n;  vector<int> v; int a; for(int i = 0; i < n; i++) {   cin >> a;   v.push_back(a); }  map<string, string> ying = { // 三种手势对应赢的招数 {"ChuiZi", "Bu"}, {"JianDao", "ChuiZi"}, {"Bu", "JianDao"} },   shu = { // 三种手势对应输的招数 {"Bu", "ChuiZi"}, {"ChuiZi", "JianDao"}, {"JianDao", "Bu"} }; int current = 0, end = 0; while(1) { // 赢若干次 for(int j = 0; j < v[current % n]; j++) {    string x;    cin >> x; if(x == "End") {     end = 1; // "End"代表输入结束，设置标志并退出循环 break; }    cout<<ying[x]<<endl; } if(end) break; // 输一次   string x;   cin >> x; if(x == "End") break;   cout<<shu[x]<<endl;   current++; // 换下一组随机数 } return 0; } 

如果对方出招太多，则随机数按顺序循环使用，所以是 v [current % n]

7-7 阶乘的非零尾数 (20分)

#include<bits/stdc++.h> using namespace std; int main() {     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //加快 cin 与 cout的速度  int n,k;     cin>>n>>k; // N 阶乘末尾的第一个非零 k 位数 int base=pow(10,k); //对 k位数 取模  int t=n; // 找个替代，防止 n 改变  int ans=0; // N 阶乘末尾的 0 的个数  while(t) //用于求 N 阶乘末尾的 0 的个数的方法（不懂的话硬记着就好）  {         ans+=t/5;         t/=5; } int cnt2=ans,cnt5=ans,ans1=1; for(int i=1;i<=n;i++) //求阶乘  { int t=i; while(cnt2&&t%2==0)t>>=1,cnt2--; // 减少因子 2 的个数  while(cnt5&&t%5==0)t/=5,cnt5--; // 减少因子 5 的个数          ans1=ans1*t%base; //结果取模  }     cout<<setw(k)<<setfill('0')<<ans1<<' ';     cout<<ans<<endl; return 0; } 

末尾 10 的个数代表了因子 2 和 5 的个数，所以在求阶乘时提前除去因子 2 和 5 就可以简化取模时的运算

7-8 三足鼎立 (25分)

//先看最下面的题解 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; int a[maxn]; int main() {     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); //加快 cin 与 cout的速度  int n,s;     cin>>n>>s; //n ,相当于已知 A  for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+1+n);     ll ans=0; for(ll i=1;i<=n;i++) //穷举 B  { //寻找 C,从 a+i+1 开始搜索可以避免 B 与 C 重复         ll q=lower_bound(a+1+i,a+1+n,s+a[i])-(a+1); //不满足 A+B>C 的最小下标          ll p=upper_bound(a+1+i,a+1+n,abs(s-a[i]))-(a+1); //满足 B-A<C 与 A-B<C 的最大下标         ans+=q-p; //中间就是满足条件的 C，加起来即可  }     cout<<ans<<endl; return 0; } 

思路：ABC三个国家，已知 A，穷举 B，寻找 C
寻找的条件：满足 A+B>C 与 B-A<C 与 A-B<C

关于 lower_bound/upper_bound

lower_bound( begin,end,num)查找第一个大于或等于 num 的数字，找到返回该数字的地址，不存在则返回 end
upper_bound( begin,end,num)查找第一个大于 num 的数字，找到返回该数字的地址，不存在则返回 end