• Codeforces Round 895 (Div. 3)


    A.Two Vessels

    AC代码:

    1. #include
    2. #include
    3. #include
    4. #include
    5. #define endl '\n'
    6. #define int long long
    7. using namespace std;
    8. typedef long long ll;
    9. int a,b,c;
    10. void solve() {
    11. cin>>a>>b>>c;
    12. int diff=abs(a-b);
    13. if(diff==0){
    14. cout<<0<
    15. return;
    16. }
    17. if(diff<=c*2) {
    18. cout<<1<
    19. return;
    20. }
    21. cout<2)+(diff%(c*2)!=0)<
    22. }
    23. signed main() {
    24. ios::sync_with_stdio(false);
    25. cin.tie(0);
    26. cout.tie(0);
    27. int t=1;
    28. cin>>t;
    29. while(t--) {
    30. solve();
    31. }
    32. return 0;
    33. }

    B.The Corridor or There and Back Again

    二分

    AC代码:

    1. #include
    2. #include
    3. #include
    4. #include
    5. #define endl '\n'
    6. //#define int long long
    7. using namespace std;
    8. typedef long long ll;
    9. const int N=110;
    10. int d[N],s[N];
    11. int n;
    12. bool check(int x){
    13. for(int i=n;i>=1;i--){
    14. if(2*(x-d[i])>=s[i]) return false;
    15. }
    16. return true;
    17. }
    18. void solve() {
    19. cin>>n;
    20. for(int i=1;i<=n;i++) cin>>d[i]>>s[i];
    21. int l=1,r=1000;
    22. while(l
    23. int mid=(l+r+1)/2;
    24. // cout<
    25. if(check(mid)) l=mid;
    26. else r=mid-1;
    27. }
    28. cout<
    29. }
    30. int main() {
    31. ios::sync_with_stdio(false);
    32. cin.tie(0);
    33. cout.tie(0);
    34. int t=1;
    35. cin>>t;
    36. while(t--) {
    37. solve();
    38. }
    39. return 0;
    40. }

    C.http://Non-coprime Split

    素数分解成两个数的和,这两个数的最大公约数一定是1

    如果两者有公约数,那么该也有不为1的约数,就不是素数了

    AC代码:

    1. #include
    2. #include
    3. #include
    4. #include
    5. #define endl '\n'
    6. //#define int long long
    7. using namespace std;
    8. typedef long long ll;
    9. const int N=1e7+10;
    10. int prime[N];
    11. int vis[N];
    12. bool st[N];
    13. int cnt;
    14. //欧拉筛
    15. void get_prime(int n){
    16. for(int i=2;i<=n;i++){
    17. if(!st[i]) prime[cnt++]=i;
    18. for(int j=0;prime[j]<=n/i;j++){
    19. st[prime[j]*i]=true;
    20. if(i%prime[j]==0) break;
    21. }
    22. }
    23. }
    24. void solve() {
    25. int l,r;
    26. cin>>l>>r;
    27. //如果有偶数(除了2)的话
    28. if(r-l>=1){
    29. for(int i=l;i<=r;i++){
    30. if(i%2==0&&i!=2){
    31. cout<<2<<' '<-2<
    32. return;
    33. }
    34. }
    35. }
    36. //其它的情况都是只有一个数,判断一个数即可
    37. if(l==r){
    38. // //如果是素数,直接输出-1
    39. // if(vis[l]){
    40. // cout<<-1<
    41. // return;
    42. // }
    43. //如果是偶数
    44. if(l%2==0&&l!=2){
    45. cout<<2<<' '<-2<
    46. return;
    47. }
    48. else{
    49. for(int i=3;i<=l/i;i+=2){
    50. if(l%i==0){
    51. cout<' '<
    52. return;
    53. }
    54. }
    55. }
    56. }
    57. cout<<-1<
    58. }
    59. int main() {
    60. ios::sync_with_stdio(false);
    61. cin.tie(0);
    62. cout.tie(0);
    63. get_prime(N);
    64. for(int i=0;i1;
    65. // for(int i=0;i
    66. int t=1;
    67. cin>>t;
    68. while(t--) {
    69. solve();
    70. }
    71. return 0;
    72. }

    AC代码: 

    1. #include
    2. #include
    3. #include
    4. #include
    5. #define endl '\n'
    6. //#define int long long
    7. using namespace std;
    8. typedef long long ll;
    9. const int N=1e7+10;
    10. int prime[N];
    11. int vis[N];
    12. bool st[N];
    13. int cnt;
    14. //欧拉筛
    15. void get_prime(int n){
    16. for(int i=2;i<=n;i++){
    17. if(!st[i]) prime[cnt++]=i;
    18. for(int j=0;prime[j]<=n/i;j++){
    19. st[prime[j]*i]=true;
    20. if(i%prime[j]==0) break;
    21. }
    22. }
    23. }
    24. void solve() {
    25. int l,r;
    26. cin>>l>>r;
    27. //如果有偶数(除了2)的话
    28. if(r-l>=1){
    29. for(int i=l;i<=r;i++){
    30. if(i%2==0&&i!=2){
    31. cout<<2<<' '<-2<
    32. return;
    33. }
    34. }
    35. }
    36. //其它的情况都是只有一个数,判断一个数即可
    37. if(l==r){
    38. //如果是素数,直接输出-1
    39. if(vis[l]){
    40. cout<<-1<
    41. return;
    42. }
    43. //如果是偶数
    44. if(l%2==0&&l!=2){
    45. cout<<2<<' '<-2<
    46. return;
    47. }
    48. else{
    49. for(int i=3;i<=l/i;i+=2){
    50. if(l%i==0){
    51. cout<' '<
    52. return;
    53. }
    54. }
    55. }
    56. }
    57. cout<<-1<
    58. }
    59. int main() {
    60. ios::sync_with_stdio(false);
    61. cin.tie(0);
    62. cout.tie(0);
    63. get_prime(N);
    64. for(int i=0;i1;
    65. // for(int i=0;i
    66. int t=1;
    67. cin>>t;
    68. while(t--) {
    69. solve();
    70. }
    71. return 0;
    72. }

    D.Problem - D - Codeforces

    AC代码:

    1. #include
    2. #include
    3. #include
    4. #include
    5. #define endl '\n'
    6. #define int long long
    7. using namespace std;
    8. typedef long long ll;
    9. int n,x,y;
    10. int gcd(int a,int b){
    11. if(b==0) return a;
    12. return gcd(b,a%b);
    13. }
    14. void solve() {
    15. cin>>n>>x>>y;
    16. int cnt1=n/x;
    17. int cnt2=n/y;
    18. int cnt3=n/(x*y/gcd(x,y));
    19. cnt1=cnt1-cnt3;
    20. cnt2=cnt2-cnt3;
    21. int sum2=(1+cnt2)*cnt2/2;
    22. int sum1=(2*n+1-cnt1)*cnt1/2;
    23. cout<
    24. }
    25. signed main() {
    26. ios::sync_with_stdio(false);
    27. cin.tie(0);
    28. cout.tie(0);
    29. int t=1;
    30. cin>>t;
    31. while(t--) {
    32. solve();
    33. }
    34. return 0;
    35. }

    E.Data Structures Fan

    利用前缀异或和,pre[i]表示从a[1]一直异或到a[i]

    ans0将所有s中为0对应的a值异或起来,之后ans0也将不断地变化,始终为所有s中为0对应的a值异或起来

    ans1将所有s中下标为1对应的a值异或起来,之后ans1也将不断地变化,始终为所有s中为1对应的a值异或起来

    当op等于2时,直接输出ans0或者ans1即可

    那么当op等于1时,我们就要考虑如何变化ans0和ans1了,每次都是[l,r]进行01互换,那么相应地,ans0和ans1也会变化

    由于只有[l,r]区间变化,所以我们也只考虑[l,r]这一区间

    我们将ans0异或上a[l]^a[l+1]^...a[r],如果ans0中的项有该区间以外的,那么仍异或上,如果项有该区间里面的,那么就消掉,如果区间有项是ans0没有的,也异或上

    ans1同理

     

    这样就实现了每次异或的项的转换

    AC代码:

    1. #include
    2. #include
    3. #include
    4. #include
    5. #define endl '\n'
    6. //#define int long long
    7. using namespace std;
    8. const int N=1e5+10;
    9. int a[N];
    10. int pre[N];
    11. int n,q;
    12. void solve() {
    13. cin>>n;
    14. for(int i=1;i<=n;i++) {
    15. cin>>a[i];
    16. pre[i]=pre[i-1]^a[i];
    17. }
    18. string s;
    19. cin>>s;
    20. s=' '+s;
    21. int ans0=0,ans1=0;
    22. for(int i=1;i<=n;i++){
    23. if(s[i]=='0') ans0^=a[i];
    24. else ans1^=a[i];
    25. }
    26. cin>>q;
    27. while(q--){
    28. int op;
    29. cin>>op;
    30. if(op==1){
    31. int l,r;
    32. cin>>l>>r;
    33. int ans=pre[r]^pre[l-1];
    34. ans0^=ans;
    35. ans1^=ans;
    36. }
    37. else{
    38. int x;
    39. cin>>x;
    40. if(x==0) cout<' ';
    41. else cout<' ';
    42. }
    43. }
    44. cout<
    45. }
    46. int main() {
    47. ios::sync_with_stdio(false);
    48. cin.tie(0);
    49. cout.tie(0);
    50. int t=1;
    51. cin>>t;
    52. while(t--) {
    53. solve();
    54. }
    55. return 0;
    56. }

    F.Selling a Menagerie

    拓扑排序+dfs

    首先进行拓扑排序,将那些没有成环的排好序,然后对于成环的,用dfs搜索环中价值最小的,将其放在最后

    AC代码:

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #define endl '\n'
    8. //#define int long long
    9. using namespace std;
    10. const int N=1e5+10;
    11. int a[N],c[N];
    12. int d[N];
    13. bool ok[N];
    14. int n;
    15. int minn,mini;
    16. void dfs(int x) {
    17. if(ok[x]) return;
    18. ok[x]=true;
    19. if(minn>c[x]) {
    20. minn=c[x];
    21. mini=x;
    22. }
    23. dfs(a[x]);
    24. }
    25. void solve() {
    26. cin>>n;
    27. //初始化
    28. for(int i=1; i<=n; i++) {
    29. d[i]=0;
    30. ok[i]=false;
    31. }
    32. for(int i=1; i<=n; i++) {
    33. cin>>a[i];
    34. d[a[i]]++;//入度+1
    35. }
    36. for(int i=1; i<=n; i++) cin>>c[i];
    37. queue<int>q;
    38. vector<int>ans;
    39. for(int i=1; i<=n; i++) {
    40. if(d[i]==0) {
    41. q.push(i);
    42. }
    43. }
    44. while(q.size()) {
    45. int t=q.front();
    46. q.pop();
    47. ans.push_back(t);
    48. ok[t]=true;//表示t已经排好了
    49. d[a[t]]--;
    50. if(d[a[t]]==0) q.push(a[t]);
    51. }
    52. if(ans.size()
    53. for(int i=1; i<=n; i++) {
    54. if(!ok[i]) {
    55. minn=c[i],mini=i;
    56. dfs(i);
    57. int x=a[mini];
    58. ans.push_back(x);
    59. x=a[x];
    60. while(x!=a[mini]) {
    61. ans.push_back(x);
    62. x=a[x];
    63. }
    64. }
    65. }
    66. }
    67. for(auto v:ans) cout<' ';
    68. cout<
    69. }
    70. int main() {
    71. ios::sync_with_stdio(false);
    72. cin.tie(0);
    73. cout.tie(0);
    74. int t=1;
    75. cin>>t;
    76. while(t--) {
    77. solve();
    78. }
    79. return 0;
    80. }
  • 相关阅读:
    YOLOv5的Tricks | 【Trick10】从PyTorch Hub加载YOLOv5
    Spring Security学习笔记(一)Spring Security架构原理
    HTTPSConnectionPool(host=‘files.pythonhosted.org‘, port=443): Read timed out解决
    Three.js 进阶之旅:全景漫游-高阶版在线看房 🏡
    面试所必问的技术点,你都知道吗?
    docker入门(二)—— docker三大概念(镜像、容器、仓库)
    GNN 101
    身份证合法验证查询易语言代码
    肝了一星期,终于把堆的创建、插入、删除和堆排序肝完了(超详细图文讲解)
    Ubuntu镜像源cn.arichinve.ubuntu.com不可用原因分析和解决
  • 原文地址:https://blog.csdn.net/m0_74087709/article/details/132792563