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

蒟蒻我可能考了一场假试

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)

上一篇:Some Simple Models of Neurons


下一篇:PHP 文件上传功能