首页 > 编程语言 >【题解】2023传智杯全国大学生程序设计竞赛-初赛第一场

【题解】2023传智杯全国大学生程序设计竞赛-初赛第一场

时间:2024-10-10 14:00:11浏览次数:8  
标签:传智杯 num int 题解 ans 初赛 ++ edge 染色

A.字符串拼接

直接拼接两个字符串即可,注意的是字符串可能包含空格,因此需要使用getline函数进行输入。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    cout << s1 + s2 << endl;
    return 0;
}

B.差值

注意到,题目需要求出任意两个数的差值的最小值,我们知道,差值最小的情况就是两个数越接近越好,因此我们可以将数组排序,然后求相邻两个数的差值的最小值即可。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int ans = INT_MAX;
    for (int i = 1; i < n; i++) {
        ans = min(ans, a[i] - a[i - 1]);
    }
    cout << ans << endl;
}

C.红色和紫色

可以证明:当且仅当 \(n,m\) 都是奇数时,小红可以获胜。否则一定是紫获胜。

证明如下:

如果 \(n\) 和 \(m\) 都是奇数,那么 \(n*m\) 是奇数,存在一个中心的方格。小红只需要第一步给中间染色,之后紫在任意地方染色,小红只需要在紫染色的方格中心对称的位置染上和紫上次操作相同的颜色即可。这样一定是紫最先无法行动。

如果 \(n\) 和 \(m\) 不全是奇数,说明不存在中心的方格。紫只需要在每次小红染色后,在中心对称的位置上染上和小红上次操作不同的颜色(显然,这样一定是合法的)。如此最后不能操作的一定是小红。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    if (n % 2 == 1 && m % 2 == 1) {
        cout << "akai" << endl;
    } else {
        cout << "yukari" << endl;
    }
    return 0;
}

D.abb

对于每个字符 \(c\),可以先利用后缀和统计出在该字符后有多少个与 \(c\) 不同的字符,那么对于每种不同的字符,\(c\) 能够就从他们中任意选取2个构成一个合法的abb串,那么答案就是 \(C_n^2\),其中 \(n\) 表示该种字符在 \(c\) 后出现的个数,因此当前位置能够构成的答案数量就是 \(\sum C_{n_i}^2\),也就是不同于 \(c\) 的所有字符可以提供的贡献之和。最后枚举每个位置即可得到答案。

#include<bits/stdc++.h>
using namespace std;
// sum(i,j)表示在i位置后j字符的个数
long long sum[101010][26];
int main(){
    int n,i,j;
    string s;
    cin>>n>>s;
    for(i=n-1;i>=0;i--){
        for(j=0;j<26;j++)sum[i][j]=sum[i+1][j];
        sum[i][s[i]-'a']++;
    }
    long long res=0;
    for(i=0;i<n;i++){
        for(j=0;j<26;j++){
            // 对于当前位置,枚举每个不等于当前位置的字符,计算能够构成的abb串数量
            if(j!=s[i]-'a'){
                // C_n^2 = n*(n-1)/2
                res+=sum[i+1][j]*(sum[i+1][j]-1)/2;
            }
        }
    }
    cout<<res;
}

E.kotori和素因子

观察到数据范围很小,因此暴力枚举所有方案即可。

#include<stdio.h>
#define N 1010
int prime[168] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
bool st[168];        //第几个素数被用过了
int f[10][100];        //第i个数的质因子有第几个素数
int n,cnt[10];        //第i个数有几个质因子

int ans = 0x3f3f3f3f;
void dfs(int num, int sum)
{
    if(num == n){
        if(sum < ans)  ans = sum;
        return;
    }else{
        for(int i = 0; i < cnt[num]; i ++)
        {
            if(!st[f[num][i]]){
                st[f[num][i]] = true;
                dfs(num + 1, sum + prime[f[num][i]]);
                st[f[num][i]] = false;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n; i ++)
    {
        int a;
        scanf("%d",&a);
        for(int j = 0; a != 1; j ++)
        {
            if(a % prime[j] == 0)
            {
                f[i][cnt[i]++] = j;        //质因子有第几个素数
                while(a % prime[j] == 0)
                    a /= prime[j];
            }
        }
    }
    dfs(0,0);
    if(ans == 0x3f3f3f3f)  ans = -1;
    printf("%d",ans);
    return 0;
}

F. 红和蓝

对于叶子节点来说,他的周围只有一个点,即为他的父节点,因此为了满足条件,他必须要和父亲节点同色,此时,我们将他和他的父亲染上相同的颜色。染色后,我们可以看成被染色的点已经从树上去掉,因此此时会出现新的"叶子节点",重复上述过程,直到所有点都被染色即可,同时,如果染色中间出现了冲突(即一个节点同时被染上两种颜色),则说明无解,同时,如果最后没有点能帮助根节点染色,也无解。最后根据染色情况,计算答案即可。

#include <bits/stdc++.h>
using namespace std;
int n, tot = 0;
int head[100010];
struct ty
{
    int t, next;
}edge[200010];
int f[100010];
int col[100010];
int cnt = 0;
bool boo = 1;
void addedge(int x, int y)
{
    edge[++tot].t = y;
    edge[tot].next = head[x];
    head[x] = tot;
}
void dfs1(int x, int fa)
{
    int son  = 0;
    for (int i = head[x]; i != -1; i= edge[i].next)
    {
        if (edge[i].t == fa) continue;
        son++;
        dfs1(edge[i].t, x);
    }
    // 如果是叶子节点
    if (son == 0 || f[x] == 0)
    {
        // 如果他的父亲已经被染上颜色,而此时当前节点又要给父亲节点染色,说明发生冲突,无解
        if (f[fa] != 0) {boo = 0; return ;}
        // 将他和他的父亲染上相同颜色
        f[x] = f[fa] = ++cnt;
    }
}
void dfs2(int x, int fa) //计算答案
{
    for (int i = head[x]; i != -1; i= edge[i].next)
    {
        if (edge[i].t == fa) continue;
        if (f[edge[i].t] == f[x]) col[edge[i].t] = col[x];
        else col[edge[i].t] = col[x] ^ 1;
        dfs2(edge[i].t, x);
    }
}
int main()
{
    memset(head, -1, sizeof(head));
    memset(edge, -1, sizeof(edge));
    scanf("%d", &n);
    for (int i =1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    dfs1(1, 0);
    // 如果之前染色发生冲突或者根节点没有被染色,无解
    if (f[0] != 0  || boo == 0)
    {
        printf("-1\n"); return 0;
    }
    col[1] = 1;
    dfs2(1, 0);
    for (int i = 1; i <= n;i++)
    {
        if (col[i] == 1) printf("R");
        else printf("B");
    }
    return 0;
}

标签:传智杯,num,int,题解,ans,初赛,++,edge,染色
From: https://www.cnblogs.com/orangecodelog/p/18456203

相关文章

  • 传智杯 第六届—C
    题目描述:        输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如:第一个字符串是"Theyarestudents.",第二个字符串是”aeiou"。删除之后的第一个字符串变成"Thyrstdnts."。保证两个字符串的长度均不超过100。输入描述:        输入两行......
  • 传智杯 第六届—B
    题目:        擂台赛要开始了,现在有n名战士,其中第i 名战士的战斗力为ai​。现在准备从这些战士中挑两名战士进入擂台赛进行对战,由于观众们更喜欢看势均力敌的比赛,所以我们也要挑选两个战斗力尽可能相近的战士进行参赛。那么现在请问,战斗力最接近的两名战士,战斗力......
  • SNOI 2020 排列 题解
    https://www.luogu.com.cn/problem/P6795我一直很注重思考过程。这是做题的根本。初看T3,一个比较显然的贪心思路是,向外扩张合并连续段。由此清晰地发现,从1到N,被左边的数切分成若干“剩余”连续段,连续段内部,在右边的排列一定是连续的,右边的答案实际上已经确定。并且这些连......
  • 题解:CF1007D Ants
    题目传送门每只蚂蚁只走一对点肯定是不劣的,由此想到2-sat。限制条件是:若\((a,b)\)和\((c,d)\)两条链相交,则不能同时选。直接建图肯定是爆炸的。用树剖可以将\((a,b)\)这条链划分成\(O(\logn)\)个区间。因为同一条链的区间不交,限制条件变为若两个区间相交,则这两个点不......
  • BUUCTF_MISC题解析(6,8)
    6.乌镇峰会种图把打开的图片放进010editor,拉到最末尾就可以发现flag 8.N种方法解决打开文件是KEY.exe点击打不开,运行不了(exe文件是二进制文件),所以把他拉到010editor打开,data:image/jpg;base64,iVBORw0KGgo......gg==发现是base编码的形式,开头的提示说明是jpg格式的图片,......
  • P6309 题解
    很经典但是很好的题目。/qiang标签:线段树。数轴上有一些关键点,不同的关键点可能在同一坐标。关键点的坐标均为整数。支持两种操作:删去/添加一些关键点。取一个点。使得它与\([l,r]\)范围内所有关键点的距离最小。求最小距离。\(\text{关键点的坐标数}\le3\times......
  • 深度学习No module named ‘torchvision.transforms.functional_tensor‘问题解决
    问题在进行深度学习训练过程中出现ModuleNotFoundError:Nomodulenamed'torchvision.transforms.functional_tensor'报错,多方查阅资料后得到了解决方案。关于我的环境:CUDA==12.1torch==2.4.1GPU==4090D原先进行深度学习用的CUDA11.3,torch1.2.1,但是在训练时出现nvrtc......
  • AGC005 题解
    目录A-STringB-MinimumSumC-TreeRestoringA-STring用栈模拟一下即可,具体的,当栈顶出现形如ST时,将其弹出。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;llRead(){ intsig=1; llnum=0; charc=getchar(); while(!isdigit(c))......
  • 2024年江西省职业院校技能大赛高职组“数据库运行与管理“竞赛样题解析答案
    2024年江西省职业院校技能大赛高职组"数据库运行与管理"竞赛样题解析答案文章目录2024年江西省职业院校技能大赛高职组"数据库运行与管理"竞赛样题解析答案模块A:数据库理论模块B:数据库设计与运维`任务一参考答案:``任务二参考答案:`模块C:数据库查询与分析`模块C参考答案:`......
  • [NOIP2006 提高组] 作业调度方案 题解
    题目描述我们现在要利用 m 台机器加工 n 个工件,每个工件都有 m 道工序,每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。每个工件的每个工序称为一个操作,我们用记号 j-k 表示一个操作,其中 j 为 1 到 n 中的某个数字,为工件号;k 为 ......