这次比赛估计排名和我水平差不多了，。，

%%%XRY%%%DSY

T1：

暴力出奇迹！！

code:

#include<bits/stdc++.h>
using namespace std;
int x,now;
bool check(int tot){
    int cnt1=tot%10+(tot/10)%10+(tot/100)%10;
    int cnt2=(tot/1000)%10+(tot/10000)%10+(tot/100000)%10;
    return cnt1==cnt2;
}
int main(){
    scanf("%d",&x);
    now=x+1;
    while(now<1e7){
        if(check(now)){printf("%d",now);return 0;}
        now++;
    }
    return 0;
}

T2:

比赛时第一眼就看出了是个贪心，肯定是从min走到max。。。

但是还是打了个最小生成树对拍一下。。。。

code:

#include<bits/stdc++.h>
using namespace std;
int t,n,x[110],ans;
int main(){
    scanf("%d",&t);
    while(t--){
        ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&x[i]);
        sort(x+1,x+n+1);
        for(int i=1;i<n;i++)ans+=abs(x[i+1]-x[i]);
        printf("%d\n",ans);
    }
    return 0;
}

T3:

我们记fa[i]表示A数组中有无i的倍数，fb[i]表示B数组中有无i的倍数

然后我们枚举对于每个A,B,预处理出fa，fb数组（sqrt(A)的复杂度）

接着枚举i，如果fa[i]与fb[i]同时为true时，说明i满足gcd，更新答案

最后O(n)扫一遍，求出最大的x+y即可

code：

#include<bits/stdc++.h>
using namespace std;
int n,A[500010],B[500010],fa[1000010],fb[1000010];
int ans;
void solve1(int x){
    for(int i=1;i<=sqrt(x);i++){
        int k=x/i;
        if(x%i==0){fa[i]++;fa[k]++;}
    }
    return;
}
void solve2(int x){
    for(int i=1;i<=sqrt(x);i++){
        int k=x/i;
        if(x%i==0){fb[i]++;fb[k]++;}
    }
    return;
}
int tot,ansa,ansb;
int main(){
    freopen("gcd.in","r",stdin);
    freopen("gcd.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&A[i]),solve1(A[i]);
    for(int i=1;i<=n;i++)scanf("%d",&B[i]),solve2(B[i]);
    for(int i=1000000;i>=1;i--)if(fa[i]&&fb[i]){tot=i;break;}
    for(int i=1;i<=n;i++)if(A[i]%tot==0) ansa=max(ansa,A[i]);
    for(int i=1;i<=n;i++)if(B[i]%tot==0) ansb=max(ansb,B[i]);
    printf("%d",ansa+ansb);
    return 0;
}

T4:

考虑品牌数量极少，可以直接二分+暴力check

首先把物品按价格sort，接下来设s1[i]表示比i物品便宜的，品牌为1的物品数量，其他以此类推

然后二分物品标号，check的话就把所有物品标号<=mid且品牌被XXX所喜爱的加起来

如果数量小于k,那么说明需要价格更高的,l=mid+1;

否则的话就r=mid-1;

code:

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int n,q,d,k,brand[6];
struct node{
    int b,p;
}a[100010];
int s1[100010],s2[100010],s3[100010],s4[100010],s5[100010];
bool cmp(node x,node y){return x.p<y.p;}
int check(int x){
    int cnt=0;
    for(int i=1;i<=d;i++){
        if(brand[i]==1) cnt+=s1[x];
        if(brand[i]==2) cnt+=s2[x];
        if(brand[i]==3) cnt+=s3[x];
        if(brand[i]==4) cnt+=s4[x];
        if(brand[i]==5) cnt+=s5[x];
    }
    return cnt;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].b);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].p);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(a[i].b==1) s1[i]=s1[i-1]+1;else s1[i]=s1[i-1];
        if(a[i].b==2) s2[i]=s2[i-1]+1;else s2[i]=s2[i-1];
        if(a[i].b==3) s3[i]=s3[i-1]+1;else s3[i]=s3[i-1];
        if(a[i].b==4) s4[i]=s4[i-1]+1;else s4[i]=s4[i-1];
        if(a[i].b==5) s5[i]=s5[i-1]+1;else s5[i]=s5[i-1];
    }
    scanf("%d",&q);
    int ans=0;
    while(q--){
        ans=0;
        scanf("%d",&d);
        for(int i=1;i<=d;i++)scanf("%d",&brand[i]);
        scanf("%d",&k);
        if(check(n)<k){puts("-1");continue;}
        int l=1,r=n;
        ans=-1;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)>=k) r=mid-1;
            else l=mid+1;
        }
        printf("%d\n",a[l].p);
    }
    return 0;
}

T5:

设f[i][j][k]表示A串前i个字符，B串前j个字符，LCS至少为K的最小代价

考虑对于i和j，有三种决策：

1.修改i，使其变成j，代价为i^j

2.对于第i个，跳过，不放入LCS

3.对于第j个，跳过，不放入LCS

code:

#include<bits/stdc++.h>
using namespace std;
int n,m,k,f[360][360][360];
char A[360],B[360];
int solve(int a,int b,int c){
    if(!c) return 0;
    if(!a||!b||!c) return 1e9;
    if(f[a][b][c]!=-1) return f[a][b][c];
    int cos=(A[a]-'a')^(B[b]-'a');
    return f[a][b][c]=min(cos+solve(a-1,b-1,c-1),min(solve(a-1,b,c),solve(a,b-1,c)));
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    memset(f,-1,sizeof(f));
    scanf("%s%s",A+1,B+1);
    if(solve(n,m,k)==1e9) puts("-1");
    else printf("%d",solve(n,m,k));
    return 0;
}

T6:

这题的标算是线段树，没有敲。。敲了一个玄学暴力。。于是只讲做法。。。

发现如果x>=40,则x!%1e9==0

所以只需要考虑小于40的所有数，这些数用线段树来维护即可（说起来真简单）

暴力code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1000010],n,m,p,l,r;
ll jie[41];
const int mod=1e9;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    jie[0]=1;
    for(int i=1;i<=40;i++)jie[i]=(ll)jie[i-1]*i%mod;
    while(m--){
        ll cnt=0;
        scanf("%d%d%d",&p,&l,&r);
        if(p==1) for(int i=l;i<=r;i++) a[i]++;
        if(p==2) for(int i=l;i<=r;i++){cnt+=a[i]>40?0:jie[a[i]];cnt%=mod;}
        if(p==3) a[l]=r;
        if(p==2) printf("%lld\n",cnt);
    }
    return 0;
}