A - Cut
- 题意:
将数组的后k个字符移到前面 - 思路:
- 可以用rotate()函数让数组中的元素滚动旋转
rotate(v.begin(), v.begin() + n - k, v.end());
- 直接输出后k个元素,再输出前n-k个元素
for(int i=n-k;i<n;i++) write(v[i]); for(int i=0;i<n-k;i++) write(v[i]);
- 可以用rotate()函数让数组中的元素滚动旋转
B - Decrease 2 max elements
- 题意:
每次令数组中最大的两个数-1,求多少次操作后只剩下一个数 - 思路:
注意到 2≤N≤100 , 1<=A[i]<=100
两眼一闭就是写,直接就上priority_queue,不带半点智慧和思考,题干怎么说就怎么写,怎么简单怎么来void solve() { priority_queue<int> q; int n = read(); for(int i=0;i<n;i++) q.push(read()); int cnt = 0; while(q.size()>1){ int t1 = q.top(); q.pop(); int t2 = 1; if(q.size()) t2 = q.top(); q.pop(); if(t1 - 1) q.push(t1-1); if(t2 - 1) q.push(t2-1); cnt++; } cout<<cnt<<endl; }
C - Triple Attack
- 题意:
从前往后遍历数组A, 每次操作 T+=1, T%3!=0 的时候 A[i]-=1, T%3==0 的时候 A[i]-=3; - 思路:
每轮 T += 3, A[i] -= 5 , 所以当 T%3==0 的时候直接将 A[i] 减到5以下,再逐次操作
code:int n = read(); vector<int> v; for(int i = 0; i < n; i++) v.push_back(read()); int t = 1; for(int i=0; i < n; i++){ while(v[i]>0){ if(t%3==0 && v[i]>0) v[i]-=3,t++; else if(t%3!=0 && v[i]>0) v[i]-=1,t++; if(t%3==0 && t>=3 && v[i]>=5) t+=v[i]/5*3,v[i]%=5; } } cout<<t-1<<endl;
D - Minimum Steiner Tree
- 题意:
给一个树,再给一些关键节点,求如果要保留这些关键节点则至少应该保留哪些节点 - 思路:
显然给出的关键节点必须保留,考虑到是树可以用dfs,而因为关键节点必须保留所以可以任意选一个关键节点当作根
从根往深处搜索,如果该节点为关键节点则该节点必然需要保留,标记此节点;
如果该节点往下的任一 一节点为关键节点,该节点同样不可或缺,标记节点;
可以根据dfs的返回值知道该节点往下的分支是否包含关键节点。int n, k; vector<vector<int>> e; unordered_map<int,int> mp,st,vis; int dfs(int x){ int ret = 0; vis[x] = 1; //记忆化搜索,搜过的就不再搜了 for(auto it:e[x]){ if(!vis[it]){ ret |= dfs(it); //按位与,如果返回值有1则ret为1 } } if(mp[x]) ret = 1; if(ret) st[x] = 1; return ret; } void solve() { n = read(), k = read(); e.resize(n+1); for(int i=1;i<n;i++){ int u = read(), v = read(); e[u].push_back(v); e[v].push_back(u); } int ed = 0; for(int i=0;i<k;i++){ ed = read(); mp[ed] = 1; //记录该节点为关键节点 } dfs(ed); int ans = 0; for(auto it:st){ if(it.se) ans++; } cout<<ans<<endl; }