首页 > 其他分享 >CSP-J 2023

CSP-J 2023

时间:2023-10-22 20:35:15浏览次数:31  
标签:p2 p1 cout ll long sqrt 2023 CSP

[CSP-J 2023] 小苹果

这道题由于不会算时间复杂度,大概用了 \(\frac{3}{10}\) 的时间。

思路

样例我们先手推一下:

1 2 3 4 5 6 7 8
2 3 5 6 8
3 5 8
5 8
8

我们先将每个数的位置对三取模后的数标一下(括号里的数就是位置对三取模后的数):

1(1) 2(2) 3(0) 4(1) 5(2) 6(0) 7(1) 8(2)
2(1) 3(2) 5(0) 6(1) 8(2)
3(1) 5(2) 8(0)
5(1) 8(2)
8(1)

我们观察 \(8\) 的位置对三取模后的数的规律,首先是 \(2\) 然后删掉所有位置是 \(1\) 的数,也就是 \(\left\lceil\dfrac{8}{3}\right\rceil\),所以位置 \(8\) 也就变成了 \(8 - \left\lceil\dfrac{8}{3}\right\rceil = 5\) 位置 \(5\),而原来对三取模的 \(2\) 也就变成了 \(5 \equiv2\pmod{3}\),直到位置对三取模为 \(1\) 为止,它才被删掉,那什么时候结束呢?同样的对于当前个数为 \(n\) 的,它将会被删掉 \(n - \left\lceil\dfrac{n}{3}\right\rceil\) 个数,直到删完,两个问题递归求解即可。然后考试是因为不会算时间复杂度,就一直再算(悲)。

code

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll n;

ll S(ll x) {
  if (x == 1) {
    return 1;
  }
  return S(x - ceil(1.0 * x / 3)) + 1;
}

ll C(ll x) {
  if (x % 3 == 1) {
    return 1;
  }
  return C(x - ceil(1.0 * x / 3)) + 1;
}

int main() {
  cin >> n;
  cout << S(n) << " " << C(n) << endl;
  return 0;
}

[CSP-J 2023] 公路

大概又用了 \(\frac{3}{10}\)。

思路

由于要算的是最小的油费,而且油箱有时没上限的,所以我们肯定选择在油费最小的站点买完会是最优的,但是第一个点不一定是油费最小的也就是我们还得再最优的位置之前与第一个位置内选一个最优的作为补给,可是这个最优的也不一定是在第一个位置,所以我们还得找一个……,这么做完后,便会发现整个路程分为了几个段,而每个段的第一个位置是当前段里油费最优的,那么我们便可以处理完所有的段,然后分段计费。考试时我先写了一个前缀最小值来分段,可是挂了,所以我又重新写了个双指针的写法才对,此处耗时巨大(悲)。

code

#include <bits/stdc++.h>

using namespace std;

const int MaxN = 1e5 + 10;

long long a[MaxN], c[MaxN], len, n, ans, d;

int main () {
  cin >> n >> len;
  for (int i = 1; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> c[i];
  }
  for(int i = 1; i <= n;) {
    int nw = i;
    long long sum = -d;
    for (; i <= n && c[i] >= c[nw]; i++) {
      sum += a[i];
    }
    ans += (sum + len - 1) / len * c[nw];
    d = (sum + len - 1) / len * len - sum;
  }
  cout << ans << endl;
  return 0;
}

[CSP-J 2023] 一元二次方程

最没可能 \(A\) 的一道题,却是最顺畅的一道题,耗时 \(\frac{3}{10}\) 太顺畅了,直接写了 \(101\) 行。

思路

这是到大模拟,我的想法是写一个有理数的结构体,然后自动处理掉有理数规则,然后自动约分和自动将根号最简话,然后直接模拟即可,那这个有理数结构体要处理些什么呢?它分为分子和分母,分子有个普通的计数,和一个根号的计数,然后用一个 \(flag\) 来判断有没有根号,分母就直接记下来就可以了,注意分母不能是负数!。

code

赛时代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct S {
  ll p1, p2, q;
  bool sqr;

  void I() {
    ll a = 1, b = p2;
    for (ll i = 2; i * i <= p2; i++) {
      if (p2 % i == 0 && ll(sqrt(i)) * ll(sqrt(i)) == i) {
        if (b > p2 / i) {
          b = min(p2 / i, b), a = sqrt(i);
        }
      }
      if (p2 % i == 0 && ll(sqrt(p2 / i)) * ll(sqrt(p2 / i)) == p2 / i) {
        if (b > i) {
          b = min(i, b), a = sqrt(p2 / i);
        }
      }
    }
    p2 = b, p1 *= a;
    ll d = __gcd(p1, q);
    p1 /= d, q /= d;
    if (q < 0) {
      p1 *= -1, q *= -1;
    }
  }

  void print() {
    I();
    if (q != 1) {
      if (!sqr) {
        cout << p1 << "/" << q;
      } else {
        if (p1 != 1) {
          cout << p1 << "*sqrt(" << p2 << ")/" << q;
        } else {
          cout << "sqrt(" << p2 << ")/" << q;
        }
      }
    } else {
      if (!sqr) {
        cout << p1;
      } else {
        if (p1 != 1) {
          cout << p1 << "*sqrt(" << p2 << ")";
        } else {
          cout << "sqrt(" << p2 << ")";
        }
      }
    }
  }
};

ll t, m, a, b, c;

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  for (cin >> t >> m; t; t--) {
    cin >> a >> b >> c;
    ll dt = b * b - 4 * a * c;
    if (dt < 0) {
      cout << "NO" << '\n';
    } else {
      if (ll(sqrt(dt)) * ll(sqrt(dt)) == dt) {
        S ans1 = {ll(-b + sqrt(dt)), 0, 2 * a, 0}, ans2 = {ll(-b - sqrt(dt)), 0, 2 * a, 0};
        ans1.I(), ans2.I();
        S ans3;
        if (ans1.p1 * ans2.q > ans2.p1 * ans1.q) {
          ans3 = ans1;
        } else {
          ans3 = ans2;
        }
        ans3.print();
      } else {
        S q1 = {-b, 0, 2 * a, 0}, q2 ={(2 * a > 0 ? 1 : -1), dt, 2 * a, 1};
        q1.I(), q2.I();
        if (-b != 0) {
          q1.print();
          cout << "+";
        }
        if (q2.p1 == q2.q) {
          q2.print();
        } else if (q2.p1 % q2.q == 0) {
          q2.print();
        } else if (q2.q % q2.p1 == 0) {
          q2.q = q2.q / q2.p1, q2.p1 = 1;
          q2.print();
        } else {
          q2.print();
        }
      }
      cout << '\n';
    }
  }
  return 0;
}

我如果正常写的代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct S {
  ll p1, p2, q;
  bool sqr;

  void I() {
    ll a = 1, b = p2;
    for (ll i = 2; i * i <= p2; i++) {
      (p2 % i == 0 && ll(sqrt(i)) * ll(sqrt(i)) == i) && (b > p2 / i) && (b = min(p2 / i, b), a = sqrt(i));
      (p2 % i == 0 && ll(sqrt(p2 / i)) * ll(sqrt(p2 / i)) == p2 / i) && (b > i) && (b = min(i, b), a = sqrt(p2 / i));
    }
    p2 = b, p1 *= a;
    ll d = __gcd(p1, q);
    p1 /= d, q /= d;
    (q < 0) && (p1 *= -1, q *= -1);
  }

  void print() {
    I();
    if (q != 1) {
      if (!sqr) {
        cout << p1 << "/" << q;
      } else {
        (p1 != 1) ? (cout << p1 << "*sqrt(" << p2 << ")/" << q) : (cout << "sqrt(" << p2 << ")/" << q);
      }
    } else {
      if (!sqr) {
        cout << p1;
      } else {
        (p1 != 1) ? (cout << p1 << "*sqrt(" << p2 << ")") : (cout << "sqrt(" << p2 << ")");
      }
    }
  }
};

ll t, m, a, b, c;

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  for (cin >> t >> m; t; t--) {
    cin >> a >> b >> c;
    ll dt = b * b - 4 * a * c;
    if (dt < 0) {
      cout << "NO" << '\n';
    } else {
      if (ll(sqrt(dt)) * ll(sqrt(dt)) == dt) {
        S ans1 = {ll(-b + sqrt(dt)), 0, 2 * a, 0}, ans2 = {ll(-b - sqrt(dt)), 0, 2 * a, 0};
        ans1.I(), ans2.I();
        S ans3 = (ans1.p1 * ans2.q > ans2.p1 * ans1.q ? ans1 : ans2);
        ans3.print();
      } else {
        S q1 = {-b, 0, 2 * a, 0}, q2 = {(2 * a > 0 ? 1 : -1), dt, 2 * a, 1};
        q1.I(), q2.I();
        if (-b != 0) q1.print(), cout << "+";
        (q2.q % q2.p1 == 0) && (q2.q = q2.q / q2.p1, q2.p1 = 1);
        q2.print();
      }
      cout << '\n';
    }
  }
  return 0;
}

好一只压行鸭(

[CSP-J 2023] 旅游巴士

只有 \(\frac{1}{10}\) 了,极限乱搞!

思路

没有思路,暴力乱搞 \(BFS\)

code

算了吧

预估分数 \(300\)

标签:p2,p1,cout,ll,long,sqrt,2023,CSP
From: https://www.cnblogs.com/ybtarr/p/17781038.html

相关文章

  • CSP-S 2023 题解
    CSP-S2023题解密码锁发现总状态数只有\(10^5\)个,枚举\(O(n)\)暴力判断即可,复杂度\(O(10^5n)\)。或者每一个状态只对应了\(81\)个状态,枚出来,取交集即可,复杂度\(O(81n)\)。消消乐好的,来一波抽象做法QwQ我看到这道题的第一眼:这不就是QOJ6504Flower'sLand2吗......
  • 2023 CSP-J/S 游寄
    赛前停课了两个星期,打了好几场模拟赛。(吐槽一下,说是CSP-S模拟赛,但难度和知识点早就超了提高了)。模拟赛的质量很高,学到了很多算法和小技巧。当然,每天都被爆踩。上午:CSP-J开题仍然延续老传统:顺序开题。apple很快找到了性质:逢三取一,打了一会就切了。road一开始考虑了dp......
  • CSP-S 2023 总结
    CSP-S2023总结第一次搞csp-s复赛,感觉没考好。估分150+,感觉要寄。先全部看一遍,第三题看了一眼就走了,其他题大概有一点思路,感觉大概150的样子。T1一开始读错题乱搞了30分钟才发现,然后有花了15分钟打完。T2第二题花了一小时想不到正解,就搞了个\(O(n^2)\)的水法。打完之后......
  • Pycharm 2023.2 最新po jie版安装教程(附激活码,亲测有效)
    申明:本教程Pycharmpojie补丁、激活码均收集于网络,请勿商用,仅供个人学习使用,如有侵权,请联系作者删除。若条件允许,希望大家购买正版!前言笔者分享一种比较靠谱的Pycharm pojie方案:激活脚本+激活码(全自动模式),即本文教程所写,这种方法适合最新的几个版本,具体步骤跟着本文教程一步......
  • CSP-S 2023游记
    CSP-S2023游记Day?-Day-1备考,思考了很多种的骗分算法,查看准考证。每天依然在做模拟赛,感觉对DS题的感觉不太良好。Day0比赛前一天,感觉心情不是十分紧张。上午玩了一下NOILinux,挺好玩的。下午有老选手给我们讲保龄经验,挺乐的,然后挺期待CSP的题的吧,只要不太变态就可以了(许......
  • 「CSP 2023」邮寄
    day-10086没事干来开个坑临近才想起马上CSP2023了...开始复习(得知提高\(>60\)就能二等233333,于是乎报了提高)day-48csp-j模拟赛100+0+90+10=200有点崩day-41初赛资料终于发了,还以为学校准备放弃我们了day-36这一周都在背初赛资料还要搞WHK。。。32页给我脑子背ML......
  • 吃薯片2023游记
    吐槽:开赛太热,后半场太冷,可能是第一排太靠前门导致的。啥都想不了,啥都想不了,啥都想不了,啥都想不了,啥都想不了。没有c++14属实答辩(虽然不是他的问题,但是删了=c++14忘打=c++11属实难绷)。shift+空格打不出空格真是ex。体验极差。正文:题解:T1:水题,先看数据范围,然后暴力找交集......
  • 2023-2024-1 20231405 《计算机基础与程序设计》第四周学习总结
    2023-2024-120231405《计算机基础与程序设计》第四周学习总结作业信息作业属于哪个课程https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP作业要求在哪里https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP/homework/13009作业的目标自学《计算机科......
  • 2023-2024-1 20211211 第三章学习笔记
    一、多任务处理多任务处理指的是同时进行几个独立活动的能力在单处理器(单CPU)系统中,一次只能执行一个任务。而多任务处理是通过在不同任务之间多路复用CPU的执行时间来实现的,即将CPU执行操作从一个任务切换到另一个任务。不同任务之间的执行切换机制称为上下文切换,将一个任务的......
  • 2023.10.22博客
    有一段时间没写博客了,主要原因是忘了写了,哈哈哈。这段时间把分支与循环的内容收了尾,并开启了一个全新篇章函数,我会将我的笔记贴在下面:库函数(cplusplus.com/reference/clibrary/库函数查询)常见库函数 strcpy//strcpy-stringcopy-字符串拷贝#include<stdio.h>#include<s......