ZOJ Monthly, March 2018

时间:2021-12-08 12:58:49

A. Easy Number Game

贪心将第$i$小的和第$2m-i+1$小的配对即可。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
int n,m,i,Case,a[N];long long ans;
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
ans=0;
for(i=1;i<=m;i++)ans+=1LL*a[i]*a[m*2+1-i];
printf("%lld\n",ans);
}
}

  

B. Lucky Man

$\sum_{i=1}^n\lfloor\frac{n}{n-i+1}\rfloor=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor=\sum_{i=1}^n d(i)$

设$n=p_1^{k_1}p_2^{k_2}...p_m^{k_m}$,则$d(n)=(k_1+1)(k_2+1)...(k_m+1)$,当且仅当所有$k$都为偶数时$d(n)$模$2$才为$1$。

故答案就是$n$以内完全平方数的个数的奇偶性,即$\lfloor{\sqrt{n}}\rfloor\bmod 2$,牛顿迭代法开根号即可。

C = int(raw_input())
for i in range(0, C):
n = int(raw_input())
if n < 2 :
print n
continue
m = 2
tmpn, len = n, 0
while tmpn > 0:
tmpn /= 10
len += 1
base, digit, cur = 300, len / m, len % m
while (cur + m <= base) and (digit > 0):
cur += m
digit -= 1
div = 10 ** (digit * m)
tmpn = n / div
x = int(float(tmpn) ** (1.0 / m))
x *= (10 ** digit)
while True:
x0 = x
x = x + x * (n - x ** m) / (n * m)
if x == x0: break
while (x + 1) ** m <= n:
x = x + 1
print x % 2

  

C. Travel along the Line

枚举$1$的个数,那么$-1$和$0$的个数也就知道了,组合数计算概率即可,时间复杂度$O(n)$。

#include<cstdio>
const int N=1000010,P=1000000007;
int i,fac[N],inv[N],Case,n,m,x,y,z,ans,p[N];
inline int C(int n,int m){return n<m?0:1LL*fac[n]*inv[m]%P*inv[n-m]%P;}
int main(){
for(fac[0]=fac[1]=1,i=2;i<N;i++)fac[i]=1LL*fac[i-1]*i%P;
for(inv[0]=inv[1]=1,i=2;i<N;i++)inv[i]=1LL*(P-inv[P%i])*(P/i)%P;
for(i=2;i<N;i++)inv[i]=1LL*inv[i-1]*inv[i]%P;
for(p[0]=1,p[1]=inv[2],i=2;i<N;i++)p[i]=1LL*p[i-1]*p[1]%P;
scanf("%d",&Case);
while(Case--){
scanf("%d%d",&n,&m);
ans=0;
for(i=0;i<=n;i++){
x=i;//1
y=i-m;//-1
z=n-x-y;//0
if(y<0||y>n||z<0||z>n)continue;
ans=(1LL*C(n,x)*C(n-x,y)%P*p[(x+y)*2+z]+ans)%P;
}
printf("%d\n",ans);
}
}

  

D. Machine Learning on a Tree

问题等价于给每个$y=-1$的点确定一个$0$或者$1$的颜色,使得树上相邻异色点对数量最少。

树形DP,设$f[i][j]$表示考虑$i$的子树,$i$点颜色为$j$时相邻异色点对数量的最小值。

时间复杂度$O(n)$。

#include<cstdio>
const int N=100010,inf=100000000;
inline void up(int&a,int b){a>b?(a=b):0;}
int Case,n,a[N],i,x,y,f[N][2],h[2],g[N],v[N<<1],nxt[N<<1],ed;
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x,int y){
f[x][0]=f[x][1]=inf;
if(a[x]==0)f[x][0]=0;
else if(a[x]==1)f[x][1]=0;
else f[x][0]=f[x][1]=0;
for(int i=g[x];i;i=nxt[i]){
int u=v[i];
if(u==y)continue;
dfs(u,x);
for(int j=0;j<2;j++)h[j]=inf;
for(int j=0;j<2;j++)for(int k=0;k<2;k++)up(h[j],f[x][j]+f[u][k]+(j^k));
for(int j=0;j<2;j++)f[x][j]=h[j];
}
}
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(ed=i=0;i<=n;i++)g[i]=0;
for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs(1,0);
up(f[1][0],f[1][1]);
printf("%d\n",f[1][0]);
}
}

  

E. Yet Another Tree Query Problem

$[l,r]$的连通块数量$=$点数$-$边数$=r-l+1-$两端点都在该区间内的树边数量。

二维数点问题,扫描线+树状数组即可。

时间复杂度$O(n\log n)$。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200010;
int Case,n,m,i,x,y,ans[N],bit[N],ce;
struct E{int x,y,t;E(){}E(int _x,int _y,int _t){x=_x,y=_y,t=_t;}}e[N*3];
inline bool cmp(const E&a,const E&b){
if(a.x!=b.x)return a.x>b.x;
return a.t<b.t;
}
inline void add(int x){for(;x<=n;x+=x&-x)bit[x]++;}
inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d%d",&n,&m);
ce=0;
for(i=1;i<n;i++){
scanf("%d%d",&x,&y);
if(x>y)swap(x,y);
e[++ce]=E(x,y,0);
}
for(i=1;i<=m;i++){
scanf("%d%d",&x,&y);
ans[i]=y-x+1;
e[++ce]=E(x,y,i);
}
sort(e+1,e+ce+1,cmp);
for(i=1;i<=n;i++)bit[i]=0;
for(i=1;i<=ce;i++)if(e[i].t)ans[e[i].t]-=ask(e[i].y);else add(e[i].y);
for(i=1;i<=m;i++)printf("%d\n",ans[i]);
}
}

  

F. And Another Data Structure Problem

对于题中所给模数,每个数操作很少步之后就会进入循环。

每个循环长度都很小,且长度不同的循环一共$5$种,长度之和不超过$70$。

线段树每个区间维护区间内尚未进入循环的数字个数、所有数的和、以及对于每种长度的循环,假设长度为$len$,维护$f[0..len-1]$,其中$f[i]$表示若继续在这个区间整体立方操作$i$次,在$len$长度的循环中所有数的和。

对于立方操作,若区间还存在尚未进入循环的数字,则暴力递归修改,否则打标记。

标记下放/生效时,假设标记是区间整体操作了$p$次,那么将$f[i]$赋值给$f[(i-p)\bmod len]$即可。

时间复杂度$O(n\log n\times 常数)$。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N=100010,M=262150,P=99971;
int i,j,k,vis[N],f[N],q[N],m,mark[N];
int tot,cur,cnt,have[N],len[100],st[100],en[100],posx[N],posy[N];
int tag[M],val[M][72],ok[M][5],sum[M],ret[M];
int Case,n,qqq,op,x,y,a[N];
inline void add1(int x,int p){
static int pool[1000];
tag[x]+=p;
int s=sum[x];
for(int i=0;i<cnt;i++)if(ok[x][i]){
int l=len[i],ST=st[i];
int t=p%l;
t=(l-t)%l;
if(!t)continue;
s-=val[x][ST];
if(s<0)s+=P;
int j;
memcpy(pool+t,val[x]+ST,(l-t)<<2);
memcpy(pool,val[x]+ST+l-t,t<<2);
memcpy(val[x]+ST,pool,l<<2);
//for(j=0;j+t<l;j++)pool[j+t]=val[x][ST+j];
//for(;j<l;j++)pool[j+t-l]=val[x][ST+j];
//for(j=0;j<l;j++)val[x][ST+j]=pool[j];
s+=val[x][ST];
if(s>=P)s-=P;
}
sum[x]=s;
}
inline void pb(int x){
if(tag[x]){
add1(x<<1,tag[x]);
add1(x<<1|1,tag[x]);
tag[x]=0;
}
}
inline void upd(int&a,int b){a=a+b<P?a+b:a+b-P;}
inline void up(int x){
sum[x]=(sum[x<<1]+sum[x<<1|1])%P;
ret[x]=ret[x<<1]+ret[x<<1|1];
for(int i=0;i<cnt;i++)ok[x][i]=ok[x<<1][i]+ok[x<<1|1][i];
if(!ret[x])for(int i=0;i<cur;i++){
val[x][i]=val[x<<1][i];
upd(val[x][i],val[x<<1|1][i]);
}
}
inline void init(int x,int y){
for(int i=0;i<cnt;i++)ok[x][i]=0;
sum[x]=y;
if(!mark[y]){
ret[x]=1;
}else{
ret[x]=0;
for(int i=0;i<cur;i++)val[x][i]=0;
int o=posx[y];
ok[x][o]=1;
for(int i=0;i<len[o];i++){
val[x][st[o]+i]=y;
y=f[y];
}
}
}
void build(int x,int a,int b){
tag[x]=0;
if(a==b){
init(x,::a[a]);
return;
}
int mid=(a+b)>>1;
build(x<<1,a,mid);
build(x<<1|1,mid+1,b);
up(x);
}
void change(int x,int a,int b,int c,int d){
if(c<=a&&b<=d){
if(!ret[x]){
add1(x,1);
return;
}
if(a==b){
init(x,::a[a]=f[::a[a]]);
return;
}
}
pb(x);
int mid=(a+b)>>1;
if(c<=mid)change(x<<1,a,mid,c,d);
if(d>mid)change(x<<1|1,mid+1,b,c,d);
up(x);
}
int ask(int x,int a,int b,int c,int d){
if(c<=a&&b<=d)return sum[x];
pb(x);
int mid=(a+b)>>1,t=0;
if(c<=mid)t=ask(x<<1,a,mid,c,d);
if(d>mid)t+=ask(x<<1|1,mid+1,b,c,d);
return t%P;
}
int main(){
for(i=0;i<P;i++)f[i]=1LL*i*i%P*i%P;
for(i=0;i<P;i++)have[i]=-1;
for(i=0;i<P;i++)if(!vis[i]){
for(j=i;!vis[j];j=f[j])vis[j]=1;
if(mark[j])continue;
q[m=1]=j;
for(k=f[j];k!=j;k=f[k])q[++m]=k;
for(j=1;j<=m;j++)mark[q[j]]=1;
if(have[m]==-1){
have[m]=cnt;
len[cnt]=m;
st[cnt]=cur;
en[cnt]=cur+m;
cur+=m;
//[st,en)
cnt++;
}
for(j=1;j<=m;j++)posx[q[j]]=have[m],posy[q[j]]=j-1;
}
scanf("%d",&Case);
//Case=1;
while(Case--){
scanf("%d%d",&n,&qqq);
//n=100000;
//qqq=100000;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
//a[i]=rand();
a[i]%=P;
}
build(1,1,n);
while(qqq--){
//op=rand()%2+1;
//x=rand()%n+1;
//y=rand()%n+1;
//if(x>y)swap(x,y);
scanf("%d%d%d",&op,&x,&y);
if(op==1)change(1,1,n,x,y);
else printf("%d\n",ask(1,1,n,x,y));
}
}
}

  

G. Neighboring Characters

首先将环倍长,破环成链,那么剩下的子串要满足相邻字符不同且首尾字符不同。

通过双指针求出每一段极长的子串,满足相邻字符不同,设这一段长度为$len$,从$2$到$len$枚举剩下的串的长度$L$,若该子串长度为$len-L+1$的前后缀不能完全匹配,则说明存在距离为$L-1$的位置不同,也就能充当首尾,Hash判断即可。

时间复杂度$O(n)$。

#include<cstdio>
#include<cstring>
typedef long long ll;
const int N=2000010,D=233,P=1000000009;
int C,n,m,i,j,k,len;char a[N],ans[N];ll pow[N],f[N];
int Case;
inline ll hash(int l,int r){return((f[r]-f[l-1]*pow[r-l+1])%P+P)%P;}
int main(){
for(pow[0]=i=1;i<N;i++)pow[i]=pow[i-1]*D%P;
scanf("%d",&Case);
while(Case--){
scanf("%s",a+1);
n=strlen(a+1);m=n+n;
for(i=1;i<=n;i++)a[i+n]=a[i];
for(i=1;i<=m;i++)f[i]=(f[i-1]*D+a[i])%P;
for(i=0;i<n;i++)ans[i]='0';
for(i=1;i<=m;i=j+1){
for(j=i;j<m&&a[j]!=a[j+1];j++);
len=j-i+1;
for(k=2;k<=len&&k<=n;k++)if(hash(i,i+len-k)!=hash(j-len+k,j))ans[n-k]='1';
}
for(i=0;i<n-1;i++)putchar(ans[i]);puts("1");
}
return 0;
}

  

H. Happy Sequence

$f[i][j]$表示长度为$i$的序列,最后一项为$j$的方案数,调和级数枚举$j$的倍数$k$转移给$f[i+1][k]$即可。

时间复杂度$O(mn\log n)$。

#include<cstdio>
const int N=2010,P=1000000007;
int Case,n,m,i,j,k,f[N][N],ans;
inline void up(int&a,int b){a=a+b<P?a+b:a+b-P;}
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d%d",&n,&m);//length m
for(i=0;i<=m;i++)for(j=1;j<=n;j++)f[i][j]=0;
for(i=1;i<=n;i++)f[1][i]=1;
for(i=1;i<m;i++)for(j=1;j<=n;j++)for(k=j;k<=n;k+=j)up(f[i+1][k],f[i][j]);
ans=0;
for(i=1;i<=n;i++)up(ans,f[m][i]);
printf("%d\n",ans);
}
}

  

I. Your Bridge is under Attack

因为点随机生成,所以对所有点建立KD-Tree。

对于每个查询操作,在KD-Tree上从根往下递归查找,若查询直线与当前点子树的最小包围矩形不相交,则显然无解,直接退出。

因为随机情况下答案很小,所以加上这条剪枝即可通过。

#include<cstdio>
#include<algorithm>
const int N=100010;
using namespace std;
typedef long long ll;
int Case,n,m,i,root,cmp_d,ans,A,B;
ll LB,LA,LC;
struct node{
int d[2];
int l,r;
int Max[2],Min[2];
int sum;
}t[N];
inline bool cmp(const node&a,const node&b){
return a.d[cmp_d]<b.d[cmp_d];
}
inline void umax(int&a,int b){if(a<b)a=b;}
inline void umin(int&a,int b){if(a>b)a=b;}
inline void up(int x){
if(t[x].l){
umax(t[x].Max[0],t[t[x].l].Max[0]);
umin(t[x].Min[0],t[t[x].l].Min[0]);
umax(t[x].Max[1],t[t[x].l].Max[1]);
umin(t[x].Min[1],t[t[x].l].Min[1]);
}
if(t[x].r){
umax(t[x].Max[0],t[t[x].r].Max[0]);
umin(t[x].Min[0],t[t[x].r].Min[0]);
umax(t[x].Max[1],t[t[x].r].Max[1]);
umin(t[x].Min[1],t[t[x].r].Min[1]);
}
}
int build(int l,int r,int D){
int mid=(l+r)>>1;
cmp_d=D;
nth_element(t+l+1,t+mid+1,t+r+1,cmp);
t[mid].Max[0]=t[mid].Min[0]=t[mid].d[0];
t[mid].Max[1]=t[mid].Min[1]=t[mid].d[1];
t[mid].sum=1;
if(l!=mid)t[mid].l=build(l,mid-1,!D);else t[mid].l=0;
if(r!=mid)t[mid].r=build(mid+1,r,!D);else t[mid].r=0;
up(mid);
return mid;
}
inline bool check(int xl,int xr,int yl,int yr){
ll t=-LB*xl+LC;
if(LA*yl<=t&&t<=LA*yr)return 1;
t=-LB*xr+LC;
if(LA*yl<=t&&t<=LA*yr)return 1;
t=-LA*yl+LC;
if(LB*xl<=t&&t<=LB*xr)return 1;
t=-LA*yr+LC;
if(LB*xl<=t&&t<=LB*xr)return 1;
return 0;
}
void ask(int x){
if(!check(t[x].Min[0],t[x].Max[0],t[x].Min[1],t[x].Max[1]))return;
if(LB*t[x].d[0]+LA*t[x].d[1]==LC)ans++;
if(t[x].l)ask(t[x].l);
if(t[x].r)ask(t[x].r);
}
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d%d",&t[i].d[0],&t[i].d[1]);
root=build(1,n,0);
while(m--){
scanf("%d%d",&A,&B);
LA=A;
LB=B;
LC=LA*LB;
ans=0;
ask(root);
printf("%d\n",ans);
}
}
}

  

J. Super Brain

按题意模拟即可。

#include<cstdio>
const int N=1000010;
int Case,n,i,a[N],b[N],f[N],g[N],ans;
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]),f[a[i]]=g[a[i]]=0;
for(i=1;i<=n;i++)scanf("%d",&b[i]),f[b[i]]=g[b[i]]=0;
for(i=1;i<=n;i++)f[a[i]]++;
for(i=1;i<=n;i++)g[b[i]]++;
for(i=1;i<=n;i++)if(f[a[i]]==1&&g[a[i]]==1)ans=a[i];
for(i=1;i<=n;i++)if(f[b[i]]==1&&g[b[i]]==1)ans=b[i];
printf("%d\n",ans);
}
}

  

ZOJ Monthly, March 2018的更多相关文章

  1. ZOJ 4010 Neighboring Characters(ZOJ Monthly&comma; March 2018 Problem G,字符串匹配)

    题目链接  ZOJ Monthly, March 2018 Problem G 题意  给定一个字符串.现在求一个下标范围$[0, n - 1]$的$01$序列$f$.$f[x] = 1$表示存在一种 ...

  2. ZOJ 4009 And Another Data Structure Problem(ZOJ Monthly&comma; March 2018 Problem F,发现循环节 &plus; 线段树 &plus; 永久标记)

    题目链接  ZOJ Monthly, March 2018 Problem F 题意很明确 这个模数很奇妙,在$[0, mod)$的所有数满足任意一个数立方$48$次对$mod$取模之后会回到本身. ...

  3. ZOJ Monthly&comma; March 2018 题解

    [题目链接] A. ZOJ 4004 - Easy Number Game 首先肯定是选择值最小的 $2*m$ 进行操作,这些数在操作的时候每次取一个最大的和最小的相乘是最优的. #include & ...

  4. ZOJ Monthly&comma; March 2018 Solution

    A - Easy Number Game 水. #include <bits/stdc++.h> using namespace std; #define ll long long #de ...

  5. ZOJ Monthly&comma; January 2018 训练部分解题报告

    A是水题,此处略去题解 B - PreSuffix ZOJ - 3995 (fail树+LCA) 给定多个字符串,每次询问查询两个字符串的一个后缀,该后缀必须是所有字符串中某个字符串的前缀,问该后缀最 ...

  6. ZOJ Monthly&comma; March 2013

    A题 题目大意:给出一棵树,一开始节点值均为0,先要求完成在线操作:将某子树所有节点值取反,或者查询某子树总点权. 题解:很基础的线段树题,既然两个操作都是子树操作,那么就先树链剖分一下,将子树操作转 ...

  7. ZOJ Monthly&comma; January 2018

    A 易知最优的方法是一次只拿一颗,石头数谁多谁赢,一样多后手赢 #include <map> #include <set> #include <ctime> #in ...

  8. ZOJ Monthly&comma; January 2018 Solution

    A - Candy Game 水. #include <bits/stdc++.h> using namespace std; #define N 1010 int t, n; int a ...

  9. ZOJ Monthly&comma; June 2018 Solution

    A - Peer Review Water. #include <bits/stdc++.h> using namespace std; int t, n; int main() { sc ...

随机推荐

  1. php防止外链导出的代码

    先收藏起来再说! URL跳转代码 1.代码: <? $url=$_GET["url"];header("Location:"."http://& ...

  2. NetLink Communication Mechanism And Netlink Sourcecode Analysis

    catalog . Netlink简介 . Netlink Function API Howto . Generic Netlink HOWTO kernel API . RFC Linux Netl ...

  3. 下拉刷新列表添加SwipeDismissListViewTouchListener实现滑动删除某一列。

    <Android SwipeToDismiss:左右滑动删除ListView条目Item> Android的SwipeToDismiss是github上一个第三方开源框架(github上的 ...

  4. Compare the value of entity field&period;

    public class Program { static void Main(string[] args) { Program p = new Program(); p.Test(); Consol ...

  5. 源码分析——从AIDL的使用开始理解Binder进程间通信的流程

    源码分析——从AIDL的使用开始理解Binder进程间通信的流程 Binder通信是Android系统架构的基础.本文尝试从AIDL的使用开始理解系统的Binder通信. 0x00 一个AIDL的例子 ...

  6. XXX系统项目目标文档课堂讨论

    XXXX重大技术征集系统 1.讨论结果: 2.项目目标文档 A目标: 1. 实现普通用户在线需求填报,个人信息管理,需求结果查看. 2. 实现审核员用户的需求审核,需求查看浏览和生成图表结果. 3. ...

  7. 知识点:Java 内存模型完全解密

    Java虚拟机(JVM) 规范中定义了一种Java的内存模型,即Java Memoory Model(简称JMM),用来实现让Java程序在各个平台下都能达到一致的内存访问效果. JVM是整个虚拟机, ...

  8. &lbrack;CocoaPods&rsqb;故障排除

    安装CocoaPods 如果您在macOS 10.9.0-10.9.2上安装,当RubyGems尝试安装jsongem 时可能会遇到问题.要解决此问题,请遵循以下说明 从macOS 10.8升级到10 ...

  9. AutoMapper在MVC中的运用小结

    配置.单元测试.AOP注入 Decimal转换成String类型 源数组转换成目标数组 源中的集合(数组)属性转换成目标中的集合(数组)属性 子类父类间的映射 源字典集合转换成目标字典集合 枚举映射 ...

  10. Tomcat的error-page掩盖action实例化的exception

    在使用Struts2+Spring+Tomcat开发的时候,为了避免骚扰用户,线上系统我们一般会定义错误处理页面.但是如果开发环境中也这么做(在web.xml定义了错误转发页面),而碰巧某个actio ...