Educational Codeforces Round 1

A. Tricky Sum

int fac[N],p2[N];
void init(){
    fac[0]=1;p2[0]=1;
    for(int i=1;i<=33;i++){
        fac[i]=fac[i-1]*2;
        p2[i]=p2[i-1]+fac[i];
    }
}
void solve(){
    int n=read();
    int sum=(1+n)*n/2;
    cout<<sum-p2[(int)log2(n)]*2<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

B. Queries on a String

void solve(){
    string s;
    cin>>s;
    int n=s.size();
    s=' '+s;
    // cout<<"chushi:"<<s<<" end"<<'\n';
    int q=read();
    for(int i=1;i<=q;i++){
        int l=read(),r=read(),k=read()%(r-l+1);
        string t=" ";
        for(int j=1;j<=l-1;j++){
            t+=s[j];
        }
        for(int j=r-k+1;j<=r;j++){
            t+=s[j];
        }
        for(int j=l;j<r-k+1 ;j++){
            t+=s[j];
        }
        for(int j=r+1;j<=n;j++){
            t+=s[j];
        }
        s=t; 
        // cout<<s<<'\n';
    }
    for(int i=1;i<=n;i++){
        cout<<s[i];
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

C. Nearest vectors

极角排序后判断相邻的两个是否是更优

因为有还不会的知识点\(（极角排序）\)所以没写出来

const long double pi=acos(-1);
pair<long double,int> a[N];
void solve(){
    int n=read();
    for(int i=1;i<=n;i++){
        long double x,y;
        cin>>x>>y;
        long double e=atan2(y,x);
        a[i]={e,i};
    }
    sort(a+1,a+1+n);
    a[n+1]=a[1];
    long double minn=inf;
    int ansx=-1,ansy=-1;
    for(int i=1;i<=n;i++){
        long double d=fabs(a[i+1].first-a[i].first);
        if(d>pi)d=pi*2-d;
        if(d<minn){
            minn=d;
            ansx=a[i].second;
            ansy=a[i+1].second;
        }
    }
    cout<<ansx<<" "<<ansy<<"\n";
    //puts(ans>0?"YES":"aNO");
    //puts(ans>0?"Yes":"No");
}

D. Igor In the Museum

int ans[N][N],vis[N][N],n,m;
char a[N][N];
void bfs(int xx,int yy){
    queue<PII>q;
    q.push({xx,yy});
    vis[xx][yy]=1;
    int res=0;
    while(q.size()){
        int x=q.front().first,y=q.front().second;
        q.pop();
        if(a[x+1][y]=='.'&&vis[x+1][y]==0)q.push({x+1,y}),vis[x+1][y]=1;;
        if(a[x-1][y]=='.'&&vis[x-1][y]==0)q.push({x-1,y}),vis[x-1][y]=1;;
        if(a[x][y+1]=='.'&&vis[x][y+1]==0)q.push({x,y+1}),vis[x][y+1]=1;;
        if(a[x][y-1]=='.'&&vis[x][y-1]==0)q.push({x,y-1}),vis[x][y-1]=1;;
        if(a[x+1][y]=='*')res++;
        if(a[x-1][y]=='*')res++;
        if(a[x][y+1]=='*')res++;
        if(a[x][y-1]=='*')res++;
    }
    q.push({xx,yy});
    ans[xx][yy]=res;
    while(q.size()){
        int x=q.front().first,y=q.front().second;
        q.pop();
        if(a[x+1][y]=='.'&&ans[x+1][y]==0)q.push({x+1,y}),ans[x+1][y]=res;
        if(a[x-1][y]=='.'&&ans[x-1][y]==0)q.push({x-1,y}),ans[x-1][y]=res;
        if(a[x][y+1]=='.'&&ans[x][y+1]==0)q.push({x,y+1}),ans[x][y+1]=res;
        if(a[x][y-1]=='.'&&ans[x][y-1]==0)q.push({x,y-1}),ans[x][y-1]=res;
    }
}   
void solve(){
    n=read(),m=read();
    int q=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(ans[i][j]==0&&a[i][j]=='.')bfs(i,j);
        }
    }
    for(int i=1;i<=q;i++){
        int x=read(),y=read();
        cout<<ans[x][y]<<'\n';
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

E. Chocolate Bar

记忆化搜索，用\(F[i][j][ned]\)分别表示，从\(i*j\)的矩形切出\(ned\)个巧克力的消耗

对于每个矩形只有横着掰和竖着掰

让我想起上一场\(div3\)的记忆化搜索也差点没写出来

int f[35][35][55];
int dfs(int n,int m,int ned){
    if(n*m==ned||ned==0)return f[n][m][ned]=0;
    if(n>m)swap(n,m);
    if(f[n][m][ned]){
        return f[n][m][ned];
    }
    int minn=inf;
    for(int i=1;i<=n/2;i++){
        for(int j=0;j<=ned;j++){
            minn=min(minn,m*m+dfs(i,m,j)+dfs(n-i,m,ned-j));
        }
    }
    for(int i=1;i<=m/2;i++){
        for(int j=0;j<=ned;j++){
            minn=min(minn,n*n+dfs(n,i,j)+dfs(n,m-i,ned-j));
        }
    }
    return f[n][m][ned]=minn;
}
void solve(){
    int n=read();
    for(int i=1;i<=n;i++){
        int x=read(),y=read(),ned=read();
        if(x>y)swap(x,y);
        dfs(x,y,ned);
        cout<<f[x][y][ned]<<'\n';
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

F. Cut Length

*2900 计算几何