Codeforces Round #426 Div. 1
2024-10-15 08:25:46
A：考虑每个质因子，显然要求次数之和是3的倍数，且次数之差的两倍不小于较小的次数。对于第一个要求，乘起来看开三次方是否是整数即可。第二个取gcd，两个数分别除掉gcd，之后看两个数的剩余部分是否都能被gcd整除即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n;
ll cube(ll x)
{
return x*x*x;
}
signed main()
{
n=read();
while (n--)
{
int x=read(),y=read();
ll z=1ll*x*y,t=pow(z,1.0/3);
if (cube(t-1)==z||cube(t)==z||cube(t+1)==z)
{
ll u=gcd(x,y);
x/=u,y/=u;
//cout<<x<<' '<<y<<' '<<u<<endl;
if (u%x==0&&u%y==0) printf("Yes\n");
else printf("No\n");
}
else printf("No\n");
}
return 0;
//NOTICE LONG LONG!!!!!
}
B：显然有f[i][j]表示前i位分成j段的最大价值。考虑套路，在每个数最后一次出现的位置标1。这样转移时要查的就是后缀和与dp值的和的最大值。容易发现线段树区间加查查最大值就完了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 35010
#define M 55
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,m,f[N][M],a[N],pre[N],p[N],L[N<<2],R[N<<2],tree[N<<2],lazy[N<<2];
void up(int k){tree[k]=max(tree[k<<1],tree[k<<1|1]);}
void build(int k,int l,int r,int x)
{
L[k]=l,R[k]=r;lazy[k]=0;
if (l==r) {tree[k]=f[l][x];return;}
int mid=l+r>>1;
build(k<<1,l,mid,x);
build(k<<1|1,mid+1,r,x);
up(k);
}
void update(int k,int x)
{
tree[k]+=x;
lazy[k]+=x;
}
void down(int k)
{
update(k<<1,lazy[k]);
update(k<<1|1,lazy[k]);
lazy[k]=0;
}
void add(int k,int l,int r)
{
if (L[k]==l&&R[k]==r) {tree[k]++,lazy[k]++;return;}
if (lazy[k]) down(k);
int mid=L[k]+R[k]>>1;
if (r<=mid) add(k<<1,l,r);
else if (l>mid) add(k<<1|1,l,r);
else add(k<<1,l,mid),add(k<<1|1,mid+1,r);
up(k);
}
int query(int k,int l,int r)
{
if (L[k]==l&&R[k]==r) return tree[k];
if (lazy[k]) down(k);
int mid=L[k]+R[k]>>1;
if (r<=mid) return query(k<<1,l,r);
else if (l>mid) return query(k<<1|1,l,r);
else return max(query(k<<1,l,mid),query(k<<1|1,mid+1,r));
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read(),m=read();
for (int i=1;i<=n;i++)
{
a[i]=read();
pre[i]=p[a[i]];
p[a[i]]=i;
}
memset(f,200,sizeof(f));f[0][0]=0;
for (int j=1;j<=m;j++)
{
f[0][j]=0;
build(1,0,n,j-1);
for (int i=1;i<=n;i++)
{
add(1,pre[i],i-1);
f[i][j]=query(1,0,i-1);
}
}
cout<<f[n][m];
return 0;
//NOTICE LONG LONG!!!!!
}
C：注意到事实上答案并不会很大，于是暴力枚举每个尾巴判断是否合法即可。至于如何判断，逐位考虑，如果该位上下界相同就填上并继续考虑下一位，如果有可以既不卡上界又不卡下界的数显然就合法了，否则考虑是填上界还是下界，填完之后就只会有一个边界很好处理了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 20
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
ll l,r;
int n,m,s,a[N],b[N],f[N],g[N],ans;
bool calcup(int k)
{
for (int i=k;i>=0;i--)
{
if (i+1<s) return 0;
for (int j=1;j<f[i];j++)
if (a[j]) return 1;
if (f[i]&&i+1>s) return 1;
if (f[i]==0||a[f[i]])
{
if (f[i]) a[f[i]]--,s--;
}
else return 0;
}
return s==0;
}
bool calcdown(int k)
{
for (int i=k;i>=0;i--)
{
if (i+1<s) return 0;
for (int j=g[i]+1;j<10;j++)
if (a[j]) return 1;
if (g[i]==0||a[g[i]])
{
if (g[i]) a[g[i]]--,s--;
}
else return 0;
}
return s==0;
}
void get()
{
ans++;
//for (int i=1;i<=9;i++) cout<<b[i]<<' ';cout<<endl;
}
void check()
{
s=0;
for (int i=1;i<=9;i++) s+=a[i]=b[i];
for (int i=n-1;i>=0;i--)
{
if (i+1<s) return;
for (int j=g[i]+1;j<f[i];j++)
if (a[j]) {get();return;}
if (g[i]==f[i])
{
if (f[i])
{
if (!a[f[i]]) return;
a[f[i]]--;
s--;
}
}
else
{
if (a[f[i]])
{
int c[N];memcpy(c,a,sizeof(c));int tmps=s;
a[f[i]]--;s--;
if (calcup(i-1)) {get();return;}
memcpy(a,c,sizeof(a));s=tmps;
}
if (a[g[i]]||g[i]==0)
{
if (g[i]) a[g[i]]--,s--;
if (calcdown(i-1)) {get();return;}
}
return;
}
}
if (s==0) get();
}
void dfs(int k,int s)
{
if (k>9) {check();return;}
for (int i=0;i<=18-s;i++)
{
b[k]=i;
dfs(k+1,s+i);
}
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
cin>>l>>r;
while (r) f[n++]=r%10,r/=10;
while (l) g[m++]=l%10,l/=10;
dfs(1,0);
cout<<ans;
return 0;
//NOTICE LONG LONG!!!!!
}
D：考虑点分。点分时考虑每条由根下去的链被统计了几次。化一下限制的式子容易发现是一个二维数点，bit套treap维护。常数小时限大二维数点O(nlog3n)就跑过去了。只是码力弱如我场上根本写不完。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<ctime>
using namespace std;
#define ll long long
#define N 100010
#define P 1000000007
#define lson tree[k].ch[0]
#define rson tree[k].ch[1]
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,p[N],len[N],size[N],t,ans=1,mx,mn;
bool flag[N];
struct data{int to,nxt,len,color;
}edge[N<<1];
struct data2{int x,y,x1,y1;
}deep[N];
namespace bitreap
{
int root[N<<2],cnt=0;
struct data{int ch[2],p,x,s;}tree[N<<5];
void up(int k){tree[k].s=tree[lson].s+tree[rson].s+1;}
void move(int &k,int p)
{
int t=tree[k].ch[p];
tree[k].ch[p]=tree[t].ch[!p],tree[t].ch[!p]=k,up(k),up(t),k=t;
}
void ins(int &k,int x)
{
if (k==0) {k=++cnt;tree[k].p=rand();lson=rson=0;tree[k].x=x;tree[k].s=1;return;}
tree[k].s++;
if (tree[k].x<x) {ins(rson,x);if (tree[rson].p>tree[k].p) move(k,1);}
else {ins(lson,x);if (tree[lson].p>tree[k].p) move(k,0);}
}
void del(int &k,int x)
{
if (tree[k].x==x)
{
if (lson==0||rson==0) {k=lson|rson;return;}
if (tree[lson].p>tree[rson].p) move(k,0),del(rson,x);
else move(k,1),del(lson,x);
}
else if (tree[k].x<x) del(rson,x);
else del(lson,x);
up(k);
}
int query(int k,int x)
{
if (k==0) return 0;
if (tree[k].x<x) return query(rson,x);
else return tree[rson].s+1+query(lson,x);
}
void Insert(int k,int x){k-=mn;k++;while (k<=mx-mn+1) ins(root[k],x),k+=k&-k;}
void Delete(int k,int x){k-=mn;k++;while (k<=mx-mn+1) del(root[k],x),k+=k&-k;}
int Query(int k,int x)
{
k-=mn;int s=0;
while (k) s-=query(root[k],x),k^=k&-k;
k=mx-mn+1;
while (k) s+=query(root[k],x),k^=k&-k;
return s;
}
}
void addedge(int x,int y,int z,int c)
{
t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,edge[t].color=c,p[x]=t;
}
int ksm(int a,int k)
{
int s=1;
for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;
return s;
}
void makes(int k,int from)
{
size[k]=1;
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=from&&!flag[edge[i].to])
{
makes(edge[i].to,k);
size[k]+=size[edge[i].to];
}
}
int findroot(int k,int s,int from)
{
int mx=0;
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=from&&!flag[edge[i].to]&&size[edge[i].to]>size[mx]) mx=edge[i].to;
if ((size[mx]<<1)>s) return findroot(mx,s,k);
else return k;
}
void make(int k,int from)
{
mx=max(mx,deep[k].x);mx=max(mx,deep[k].y);
mn=min(mn,deep[k].x);mn=min(mn,deep[k].y);
mx=max(mx,deep[k].x1);mx=max(mx,deep[k].y1);
mn=min(mn,deep[k].x1);mn=min(mn,deep[k].y1);
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=from&&!flag[edge[i].to])
{
deep[edge[i].to].x=deep[k].x;
deep[edge[i].to].y=deep[k].y;
if (edge[i].color>0) deep[edge[i].to].x++,deep[edge[i].to].y-=2;
else deep[edge[i].to].y++,deep[edge[i].to].x-=2;
deep[edge[i].to].x1=deep[k].x1;
deep[edge[i].to].y1=deep[k].y1;
if (edge[i].color>0) deep[edge[i].to].x1--,deep[edge[i].to].y1+=2;
else deep[edge[i].to].y1--,deep[edge[i].to].x1+=2;
len[edge[i].to]=1ll*len[k]*edge[i].len%P;
make(edge[i].to,k);
}
}
void work(int k,int from,int x)
{
if (x==1) bitreap::Insert(deep[k].x1,deep[k].y1);
else bitreap::Delete(deep[k].x1,deep[k].y1);
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=from&&!flag[edge[i].to]) work(edge[i].to,k,x);
}
void calc(int k,int from)
{
ans=1ll*ans*ksm(len[k],bitreap::Query(deep[k].x,deep[k].y))%P;
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=from&&!flag[edge[i].to]) calc(edge[i].to,k);
}
void solve(int k)
{
makes(k,k);
k=findroot(k,size[k],k);
flag[k]=1;deep[k].x=deep[k].y=deep[k].x1=deep[k].y1=0;len[k]=1;mx=mn=0;make(k,k);
bitreap::cnt=0;
for (int i=0;i<=mx-mn+1;i++) bitreap::root[i]=0;
work(k,k,1);
for (int i=p[k];i;i=edge[i].nxt)
if (!flag[edge[i].to])
{
work(edge[i].to,edge[i].to,-1);
calc(edge[i].to,edge[i].to);
work(edge[i].to,edge[i].to,1);
}
for (int i=p[k];i;i=edge[i].nxt)
if (!flag[edge[i].to]) solve(edge[i].to);
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
srand(time(0));
n=read();
for (int i=1;i<n;i++)
{
int x=read(),y=read(),z=read(),c=read();if (c==0) c=-1;
addedge(x,y,z,c),addedge(y,x,z,c);
}
solve(1);
cout<<ans;
return 0;
//NOTICE LONG LONG!!!!!
}
E：下定义贡献为将某植物本来要经历的阴天变成了晴天。
由于删除线段的贡献与植物所需时间有关并不断增加，考虑扫描线，这样就能对每个前缀考虑删除线段的贡献了。过程中显然可以回答询问。
注意到被超过两条线段覆盖的区间是一定不能作出贡献的。事情变得简单了一点。
对线已扫过的部分，维护以下变量：
leni 单独删除第i条线段的贡献
crossi,j 恰被第i条线段和第j条线段覆盖的区间长度（显然只有O(n)对线段该值不为0）
valuei 删除第i条线段和当前右端点（即未扫完的线段右端点视为扫描线的位置）不在其之后的另一条线段的最大贡献
前两个变量用来辅助求出第三个变量，维护出第三个变量显然就能知道答案，也即当前最大的value。
考虑当前区间被几条线段覆盖。并用set维护出是哪些线段。
如果未被覆盖，显然可以直接计入晴天的时间。如果超过两条，显然不用管。
如果是两条，就更新其cross，并以此更新两线段的value。
如果只有一条，就更新其len。考虑对其value的更新。一方面，显然加上len的增加量，这样删除其和右端点在其之前的有交线段的最大贡献一定完成了更新。另一方面考虑选择它和其之前一条与其没有交的线段的最大贡献。这个东西显然随便拿一个数据结构都能维护了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define N 600010
#define lson tree[k].ch[0]
#define rson tree[k].ch[1]
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
typedef pair<int,int> pii;
int n,C,m,c[N],ans[N],len[N],ctrb[N],cnt,root;
struct data
{
int x,op,i;
bool operator <(const data&a) const
{
return x<a.x;
}
}a[N];
pii q[N];
set<int> cloud;
map<int,int> cross[N];
struct data2{int ch[2],p,x,v,mx;
}tree[N<<1];
void up(int k){tree[k].mx=max(max(tree[lson].mx,tree[rson].mx),tree[k].v);}
void move(int &k,int p)
{
int t=tree[k].ch[p];
tree[k].ch[p]=tree[t].ch[!p],tree[t].ch[!p]=k,up(k),up(t),k=t;
}
void ins(int &k,int x,int v)
{
if (k==0) {k=++cnt;tree[k].p=rand();tree[k].x=x;tree[k].mx=tree[k].v=v;return;}
tree[k].mx=max(tree[k].mx,v);
if (tree[k].x<x||tree[k].x==x&&tree[k].v<v) {ins(rson,x,v);if (tree[rson].p>tree[k].p) move(k,1);}
else {ins(lson,x,v);if (tree[lson].p>tree[k].p) move(k,0);}
}
void del(int &k,int x,int v)
{
if (tree[k].x==x&&tree[k].v==v)
{
if (lson==0||rson==0) {k=lson|rson;return;}
if (tree[rson].p>tree[lson].p) move(k,1),del(lson,x,v);
else move(k,0),del(rson,x,v);
}
else if (tree[k].x<x||tree[k].x==x&&tree[k].v<v) del(rson,x,v);
else del(lson,x,v);
up(k);
}
int query(int k,int x)
{
if (k==0) return 0;
if (tree[k].x>x) return query(lson,x);
else return max(query(rson,x),max(tree[lson].mx,tree[k].v));
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("e.in","r",stdin);
freopen("e.out","w",stdout);
#endif
srand(20020509);
n=read(),C=read();
for (int i=1;i<=n;i++)
{
int l=read(),r=read();c[i]=read();
a[i*2-1].x=l,a[i*2-1].op=1,a[i*2-1].i=i;
a[i*2].x=r,a[i*2].op=-1,a[i*2].i=i;
}
sort(a+1,a+n*2+1);
m=read();
for (int i=1;i<=m;i++) q[i].first=read(),q[i].second=i;
sort(q+1,q+m+1);
int x=0,tot=0,mx=0,s=0;a[n*2+1].x=2000000000;
for (int i=1;i<=n;i++) ins(root,c[i],0);
for (int i=1;i<=n*2+1;i++)
{
if (s==0) tot+=a[i].x-a[i-1].x;
if (s==1)
{
auto it=cloud.begin();
int x=*it;
del(root,c[x],len[x]);
len[x]+=a[i].x-a[i-1].x;
ctrb[x]+=a[i].x-a[i-1].x;
if (c[x]<=C)
{
ctrb[x]=max(ctrb[x],len[x]+query(root,C-c[x]));
mx=max(mx,ctrb[x]);
}
ins(root,c[x],len[x]);
}
if (s==2)
{
auto it=cloud.begin();
int x=*it;it++;int y=*it;
if (x>y) swap(x,y);
cross[x][y]+=a[i].x-a[i-1].x;
if (c[x]+c[y]<=C)
{
ctrb[x]=max(ctrb[x],cross[x][y]+len[x]+len[y]);
ctrb[y]=max(ctrb[y],cross[x][y]+len[x]+len[y]);
mx=max(mx,ctrb[y]);
}
}
while (x<m&&tot+mx>=q[x+1].first) x++,ans[q[x].second]=a[i].x-(tot+mx-q[x].first);
if (a[i].op==1) cloud.insert(a[i].i),s++;
else cloud.erase(a[i].i),s--;
}
for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
//NOTICE LONG LONG!!!!!
}
最新文章
- datepicker使用
- 深入理解PHP内核(五)函数的内部结构
- ACM 盗梦空间
- Folder Recursion with C#
- php判断爬虫
- RxJava + Retrofit 的实际应用场景
- 百度首页html代码
- 《Python基础教程（第二版）》学习笔记 -> 第四章 字典
- Android开发之启动Activity的最佳写法
- ios专题 - 委托模式实现
- wcf系列学习5天速成——第三天 分布性事务的使用 有时间再验证下 不同库的操作
- 利用Azure Automation实现云端自动化运维(4)
- Hadoop错误之namenode宕机的数据恢复
- oracle针对某列让特定信息排序[decode]
- SVN服务端和客户端的安装与搭建
- Python 爬虫 解析库的使用 --- Beautiful Soup
- 第二篇：SpringBoot2.0整合ActiveMQ
- HTML5视频播放插件Video.js使用详解
- Linux - iptable 限制 IP 访问端口
- docker使用以及dockerfile编写
热门文章
- Java性能优化之编程技巧总结
- SpringBoot整合Shiro使用Ehcache等缓存无效问题
- 2019年DNS服务器速度排行榜
- Golang-教程
- 闽江学院软件学院2016级JAVA构建之法-学生自学兴趣小组招募通知
- H5上传图片之canvas
- [python]解决Windows下安装第三方插件报错：UnicodeDecodeError: 'ascii' codec can't decode byte 0xcb in position 0:
- 在C 与 C++混编中, 出现error LNK2019: 无法解析的外部符号 "int __cdecl main_(int,char * *)" (?main_@@YAHHPEAPEAD@Z)，该符号在函数 main 中被引用
- [转帖]CS、IP和PC寄存器
- [转帖]一段关于Unix与 Linux的暗黑史