CF-929
开学以来打得最烂的一场(⊙﹏⊙)
B
两种操作：删除一个元素、把一个元素的权值增加1。求使得序列元素和整除于3的最小操作次数。
分析
如果序列和sum模3的余数为0，答案为0，若为2，可以进行第二种操作，答案为1，但是若为1，答案就不一定为2，因为若能进行第一种操作删去一个模3为1的元素，可以使sum模3的余数为0，答案为1,否则答案才为2。
如sum(4，9)%3=1,4%3=1,删去4后sum%3=0
代码
没错，赛时这题都没做出来……
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int N=2e5+5;
int a[N];
void solve(){
int n,sum=0;cin>>n;
int f=0;
rep(i,1,n){
cin>>a[i];
sum+=a[i];
if(a[i]%3==1){
f=1;
}
}
if(sum%3==0){
cout<<"0";
}
else if(sum%3==2){
cout<<"1";
}
else{
if(f) cout<<"1";
else{
cout<<"2";
}
}
cout<<endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;cin>>t;while(t--)
solve();
return 0;
}
C
分析
数据量小，就是暴力枚举x,y，答案为满足条件的k的个数，但要注意枚举的条件，要满足整除于l
代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
int fp(int b,int p){
int res=1;
while(p){
if(p&1) res=res*b;
b=b*b;
p>>=1;
}
return res;
}
void solve(){
int a,b,l;cin>>a>>b>>l;
set<int>s;
for(int i=0;l%fp(a,i)==0;i++){
int tp=l/fp(a,i);
for(int j=0;tp%fp(b,j)==0;j++){
s.insert(tp/fp(b,j));
}
}
cout<<s.size()<<endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;cin>>t;while(t--)
solve();
return 0;
}
D
自己现在做构造题只能纯靠猜……
分析
由样例可知： 只要满足最小数只出现一次或者数列中有一个数模上最小数结果不为0，就输出yes，否则输出no
代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int N=2e5+5;
int a[N];
void solve(){
int n;cin>>n;
map<int,int>mp;
rep(i,1,n){
cin>>a[i];
mp[a[i]]++;
}
sort(a+1,a+n+1);
int f=0;
if(mp[a[1]]==1) f=1;
else{
rep(i,2,n){
if(a[i]%a[1]!=0){
f=1;
break;
}
}
}
if(f) cout<<"YES";
else cout<<"NO";
cout<<endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;cin>>t;while(t--)
solve();
return 0;
}
E
感觉甚至是这场里做法最清楚的一道题……
分析
就是找长度为r的区间[l,r]，其区间和sum满足sum个序列pu{u,u-1,……0，-1，-2……}的和最大的r的最小值，为了取到尽量多的pu的正值，可以先找到满足sum<=u的sum的最大的区间，显然可以用二分与前缀和找这个区间，也就是sum<u,l=mid，再对是否取这个二分到的区间[l,r]外的第一个元素进行判断
如 3 1 4 1 5 9
l=1,u=8时，二分到的区间为[3,1,4],已去完pu的所有正权值，此时pu和就是最大
但对于 5 10 9 6 8 3 10 7 3
l=1,u=12时，二分到的区间为[5]，还有7个pu的正权值没取到，而取下一个元素10的话就能取到所有正权值{12，11，10……，2，1}加三个负权值{-1，-2，-3}，因此取下一个元素收益最大
代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int N=2e5+5;
int p[N];
void solve(){
int n,x;cin>>n;
rep(i,1,n){
cin>>x;
p[i]=0;
p[i]=p[i-1]+x;
}
int q,ll,u;cin>>q;
while(q--){
cin>>ll>>u;
int l=ll,r=n+1,mid;
while(r-l>1){
mid=l+r>>1;
if(p[mid]-p[ll-1]<=u) l=mid;
else r=mid;
}
//判断是否取下一个元素
if(u-p[l]+p[ll-1]>=p[l+1]-p[l]-(p[l+1]-p[l])/2) l++,l=min(l,n);
cout<<l<<" ";
}
cout<<endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;cin>>t;while(t--)
solve();
return 0;
}