(0条未读通知) 牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ
国庆中秋玩后第一场vp,选择了一个比较简单的周赛,兴许是想挑软柿子捏🤭,写了5题还行,做个总结,一步一步恢复状态。
这场的D是个典题,位运算贪心,每一位贡献独立,贪心从高位,在兼顾前面高位的选择下添加新的位的贡献,是否能够满足条件。
A题
模拟
给定总队伍数\(n\)和排名\(k\),问能拿那个牌子。
题解:规定金奖数量为\(d=\lceil \frac{x}{10}\rceil\),银牌数量为\(2\times d\),铜牌数量为\(3\times d\),也就是\([1,d]\)为金奖,\([d+1,3\times d]\)为银奖,\([3\times d+1,6\times d]\)为铜奖,剩下的就打铁啦。那我们看\(k\)在那个区间就好。
B题
贪心
小苯有\(n\)张带点数的卡牌,第\(i\)张的卡牌点数为\(a_i\),小苯现在要选一张去和小红比大小,他想选一张尽可能大的牌,现在小苯可以选择以下操作任意次:
- 任意地选择 \(k\ (1 \leqq k \leqq |a|)\) 张牌(不能超过当前的牌总数)弃掉,同时获得一张点数为 \(k\) 的牌。
现在求小苯能够获得的最大的牌的点数是多少。
题解:我们考虑小苯能够获得的牌,因为弃牌是会新增加一张牌,对剩下的牌的点数没有影响,所以我们考虑使用操作和不使用操作能够获得的最大点数就好,在二者取\(max\)。
C题
思维
小红给了小苯一个长度为 \(n\) 的 \(01\) 串,一开始所有的字符均为黑色,小红希望小苯将所有的字符均涂成红色。
为此小苯可以做以下操作任意次:
$\hspace{23pt}\bullet\ $ 选择一个非空的子序列(可以不连续),满足子序列中所有的字符均为黑色,且此子序列是一个回文的字符串,将这个子序列的所有字符均涂红。
现在找到达到小红要求的最小操作次数。
题解:很容易可以看出答案上限为2,也就是我们单独操作1和0,这样一定2次就可以。然后我们考虑什么时候可以一次就行,发现只有当给定的01串为回文串,那么一次就行。用一个双指针判断一下就好。
时间复杂度为\(O(n)\)。
D题
贪心,位运算
小苯在研究一种特殊的数字配对问题。给定 \(2\times n\) 个正整数 \(a_1,a_2,...,a_{2n}\),需要将它们恰好平分成 \(2\) 组,每组的"配对值"定义为每组 \(n\) 个数的按位与(\(\rm AND\))。
定义两个组的"总和谐度"为两组"配对值"的最大值。
现在小苯想知道,在所有可能的分组方式中,能够获得的最大总和谐度是多少?
题解:我们从答案入手,从高到底考虑答案的每一位二进制,有\(ans_i=1\),当且仅当\(\sum_{j=1}^{2\times n}{a_{j,i}=1}\geq n\),\(a_{j,i}\)表示\(a_j\)的二进制第\(i\)位。由于每一位的贡献是独立的,且高位的贡献大于所有低位贡献和,所以从高位贪心一定是对的,每次我们检查在保证高位成立的情况下,新添加的位也能满足条件,那么将新添加的位的贡献加入答案,这里判断条件即为上面那个式子。
时间复杂度为\(O(n\log{V})\)。
void solve() {int n;cin >> n;vector<int> a(2*n+1);for(int i=1;i<=2*n;i++){cin >> a[i];}auto check=[&](int mid)->bool{int cnt=0;for(int i=1;i<=2*n;i++){if((a[i]&mid)==mid) cnt++;}return cnt>=n;};int ans=0;for(int i=31;i>=0;i--){if(check(ans|1<<i)){ans|=1<<i;}}cout << ans << endl;
}
E题
数学,容斥原理
由于经常做不出 \(\gcd\) 题,因此小苯不喜欢 \(\gcd\),所以小苯认为:数组的 \(\gcd\) 不存在于数组中的话,则该数组是美丽的。
他现在有一个长度为 \(n\) 的序列 \(a\),请你帮他算一算,\(a\) 中有多少个非空子序列(不要求连续)是美丽的数组吧。
题解:一个子序列\(A\),其\(g=\gcd_{v\in A}{(g,v)}\notin A\),我们称这样的子序列为美丽的。那么我们正面去找美丽子序列并不好维护,相反我们不美丽的子序列非常好找,我们枚举\(A\)的\(g\),然后所有\(g\mid v\)的\(v\)显然都可以在\(A\)集合中,且\(A\)集合至少包含一个\(g\),那么就保证了\(A\)的\(gcd=g\),因为值域并不大,这样是可行的。
根据容斥原理:\(美丽子序列数量=2^n-1-不美丽子序列数量\),那么问题转化为求不美丽的子序列数量,我们按照上面的分析可以写出下面公式:
\(sum_g\)可以用因数分解求出,时间复杂度为\(O(n\sqrt{n})\),每次求\(2^k\)用快速幂时间复杂度为\(O(n\log{n})\),最后总时间复杂度为为\(O(n\sqrt{n}+n\log{n})\)。
#include <bits/stdc++.h>
using namespace std;
#define inf 1e18
#define endl '\n'
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 9, M = 2e5 + 9, mod = 998244353;
int ksm(int b,int p){int res=1;while(p){if(p&1) res=res*b%mod;b=b*b%mod;p>>=1;}return res;
}
void solve() {int n;cin >> n;int mx=0;vector<int> a(n+1),vis(n+1);for(int i=1;i<=n;i++){cin >> a[i];vis[a[i]]++;mx=max(mx,a[i]);}
// sort(a.begin()+1,a.end(),greater<int>());vector<int> cnt(n+1);for(int i=1;i<=n;i++){for(int j=1;j*j<=a[i];j++){if(a[i]%j==0){cnt[j]++;if(a[i]/j*a[i]/j!=a[i]) cnt[a[i]/j]++;}}}int ans=ksm(2,n)-1;for(int g=1;g<=mx;g++){if(vis[g]){ans=(ans-(ksm(2,vis[g])-1)*ksm(2,cnt[g]-vis[g])%mod+mod)%mod;}}cout << ans << endl;
}
/*
分解每个数的因数,然后统计gcd为g的每个子序列个数
*/
signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {solve();}return 0;
}