2022/8/6

活动地址：CSDN21天学习挑战赛

1690E - Price Maximization

先把除以k的整数部分都加上，最后再利用双指针两两配对就行

#include 
using namespace std;
#define ll long long
const ll mod=998244353;
const int N = 2e5+5;
ll t,n,k,a[200005],b[200005];
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&k);
        ll ans=0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            ans+=a[i]/k;
            b[i]=a[i]%k;
        }
        sort(b+1,b+n+1);
        ll l=1,r=n;
        while(l
            if(b[l]+b[r]>=k){ans++;l++;r--;}
            else l++;
        }
        printf("%lld\n",ans);
    }
    system("pause");
    return 0;
}

J-Number Game_"蔚来杯"2022牛客暑期多校训练营6 (nowcoder.com)

到最后才真正的理解了这道题，推出了式子，但最后化简的时候把第一个式子给化错了，，，

可以发现B是只有两种取值情况的：B，A-B，然后操作的过程可以看成从这两种情况中选一个减去C这个整体的值，注意这时候的C可能不是原来的C了，可能是多次操作后的C，我们可以发现选了B这个值之后再去选B是没有意义的，他会和上一次抵消掉，也就是说选B的值一定是B，A-B这样交错着来，那我们就可以总结出情况来了：

B先开头，A-B结尾一共操作了2n次：n（A-B）-nB+C=x

B先开头，B结尾，一共操作了2n+1次：（n+1)B-n(A-B)-C=x;

A-B先开头，A-B结尾一共操作2n次：nB-n（A-B）+C=x;

A-B先开头,B结尾一共操作2n+1次：（n+1）(A-B)-nB-C=x;

如果操作了奇数次C就是负数，否则就是偶数，然后判断是否有一种成立就可以了

#include 
using namespace std;
#define ll long long
const ll mod=998244353;
const int N = 2e5+5;
ll t,a,b,c,n;
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld%lld",&a,&b,&c,&n);
        if(a-b==b){
            if(b-c==n||c==n) printf("Yes\n");
            else printf("No\n");
            continue;
        }
        
        if(a!=0&&(n-c)%a==0&&(n-c)/a>=0||(2*b!=a)&&((n+c-2*b)%(2*b-a)==0&&(n+c-2*b)/(2*b-a)>=0||(n-c)%(2*b-a)==0&&(n-c)/(2*b-a)>=0||(n+c+2*b-a)%(a-2*b)==0&&(n+c+2*b-a)/(a-2*b)>=0))
        printf("Yes\n");
        else printf("No\n");
    }
    system("pause");
    return 0;
}

B-Eezie and Pie_"蔚来杯" 树上差分

wdnmd，数组越界你告诉我答案错误，但凡你提示我一下re我都不会检查上一个小时！！！

这题就是树上差分，原来1级祖先可以直接在dfs1里直接预处理出来，，，

#include 
using namespace std;
#define ll long long
const ll mod=998244353;
const int N = 2e5+5;
ll n,u,v,d[2000006];
ll head[4000006],cnt;
struct Edge{
    ll from,to,next;
}edge[4000006];
void addedge(ll from,ll to){
    edge[++cnt].from = from;
    edge[cnt].to = to;
    edge[cnt].next = head[from];
    head[from] = cnt;
}
ll dep[2000006];
ll lg[2000006],f[2000006][30];
void dfs1(ll u,ll fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<=lg[dep[u]];i++)
        f[u][i]=f[f[u][i-1]][i-1];
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j==fa) continue;
        dfs1(j,u);
    }
}
ll kthparent(ll u,ll k){
    for(int i=lg[dep[u]];i>=0;i--)
        if(dep[u]-dep[f[u][i]]<=k) k-=dep[u]-dep[f[u][i]],u=f[u][i];
    return u;
}
ll ans[2000006];
void dfs(ll u,ll fa){
    ans[u]+=1;
    ll kth=kthparent(u,d[u]+1);
    //cout<
    if(kth) ans[kth]-=1;
    for(int i=head[u];i;i=edge[i].next){
        ll j=edge[i].to;
        if(j==fa) continue;
        dfs(j,u);
        ans[u]+=ans[j];
    }
}
int main(){
    lg[0]=-1;
    for(int i=1;i<=2000000;i++) lg[i]=lg[i>>1]+1;
    scanf("%lld",&n);
    for(int i=1;i
        ll u,v;
        scanf("%lld%lld",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    for(int i=1;i<=n;i++) scanf("%lld",&d[i]);
    dfs1(1,0);
    dfs(1,0);
    for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
    system("pause");
    return 0;
}