(QAQ我会更新完的)
A 组队比赛
题目类型:思维
题目链接:
题目大意:
给你四个数组,两两一组,每组实力值为队内实力值之和,求解两组差值最小
解题思路:
四个数组排序,最大与最小,第二与倒二,绝对值下差值即可
代码:
int a[4]; int main(){ cin >> a[0] >> a[1] >> a[2] >> a[3]; sort(a, a+4); cout << abs(a[0] + a[3] - a[1] - a[2]) << '\n'; }
B 每日一报
题目类型:模拟、排序
题目链接:
题目大意:
给你一份n个学生的数据,里面包含学生的测温时间、学号、体温三个信息,现在要求你取出大于38.0的学生信息,并按照如下要求进行排序
链接:https://ac.nowcoder.com/acm/contest/5278/B
来源:牛客网
报送日期不一致的,则日期较近的在上,日期较久远的在下;
报送日期一致体温不一致的,则体温高的在上,体温低的在下;
报送日期和体温都一致的,则学号小的在上,学号大的在下。
解题思路:
通过结构体排序实现
代码:
struct sit{ string day, num; DB tem; } a[101]; bool cmp (sit fir, sit sed){ if (fir.day != sed.day) return fir.day > sed.day; else if (fir.tem != sed.tem) return fir.tem > sed.tem; else { return fir.num < sed.num; } } int main(){ int n, k = 0; cin >> n; REP(i, n){ string rday, rnum; DB rtem; cin >> rday >> rnum >> rtem; if (rtem >= 38.0) a[k].day = rday, a[k].num = rnum, a[k].tem = rtem, k++; } OT(k); sort(a, a+k, cmp); REP(i, k) { cout << a[i].day << " " << a[i].num << " "; printf("%.1f\n", a[i].tem); } }
C 最长非公共子序列
题目类型:思维
题目链接:
题目大意:
给你两段字符串,现在要求你求解,最长不相同子序列的长度
解题思路:
其实很简单,原比最长公共子序列容易的多,两个字符串完全相同的情况下是不可能有不相同子序列的,而一但两个字符串不同直接输出较长那个字符串的就可以了,简单的思维题
代码:
int main(){ string s1, s2; cin >> s1 >> s2; if (s1 == s2) cout << "-1" << '\n'; else cout << max(SZ(s1), SZ(s2)) << '\n'; }
D 组队比赛
题目类型:思维
题目链接:
题目大意:
给你一个n,要求你求解出最多01字符串,这些字符串要求相互不是子串,且任意两两长度不同
解题思路:
实际上当你写几个01字符串你会发现几个要点
- 1或0会是所有长度大于等于的字符串的子串(这一点是告诉你要特判n=2的情况)
- 两个1中间不断加0比不可能是上一串的子串
针对第二个我写几个,就很好理解了,
11
101
1001
10001
100001
你会发现恰好满足长度不一致,且不互为子串的条件(00也一样),所以只需要特判n=1和n=2的情况就可以了
代码:
int main(){ int n; cin >> n; if (n == 1){ cout << 1 << '\n' << 1 << '\n';} else if (n == 2) cout << "2\n" << 0 << '\n' << "11" << '\n'; else { cout << n - 1 << '\n'; REP(i, n - 1){ cout << "1"; REP(j, i){cout << "0";} cout << 1 << '\n'; } } }
E 组队比赛
题目类型:思维
题目大意:
给你一个长度为n的数组,每个位置的值表示美味度(即),你可以从头或者从尾食用,一秒只能食用一个,并且未被食用的部分会美味度-1,要求你求解最大的总美味度
解题思路:
这题你可能会思考,到底是从头吃呢还是从尾吃呢,其实是没差别的,因为
他用数字标识了每个部分的美味度(可能是负的)
美味度可能是负值,你要减去的数量就一定会
可以边加边减,也可以全部加完再减
代码:
有人可能会是第一种方法,却wa了,n必须要是是LL,为什么n要是LL呢?
明明题目给的数据没有溢出啊,是因为在计算的时候溢出的,这个可能导致你的wa(还好我用的是第二个方法QAQ)
int main(){ LL n; cin >> n; LL ans = 0; REP(i, n){ LL x; scanf("%lld",&x); ans += x; } ans -= (n - 1) * n / 2; OT(ans); }
int main(){ int n; cin >> n; LL ans = 0; REP(i, n){ int x; scanf("%d",&x); ans += x - i; } OT(ans); }
F 组队比赛
题目链接:
题目类型:模拟
题目大意:
母亲节和父亲节你需要送礼,对于每一个日期,输出下一个需要送礼的日子(下一个需要送礼的日子可能是母亲节也可能是父亲节)
解题思路:
依照模拟,需要判断的实际上就是下一个节日是什么,
母亲节在8到14之间变动
if(a[i] < 8) a[i] += 7;
,父亲节在15到21之间变动,
if(b[i] < 15) b[i] += 7;
代码:
const int maxn = 200; int a[maxn], b[maxn]; int main(){ int n = 0, p; a[0] = 14; b[0] = 18; FOR_1(i, 1, 103) { a[i] = a[i-1]-1; b[i] = b[i-1]-1; if(i % 4 == 0 && i != 100) { a[i]--; b[i]--; }//闰年 if(a[i] < 8) a[i] += 7; if(b[i] < 15) b[i] += 7; } int _; for(scanf("%d", &_); _; _--){ int y, m, d;scanf("%d%d%d",&y,&m,&d); n = y - 2000; //易知是从2000年开始 if(m > 6 || m == 6 && d >= b[n]) printf("Mother's Day: May %dth, %d\n",a[n+1], y+1); else if(m < 5 || m == 5 && d < a[n]) printf("Mother's Day: May %dth, %d\n",a[n], y); else if(b[n]!=21) printf("Father's Day: June %dth, %d\n",b[n], y); else printf("Father's Day: June 21st, %d\n", y); } }
G 血压游戏
题目链接
题目类型:树
题目大意:
官方题意
Compute 有一棵 n 个点,编号分别为 1∼n 的树,其中 s 号点为根。
Compute 在树上养了很多松鼠,在第 i 个点上住了 ai 个松鼠。
因为某些缘故,它们开始同时向根节点移动,但它们相当不安分,如果在同一个节点上,它们就会打起来,简单地来说以下事件会依序发生:
如果一个节点上有 2 只或 2 只以上的松鼠,他们会打架,然后这个节点上松鼠的数量会减少 1;
根节点的所有松鼠移动到地面,位于地面上的松鼠不会再打架;
所有松鼠同时朝它们的父节点移动。
所有事件各自都在一瞬间完成,直至树上没有松鼠。
现在 Compute 想知道最终有多少只松鼠到达了地面。
乱搞题意
给你一个树,每个节点上都有个松鼠,所有位置上的松鼠都是向父节点进行移动的,而根节点上的松鼠是向地面上移动,就是从根节点移动出去
每次的操作时这样的
- 如果一个节点上有 2 只或 2 只以上的松鼠,他们会打架,然后这个节点上松鼠的数量会减少 1;
- 根节点的所有松鼠移动到地面,位于地面上的松鼠不会再打架;
- 所有松鼠同时朝它们的父节点移动。
题目问的是最后到地面上的松鼠有多少只
解题思路:
结论1
由于每一步的松鼠都是向父节点移动的,只有一个节点上有2只或者两只以上的松鼠才会打架,那么可以确定 只有同一层上的松鼠才会相互打架
- 因为是同一时间进行向父节点进行移动的
思考1
由于是子节点向父节点进行移动所以可以考虑子树合并的思想,(可以思考是不是树上启发式合并的方法)
思考2
由于是不断的向上移动,也就是每个节点需要不断的查询,那么可能会面临较多次数的查询次数, 可以思考是不是需要使用虚树这个数据结构呢?
虚树中包含了所有的关键点,也包含了所有关键点两两之间的 LCA(lowest common ancestor, 最近公共祖先)(LCA 的数量不超过关键点的个数,稍后有证明),这就保证了虚树不会丧失原有的树形结构,同时尽可能地压缩了树的大小。同时虚树中 uu 到 vv 的边权定义为原树中 uu 到 vv 的最短路径
关于虚树虚树学习笔记
dp[x]=∑t∈sonx ,dp[t]>0max{1,dp[t]−(deep[t]−deep[x])}
for(auto k : ma[rt]) if(k.second) ans += max(1ll, k.second-tag[rt]);
总结
方法1 .利用DFS序合并区间虚树的线段树 && 启发式合并的思想
方法2. 虚树构建一下,再进行dp,根据子节点情况去计算父节点情况(将子节点合并到父节点上),满足通过计算有限集统计总和情况
树上合并式启发
void merge(int x, int y) { int xx = find(x), yy = find(y); if (size[xx] < size[yy]) swap(xx, yy); fa[yy] = xx; size[xx] += size[yy]; }
虚树
我们将两个大小不一样的集合,我们将小的集合合并到大的集合中,而不是将大的集合合并到小的集合中。
为什么呢?这个集合的大小可以认为是集合的高度(在正常情况下),而我们将集合高度小的并到高度大的显然有助于我们找到父亲
让高度小的树成为高度较大的树的子树,这个优化可以称为启发式合并算法。
代码:
const int maxn = 200100; int n, rt; LL ans; int a[maxn]; vector<int> G[maxn]; int fa[maxn], dep[maxn]; LL tag[maxn]; map<int, long long> ma[maxn]; void inse(int u, int d, long long val) { if(!ma[u].count(d)) ma[u][d] = val+tag[u]; else ma[u][d] = max(ma[u][d], tag[u]+1) + val; } void merg(int u, int v) { if(ma[v].size() > ma[u].size()) { swap(ma[u],ma[v]); swap(tag[u],tag[v]); } for(auto i : ma[v]) if(i.second) inse(u, i.first, max(i.second-tag[v], 1ll)); }//将小的子树合并到大的父节点中 void dfs(int u) { dep[u] = dep[fa[u]] + 1; for(int v : G[u]) { if(v == fa[u]) continue; fa[v] = u; dfs(v); merg(u, v); } if(a[u]) inse(u, dep[u], a[u]); tag[u]++; } int main() { scanf("%d%d", &n, &rt);//点的数量和根的编号 for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); for(int i = 2; i <= n; ++i) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } dfs(rt); for(auto k : ma[rt]) if(k.second) ans += max(1ll, k.second-tag[rt]); printf("%lld\n", ans); }
H 纸牌游戏
题目链接:
题目类型:数学
题目大意:
给你一个字符串s 要求你拼出一个长度为 k 的同时能被 3 整除的最大非负整数,并且不能有前导0
解题思路:
什么样的数能被3整除?
该数字的各个位置上的数相加之和能被3整除,那么该数也一定能被3整除
注意
一开始我求简便,是这么做,因为要最大,所以我直接排序,取较大的k个数字,然后判断是否能被3整除,如果不行我选一位去枚举和后面一位交换直到成立,这么做是不对的,因为当需要出现交换两个的时候就会出错,这里给出一下样例,有兴趣的可以跑一下
输入
998244151 3
输出
984
正文
1.我们因为每位字符纯粹是我们自己决定的,没有什么其他的要求,所以我们完全可以统计0-9数字出现的次数去进行组合
2.取余3为1的数字和取余3位2的数字组合之和一定能被3整除,例如2和1
3.我们在组合区间枚举出符合条件最大的就可以
代码:
int cntmod[3]; // 被3取余后只会有3种情况 0, 1, 2,这里对三种情况进行一下计数 int cnt[10]; bool judge(int x, int m){ if (!m) return !x; int a = cntmod[0], b = cntmod[1],c = cntmod[2]; int l0 = max(0, m - b - c), r0 = min(a, m); //一个除3余数为1的数和一个除3余2的数匹配就是一个能被3整除的数,例如1和2, 那么我们就枚举这些组合判断是否能被整除 for(int i = l0; i <= r0; i++){ int t = ((2 * (m - i) - x) % 3 + 3 ) % 3; int l1 = max(0, m - i - c), r1 = min(b, m - i); while(l1 % 3 != t) l1++; if(l1 <= r1) return true; } return false; } void init(){ //初始化 memset(cntmod, 0, sizeof cntmod); memset(cnt, 0, sizeof cnt); } int main(){ int _; for(scanf("%d", &_); _; _--){ init(); string s; int k; cin >> s >> k; int len = SZ(s); FOR(i, 0, SZ(s)){ cnt[s[i] - '0']++; cntmod[(s[i] - '0') % 3]++; } //统计 int n; for(int i = 9, j = n = 0; i >= 0; i--){ //枚举各个数出现次数之前已经统计过了,现在只是运用 while(cnt[i] > 0 && n < k){ int t = (i + j) % 3; cnt[i]--, cntmod[i % 3] --;//如果这数字字i使用了,就减去 if (!judge((3 - t) % 3, k - n - 1)){ cnt[i]++, cntmod[i % 3]++; break;//如果不能被整除那么就回溯,不使用这个i } s[++n] = '0' + i;j = t; } } //s[n + 1] = '\0'; if(n < k || (s[1] == '0' && n > 1)) OT("-1");//出现前导0的情况 else { FOR_1(i, 1, n){ cout << s[i]; } OT(""); } } }