首页 > 其他分享 >2023暑假集训 Day 1

2023暑假集训 Day 1

时间：2023-07-25 20:55:59浏览次数：36  
标签：prime std return sticks int Day 2023 集训 dp

比赛题目共2套，其中初赛题1套，复赛2题。

比赛时间: 10:50 - 12:00 a.m。

Part 0x01 过程-Process

\(8:40\,a.m.\) 做初赛题目；

\(10:40\,a.m.\) 拿到题目；

\(10:51\,a.m.\) 先写 \(\text{T2}\)，发现是初赛考过的题目，但时限变小；

\(11:20\,a.m.\) 在 \(\text{T2}\) 上花了太久，没调出来，赶紧写 \(\text{T1}\)；

\(11:35\,a.m.\) 终于把 \(\text{T1}\) 写完了，估计能过。

\(11:36\,a.m.\) 接着看 \(\text{T2}\)，突然发现理解错题目了，但是样例 \(2\) 没过……

\(12:00\,a.m.\) \(\text{T2}\) 发现了一些问题，但是样例 \(2\) 还是没过。

总分 \(= 100pts + 30pts = 130pts\)。

Part 0x02 初赛注意事项-Theory

  1. \(∨\) 代表或运算，即 ||
  2. \(∧\) 代表与运算，即 &&
  3. \(?\) 代表非运算，即 !
  4. 文件型病毒传染的主要对象是 EXE 和 COM 文件
  5. Linux下可执行文件没有后缀名
  6. 田忌赛马思想：
    • 对手必胜，就用最小的马输给对手
    • 对手必败，就用最小的马赢对手
    • 我方必胜，就用最小的马赢对手
    • 我方必败，就用最小的马输给对手

Part 0x03 复赛题目-Problem

T1 幸运质数

题链

正经做法

使用埃式筛筛出 \([1, m]\) 内的所有质数，就可以快速判断了。

My Code:

// g++ "prime.cpp" -Wall -std=c++14 -o "prime"
// ./"prime"

#include <bits/stdc++.h>

using namespace std;
 
int vis[10000001]; 

void GetPrime(int n)
{
    memset(vis, 0, sizeof(vis));
  
    vis[1] = 1;
    vis[2] = 0;
  
    for (int i = 2; i <= n; i++) 
	{
        if(vis[i] == false)
        {
            for (int j = i * i; j <= n; j += i)
            {
                vis[j] = 1;
			}
		}
        if(i * i > n)
        {
            break;
		}
    }
}

bool Check(int num)
{
    while(num > 0)
    {
        if(vis[num] == true)
        {
            return false;
        }
        num /= 10;
    }
  
    return true;
}

int main()
{
    freopen("prime.in", "r", stdin);
    freopen("prime.out", "w", stdout);

    int n, m;

    scanf("%d %d", &n, &m);
  
    GetPrime(m);

    for(int i = n; i <= m; i++)
    {
//        printf("%d:%d\n", i, vis[i]);
        if(Check(i))
        {
            printf("%d\n", i);
        }
    }
  
    return 0;
}

时间复杂度 \(O(n\,log_2\,n)\)

打表

注意到 \([1, 10^7]\) 内只有 \(78\) 个幸运素数，直接打表即可。

打表器 (gen.cpp, 暴力即可):

// g++ "gen.cpp" -Wall -std=c++14 -o "gen"
// ./"gen"

#include <bits/stdc++.h>

using namespace std;

bool IsPrime(int n)
{
    if(n == 1)
    {
        return false;
    }

    for(int i = 2; i <= sqrt(n); i++)
    {
        if(n % i == 0)
        {
            return false;
        }
    }

    return true;
}

bool Check(int num)
{
    while(num > 0)
    {
        if(IsPrime(num) != true)
        {
            return false;
        }
        num /= 10;
    }
  
    return true;
}

int main()
{
    freopen("biao.txt", "w", stdout);

    for(int i = 1; i <= 1e7; i++)
    {
//        printf("%d:%d\n", i, vis[i]);
        if(Check(i))
        {
            printf("%d, ", i);
        }
    }
  
    return 0;
}
*/

提交代码 (prime.cpp, 按表输出):

// g++ "prime.cpp" -Wall -std=c++14 -o "prime"
// ./"prime"

#include <bits/stdc++.h>

using namespace std;

const int biao[100] = {0, 2, 3, 5, 7, 23, 29, 31, 37, 53, 59, 71, 73, 79, 233, 239, 293, 311, 313, 317, 373, 379, 593, 599, 719, 733, 739, 797, 2333, 2339, 2393, 2399, 2939, 3119, 3137, 3733, 3739, 3793, 3797, 5939, 7193, 7331, 7333, 7393, 23333, 23339, 23399, 23993, 29399, 31193, 31379, 37337, 37339, 37397, 59393, 59399, 71933, 73331, 73939, 233993, 239933, 293999, 373379, 373393, 593933, 593993, 719333, 739391, 739393, 739397, 739399, 2339933, 2399333, 2939999, 3733799, 5939333, 7393913, 7393931, 7393933};

int main()
{
    freopen("prime.in", "r", stdin);
    freopen("prime.out", "w", stdout);

    int n, m;

    scanf("%d %d", &n, &m);

    for(int i = 1; i <= 78; i++)
    {
        if(biao[i] >= n && biao[i] <= m)
        {
            printf("%d\n", biao[i]);
        }
    }
  
    return 0;
}

T2 学习

题链

初赛考过这题的暴力解法；

使邻接表存储有向图，使用拓扑排序，注意不能用普通队列，应用优先队列对门槛经验值排序。

My Code:

// g++ "study.cpp" -Wall -std=c++14 -o "study"
// ./"study"

#include <bits/stdc++.h>

using namespace std;

vector <int> G[100010];
int in[100010];
int a[100010], b[100010];

int n, m, w;

struct Node
{
    int id;
    int need;
};

struct Greater
{
    bool operator ()(Node a, Node b)
    {
        return a.need > b.need;
    }
};

void Kahn()
{
    priority_queue <Node, vector<Node>, Greater> S;
 
//    queue <int> S;
    vector <int> L;
  
    for(int i = 1; i <= n; i++)
    {
        if(in[i] == 0)
        {
            S.push((Node){i, a[i]});
        }
    }
    int ans = 0;
  
    while(S.empty() == false)
    {
        int u = S.top().id;
    
        S.pop();
        L.push_back(u);
        if (a[u] > w)
        {
            break;
        }
    
        ans++;
        w = w + b[u];
    
        for(int v : G[u])
        {
            in[v]--;
        
            if(in[v] == 0)
            {
                S.push((Node){v, a[v]});
            }
        }
    }
  
    printf("%d\n", ans);
}

int main()
{
    freopen("study.in", "r", stdin);
    freopen("study.out", "w", stdout);

    scanf("%d %d %d", &n, &m, &w);

    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }

    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &b[i]);
    }
  
    for(int i = 1; i <= m; i++)
    {
        int u, v;
    
        scanf("%d %d", &u, &v);
    
        G[u].push_back(v);
        in[v]++;
    }

    Kahn();
  
    return 0;
}

时间复杂度 \(O(n+m)\)

Other

题目描述

给出 \(n\) 根长度各异的木棍，求这些木棍能否头尾相连形成一个正方形?

\(1 \leq n \leq 100\)

题解

初赛考了这题的暴力，老师说会考写一下。

类似背包的思路， 设 \(dp_{i, j, k, l}\) 为考虑第 \(i\) 根木棍，当前第一条边长度为 \(j\)，第二条边长度为 \(k\)，第三条边长度为 \(l\) 是否可行

明显有转移式：

\[dp_{i, j, k, l} = dp_{i-1, j, k, l}\,|\,dp_{i-1, j-a_i, k, l}\,|\,dp_{i-1, j, k-a_i, l}\,|\,dp_{i-1, j, k, l-a_i} \]

// g++ "sticks.cpp" -Wall -std=c++14 -o "sticks"
// ./"sticks"

#include <bits/stdc++.h>

using namespace std;

int side;
int n;
int sticks[110];
bool dp[110][110][110][110];

void DP()
{
    memset(dp, 0, sizeof(dp));

    for(int i = 1; i <= n; i++)
    {
        dp[1][sticks[i]][0][0] = true;
        dp[1][0][sticks[i]][0] = true;
        dp[1][0][0][sticks[i]] = true;
    }
  
    for(int i = 2; i <= n; i++)
    {
        for(int j = side; j >= 0; j--)
        {
            for(int k = side; k >= 0; k--)
            {
                for(int l = side; l >= 0; l--)
                {
                    dp[i][j][k][l] = dp[i-1][j][k][l];
                    if(j >= sticks[i])
                    {
                        dp[i][j][k][l] |= dp[i-1][j - sticks[i]][k][l];
                    }
                    if(k >= sticks[i])
                    {
                        dp[i][j][k][l] |= dp[i-1][j][k - sticks[i]][l];
                    }
                    if(l >= sticks[i])
                    {
                        dp[i][j][k][l] |= dp[i-1][j][k][l - sticks[i]];
                    }
                }
            }
        }
    }
}

int main() 
{
    int T;

    scanf("%d", &T);

    while (T--) 
    {
        int length = 0;

        scanf("%d", &n);

        for(int i = 1; i <= n; i++)
        {
            scanf ("%d", &sticks[i]);
            length += sticks[i];
        }

        if(length % 4 != 0)
        {
            printf("no\n");
            continue;
        }

        side = length / 4;
        sort(sticks + 1, sticks + n + 1, greater<int>());

        if(sticks[1] > side)
        {
            printf("no\n");
            continue;
        }

        DP();
    
        if(dp[n][side][side][side] == true)
        {
            printf("yes\n");
        } 
        else
        {
            printf("no\n");
        }
    }
    return 0;
}

时间复杂度 \(O(n^4)\)

Part 0x04 总结-Summary

  1. 不要死磕，不要死磕，不要死磕（重要的事情说三遍）
  2. 注意代码细节
  3. 存图应使用邻接表
  4. 当数据小的时候，可以使用 打表 解决问题

标签：prime,std,return,sticks,int,Day,2023,集训,dp
From： https://www.cnblogs.com/CareyBlog/p/17580983.html

相关文章

  • Day05-22 多态
    多态即同一方法可以根据发送对象的不同而采用多种不同的行为方式一个对象的实际类型是确定的，但可以指向对象的引用的类型有很多（父类，有关系的类）多态存在的条件有继承关系子类重写父类方法父类引用指向子类对象注意：多态是方法的多态，属性没有多态性。ins......
  • 2023 暑假集训模拟赛 Day 2
    比赛题目共2套，其中初赛题1套，复赛2题。比赛时间:\(10:50-12:00a.m\)Part0x01过程-Process\(8:40\,a.m.\)做初赛题目；\(10:40\,a.m.\)拿到题目；\(10:51\,a.m.\)先写\(\text{T2}\)，发现是初赛考过的题目，但时限变小；\(11:20\,a.m.\)在\(\text{T2}\)上花了太久，没调出来，......
  • 集训Day 2
    A题： B题： 比赛开始先整了第一题，由于题面很高级一看就是我写不出正解的样子，就先写了一个暴力，然后开始考虑如何优化，突然开窍啦~前缀和！然后瞎优化了一番，总算过了所有样例（get100points），第二题吗…………看了半天重构了3次思路，还是连样例1都爆零。然后就放弃了好一点的解法选择了......
  • 集训Day 1
    A题： B题： 刚开始看了眼T1觉得简单，就敲了一个暴力（get65）过了所有样例后就直奔T2，T2是拓扑排序的板子，但由于数据就只写了n^2算法(get100)又过了所有样例，信心暴涨（当时想着能AK）但T1由于没写筛法，卒。giao~t1其实很简单就是一个筛法模板（但我居然没看出来！）埃氏筛、欧拉筛均可（当然由......
  • 暑假集训D2 2023.7.25 补题
    D.P1796汤姆斯的天堂梦这道题目非常ex，赛时死活调不出来，思路是对的,容易发现是一个DAG,所以直接DP就好,虽然后面看题解AC了，发现是重边的问题。但还是来记录一下这道ex的题目，警醒一下自己切记注意重边！！如下两份代码，一份爆0，一份AC#include<stdio.h>#include<stdlib.h>#include<s......
  • day119 - spring-获取bean
    获取bean根据id获取上一篇的入门文章讲解的就是根据id获取bean的方式根据类型获取@TestpublicvoidtestIOC(){//获取ioc容器ApplicationContextioc=newClassPathXmlApplicationContext("spring-ioc.xml");//获取beanStudentstudent=ioc.getBean......
  • [省选联考2023] 填数游戏
    [省选联考2023]填数游戏题目描述众所周知，Alice和Bob是一对好朋友。今天，他们约好一起玩游戏。一开始，他们各自有一张空白的纸条。接下来，他们会在纸条上依次写\(n\)个\([1,m]\)范围内的正整数。等Alice写完，Bob在看到Alice写的纸条之后开始写他的纸条。Alice需要保......
  • 2023年7月25日，File类,IO流
    File类1.概述File，是文件和目录路径的抽象表示File只关注文件本身的信息，而不能操作文件里的内容。如果需要读取或写入文件内容，必须使用IO流来完成。在Java中，java.io.File类用于表示文件或目录的抽象路径名。它提供了一组方法，可以用于创建、访问、重命名、删除文件或目录，以及获取......
  • day13
    一、[第五空间2021]alpha101.foremost分离，得到png和jpg,两张图片一样，猜测是盲水印隐写，得到一张类似于flag的图片pythonbwmforpy3.pydecode1.jpg2.pngresult.png2.颜色异或转换一下，得到flag二、messy_traffic1.打开流量过滤HTTP流，发现了文件上传，直接导出HTTP对象文......
  • 学习生理基础 | 记忆的四个环节2——保持 | 2023年7月25日
    小虾米原创作品，转载请注明出处：https://www.cnblogs.com/shrimp-can/p/17580595.html我们都想高效学习，但如何实现呢？网络上充斥着各种记忆、学习的技巧，能给予我们很大的帮助。但我始终认为，要做好一件事，须得“顺势而为”。那对于学习，什么是这个“势”呢？我认为便是人学习的生理和心......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99