新智认知”杯 部分题解

新智认知”杯 部分题解

传送门

A：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
typedef long long ll;
#define N 0x3f3f3f3f
using namespace std;
int main()
{int n;cin>>n;if(n>=3){cout<<"BigBoLang"<<endl;return 0;}if(n>=2){cout<<"YingHuaTang"<<endl;return 0;}if(n>=1){cout<<"XiZhiTang"<<endl;return 0;}cout<<"None"<<endl;
}

B：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#include <algorithm>
typedef long long ll;
#define N 0x3f3f3f3f
using namespace std;
map<char,int>mp;
int main()
{int t;cin>>t;for(int i=1;i<=26;i++){char c;cin>>c;mp[c]=i;}while(t--){string s,ss;cin>>s>>ss;if(s.size()>ss.size()){int flag=0;for(int i=0;i<ss.size();i++){if(mp[s[i]]<mp[ss[i]]){cout<<"<"<<endl;flag=1;break;}else if(mp[s[i]]>mp[ss[i]]){cout<<">"<<endl;flag=1;break;}}if(flag==0){cout<<">"<<endl;}}else if(s.size()==ss.size()){int flag=0;for(int i=0;i<s.size();i++){if(mp[s[i]]<mp[ss[i]]){cout<<"<"<<endl;flag=1;break;}else if(mp[s[i]]>mp[ss[i]]){cout<<">"<<endl;flag=1;break;}}if(flag==0){cout<<"="<<endl;}}else{int flag=0;for(int i=0;i<s.size();i++){if(mp[s[i]]<mp[ss[i]]){cout<<"<"<<endl;flag=1;break;}else if(mp[s[i]]>mp[ss[i]]){cout<<">"<<endl;flag=1;break;}}if(flag==0){cout<<"<"<<endl;}}}return 0;
}

D：

栈的运用 标记每个元素最后一次出现的位置 在放入这个字母之前 首先判断这个字母的字典序是否比栈顶字典序小 若小且这个栈顶元素不是最后一个 则弹出栈顶元素

#include<bits/stdc++.h>
using namespace std;
# define ll long long
map<char,int>mp,vis;
int main()
{stack<char>q;string s;cin>>s;for(int i=0;i<s.size();i++){mp[s[i]]=i;}for(int i=0;i<s.size();i++){if(vis[s[i]])continue;else{while(q.size()!=0&&p()>s[i]&&p()]>i){p()]=0;q.pop();}q.push(s[i]);vis[s[i]]=1;}}string ans;while(q.size()!=0){ans+&#p();q.pop();}for(int i=ans.size()-1;i>=0;i--){cout<<ans[i];}cout<<endl;return 0;
}

E：

一：首先最终的结果肯定是a数组最小的配对b数组最大的，

   a数组第二小的配对b数组第二大的，以此类推。。。。。。

   所以我们对两个数组分别按升序和降序排列即可得到结果的数组。

记录a输入的位置 已经 他的cp（和他匹配的数在数组b）的位置 然后进行查找  这题需要的注意的是 挑选一个序列并任意交换序列中两个元素的位置 所以是while 而不是 if 我自己想了一个比较容易理解的样例

5

1 2 3 4 5

1 3 2 4 4  你们可以手推一下哦

#include<bits/stdc++.h>
using namespace std;
struct node
{int add,cp,v;
}a[100010],b[100010];
int cmp1(node w,node e)
{return w.v<e.v;
}
int cmp2(node w,node e)
{return w.v>e.v;
}
int cmp3(node w,node e)
{return w.add<e.add;
}
int vis[100010];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i].v;a[i].add=i;}for(int i=1;i<=n;i++){cin>>b[i].v;b[i].add=i;}sort(a+1,a+n+1,cmp1);sort(b+1,b+n+1,cmp2);for(int i=1;i<=n;i++){a[i].cp=b[i].add;}sort(a+1,a+n+1,cmp3);sort(b+1,b+n+1,cmp3);int ans=0;for(int i=1;i<=n;i++){if(vis[i])continue;int root=i,g=a[i].cp;vis[g]=1;int num=0;while(g!=root){num++;vis[g]=1;g=a[g].cp;}ans+=num;}cout<<ans<<endl;return 0;
}

F：

样例中w=1时，打表发现当n=1时，an = a1 = 1/2,当n=2时，an = a2 = 3/8。

易发现（其实我是看别人的题解的 嘻嘻）a_n = k/（2^n * n!）      k = 1*3*5*....*(2n-1)

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define INF 2000000000
const LL mod = 998244353;
LL d[1000001];
LL w,n;
int main()
{cin>>w>>n;d[1]=1;for(LL i=2;i<=1000000;i++){d[i]=(d[i-1]*(2*i-1))%mod;}while(n--){LL x;cin>>x;cout<<(d[x]*w)%mod<<endl;}return 0;
}