A. Odd Divisor
思路
读题可知，只有这个数字可用$2^x$表示时不存在奇数除数。
这题比赛的时候没怎么想就开始写了，赛后才想到可以用lowbit判断是否是形如$2^x$的数，如果lowbit(x)==x，则这个数字可以用$2^x$表示。
我的方法是预处理出$2^x(x\in[0,60])$这样的一个数组，之后遇到一个数字，使用lowerbound进行二分，找到对应的位置之后，比较两个数字是否相同即可。
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
#define INF 0x3f3f3f3f
ll p[114514];
void init(){
p[0] = 1;
rep(i,1,60){
p[i] = p[i-1]*2;
}
}
void solve(){
ll n;
cin>>n;
if(*lower_bound(p+1,p+1+60,n)==n||n==1){
cout<<"NO"<<endl;
}
else cout<<"YES"<<endl;
}
int main(){
init();
int z;
cin>>z;
while(z--) solve();
}B. New Year’s Number
思路
已知2021比2020多1，如果一共有n个数供我们选择求和，全选2020会比全选2021少n。
因此，我们如果要判断一个数能不能被2020和2021表示，直接先把这个数整除2020得到t,知道这个数最多可以被t个数求和来表示。再把这个数对2020取余得到y，得知我们至少需要把y个2020改成2021来弥补这些差距。
之后只要检查t是否比y小，即是否有至少y个2020可以被改成2021的。
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
#define INF 0x3f3f3f3f
int n;
void solve(){
cin>>n;
int t = n/2020;
int y = n%2020;
//cout<<t<<' '<<y<<endl;
if(y<=t) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main(){
int z;
cin>>z;
while(z--) solve();
}C. Ball in Berland
思路
首先从最暴力的方法想，我们枚举第一个组合$(x,y)$,那么组合$(x,i)，i\in[1,a]$是不能被选择的，组合$(x,j)，j\in[1,b]$也是不能被选择的。
我们如果把$(x,y)$放在坐标轴上看，可以发现上面不能被选择的那些组合，就是x行和j列的这些数字。
如这张图中，我们选中了(4,6)则直接从总数k上减去第四行的总和以及第六列的总和，又因为(4,6)被减去了两次，所以要+1.
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
#define INF 0x3f3f3f3f
int a,b,k;
const int MAXN = 114514*2;
int aa[MAXN],bb[MAXN];//读入a,b
int cnta[MAXN],cntb[MAXN];//记录行列的和
ll res;
void solve(){
res = 0;
cin>>a>>b>>k;
rep(i,1,a) cnta[i] = 0;//计数的清空
rep(i,1,b) cntb[i] = 0;
rep(i,1,k){
cin>>aa[i];
cnta[aa[i]]++;//aa[i]行的总和增加
}
rep(i,1,k){
cin>>bb[i];
cntb[bb[i]]++;//bb[i]列的总和增加
}
rep(i,1,k){
res += k-cnta[aa[i]]-cntb[bb[i]]+1;
}
cout<<res/2<<endl;//因为两个组合前后顺序无关,所以要除2
}
int main(){
int z;
cin>>z;
while(z--) solve();
}D. Cleaning the Phone
思路
先按照”性价比“(即 $\frac{a[i]}{b[i]}$ )对所有app进行排序.
从开头往后遍历数组，优先取性价比高的放入要删掉的集合中。
我们维护pre1(上一个取得消耗为1的app)和pre2(上一个取得消耗为1的app)有两种情况需要讨论。
- 如果此时删掉的集合的内存总和$nowm<m$,且$b[i]=2$,把当前app加进来能满足$nowm\geq m$，这时候pre1可能是不必要的，我们要讨论pre1移除后是否能满足条件。
- 如果此时删掉的集合内存总和$nowm\geq m$,且$b[i]=1$,这时候pre2可能是不必要的，即用当前第i个app代替之前的pre2可能仍旧能满足$nowm\geq m$的条件。
我们只需要贪心地先把nowm补足，并且用上面两条判断特殊情况即可。
另一种方法是，也可以用两个数组分别存放消耗为1和消耗为2的app，用两个指针表示每边的进度。
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
#define INF 0x3f3f3f3f
typedef pair<int,int> pii;//用pair来存app的信息,first存a,second存b
#define ft first
#define sd second
const int MAXN = 114514*2;
pii a[MAXN];
bool cmp(pii a,pii b){//自定义地比较函数，性价比高地排在前面
if((double)a.ft/a.sd>(double)b.ft/b.sd) return 1;
else if((double)a.ft/a.sd==(double)b.ft/b.sd)
return a.sd<b.sd;
return 0;
}
int n,m;
void solve(){
cin>>n>>m;
rep(i,1,n)
cin>>a[i].ft;
rep(i,1,n)
cin>>a[i].sd;
sort(a+1,a+1+n,cmp);
int nowm = 0;
int cost = 0;
int pre1=0,pre2=0;//上次选择的
rep(i,1,n){
if(nowm>=m&&pre2&&nowm-a[pre2].ft+a[i].ft>=m&&a[i].sd==1){
cost--;
nowm=INF;
break;//处理完这种特殊情况后可以直接退出了,因为消耗不可能更小了
}//第二种特殊情况
else if(nowm<m&&pre1&&nowm-a[pre1].ft+a[i].ft>=m){
cost++;
nowm=INF;
break;
}//第一种特殊情况
else if(nowm<m){
if(a[i].sd==1)pre1 = i;
else if(a[i].sd==2) pre2 = i;
cost+=a[i].sd;
nowm+=a[i].ft;
}
}
if(nowm<m) cout<<-1<<endl;
else cout<<cost<<endl;
}
int main(){
int z;
cin>>z;
while(z--) solve();
}E. Advertising Agency
思路
这题其实比较简单。
举一组例子来说明：假如$k=7,n=12,$主播数组有$[5,5,4,4,4,3,3,3,3,3,2,1]$
如果要使粉丝数总和最大，选出7人，那么5和4粉丝的必须全部选择，不然不可能达到最大，且1和2的也必不可能取。只需要讨论3有几种情况即可。
选完5和4后还有$7-2-3=2$个名额，一共有5个3粉丝的主播，所以方数为$C^2_5$.
所以我们用一个cnt[1001]的数组统计每个数字一共出现几次。再从1000往1循环，找到需要在哪个数字上讨论(例子中是对3进行讨论)，now来统计当前消耗了几个名额，当$k-now\leq cnt[x]$时，说明需要对当前数字进行讨论。
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
#define INF 0x3f3f3f3f
//组合数板子
const int MAXN = 3e5+5;
const int med = 1e9+7;
ll jc[MAXN];
ll qpow(ll d,ll c){//快速幂
ll res = 1;
while(c){
if(c&1) res=res*d%med;
d=d*d%med;c>>=1;
}return res;
}
inline ll niyuan(ll x){return qpow(x,med-2);}
void initjc(){//记得要初始化阶乘
jc[0] = 1;
rep(i,1,MAXN-1) jc[i] = jc[i-1]*i%med;
}
inline int C(int n,int m){//n是下面的
if(n<m) return 0;
return jc[n]*niyuan(jc[n-m])%med*niyuan(jc[m])%med;
}
//组合数板子
const int MAXX = 114514;
int a[MAXX],cnt[MAXX];
int n,k;//选k个人
void solve(){
cin>>n>>k;
rep(i,1,1000) cnt[i]=0;
int hc;
rep(i,1,n){
cin>>hc;
cnt[hc]++;//统计每个数字出现几次
}
int now=0;
repb(i,1000,1){//找到需要对哪个数字进行讨论
if(now+cnt[i]>=k){
cout<<C(cnt[i],cnt[i]+now-k)<<endl;//计算排列组合
return;
}
now+=cnt[i];
}
}
int main(){
initjc();
int z;
cin>>z;
while(z--) solve();
}F. Unusual Matrix
思路
每次操作影响了一整行/一整列，我们只需要设每行和每列操作了几次(只需要考虑是奇数次还是偶数次)，之后检验每个格子操作了几次(也只需要考虑奇数次还是偶数次即可)是否和之前所设的行和列的操作数匹配即可。
$jiou[i][j]$即$(i,j)$上的操作数即$(a[i][j])xor(b[i][j])$,从$a[i][j]$变成$b[i][j]$进行了奇数次还是偶数次操作。
$x[i]$表示第i行进行了几次操作，$y[i]$表示第y列进行了几次操作。
我们先设$x[1]=0$即第一行进行偶数次操作，那么就可以通过$x[1]$和$jiou[1][i]$推得第i列($i\in[1,n]$)的操作数.
然后通过$y[1]$和$jiou[i][1]$，可以推得第i行($i\in[2,n]$)的操作数.
当得到了每行每列的操作数后，我们通过judge()函数对每个格子进行检查，是否符合“每个格子的操作数是所处行和所处列的操作数总和”这一条件，即jiou[i][j] = b[i][j]^a[i][j];。
之后再设$x[1]=1$，重复上述操作即可。
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
#define INF 0x3f3f3f3f
const int MAXN = 1145;
int a[MAXN][MAXN],b[MAXN][MAXN];
int jiou[MAXN][MAXN];//记录每个格子上操作了几次
int x[MAXN],y[MAXN];//分别记录行和列上操作了几次
int n;
bool judge(){//判断行列操作数和格子操作数是否匹配
rep(i,1,n)
rep(j,1,n)
if(jiou[i][j]!=(x[i]^y[j])) return 0;
return 1;
}
void solve(){
cin>>n;
char hc;
rep(i,1,n){
rep(j,1,n){
cin>>hc;
a[i][j]=hc-'0';
}
}
rep(i,1,n){
rep(j,1,n){
cin>>hc;
b[i][j]=hc-'0';
jiou[i][j] = b[i][j]^a[i][j];
}
}
bool flag = 0;
x[1] = 0;//先假设第一行是偶数
rep(j,1,n) y[j] = jiou[1][j];
rep(i,2,n) x[i] = jiou[i][1]^y[1];
if(judge()) flag = 1;
x[1] = 1;//再设第一行是奇数
rep(j,1,n) y[j] = jiou[1][j]^1;
rep(i,2,n) x[i] = jiou[i][1]^y[1];
if(judge()) flag = 1;
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main(){
int z;
cin>>z;
while(z--) solve();
}G. Strange Beauty
思路
已知如果要满足$a[i]\mod a[j]=0$即aj为ai的除数，那么肯定满足$a[i]\leq a[j]$。所以如果我们对数组从小到大排序，则一定满足$a[i-1]\leq a[i]$,只需要考虑前面的数字是否是后面的数字即可。
用动态规划写，如果是最暴力的方法：
- dp[i]统计到第i个数字最多可以保留几个。
- 统计到第i个数字时，j从头1到i-1扫一遍，如果a[i]%a[j]==0,那么dp[i]就可以是dp[j]+1
- 在这些dp[j]+1中取最大值赋给dp[i]即可。
这样的复杂度是$O(n^2)$的
之后考虑怎么优化：
因为要求a[i]%a[j]==0，所以只需要考虑a[j]为a[i]因子的情况，我们枚举a[i]的因子，再检查之前是否有符合条件的a[j]即可。
- 用一个map[x]来存当前等于x的最大下标，即上一个x出现在哪一位置。
- 处理a[i]时，只需要枚举a[i]的所有因子y，检查map[y]，那么dp[i]就可以是dp[map[y]]+1
- 这些dp[map[y]]+1中取最大值赋给dp[i]即可。
因为数字x范围比较小，这个map可以用数组实现，而且会比stl的map更快,复杂度为$O(n\cdot sqrt(n))$。我图方便用stl的map写的，因此复杂度为$O(n\cdot sqrt(n)\cdot logn)$
代码
#include<iostream>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
#define INF 0x3f3f3f3f
const int MAXN = 114514*2;
int a[MAXN];
int dp[MAXN];//存最大长度
map<int,int> mp;//从数字到下标的映射
int n;
void solve(){
mp.clear();
cin>>n;
rep(i,1,n) cin>>a[i];
sort(a+1,a+1+n);//小的排在前面
dp[0]=0;
int res=0;
rep(i,1,n){
dp[i] = 0;
int sqr = sqrt(a[i]);
rep(k,1,sqr){//细节是1和a[i]也需要去map找,因为可能有重复数字
if(a[i]%k==0){
dp[i]=max(dp[i],dp[mp[k]]+1);//dp[i]要取最大值！
dp[i]=max(dp[i],dp[mp[a[i]/k]]+1);
}
}
mp[a[i]]=i;//更新map
res = max(res,dp[i]);
}
cout<<n-res<<endl;
}
int main(){
int z;
cin>>z;
while(z--) solve();
}PS
以后想尽量每次都写个题解出来，我水平比较菜，所以主要还是给零基础学弟学妹看的QAQ
