记录一下div3第一次
a
k
ak
ak,虽然是因为这次很简单的原因…不过还是很开心hhh
A , B A,B A,B太简单了就不写了,然后下面每一题都写了比较详细的题解^_^.
目录~
- [1475C. Ball in Berland(容斥原理)](https://issue-is-vegetable.blog.csdn.net/article/details/113157043)
- [1475D. Cleaning the Phone(二分+前缀和)](https://issue-is-vegetable.blog.csdn.net/article/details/113156561)
- [1475E.Advertising Agency(排序)](https://issue-is-vegetable.blog.csdn.net/article/details/113156270)
- [1475F. Unusual Matrix(构造,模拟)](https://issue-is-vegetable.blog.csdn.net/article/details/113155561)
- [1475G. Strange Beauty(dp+优化)](https://issue-is-vegetable.blog.csdn.net/article/details/113155261)
1475C. Ball in Berland(容斥原理)
因为只选择两组男女关系
枚举当前选择第 i i i组,然后去 [ i + 1 , n ] [i+1,n] [i+1,n]选择一组男女关系
如果不考虑冲突关系,答案直接加上 n − i n-i n−i
然而后面 n − i n-i n−i个可能和这个男生有冲突,需要减掉
后面 n − i n-i n−i个可能和这个女生有冲突,需要减掉
这样写可能多减了,因为有的组男女同时和第 i i i组冲突
所以需要加上后面 n − i n-i n−i组中男女关系和第 i i i组相同的对数
就是一个容斥原理, P ( a ∪ b ) = P ( a ) + P ( b ) − P ( a b ) P(a∪b)=P(a)+P(b)-P(ab) P(a∪b)=P(a)+P(b)−P(ab)
男女关系是一个二元组,用 m a p map map来存
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 3e5+10; int n1,n2,k,l[maxn],r[maxn],L[maxn],R[maxn]; typedef pair<int,int>p; map<p,int>mp; signed main() { int t; cin >> t; while( t-- ) { long long ans=0; cin >> n1 >> n2 >> k; for(int i=1;i<=k;i++) scanf("%d",&l[i]); for(int i=1;i<=k;i++) scanf("%d",&r[i]); for(int i=1;i<=k;i++) mp[p(l[i],r[i])]++,L[l[i]]++,R[r[i]]++; for(int i=1;i<=k;i++) { mp[p(l[i],r[i])]--; L[l[i]]--; R[r[i]]--; if( i==k ) break; int pre = k-i; ans += pre-L[l[i]]-R[r[i]]+mp[p(l[i],r[i])]; // cout << pre-L[l[i]]-R[r[i]]+mp[p(l[i],r[i])] << endl; } cout << ans << endl; mp.clear(); } }
1475D. Cleaning the Phone(二分+前缀和)
因为 b i b_i bi只有 1 1 1和 2 2 2两种,考虑分成 a 1 , a 2 a1,a2 a1,a2两个数组装相应的 a i a_i ai
a 1 a1 a1里的 a i a_i ai的 b i = 1 b_i=1 bi=1,那么 a 1 a1 a1里的物品具有明显的优劣关系, a i a_i ai越大的越好
所以 a 1 , a 2 a1,a2 a1,a2按照 a i a_i ai从大到小排序
枚举 a 1 a1 a1数组取前 i i i个物品
此时可以使用二分去快速得到一个最小的 i n d e x index index使得取走前 i n d e x index index大的 a 2 a2 a2元素
满足条件,然后更新答案即可
dp似乎是行不通的(可能可以???)…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 3e5+10; const int inf = 1e15; int t,n,m,a[maxn],b[maxn],a1[maxn],a2[maxn],pre[maxn]; bool com(int a,int b){ return a>b; } signed main() { int t; cin >> t; while( t-- ) { cin >> n >> m; for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=n;i++) scanf("%lld",&b[i]); a1[0]=a2[0]=0; for(int i=1;i<=n;i++) { if( b[i]==1 ) a1[++a1[0]] = a[i]; else a2[++a2[0]] = a[i]; } sort( a1+1,a1+1+a1[0],com ); sort( a2+1,a2+1+a2[0],com ); for(int i=1;i<=a2[0];i++) pre[i] = pre[i-1]+a2[i]; //ö��ѡ��s�� int ans = inf,sum=0; for(int i=1;i<=a1[0];i++) { sum+=a1[i]; if( sum>=m ){ ans=min(i,ans); break; } int yu = m-sum; int index = lower_bound( pre+1,pre+1+a2[0],yu )-pre; if( index==a2[0]+1 ) continue; ans = min( ans,i+index*2 ); } int index = lower_bound( pre+1,pre+1+a2[0],m )-pre; if( index!=a2[0]+1 ) ans = min( ans,index*2 ); if( ans==inf ) cout << -1 << endl; else cout << ans << endl; } }
1475E.Advertising Agency(排序)
由于选择的数字需要最大
那么首先把 a a a数组排序,从大到小选 k k k个肯定是最大的
然后为什么最大值有几种方案呢??
因为和 a k a_k ak相等的有很多
设从大到小选的过程中选了 x x x个 a k a_k ak
数组中一共有 s u m sum sum个 a k a_k ak
那么方案数是 C s u m x C_{sum}^{x} Csumx
除了和 a k a_k ak相等的,其他数字都不能变动
比 a k a_k ak大的都进来了,小的进来答案会变小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#include <bits/stdc++.h> using namespace std; #define int long long const int maxn =1e5+10; const int mod = 1e9+7; int n,t,a[maxn],k,fac[maxn]; bool com(int a,int b){ return a>b; } int quick(int x,int n) { int ans = 1; for( ;n;n>>=1,x=x*x%mod ) if( n&1 ) ans = ans*x%mod; return ans; } int C(int n,int m) { if( n<m ) return 0; return fac[n]*quick( fac[m]*fac[n-m]%mod,mod-2 )%mod; } signed main() { fac[0] = 1; for(int i=1;i<=1000;i++) fac[i] = fac[i-1]*i%mod; cin >> t; while( t-- ) { cin >> n >> k; for(int i=1;i<=n;i++) scanf("%lld",&a[i] ); sort( a+1,a+1+n,com ); int ans = 0, x=-1e9, sum = k; for(int i=1;i<=k;i++) { if( a[i]!=a[i-1] ) x=a[i]; } for(int i=1;i<=n;i++) { if( a[i]==x ) ans++; if( a[i]>x ) sum--; } //��ans��ѡ��sum printf("%lldn",C(ans,sum) ); } }
1475F. Unusual Matrix(构造,模拟)
发现每一行,每一列如果操作,必然是奇数次操作
否则,偶数次的操作和不操作没有区别。
而且,当 a i , j = = b i , j a_{i,j}==b_{i,j} ai,j==bi,j时每个格子被操作偶数次
当 a i , j ! = b i , j a_{i,j}!=b_{i,j} ai,j!=bi,j时这个格子被操作奇数次
设 r o w i row_i rowi为第 i i i行操作次数, l i e j lie_j liej为第 j j j列操作的次数
那么 a i , j a_{i,j} ai,j的操作次数等于 r o w i + l i e j row_i+lie_j rowi+liej
假如我们枚举第一行的操作次数,那么由于 a 1 , 1 a_{1,1} a1,1到 a 1 , n a_{1,n} a1,n(第一行)的操作次数已知
那么不久可以直接解得 c o l 1 col_1 col1到 c o l n col_n coln吗
然后由于 a 1 , 1 a_{1,1} a1,1到 a n , 1 a_{n,1} an,1(第一列)的操作次数已知,不久可以解得 r o w 2 row_2 row2到 r o w n row_n rown吗
现在已知 r o w row row和 l i e lie lie,叫你去判断每个格子是否合法不会判断吗??
所以只需要分第一行操作偶数次和奇数次讨论一下就好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#include <bits/stdc++.h> using namespace std; #define int long long const int maxn =1009; const int mod = 1e9+7; int n,t; int row[maxn],lie[maxn]; char a[maxn][maxn],b[maxn][maxn]; bool ok() { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if( a[i][j]==b[i][j]&&(row[i]+lie[j])%2==0 ) continue; else if( a[i][j]!=b[i][j]&&(row[i]+lie[j])%2==1 ) continue; else return false; return true; } signed main() { int t; cin >> t; while( t-- ) { cin >> n; for(int i=1;i<=n;i++) scanf("%s",a[i]+1); for(int i=1;i<=n;i++) scanf("%s",b[i]+1); //第一行不操作 row[1] = 0; for(int i=1;i<=n;i++) if( a[1][i]==b[1][i] ) lie[i] = 0; else lie[i] = 1; for(int i=2;i<=n;i++) if( a[i][1]==b[i][1] ) row[i] = lie[1]; else row[i] = lie[1]^1; if( ok() ) { printf("YESn"); continue; } row[1] = 1; for(int i=1;i<=n;i++) if( a[1][i]==b[1][i] ) lie[i] = 1; else lie[i] = 0; for(int i=2;i<=n;i++) if( a[i][1]==b[i][1] ) row[i] = lie[1]; else row[i] = lie[1]^1; if( ok() ) printf("YESn"); else printf("NOn"); } }
1475G. Strange Beauty(dp+优化)
考虑最终状态
数组中任意两个数都是彼此的因子(倍数)
那么如果从小到大排序,一定有 a i % a i − 1 = = 0 a_i%a_{i-1}==0 ai%ai−1==0
于是我们一开始就对 a a a数组从小到大排序,按照这个规则去 d p dp dp
定义 f [ i ] f[i] f[i]为以 a i a_i ai结尾,在 [ 1 , a i ] [1,a_i] [1,ai]最多可以选多少个数字
那么对于每一个 i i i,去 [ 1 , i − 1 ] [1,i-1] [1,i−1]找一个符合条件的 j j j满足 a i % a j = = 0 a_i%a_j==0 ai%aj==0
f [ i ] = m a x ( f [ i ] , f [ j ] + 1 ) f[i]=max(f[i],f[j]+1) f[i]=max(f[i],f[j]+1)
但是这样复杂度是 O ( n 2 ) O(n^2) O(n2)
不难发现符合条件的 a j a_j aj都是 a i a_i ai的因子,于是我们直接去枚举 a i a_i ai的因子进行转移
复杂度降到 O ( n s q r t ( n ) ) O(nsqrt(n)) O(nsqrt(n))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include <bits/stdc++.h> using namespace std; const int maxn =2e5+10; const int mod = 1e9+7; int f[maxn],a[maxn],id[maxn]; signed main() { int t; cin >> t; while( t-- ) { int n,ans=0; cin >> n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort( a+1,a+1+n ); for(int i=1;i<=n;i++) { f[i] = 1; for(int j=1;j*j<=a[i];j++) { if( a[i]%j!=0 ) continue; int last = a[i]/j; f[i] = max( f[i],f[id[j]]+1 ); f[i] = max( f[i],f[id[last]]+1 ); } id[a[i]] = i; ans = max( ans,f[i] ); } printf("%dn",n-ans); for(int i=1;i<=200000;i++) f[i] = id[i] = 0; } }
最后
以上就是漂亮白猫最近收集整理的关于Codeforces Round #697 (Div. 3 A-G)题解(新鲜)的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。
发表评论 取消回复