A
按题意模拟。
B
贪心。题意可以转化为:选择
个小球,使得小球种类数最小是多少。
显然从小球颜色种类最多的开始选择更优。模拟即可。
signed main(void) {
n=read(),k=read(); int sum=0;
for (int i=1;i<=n;i++) a[i]=read(),sum+=a[i];
sort(a+1,a+n+1); sum%=k;
if (sum==0) {puts("0"); return 0;}
int ans=0;
for (int i=n;i>=1;i--) {
if (sum>a[i]) sum-=a[i],++ans;
else {printf("%lld",ans+1);return 0;}
}
}
C&D
对所有 模
,这样是等价的。以下的每一个数默认是模
后的结果。
对于 个编号为
的点,进行连边:编号为
的点向编号为
的点连边。每经过一条边,相当于选了一个物品。
起始点为 ,进行广度优先搜索,搜索到编号为
的点所经过的距离
即为所求。
#define fi first
#define se second
#define mk make_pair
signed main(void) {
n=read(),p=read(); queue<pair<int,int> > q;
for (int i=1;i<=n;i++) {
int x=read(); if (f[x%p]==0) q.push(mk(x%p,1)),vis[x%p]=f[x%p]=1;
}
while (!q.empty()) {
int pos=q.front().fi,num=q.front().se;
if (pos==0) {printf("%lld",num);return 0;}
for (int i=0;i<p;i++) {
if (f[i]==1&&vis[(pos+i)%p]==0) vis[(pos+i)%p]=num+1,q.push(mk((pos+i)%p,num+1));
} q.pop();
}
}
E
目标函数
,枚举
,判断是否存在整数
,满足
signed main(void) {
int n=read(),m=read(),p=read(),x=read(),ans=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) {
int nx=x-i*j;
if (nx<i+j) continue;
int k=nx/2/(i+j);
if (k<=p&&nx==2*(i+j)*k) ++ans;
}
printf("%lld",ans);
// x==i*j+2*i*k+2*j*k
}
F
如果你能在 20min 内写完线段树,那么正解做法也就没有必要去想了。
const int N=1e5+10;
int a[N],b[N];
struct tree{
int sum[N*4],tag1[N*4],tag2[N*4],sum1[N*4],sum2[N*4];
void update(int l,int r,int k) {
int mid=(l+r)>>1,lchild=(k<<1),rchild=(k<<1)+1;
sum[k]=sum[lchild]+sum[rchild];
sum1[k]=sum1[lchild]+sum1[rchild];
sum2[k]=sum2[lchild]+sum2[rchild];
}
void build(int l,int r,int k){
if (l==r){
sum[k]=a[l]&b[l];
sum1[k]=a[l],sum2[k]=b[l];
return ;
}
int mid=(l+r)>>1,lchild=(k<<1),rchild=(k<<1)+1;
build(l,mid,lchild);
build(mid+1,r,rchild);
update(l,r,k);
}
inline void pushdown(int l,int r,int k){
int mid=(l+r)>>1,lchild=(k<<1),rchild=(k<<1)+1;
if (tag1[k]) {
tag1[lchild]=tag1[rchild]=1;
sum1[lchild]=(mid-l+1),sum1[rchild]=(r-mid);
sum[lchild]=sum2[lchild],sum[rchild]=sum2[rchild];
}
if (tag2[k]) {
tag2[lchild]=tag2[rchild]=1;
sum2[lchild]=(mid-l+1),sum2[rchild]=(r-mid);
sum[lchild]=sum1[lchild],sum[rchild]=sum1[rchild];
}
}
int query(int l,int r,int k,int L,int R){
if (l>R||r<L) return 0;
if (L<=l&&R>=r) return sum[k];
int mid=(l+r)>>1,lchild=(k<<1),rchild=(k<<1)+1;
pushdown(l,r,k);
return query(l,mid,lchild,L,R)+query(mid+1,r,rchild,L,R);
}
void update1(int l,int r,int k,int L,int R){
if (l>R||r<L) return ;
if (L<=l&&R>=r){
tag1[k]=1; sum1[k]=(r-l+1); sum[k]=sum2[k];
return ;
}
int mid=(l+r)>>1,lchild=k<<1,rchild=(k<<1)+1;
pushdown(l,r,k);
update1(l,mid,lchild,L,R);
update1(mid+1,r,rchild,L,R);
update(l,r,k);
}
void update2(int l,int r,int k,int L,int R){
if (l>R||r<L) return ;
if (L<=l&&R>=r){
tag2[k]=1; sum2[k]=(r-l+1); sum[k]=sum1[k];
return ;
}
int mid=(l+r)>>1,lchild=k<<1,rchild=(k<<1)+1;
pushdown(l,r,k);
update2(l,mid,lchild,L,R);
update2(mid+1,r,rchild,L,R);
update(l,r,k);
}
}f;
signed main(void) {
int n=read();
for (int i=1;i<=n;i++) {
char ch=getchar();
if (ch=='0'||ch=='1') a[i]=ch^'0';
else --i;
}
for (int i=1;i<=n;i++) {
char ch=getchar();
if (ch=='0'||ch=='1') b[i]=ch^'0';
else --i;
}
f.build(1,n,1); int q=read();
while (q--) {
char ch; cin>>ch; int l=read(),r=read();
if (ch=='A') f.update1(1,n,1,l,r);
else f.update2(1,n,1,l,r);
printf("%lld\n",f.query(1,n,1,1,n));
}
}
但好像 也能过,数据太水了,
G
目前最优解,做法
将单增区间和单减区间单独拿出来分别分类讨论(记录单增和单减区间两端端点和第一个区间是单增的还是单减的,后续区间按照单增单减依次排列出现)
只存在这几种情况需要计数:单增、单减、先增后减、先减后增、先增后减再增
具体的讨论情况见代码(前不久出过类似的 trick 的题目)。注意细节。
#define pb push_back
signed main(void) {
int n=read(); vector<int> v; v.pb(1);
if (n==1) {puts("1"); return 0;}
for (int i=1;i<=n;i++) a[i]=read();
int fl=1; if (a[1]>a[2]) fl=0;
for (int i=2;i<n;i++) {
if (a[i]>a[i-1]&&a[i]>a[i+1]) v.pb(i);
else if (a[i]<a[i-1]&&a[i]<a[i+1]) v.pb(i);
} v.pb(n); int len=v.size(),ans=0;
//for (int i=0;i<len;i++) cout<<v[i];
for (int i=1;i<len;i++) {
int m=v[i]-v[i-1]+1; ans+=m*(m+1)/2;
} ans-=len-2;
for (int i=fl;i<len-2;i+=2) {
// v[i],v[i+1],v[i+2]
for (int j=v[i+1]-1;j>=v[i];j--) if (a[j]<a[v[i+1]+1]) ans+=(v[i+2]-v[i+1]);
}
for (int i=fl^1;i<len-2;i+=2) {
// v[i],v[i+1],v[i+2] 1,4,3
for (int j=v[i+1]+1;j<=v[i+2];j++) if (a[j]>a[v[i+1]-1]) ans+=(v[i+1]-v[i]);
}
//cout<<ans<<endl;
for (int i=fl^1;i<len-3;i+=2) {
// v[i],v[i+1],v[i+2],v[i+3] 1,7,2,10,9
if (a[v[i+1]]<a[v[i+2]+1]&&a[v[i+2]]>a[v[i+1]-1]) ans+=(v[i+1]-v[i])*(v[i+3]-v[i+2]);
}
printf("%lld",ans);
// 1,2,3,4
// case1: (a,b) -> n=b-a+1,ans+=n(n+1)/2; ans-=v.size()-2
// case2: (a,b,c) [down,up] -> ans+=(c-b)*cnt -> if a[i]<a[b+1]
// case3: (a,b,c,d) [up,down,up]
}