A. Maxim and Biology

题意:

给一串字符,字符可以通过操作变成前一个或者后一个字符,a的前一个字符为zz的后一个字符为a,求一个长度为4的子串,可以通过最小的操作数变成ACTG,输出操作数。

题解:

暴力算出每个字符对于ACTG的距离,然后前缀和就好了。

代码:

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 1000005
#define int long long
using namespace std;
il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char s[Max];
int n,t[Max][4],ans=1e16;
il int cg(char a)
{
    return a-'A'+1;
}
il int dis(char a,char b)
{
    return min(abs(cg(a)-cg(b)),min(abs(cg(a)+26-cg(b)),abs(cg(b)+26-cg(a))));
}
signed main()
{
    n=read();
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        t[i][0]=dis(s[i],'A');
        t[i][1]=dis(s[i],'C');
        t[i][2]=dis(s[i],'T');
        t[i][3]=dis(s[i],'G');
        for(int j=1;j<=3;j++)
        {
            t[i][j]+=t[i-1][j-1];
        }
    }
    for(int i=4;i<=n;i++)
    {
        ans=min(ans,t[i][3]);
        //cout<<i<<' '<<t[i][3]<<endl;
    }
    cout<<ans<<endl;
}

B. Dima and a Bad XOR

题意:

给出一个n*m的矩阵,需要每行取一个数,使得总异或和不为0,有解输出TAK和每行取的数字,无解输出NIE

题解:

首先考虑无解的情况,每行的数字必须一样,然后每行取一个数字异或和为0

那么事情就好办了,如果一行有两个不同的数字,如果取其中一个异或和为0那么另一个异或和一定不为0

代码:

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 505
#define int long long
using namespace std;
il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m,a[Max][Max],flg[Max],flag,ans[Max],tp;
il void print()
{
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<' ';
    puts("");
    exit(0);
}
il void dfs(int nw,int s)
{
    if(nw==n+1)
    {
        if(s) print();
        return;
    }
    //cout<<nw<<' '<<flg[nw]<<" qwq\n";
    if(!flg[nw])
    {
        ans[++tp]=1;
        dfs(nw+1,s^a[nw][1]);
        tp--;
        return;
    }
    for(int i=1;i<=m;i++)
    {
        while(i!=1&&i<=m&&a[nw][i]==a[nw][i-1]) i++;
        if(i==m+1) break;
        ans[++tp]=i;
        dfs(nw+1,s^a[nw][i]);
        tp--;
    }
}
signed main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            a[i][j]=read();
            if(j!=1&&a[i][j]!=a[i][j-1]) flg[i]=1;
        }
        if(flg[i]) flag=1;
    }
    if(!flag)
    {
        int qwq=0;
        for(int i=1;i<=n;i++)
        {
            qwq^=a[i][1];
        }
        if(!qwq) puts("NIE"),exit(0);
    }
    puts("TAK");
    dfs(1,0);
}

C. Problem for Nazar

题意:

给出数列\{a_n=2n-1\}, \{b_n=2n\}

数列c第一次从a取一项,第二次从b取两项,第三次从a取四项,第四次从b取八项,依次类推。

前十项为1,2,4,3,5,7,9,6,8,10

给出l,r,求l~r之前的所有元素和。

题解:

先变成求前缀和,ans=s_r-s_{l-1}

通过某些数学方法算出来有多少项a和多少项b就好了。

代码:

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 1000005
#define int long long
#define Mod 1000000007
using namespace std;
il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
il ll qpw(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%Mod;
        a=a*a%Mod;
        b>>=1;
    }
    return res;
}
int l,r,inv3=qpw(3,Mod-2);
il int s1(int n)
{
    return n*n%Mod;
}
il int s2(int n)
{
    return n*(n+1)%Mod;
}
il int calc(int x)
{
    if(!x) return 0;
    int q=1,n=1;
    while((q<<1)-1<x) n++,q<<=1;
    int a=n/2,b=a;
    if(!(n&1)) b--;
    a=(qpw(4,a)-1)*inv3%Mod;
    if(n&1) a+=(x-qpw(2,n-1)+1)%Mod;
    b=2ll*(qpw(4,b)-1)%Mod*inv3%Mod;
    if(!(n&1)) b+=(x-qpw(2,n-1)+1)%Mod;
    a%=Mod,b%=Mod;
    return (s1(a)+s2(b))%Mod;
}
signed main()
{
    l=read(),r=read();
    cout<<(calc(r)-calc(l-1)+Mod)%Mod<<endl;
}

D. Stas and the Queue at the Buffet

题意:

n个人排队,每个人有两个值a_i,b_i,对于第i个人,如果在j的位置排队就会产生a_i⋅(j−1)+b_i⋅(n−j)的不满足度。最小化总的不满足度。

题解:

化式子:

a_i⋅(j−1)+b_i⋅(n−j)

=(a_i-b_i)⋅j-a_i+b_i⋅n

发现后面是一个常数,所以要最小化(a_i-b_i)⋅j

然后利用排序不等式,逆序和最小,对a_i-b_i从大到小排序就完事了。

代码:

#include <bits/stdc++.h>
#define il inline
#define ll long long
#define Max 1000005
#define int long long
using namespace std;
il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node
{
    int a,b,c;
}e[Max];
int n,ans;
il bool cmp(node x,node y)
{
    return x.c>y.c;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
        e[i].a=read(),e[i].b=read(),e[i].c=e[i].a-e[i].b;
    sort(e+1,e+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        ans+=e[i].a*(i-1)+e[i].b*(n-i);
    }
    cout<<ans<<endl;
}

后面的题目暂时不会qwq