凡科做数据查询网站,荣耀商城app,wordpress安装博客,枣庄建设局网站C. Ball in Berland
传送门#xff1a;Problem - C - Codeforces
题意#xff1a; 思路#xff1a;容斥原理
考虑 第 i 对情侣组合 #xff0c;男生为 a #xff0c;女生为 b #xff0c;那么考虑与之匹配的情侣 必须没有 a | b
#xff0c;一共有 k 对情侣#x…C. Ball in Berland
传送门Problem - C - Codeforces
题意 思路容斥原理
考虑 第 i 对情侣组合 男生为 a 女生为 b 那么考虑与之匹配的情侣 必须没有 a | b
一共有 k 对情侣 a | b 可以表示为 k - cnt[a] - cnt[b] 1 ( cnt[a] 表示为有男生 a 的方案数 )
AC代码
#includebits/stdc.h
using namespace std;
#define int long long
void solve()
{int n , m , k; cin n m k;vectorint cnta( n 1 ) , cntb( m 1 ) , a( k 1 ) , b( k 1 );for( int i 1 ; i k ; i ) cin a[i] , cnta[a[i]];for( int i 1 ; i k ; i ) cin b[i] , cntb[b[i]];int ans 0;for( int i 1 ; i k ; i ){ans k - cnta[a[i]] - cntb[b[i]] 1;}cout ans / 2 endl;
}
signed main()
{int tt; cin tt;while(tt--)solve();return 0;
}
B. Sifid and Strange Subsequences
传送门Problem - B - Codeforces
题意 思路
我们要保证 | a[i] - a[j] | 的最小值 要 MAX MAX为 a[i] 中的某一个值
AC代码
#includebits/stdc.h
using namespace std;
#define int long long
void solve()
{int n; cin n;vectorint a(n 1);for( int i 1 ; i n ; i ) cin a[i];int cnt 0; sort( a.begin() 1 , a.end() );for( int i 1 ; i n ; i )if( a[i] 0 )cnt; // 此时的 cnt 表示 a[i] 0 的个数int mn 2e18;for( int i 1 ; i cnt ; i )mn min( mn , a[i 1] - a[i] );for( int i cnt 1 ; i n ; i ){// 考虑 a[i] 0 的情况mn min( mn , a[i] - a[i-1] );if( mn a[i] )cnt;else break;}cout cnt endl;
}
signed main()
{int tt; cin tt;while(tt--)solve();return 0;
}
传送门Problem - A - Codeforces
A. Bestie
题意 思路
首先有一个结论 gcd( n , n - 1 ) 1
所以这个题的答案一定 3
分情况讨论即可 答案为 1 2 3时的情况
#includebits/stdc.h
using namespace std;
#define int long long
int gcd( int a , int b )
{return b ? gcd( b , a % b ) : a;
}
void solve()
{int n; cin n;vectorint a( n 1 );for( int i 1 ; i n ; i ) cin a[i];int g 0;for( int i 1 ; i n ; i )g gcd( g , a[i] );int temp1 0 ;for( int i 1 ; i n; i )temp1 gcd( temp1 , a[i] );int temp2 0;for( int i 1 ; i n ; i ){if( i n - 1 )continue;temp2 gcd( temp2 , a[i] );}if( g 1 ){cout 0 endl;}else if( gcd( temp1 , gcd( n , a[n] ) ) 1 ){cout 1 endl;}else if( gcd( temp2 , gcd( n - 1 , a[n - 1] ) ) 1 ){cout 2 endl;}else cout 3 endl;
}
signed main()
{int tt; cin tt;while(tt--)solve();return 0;
}
