- 39

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]
}