CF689
CF689A
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
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
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
CF689D题意
- 给定序列 \(a\) 和序列 \(b\),长度均为 \(n\)。问有多少组 \((l,r)\),满足 \(1\le l\le r\le n\) 且
- \(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
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