A Odd Divisor
思路：当前数为偶数则不断除以2，直到遇到奇数退出打印YES，一直未发现奇数因子则打印NO
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; int main() { int t; cin>>t; while(t--){ ll n; cin>>n; bool flag=false; for(ll i=n;i>1;){ if(i&1){ flag=true; break; }else i/=2; } if(flag)puts("YES"); else puts("NO"); } return 0; }
B New Year's Number
思路：直接计算n中2020的个数，剩下的数看个数是否不大于2020的个数，是则说明这些数可以用来补成2021则可符合题目条件，否则不行
1 #include<iostream> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 6 using namespace std; 7 8 typedef long long ll; 9 10 int main() 11 { 12 int t; 13 cin>>t; 14 while(t--){ 15 int n; 16 cin>>n; 17 int num=n/2020; 18 int tmp=n-n/2020*2020; 19 if(tmp<=num)puts("YES"); 20 else puts("NO"); 21 } 22 return 0; 23 }
C Ball in Berland
思路：从第一对开始枚举，对每一对都有除去当前对以外的对数剩下k-1对以后，再减去对应二部图
中除去当前两个顶点以外的对数（不符合同时出场的对数）即当前对可以出场的数量即k-1-（mpa[nd[i].a]-1）
-(mpb[nd[i].b]-1)//除去本身顶点
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #include<string> 6 #include<algorithm> 7 #include<map> 8 9 using namespace std; 10 11 typedef long long ll; 12 13 const int N=2e5+10; 14 15 struct node{ 16 ll a,b; 17 }; 18 19 int main() 20 { 21 int t; 22 cin>>t; 23 while(t--){ 24 node nd[N]; 25 int x,y,n; 26 cin>>x>>y>>n; 27 map<ll,int> mpa,mpb; 28 for(int i=1;i<=n;i++)cin>>nd[i].a,mpa[nd[i].a]++; 29 for(int i=1;i<=n;i++)cin>>nd[i].b,mpb[nd[i].b]++; 30 ll res=0,k=n; 31 for(int i=1;i<=n;i++){ 32 mpa[nd[i].a]--,mpb[nd[i].b]--; 33 ll tmp=k-1-mpa[nd[i].a]-mpb[nd[i].b]; 34 if(tmp<=0)tmp=0; 35 res+=tmp; 36 k--; 37 } 38 cout<<res<<endl; 39 } 40 return 0; 41 }
D Cleaning the Phone
题意：给出n个数，对应的代价和内存也给出，代价只能是1和2，求能够使得内存释放不小于m的最小总代价
思路：对1和2对应的内存分别用数组a和b存起来从大到小排序后求前缀和，因为m肯定是由x个代价为1对应的内存和y个代价为2对应的内存的总和，因此枚举1的数量，并
通过二分求得此时要达到m所需要的2的数量，for一遍求最小代价，O(nlogn)，但是要注意，会爆int，要开longlong
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cmath> 6 #define INF 0x3f3f3f3f 7 8 using namespace std; 9 10 typedef long long ll; 11 12 const int N=2e5+10; 13 ll a[N],b[N]; 14 15 struct node{ 16 ll a,b; 17 }; 18 19 bool cmp(ll a,ll b) 20 { 21 return a>b; 22 } 23 24 int main() 25 { 26 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 27 int t; 28 cin>>t; 29 while(t--){ 30 ll n,m; 31 cin>>n>>m; 32 node nd[N]; 33 memset(a,0,sizeof(a)); 34 memset(b,0,sizeof(b)); 35 for(int i=1;i<=n;i++)cin>>nd[i].a; 36 for(int i=1;i<=n;i++)cin>>nd[i].b; 37 int p1=1,p2=1; 38 for(int i=1;i<=n;i++){ 39 if(nd[i].b==1)a[p1++]=nd[i].a; 40 else b[p2++]=nd[i].a; 41 } 42 sort(a+1,a+p1,cmp);sort(b+1,b+p2,cmp); 43 for(int i=1;i<p1;i++)a[i]+=a[i-1]; 44 for(int i=1;i<p2;i++)b[i]+=b[i-1]; 45 if(a[p1-1]+b[p2-1]<m){ 46 cout<<"-1"<<endl; 47 continue; 48 } 49 //枚举1和2的数量c 50 ll cnt=INF; 51 for(int i=0;i<p1;i++){ 52 //i个1需要的对应的多少个2需要搜索 大到小排序二分查找 53 int pos=lower_bound(b,b+p2,m-a[i])-b;//从b到b+p2使得下标从0开始可以处理好m-a[i]<=0时的情况 54 //cout<<pos<<' '<<b[pos]<<' '<<m-a[i]<<' '<<endl; 55 if(pos<p2&&a[i]+b[pos]>=m)cnt=min(cnt,i*1ll+pos*2); 56 } 57 if(cnt==INF)cnt=-1; 58 cout<<cnt<<endl; 59 } 60 return 0; 61 }
E Advertising Agency
题意：求输出中使得达到最大的k个数的组合方式
思路：数组排序，对于第k大的数先固定比第k个大的数更大的数的排列，对于和第k大的数一样大的数，按排列组合输出第k大的数的数里边选择比第k大数更大的数剩下的数数量，
具体见代码
1 #include<iostream> 2 #include<cstring> 3 #include<cmath> 4 #include<map> 5 #include<algorithm> 6 7 using namespace std; 8 9 typedef long long ll; 10 const ll mod=1e9+7; 11 const int N=1e3+10; 12 int a[N]; 13 14 ll quick_pow(ll x,ll y) 15 { 16 ll ans=1; 17 while(y){ 18 if(y&1)ans=(ans*x)%mod; 19 x=(x*x)%mod; 20 y>>=1; 21 } 22 return ans%mod; 23 } 24 25 ll C(ll n,ll k) 26 { 27 ll res=1; 28 for(ll i=1,j=n;i<=k;i++,j--){ 29 res=(res*j)%mod; 30 res=(res*quick_pow(i,mod-2))%mod;//注意一下这里不能直接res/i，不然结果不准确，应用一下费马小定理 31 } 32 return res%mod; 33 } 34 35 int main() 36 { 37 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 38 int t; 39 cin>>t; 40 while(t--){ 41 int n,k; 42 cin>>n>>k; 43 memset(a,0,sizeof(a)); 44 map<int,int> mp; 45 for(int i=0;i<n;i++){ 46 cin>>a[i]; 47 ++mp[a[i]]; 48 } 49 sort(a,a+n); 50 int m=k; 51 for(int i=n-1;i>=n-k;i--){ 52 if(a[i]!=a[n-k])m--; 53 } 54 //cout<<m<<' '<<mp[a[n-k]]<<endl; 55 ll ans=C(mp[a[n-k]],m)%mod; 56 cout<<ans<<endl; 57 } 58 return 0; 59 }
F Unusual Matrix
思路：直接模拟一下，对第一行a和b如果有不同的元素就翻转相应的列，对接下来的每一行第一个元素如果a和b不相同就翻转相应的行，这样处理下来判断一下a和b是否相等，
不相等打印NO，否则YES
1 #include<iostream> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 6 using namespace std; 7 8 const int N=1e3+10; 9 char a[N][N],b[N][N]; 10 int n; 11 12 void Flip1(char s[N][N],int j) 13 { 14 for(int i=0;i<n;i++)s[i][j]=s[i][j]=='0'?'1':'0'; 15 } 16 17 void Flip2(char s[N][N],int i) 18 { 19 for(int j=0;j<n;j++)s[i][j]=s[i][j]=='0'?'1':'0'; 20 } 21 22 bool is_equal() 23 { 24 for(int i=0;i<n;i++){ 25 for(int j=0;j<n;j++){ 26 if(a[i][j]!=b[i][j])return false; 27 } 28 } 29 return true; 30 } 31 32 void print(char s[N][N]) 33 { 34 for(int i=0;i<n;i++){ 35 for(int j=0;j<n;j++)cout<<s[i][j]; 36 cout<<endl; 37 } 38 cout<<endl; 39 } 40 41 int main() 42 { 43 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 44 int t; 45 cin>>t; 46 while(t--){ 47 cin>>n; 48 for(int i=0;i<n;i++)cin>>a[i]; 49 for(int i=0;i<n;i++)cin>>b[i]; 50 for(int j=0;j<n;j++){ 51 if(a[0][j]!=b[0][j])Flip1(a,j); 52 } 53 for(int i=1;i<n;i++){ 54 if(a[i][0]!=b[i][0])Flip2(a,i); 55 } 56 if(is_equal())puts("YES"); 57 else puts("NO"); 58 } 59 return 0; 60 }
G Strange Beauty
思路：素数筛思想+DP
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<unordered_map> 6 #include<cstdio> 7 #include<set> 8 #include<vector> 9 10 using namespace std; 11 12 const int N=2e5+10; 13 int a[N],dp[N]; 14 15 int main() 16 { 17 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 18 int t; 19 cin>>t; 20 while(t--){ 21 int n,x; 22 cin>>n; 23 memset(a,0,sizeof(a)); 24 memset(dp,0,sizeof(dp)); 25 for(int i=0;i<n;i++){ 26 cin>>x; 27 a[x]++; 28 } 29 int ans=0; 30 for(int i=1;i<=N;i++){ 31 if(!a[i])continue; 32 dp[i]+=a[i]; 33 for(int j=i+i;j<=N;j+=i)dp[j]=max(dp[j],dp[i]); 34 //cout<<i<<' '<<dp[i]<<endl; 35 ans=max(ans,dp[i]); 36 } 37 cout<<n-ans<<endl; 38 } 39 return 0; 40 }