太菜了，太菜了。
A. Odd Divisor
题意
给出一个整数，如果这个数有除了1以外的奇数因子，输出yes，否则no。
题解
打出小于2^{14}的2的幂即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
ll nums[49]={2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312};
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
set<ll> s;
for(ll i=0;i<48;i++) {
ll j=nums[i];
s.insert(j);
}
cin>>_;
while(_--){
ll a;
cin>>a;
if(s.count(a)==1)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
B. New Year’s Number
题意
给出一个数，如果能被n个2020和m个2021相加得到，输出yes，否则no。
题解
入门dp，首先将num[2020]和num[2021]标记为1，然后遍历，如果遇到标记为1的就把num[i+2020]和num[i+2021]标记为1。注意数组开成bool型以免超内存。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
bool num[1003000];
memset(num,0,sizeof(num));
num[2020]=1;
num[2021]=1;
for(int i=2020;i<1000008;i++){
if(num[i]==1){
num[i+2020]=1;
num[i+2021]=1;
}
}
cin>>_;
while(_--){
ll a;
cin>>a;
if(num[a]==1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
C. Ball in Berland
题意
这题当时读了半个多小时才读懂，就是有n个男孩和b个女孩，同时在舞会上有k对组合方式，从中找出两对，问有多少种方式。
题解
按照男孩排序（比赛时的样例是有问题的，题中没有提示有序，但最初样例都是有序的，后来hack了一组无序样例），求出编号为i的男孩可以对应多少个女孩的后缀和、编号为i的女孩对应多少个男孩。然后遍历，当遍历到某一对的时候，总数+=男孩的后缀和-女孩对应男孩的数量+1，同时要该女孩对应男孩的数量–。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
struct node{
int a;
int b;
bool operator < (node nod){
if(a!=nod.a)
return a < nod.a;
return b < nod.b;
}
};
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
int a,b,k,s;
cin>>a>>b>>k;
vector<node> n1;
map<int,int> s1;
map<int,int> s2;
for(int i=0;i<k;i++){
cin>>s;
node nod;
nod.a=s;
n1.push_back(nod);
s1[s]++;
}
for(int i=0;i<k;i++){
cin>>s;
n1[i].b=s;
s2[s]++;
}
sort(n1.begin(),n1.end());
ll re=0;
int nums[a+1];
memset(nums,0,sizeof(nums));
int last=n1.back().a,num=0;
for(int i=n1.size()-1;i>=0;i--){
if(n1[i].a!=last){
nums[n1[i].a]=num;
last=n1[i].a;
}
num++;
}
nums[0]=num;
for(int i=0;i<k;i++){
//cout<<nums[n1[i]]<<" "<<s2[n2[i]]<<endl;
re+=nums[n1[i].a]-s2[n1[i].b]+1;
s2[n1[i].b]--;
//cout<<re<<endl;
}
cout<<re<<endl;
}
}
D. Cleaning the Phone
题意
需要清理手机中m的内存，同时重要度的和最小，求最小的重要度。
题解
开始一看像背包，不过数据范围太大，背包一定会TLE。因为只有1和2两种状态，所以是贪心。
当然我们不能直接去贪，因为要考虑不少条件，比如我的第一版代码：
（在加了不少条件之后WA在test2的第1609个样例上）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
bool cmp(int a,int b){return a>b;}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
ll n,m,s;
cin>>n>>m;
vector<int> num;
vector<int> num1;
vector<int> num2;
ll sum=0;
for(int i=0;i<n;i++){
cin>>s;
num.push_back(s);
sum+=s;
}
for(int i=0;i<n;i++){
cin>>s;
if(s==1) num1.push_back(num[i]);
else num2.push_back(num[i]);
}
if(sum<m){
cout<<-1<<endl;
continue;
}
sort(num1.begin(),num1.end(),cmp);
sort(num2.begin(),num2.end(),cmp);
ll re=0,mem=0;
int i=0,j=0;
while(mem<m){
if(j==num2.size()){
mem+=num1[i];
re+=1;
i++;
continue;
}
if(i==num1.size()){
mem+=num2[j];
re+=2;
j++;
continue;
}
if(mem+num1[i]>=m){
re+=1;
break;
}
if(mem+num2[j]>=m){
re+=2;
break;
}
if(i==num1.size()-1){
mem+=num2[j];
re+=2;
j++;
continue;
}
if(j==num2.size()-1){
mem+=num1[i];
re+=1;
i++;
continue;
}
if(num1[i]+num[i+1]<=num2[j]){
mem+=num2[j];
re+=2;
j++;
}
else{
mem+=num1[i];
re+=1;
i++;
}
//cout<<re<<"re"<<endl;
}
cout<<re<<endl;
}
}
后来参考了tourist的做法，这是一种很巧妙的贪心。
统计出重要度为2的总和，然后逐渐减少，O(n)时间复杂度下就能找到最小值。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
bool cmp(int a,int b){return a>b;}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
ll n,m,s;
cin>>n>>m;
vector<int> num;
vector<int> num1;
vector<int> num2;
ll sum=0,sum2=0;
for(int i=0;i<n;i++){
cin>>s;
num.push_back(s);
sum+=s;
}
for(int i=0;i<n;i++){
cin>>s;
if(s==1) num1.push_back(num[i]);
else {
num2.push_back(num[i]);
sum2+=num[i];
}
}
if(sum<m){
cout<<-1<<endl;
continue;
}
sort(num1.begin(),num1.end(),cmp);
sort(num2.begin(),num2.end(),cmp);
ll re=lmax,mem=0;
int j=0;
for(int i=num2.size();i>=0;i--){
while(j<num1.size()&&sum2<m){
sum2+=num1[j];
j++;
}
if(sum2>=m){
re=min(re,2*i+j);
}
if(i>0){
sum2-=num2[i-1];
}
//cout<<re<<endl;
}
cout<<re<<endl;
}
}
这题另外还有二分做法。
E. Advertising Agency
题意
每个物品都有不同的收益，求拿k件物品的最大收益的方案总数。
题解
首先按照收益为n的物品个数分组，然后贪心一波，贪到再加一组中的n个就够了的时候，求组合。
求组合的时候用卢卡斯定理模板。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
ll fpow(ll a,ll n,ll mod)
{
ll res = 1;
while(n)
{
if(n & 1)
{
res = res % mod * a % mod;
}
a = a % mod * a % mod;
n >>= 1;
}
return res;
}
ll inv(ll x, ll p)
{
return fpow(x, p - 2, p);
}
ll C(ll n, ll m, ll p)
{
if(m > n)return 0;
ll up = 1, down = 1;
for(int i = n - m + 1; i <= n; i++)up = up * i % p;
for(int i = 1; i <= m; i++)down = down * i % p;
return up * inv(down, p) % p;
}
ll Lucas(ll n, ll m, ll p)
{
if(m == 0)return 1;
return C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
int n,k,s;
cin>>n>>k;
map<ll,ll> m;
for(int i=0;i<n;i++){
cin>>s;
m[s]++;
}
ll num=0;
for(map<ll,ll>::reverse_iterator rit=m.rbegin();rit!=m.rend();rit++) {
if(k>(*rit).second) k-=(*rit).second;
else {
num=(*rit).second;
break;
}
}
cout<<Lucas(num,k,1000000007)<<endl;
}
}
