nowcoder(牛客网)普及组模拟赛第一场 解题报告

时间:2022-06-11 00:19:39

蒟蒻我可能考了一场假试

T1 绩点

这题没什么好说的,应该是只要会语言的就会做。

T2 巨大的棋盘

一个模拟题吧qwq,但是要注意取模的时候先加上n或者m再取模,要不然会错的。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 100010
using namespace std;
int n,m,t,q;
string s;
long long x[MAXN],y[MAXN],up,down,le,ri;
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    cin>>s;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='U') up++;
        else if(s[i]=='D') down++;
        else if(s[i]=='L') le++;
        else ri++;
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
       scanf("%lld%lld",&x[i],&y[i]);
    up*=t;
    down*=t;
    le*=t;
    ri*=t;
    //printf("up=%d\ndown=%d\nleft=%d\nright=%d\n",up,down,le,ri);
    for(int i=1;i<=q;i++)
    {
        long long ansx=x[i]+down-up;
        while(ansx<=0) ansx+=n;
        ansx=ansx%n;
        if(ansx==0) ansx=n;
        long long ansy=y[i]+ri-le;
        while(ansy<=0) ansy+=m;
        ansy=ansy%m;
        if(ansy==0)  ansy=m;
        printf("%lld %lld\n",ansx,ansy);
    }
     
    return 0;
 }

T3 括号

这个题是我考试的时候真的不会写qwq,猜测是组合计数问题??然而WA掉了,连样例都过不去qwq。
之后就开始想DP,但是看看数据范围,感觉会MLE??还是不会做啊qwq
不会写正解,就也不想写暴力部分分了qwq,最后弃掉了这个题。
考完试了之后看了dalao的代码恍然大悟,原来可以优化掉数组的第一维。。。。。。。
代码和注释如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define mod 1000000007
using namespace std;
long long dp[10010];
//我们设dp[i][j]表示到第i个括号的时候有j个左括号没有匹配上的方案数,然后这里优化掉第一维,只保留第二维
char ch[10010];
int n;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        cin>>ch[i];
    dp[0]=1;
        //DP初始化,都匹配上的话自然是存在一种情况的
    for(int i=0;i<n;i++)
    {
        if(ch[i]=='(')
            for(int j=n-i-1;j>=0;j--)
               dp[j+1]=(dp[j]+dp[j+1])%mod;
                //如果是左括号的话,自然是又多一种无法匹配到的状态,因为我们表示的是有j个左括号没有匹配到的方案数,所以+1并且后面的由前面转移过来
                //而因为已经匹配到i了,所以.....j到n-i就可以了
        else
            for(int j=1;j<=n-i;j++)
               dp[j-1]=(dp[j]+dp[j-1])%mod;
                //原理同上
    }
    printf("%lld\n",(dp[0]-1)%mod);
        //这里的减一是因为所有括号都被删除的情况不符合题目要求,所以方案数--
    return 0;
}

T4 配对

官方题解是这样说的:qwq

  • 直接枚举选择哪些字母配对很慢,可以考虑枚举联通块。当K>7时,显然所有串都能 相同了,因为只需要7条边就能让所有字母等价。
  • 因此考虑枚举字母的联通块情况。而贪心地想,K肯定用完最好,因此联通块情况就只 有S(8,8-K)种情况,其中S为第二类斯特林数。
  • N=8时的斯特林数,0 1 127 966 1701 1050 266 28 1
  • 实际可以跑一个爆搜看看要遍历多少个状态
  • 枚举完联通块情况后,每个字符串中,每种字符替代为对应联通块编号,变成等价的 字符串。
  • 然后计算哈希排序算等价对数。但这样可能超时。算一次哈希的复杂度为O(L)。可以 按字母分别维护每个字母出现位置的哈希值,重新算时复杂度是O(Σ),而不是O(L)的。
    nowcoder(牛客网)普及组模拟赛第一场 解题报告
    nowcoder(牛客网)普及组模拟赛第一场 解题报告
    qwq然鹅我并不会做这种解法的!
    所以。。。我们可以尝试。。。并查集!!
    我们首先可以知道,因为最后就只有小写字母的前8个,所以我们考虑联通块情况,最多只需要7次转换,所有字串就一定可能相同。
    然后如果小于7次......我们可以先预处理出同位字符与其对应字符对应的最大数(啊啊啊,语文掉线了qwq不知道怎么表述啊qwq),就是比如同位(同一列)a对应的有两个b,一个c。。。我们先把个数存下来,然后之后转换的时候肯定选取较大的那个转换(a转换成b而不是c)(emmmm。。。如果这个不理解的话,可以把我代码里的注释去掉看一下就明白了qwq)
    然后就是init(),我们把每个字母的每次转换都进行连边操作,将他们的sum值记录成边权值。
    之后因为转换存在传递性,我们就执行并查集合并操作,因为肯定是每次转换尽可能让更多的同位字母相等,所以我们可以先将边权从大到小排序,然后每次选大的那个连起来,之后合并qwq(这样肯定是最优的),注意如果连的边达到k个要及时跳出。
    之后呢就是最后的统计ans,我们将每个字串和其匹配字串都枚举一边,然后逐个判断是否合法。。。。感觉时间复杂度还是有点高的qwq但是可能是因为及时return+评测机快qwq跑的还是很快的qwq。。。。。。
    代码如下:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 110
using namespace std;
int n,l,k,edge_number,cnt,ans;
int sum[10][10],fa[10],done[MAXN][MAXN];
char s[MAXN][1100];
struct Edge{int x,y,len;}edge[MAXN];
bool cmp(struct Edge x,struct Edge y){return x.len>y.len;}
inline void init()
{
    for(int i=0;i<8;i++)
        for(int j=i+1;j<8;j++)
        {
            edge[++edge_number].x=i;
            edge[edge_number].y=j;
            edge[edge_number].len=sum[i][j];
        }
}
inline int find(int x)
{
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}
inline bool check(int x,int y)
{
    for(int i=0;i<l;i++)
        if(find(s[x][i]-'a')!=find(s[y][i]-'a')) return false;
    return true;
}
int main()
{
    scanf("%d%d%d",&n,&l,&k);
    for(int i=1;i<=n;i++)
        scanf("%s",&s[i]);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            for(int q=0;q<l;q++)
                if(s[i][q]!=s[j][q])
                    sum[s[i][q]-'a'][s[j][q]-'a']++,sum[s[j][q]-'a'][s[i][q]-'a']++;
    /*for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
           cout<<sum[i][j]<<" ";
        cout<<endl;
    }*/
    init();
    for(int i=0;i<8;i++)  fa[i]=i;
    sort(edge+1,edge+1+edge_number,cmp);
    for(int i=1;i<=edge_number;i++)
    {
        int a=find(edge[i].x);
        int b=find(edge[i].y);
        if(a!=b)
            fa[a]=b,cnt++;
        if(cnt==k)   break;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(done[i][j]||done[j][i]) continue;
            if(check(i,j))
            {
                ans++;
                done[i][j]=1;
                done[j][i]=1;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

(话说nowcoder的评测真的快qwq)