CodeChef April Challenge 2019 Division 2

ZigZagK

2019年4月15日 19:41

CodeChef

查看标签

0 条评论

上次打完之后分数还是不够Div1……只能再打Div2。

UPD：这次打完分数还是不够QAQ。

Maximum Remaining

去重后第二大。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000;

int n,a[maxn+5];

int main(){
    freopen("MAXREM.in","r",stdin);freopen("MAXREM.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);n=unique(a+1,a+1+n)-a-1;
    if (n==1) return puts("0"),0;printf("%d\n",a[n-1]%a[n]);return 0;
}

Friend or Girlfriend

我tm题目看错了，以为另一个也是字符串……不要在意我代码里的KMP……

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=1000000;

int te,n,m,fai[maxn+5],K,pos[maxn+5];char a[maxn+5],b[maxn+5];LL ans;

int main(){
    freopen("STRCH.in","r",stdin);freopen("STRCH.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%d",&n);scanf("%s%s",a+1,b+1);m=strlen(b+1);K=ans=0;
        for (int i=2,j=0;i<=m;i++){
            while (j&&b[j+1]!=b[i]) j=fai[j];
            j+=b[j+1]==b[i];fai[i]=j;
        }
        for (int i=1,j=0;i<=n;i++){
            while (j&&b[j+1]!=a[i]) j=fai[j];
            j+=b[j+1]==a[i];if (j==m) pos[++K]=i,j=fai[j];
        }
        for (int i=1,j=1;i<=n;i++){
            while (j<=K&&i+m-1>pos[j]) j++;
            if (j<=K) ans+=n-pos[j]+1;
        }printf("%lld\n",ans);
    }return 0;
}

Fencing

DFS（其实根本不用）。

#include<cstdio>
#include<cctype>
#include<unordered_set>
using namespace std;
typedef long long LL;
const int maxk=100000,dif[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

int te,n,m,K,X[maxk+5],Y[maxk+5],ans;
unordered_set<LL> us,vis;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define ID(x,y) ((LL)((x)-1)*m+(y))
void Dfs(int x,int y){
    if (vis.count(ID(x,y))) return;vis.insert(ID(x,y));
    for (int d=0;d<4;d++){
        int xx=x+dif[d][0],yy=y+dif[d][1];LL z=ID(xx,yy);
        if (1<=xx&&xx<=n&&1<=yy&&yy<=m&&us.count(z)) {ans--;if (!vis.count(z)) Dfs(xx,yy);}
    }
}
int main(){
    freopen("FENCE.in","r",stdin);freopen("FENCE.out","w",stdout);
    for (readi(te);te;te--){
        readi(n);readi(m);readi(K);ans=K<<2;us.clear();vis.clear();
        for (int i=1;i<=K;i++) readi(X[i]),readi(Y[i]),us.insert(ID(X[i],Y[i]));
        for (int i=1;i<=K;i++) Dfs(X[i],Y[i]);printf("%d\n",ans);
    }return 0;
}

Subtree Removal

DFS序上DP，不过也可以直接贪心。

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000;

int te,n,X,a[maxn+5],Lt[maxn+5],Rt[maxn+5],ID[maxn+5];LL si[maxn+5],f[maxn+5];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x,int pre=0){
    for (int j=(ID[Lt[x]=++Lt[0]]=x,si[x]=a[x],lnk[x]);j;j=nxt[j])
        if (son[j]!=pre) Dfs(son[j],x),si[x]+=si[son[j]];Rt[x]=Lt[0];
}
int main(){
    freopen("SUBREM.in","r",stdin);freopen("SUBREM.out","w",stdout);
    for (readi(te);te;te--){
        readi(n);readi(X);E=0;for (int i=1;i<=n;i++) readi(a[i]),lnk[i]=0;
        for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);Lt[0]=0;Dfs(1);
        for (int i=0;i<=n+1;i++) f[i]=-1e18;f[1]=si[1];
        for (int i=1;i<=n;i++){
            int x=ID[i];f[i+1]=max(f[i+1],f[i]);
            f[Rt[x]+1]=max(f[Rt[x]+1],f[i]-si[x]-X);
        }printf("%lld\n",f[n+1]);
    }return 0;
}

Playing with Numbers

扩展裴蜀定理，满足条件的一定是 $(a_0,a_1,\cdots,a_k,m_x)$ 的倍数，其中 $\{a_k\}$ 是 $x$ 到根路径上的所有点权。

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=100000;

int te,n;LL a[maxn+5],b[maxn+5],ans[maxn+5];bool vis[maxn+5];
int E,lnk[maxn+5],nxt[(maxn<<1)+5],son[(maxn<<1)+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
void Dfs(int x,int pre=0,LL GCD=0,int D=0){
    GCD=gcd(GCD,a[x]);for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) D++,Dfs(son[j],x,GCD);
    vis[x]=!D;if (D) return;GCD=gcd(GCD,b[x]);ans[x]=(b[x]-1)/GCD*GCD%b[x];
}
int main(){
    freopen("SJ1.in","r",stdin);freopen("SJ1.out","w",stdout);
    for (readi(te);te;te--){
        readi(n);E=0;for (int i=1;i<=n;i++) lnk[i]=0;
        for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);
        for (int i=1;i<=n;i++) readi(a[i]);for (int i=1;i<=n;i++) readi(b[i]);Dfs(1);
        for (int i=1,fst=true;i<=n;i++)
            if (vis[i]) fst?fst=false:putchar(' '),printf("%lld",ans[i]);puts("");
    }return 0;
}

Kira Loves Palindromes

LTL神仙秒了此题。一组合法的方案一定是两个串，其中长的串去掉一个回文串之后是短的串反过来。

枚举第一个串开始位置 $i$ ，第二个串结束位置 $j$ ，二分求出最远扩展到哪里满足第一个串和第二个串反过来一样，然后只要找到一个回文串与这两个串有接触，就对应了一组方案。

那么问题就转化为求一个区间内的回文串个数，可以直接容斥。

还要注意如果一个回文串与枚举的两个串接触部分长度相同，那么会对应两组方案。

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;typedef unsigned long long ULL;
const int maxn=1000,BA=19260817;

int n,num[maxn+5][maxn+5];char s[maxn+5];LL ans;
ULL ha[2][maxn+5][maxn+5];bool PM[maxn+5][maxn+5];

int main(){
    freopen("KLPM.in","r",stdin);freopen("KLPM.out","w",stdout);
    scanf("%s",s+1);n=strlen(s+1);
    for (int i=1;i<=n;i++) for (int j=i;j<=n;j++) ha[0][i][j]=ha[0][i][j-1]*BA+s[j];
    for (int j=1;j<=n;j++) for (int i=j;i>=1;i--) ha[1][i][j]=ha[1][i+1][j]*BA+s[i];
    for (int i=1;i<=n;i++) PM[i][i]=true,PM[i][i-1]=true;
    for (int L=2;L<=n;L++)
        for (int i=1,j=L;j<=n;i++,j++)
            PM[i][j]=PM[i+1][j-1]&&s[i]==s[j];
    for (int L=1;L<=n;L++)
        for (int i=1,j=L;j<=n;i++,j++)
            num[i][j]=num[i+1][j]+num[i][j-1]-num[i+1][j-1]+PM[i][j];
    for (int p=1;p<=n;p++) for (int i=p,j=p,sum=0;1<=i&&j<=n;i--,j++) sum+=PM[i][j],num[i][j]+=sum;
    for (int p=1;p<n;p++) for (int i=p,j=p+1,sum=0;1<=i&&j<=n;i--,j++) sum+=PM[i][j],num[i][j]+=sum;
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++){
            if (s[i]!=s[j]) continue;int L=0,R=j-i-1>>1;
            for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
                ha[0][i][i+mid]==ha[1][j-mid][j]?L=mid+1:R=mid-1;
            ans+=num[i+1][j-1]-num[i+L+1][j-L-1]+L;
        }
    printf("%lld\n",ans);return 0;
}

Mininum XOR over Tree

这题是可持久化Trie裸题……第一问第二问分开做即可，先求出最大异或，然后去找位置最小的满足条件的数。

结果这道题是过的人最少的（除Challenge）？果然中国人民数据结构高超QAQ……

#include<cstdio>
#include<cctype>
#include<algorithm>
#define mp make_pair
using namespace std;
const int maxn=200000,maxt=maxn*21,Log=18;

int T,n,te,a[maxn+5],b[maxn+5],ID[maxn+5],Lt[maxn+5],Rt[maxn+5],A,B;
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];
int len,ro[maxn+5],ch[maxt+5][2],num[maxt+5],ST[maxn+5][Log+5],Lg[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline void writei(int x){
    static int len=0,buf[30];do buf[len++]=x%10,x/=10; while (x);
    while (len) putchar(buf[--len]+48);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
inline bool cmp(const int &A,const int &B) {return a[A]==a[B]?Lt[A]<Lt[B]:a[A]<a[B];}
void Dfs(int x,int pre=0){
    for (int j=(b[Lt[x]=++Lt[0]]=a[x],lnk[x]);j;j=nxt[j])
        if (son[j]!=pre) Dfs(son[j],x);Rt[x]=Lt[0];
}
int Insert(int p,int k,int pos=19){
    int now=++len,d;ch[now][0]=ch[p][0];ch[now][1]=ch[p][1];num[now]=num[p]+1;
    if (~pos) d=k>>pos&1,ch[now][d]=Insert(ch[p][d],k,pos-1);return now;
}
int Ask(int A,int B,int k,int pos=19){
    if (pos<0) return 0;int d=k>>pos&1^1,s=num[ch[B][d]]-num[ch[A][d]];
    return s?Ask(ch[A][d],ch[B][d],k,pos-1)+(1<<pos):Ask(ch[A][d^1],ch[B][d^1],k,pos-1);
}
inline int Find(int x,int l,int r){
    int L=1,R=n,A,B,k;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        mp(a[ID[mid]],Lt[ID[mid]])>=mp(x,l)?R=mid-1:L=mid+1;
    A=L;L=1;R=n;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        mp(a[ID[mid]],Lt[ID[mid]])<=mp(x,r)?L=mid+1:R=mid-1;
    B=R;k=Lg[B-A+1];return min(ST[A][k],ST[B-(1<<k)+1][k]);
}
int main(){
    freopen("XORMIN.in","r",stdin);freopen("XORMIN.out","w",stdout);
    for (int i=2;i<=maxn;i++) Lg[i]=Lg[i>>1]+1;
    for (readi(T);T;T--){
        readi(n);readi(te);E=0;for (int i=1;i<=n;i++) readi(a[i]),ID[i]=i,lnk[i]=0;
        for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);Lt[0]=0;Dfs(1);
        A=B=len=0;for (int i=1;i<=n;i++) ro[i]=Insert(ro[i-1],b[i]);sort(ID+1,ID+1+n,cmp);
        for (int i=1;i<=n;i++) ST[i][0]=ID[i];
        for (int j=1;(1<<j)<=n;j++)
            for (int i=1;i+(1<<j)-1<=n;i++)
                ST[i][j]=min(ST[i][j-1],ST[i+(1<<j-1)][j-1]);
        for (int x,y;te;te--){
            readi(x);readi(y);x^=A;y^=B;int Y=Ask(ro[Lt[x]-1],ro[Rt[x]],y),X=Find(y^Y,Lt[x],Rt[x]);
            writei(A=X);putchar(' ');writei(B=Y);puts("");
        }
    }return 0;
}

Moving Rectangles(Challenge)

我当然不会啦……这里放一个能比纯随机多骗点分的想法：

为了方便假装第 $i$ 次操作在第 $i$ 秒，每次随机 $70$ 个点，找到改变方向之后使得面积增加最大的矩阵，将修改应用在这个矩阵上。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define mp make_pair
using namespace std;
const int maxn=1000,dif[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int te,n,A[maxn+5],B[maxn+5],C[maxn+5],D[maxn+5],d[maxn+5],ID[maxn+5];char s[10];

inline int Area(int i,int j){
    int xs=max(A[i],A[j]),xt=min(B[i],B[j]),ys=max(C[i],C[j]),yt=min(D[i],D[j]);
    if (xt<xs||yt<ys) return 0;return (xt-xs)*(yt-ys);
}
inline int Count(int i) {int S=0;for (int j=1;j<=n;j++) if (i!=j) S+=Area(i,j);return S;}
inline void Inc(int i,int d) {A[i]+=dif[d][0];B[i]+=dif[d][0];C[i]+=dif[d][1];D[i]+=dif[d][1];}
inline void Dec(int i,int d) {A[i]-=dif[d][0];B[i]-=dif[d][0];C[i]-=dif[d][1];D[i]-=dif[d][1];}
inline void Rotate(int t){
    int x=1,y=1,MAX=-2e9,now;random_shuffle(ID+1,ID+1+n);
    for (int j=1,i=ID[j],f;j<=70&&j<=n;i=ID[++j]){
        now=-Count(i);Dec(i,d[i]);f=(d[i]+1)%4;Inc(i,f);now+=Count(i);
        if (now>MAX) MAX=now,x=i,y=1;Dec(i,f);Inc(i,d[i]);
        now=-Count(i);Dec(i,d[i]);f=(d[i]+3)%4;Inc(i,f);now+=Count(i);
        if (now>MAX) MAX=now,x=i,y=3;Dec(i,f);Inc(i,d[i]);
    }Dec(x,d[x]);d[x]=(d[x]+y)%4;Inc(x,d[x]);
    printf("%d %d %d\n",x,d[x],t);fflush(stdout);
}
inline void Reverse(int t){
    int x=1,MAX=-2e9,now;random_shuffle(ID+1,ID+1+n);
    for (int j=1,i=ID[j],f;j<=70&&j<=n;i=ID[++j]){
        now=-Count(i);Dec(i,d[i]);f=(d[i]+2)%4;Inc(i,f);now+=Count(i);
        if (now>MAX) MAX=now,x=i;Dec(i,f);Inc(i,d[i]);
    }Dec(x,d[x]);d[x]=(d[x]+2)%4;Inc(x,d[x]);
    printf("%d %d\n",x,t);fflush(stdout);
}
int main(){
    freopen("RECTARAN.in","r",stdin);freopen("RECTARAN.out","w",stdout);
    for (srand(759405),scanf("%d",&te);te;te--){
        for (int i=(scanf("%d",&n),1);i<=n;i++)
            scanf("%d%d%d%d%d",&A[i],&C[i],&B[i],&D[i],&d[i]),B[i]+=A[i],D[i]+=C[i],ID[i]=i;
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++) Inc(j,d[j]);
            scanf("%s",s);if (s[1]=='O') Rotate(i); else Reverse(i);
        }
    }return 0;
}

本文链接：https://zigzagk.top/2019/04/15/CCAPRIL19B

请不要发毫无意义或内容不文明的评论。与本文无关评论请发留言板！

邮箱格式错误

网址请用http://或https://开头

支持Markdown和LaTeX数学公式

Emoji QwQ 贴吧 QQ Orz

😀 😁 😂 🤣 😃 😄 😅 😆 😉 😊 😋 😎 😍 😘 🥰 😗 😙 😚 🙂 🤗 🤩 🤔 🤨 😐 😑 😶 🙄 😏 😣 😥 😮 🤐 😯 😪 😫 😴 😌 😛 😜 😝 🤤 😒 😓 😔 😕 🙃 🤑 😲 ☹️ 🙁 😖 😞 😟 😤 😢 😭 😦 😧 😨 😩 😬 😰 😱 🥵 🥶 😳 🤪 😵 😡 😠 🤬 😷 🤒 🤕 🤢 🤮 🤧 😇 🤠 🥳 🥴 🥺 🤥 🤫 🤭 🧐 🤓 👻 🤲 👐 🙌 👏 🤝 👍 👎 👊 ✊ 🤛 🤜 🤞 ✌️ 🤟 🤘 👌 👈 👉 👆 👇 ✋ 🤚 🖐 🖖 👋 🤙 💪 🦵 🦶 🖕 ✍️ 🙏 👀 👴 🐴 🍋