建站系统网站建设,灯塔seo,如何改变网站首页栏目,软件正版化情况及网站建设情况文章目录 A Cidoai的吃饭思路code B Cidoai的听歌思路code C Cidoai的植物思路code D Cidoai的猫猫思路code E Cidoai的可乐思路code 牛客小白月赛107
A Cidoai的吃饭
思路
签到题#xff0c;按题意模拟即可
code
void solve(){int n,a,b,c;cin n a 按题意模拟即可
code
void solve(){int n,a,b,c;cin n a b c;int ans0;ansn/a;n%a;ansn/b;n%b;ansn/c;n%c;cout ans endl;return ;
}B Cidoai的听歌
思路
通过模拟不难发现这个序列操作的次数和最终的数字跟这个序列的最小值和最大值有关 如果这个序列的最大值为mx最小值为mn假设最终的数字为x 那么它所需的操作次数就为 ( m x − x ) ( x − m n ) m x − m n (mx-x)(x-mn)mx-mn (mx−x)(x−mn)mx−mn 既然这个数字x跟mx和mn有关那么数字x取到这两个数的平均值显然是最优的 由于操作是先1后-1显然这个平均值要向上取整
code
void solve(){int n;cin n;for(int i1;in;i) cin a[i];int mx0,mninf;for(int i1;in;i){mxmax(mx,a[i]);mnmin(mn,a[i]);}cout mx-mn (mxmn1)/2 endl;return ;
}C Cidoai的植物
思路
考点读题不是模拟优化 这题赛时看了好久才看懂的服啦
显然如果纯模拟这题会超时 O ( n k ) 1 e 8 O(nk)1e8 O(nk)1e8 那么我们就需要考虑如何优化这个 n n n 对于操作1我们只需要将 i i i 行没有植物的数填上x 那么我们就可以用树的思想去优化即用一个动态二维数组e让列数存储行数 如果当前动态数组 e [ i ] e[i] e[i]不为空遍历这个数组将x填进去然后让 e [ i ] e[i] e[i]清空 对于操作2我们将行数b存储列数a即 e [ b ] . p u s h _ b a c k ( a ) e[b].push\_back(a) e[b].push_back(a)
这样就可以将时间复杂度压缩成 O ( m k ) O(mk) O(mk)可以过这道题了
code
const int N2e45;
unsigned n,m,k,seed;
int p[N][210];
vectorint e[210];
unsigned rnd(){int retseed;seed^seed13;seed^seed17;seed^seed5;return ret;
}
void solve(){cin n m k seed;for(int j1;jm;j)for(int i1;in;i){e[j].push_back(i); }for(int t1;tk;t){int op(rnd() % 2) 1;if(op1){int I(rnd() % m) 1;int x(rnd() % (n*m)) 1;if(e[I].empty()) continue;for(auto i : e[I]){p[i][I]x;}e[I].clear();}else{int a(rnd() % n) 1;int b(rnd() % m) 1;p[a][b]0;e[b].push_back(a);}}int ans0;for(int i1;in;i)for(int j1;jm;j){ans^p[i][j]*((i-1)*mj);}cout ans endl;return ;
}D Cidoai的猫猫
思路
对于超过 k k k 的连续子串我们让这个子串的个数变为 k k k 接着考虑如何将 O ( n 2 ) O(n^2) O(n2) 优化成 O ( n ) O(n) O(n) 我们可以倒着遍历如果当前下标为 i i i 时有连续子串的长度为 i i i 那么我们用一个sum累加这个连续子串 i i i在用一个num统计可变的子串个数 显然对于每一个 i i i来说它最小长度为 s u m − n u m ∗ i sum-num*i sum−num∗i 最后按题意求出ans即可
code
const int N5e65;
int cnt[N],ans[N];
void solve(){int n;cin n;string s;cin s;s ;int len1;for(int i1;in;i){if(s[i]s[i-1]) len;else{cnt[len];len1;}}int sum0,num0;for(int i1;in;i) ans[i]n;for(int in;i1;--i){ans[i]-sum-num*i;sumcnt[i]*i;numcnt[i];}int res0;for(int i1;in;i){res^i*ans[i];}cout res endl;return ;
}E Cidoai的可乐
思路
这题非常的简单赛时根本没看QAQ 每个节点的度就是它拥有的子树个数 对于 n n n个节点我们只需要连 n − 1 n-1 n−1 条线即可 我们每次挑选一个节点显然每次用权值最小的节点来建树是最优的 将权值从小到大排序将权值最小的节点的度全填满接着连权值第二小的节点循环往复直到连接 n − 1 n-1 n−1条线 最后统计一个它的权值即可
code
PII a[N];
bool cmp(PII x,PII y){return x.fiy.fi;
}
void solve(){int n;cin n;for(int i1;in;i) cin a[i].fi;for(int i1;in;i) cin a[i].se;sort(a1,a1n,cmp);int ans0,kn-1;for(int i1;in;i){if(a[i].sek){ansa[i].fi*a[i].se;k-a[i].se;}else{ansk*a[i].fi;break;}}cout ans endl;return ;
}
