NOIP2023 国庆集训 A 组 Day7

A. 字母还原(restore)

水题，由于第一种加密方式最容易得出字符串s，所以我们枚举三个串，哪一个可能是s经过第一种加密得来的.然后再枚举k进行验证剩下两个串即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10100;
string s[3];
char a[]="abcdefghijklmnopqrstuvwxyz",c[N];
inline ll read() 
{
    ll x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c) && c != &#039;-&#039;) c = getchar();
    if (c == &#039;-&#039;)
        f = -1, c = getchar();
    while (isdigit(c)) x = x * 10 + c - &#039;0&#039;, c = getchar();
    return f * x;
}
int check(char x[],string y,int z,int o)
{
    for(int i=0;i<z;i++)
    {
        if(a[(y[i]-&#039;a&#039;+o+26)%26]!=x[i])
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    freopen("restore.in", "r", stdin);
    freopen("restore.out", "w", stdout);
    int n=read();
    cin>>s[0]>>s[1]>>s[2];
    for(int i=0;i<3;i++)
    {
        c[n]=&#039;\0&#039;;
        for(int j=0;j<n;j++)
        {
            c[j]=s[i][n-1-j];
        }
        for(int j=0;j<3;j++)
        {
            if(j!=i)
            {
                for(int k=0;k<=6;k++)
                {
                    if(check(c,s[j],n,k))
                    {
                        for(int l=0;l<3;l++)
                        {
                            if(l!=i&&l!=j)
                            {
                                if(check(c,s[l],n,-k))
                                {
                                    cout<<c<<endl;
                                    return 0;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}

B. 棋盘染色（board）

暴力模拟三十分

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
const int N1=100100;
ll ans;
int a[N][N1];
inline ll read() 
{
    ll x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c) && c != &#039;-&#039;) c = getchar();
    if (c == &#039;-&#039;)
        f = -1, c = getchar();
    while (isdigit(c)) x = x * 10 + c - &#039;0&#039;, c = getchar();
    return f * x;
}
int main()
{
    freopen("board.in","r",stdin);
    freopen("board.out","w",stdout);
    int n=read(),m=read(),q=read();
    while(q--)
    {
        int x=read(),y=read(),z=read();
        if(x==0)
        {
            if(z==0)
            {
                for(int i=1;i<=m;i++)
                {
                    a[i][y]=0;
                }
            }
            if(z==1)
            {
                for(int i=1;i<=m;i++)
                {
                    a[i][y]=1;
                }
            }
        }
        if(x==1)
        {
            if(z==0)
            {
                for(int i=1;i<=n;i++)
                {
                    a[y][i]=0;
                }
            }
            if(z==1)
            {
                for(int i=1;i<=n;i++)
                {
                    a[y][i]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j])
            {
                ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

C. 为你写串（string）

水题，易得一个 a 到达末尾的步数为该字符到末尾之间 b 的个数。可以发现每个 a 在操作过程中相对位置不会改变，所以必须等后一个 a 到达末端，该 a 才能到最后。那么每个 a 到达末尾的步数事实上已经固定了，为了方便，我们倒序将 a 移动至末尾，并记录移动后 b 的数量即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000100;
const ll mod = 1000000007;
ll a[N];
ll ans = 0;
char s[N];
inline ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c) && c != &#039;-&#039;) c = getchar();
    if (c == &#039;-&#039;)
        f = -1, c = getchar();
    while (isdigit(c)) x = x * 10 + c - &#039;0&#039;, c = getchar();
    return f * x;
}
int main() {
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);
    scanf("%s", s);
    int n = strlen(s), m = 0, o = 0;
    s[n] = &#039;a&#039;;
    for (int i = n - 1, j = n; i >= 0; --i) {
        if (s[i] == &#039;a&#039;) {
            a[++m] = j - i - 1;
            j = i;
        }
    }
    for (int i = 1; i <= m; ++i) {
        ans = (ans + a[i]) % mod;
        a[i + 1] = (a[i] * 2 + a[i + 1]) % mod;
    }
    cout << ans << endl;
    return 0;
}

D. 货物分组（package）

无优化DP30分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+100;
int a[N],dp[N],sum[N];
inline ll read() 
{
    ll x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c) && c != &#039;-&#039;) c = getchar();
    if (c == &#039;-&#039;)
        f = -1, c = getchar();
    while (isdigit(c)) x = x * 10 + c - &#039;0&#039;, c = getchar();
    return f * x;
}
int main()
{
    freopen("package.in", "r", stdin);
    freopen("package.out", "w", stdout);
    memset(dp,0x3f,sizeof(dp));
    int n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+a[i];
    }
    dp[0]=sum[n];
    for(int i=1;i<=n;i++)
    {
        int cnt=0,maxx=0,minn=INT_MAX;
        for(int j=i;j>=1;j--)
        {
            cnt+=a[j];
            maxx=max(maxx,a[j]);
            minn=min(minn,a[j]);
            if(cnt>m) 
            {
                break;
            }
            dp[i]=min(dp[i],dp[j-1]+maxx-minn);
        }
        dp[i]+=sum[n]-sum[i];
    }
    printf("%lld",dp[n]);
    return 0;
}

今天260