YAOI Round #7 题解
前言
比赛链接：
Div.1 : http://47.110.12.131:9016/contest/16
Div.2 : http://47.110.12.131:9016/contest/15
Div.2——Angel Beats!
下面是 Div.2 的题解。
A. Favorite Flavor
对于 \(40\%\) 的数据，考虑 \(O(n)\) 预处理，然后 \(O(1)\) 求解，时间复杂度为 \(O(n+q)\)。
对于 \(100\%\) 的数据，考虑在线处理，即模拟题意过程，时间复杂度为 \(O(q\log n)\)
但实际上，本题有 \(O(\log^3 n+q)\) 的做法，即预处理的时候考虑分别枚举 \(2,3,5\) 的次幂，然后 \(O(1)\) 求解。
scanf("%d",&q);
while(q--)
{
ans=0;
scanf("%lld",&n);
while(n%5==0) ans+=3,n/=5;
while(n%3==0) ans+=2,n/=3;
while(n%2==0) ans+=1,n/=2;
if(n>1) continue;
else res^=ans;
}
printf("%d",res);
B. Dancer in the Dark
对于 \(40\%\) 的数据，枚举所有情况，时间复杂度约为 \(O(n^m)\)。
对于 \(100\%\) 的数据，我们容易算得答案为 \(m^n-m\times (m-1)^{n-1}\)，于是快速幂求解即可，时间复杂度为 \(O(\log n)\)。
printf("%d",((qpow(m,n)-1ll*m*qpow(m-1,n-1))%mod+mod)%mod);
C. In Your Memory
咕咕咕……
D. Change the World
咕咕咕……
E. Stairway to Heaven
对于 \(20\%\) 的数据，枚举每个数的颜色，时间复杂度为 \(O(n^n)\)，还需要稍微卡卡常。
对于 \(50\%\) 的数据，我们仔细思考一下这个问题，它其实就是求最长不上升子序列的长度（可以自己手模几组试试），于是随便 \(O(n^2)\) 求解。
对于 \(100\%\) 的数据，在求最长不上升子序列长度的时候考虑二分转移，或者树状数组维护，这都非常经典，时间复杂度为 \(O(n\log n)\)。
dp[m=1]=a[1];
for(Re int i=2;i<=n;i++)
{
if(dp[m]>a[i]) dp[++m]=a[i];
else dp[lower_bound(dp+1,dp+m+1,a[i],greater<int>())-dp]=a[i];
}
printf("%d",m);
Div.1——玉子市场
下面是 Div.1 的题解。
A. ドラマチックマーケットライド
咕咕咕……
B. ねぐせ
咕咕咕……
C. プリンシプル
这题出题人也想不出什么部分分做法，于是就不给部分分了（
我们只需要考虑在原图的一棵生成树上怎样构造答案即可。
由于图连通，故一定有解。
以 \(1\) 号节点为根，节点上的整数设为任意值，然后遍历一下原图。
当遍历到一条边 \((u,v,c)\) 时，若 \(num[u]=c\)，则 \(num[v]\not=num[u]\)；否则，\(num[v]=c\)。
这样做的话，得到的显然是连通的，时间复杂度为 \(O(n+m)\)。
inline void dfs(int u)
{
for(Re int i=hd[u];i;i=e[i].nxt)
{
int v=e[i].ver,c=e[i].val;
if(cl[v]) continue;
if(c==cl[u]) cl[v]=(cl[u]+1)%n+1;
else cl[v]=c;
dfs(v);
}
}
D. 星とピエロ
对于 \(20\%\) 的数据，考虑枚举第 \(k\) 小的数是哪一个，然后检验用显然的 DP 去做，时间复杂度为 \(O(n^2ms)\)。
对于 \(60\%\) 的数据，考虑在枚举第 \(k\) 小的数的时候二分一下，DP 不变，时间复杂度为 \(O(nms\log n)\)。
对于 \(100\%\) 的数据，考虑记录一个数组 \(nxt[i]\) 表示包含第 \(i\) 个点的线段最右端，然后去进行 DP 就会发现 \(m\) 没用了，时间复杂度为 \(O(ns\log n)\)。
#include<bits/stdc++.h>
#define Re register
using namespace std;
const int N=5005;
int n,m,s,k,a[N],aa[N],ans=-1;
int nxt[N],sum[N],f[N][N];
inline bool check(int mid)
{
memset(f,0,sizeof f);
for(Re int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+(a[i]<=aa[mid]);
}
for(Re int i=1;i<=s;i++)
{
for(Re int j=1;j<=n;j++)
{
f[i][j]=max(f[i][j],f[i-1][j]);
}
for(Re int j=0;j<=n;j++)
{
if(nxt[j])
{
f[i][nxt[j]]=max(f[i][nxt[j]],f[i-1][j-1]+sum[nxt[j]]-sum[j-1]);
}
}
for(Re int j=1;j<=n;j++)
{
f[i][j]=max(f[i][j],f[i][j-1]);
}
}
return f[s][n]>=k;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&k);
for(Re int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
aa[i]=a[i];
}
sort(aa+1,aa+n+1);
for(Re int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
for(Re int j=l;j<=r;j++)
{
nxt[j]=max(nxt[j],r);
}
}
int l=1,r=n,mid;
while(l<=r)
{
mid=l+r>>1;
if(!check(mid)) l=mid+1;
else ans=aa[mid],r=mid-1;
}
printf("%d",ans);
return 0;
}
E. うさぎ山から爱をこめて
咕咕咕……
最新文章
- EnumHelper.cs枚举助手（枚举描述信息多语言支持）C#
- 我的LaTeX中文文档模板
- Ionic2学习笔记（6）：Navigation
- 两个list 合并成新一个list
- 使用localResizeIMG微信压缩上传图片安卓报错 weixin://preInjectJSBridge/fail
- jQuery插件编写笔记
- Sandcastle----强大的C#文档生成工具
- Firebird 同一字段的多行合并为一行
- Elasticsearch之索引模板index template与索引别名index alias
- javascript的数组之slice()
- oracle去掉字符串中所有指定字符
- 【OCP|OCM】Oracle培训考证系列
- FeignClient使用
- 怎么使用 JavaScript 将网站后台的数据变化实时更新到前端
- 利用Angular.js从PHP读取后台数据
- 关于如何准备CKA考试
- python 清空列表
- Ubuntu14.04下部署FastDFS 5.08+Nginx 1.9.14
- 基于FPGA的DDR3多端口读写存储管理系统设计
- 清空oracle数据库