noip2016题解汇总
【uoj#260】玩具谜题
传送门
分析
模拟。
int n,m;
int dir[N]; char nam[N][L];
int a[M],s[M];
int now;
int Go(int now,int dir1,int len) {
int dirFin=(dir[now]^dir1);
if (!dirFin) now-=len; else now+=len;
now%=n; if (now<=0) now+=n;
return now;
}
int main(void) {
n=rd(),m=rd();
rep(i,1,n) {
dir[i]=rd();
scanf("%s",nam[i]+1);
}
rep(i,1,m) a[i]=rd(),s[i]=rd();
now=1;
rep(i,1,m)
now=Go(now,a[i],s[i]);
printf("%s\n",nam[now]+1);
}
【uoj#261】天天爱跑步
题意
分析
我们考虑一条路径\((u,v)\)的影响。设\(u,v\)的LCA为\(anc\),每个节点的深度为\(dep\)。
那么,分两种情况讨论:
①当\(i\)在\(u,anc\)上时,路径\((u,v)\)对\(i\)产生影响,当且仅当
\(dep[u]-dep[i]=w[i]\)
参变分离得:\(dep[u]=dep[i]+w[i]\)
②当\(i\)在\(anc,v\)上时,路径\((u,v)\)对\(i\)产生影响,当且仅当
\(dep[u]-dep[anc]+dep[i]-dep[anc]=dep[u]-2*dep[anc]+dep[i]=w[i]\)
参变分离得:\(dep[u]-2*dep[anc]=w[i]-dep[i]\)
由于情况①与情况②类似,所以我们只要解决了情况①,情况②便迎刃而解。
所以我们现在解决情况①。
我们对于每个点\(i\),求出\(p[i]=dep[i]+w[i]\)。
枚举每条路径\((u,v)\),对于满足\(dep[u]=p[i]\)的所有点\(i\),若\(i\)在\((u,anc)\)上,那么答案+1。
这样直接均摊为\(O(n)\)???!!!
mdzz考场上我就栽在这里了。
复杂度是:\(\sum_{i=1}^{路径条数}\lbrace i|p[i]=当前路径的u\rbrace\)
均摊下来并不是\(O(n)\)的,而是\(O(n^2)\)的。
那怎么办?
我们把所有点按照\(p\)从小到大排序。
把路径按照\(dep[u]\)排序。
那么对于两条链,我们每次处理上下两端连续的信息,用two pointer实现。
那么,对于当前的一条路径,我们把\((u,anc)\)上的每个点的点权+1。
然后有多个单点查询点权是多少。
通过树链剖分+树状数组实现。
就这样少了60pt。
【uoj#262】换教室
待补充...
【uoj#263】组合数问题
传送门
http://uoj.ac/problem/263
多组询问,求\(\sum_{i=0}^n\sum_{j=0}^{\min(i,m)}[k|C_i^j],n,m\leq 2000,k\leq 21\)
分析
\(\sum_{i=0}^n\sum_{j=0}^{\min(i,m)}[k|C_i^j]\\=\sum_{i=0}^n\sum_{j=0}^m [k|C_i^j]\\=\sum_{i=0}^n\sum_{j=0}^m [k|{i!\over j!(i-j)!}]\)
记\(can(k,i,j)=[k|{i!\over j!(i-j)!}]\)
我们只要快速预处理出\(can\),再在\(O(n^2)\)内求出前缀和,就可以支持\(O(1)\)查询了。
设\(k\)的分解为\({a_1}^{p_1}{a_2}^{p_2}...{a_m}^{p_m}\),
\([k|x]=\prod_{i=1}^m[{a_i}^{p_i}|x]\)
所以我们把\(k\)分解,先求出\(cnt(k,i)=i的阶乘中素因子k的个数\),然后即可处理处\(can\)的值。
核心代码
int k;
int ret[B],ned[B],tot;
int cnt[N][B];
int can[N][N];
int sum[N][N];
int cas;
int n,m;
void Split(int x) {
for (int i=2; i<=x; i++)
if (x%i==0) {
tot++;
ret[tot]=i;
ned[tot]=1;
x/=i;
while (x%i==0) ned[tot]++,x/=i;
}
}
int Get(int x,int d) {
int siz=0;
while (x>0) {
int t=x/d;
siz+=t;
x=t;
}
return siz;
}
int Check(int n,int m) { // k|C(n,m) ???
rep(b,1,tot) {
int t=cnt[n][b]-cnt[m][b]-cnt[n-m][b];
if (t<ned[b]) return 0;
}
return 1;
}
int main(void) {
cas=rd(),k=rd();
Split(k);
rep(i,1,U_N) {
rep(b,1,tot)
cnt[i][b]=Get(i,ret[b]);
}
rep(i,0,U_N) rep(j,0,i)
if (Check(i,j))
can[i][j]=1;
rep(i,0,U_N) rep(j,0,i) sum[i][j]=can[i][j];
rep(i,1,U_N) sum[0][i]+=sum[0][i-1];
rep(i,1,U_N) sum[i][0]+=sum[i-1][0]; //Get Border
rep(i,1,U_N) {
rep(j,1,U_N)
sum[i][j]+=sum[i][j-1];
}
rep(i,1,U_N) {
rep(j,1,U_N)
sum[i][j]+=sum[i-1][j];
}
rep(tms,1,cas) {
n=rd(),m=rd();
int res=sum[n][m];
printf("%d\n",res);
}
}
【uoj#264】蚯蚓
传送门
分析
开始的时候被跳蚤吓到了...
因为跳蚤一般都是NOI难度的。
实际上被吓到了之后就太紧张了,简单的合并果子都不会做了,就这样又少了40pt。
然后发育畸形的\(m=0\)的蚯蚓导致我的输出也畸形了,又少了15pt。
很直观的想法就是用优先队列优化模拟。用delta记共同增量。
但是很明显会TLE。
发现自己还有一个特性没有使用:每次加入队列的是由原来的数生成的,而且一定会比原来小。
开三个单调队列。
队列1:原长
队列2:\(\lfloor px\rfloor\)队列
队列3:\(x-\lfloor px\rfloor\)队列
为什么单调?因为每次截出来的蚯蚓长度都是递减的。
类似于哈夫曼树的建立啊。
只不过Huffman树是两条单调队列的。
核心代码:优先队列
int n;
int a[N];
int m;
int u,v;
double p;
int q;
int t;
int del;
priority_queue<int> que;
int main(void) {
n=rd();
m=rd(),q=rd(),u=rd(),v=rd();
p=(double)u/v;
t=rd();
rep(i,1,n) a[i]=rd();
rep(i,1,n) que.push(a[i]);
del=0;
rep(tms,1,m) {
int now=que.top();
now+=del;
que.pop();
int a=(floor)(now*p),b=now-a;
del+=q;
que.push(a-del),que.push(b-del);
if (tms%t==0) {
printf("%d",now);
if (tms+t>m) printf("\n");
else printf(" ");
}
}
rep(tms,1,n+m) {
int now=que.top();
now+=del;
que.pop();
if (tms%t==0) {
printf("%d",now);
if (tms+t>n+m) printf("\n");
else printf(" ");
}
}
}
核心代码:单调队列
#include <cstdio>
#include <cstring>
#include <cctype>
#include <climits>
#include <cmath>
#include <algorithm>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
typedef long long LL;
const int N=131072;
const int M=10000000;
const int MIN=INT_MIN;
int n,m,q,u,v,t;
int a[N];
int del;
struct Queue {
int q[M]; int qh,qt;
Queue(void) {
memset(q,0,sizeof q);
qh=1,qt=0;
}
void Add(int x) {
q[++qt]=x;
}
void Pop(void) {
q[qh++]=0;
}
int Top(void) {
return q[qh];
}
int Empty(void) {
return qh>qt;
}
}q1,q2,q3;
int rd(void) {
int x=0,f=1; char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
int cmp(int a,int b) {
return a>b;
}
Queue *PreChosen(Queue *a,Queue *b,Queue *c) {
int mx=MIN;
if (!(*a).Empty())
mx=max(mx,(*a).Top());
if (!(*b).Empty())
mx=max(mx,(*b).Top());
if (!(*c).Empty())
mx=max(mx,(*c).Top());
if (!(*a).Empty()&&mx==(*a).Top())
return a;
else if (!(*b).Empty()&&mx==(*b).Top())
return b;
else return c;
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("uoj#264.in","r",stdin);
freopen("uoj#264.out","w",stdout);
#endif
n=rd(),m=rd(),q=rd(),u=rd(),v=rd(),t=rd();
rep(i,1,n) a[i]=rd();
sort(a+1,a+n+1,cmp); rep(i,1,n) q1.Add(a[i]);
rep(i,1,m) {
Queue *now=PreChosen(&q1,&q2,&q3);
int facLen=(*now).Top()+del; (*now).Pop();
if (i%t==0) printf("%d ",facLen);
del+=q; q2.Add((LL)facLen*u/v-del); q3.Add(facLen-(LL)facLen*u/v-del);
}
printf("\n");
rep(i,1,n+m) {
Queue *now=PreChosen(&q1,&q2,&q3);
int facLen=(*now).Top()+del; (*now).Pop();
if (i%t==0) printf("%d ",facLen);
}
printf("\n");
return 0;
}
【uoj#265】愤怒的小鸟
传送门
分析
状压dp。
设\(f[S]\)表示打掉状态为\(j\)的猪的最小小鸟数。
由于所有鸟都要打掉,所以\(S\)中的状态转移为低位填满的。
转移有两种情况:①打掉一只 ②选择当前这只和另外一只打掉
转移方程自行脑补。
考场上由于精度问题少了20pt。
代码
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define per(i,a,b) for (int i=(a);i>=(b);i--)
const int N=32;
const int S=1048576;
const double EPS=1e-8;
int cas;
int n,m;
double x[N],y[N];
int full;
int f[S];
inline int rd(void)
{
int x=0,f=1; char c=getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
/*
a * xi * xi + b * xi = yi
a * xj * xj + b * xj = yj
a*(xi^2)*(xj^2) + b*xi*(xj^2) = yi*(xj^2)
a*(xi^2)*(xj^2) + b*(xi^2)*xj = yj*(xi^2)
b( xi*xj^2 - xi^2*xj ) = yi*(xj^2)-yj*(xi^2)
*/
inline int cmp(double a,double b)
{
if (fabs(a-b)<EPS) return 0;
return a<b?-1:1;
}
int Solve(double xi,double yi,double xj,double yj,double &a,double &b)
{
double t=xi*xj*xj-xi*xi*xj; if (!cmp(t,0)) return 0;
b=(yi*xj*xj-yj*xi*xi)/(xi*xj*xj-xi*xi*xj);
a=(yi-xi*b)/(xi*xi);
if (cmp(a,0)>=0) return 0; else return 1;
}
inline int OnLine(double xi,double yi,double a,double b)
{
double t=a*xi*xi+b*xi;
return !cmp(t,yi);
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("angrybirds.in","r",stdin);
freopen("angrybirds.out","w",stdout);
#endif
cas=rd();
rep(tms,1,cas)
{
memset(x,0,sizeof x); memset(y,0,sizeof y);
n=rd(),m=rd();
rep(i,1,n) scanf("%lf%lf",x+i,y+i);
full=(1<<n)-1;
fill(f,f+full+1,n+1); f[0]=0;
rep(st,0,full-1) //从低位到高位,第1个空位
{
int bit=1; while (st>>(bit-1)&1) bit++;
f[st|(1<<(bit-1))]=min(f[st|(1<<(bit-1))],f[st]+1);
rep(i,bit+1,n) if (!(st>>(i-1)&1))
{
double a,b; int tag=Solve(x[bit],y[bit],x[i],y[i],a,b); if (!tag) continue;
int nxST=st; rep(j,bit,n) if (OnLine(x[j],y[j],a,b)) nxST|=(1<<(j-1));
f[nxST]=min(f[nxST],f[st]+1);
}
}
printf("%d\n",f[full]);
}
return 0;
}
最新文章
- 快递Api接口 &; 微信公众号开发流程
- android 绑定spinner键值对显示内存地址的问题
- Android&mdash;&mdash;组件简介
- Java Hour 62 J2EE App 服务器
- 在WPF下快速生成线的方法
- Python学习第四天集合
- Java Web指导方向
- 8.PHP内核探索:再次探讨SAPI
- Codeforces Round #284 (Div. 2)
- 在Linux中,如何取出一个字符串的前5位
- js中replace的正则替换
- UMA - Unity Multipurpose Avatar
- Java Web开发中的名词解释
- 表达式求值(栈方法/C++语言描述)(三)
- 怎么给PDF去除页眉页脚
- 爬虫 requests 模块
- ElasticSearch权威指南学习(分布式搜索)
- 作用域&;作用域链和with,catch语句&;闭包
- Mysql的两种引擎
- Python练习笔记——计算输入日期为改年的第几天、星期几