2023 年第五届河南省 CCPC 大学生程序设计竞赛
Problem A. Mocha 上小班啦
思路：求n个数位的最小值，条件：每一位数字都不同切不含前导零。
只需要把0放到第二位，其他按从小到大输出，大于10以后输出-1即可。
#include <bits/stdc++.h>
using namespace std;
int main()
{
//预处理每一位的数字
int a[10]={1,0,2,3,4,5,6,7,8,9};
int n;
cin>>n;
if(n<=10)//小于10的按位输出
for(int i=0;i<n;i++)cout<<a[i];
else//大于10的输出-1
cout<<"-1";
return 0;
}
Problem E. Serval 的俳句
思路:暴力循环，先找出第一个包含5个相同字母的位置，然后找第二个包含7个相同字母的位置，最后找5个相同字母的位置，若都能找到就输出答案，若当层循环内为找到，则退出并把这一层记录的清空，否则下一次再进入这一层就会使用上一次的记录。
#include <bits/stdc++.h>
using namespace std;
//用桶记录每个字母出现的次数。
int a[26],b[26],c[26];
int main()
{
int n;
string s;
cin>>n>>s;
for(int i=0;i<n;i++)
{
a[s[i]-'a']++;
//当前字母出现过5次进入下一层循环
if(a[s[i]-'a']==5)
{
for(int j=i+1;j<n;j++)
{
//是-'a'不要写成-'0'
b[s[j]-'a']++;
//当前字母出现过7次进入下一层循环
if(b[s[j]-'a']==7)
{
for(int k=j+1;k<n;k++)
{
c[s[k]-'a']++;
//当前字母出现过5次输出结果退出循环
if(c[s[k]-'a']==5)
{
for(int t=0;t<5;t++)cout<<s[i];
for(int t=0;t<7;t++)cout<<s[j];
for(int t=0;t<5;t++)cout<<s[k];
return 0;
}
}
//退出当前循环，清空数组
memset(c,0,sizeof(c));
}
}
memset(b,0,sizeof(b));
}
}
//没找到输出"none"
cout<<"none";
return 0;
}
Problem F. 集合之和
题意：构造一个集合，使得集合内的元素和等于n；
题解：先拿顺序数组{1,2,3,4,5,6…n}尝试构造，发现只有第一行和最后一列是不充分元素,易观察到构造出集合的数量是2*n+1，涵盖所有奇数，只需再构造一个偶数数组即可，第一列和最后一行的元素包含了第一行和最后一列，可知数量为2和4的构造不出，顺序数组构造出的第一列和最后一行是按大小递增的再{2，n}之间包含了所有大小的数，可以想到若把中间抽出一个数就会有一个空缺，可以放入其他数，试构造{1，3，4，5，6…n}可以发现得到的数据量正好为偶数个。使用这两个数组可以构造出除2，4以外的所有数。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
//先排除2和4
if (n == 2 || n == 4) {
cout << "-1";
return 0;
}
int x;
if (n % 2 == 1) {//若为奇数则用{1，2，3，...，n}
x = n / 2 + 1;
cout << x << endl;
for (int i = 1; i <= x; i++)
cout << i << " ";
} else {//若为偶数则用{1，3，4，...，n}
x = n / 2;
cout << x << endl;
for (int i = 1; i <= x + 1; i++) {
if (i == 2)
continue;
cout << i << " ";
}
}
return 0;
}
Problem G. Mocha 上大班了
思路：诈骗题！如果0&1的话结果为1，只有1&1与结果为1，可知如果某一列出现了0，那么n个字符串按位与运算后必为0，只有每一个字符串同一个位置都为1最后该位置的结果才是1。
#include <bits/stdc++.h>
using namespace std;
int a[5000];
int main()
{
//先给数组都赋值为1
for(int i=0;i<5000;i++)a[i]=1;
int n,m,ans=0;
cin>>n>>m;
for(int i=0;i<n;i++)
{
string s;
cin>>s;
for(int i=0;i<m;i++)
{//如果当前字符串的当前位置出现了0，那么这一位最后与运算后必为0。
if(s[i]=='0')
a[i]=0;
}
}
int t;
cin>>t;
for(int i=0;i<5;i++)cin>>t;//输入无用的变量
for(int i=0;i<m;i++)ans+=a[i];//把最后剩下的1都加起来即为数字1的个数和
cout<<ans;
return 0;
}
Problem H.旋转水管
思路：dfs搜索，如果是I的话只有一个方向，L的话有两个方向。进入dfs的时候判断是哪个类型的水管在进行对应的判断即可，维护当前进入的方向，便于判断下一步该往哪走。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
char mp[3][N];
//不是st[N][N],会爆内存
int st[3][N];
//定义反向为下右上左
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int n, zx, zy,ti;
//x，y为当前位置，dic为当前进入的方向
void dfs(int x,int y,int dic)
{
//记录当前位置走过
st[x][y]=1;
int tx,ty;
if(mp[x][y]=='I')
{
//如果当前位置为I则下一步的方向与当前的方向一致
tx=x+dx[dic];
ty=y+dy[dic];
//管道只有两行
if(tx==1||tx==2)
{
if(ty>=1&&ty<=n&&st[tx][ty]==0)//若下一步位置没走过且不越界则继续往下走，方向不变。
{
dfs(tx,ty,dic);
st[tx][ty]=0;//回溯
}
}
if(tx==3&&ty==zy)//如果下一步的位置为出口这标记为1；
{
ti=1;
return;
}
}else
{//如果当前位置为L则下一步的方向有两种分别为(dic+1)%4或(dic+3)%4，其他思路和上面相同
tx=x+dx[(dic+1)%4];
ty=y+dy[(dic+1)%4];
if(tx==1||tx==2)
{
if(ty>=1&&ty<=n&&st[tx][ty]==0)
{
dfs(tx,ty,(dic+1)%4);
st[tx][ty]=0;
}
}
if(tx==3&&ty==zy)
{
ti=1;
return;
}
tx=x+dx[(dic+3)%4];
ty=y+dy[(dic+3)%4];
if(tx==1||tx==2)
{
if(ty>=1&&ty<=n&&st[tx][ty]==0)
{
dfs(tx,ty,(dic+3)%4);
st[tx][ty]=0;
}
}
if(tx==3&&ty==zy)
{
ti=1;
return;
}
}
return;
}
int main() {
int t;
cin>>t;
while(t--)
{
//每次循环记得把t跟新为0
ti=0;
cin>>n>>zx>>zy;
for(int i=1;i<=2;i++)
for(int j=1;j<=n;j++)
cin>>mp[i][j];//输入管道
dfs(1,zx,0);//从人口进入
st[1][zx]=0;//回溯
if(ti)//如果标记过，即为找到了出口，反之没找到
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;;
}
return 0;
}
Problem J. Mex Tree
思路：
我们用权值作为编号：（官方题解）
- k = 0，那么自然要删掉0号点，会得到若干子树，为了保证连通性，从中选择最大子树即可
- k = n，最大编号为n-1，所以选所有点即可
- 0<k<n：
首先选出的子树肯定需要包含0号点。但是去判断位置关系非常麻烦，我们可以直接以0号点作为根节点。
这个时候我们需要删除k号点，那么为了保证0号点的存在，那么我们只能连同k及其子树全部删除，这是唯一的可能合法操作，并且可以得到这个子树大小为n-sizek
那么为了进一步判断合法性，就需要知道k及其子树内，是否存在一个点i，使得i<k。（因为mex=k，那么只要所有小于k的点都不在子树内，剩下未删除的子树的mex就是k）。
这个只需要记录一下子树内的最小值即可。如果最小值就是k，就说明内部没有i<k的节点。
#include <bits/stdc++.h>
using namespace std;
// 范围再1e6！
const int N = 1e6 + 10, M = 2e6 + 10;
int e[M], h[N], ne[M], idx;
int vi[N], mn[N], sz[N], ans[N], n;
//构造连通图
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
//递归整颗树，维护每个点的子树的大小和该子树的最小权值
void dfs(int a, int b) {//a为当前点，b为上一个点
//每一点的初识长度为1
sz[a] = 1;
mn[a] = vi[a];//记录当前点的权值
for (int i = h[a]; ~i; i = ne[i]) {
int j = e[i];
if (j == b)
continue;//防止自环
dfs(j, a);//递归下一个点
sz[a] += sz[j];//计算当前子树的长度
mn[a] = min(mn[a], mn[j]);//维护当前子树的最小值
}
}
void dfs1(int a, int b) {
if (vi[a] != 0 && vi[a] != n) {
if (vi[a] == mn[a])//若a点的权值等于a子树的最小权值，另一个子树肯定包含小于a点权值的所有点即mek=k
ans[vi[a]] = n - sz[a];
else//若a点的权值不等于等于a子树的最小权值，另一个子树肯定不包含小于a点权值的所有点
ans[vi[a]] = 0;
}
for (int i = h[a]; ~i; i = ne[i]) {
int j = e[i];
if (j == b)
continue;
// 不要写成dfs()
dfs1(j, a);//进入下一个点判断
}
}
int main() {
memset(h, -1, sizeof(h));
cin >> n;
for (int i = 1; i <= n; i++)
scanf("%d", &vi[i]);
for (int i = 2; i <= n; i++) {
int j;
scanf("%d", &j);
add(i, j);
add(j, i);
}
int root = 0;
for (int i = 1; i <= n; i++)
if (vi[i] == 0) {
root = i;
break;
}
dfs(root, -1);
ans[n] = n;
// 不是i++！
for (int i = h[root]; ~i; i = ne[i]) {
int j = e[i];
ans[0] = max(ans[0], sz[j]);//找出除0点以外的最大的子树
}
dfs1(root, -1);
for (int i = 0; i <= n; i++)
cout << ans[i] << " ";
return 0;
}
标签：vi,子树,2022ccpc,int,题解,dfs,权值,include From： https://www.cnblogs.com/ckeri/p/18155870看看就好，不太会