比赛链接
A - camel Case
题目大意
给一个由英文字母构成的字符串\(S\)，\(S\)中只有一个大写字母，输出该大写字母是字符串中第几个字母。
题目思路
遍历字符串找出大写字母即可
代码实现
#include <bits/stdc++.h>
using namespace std;
int main()
{
string str;
cin>>str;
for(int i=0;str[i];i++)
{
if(str[i]>='A' && str[i]<='Z')
{
//下标从0开始,要记得+1
cout<<i+1;
return 0;
}
}
}
B - Trimmed Mean
题目大意
题目给出\(5*n\)个数字，去掉前\(n\)大的数字，然后去掉前\(n\)小的数字，求剩下的数字的平均值。
题目思路
对给出的\(5*n\)个数字排序，然后累加\([n+1,4*n]\)间的数字，然后求平均值即可。
代码实现
#include <bits/stdc++.h>
using namespace std;
int a[5000];
int main()
{
int n;
cin>>n;
for(int i=1;i<=5*n;i++) cin>>a[i];
sort(a+1,a+1+5*n);
int b = 0;
//累加
for(int i=n+1;i<=4*n;i++) b+=a[i];
//输出均值
printf("%.7lf",b*1.0/(3*n));
return 0;
}
C - LRUD Instructions 2
题目大意
给出一个由\('RLUD'\)构成的字符串，
若原坐标为\((x,y)\)：
\(R\)表示向右移动，移动后的坐标为\((x+1,y)\)
\(L\)表示向左移动，移动后的坐标为\((x-1,y)\)
\(U\)表示向右移动，移动后的坐标为\((x,y+1)\)
\(D\)表示向右移动，移动后的坐标为\((x,y-1)\)
求从起点\((0,0)\)开始，按字符串移动后是否经过重复的坐标？
题目思路
直接模拟移动的过程即可，同时用\(map\)记录下走过的坐标。
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
//标记哪些坐标经过了
map<PII,int>st;
int sx,sy;
int main()
{
int n;
string str;
cin>>n>>str;
for(int i=0;str[i];i++)
{
//判断当前的坐标是否重复经过
if(st.find({sx,sy})!=st.end())
{
puts("Yes");
return 0;
}
st[{sx,sy}]++;
//移动到下一个坐标
if(str[i]=='R') sx++;
else if(str[i]=='L') sx--;
else if(str[i]=='U') sy++;
else sy--;
}
//判断最后走到的坐标是否重复经过
if(st.find({sx,sy})!=st.end())
{
puts("Yes");
return 0;
}
puts("No");
}
D - Flip Cards
题目大意
编号为\(1\)到\(N\)的\(N\)张卡排列成一行。对于每个\(i（1≤i<N）\)，卡\(i\)和卡\(（i+1）\)彼此相邻。卡\(i\)有\(A_i\) 写在正面，\(B_i\) 写在背面。最初，所有卡片都是面朝上的。
考虑从\(N\)张卡中选择\(0\)张或更多张卡进行翻转。
在\(2^N\)种选择要翻转的卡片的方法中，找出满足情况的翻转方式的数量——当所选卡片翻转时，每对相邻卡片的正面朝上的整数都不同，最后求出的答案要对\(998244353\)取模。
题目思路
动态规划
状态表示
\(f[i][0]\)表示，不翻转第\(i\)张牌，前\(i\)张卡片不存在相邻卡片正面数字相同的情况数量。
\(f[i][1]\)表示，翻转第\(i\)张牌，前\(i\)张卡片不存在相邻卡片正面数字相同的情况数量。
状态计算
（1）不翻转第\(i\)张牌
如果第\(i-1\)张牌正面不与第\(i\)张牌正面相同，\(f[i][0] += f[i-1][0]\)
如果第\(i-1\)张牌反面不与第\(i\)张牌正面相同，\(f[i][0] += f[i-1][1]\)
（2）翻转第\(i\)张牌
如果第\(i-1\)张牌正面不与第\(i\)张牌反面相同，\(f[i][1] += f[i-1][0]\)
如果第\(i-1\)张牌反面不与第\(i\)张牌反面相同，\(f[i][1] += f[i-1][1]\)
最后的答案即为，不翻转第\(N\)张牌，前\(N\)张卡片不存在相邻卡片正面数字相同的情况数量 和 翻转第\(N\)张牌，前\(N\)张卡片不存在相邻卡片正面数字相同的情况数量。
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5+5,mod = 998244353;
ll f[N][2];
ll a[N],b[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
}
f[0][0] = 1;
for(int i=1;i<=n;i++)
{
if(a[i-1]!=a[i]) f[i][0] = (f[i][0] + f[i-1][0]) % mod;
if(b[i-1]!=a[i]) f[i][0] = (f[i][0] + f[i-1][1]) % mod;
if(a[i-1]!=b[i]) f[i][1] = (f[i][1] + f[i-1][0]) % mod;
if(b[i-1]!=b[i]) f[i][1] = (f[i][1] + f[i-1][1]) % mod;
}
ll ans = (f[n][0] + f[n][1]) % mod;
cout<<ans;
return 0;
}
E - Find Permutation
题目大意
有一个长度\(N\)的序列\(a=(A_1 ,…,A_N )\) 即\(1,...,N\)的其中一种排列。
虽然你不知道序列\(a\)，但你知道\(A_{xi}<A_{yi}\)，对于\(M\)对整数\((X_i,Y_i)\)。
序列\(a\)是否可以唯一确定？如果可能，找到序列\(a\)。
题目思路
当序列\(a\)唯一确定的时候，将序列\(a\)排序后，可以得到长度为\(N\)的严格递增序列
为什么排序后得到长度为\(N\)的严格递增序列？
如果排序后得到多个严格递增序列，那么\(1,...,N\)可以有多种方式分配到不同的序列中。
比如 \(N=5\)，\(a_1<a_2<a_5\)，\(a_3<a_4\)，
那么序列\(a\)既可以为\((1,2,3,4,5)\)，也可以为\((1,2,4,3,5)\)
为什么会存在多种分配方式呢？
最开始有\(1,...,N\)个数，如果要把它分成两个递增序列，其实就是在\(1,...,N\)的递增序列中"扣出"一个递增序列出来，剩下的也必然为一个递增序列。
"扣出"的时候只需要保证"扣出"的数字是递增的即可，也就是说，在"扣出"一个数字\(x\)之后，如果\(1,...,N\)中存在多个大于\(x\)的数\(y\)，此时是存在多种选择的情况的，并不唯一。
为什么是严格递增的序列？
如果序列不是严格递增的，那么根据鸽巢原理，必然存在着相同的数字，则此时数字种类有\(N-1\)种，显然无法是\(1...N\)的其中一种排列。
（鸽巢原理：如果有n+1个鸽子飞进了n个鸽巢中，那么必定有鸽巢中至少飞进了2只鸽子。）
将\(a\)排序后的严格递增序列实则是一个拓扑序列
设将\(a\)排序后的长度为\(N\)的严格递增序列为\(b=(b_1 ,…,b_N )\)，也就是说，\(b_1<...<b_n\)，
对于\(b_i\)来说，有\(n-i\)个比它大的数，所以，从最大的数开始遍历，遍历到\(b_i\)时，必然先遍历了\(n-i\)个数。
如果把\(b_i\)（每个\(b_i\)对应一个\(a_i\)）看做一个节点，\(n-i\)看做该节点的入度，可以发现，\(b_1<...<b_n\)实则是一个拓扑序列。
因为拓扑序必须要满足以下两点：
1，每个顶点只出现一次。
2，对于图中的任何一条边，起点必须在终点之前。
这和序列\(b\)的构造原则实则是一样的。
不满足条件的情况
如果序列不严格递增，那么就会存在多个点入度相同。
如果有多个递增序列，那么拓扑排序排序到的点数将小于\(N\)
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
//cnt[i]为ai的入度
int cnt[N];
//h[i]记录所有大于ai的数
set<int>h[N];
int ans[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
//给出 u<v
//注意！输入会给出重复的大小关系
if(h[v].find(u)==h[v].end())
{
h[v].insert(u);
cnt[u]++;
//au的入度+1
}
}
int sx = 0;
//如果i的入度为0,那么ai为最大的
for(int i=1;i<=n;i++)
{
if(!cnt[i]) sx = i;
}
//p为分配的数字,从大到小分配
//num为拓扑排序排序到的点数
int p = n,num = 0;
bool is = true;
//拓扑排序
queue<int>q;
q.push(sx);
while(q.size())
{
int t = q.front();
ans[t] = p--;
q.pop();
num++;
int tmp = 0;
for(int i:h[t])
{
cnt[i]--;
if(!cnt[i])
{
q.push(i);
tmp++;
}
}
//存在多个点入度相同
if(tmp>1) is = false;
}
if(num==n && is)
{
puts("Yes");
for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
}
else puts("No");
return 0;
}