CodeForces round 520 div2
A:A Prank
题意:给定一个递增序列, 问最多能删除多少个连续数字,要求删除数字之后能还原成原来的数列。
题解:直接找就好了,为了方便可以使得第0个数字为0, 第n+1个元素为1001
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 1e5 + ;
int a[N];
int main(){
int n, m = ;
scanf("%d", &n);
a[] = , a[n+] = ;
for(int i = ; i <= n; ++i) scanf("%d", &a[i]);
int ans = ;
for(int i = ; i <= n; ++i){
if(a[i-]+ == a[i] && a[i]+ == a[i+]) m++;
else m = ;
ans = max(ans, m);
}
cout << ans << endl;
return ;
}
B:Math
题意:给你一个n,现在有2种操作,1把这个n乘上一个值,2把这个n开根号,要求开完根号之后还是整数,求n最小能变成多少,以及最小的操作次数。
题解:对于一个数字,我们先把他分解质因子,计算每个因子的个数,很明白,只有所有的质因子都为偶数的时候,他这个时候才能开方,
并且,这个数的最小值就是这些不同的质因子的乘积。
要使数字变小,所以我们先需要把每个因子的个数都变成偶数,然后在开根号,因子个数都会/2
所以我们需要找到最大的因子个数是啥,假如为x,然后把所有数目都变成 x <= 2^k 次,然后我们只需要一直开方就好了。
如果x = 5, 我们至少要把除3次,为了避免每次都需要先乘上一个数,我们把第一次乘法的时候就把他变成2^k。
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 1e5 + ;
vector<int> vc;
int aaans = ;
void solve(int x){
for(int i = ; i*i <= x; ++i){
if(x%i == ){
int cnt = ;
aaans *= i;
while(x%i == ){
x /= i;
cnt++;
}
vc.pb(cnt);
}
}
if(x != ) vc.pb();
aaans *= x;
}
int cnt = ; int main(){
int n;
scanf("%d", &n);
solve(n);
if(vc.size() == ) vc.pb();
int mx = , f = ;
for(auto v : vc){
mx = max(v, mx);
}
int tmp = ;
for(int i = ;;++i){
if(mx <= (<<i)){
tmp = i;
break;
}
}
int ans = tmp;
tmp = << tmp;
for(auto v: vc){
if(tmp != v) f = ;
}
ans += f;
cout << aaans << ' ' << ans << endl;
return ;
}
C:Banh-mi
题解:找规律。
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 1e5 + ;
int cnt[N][];
LL dp[N];
void init(){
//LL t = 1;
dp[] = ;
for(int i = ; i < N; ++i){
dp[i] = dp[i-]<<;
if(dp[i] > mod) dp[i] -= mod;
}
}
int solve(int x, int y){
LL ret = ;
ret = dp[y+] - ;
ret += (dp[y+]-)*(dp[x+]-);
ret = ((ret%mod)+mod)%mod;
return ret;
}
char s[N];
int main(){
int n, q;
init();
scanf("%d%d", &n, &q);
scanf("%s", s+);
for(int i = ; i <= n; ++i){
cnt[i][] = cnt[i-][];
cnt[i][] = cnt[i-][];
cnt[i][s[i]-'']++;
}
int l, r;
while(q--){
scanf("%d%d", &l, &r);
printf("%d\n", solve(cnt[r][]-cnt[l-][],cnt[r][]-cnt[l-][]));
}
return ;
}
题解:我们可以从样例分析中发现,我们可以经过4次跳跃之后返回到原来的这个地方。
也就是说,我们每次走到一个新的位置之后,我们可以遍历他的所有因子,再返回到这个位置,然后继续按原来的路径行事。
我们不用管他怎么走,只需要明白每出现一个数会对答案产生什么影响就好了。
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 1e5 + ;
int vis[N];
void init(){
for(int i = ; i < N; ++i){
for(int j = i+i, t = ; j < N; j+=i, t++){
vis[j] += t;
}
}
}
int main(){
int n;
scanf("%d", &n);
init();
LL sum = ;
for(int i = ; i <= n; ++i){
sum += vis[i];
}
cout << sum* << endl;
return ;
}
E:Company
题意:求多个点 在可以删除一个点的前提下剩下的点lca 取 深度最大的点能是啥。
题解:我们把树建立起来,跑一遍dfs,记录下他的dfs序。
那么答案就是找到这个区间的 最大值dfs序, 次大值, 次小值, 最小值。
然后答案就是在删除最大值的位置下 和 删除最小值的位置下取优。
这个操作是基于一个思想,就是 这些点的lca就是 dfs序的最大值的那个位置 和 最小值的那个位置的lca。
原因很简单,我们需要找到一个点 他的dfs序 入和出 能包括询问的所有的dfs序。
也就是说找到一个点 in[v] <= min(q - point ) out[v] >= max( q - point)
观察上式,我们发现只有 最大值和最小值发生了改变才会对答案产生影响, 删除中间的点是不会产生影响的。
所以我们只需要找到 最大值, 次大值, 次小值, 最小值 然后删除最大值 查询最小值和次大值的lca 和 删除最小值查询次小值和最大值的lca 2者取优就好了。
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 1e5 + ;
int anc[N][];
int dfn[N], now = , deep[N], pos[N];
int n, q;
vector<int> vc[N];
void dfs(int u){
dfn[u] = ++now;
pos[now] = u;
for(auto v : vc[u]){
deep[v] = deep[u] + ;
anc[v][] = u;
for(int i = ; i < ; ++i) anc[v][i] = anc[anc[v][i-]][i-];
dfs(v);
}
}
int Find(int u, int v){
if(deep[u] < deep[v]) swap(u,v);
int x = deep[u] - deep[v];
for(int i = ; i >= ; --i)
if((x>>i)&)
u = anc[u][i];
if(u == v) return u;
for(int i = ; i >= ; --i)
if(anc[u][i] != anc[v][i])
u = anc[u][i], v = anc[v][i];
return anc[v][]; }
int tmx[N<<], tmn[N<<];
void build(int l, int r, int rt){
if(l == r){
tmx[rt] = tmn[rt] = dfn[l];
return ;
}
int m = l+r >> ;
build(lson); build(rson);
tmx[rt] = max(tmx[rt<<], tmx[rt<<|]);
tmn[rt] = min(tmn[rt<<], tmn[rt<<|]);
}
int Qmax(int L, int R, int l, int r, int rt){
if(L > R) return ;
if(L <= l && r <= R) return tmx[rt];
int m = l+r >> ;
int ret = ;
if(L <= m) ret = max(ret, Qmax(L,R,lson));
if(m < R) ret = max(ret, Qmax(L,R,rson));
return ret;
}
int Qmin(int L, int R, int l, int r, int rt){
if(L > R) return N;
if(L <= l && r <= R) return tmn[rt];
int m = l+r >> ;
int ret = N;
if(L <= m) ret = min(ret, Qmin(L,R,lson));
if(m < R) ret = min(ret, Qmin(L,R,rson));
return ret;
}
void solve(int l, int r){
int x1, x2, x3, x4;
int v1, v2, v3, v4;
v1 = Qmax(l,r,,n,);
x1 = pos[v1];
v2 = max(Qmax(l,x1-,,n,), Qmax(x1+,r,,n,));
x2 = pos[v2];
v4 = Qmin(l,r,,n,);
x4 = pos[v4];
v3 = min(Qmin(l,x4-,,n,), Qmin(x4+,r,,n,));
x3 = pos[v3];
int ans1 = deep[Find(x1,x3)];
int ans2 = deep[Find(x2,x4)];
if(ans1 >= ans2)
printf("%d %d\n", x4, ans1);
else printf("%d %d\n", x1, ans2);
}
int main(){
scanf("%d%d", &n, &q);
for(int i = , u; i <= n; ++i){
scanf("%d", &u);
vc[u].pb(i);
}
dfs();
build(,n,);
int l, r;
while(q--){
scanf("%d%d", &l, &r);
solve(l, r);
}
return ;
}
题意:问有多少个点是合法点,u点如果是合法点,则最多只有一个点v 是 u没法走到v, v没法走到u。 题目说了一开始的图不会是强连通图。
题解:
我们先正向建图,然后按照拓扑排序的写法,当一个点的度数为0的时候入队。
每次我们取出一个点,我们看看队内是否为空,如果队内为空,则我们目前的这个点一定就是可以走到剩下图中所有的点。
如果队内还有一个点, 首先我们需要明白, 已经取出来的点x 和 还在队内的那个点y 这2个点之间是没有边的关系的,即 x 不能走到 y, y不能走到x。
现在我们判断一下,在剩下的图中,是不是有一个点是只能通过y走到的,如果存在这样的一个点,那么算上y之后就有2个点是x所不能走到了,那么x一定是非法点,所以我们不需要再精确的计算出x能到达多少点,这已经是没有意义的了。如果不存在一个点只能通过y走到,那么到目前为止,对于x来说只有y是没办法走到了,剩下图中的所有点都是可以走到的。
当队内不止有一个点之后,我们通过上面的分析可以明白,x一定不会是合法点,因为已经至少有2个点不行了,同样的我们也不再需要计算x可以到多少个点。
我们再反向建图,再按上面的程序跑一遍。
最后我们把v能达到的点的数目和能到达v点的数目加起来,就可以判断这个点是不是合法点了。
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 3e5 + ;
vector<int> vc[N];
int u[N], v[N], d[N];
int ans[N];
int n, m;
int sta[N];
void bfs(){
int tot = n;
int l = , r = ;
for(int i = ; i <= n; ++i)
if(d[i] == ){
sta[r++] = i;
tot--;
}
while(l < r){
int x = sta[l++];
if(l == r) ans[x] += tot;
else if(l+ == r){
int y = sta[l], f = ;
for(auto v : vc[y]){
if(d[v] == ){
f = ;
break;
}
}
if(f) ans[x] += tot;
}
for(auto v : vc[x]){
--d[v];
if(d[v] == ){
sta[r++] = v;
tot--;
}
}
} }
int main(){
scanf("%d%d", &n, &m);
for(int i = ; i <= m; ++i)
scanf("%d%d", &u[i], &v[i]);
for(int i = ; i <= m; i++){
vc[u[i]].pb(v[i]);
++d[v[i]];
}
bfs();
for(int i = ; i <= n; ++i)
vc[i].clear();
for(int i = ; i <= m; ++i){
vc[v[i]].pb(u[i]);
++d[u[i]];
}
bfs();
int fans = ;
for(int i = ; i <= n; ++i){
fans += (ans[i] >= n-);
}
printf("%d\n", fans);
return ;
}
最新文章
- JS阻止冒泡事件以及默认事件发生的简单方法
- raspbian调整分辨率
- ADO.NET数据访问技术
- 0.[WP Developer体验Andriod开发]之从零安装配置Android Studio并编写第一个Android App
- Python 读取文件下所有内容、获取文件名、截取字符、写回文件
- 怎么在Ubuntu Scope中获取location地址信息
- 9天快速入门java
- centos7安装codeblocks教程
- bzoj4818 [Sdoi2017]序列计数
- Django练习——TodoList
- Oracle E-Business Suite Maintenance Guide Release 12.2(Patching Procedures)
- 微信小程序上传后发布或者体验版测试无数据解决办法
- 使用korofileheader插件vs code添加文件头注释和函数注释
- yuv rgb 互转 公式 及算法
- PythonStudy——函数的使用 Use of functions
- 如何在Windows平台下安装配置Memcached
- Mac 安装HTMLTestRunner模块
- Android4.0 主线程不能访问网络异常解决办法
- requestAnimFrame动画兼容性封装
- ARM9/ARM11/Cortex A8处理器(转载) .