YRC的Blog-文章

干物妹！小埋！第二弹比赛题解

Problem A（小埋与Chicken rabbit with cages）：

此题为典型的鸡兔同笼问题，原意用于照顾蒟蒻，故比较简单，模拟解方程组即可。

x+y=head

2x+4y=leg

附标程：

#include<iostream>
namespace UMR/*防抄袭命名空间*/
{
    long long a=0,b=0,x=0,y=0;
    int n;
};
using namespace std;
using namespace UMR;
int main()
{
    cin>>n;
    for(int d=1;d<=n;d++)
    {
        cin>>a>>b;
        y=(b-2*a)/2;
        x=a-y;
        cout<<x<<" "<<y<<endl;
    }
}

Problem B（小埋与哥哥的企划）：

采用深度优先搜索（DFS）算法，可以从两个角度出发：

（1）以专家为出发点，每个专家要么选择他要么不选择他，当所有专家都确定是否选择后，这代表一种备选的方案，但是这个方案是否可行，需要检查是否所有n个问题都得到解决，在搜索的过程中记录最少的专家数。

（2）以问题为出发点，每个问题都可能会有若干个专家可以解决该问题，依次尝试选择每个专家，然后继续下个问题，直到所有问题被解决。

我们考虑以第（2）个角度出发，尝试如何优化和剪枝，基本思想是：对于某个问题，如果只有一个专家能解决，则该专家是必选的，这是其中一个优化策略。对于尝试对某个问题选择专家时，如果当前已选择的专家数>=已记录的最少专家数-1，则表示即使选择该专家，其最终方案的专家数也不可能少于当前记录的最少专家数，因此不需要尝试选择该专家。

进一步的优化还可以这样做：在调用搜索函数前，检查每一位专家能解决的问题，如果该专家能解决的问题，另一位专家都能解决，则该专家不需要参与选择，即可以在数组中标志该专家为已选择（注意，虽然将他标志为已选择，但是该专家不计算在已选择专家数中），这样在递归搜索时其搜索的规模将会降低。

附标程（效率还是比较低）：

#include <cstdio>
#include <cstring>
namespace UMR/*防作弊专用命名空间*/
{
    int a[61][7],wo[61],used[61],n,w,dec[61],ans,min;
};
using namespace UMR;
using namespace std;
void dfs(int step)
{
    bool f=true;
    if (step>n)
    {
        if (min>ans)
        min=ans;
    }
    else
    if (wo[step])
    dfs(step+1);
    else
    if (ans<min)
    for (int i=1; i<=w; i++)
    if (used[i]==0)
    {
        f=true;
        for (int j=1; j<=a[i][0]; j++)
        if (a[i][j]==step)
        {
            f=false;
            break;
        }
        if (not f)
        {
            used[i]++;
            ans++;
            for (int j=1; j<=a[i][0]; j++)
            wo[a[i][j]]++;
            dfs(step+1);
            used[i]--;
            ans--;
            for (int j=1; j<=a[i][0]; j++)
            wo[a[i][j]]--;      
         }
    }
}
int main ()
{
    scanf("%d%d",&n,&w);
    memset(a,0,sizeof(a));
    memset(wo,0,sizeof(wo));
    memset(used,0,sizeof(used));
    memset(dec,0,sizeof(dec));
    for (int i=1; i<=w; i++)
    {
        scanf("%d",&a[i][0]);
        for (int j=1; j<=a[i][0]; j++)
        {
            scanf("%d",&a[i][j]);
            if (dec[a[i][j]]!=-1)
            if (dec[a[i][j]]==0)
            dec[a[i][j]]=i;
            else
            dec[a[i][j]]=-1;
        }       
    }
    ans=0; 
    for (int i=1; i<=n; i++)
    if (dec[i]!=0 && dec[i]!=-1)
    { 
        if (used[dec[i]]==0)  
        {
            ans++;
            used[dec[i]]++;
            for (int j=1; j<=a[dec[i]][0]; j++)
            wo[a[dec[i]][j]]++;
        } 
    }
    min=2147483647;
    dfs(1);
    printf("%d",min);
    return 0;
}

Problem C（小埋与TSF的密信）：

跟普通的加密解密字符一样，只不过这道题要多做一步：

统计！

根据大量的英文文章字母统计，绝大部分的文章中字母"e","E"出现得最多，因此可以在此入手。

先将输入的加密后的字符进行统计，找出出现得最多的字母，根据这个字母与"e","E"的关系，即可按照正常的思路进行解密。

附标程：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int main()
{
    char in,str[100000];
    long long a=1,max=0,ji=0;
    int zm[256]={0};
    while((in=getchar())!=EOF)
    {
        a++;
        str[a]=in;
        if(in<='Z'&&in>='A')
        {
            zm[in-65]++;
        }
        if(in>='a'&&in<='z')
        {
            zm[in-97]++;
        }
    }
    for(int t=0;t<=26;t++)
    {
        if(zm[t]>zm[max])
        {
            max=t;
        }
    }
    ji=max+65-'E';
    for(int t=2;t<=a;t++)
    {
        if(str[t]>='A'&&str[t]<='Z')
        {
            if(str[t]-ji<'A')
            {
                cout<<(char)(str[t]+26-ji);
            }
            else
            {
                if(str[t]-ji>'Z')
                {
                    cout<<(char)(str[t]-26-ji);
                }
                else
                {
                    cout<<(char)(str[t]-ji);
                }               
            }           
            continue;
        }
        if(str[t]>='a'&&str[t]<='z')
        {
            if(str[t]-ji<'a')
            {
                cout<<(char)(str[t]+26-ji);
            }
            else
            {
                if(str[t]-ji>'z')
                {
                    cout<<(char)(str[t]-26-ji);
                }
                else
                {
                    cout<<(char)(str[t]-ji);
                }   
            }
            continue;
        }
        cout<<str[t];
    }       
}

比赛详见:https://www.luogu.org/contestnew/show/7846

干物妹！小埋！第二弹 比赛题解

Problem A（小埋与Chicken rabbit with cages）：

Problem B（小埋与哥哥的企划）：

Problem C（小埋与TSF的密信）：

统计！

干物妹！小埋！第二弹比赛题解