23.3.4打卡 AtCoder Beginner Contest 291（Sponsored by TOYOTA SYSTEMS）A~E

F题题面都看不懂嘞!开摆!
没找到合适的markdown, 截图网页翻译了我真是天才
比赛链接:
https://atcoder.jp/contests/abc291

A题

题意

给出一个字符串, 找到第一个大写字母的下标

简单题就不多说了, 直接放代码

代码

void solve()
{cin>>str;n=str.size();str=" "+str;rep(i,1,n){if(str[i]<='Z'){cout<<i<<endl;return;}}return;
}

B题

题意

给出n*5个裁判, 去掉n个最高分和n个最低分, 剩下的全加起来求平均数, 精度要求$10^{-5}$
网页翻译发癫说此网站不支持翻译麻了没图了

题解

我用优先队列pop了n次然后读取了前3*n个

代码

void solve()
{cin>>n;priority_queue<ll>q;   rep(i,1,n*5){R ant;q.push(ant);}rep(i,1,n) q.pop();cnt=n*3;ans=0;rep(i,1,cnt){ans+=q.top();q.pop();}double a=1.0*ans/cnt;printf("%.10lf\n",a);return;
}

C题

题意

给出一个字符串只包含UDLR模拟前后左右, 从0,0开始走, 问是否会走之前走过的点

题解

用map储存pair类型查重即可

代码

void solve()
{cin>>n>>str;str=" "+str;ll x,y;x=y=0;map<pair<ll,ll>,ll>mp;mp[{0,0}]++;rep(i,1,n){auto v=str[i];if(v=='R') x++;if(v=='L') x--;if(v=='U') y++;if(v=='D') y--;if(mp.count({x,y})){yesreturn;}mp[{x,y}]++;}noreturn;
}

D题

题面

有N张卡片排成一排, 正反面各有一个数字, 初始卡牌全部为正面, 卡牌可以随意翻面, 问有多少种方式使得在正面的卡牌数字不同

题解

组合数学想了贼久, 然后发现其实是个dp
需要考虑四种情况

与上一个同面元素是否相同
与上一个异面元素是否相同

如果是相同的情况, 那么当前这个卡牌必须翻面(也就是无法转移状态)
然后其他情况都能专题状态, 写个2维dp就好了

代码

void solve()
{cin>>n;vector<ll>a(n+1),b(n+1);rep(i,1,n) R a[i]>>b[i];f[1][0]=f[1][1]=1;rep(i,2,n){if(a[i]!=a[i-1]) f[i][0]=(f[i-1][0]+f[i][0])%mod; if(a[i]!=b[i-1]) f[i][0]=(f[i-1][1]+f[i][0])%mod; if(b[i]!=b[i-1]) f[i][1]=(f[i-1][1]+f[i][1])%mod; if(b[i]!=a[i-1]) f[i][1]=(f[i-1][0]+f[i][1])%mod; }cout<<(f[n][0]+f[n][1])%mod<<endl;return;
}

E题

题意

现在有一个打乱顺序的排列A, 1~n, 给出m个x和y
x和y的含义是$A_{Xi}<A_{Yi}$
按1~n的顺序输出 原本排列在A排列中的位置

题解

按照样例1画个图先

是不是很像一个图, xy就是y通向x有向边
如此建一个图
存下每个边的终点, 找出图的起点
如果没有终点的点>=2说明这个图不合法直接输出no完事
然后遍历一遍图, 记录下顺序就好了, 注意重边感谢样例3的重边提醒我, 不然铁wa

代码

void solve()
{cin>>n>>m;rep(i,1,m){ll x,y;cin>>x>>y;g[x].push_back(y);to[y]++;}queue<ll>q;vector<ll>ans(n+1);rep(i,1,n)if(to[i]==0) q.push(i);ll pos=0;while(q.size()){if(q.size()>=2) {noreturn;}ll tp=q.front();q.pop();ans[tp]=++pos;for(auto it:g[tp]){to[it]--;if(to[it]==0) q.push(it);}}yesrep(i,1,n) cout<<ans[i]<<' ';return;
}