Wannafly 挑战赛11

A. 水

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    LL n;
    cin>>n;
    cout<<n+1<<endl;
    return 0;
}

B: 组合数学, 预处理阶乘逆元

因为不可能暴力,所以我们想到是推式子
我们可以把前几项放在Excel表中推一下
然后我们会发现 关于m,n的式子为

常数k*b^(m-1)*a^(n-m)

该式子即为目标结果

如何求常数k呢

设k[n][m] 为n行m列的常数

我们发现 k[n][m]=k[n-1][m]+k[n-1][m-1]
这个式子和组合数学里的 C(n,k)+C(n,k+1)=C(n+1,k+1) 相似

所以 k[n][m]=C(n-1,m-1)

但因为我们无法以O(N^2)解决这道题,所以不能用递推式求组合数

那我们就直接用 组合数的公式求

C(n,m)=n!/((n-m)!*m!)

预处理n!和n!的逆元

这里因为数组有限,无法使用递推式求逆元,

所以我们用费马小定理求逆元

a^(p-1)≡1(mod p)

则 a^(p-2) 即为 a 对于 p 的逆元.

预处理即可

当n < m时,ans=0

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int maxn = 100000;

int a,b,n,m;
int T;

ll inv[maxn+10],fac[maxn+10];
///预处理N!的逆元
//费马小定理
/*
 *假如p是质数,且gcd(a,p)=1,那么 a^(p-1)≡1(mod p)
 *根据这个性质我们可以知道 a的逆元为a^(p-2)
 */
ll fast_pow(ll a,ll b)
{
    ll ans=1;
    while(b){
        if(b&1ll)ans=a*ans%MOD;
        a=a*a%MOD;
        b>>=1ll;
    }
    return ans;
}
void pre()
{
    inv[0]=1ll;
    fac[0]=1ll;
    for(int i=1;i<=maxn;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=fast_pow(fac[i],MOD-2ll);
    }
}
ll C(ll a,ll b)
{
    return fac[a]*inv[b]%MOD*inv[a-b]%MOD;
}

int main(){
    pre();
    scanf("%d",&T);
    for(int k=0;k<T;++k){
        scanf("%d%d%d%d",&a,&b,&n,&m);
        if(n<m){
            printf("0\n");
            continue;
        }
        int t=n-1,s=m-1;
        ll ans=1;

        ans=ans*C(n-1,m-1)%MOD*fast_pow(a,n-m)%MOD*fast_pow(b,m-1)%MOD;
        printf("%lld\n",ans);
    }
    return 0;
}


/// C(N-1,M-1)*b^(M-1)*a^(N-M)
/// N<M 0

2018年全国多校算法寒假训练营练习比赛(第五场) C KMP-Next数组

Next数组

自己写的卡在%95.00的代码

我自己写的代码,至今想不通漏了什么情况,被卡在%95.00…

#include<bits/stdc++.h>
using namespace std;
const int maxn=1001000;
int Next[maxn],len;
char str[maxn];

map<int,int> ex;

void getNext(){
    Next[0]=-1;
    int k=-1;
    int j=0;
    while(j<len){
        if(k==-1 || str[j]==str[k]) Next[++j]=++k;
        else k=Next[k];
    }
}

void print(){
    for(int i=1;i<=len;++i){
        printf("%d ",Next[i]);
    }
}

void solve(){
    ex.clear();
    getNext();
    //print();
    int bef=Next[len],now,max_len=0;
    if(bef==0){
        printf("Just a legend\n");
        return;
    }
    while(bef!=0){
        now=bef;
        bef=Next[bef];
    }

    for(int i=1;i<=len;++i){
        if(Next[i] && Next[i]%now==0){
            int k=Next[i]/now;
            for(int j=1;j<=k;++j){
                ex[j*now]++;
            }
        }
    }
    map<int,int>::iterator it;
    for(it=ex.begin();it!=ex.end();it++){
        if(it->second>1) max_len=max(max_len,it->first);
    }
    if(max_len){
        max_len=min(max_len,Next[len]);
        for(int i=0;i<max_len;++i){
            printf("%c",str[i]);
        }
    }else printf("Just a legend");
    printf("\n");
}

int main(){
    while(cin>>str){
        len=strlen(str);
        solve();
    }
    return 0;
}

AC代码

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1001000;
int Next[maxn],len;
char str[maxn];

int exist[maxn];

void getNext(){
    Next[0]=-1;
    int k=-1;
    int j=0;
    while(j<len){
        if(k==-1 || str[j]==str[k]) Next[++j]=++k;
        else k=Next[k];
    }
}

void solve(){
    memset(exist,0,sizeof(exist));
    getNext();
    int bef=Next[len];
    if(bef==0){
        printf("Just a legend\n");
        return;
    }
    //忽略第一个和最后一个
    for(int i=2;i<len;++i){
        exist[Next[i]]++;
    }

    while(bef>0){
        if(exist[bef]){
            for(int i=0;i<bef;++i){
                printf("%c",str[i]);
            }
            printf("\n");
            return;
        }
        bef=Next[bef];
    }
    printf("Just a legend\n");
}

int main(){
    while(cin>>str){
        len=strlen(str);
        solve();
    }
    return 0;
}

当然,还有一种方法是比较特别的(比较直观),把每个可能子串KMP一下,如果匹配成功了,就直接输出就好了

#include<cstdio>
#include<cstring>
char a[1000005],b[1000005];
int next[1000006];
void getnext(char *c)
{
    next[0]=next[1]=0;
    int i,j,len=strlen(c);
    for(i=1,j=0;i<len;i++)
    {
        while(c[i]!=c[j]&&j!=0)
            j=next[j];
        if(c[i]==c[j])j++;
        next[i+1]=j;
    }
}
int kmp(char *o,char *f)
{
    int cont=0;
    int i,j,len1=strlen(o),len2=strlen(f);
    for(i=0,j=0;i<len1;i++)
    {
        while(o[i]!=f[j]&&j!=0)
            j=next[j];
        if(o[i]==f[j])j++;
        if(j==len2)
        {
            cont++;
            j=next[j];
        }
    }
    return cont;
}
int main()
{
    int i;
    scanf("%s",a);
    getnext(a);
    int len=next[strlen(a)];
    if(len==0)
    {
        printf("Just a legend\n");
        return 0;
    }
    for(i=0;i<len;i++)
        b[i]=a[i];
    b[i]='\0';
    int cont=kmp(a,b);
    while(cont<3)
    {
        len=next[len];
        if(len==0)break;
        for(i=0;i<len;i++)
            b[i]=a[i];
        b[i]='\0';
        cont=kmp(a,b);
    }
    if(cont>=3&&len)printf("%s\n",b);
    else printf("Just a legend\n");
    return 0;
}

1

2

2018年全国多校算法寒假训练营练习比赛(第五场) G 斐波那契博弈

斐波那契博弈模板题,我凑…

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
set<int> st;
int FB[maxn];
int n;
inline void init(){
    FB[1]=1ll;FB[0]=1ll;
    int i;
    for(i=2;FB[i-1]<=1e9+7;++i){
        FB[i]=FB[i-1]+FB[i-2];
        st.insert(FB[i]);
    }
}

int main(){
    init();
    while(~scanf("%d",&n)){
        if(st.find(n)!=st.end()){
            cout<<"Sha"<<endl;
        }else{
            cout<<"Xian"<<endl;
        }
    }
    return 0;
}

2018年全国多校算法寒假训练营练习比赛(第五场) H,F,B

H,和B是树状数组.F是水题,其实前两个也算水(模板)了.

需要提的是,H用的是树状数组的区间更新和区间查询.

H

#include<bits/stdc++.h>

#define lowbit(i) (i & (-i))

using namespace std;
typedef long long LL;
const int Nmax = 100100;
int N,Q;
LL delta[Nmax];//delta的前缀和
LL deltai[Nmax];//delta*i的前缀和
LL sum[Nmax];//原始前缀和

LL query(LL *arr,int pos){
    LL temp=0ll;
    while(pos>0){
        temp+=arr[pos];
        pos-=lowbit(pos);
    }
    return temp;
}

void update(LL *arr,int pos,int x){
    while(pos<=N){
        arr[pos]+=x;
        pos+=lowbit(pos);
    }
}

int main(){
    scanf("%d%d",&N,&Q);
    LL nw;
    char opt;
    for(int i=1;i<=N;++i){
        scanf("%lld",&nw);
        sum[i]=sum[i-1]+nw;
    }
    while(Q--){
        getchar();
        scanf("%c",&opt);
        if(opt=='C'){
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            update(delta, l, x);
            update(delta, r+1, -x);
            update(deltai, l, x * l);
            update(deltai, r+1, -x * (r+1));
        }else{
            int l,r;
            scanf("%d%d",&l,&r);
            LL suml = sum[l - 1] + l * query(delta, l - 1) - query(deltai, l - 1);
            LL sumr = sum[r] + (r + 1) * query(delta, r) - query(deltai, r);
            printf("%lld\n", sumr - suml);
        }
    }
    return 0;
}

B

#include<bits/stdc++.h>
#define lowbit(i) (i&(-i))
using namespace std;
typedef long long LL;
const int maxn=100100;
LL Tree[maxn];

void add(int x,int value){
    for(int i=x;i<=maxn;i+=lowbit(i)){
        Tree[i]+=value;
    }
}

LL get(int x){
    LL sum=0ll;
    for(int i=x;i;i-=lowbit(i)){
        sum+=Tree[i];
    }
    return sum;
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        LL q;
        scanf("%lld",&q);
        add(i,q);
    }
    for(int i=0;i<m;++i){
        int ck;
        scanf("%d",&ck);
        if(ck==1){
            int x,k;
            scanf("%d%d",&x,&k);
            add(x,k);
        }else{
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%lld\n",get(r)-get(l-1));
        }
    }
    return 0;
}

F

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    while(cin>>n){
        while(n/10){
            int nn=0;
            while(n>0){
                nn+=(n%10);
                n/=10;
            }
            n=nn;
        }
        cout<<n<<endl;
    }
    return 0;
}

2018年全国多校算法寒假训练营练习比赛(第五场) A 逆序数

链接:https://www.nowcoder.com/acm/contest/77/A
来源:牛客网

题目描述

在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为4 5 1 3 2, 那么这个序列的逆序数为7,逆序对分别为(4, 1), (4, 3), (4, 2), (5, 1), (5, 3), (5, 2),(3, 2)。

输入描述:

第一行有一个整数n(1 <= n <= 100000), 然后第二行跟着n个整数,对于第i个数a[i],(0 <= a[i] <= 100000)。

输出描述:

输出这个序列中的逆序数

示例1

输入

5
4 5 1 3 2

输出

7

两种方法求逆序数

归并排序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=100010;

int seq[maxn],N;
int temp[maxn];
LL cnt;
//归并排序求逆序数
void merge_sort(int arr[],int l,int r){
    if(l==r)return;
    int mid=((l+r)>>1);
    merge_sort(arr,l,mid);
    merge_sort(arr,mid+1,r);
    int i=l,j=mid+1;
    for(int k=l;k<=r;++k){
        if(j>r || (i<=mid && arr[i]<arr[j]))temp[k]=arr[i++];
        else temp[k]=arr[j++],cnt+=mid-i+1;
        //如果a[i]>a[j]则逆序数加上mid+1-i,即剩下的前面个数
    }
    for(i=l;i<=r;++i)arr[i]=temp[i];
}

int main(){
    cin>>N;
    for(int i=0;i<N;++i){
        cin>>seq[i];
    }
    cnt=0;
    merge_sort(seq,0,N-1);
    cout<<cnt<<endl;
    return 0;
}

树状数组

牛客练习赛 12 A,B

Link

https://www.nowcoder.net/acm/contest/68#question

题目都很易懂

第一题题解

把弧度值当角度来做即可,如果弧度是负数,把它转换成顺时针下的弧度值即可, 那么如果 a-b\<0则代表b在a顺时针前面,否则是a在b顺时针之前

然后分情况讨论即可,即钝角和锐角的情况

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    double a,b;
    int t;
    cin>>t;
    while(t--){
        cin>>a>>b;
        if(a<0.0) a=M_PI+a;
        if(b<0.0) b=M_PI+b;
        double rg=a-b,rt=abs(rg);
        if(rt>M_PI){
            if(rg>0.0){
                printf("counterclockwise\n");
            }else{
                printf("clockwise\n");
            }
        }else{
            if(rg>0.0){
                printf("clockwise\n");
            }else{
                printf("counterclockwise\n");
            }
        }
    }
    return 0;
}

第二题题解

我们将vis数组设为两重,一重是有钥匙,一重是无钥匙

vis[has_key?1:0][x][y]

bfs即可

代码

#include<bits/stdc++.h>
using namespace std;

typedef struct Node{
    int has_key;
    int cnt,x,y;
}node;

char mp[510][510];
int h,w,sx,sy;
//об,ио,ср,вС
int mv[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

int vis[2][600][600];

void bfs(){
    bool yes=false;
    queue<node> st;
    st.push((Node){0,0,sx,sy});
    vis[0][sx][sy]=1;
    while(!st.empty()){
        node nd=st.front();st.pop();
        if(mp[nd.x][nd.y]=='E'){
            printf("%d\n",nd.cnt);
            return;
        }
        if(mp[nd.x][nd.y]=='K'){
            nd.has_key=1;
        }
        int nx,ny;
        for(int i=0;i<4;++i){
            nx=nd.x+mv[i][0],ny=nd.y+mv[i][1];
            if(vis[nd.has_key][nx][ny]) continue;
            if(mp[nx][ny]=='W') continue;
            if(mp[nx][ny]=='D' && !nd.has_key) continue;
            vis[nd.has_key][nx][ny]=1;
            st.push((Node){nd.has_key,nd.cnt+1,nx,ny});
        }
    }
    printf("-1\n");
}

int main(){
    cin>>h>>w;
    bool flag=true;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<h;++i){
        scanf("%s",mp[i]);
        for(int j=0;flag && j<w;++j){
            if(mp[i][j]=='S'){
                sx=i,sy=j;
                flag=false;
            }
        }
    }
    bfs();
    return 0;
}

2018全国多校算法寒假练习赛(三) A

Link

https://www.nowcoder.net/acm/contest/75/A

Type: 数论-Stirling公式

题意

给你一个n,问你n!的八进制位数是多少.

数据范围

有t(1~1000000)组数据
每组数据大小为 0~1000000

题解

由以上数据范围我们知道不能乱搞(暴力或者打表都会爆)了.
这里提第一个点:

求数M的K进制位数,答案就是

logK(M)+1

第二点:

n! 近似公式 – Stirling公式

结合这两点不难得出下列公式:

log8(n!) = M
=log8(sqrt(2*pi*n))+log8((n/e)^n)
=log8(sqrt(2*pi*n))+log8((n/e)^n)
=log8(sqrt(2*pi*n))+n*log8(n/e)
=ln(sqrt(2*pi*n))/ln(8)+n*ln(n/e)/ln(8)

常数时间就可以求出来了.

Code

#include<bits/stdc++.h>
using namespace std;
//M_PI,M_E
int main(){
    int t,n;
    cin>>t;
    for(int i=0;i<t;++i){
        scanf("%d",&n);
        if(n==0){
            printf("1\n");
            continue;
        }
        double ans=log(sqrt(2*M_PI*n))/log(8)+n*log(n/M_E)/log(8);
        printf("%d\n",(int)ans+1);
    }
    return 0;
}

2018全国多校算法寒假练习赛(三) G

Link

https://www.nowcoder.net/acm/contest/75/G

type: 容斥定理,1~n整数倍定理

题意

给你一个n(1~1e18 long long 范围内),问你1~n中不为2,5,1,,13倍数的数有多少个.

题解

1.我忘了一个定理:

设求: 1~n之间有多少个数是给定的x的倍数?

答案为 n/x

有了以上那个定理就好求了,设条件 A 为1~n中2的倍数,B 为1~n中5的倍数,C,D.
则答案就是:

|(~A)∩(~B)∩(~C)∩(~D)|

标准容斥,情况只有2^4-1=15种,写代码吧

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

void solve(LL N){
    LL ans=N;
    LL k[4]={2,5,11,13};
    for(int seq=1;seq<16;++seq){
        LL reg=1;
        int d=0;
        if(seq&1) reg*=k[0],d++;
        if(seq&2) reg*=k[1],d++;
        if(seq&4) reg*=k[2],d++;
        if(seq&8) reg*=k[3],d++;
        if(d&1) ans-=(N/reg);
        else ans+=(N/reg);
    }
    printf("%lld\n",ans);
}

int main(){
    LL n;
    while(cin>>n){
        solve(n);
    }
    return 0;
}

2018全国多校算法寒假练习赛(三) D

这道题以前在lrj上见过,不过没注意.

Link

https://www.nowcoder.net/acm/contest/75/D

Type: 博弈论

题目

链接:https://www.nowcoder.net/acm/contest/75/D
来源:牛客网

小牛和小客玩石子游戏,他们用n个石子围成一圈,小牛和小客分别从其中取石子,谁先取完谁胜,每次可以从一圈中取一个或者相邻两个,每次都是小牛先取,请输出胜利者的名字(小牛获胜输出XiaoNiu,小客获胜输出XiaoKe)(1 2 3 4 取走 2 13 不算相邻)

约束

输入包括多组测试数据
每组测试数据一个n(1≤n≤1e9)

输出

每组用一行输出胜利者的名字(小牛获胜输出XiaoNiu,小客获胜输出XiaoKe)

题解

我直接说推出的结论了
很明显的是:

n=0时,先手必败,n=1,2时,先手必胜

然后我们看n>=3:

  1. n=3时很明显先手必败
  2. n=4时,无论先手者取1还是2,只需要和他取一样的即可,把当前的石子堆分成两部分,每部分有一样的石子,可以发现,该情况下先手必败(只需要和先手者操作一样即可获胜).

    然后我们可以发现只要是偶数都可以这样乱搞

  3. n=5时,无论先手者取1还是2,只需要和他取相反的即可,其余和以上一样,同样将石子堆分为两堆.

    然后我们发现只要是奇数都可以这样乱搞

Code

/**

                                                                       :;LaEaHKEEGpPXU7;,
                                                                  .:75pKH11252U252XapZgRQgD6XJscLr;,.
                                                               :LXpRgGaX521JLw1JswJJsJs22XHPPEZEGDOMMRDOa7.
                                                           .r2EDDZEpZPZP6KpHX5SXH5XXa5KwaXaSX5UJ1c77sLs2GMQQ6r                                       .
                                                        ,LpgOGpEZGZEZEpZKpHHU5wP5HEDgpXpHa2SSa5aSXULr7rrirrJXRBp;                                   ;B
                                                     ,J6MRZH6EgEEZE6E6EZZPZXXwSSGQXr::aPpP5USUHaHaKa5Lvrr7ri;rLHBB2:                                Kc
                                                   rpQDOpPPOGGZOGOZG6GEOEOEDPPGBa.  .PaSSUXSUUUaUSaKXKS177r7rrrirSBBR7                             .O,
                                                :UBQOKPK6ZOOOEDEO6GZE6EpEpDgDBR:   UBpXHa5aSaUS5SUS5XapPHJc7rrv7rr7sgBBs                           .g.
                                              ;gBMPXpO6GEOEOEOEGEOEE6EZEEDRGBB    EB5pKSXpHKaHSX552S5aUHHEX17c7vr7777s5RBS:                        .R;
                                           .sQBPXpDZOODOgODGOGgEDEOEOGgGgOOMB:   LBKKSXSHa52aaKXHXKaa5aSaaHXSJLcL7vcc777JDBBg2;.                    Qi
                                         ;2ggp2EDDOggGEDGgDDOgGGZDOOZOGg6gEBX    vBZaHUKaaUXXXSXXKXpXHXH5wwaa52U1wssLsLJccv1UDQBQ67.                O7
                                       :ZZUU5PROOEOZOZGGOODZOGgODZOOgOggRgRB; ;:..R6XaKKpP6PGppKPHpHpPX5aU21UUa5Sw52UwUJJv77L77sSpQMDU;            ;B5
                                     ,SRJ7sSHGggEOZOEG6OODpOZgggOQQBBBBBQBBQ.,;;. LBOgOgDRDDZODMgQRgRDaa552a252UUa25w5UaU2sLvccs7r7sJZBBMr       ,XQJ:
                                    LQHr77J6RGOZDZOEGEDGgDRORQBBBQRDPU1Jscwa7.,::.:J7r;::::.  ..,:;i7UOgRRRgDPH5SUSU52U2HHa1JJJLJLccLr71RBB,    7R2,
                                  :RZv;77JSgGOZEODEDGOEggQBBBMS7;:,:,,.,.,.:7L;:,;.:  ,: . .....       .:;rJU6GgGRggEZHPaKXX2S221Js1Lc7r:7QB. .XX:
                                 7g1;;7rcXG6gpGDZGgZOOQBBQpr.   ::::;:;:::Jr::sr;::;:.:vs,:::::::::::,,         ,:7L5HGOggRgZUUU5wSUaJLc7r7BOiDr  ...
                               .XX;;;irLHGKpZZZEKgDRBBB6i    ,;;:;;;;r;;:s177:,;L7:;7:.rHi,:::::::::::::::::,.         .,;7ZRQgO6KUUJsLwsJ7KBM. .....
                               JZ:;rrrc5EPHp6XgpRBBBE;     :i:;;;;;:;;;:c7::r7;,::::::::rv:,:::::::::::,:,:,:,,,,            .;sORQRGX21wsXU:  .... .
                              .Br;iir72EHPHZ6EgBBR7.   ..;ii:;;;;;;;;;:71r::.:7,  .::7;:;H;.::,:::::::,:::::,,,::,,,              ,7wEDRZBMr  .......
                              1D;:r;rwOPXPKH6BBX,   .:;:;;;:::;:;;;;;::Ls,;ss..r.  ,c77;sLU,:,:::,:::,:,:,:,,,:,,,:::.                  .:.rP:.......
                              D2:i;rJpKHXHXgg7    .,,::::;:::::;:;:;;:;SL7sS2, :.   ::::,:U7.:::,:::,:,,,,,:,,.,,,.,:,                    ;L:. .. ...
                             :Qc;i7LGZPa6gBM,  ...,,::::::::::::;;::;.JJ;ic:         ;:::,v1,.:::;7,,,:,:,:,,,,.:,,,,..                :2wr.  .......
                             sRr:rrwZGgBQR7.  .,,::::::::::::::;::;:::Hr:7i          ,;;:::U: .,,,:r.,,:,:,:,,,:,,,.....             7K2:. ..........
                             OX:irsXgQZ:.   .,,:::,,:::,::::::::;;;::r5;r7:           :;;;:7L ..,.,;:,:,:,,,:,:,,,,......        .rU6w;..............
                            .BJ71EK5;.   .,,::,:,:,,,:,:,::::::::;:;.Ls;r7             :;:::s, ..,,,r:.:.,,,.:, .,..... .    .;s5XJr,..,.............
                            1Mv::.     .:,:,,,,,,,:::::::,;:::;:;::..J7;c:          ,. ,rri:27  , .,:;. ,:,:,,:..,....    .rpPL;:.. ... .............
                       ..7Ls:        .,,,:,,,:,:,:::,:,:::::,:::::: .Srrr,  .,:;;;::::..:7r;r1    .: :E:..,,:,...,,.., ..XBQ7, ................... ..
                  ,;7v7r7:,         ,,,,:.,,,,,,:,,::,:,,.::.,:.,:, :Jrr; ,r7,:..        ,:::L:  .  .7RJ .,.:.,......,,:MBs   ..............,........
            .:;vJs7i,              ,,,., ..,,:,,,:,,,:,:.,rs,,.:,,  ;J;c,                .,::;;     Lr.E: .,...,....:,:1Z:  .........,.,...........:,.
   .;,,:r7J1wv;,.               ....,.:. .,.,,:,,,:,,::::,sS;.:::,  cLrr.     .       .,. .,..:    ;;  r5 ........,,:;s7. ....,.,.,...........,.,.,,.
   ,BBs:::                   . ........,.,,,,,.:,,,:,:,,.;s7r,,,,,  cc7;         ,.,,.      .:7rrJGMPOEL1, ..... ,,:rSr, : ,.,.,.,.,.........,,,,,. ..
     rZL.                   ....... ..,,,.,,,..,,,.,;,...7J:s: ..  .wr7,        ...    .rJpQBBBBBBBQgKP77s  ..  .,7S2,,....,....,.,.,......,,.,. .:cX2
       ;SH7,               . . . .. .,.,.,.,,,...,..r, ::Ur;7L .   .57;.           .rPBBQBBBPws:;r::::.,:P.    .;S5;,..,...,.,.,.,.... ..,,, ..,7HSJvr
          r7r;:             . ... ..........,...,.. 7L;,rS;;ivr .   1r:       .  .rZBBK7;.JL,::Jrs;.:;,:;J, .,;LDv..:.,...,.,.,.,...,.,,:,, ,7sKGwc77;
             .:7L7:,            . ,r,..,.,,,...,..:iLL  7s;r;cv:    U7.         :vi;:. .. :Er:::.Ls. . ,7::::vHEi ,:,,.,,,.,.,,,,,,::::, .:1QBKJJUsssc
                .:rvw1JsL7;,      ,;..........,.:ir :r .ELr77v:,.   Pr          ..      .  Ls    ,w.   rr.r:JPr. ::,..,,,.,,,,:,:::,:,..7XgRE52US25w1c
                      .:;7JRQpX:   ; .........,i:  .,J ;gri;7r  :   1;                     .X:    .   ,v :aK1, ,,:.,,,.,,,,:::::,;::::cOBB6K55UXUX5XUw
                           ;J,XQB7,:    . ...,:   .:7Z.7Zi7;r:   ,  v,                      :w:;,.,:::7LUsc:..:,:.:,,,,,:,:::::::,:;c5BBPS5wSUSUaUaUa2
                           J7  rEBBg..,. ..... .  ,L1PLKr:,:;r;;::, :,                       :;SXsJU1XLLr....:,,,,,,::::,::::::,::LL,,rZXUJU25552aUUUU
                           JL .:sXBB:... ., .    ,OH777;,rZRBBBQL ..r,                     ,:r7::r:,;;....:,,,,,,,,.::::;::;:::.7gL    UK2UUS1aw2wU25J
                           U7 .r71BB;  . :.. .. :QJ;.;1pBBBBBGRBRi  i:                   .      .w7.   ..,,:,,,,,:,:,:::::::,.,2BR:   .DSaUSUUS525w5U1
                           2r :7rJBQ7   .;. .   KL::JGBBBgE6Hp6XMQ;     .                    ... ,2s    ,,,,:::::,:::::::,,.:sQQB2    ;DHa5U52S2U25USJ
                           a: :7;1BB2   .v,    sL;LPQgDBPH6KPQBpGBG    .                   ... ..  aP:. .. ,::,:::::,,,,.;rSgBQDa;    :gSSwSUUU525US2U
                           5; ;;r2QBB,  .s:  :a7:PBZ2,:BEaZPKgBZOgB,                        .   ...:LEHri::,:.,,.,,,::rsXRBgGKEJi,    2GH252SUS5S11wH5
                           U: ;:rwDBBr  .c, rB6r 167.,,RQPpEP6OpKEBc      .,                 .   : ::sS7;cKB6HHa1XOQRRQBRgEZDBH; ..  ;RZUPSSU525USSpK2
                           s; ;::aBg,   .; .Gv,H::,,::,;BQDOGHPXpKBs      .,.                 . .,.  .r:;:6gOEBQRRRDggQgOHgMGL,    .;PEHHXaaKaPXPKPaXS
                           s7.:,sBa     :..S,  vE::::;  7BBMgZH6pQBr             .             ,:,   ,.,r2RHSSpMZPKRRZpgggav,    ;UpEZaaaKHHUHPPaUJHGO
                           a;.775:    .::rU.    gR:,:.   :;:BBBBQar                         .  ,,   ,.,7rggJwU6DDGMgOGgXc:,   ,rPGOpKSXSXSKUKHU1UHgOEP
                          1i :SZJrLXpBBMRB:  .v  Ba,.       :sv:                             .        irsBUSpEEGPPpg65r:..,;sKZDZHSX5XaHU55K2wUGMRZ6Z6
                         :K  :7asvwc2MgEQB, :gg.:iB7  .,,,:.                      ...,.   .     ..   .:iM6GEpSSXZOEs:...;spZpKKXXSX5Xa5Ja5wwKGQDEpp6OZ
                         w; ,LXLr77sLwL5aR. gRgQgaQBi ,vJwvi,.                 .;;:;7:   .   .  ,...  rRDRJUSXpgas:,.:;U66SaHa2X5aUa552X12SgQgpZpEpGOD
                         H: ;XJ;77rv7rJUaQ;rgaPgXXHBB;        . .              .ri:;;          ,: . :6QZEKHXpXXL:,::r1PKXaa2XSS5a5S5UJ22aOBgEpOppZOOgG
                         iwsJsr7rsLrrLcJ2gQGXHwa1SUHBB:  . ... .                 ..,           :   1BRKpOEGp2Jr;::rsXP1Uaa2U5a5aUa5SsSpgQRZGZEEZZOOgDg
                           ,cs5aXaP552ssLwRSHXaSS5asXBB.      . .                             .  LBBgGgZHsr;vrr;rcXpP5UUS5X5S2XS5SS1URBggpEZgDDGOGggRD
                              ,;irrs2KgQRPJJJSUXKXSHJpBM   . . .                                ZBBOUsr;:.  ,,,rHgZPUaSaUSUSSXaUPXsSBB6ZZp6EEGOOGDEggO
                                       ;BBQQZaSJ5J15SJDQ7                                    .iEBL:.  . .,:,:;SRQGZXPXXSHaS2UUSUSswQB6OZgG6pZZGODEOGDE
                                      JgUri1aGEpEpXSS5LBQ,                              .rLap2Jr     ;712OO6ZggRDZXHXpKK2211LLLc7wgBa2PODRGE6OZgDgGDGD
                                    7QB; ,Jc76DaZXOZgDPEBBX,                       :c1HEZ1c;:,.,:;cHDgQQggMZgGOZO6OEGpXsLLsJXHPOBBBc;vss5EMggZDODOgED6
                                   LZJ::iwrrr72EPgXU5OBBBBBBBp7:               .i5P6wL;,   .:LS6DMgMgZKgEOPOGGDDGEXULvLSOBBBBBQBgDQDJ5rrr7JOQQDDZGEgDD
                                   wp rR5,       .HQRX7r72RQBBBBBQBMEK6Uc7sc7cHOU:,     .:LHgOQg6ZOPZpZGGEDERZPwcr7LKDDaJr:.      rBX;;:r:ir1DBQMgRgDp
                                   7D,sw:      ,   Z.      .LgBBQBBOsJaQBBBBBBXrr.  .:rwZBBQgROgDgDOERRMgROOScrLsPP5r,             7Qs,::::::rUgRgZOG6
                                   ,Q57:r  ,:  ,r  U:         .;;   .vL7L;r:UG7.:sr;JSgQBgDEZXXUSXpHa21svr7r7s2v:.                  iQK...:,:::;LLJJws
                                    OBHs;.  :;;,v  H:             :6X;       rpL;7pSrrr7r;::,....,,:;iirrvvvr,                       :BBPs;;:,,,,::;::
                                    ::rPDEL:..7:c;7r              pK  .:      :KL.:r:..     ..:icsS5sr:,.                              JgGgBQDOSJss77r
                                         :r;:::  ,                PH r,       ,;5: ,::::;7Ls7Lc7;:                                         ,:7JP17rJUs
                                                                  .:J: :;  .,:K6BQS7:.,.,.
                                                                    :r7Ji;r7;::;;.**/
                                                                        .
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        if(n<=2)cout<<"XiaoNiu"<<endl;
        else cout<<"XiaoKe"<<endl;
    }
    return 0;
}

牛客练习赛11

A:假的线段树

题目

链接:https://www.nowcoder.com/acm/contest/59/A
来源:牛客网

给你一个长为n的序列a,有m次操作

1.把区间[l,r]内所有x变成y

2.查询区间[l,r]内第k小值

对于100%的数据,1 <= n, m , ai <= 1000

输入描述

第一行两个数n,m
第二行n个数表示序列a
后面m行
1 l r x y :把区间[l,r]中所有x变成y
2 l r k :查询区间[l,r]中的第k小值

输出描述

对于每个询问,输出一个数表示答案

示例输入

3 3
2 3 3
2 1 3 1
1 1 3 3 1
2 1 3 2

示例输出

2
1

题解

数据量小.1000*1000的复杂度,可以暴力过.第K小直接排序即可.

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int n,m;
int num[maxn];

void solve1(){
    int l,r,x,y;
    scanf("%d%d%d%d",&l,&r,&x,&y);
    for(int i=l;i<=r;++i){
        if(num[i]==x)num[i]=y;
    }
}

void solve2(){
    int l,r,k;
    scanf("%d%d%d",&l,&r,&k);
    int copy[maxn];
    for(int i=l;i<=r;++i){
        copy[i]=num[i];
    }
    sort(copy+l,copy+r+1);
    printf("%d\n",copy[l+k-1]);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&num[i]);
    }
    int query;
    for(int i=0;i<m;++i){
        scanf("%d",&query);
        if(query==1) solve1();
        else solve2();
    }

    return 0;
}

D:求距离

题目

链接:https://www.nowcoder.com/acm/contest/59/D
来源:牛客网

给你一个1 -> n的排列,现在有一次机会可以交换两个数的位置,求交换后最小值和最大值之间的最大距离是多少?

水题

输入输出格式看链接吧

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=110;
int num[maxn];
int main(){
    int n,mi=1,ma=1;
    num[0]=0;
    scanf("%d",&n);
    scanf("%d",&num[1]);
    for(int i=2;i<=n;++i){
        scanf("%d",&num[i]);
        if(num[i]<num[mi]) mi=i;
        if(num[i]>num[ma]) ma=i;
    }
    int min_id=min(mi,ma),max_id=max(mi,ma);
    int a=n-min_id,b=min_id-1,c=n-max_id,d=max_id-1;
    printf("%d\n",max(a,max(b,max(c,d))));
    return 0;
}

E:求最值

链接:https://www.nowcoder.com/acm/contest/59/E
来源:牛客网

给你一个长为n的序列a

定义f(i,j)=(i-j)2+g(i,j)2
g是这样的一个函数

求最小的f(i,j)的值,i!=j

题解

这道题数据水,可以直接枚举距离1和距离2水过.

代码

#include<bits/stdc++.h>
#define TREE_SIZE (1<<(20))
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=100010;
long long sum_z[maxn],sum_f[maxn];
int n,num[maxn];

inline long long g(int i,int j){
    register long long sum=0;
    long long k=min(i,j),l=max(i,j);
    sum=sum_z[n]-(sum_z[k]+sum_f[j+1]);
    return sum;
}

int main(){
    scanf("%d",&n);
    sum_z[0]=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&num[i]);

        sum_z[i]=sum_z[i-1]+num[i];
    }
    sum_f[n]=0;
    for(int i=n;i>=1;--i){
        sum_f[i]=sum_f[i+1]+num[i];
    }
    long long res=1000000000;
    for(int i=2;i<=n;++i){
        int T=min(1000,i);
        for(int j=1;j<T;++j){
            long long reg=g(i-j,i);
            //printf("i:%d,j:%d,reg:%d\n",i,j,reg);
            long long ans=j*j+reg*reg;
            res=min(res,ans);
        }
    }
    printf("%lld\n",res);
    return 0;
}


但是这道题是平面最近点对