A. Odd Divisor
奇数是没有2的因子,那么我们将他反复除2即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
int w[N];
int main()
{
int T;
//T=1;
cin>>T;
while(T--)
{
ll n;
cin>>n;
if(n%2==0)
while(n%2==0) n/=2;
if(n>1) puts("YES");
else puts("NO");
}
return 0;
} New Year's Number
2020*2020大于1e6了,我们将n/2020.看需要分配多少个1即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
int w[N];
int main()
{
int T;
//T=1;
cin>>T;
while(T--)
{
ll n;
cin>>n;
int cnt=n/2020;
if(cnt>=n%2020) puts("YES");
else puts("NO");
}
return 0;
} C. Ball in Berland
考虑方案数=总的-一组相同的+两组相同的.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll a[N],b[N];
ll C(ll A,ll B)
{
return A*(A-1)/2ll;
}
map<int,int>s1;
map<int,int>s2;
map<pair<int,int>,int>s3;
int main()
{
int T;
cin>>T;
while(T--)
{
s1.clear();
s2.clear();
s3.clear();
ll A,B,n;
scanf("%lld%lld%lld",&A,&B,&n);
ll ans=C(n,2);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
for(int i=1;i<=n;i++)
{
s1[a[i]]++;s2[b[i]]++;
s3[{a[i],b[i]}]++;
}//cout<<ans<<endl;
for(auto x:s1)
if(x.second>1) ans-=C(x.second,2);
for(auto x:s2)
if(x.second>1) ans-=C(x.second,2);
for(auto x:s3)
if(x.second>1) ans+=C(x.second,2);
printf("%lld\n",ans);
}
return 0;
}
D. Cleaning the Phone
发现bi<=2.那么分bi=1和bi=2贪心讨论即可.注意别取两个bi=1的,会增加讨论难度.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e5+5;
struct node{
int a,b;
}w[N];
bool cmp(node A,node B)
{
if(A.b==B.b) return A.a>B.a;
else return A.b<B.b;
}
ll qp(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}return res;
}
ll f[N],ivf[N];
void init()
{
f[0]=1;
for(ll i=1;i<=N-5;i++) f[i]=f[i-1]*i%mod;
ivf[N-5]=qp(f[N-5],mod-2);
for(ll i=N-5;i>=1;i--) ivf[i-1]=ivf[i]*i%mod;
}
ll C(ll a,ll b)
{
return f[a]*ivf[b]%mod*ivf[a-b]%mod;
}
int main()
{
int T;
init();
cin>>T;
while(T--)
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&w[i].a);
for(int i=1;i<=n;i++) scanf("%d",&w[i].b);
sort(w+1,w+1+n,cmp);int pos=n+1;
for(int i=1;i<=n;i++)
{
if(w[i].b==2)
{
pos=i;break;
}
}bool f=false;int ans=0,num=0;
int cnt=0;int l=1,r=pos;
while(!f&&cnt<n)
{
if(pos-l>1)
{
if(r>n) num+=w[l].a,l++,cnt++,ans++;
else if(w[l].a+num>=m) num+=w[l].a,l++,cnt++,ans++;
//else if(r<=n&&w[l].a+w[l+1].a+num<m&&w[r].a+w[l].a>=m) num+=w[l].a+w[r].a,l++,r++,cnt+=2,ans+=3;
else if(w[l].a+w[l+1].a>w[r].a) num+=w[l].a,l++,cnt++,ans++;
else num+=w[r].a,r++,cnt++,ans+=2;
}
else
{
if(r>n) num+=w[l].a,l++,cnt++,ans++;
else
{
if(num+w[l].a>=m&&l!=pos) num+=w[l].a,l++,cnt++,ans++;
else num+=w[r].a,r++,cnt++,ans+=2;
}
}if(num>=m) f=true;
//cout<<num<<endl;
}
if(f) cout<<ans<<'\n';
else puts("-1");
}
return 0;
}
/*
1
4 10
5 1 3 4
1 2 1 2
*/E.Advertising Agency
大的一定要取,边界溢出的组合数取一下即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1e3+5;
ll a[N];
ll qp(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}return res;
}
ll f[N],ivf[N];
void init()
{
f[0]=1;
for(ll i=1;i<=N-5;i++) f[i]=f[i-1]*i%mod;
ivf[N-5]=qp(f[N-5],mod-2);
for(ll i=N-5;i>=1;i--) ivf[i-1]=ivf[i]*i%mod;
}
ll C(ll a,ll b)
{
return f[a]*ivf[b]%mod*ivf[a-b]%mod;
}
int main()
{
int T;
init();
cin>>T;
while(T--)
{
ll n,k;cin>>n>>k;
map<int,int>p;p.clear();
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+1+n);ll num=0;ll tot=0;
for(int i=n-k;a[i]>=a[n-k+1];i--) num++;
tot=num;//cout<<tot<<endl;
for(int i=n-k+1;a[i]<=a[n-k+1]&&i<=n;i++) tot++;
cout<<C(tot,num)<<'\n';
}
return 0;
}
F.Unusual Matrix
每个操作只会用一次.瞎搞即可.
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+50;
char s[N][N];
char p[N][N];
bool h[N];//观察这行用了没.
bool l[N];//观察这列用了没.
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int i=1;i<=n;i++) scanf("%s",p[i]+1);
for(int i=1;i<=n;i++) h[i]=l[i]=false;
bool flag=true;
for(int i=1;i<=n;i++)
{
int cnt=0;
for(int j=1;j<=n;j++)
{
if(i==1)//动列.
{
if(s[i][j]!=p[i][j]) l[j]=true;
}
else
{
if(s[i][j]!=p[i][j]&&l[j]==false) cnt++;
else if(s[i][j]==p[i][j]&&l[j]==true) cnt++;
}
}if(cnt!=0&&cnt!=n) flag=false;
}
if(flag) puts("YES");
else puts("NO");
}
return 0;
} G.Strange Beauty
集合一定是相互之间成倍数的,然后直接简单dp一下即可,可以预先处理出来因子.
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N];
vector<int>v[N];
void init()
{
for(int i=1;i<=2e5;i++)
{
for(int j=i;j<=2e5;j+=i)
{
v[j].push_back(i);
}
}
}
int main()
{
int T;scanf("%d",&T);
init();
while(T--)
{
unordered_map<int,int>p,f;
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);p[a[i]]++;
}int ans=0;sort(a+1,a+1+n);
int cnt=unique(a+1,a+1+n)-a-1;
for(int i=1;i<=cnt;i++)
{
f[a[i]]=p[a[i]];
for(int j:v[a[i]])
{
if(a[i]!=j) f[a[i]]=max(f[a[i]],f[j]+p[a[i]]);
//if(j!=a[i]/j&&j!=1) if[a[i]]=max(f[a[i]],f[a[i]/j]+p[a[i]]);
}ans=max(f[a[i]],ans);
}//for(int i=1;i<=4;i++) cout<<f[a[i]]<<endl;
printf("%d\n",n-ans);
}
return 0;
}
京公网安备 11010502036488号