A - Download More RAM 题目大意
日常卡C
(换了个世界观)给定 n n n个道具,体积为 a [ i ] a[i] a[i],效果为 b [ i ] b[i] b[i],当前容量为 k k k。每次可以选择一个体积小于等于当前容量的物品,选择后容量扩大为 k + b [ i ] k + b[i] k+b[i]。问容量最大可以扩大到多大。
思路直接排序优先选择体积小&&效果大的物品,然后贪心选择直到无法再选为止。复杂度取决于排序 O ( n log n ) O(n log n) O(nlogn)。
Accepted Code#includeB - GCD Arrays 题目大意using namespace std; const int N = 110; struct node{ int a, b; const bool operator< (const node &x) const { if(a == x.a) return b > x.b; return a < x.a; } }p[N]; inline void solve(){ int n, k; cin >> n >> k; for(int i = 1; i <= n; i++) cin >> p[i].a; for(int i = 1; i <= n; i++) cin >> p[i].b; sort(p + 1, p + 1 + n); for(int i = 1; i <= n; i++){ if(k < p[i].a) break; k += p[i].b; } cout << k << endl; } signed main(){ int t = 0; cin >> t; while(t--) solve(); return 0; }
给定一个区间 [ l , r ] [l,r] [l,r],每次 *** 作可以选择两个数字删除,并将他们的乘积加入原序列。问能否通过 k k k次以内的 *** 作,使得整个序列 G C D GCD GCD大于 1 1 1.
思路直接统计区间奇数个数,最少 *** 作次数为所有奇数合并再乘一个偶数的 *** 作次数,即为奇数的个数$-1 + 1 = $奇数个数
Accepted Code#includeC - Meximum Array 题目大意using namespace std; inline void solve(){ int l, r, k; cin >> l >> r >> k; if(l == r){ if(l > 1) cout << "YES" << endl; else cout << "NO" << endl; return; } int res = 0; int det = r - l; res += (det >> 1); if(((l & 1) == 1) || ((r & 1) == 1)) res++; if(res > k) cout << "NO" << endl; else cout << "YES" << endl; } signed main(){ int t = 0; cin >> t; while(t--) solve(); return 0; }
当 a a a不为空时有一下 *** 作:
选择一个整数 k ( 1 ≤ K ≤ ∣ a ∣ ) k(1≤K≤|a |) k(1≤K≤∣a∣)。
将数组 a a a的前 k k k个数字的 M E X MEX MEX附加到数组 b b b的末尾,并从数组 a a a中删除它们,从而移动 a a a中其余数字的位置。
要求输出字典序最大的 b b b串。
思路单独记录每个数字的出现次数,然后暴力查找MEX,模拟删除即可。
怎么会卡这题
#includeD - Peculiar Movie Preferences 题目大意using namespace std; const int N = 2e5 + 10; int vis[N], a[N], ans[N], tag[N]; inline void solve(){ int n = 0, cnt = 0; cin >> n; memset(tag, 0, (n + 5) * sizeof(int)); for(int i = 1; i <= n; i++){ cin >> a[i]; tag[a[i]]++; } for(int id = 0; id < n;){ int pos = 0; while(tag[pos]) ++pos; if(!pos){ ans[++cnt] = 0, id++; continue; } else ans[++cnt] = pos; memset(vis, 0, (n + 5) * sizeof(int)); for(int i = pos; i;){ id++; if(!vis[a[id]] && a[id] < pos) i--, vis[a[id]] = true; tag[a[id]]--; } } cout << cnt << endl; for(int i = 1; i <= cnt; i++) cout << ans[i] << (i == cnt ? 'n' : ' '); } signed main(){ int t = 0; cin >> t; while(t--) solve(); }
给定 n n n个字符串,每个串长度不超过 3 3 3,问能否通过删除某些字符串,使剩余的串按顺序连接后为回文串。
思路每个串的长度 ≤ 3 leq 3 ≤3,那么就可以进行分类讨论了:
如果某个串长度为 1 1 1,YES,它自己就能构成回文串如果某个串长度为 2 2 2:
AA型:本身可构成回文串,YESAB型:可以对前后提供贡献,先查找之前有无BA,再插入集合维护即可 如果某个串长度为 3 3 3:
ABA型:本身可构成回文串,YESABC型:
为前后提供ABC贡献,先查找之前有无CBA,再插入集合维护为前面提供BC贡献,查找之前有无CB为后面提供AB贡献,查找之后有无BA(这里无法按顺序处理,需要反序扫描一遍) Accepted Code
#includeusing namespace std; const int N = 1e5 + 10; string a[N]; set st; inline void solve(){ int n = 0; cin >> n; bool flag = false; st.clear(); for(int i = 1; i <= n; i++){ cin >> a[i]; if(flag) continue; if(a[i].length() == 1) flag = true; if(a[i].length() == 2 && a[i][0] == a[i][1]) flag = true; if(a[i].length() == 3 && a[i][0] == a[i][2]) flag = true; if(a[i].size() == 2){ string rev = ""; rev += a[i][1], rev += a[i][0]; if(st.count(rev)) flag = true; } else if(a[i].size() == 3){ string rev1 = "", rev3 = ""; rev1 += a[i][2], rev1 += a[i][1], rev1 += a[i][0]; rev3 += a[i][2], rev3 += a[i][1]; if(st.count(rev1) || st.count(rev3)) flag = true; } st.insert(a[i]); } if(!flag){ st.clear(); for(int i = n; i >= 1; --i){ if(a[i].size() == 3){ string rev = ""; rev += a[i][1], rev += a[i][0]; if(st.count(rev)){ flag = true; break; } } st.insert(a[i]); } } if(flag){ cout << "YES" << endl; return; } else cout << "NO" << endl; } signed main(){ int t = 0; cin >> t; while(t--) solve(); return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)