首页 > 其他分享 >CF689题解

CF689题解

时间：2023-11-30 19:11:06浏览次数：49  
标签：ch CF689 int 题解 路口 mid while getchar

CF689

Codeforces Round 361 (Div. 2)

CF689A

link

CF689A题意

题目描述
迈克在海滩游泳时不小心将手机放入水中。他买了一个带有老式键盘的手机。键盘只有十个数字大小的键，位于以下方式：

1 2 3
4 5 6
7 8 9
0

联系人与他的旧手机一起消失了，他现在只能记住他的手指在他输入一些数字时的移动方式。人们可以将手指动作视为连接按下按键的一系列动作。例如，数字“586”的手指移动动作与数字“253”的手指移动动作相同。
Mike通过他的“手指记忆”输入了一个数字并开始调用它，所以他现在担心，有没有其他数字，有相同的手指动作？

输入格式：
输入的第一行包含唯一的整数n（1<=N<=9）表示Mike输入的电话号码中的位数。第二行由1到9组成的n个字符的字符串。

输出格式：
如果没有其他电话号码具有相同的手指移动，则输出“YES”，否则输出“NO”（不带引号）。

CF689A题解

  • 如果出现 \(0,1,4,7\)，那么不能向左移动。
  • 如果出现 \(0,3,6,9\)，那么不能向右移动。
  • 如果出现 \(1,2,3\)，那么不能向上移动。
  • 如果出现 \(7,0,9\)，那么不能向下移动。

判定一下就好了。

CF689A代码

终于做了一道码量正常的题了。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
int n;
int opt[12];
signed main(){
    n = read();
    for(int i = 1;i <= n;i++){scanf("%1d",&opt[i]);}
    bool l = true, r = true,u = true, d = true;
    for(int i = 1;i <= n;i++){
        if(opt[i] == 0){l = r = d = false;continue;}
        if(opt[i] % 3 == 1)l = false;
        if(opt[i] <= 3) u = false;
        if(opt[i] >= 7 && opt[i] != 8) d = false;
        if(opt[i] % 3 == 0)r = false;
    }
    puts((l | r | u | d) ? "NO" : "YES");
    return 0;
}

CF689B

link

CF689B题意

最近，小贝忙于学习，考试和比赛。现在她想出去在城市里逛逛放松一下。

城市有 \(n\) 个路口，从 \(1\) 到 \(n\) 编号。小贝家在 \(1\) 号路口，她从 \(1\) 号路口出发，走过一系列的路口。从路口 \(i\) 到路口 \(j\) 需要消耗 \(|i - j|\) 单位的能量。她走过一系列路口 \(p_1,p_2,\dots,p_k\) 消耗的总能量等于 \(\sum_{i=1}^{k-1}|p_i-p_{i-1}|\)。

当然，如果没有小路，一味步行是比较无聊的。小路是特别的路径，能让小贝从一个路口到另一个路口只消耗 \(1\) 单位的能量。小贝的城市总共恰好有 \(n\) 条小路，第 \(i\) 条小路允许小贝从路口 \(i\) 走到路口 \(a_i​ (i \le a_i \le a_{i+1})\) (但不能反方向走)，因此每个路口都有且只有一条小路。严格来说，如果小贝选择一系列路口\(p_1 = 1,p_2,\dots,p_k\)，那么对于每个 \(1 \le i < k\) 满足 \(p_i+ 1 = a_{p_i}\)，并且 \(a_{p_i}\neq p_i\)，从路口 \(p_i\) 到路口\(p_{i+1}\)，小贝只会消耗1单位能量，而不是|\(p_i - p_{i+1}\)|。 例如，如果小贝选择路口序列\(p_1 = 1,p_2=a_{p_1}\), \(p_3=a_{p_2}\), \(\dots\), \(p_k\) = \(a_{p_{k-1}}\)，她总共消耗 \(k - 1\) 单位的能量。

在她开始闲逛之前，她请你帮她计算从她家到达每个路口最少消耗多少能量。

CF689B题解

翻译题面修了半天还不如自己写一遍呢
按照题意，将 \(i\to a_i\)，边权是 \(1\)，然后将 \(i\to i+1,i+1\to i\)，边权都是 \(1\)。
然后跑Dijkstra就好了。

CF689B代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 2e5 + 10,INF = 0x3f3f3f3f;
int n;

int head[maxn], tot;
struct edge{
    int to, nexte, wei;
    edge(int to = 0,int ne = 0,int wei = 0):to(to),nexte(ne),wei(wei){}
}e[maxn << 2];
void add(int u,int v,int w){e[++tot] = edge(v,head[u],w);head[u] = tot;}

int dis[maxn];bool book[maxn];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > que;

signed main(){
    n = read();
    for(int i = 1;i <= n;i++)add(i,read(),1), dis[i] = INF;
    for(int i = 1;i < n;i++) add(i,i + 1,1),add(i + 1,i,1);
    dis[1] = 0;que.push(make_pair(0, 1));
    while(!que.empty()){
        int u = que.top().second;que.pop();
        if(book[u])continue;book[u] = 1;
        for(int i = head[u];i;i = e[i].nexte){
            int v = e[i].to;
            if(dis[v] > dis[u] + e[i].wei){
                dis[v] = dis[u] + e[i].wei;
                que.push(make_pair(dis[v],v));
            }
        }
    }
    for(int i = 1;i <= n;i++)printf("%d ",dis[i]);
    return 0;
}

CF689C

link

CF689C题意

有四个小偷去偷巧克力，四个人偷巧克力的个数是一个等比数列。
给你一个 \(n\) ，找一个最小数 \(t\) ，使得在 \(t\) 内有 \(n\) 组等比数列成立。

CF689C题解

直接二分答案即可，重要的是读懂题意。

CF689C代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
int n;
int check(int mid){
    int cnt = 0;
    for(int i = 2;i * i * i <= mid;i++)
        cnt += mid / i / i / i;
    return cnt;
}
signed main(){
    n = read();
    int l = 1, r = 1e18 + 1, ans = -1;
    while(l <= r){
        int mid = l + r >> 1;
        if(check(mid) >= n){ans = mid;r = mid - 1;}
        else l = mid + 1;
    }
    if(ans == -1 || check(ans) != n)puts("-1");
    else printf("%lld\n",ans);
    return 0;
}

CF689D

link

CF689D题意

  • 给定序列 \(a\) 和序列 \(b\)，长度均为 \(n\)。问有多少组 \((l,r)\)，满足 \(1\le l\le r\le n\) 且

\[\max_{i=l}^r a_i=\min_{i=l}^r b_i \]

  • \(1\le n\le 2\times 10^5\)，\(|a_i|,|b_i|\le 10^9\)。

CF689D题解

对于每一个 \(r\)，\(\max\) 值从 \(1\to r\) 单调不增，\(\min\) 值从 \(1\to r\) 单调不降，两者相交的部分就是答案，这东西可以二分，搭配 \(st\) 表可以 \(O(n\log n)\)。

CF689D代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 2e5 + 10;
int a[maxn], b[maxn];
int n, lg[maxn];
int minn[23][maxn], maxx[23][maxn];

int qrymin(int l,int r){
    if(r - l + 1 <= 0)return 0x3f3f3f3f3f3f3f;
    int k = lg[r - l + 1];return min(minn[k][l],minn[k][r - (1 << k) + 1]);
}
int qrymax(int l,int r){
    if(r - l + 1 <= 0)return -0x3f3f3f3f3f3f3f;
    int k = lg[r - l + 1];return max(maxx[k][l],maxx[k][r - (1 << k) + 1]);
}

int qryl(int x){
    int l = x, r = n, mid = 0;
    while(r - l >= 0){
        mid = l + r >> 1;
        if(qrymax(x,mid) < qrymin(x,mid)){l = mid + 1;}
        else r = mid - 1;
    }
    if(l <= n && qrymin(x,l) == qrymax(x,l))return l;
    return -1;
}
int qryr(int x){
    int l = x, r = n, mid = 0;
    while(r - l >= 0){
        mid = l + r >> 1;
        if(qrymax(x,mid) > qrymin(x,mid)){r = mid - 1;}
        else l = mid + 1;
    }
    if(r > 0 && qrymin(x,r) == qrymax(x,r))return r;
    return -1;
}
int query(int x){
    int l = qryl(x), r = qryr(x);
    // printf("x = %lld, l = %lld, r = %lld\n",x,l,r);
    // for(int i = x;i <= n;i++){
    //     printf("i = %lld : min=%lld max=%lld\n",i,qrymin(x,i),qrymax(x,i));
    // }
    if(l == -1 || r == -1)return 0;
    return r - l + 1;
}

signed main(){
    n = read();lg[0] = -1;
    for(int i = 1;i <= n;i++){lg[i] = lg[i >> 1] + 1;a[i] = read();maxx[0][i] = a[i];}
    for(int i = 1;i <= n;i++){b[i] = read();minn[0][i] = b[i];}
    for(int k = 1;k <= 22;k++)
        for(int i = 1;i + (1 << k) -  1 <= n;i++){
            maxx[k][i] = max(maxx[k - 1][i],maxx[k - 1][i + (1 << k - 1)]);
            minn[k][i] = min(minn[k - 1][i],minn[k - 1][i + (1 << k - 1)]);
        }
    int ans = 0;
    for(int l = n;l;l--){ans += query(l);}
    printf("%lld\n",ans);
    return 0;
}

CF689E

link

CF689E题意

数轴上有 \(n\) 条线段，每条线段的端点为 \(l_i\)，\(r_i\)。
众所周知，在 \(n\) 条线段中取 \(k\) 条线段有 \(n \choose k\) 即 \(C_n^k\)
种方案，现在每种方案的贡献为这 \(k\) 条线段交集包含的整点个数（即交集那条线段的长度 \(+1\)），求所有方案的贡献和 \(mod\space 10^9+7\)。

CF689E题解

这里有野生的水紫，快来切啊（bushi）
离散化，差分两步走，得出每一段线段被覆盖几次。
发现对于覆盖次数 \(cnt_i\ge k\) 的线段，贡献是 \(cnt_i\choose k\)，即从覆盖它的线段中选出 \(k\) 条满足条件的来求并集的方案数。
然后就没了，根本不用什么数据结构。

CF689E代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e6 + 10,mod = 1e9 + 7;
int n, k, cf[maxn];
int l[maxn], r[maxn], x[maxn], tot;
int pw[maxn], pwinv[maxn];
int qpow(int x,int a){
    int res = 1;
    while(a){
        if(a & 1)res = res * x % mod;
        x = x * x % mod;a >>= 1;
    }
    return res;
}
signed main(){
    n = read();k = read();pw[0] = 1;
    for(int i = 1;i <= n;i++){
        x[++tot] = l[i] = read();
        x[++tot] = r[i] = read() + 1;
        pw[i] = pw[i - 1] * i % mod;
    }
    pwinv[n] = qpow(pw[n],mod - 2);
    for(int i = n - 1;i;i--)pwinv[i] = pwinv[i + 1] * (i + 1ll) % mod;
    pwinv[0] = 1;

    // for(int i = 1;i <= n;i++){printf("i = %lld,tim = %lld\n",i,pwinv[i] * pw[i] % mod);}

    sort(x + 1,x + 1 + tot);tot = unique(x + 1,x + 1 + tot) - x - 1;
    for(int i = 1;i <= n;i++){
        l[i] = lower_bound(x + 1,x + 1 + tot,l[i]) - x;
        r[i] = lower_bound(x + 1,x + 1 + tot,r[i]) - x;
        cf[l[i]]++;cf[r[i]]--;
    }
    int ans = 0;
    for(int i = 1;i < tot;i++){
        cf[i] += cf[i - 1];if(cf[i] < k)continue;
        int len = x[i + 1] - x[i];
        ans = (ans + pw[cf[i]] * pwinv[cf[i] - k] % mod * pwinv[k] % mod * len % mod) % mod;
    }
    printf("%lld\n",ans);
    return 0;
}

标签：ch,CF689,int,题解,路口,mid,while,getchar
From： https://www.cnblogs.com/Call-me-Eric/p/17868058.html

相关文章

  • 商家转账到零钱全攻略：开通、使用、区别与常见问题解答
    一、商家转账到零钱功能介绍微信作为中国最受欢迎的社交平台之一，其支付功能也相当强大。其中，商家转账到零钱功能可以让商家直接将款项转入用户的微信零钱，方便快捷。本文将详细介绍商家转账到零钱的功能、开通条件、使用方法以及常见问题解答。二、商家转账到零钱场景说明商家转......
  • axios(ajax)发送请求响应码200，但获取不到数据，无法加载响应数据: No datafound for res
    问题截图：没有响应数据控制台报错其实是由于浏览器的跨域资源共享（CORS）策略导致，前后端跨域请求是不行的。什么是域，看页面的url，比如https://www.baidu.com/下的网页都是属于baidu.com这个域。如果你是和我一样是从本地文件打开html的方式来调试ajax，那么一定会出现这个问题，因为本......
  • CF1846E2 Rudolf and Snowflakes (hard version) 题解
    题意：\(T\)\((\)\(1\)\(\le\)\(T\)\(\le\)\(10^4\)\()\)组询问：是否存在一个满\(k\)(\(k\)\(\ge\)\(2\)\()\)叉树节点数恰好为\(n\)\((\)\(1\)\(\le\)\(n\)\(\le\)\(10^{18}\)\()\)，且深度\(depth\)至少为\(2\)。思路：满$k$......
  • luogu2839题解
    [国家集训队]middle题目分析代码如下。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;constintMAXN=2e4+10;intx,n,Q,a[MAXN],q[6],root[MAXN],b[MAXN],tot;vector<int>locp[MAXN];structSegmentTreeNode{......
  • CF1827C Palindrome Partition 题解
    题目链接点击打开链接题目解法首先考虑一个朴素的\(dp\)令\(f_i\)表示以\(i\)结尾的合法子串的个数为了不重不漏，我们令\(le_i\)表示以\(i\)为右端点，离\(i\)最近的偶回文串的左端点，然后不难得到转移为\(f_i=f_{le_i-1}+1\)为什么不会漏？考虑以\(i\)为右端点，且比......
  • NOIP2000提高组真题解析
    NOIP2000提高组真题解析第一题进制转换题目链接解析首先，我们知道对于10进制数x转2进制数，使用的算法是：求出x%2令x=x/2不断执行1,2,直至x为0,然后倒序输出步骤1的结果。一般可以用数组存步骤1的结果倒序输出或者使用dfs回溯回来再输出。对于负数的情况，比如\(-7=1*(-2)^3......
  • ISCTF 逆向题解
    ISCTF逆向题解用一个晚上的时间看了看ISCTF，有的题还蛮难的(毕竟得嘎嘎猜出题人想法)CrackMewinhex打开exe，修改标识头PFX为UPX然后放进UPXshell里面试试脱了，放进ida，直接反编译得到flagEasyReexeinfo看看这个是什么64位，放进ida反编译得到一段很清晰的逻辑反转+异或+单表代换。。。......
  • ICPC2022Xian L Tree 题解
    LinkICPC2022XianLTreeQuestion给出一个根为\(1\)的树，需要将树分成几个块每个块，一个块中的节点需要满足以下条件中的一个：对于所有的\(u,v\inS,\u\neqv\)，满足\(u\insubtree(v)\)或\(v\insubtree(u)\)对于所有的\(u,v\inS,\u\neqv\)，满足\(u\not......
  • [ABC277G] Random Walk to Millionaire 题解
    题目链接点击打开链接题目解法首先\(O(n^3)\)的\(dp\)是显然的，令\(f_{i,j,k}\)为第\(i\)步在\(j\)，当前等级为\(k\)的\([i,n]\)步获得钱数的期望，转移枚举出边即可一个很妙的优化是：贡献都是\(k^2\)的形式，所以我们考虑维护\(k\)的\(0,1,2\)次幂，即\(\sum,\sum......
  • CF1900D - Small GCD 题解
    1900D-SmallGCD给定序列\(A\)，定义\(f(a,b,c)\)为\(a,b,c\)中最小的次小的数的\(\gcd\)，求：\[\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=j+1}^nf(a_i,a_j,a_k)\]题解目前来说有两种方法，都十分有启发意义，但是有共同的开头。考虑到\(A\)的顺序实际上没有......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99