Codeforces Round #697 (Div. 3)题解
A - Odd Divisor
题意：给定一个n(n>1)，询问是否含奇数因数。
思路：当n的二进制数中只有一个1时，不存在奇数因数。
#include <queue>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include<map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAX_N=10000000+5;
const int maxn = 2 * 1e6 + 9;
const int INF = 0x3f3f3f3f;
map<int,int>mp;
vector<int>prime;
int vis[MAX_N];
int main()
{
int t;
cin>>t;
while(t--)
{
ll n;
scanf("%lld",&n);
int sum=0;
while(n)
{
if(n&1)
sum++;
n>>=1;
}
if(sum>1)
{
puts("YES");
}
else
{
puts("NO");
}
}
return 0;
}
B - New Year’s Number
题意：给定一个n，询问其是否可以由若干2021和2020组成
思路：2021看成2020+1，当n可以由2021和2020组成，n=x2020+y(2020+1)
化简得，n=(x+y)*2020+y。所以当y<=x+y时，成立。
#include <queue>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include<map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAX_N=10000000+5;
const int maxn = 2 * 1e6 + 9;
const int INF = 0x3f3f3f3f;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
scanf("%d",&n);
int x=n/2020;
int y=n-x*2020;
if(x>=y)
{
puts("YES");
}
else
{
puts("NO");
}
}
return 0;
}
C - Ball in Berland
题意：n个男生,m个女生，有k对组合，表示可以组的男女生，要求组出两对男女，询问有多少种不同方案。
思路：利用容斥，遍历k对组合，对于第i对，得出前i-1对中男生和第i个男生相同数目，女生和第i个女生相同数目，男生女生都相同数目，则贡献为i-1-(男生+女生-男生女生)。
#include <queue>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include<map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAX_N=10000000+5;
const int maxn = 2 * 1e6 + 9;
const int INF = 0x3f3f3f3f;
int vis1[MAX_N];
int vis2[MAX_N];
int a[MAX_N];
int b[MAX_N];
map<pair<int,int>,int> mp;
int main()
{
int t;
cin>>t;
while(t--)
{
mp.clear();
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=max(n,m);i++)
{
vis1[i]=0;
vis2[i]=0;
}
for(int i=1;i<=k;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=k;i++)
{
scanf("%d",&b[i]);
}
ll ans=0;
for(int i=1;i<=k;i++)
{
if(i>1)
{
ans+=1ll*((i-1)-vis1[a[i]]-vis2[b[i]]+mp[make_pair(a[i],b[i])]);
}
vis1[a[i]]++;
vis2[b[i]]++;
mp[make_pair(a[i],b[i])]++;
}
cout<<ans<<endl;
}
return 0;
}
D - Cleaning the Phone
题意：n个软件，要释放至少m的内存，给定每个软件所占内存a，和其属性b，要求释放至少m内存后，释放掉的属性之和最小，其中属性只能是1或2.
思路：把1和2分开存，排序后预处理前缀和，枚举从2中选择多少个，再通过二分计算出从1中选出多少个，答案取最小值。
#include <queue>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAX_N = 2000000 + 5;
const int maxn = 2 * 1e6 + 9;
const int INF = 0x3f3f3f3f;
int a[MAX_N];
int b[MAX_N];
ll sum1[MAX_N];
ll sum2[MAX_N];
bool cmp(int a, int b)
{
return a > b;
}
vector<int> v1;
vector<int> v2;
int main()
{
int t;
cin >> t;
while (t--)
{
v1.clear();
v2.clear();
int n, m;
scanf("%d%d", &n, &m);
sum1[0] = sum2[0] = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &b[i]);
if (b[i] == 1)
v1.push_back(a[i]);
else
v2.push_back(a[i]);
}
sort(v1.begin(), v1.end(), cmp);
sort(v2.begin(), v2.end(), cmp);
if ((int)v1.size() == 0)
{
sum2[0] = v2[0];
for (int i = 1; i < v2.size(); i++)
{
sum2[i] = sum2[i - 1] + 1ll * v2[i];
}
int pos = (lower_bound(sum2, sum2 + (int)v2.size(), m) - sum2);
if (pos < (int)v2.size())
cout << 2 * (pos + 1) << endl;
else
puts("-1");
continue;
}
sum1[0] = v1[0];
if (v2.size())
sum2[0] = v2[0];
for (int i = 1; i < v1.size(); i++)
{
sum1[i] = sum1[i - 1] + 1ll * v1[i];
}
for (int i = 1; i < v2.size(); i++)
{
sum2[i] = sum2[i - 1] + 1ll * v2[i];
}
int ans = INF;
for (int i = 1; i <= v2.size(); i++)
{
ll x = 1ll * m - sum2[i - 1];
if (x <= 0)
{
ans = min(ans, 2 * i);
continue;
}
//cout<<x<<endl;
int pos = (lower_bound(sum1, sum1 + (int)v1.size(), x) - sum1);
if (pos >= (int)v1.size())
{
continue;
}
// cout<<i<<' '<<pos<<endl;
ans = min(ans, (2 * i + pos + 1));
}
int pos = (lower_bound(sum1, sum1 + (int)v1.size(), m) - sum1);
//cout<<pos<<endl;
if (pos < (int)v1.size())
ans = min(ans, (pos + 1));
if (ans == INF)
puts("-1");
else
cout << ans << endl;
}
return 0;
}
E - Advertising Agency
题意：给定长度为n的序列a，求从里面选出k个使其和最大的方案数。
思路：从大到小排序，发现方案数一定与a[k]有关，假设与a[k]相同的有x个，需要选出的a[k]有y个，则答案为C(y,x),用个快速幂解决.
#include <queue>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include<map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAX_N=10000000+5;
const int maxn = 2 * 1e6 + 9;
const int INF = 0x3f3f3f3f;
const ll mod=1e9+7;
int a[MAX_N];
int vis[MAX_N];
bool cmp(int a,int b)
{
return a>b;
}
ll q_pow(ll a,ll b,ll m)//
{
ll r=1,base=a;
while(b!=0){
if(b%2)
r*=base;
r%=m;
base*=base;
base%=m;
b/=2;
}
return r;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
vis[i]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
vis[a[i]]++;
}
sort(a+1,a+1+n,cmp);
ll ans=1;
int num=1;
for(int i=m-1;i>=1;i--)
{
if(a[i]!=a[i+1])
{
break;
}
num++;
}
int x=vis[a[m]];
ll zi=1;
ll mu=1;
//cout<<x<<' '<<num<<endl;
for(int i=0;i<num;i++)
{
zi*=1ll*(x-i);
zi%=mod;
}
for(int i=1;i<=num;i++)
{
mu*=1ll*i;
mu%=mod;
}
cout<<zi*q_pow(mu,mod-2,mod)%mod<<endl;
}
return 0;
}
F - Unusual Matrix
题意：给定01矩阵a和b，定义每次操作讲a的任意一行或列01翻转，询问若干次操作后，a是否能变成b。
思路：首先，对于每一列或每一行，其翻转的次数只有0或1，因为2和0是一样的，那么对于任意一个元素，如果a和b是一样的，那么要么对应的行和列都不翻转，要么都翻转，如果不一样，就只翻转一个。所以，假设我们a[1][1]的翻转已经确定，那么对于第一行的其它元素在操作时就不能对行翻转，对第一列的其它元素在操作时就不能对列翻转，因为那样会影响a[1][1]，所以只需枚举a[1][1]的两种翻转操作，第一行和第一列其它元素的操作就是固定的，在这些都规定好后，剩余的元素则不能进行操作，所以只需检查这些元素与操作是否相符即可。
#include <queue>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAX_N = 1000 + 5;
const int maxn = 2 * 1e6 + 9;
const int INF = 0x3f3f3f3f;
char a[MAX_N][MAX_N];
char b[MAX_N][MAX_N];
int vis1[MAX_N];
int vis2[MAX_N];
int n;
int main()
{
int t;
cin >> t;
while (t--)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
vis1[i] = 0;
vis2[i] = 0;
scanf("%s", a[i] + 1);
}
for (int i = 1; i <= n; i++)
{
scanf("%s", b[i] + 1);
}
int flag=1;
if(a[1][1]==b[1][1])
{
for(int i=2;i<=n;i++)
{
if(a[i][1]!=b[i][1])
{
vis1[i]=1;
}
}
for(int i=2;i<=n;i++)
{
if(a[1][i]!=b[1][i])
{
vis2[i]=1;
}
}
for(int i=2;i<=n;i++)
{
for(int j=2;j<=n;j++)
{
if(a[i][j]==b[i][j]&&vis1[i]!=vis2[j])
{
//cout<<i<<' '<<j<<' '<<vis1[i]<<' '<<vis2[j];
flag=0;
break;
}
if(a[i][j]!=b[i][j]&&vis1[i]==vis2[j])
{
//cout<<i<<' '<<j<<' '<<vis1[i]<<' '<<vis2[j];
flag=0;
break;
}
}
}
if(flag)
{
puts("YES");
continue;
}
vis1[1]=1;
vis2[1]=1;
for(int i=2;i<=n;i++)
{
if(a[i][1]==b[i][1])
{
vis1[i]=1;
}
}
for(int i=2;i<=n;i++)
{
if(a[1][i]==b[1][i])
{
vis2[i]=1;
}
}
for(int i=2;i<=n;i++)
{
for(int j=2;j<=n;j++)
{
if(a[i][j]==b[i][j]&&vis1[i]!=vis2[j])
{
//cout<<i<<' '<<j<<' '<<vis1[i]<<' '<<vis2[j];
flag=0;
break;
}
if(a[i][j]!=b[i][j]&&vis1[i]==vis2[j])
{
//cout<<i<<' '<<j<<' '<<vis1[i]<<' '<<vis2[j];
flag=0;
break;
}
}
}
if(flag)
{
puts("YES");
continue;
}
}
else
{
vis1[1]=vis2[1]=0;
vis1[1]=1;
for(int i=2;i<=n;i++)
{
if(a[i][1]!=b[i][1])
{
vis1[i]=1;
}
}
for(int i=2;i<=n;i++)
{
if(a[1][i]==b[1][i])
{
vis2[i]=1;
}
}
for(int i=2;i<=n;i++)
{
for(int j=2;j<=n;j++)
{
if(a[i][j]==b[i][j]&&vis1[i]!=vis2[j])
{
//cout<<i<<' '<<j<<' '<<vis1[i]<<' '<<vis2[j];
flag=0;
break;
}
if(a[i][j]!=b[i][j]&&vis1[i]==vis2[j])
{
//cout<<i<<' '<<j<<' '<<vis1[i]<<' '<<vis2[j];
flag=0;
break;
}
}
}
if(flag)
{
puts("YES");
continue;
}
vis1[1]=0;
vis2[1]=1;
for(int i=2;i<=n;i++)
{
if(a[i][1]==b[i][1])
{
vis1[i]=1;
}
}
for(int i=2;i<=n;i++)
{
if(a[1][i]!=b[1][i])
{
vis2[i]=1;
}
}
for(int i=2;i<=n;i++)
{
for(int j=2;j<=n;j++)
{
if(a[i][j]==b[i][j]&&vis1[i]!=vis2[j])
{
//cout<<i<<' '<<j<<' '<<vis1[i]<<' '<<vis2[j];
flag=0;
break;
}
if(a[i][j]!=b[i][j]&&vis1[i]==vis2[j])
{
//cout<<i<<' '<<j<<' '<<vis1[i]<<' '<<vis2[j];
flag=0;
break;
}
}
}
if(flag)
{
puts("YES");
continue;
}
}
puts("NO");
}
return 0;
}
海康威视工作强度 84人发布
投递快手等公司10个岗位 >