算法竞赛入门【暑期速成计划】（二）

算法竞赛入门【暑期速成计划】（二）

算法竞赛入门【暑期速成计划】（二）

文章目录

​​算法竞赛入门【暑期速成计划】（二）​​​​前言​​

​​为什么突然想学算法了？​​

​​习题训练（码题集）​​

​​1. 赌石​​​​2. 相对马高​​​​3. 小码哥学多重集​​​​4. 区间完数​​​​5. 都相差6​​​​6. 牛顿迭代法​​​​7. 对分法​​​​8. 买马​​​​9. 鸽子洞​​​​10. 饿饿！ 饭饭！​​​​11. 打折​​​​12.队列操作​​​​13.奇偶性​​​​14. 标记祖先​​​​15. 活动安排​​​​16. 滚动的小球​​​​17. 第k小函数值​​​​18. 栈的min​​​​19. 赋值​​​​20. 奇妙秘境​​​​21. 有趣的平衡​​​​22. AND​​

​​总结​​

前言

为什么突然想学算法了？> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。> 但从实际而言，是因为当下快到了考研和找工作的年纪(ಥ_ಥ)，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个暑假速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~

习题训练（码题集）

1. 赌石

【AC代码】

#include #include #include #include using namespace std; typedef long double LD; LD C_div(int k, int n){ LD res = 1; for (int i = n, j = 1; j <= k; i -- , j ++ ) res = res * i / j; for (int i = 1; i <= k; i ++ ) res /= (LD)4.0; return res;} int main(){ int n; cin >> n; n /= 2; printf("%.4llf", 1 - C_div(n - 1, 2 * n - 2)); return 0;}

2. 相对马高

【AC代码】

#include #include #include #include #include #include #include #include using namespace std;#define ll long long#define N 21000ll a[N] = {}, b[N] = {};struct op{ int a, b; }s[N];bool operator < (const op &a, const op &b){ if (a.a == b.a) return a.b < b.b ; else return a.a < b.a;}set p ;int main(){ ll n, h, m ; cin >> n >> h >> m; for(ll i = 1; i <= m; i++){ ll a1,a2; cin >> a1 >> a2; if (a1 == a2) continue; if (a1 > a2) swap(a1,a2); op f; f.a = a1, f.b = a2 ; p.insert(f); } for (set::iterator i = p.begin(); i != p.end();i++){ op f = *i; b[f.a + 1] = b[f.a + 1] - 1; b[f.b] = b[f.b] + 1 ; } for (ll i = 1;i <= n; i++){ a[i] = b[i] + a[i - 1] ; cout << a[i] + h << endl; } return 0;}

3. 小码哥学多重集

【AC代码】

#include using namespace std;void solve(){ set S; int n,k; cin >> n >> k; int a; int maxn = -1; for(int i=1;i<=n;i++){ scanf("%d",&a); S.insert(a); maxn = max(maxn,a); } int minn = 1e9; for(int i=0;;i++){ if(S.find(i)==S.end()){ minn = i; break; } } if(minn0) S.insert(ceil((maxn+minn)/2.0)); cout << (int)S.size() << '\n'; return; }else{ cout << ((int)S.size()+k) << '\n'; }}int main(){ int __ = 1; cin >> __; while(__--){ solve(); } return 0;}

4. 区间完数

【AC代码】

#includeusing namespace std;bool check(int x){ if(x==1) return false; int s = 1; for(int i=2;i*i<=x;i++){ if(x%i==0){ s += i; s += (x/i); } } return s==x;}int main(){ int l,r; cin >> l >> r; for(int i=l;i<=r;i++){ if(check(i)){ cout << i << ' '; } } cout << '\n'; return 0;}

5. 都相差6

【AC代码】

#includeint main() { printf("5 11 17 23 29"); return 0; }

6. 牛顿迭代法

【AC代码】

import java.util.Scanner;import java.util.*;class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); // code here double x = 1.5; double xn = cac1ND(x); System.out.format("%.6f",xn); input.close(); } static double cac1ND(double x){ double x1 = x-(2*x*x*x+4*x*x-7*x-6)/(6*x*x+8*x-7); if(Math.abs(x1-x)<1e-7){ return x1; }else{ return cac1ND(x1); } }}

7. 对分法

【AC】代码

import java.util.Scanner;import java.util.*;class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); // code here System.out.format("%.6f",duifen(-10,0)); input.close(); } static double f(double x){ return x*x-6*x-1; } static double duifen(double a, double b){ if(Math.abs(a-b)<1e-7){ return a; }else{ if(f(a) *f((a+b)/2)<0){ return duifen(a, (a+b)/2); }else{ return duifen((a+b)/2, b); } } }}

8. 买马

【AC代码】

#includeint main() { int n,s[200]; scanf("%d",&n); for(int i=0;i

9. 鸽子洞

【AC代码】

#include using namespace std; int main( ){ long long n, m; cin >> n >> m; int res = n / m; if (n % m) res ++ ; cout << res << endl; return 0;}

10. 饿饿！ 饭饭！

【AC代码】

#includeusing namespace std;typedef long long ll;ll ans = 1;int main( ){ int n,k,w; cin>>n>>k>>w; w*=3; if(w>k) ans=0; for(int i =k-w+1; i<=k;i++) ans*=i; cout<

11. 打折

【AC代码】

#includeusing namespace std;int a[222];int main(){ int n,m; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); int ans=0; int now=0; for(int i=1;i<=n;i++){ if(a[i]<0&&now

12.队列操作

【AC代码】

#include#include#includeusing namespace std;int n,m,q,u,v,t;int h1,h2,h3,t1,t2,t3;int q1[8000001],q2[8000001],q3[8000001];int cmp(int a,int b){ return a>b;}int pop1(int time){ int top1=-1,top2=-1,top3=-1; if(h1<=t1){ top1=q1[h1]+(time-1)*q; } if(h2<=t2){ top2=q2[h2]+(time-h2-1)*q; } if(h3<=t3){ top3=q3[h3]+(time-h3-1)*q; } int k=1; if(top1max(top1,top2)){ k=3; } switch(k){ case 1:h1++;return top1;break; case 2:h2++;return top2;break; case 3:h3++;return top3;break; }}void push1(int x){ int p1=1LL*x*u/v; int p2=x-p1; if(p1

13.奇偶性

【AC代码】

#include using namespace std;long long ans = 0;inline int read() { int ans = 0, f = 1; char ch = getchar(); if (ch == '-') f *= -1; while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { ans = ans * 10 + ch - '0'; ch = getchar(); } return ans * f;}void Merge(int A[], int L, int Mid, int R) { int *Temp = (int *)malloc((R - L + 1) * sizeof(int)); int p = L, q = Mid, k = 0; while (p <= Mid - 1 && q <= R) { if (A[p] <= A[q]) Temp[k++] = A[p++]; else { Temp[k++] = A[q++]; ans += Mid - p; } } while (p <= Mid - 1) Temp[k++] = A[p++]; while (q <= R) Temp[k++] = A[q++]; for (int i = 0; i < k; i++) A[i + L] = Temp[i];}void MSort(int A[], int L, int RightEnd) { if (L < RightEnd) { int mid = (L + RightEnd) / 2; MSort(A, L, mid); MSort(A, mid + 1, RightEnd); Merge(A, L, mid + 1, RightEnd); }}int main() { int n, t, l, r, A[100005]; n = read(); for (int i = 0; i < n; i++) A[i] = read(); MSort(A, 0, n - 1); ans %= 2; scanf("%d", &t); while (t--) { l = read(), r = read(); int p = r - l + 1;//区间长度 if ((p * (p - 1) / 2 % 2))//判断区间反转次数p*(p-1)/2的奇偶 ans ^= 1;//改变奇偶性 if (ans) printf("1\n"); else printf("0\n"); } return 0;}

14. 标记祖先

【AC代码】

#include#include#includeusing namespace std;#define INF 0x3fffffffint pre[100005];//用于保存树形结构int mark[100005];//用于存放各结点最早的标记时间typedef pairP;P Q[100005];//second 表示查询的时间 first表示查询的对象void init(int n) { for (int i = 1; i <= n; i++) { pre[i] = -1; mark[i] = INF; } //pre[1] = 1; mark[1] = 0;//事先标记根结点}int findroot(int x, int y) { if (mark[x] < y) {//该点在查询之前已经标记 return x; } else { int tmp = findroot(pre[x], y); /*路径压缩 按时间顺序倒序处理查询 那么该时间之后的mark操作就没有意义了，可直接进行路径压缩 将路径上的点进行路径压缩，直到到达在该时间之前的一次mark操作那里 */ pre[x] = tmp; return tmp; }}int main() { int n, m; while (scanf("%d%d", &n, &m) != EOF) { if (n == 0 && m == 0) break; init(n); for (int i = 2; i <= n; i++) { scanf("%d", &pre[i]); } long long ans = 0; int cnt = 0;//查询的个数 for (int i = 1; i <= m; i++) { char op; int tmp; scanf("\n%c%d", &op, &tmp); if (op == 'M') { mark[tmp] = min(i, mark[tmp]);//存放最早的标记时间 } else if (op == 'Q') { Q[++cnt] = P(tmp, i); } } for (; cnt > 0; cnt--) { ans += findroot(Q[cnt].first, Q[cnt].second); } cout << ans << endl; }}

15. 活动安排

【AC代码】

#includeusing namespace std;typedef pair PII;PII t[500010];bool cmp(PII a,PII b){ return a.second> n; int l,r; for(int i=1;i<=n;i++){ scanf("%d%d",&l,&r); t[i] = make_pair(l,r); } sort(t+1,t+1+n,cmp); r = t[1].second; int ans = 1; for(int i=2;i<=n;i++){ if(r<=t[i].first){ r = t[i].second; ans++; } } cout << ans <

16. 滚动的小球

【AC代码】

#includeusing namespace std;int main( ){ int n,l,r; scanf("%d%d%d",&n,&l,&r); int x; int ans1 = -1,ans2 = n+1; for(int i=1;i<=l;i++){ scanf("%d",&x); ans1 = max(ans1,x); } for(int i=1;i<=r;i++){ scanf("%d",&x); ans2 = min(ans2,x); } ans2 = n - ans2; int ans; if(l && !r){ ans = ans1; }else if(r && !l){ ans = ans2; }else{ ans = max(ans1,ans2); } cout<

17. 第k小函数值

【AC代码】

#includeusing namespace std;typedef long long ll;struct Node{ int a,b,c;}node[30];ll w[1000010];ll p[1000010];int total;ll calc(int a,int b,int c,int x){ return (ll)a*x*x + (ll)b*x+c;}int main( ){ int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d%d%d",&node[i].a,&node[i].b,&node[i].c); } int x = 1; int ans = 0; bool f = 0; while(true){ if(total>=k){ if(f){ memcpy(p,w,sizeof(ll)*(k+1)); sort(w+1,w+1+total); bool flag = 1; for(int i=1;i<=k;i++) if(w[i]!=p[i]){ flag = 0; break; } if(flag){ ans = w[k]; break; } }else{ f = 1; } } for(int i=1;i<=n;i++){ w[++total] = calc(node[i].a,node[i].b,node[i].c,x); } x++; } cout<

18. 栈的min

【AC代码】

#includeusing namespace std;int total;int sk[1000010];int main( ){ int n; cin>>n; for(int i=1;i<=n;i++){ int t; scanf("%d",&t); if(t==1){ int x; scanf("%d",&x); sk[++total] = x; }else if(t==2){ if(total>=1) total--; }else if(t==3){ printf("%d\n",sk[total]); }else{ int ans = 1e9; for(int i=1; i<=total;i++) ans = min(ans,sk[i]); printf("%d\n",ans); } } return 0;}

19. 赋值

【AC代码】

// 给定一张含有n个结点m条边的无向图，每条边的两个端点奇偶性必须不同，有多少种不同的赋值方式#include using namespace std;#define mem(a) memset(a, 0, sizeof(a))#define dbg(x) cout << #x <<" = " << x <<#define fi(i, l, r) for (int i = l; i < r; i++)#define cd(a) scanf("%d", &a)typedef long long ll;const ll mod = 1e9 + 7;vector a[300010]; // 存图ll Pow[300010] = {1}; // Pow[i] = 2^iint color[300010] = {0}; // 分组情况，默认值0表示未分组int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { // 预处理，计算2^i Pow[i] = (Pow[i - 1] * 2) % mod; } for (int i = 0; i < m; i++) { // 读入图 int l, r; scanf("%d%d", &l, &r); a[l].push_back(r); a[r].push_back(l); } ll ans = 1; // 答案 for (int i = 1; i <= n; i++) { // 遍历所有节点 if (!color[i]) { // 还没被染色（说明还没有被划分到某个子图中） int aNode = 0, bNode = 0; // 二分图A、B中的节点个数 queue q; // bfs队列 function addOneNode = [&](int thisNode, int thisColor) { // 处理一个新的节点 color[thisNode] = thisColor; // 标注分组 q.push(thisNode); // 入队 if (thisColor == 1) // 统计集合中节点的个数 aNode++; else bNode++; }; addOneNode(i, 1); // 先处理这个子图的“源点” while (q.size()) { // 开始BFS int thisNode = q.front(); q.pop(); // 队首节点 int toColor = (color[thisNode] == 1 ? 2 : 1); // 它的相邻节点所属的集合 for (int& toNode : a[thisNode]) { // 遍历这个节点的所有边 if (!color[toNode]) { // 相邻节点还未被分组 addOneNode(toNode, toColor); // 处理这个相邻节点（划分集合、入队、统计） } else { // 这个相邻节点已经被分组了 if (color[toNode] == color[thisNode]) { // 并且和这个节点还被分到了一组中 puts("0"); // 无法划分为二分图，方案数为0 return 0; } } } } ans = (ans * (Pow[aNode] + Pow[bNode])) % mod; // 各个子图的方案数之积 } } cout << ans << endl; return 0;}

20. 奇妙秘境

【AC代码】

#include using namespace std;#define mem(a) memset(a, 0, sizeof(a))#define dbg(x) cout << #x <<" = " << x <<#define fi(i, l, r) for (int i = l; i < r; i++)#define cd(a) scanf("%d", &a)typedef long long ll;int main() { ll n; cin >> n; if (n % 2) { cout << n * (n - 1) * (n - 2) << endl; } else { if (n % 3 == 0) { cout << (n - 1) * (n - 2) * (n - 3) << endl; } else { cout << n * (n - 1) * (n - 3) << endl; } } return 0;}

21. 有趣的平衡

【AC代码】

#include using namespace std;#define mem(a) memset(a, 0, sizeof(a))#define dbg(x) cout << #x <<" = " << x <<#define fi(i, l, r) for (int i = l; i < r; i++)#define cd(a) scanf("%d", &a)typedef long long ll;int main() { int n; cin >> n; int k = 1; while (k <= n) { k *= 2; } int remain = k - n; cout << 1 << endl; cout << k << endl; vector right; int k2 = 1; while (k2 < k) { if (k2 & remain) { right.push_back(k2); } k2 *= 2; } cout << right.size() << endl; for (int i = 0; i < right.size(); i++) { cout << right[i] << ' '; } puts(""); return 0;}

22. AND

【AC代码】

#include using namespace std;#define mem(a) memset(a, 0, sizeof(a))#define dbg(x) cout << #x <<" = " << x <<#define fi(i, l, r) for (int i = l; i < r; i++)#define cd(a) scanf("%d", &a)typedef long long ll;int a[100010];int main() { int n; cin >> n; fi (i, 0, n) // for (int i = 0; i < n; i++) cd(a[i]); // scanf a[i] ll ans = 0; for (int i = 0; i < n; i++) { ll k = a[i]; for (int j = i; j < n; j++) { k &= a[j]; if (!k) break; // 剪枝 ans += k; } } cout << ans << endl; return 0;}

总结

如上，为本周习题小结，题目内容很简单，还望各位算法大佬见谅，另，其中有部分题解参考了网上的标程与解析，如有侵权，请私信我，看到后立删，谢谢！！！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。