layout: post
title: Codeforces Round 251 (Div. 2)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
- 模拟
A.[Devu, the Singer and Churu, the Joker (签到)
题意
主角有N首不同时长的歌曲，每首歌曲之间需要相隔10分钟,并且歌曲必须连续，再主角唱完歌的时候可以表演每次五分钟的其他节目。问最多表演多少场其他节目， 不能完成演唱输出-1
思路
直接先按照题意安排歌曲，然后再在空缺的时间中填充魔术。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int a[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n,d;
cin>>n>>d;
for(int i=1;i<=n;i++)cin>>a[i];
if((n-1)*10>=d){
cout<<-1<<endl;return 0;
}
int cnt=0;
int ex=d-(n-1)*10;
int num=0;
for(int i=1;i<=n;i++){
if(i!=1)num+=10,cnt+=2;
num+=a[i];
}
if(num>d){
cout<<-1<<endl;return 0;
}
else{
cnt+=(d-num)/5;
cout<<cnt<<endl;
}
return 0;
}
B.Devu, the Dumb Guy (贪心)
题意
n个课程，每个课程都有ci个章节，完成一章需要X分钟，但是如果完成一个课程后面的课程每章都会减少一分钟（最少不低于1分钟），问少需要几分完成所有课程。
题解
直接排序 然后根据题意模拟贪心。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int a[maxn];
int cnt[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n,x;
cin>>n>>x;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
ll sum=0;
for(int i=1;i<=n;i++){
sum+=a[i]*max(1LL*(x-i+1LL),1LL);
}
cout<<sum<<endl;
return 0;
}
C.Devu and Partitioning of the Array （大模拟）
题意
给出N个数，让你分成k块，其中p块的和为偶数
思路
只要知道偶数+偶数=偶数，奇数+奇数=偶数 奇数+偶数=奇数的特性就可以做了，
不过情况比较多需要讨论
先把奇数偶数分类，然后如果奇数比较多，就判断奇数多出来的那些可不可以组成偶数（也就是多出来的是不是偶数个）
注意讨论奇数和偶数分别为0的情况。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll a[maxn];
stack<int>odd,even,exeven,exodd;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n,k,p;
cin>>n>>k>>p;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]&1)odd.push(a[i]);
else even.push(a[i]);
}
int oddnum=odd.size();
int odd_need_num=k-p;
int even_need_num=p;
if(odd_need_num>oddnum){
cout<<"NO"<<endl;return 0;
}
else{
if((oddnum-odd_need_num)%2!=0){
cout<<"NO"<<endl;return 0;
}
else{
int ex=oddnum-odd_need_num;
for(int i=1;p!=0&&i<=ex;i++){
exeven.push(odd.top());
odd.pop();
}
if(!p){
while(!even.empty()){
exodd.push(even.top());
even.pop();
}
}
if(ex/2+even.size()<even_need_num){
cout<<"NO"<<endl;return 0;
}
cout<<"YES"<<endl;
for(int i=1;i<odd_need_num;i++){
cout<<1<<" "<<odd.top()<<endl;
odd.pop();
}
if(!odd.empty()){
cout<<odd.size()+exodd.size()<<" ";
while(!odd.empty()){
cout<<odd.top()<<" ";
odd.pop();
}
while(!exodd.empty()){
cout<<exodd.top()<<" ";
exodd.pop();
}
cout<<endl;
}
for(int i=1;i<p;i++){
if(!even.empty()){
cout<<1<<" "<<even.top()<<endl;
even.pop();
}
else{
cout<<2<<" "<<exeven.top();
exeven.pop();
cout<<" "<<exeven.top()<<endl;
exeven.pop();
}
}
if(even.size()+exeven.size()==0)return 0;
cout<<even.size()+exeven.size()<<" ";
while(!even.empty()||!exeven.empty()){
if(!even.empty()){
cout<<even.top()<<" ";
even.pop();
}
else{
cout<<exeven.top()<<" ";
exeven.pop();
cout<<exeven.top()<<" ";
exeven.pop();
}
}
}
}
return 0;
}
D.Devu and his Brother (三分)
题意
两个数组A,B.想要数组A的最小值不比数组B的最大值小,一次操作可以让某个数字的一个元素增大或者减小1 问达成目的最少需要几次操作。
思路
题目的意思就是找出一个值X使得A中的所有元素都大于等于X，B中的元素小于等于X。
所以答案就是
[ans=(sum_{i=1}^{n}x-a[i])+(sum_{i=1}^{m}b[i]-x)\a[i]<x,b[i]>x
]
假设这个x是最优的解，那么X增大或者减小都会使得ans变大，所以题目就是一个凹函数求最小值了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll a[maxn];
ll b[maxn];
int n,m;
ll check(ll x){
ll ans=0;
for(int i=1;i<=n;i++)if(a[i]<x)ans+=x-a[i];
for(int i=1;i<=m;i++)if(b[i]>x)ans+=b[i]-x;
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>n>>m;
for(int i = 1; i <= n; i++){
cin>>a[i];
}
for(int i = 1; i <= m; i++){
cin>>b[i];
}
ll l=0,r=1e11,ans=inf;
for(int i=1;i<=100;i++){
ll m1=(l+r)/2;
ll m2=(m1+r)/2;
ll ans1=check(m1),ans2=check(m2);
if(ans1>ans2){
l=m1;
ans=min(ans,ans2);
}
else{
r=m2;
ans=min(ans,ans1);
}
}
cout<<ans<<endl;
return 0;
}
E.Devu and Birthday Celebration （莫比乌斯反演，素因子分解,计数原理,组合数学）
题意
Q次询问 给出一个数N 让你分成F份，使得这F份的和为N并且这F份数 最大公约数为1，问有多少种分法。Q,N,F范围都是1-1e5。
思路
如果不考虑公约数 那么答案就是Cn-1,f-1。
设F(n,k)为n个数分成F份并且最大公约数为1的答案数
所以
[F(n,k)=C_{n-1}^{k-1}-sum_{g>1}^{n}F(n/g,k)
]
然后直接递归写就行。
[F(n)=n分解为k份最大公约数为任意的值
]
[G(n)=n分解为k份且最大公约数为n的值
]
可知
[F(n,k)=C_{n-1}^{k-1}
]
同时
[F(n)=sum_{d|n}G(d)
]
于是根据莫比乌斯反演因数反演
[G(n)=sum_{d|n}u(d)F(n/d)
]
/*
莫比乌斯反演
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll inv[maxn],p[maxn];
ll ksm(ll x,ll n){
ll ans=1;
while(n){
if(n&1)ans=(ans*x)%mod;
x=(x*x)%mod;
n>>=1;
}
return ans;
}
int prime[maxn];
bool notprime[maxn];
int mu[maxn];
void init(int n){
mu[1]=1;
int tot=0;
for(int i=2;i<=n;i++){
if(!notprime[i])prime[++tot]=i,mu[i]=-1;
for(int j=1;j<=tot;j++){
if(i*prime[j]>n)break;
notprime[i*prime[j]]=true;
if(i%prime[j]==0){
mu[i*prime[j]]=0;
break;
}
else mu[i*prime[j]]=-mu[i];
}
}
inv[0]=p[0]=1;
for(int i=1;i<=n;i++)
p[i]=p[i-1]*i%mod,inv[i]=ksm(p[i],mod-2);
}
ll cal(int n,int m){
if(n<m)return 0LL;
return p[n]*inv[n-m]%mod*inv[m]%mod;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
init(1e5);
int q;
cin>>q;
while(q--){
ll n,f;
cin>>n>>f;
ll ans=0;
for(int i=1;i*i<=n;i++){
if(n%i==0){
ans=(ans+mu[i]*cal(n/i-1,f-1)+mod)%mod;
if(n/i!=i)ans=(ans+mu[n/i]*cal(i-1,f-1)+mod)%mod;
}
}
cout<<ans<<endl;
}
return 0;
}
/*
枚举GCD值
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll inv[maxn],p[maxn];
ll ksm(ll x,ll n){
ll ans=1;
while(n){
if(n&1)ans=(ans*x)%mod;
x=(x*x)%mod;
n>>=1;
}
return ans;
}
vector<int>G[maxn];
void init(int n){
inv[0]=p[0]=1;
for(int i=1;i<=n;i++)
p[i]=p[i-1]*i%mod,inv[i]=ksm(p[i],mod-2);
for(int i=2;i<=n;i++){
for(int j=i;j<=n;j+=i){
G[j].push_back(i);
}
}
}
ll cal(int n,int m){
if(n<m)return 0LL;
return p[n]*inv[n-m]%mod*inv[m]%mod;
}
ll vis[maxn];
int who[maxn];
ll F(int n,int k,int q){
if(who[n]==q)return vis[n];
ll ans=cal(n-1,k-1);
for(int i=0;i<G[n].size();i++){
ans=(ans-F(n/G[n][i],k,q)+mod)%mod;
}
who[n]=q;
vis[n]=ans;
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
init(1e5);
int q;
cin>>q;
while(q){
ll n,f;
cin>>n>>f;
cout<<F(n,f,q)<<endl;
q--;
}
return 0;
}
/*
枚举GCD倍数
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll inv[maxn],p[maxn];
ll ksm(ll x,ll n){
ll ans=1;
while(n){
if(n&1)ans=(ans*x)%mod;
x=(x*x)%mod;
n>>=1;
}
return ans;
}
void init(int n){
inv[0]=p[0]=1;
for(int i=1;i<=n;i++)
p[i]=p[i-1]*i%mod,inv[i]=ksm(p[i],mod-2);
}
ll cal(int n,int m){
if(n<m)return 0LL;
return p[n]*inv[n-m]%mod*inv[m]%mod;
}
vector<int> get(int n){
vector<int>G;
for(int i=2;i*i<=n;i++){
if(n%i==0){
G.push_back(i);
while(n%i==0)n/=i;
}
}
if(n!=1)G.push_back(n);
return G;
}
ll F(int n,int k){
vector<int>G=get(n);
ll ans=0,num=1<<G.size();
for(int i=0;i<num;i++){
ll tmp=1,sign=1;
for(int j=0;j<G.size();j++){
if(i&(1<<j)){
sign*=-1;
tmp*=G[j];
}
}
ans=(ans+sign*cal(n/tmp-1,k-1)%mod+mod)%mod;
}
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
init(1e5);
int q;
cin>>q;
while(q--){
ll n,f;
cin>>n>>f;
cout<<F(n,f)<<endl;
}
return 0;
}