noip 2016

P1563 玩具谜题

模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
using namespace std;
int i;
int n,m;
int a[101000];
char b[101000][13];
int x,y;
int k;
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%d %s",&a[i],&b[i]);
}
k=1;
for (i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
if ((a[k]==0&&x==0)||(a[k]==1&&x==1))
{
y%=n;
if (k-y<=0) k+=n;
k-=y;
} else
if ( (a[k]==0&&x==1)||(a[k]==1&&x==0))
{
y%=n;
k+=y;
k=(k-1)%n+1;
}
}
printf("%s",b[k]);

return 0;
}

P1600 天天爱跑步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!isdigit(s));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(isdigit(s)) {k=k*10+(s^'0');s=getchar();}
return k*base;
}
inline void write(int x)
{
if(x<0) {putchar('-');write(-x);}
else {if(x/10)write(x/10);putchar(x%10+'0');}
}
const int maxn=300030;
const int N=300000;
int n,m,maxde;
int to[maxn<<1],ne[maxn<<1],po[maxn],lb;//链式前向星
int to1[maxn<<1],ne1[maxn<<1],po1[maxn],bh[maxn<<1],id;//询问
int vis1[maxn<<1];//标记询问是否被访问
struct node
{
int u,v,lca,len;
} a[maxn]; //询问相关
int w[maxn];//观测时间
inline void add(int x,int y)//加边
{
lb++;
to[lb]=y;ne[lb]=po[x];po[x]=lb;
lb++;
to[lb]=x;ne[lb]=po[y];po[y]=lb;
}
inline void add_q(int x,int y,int z)//询问,z:标号
{
id++;
to1[id]=y;bh[id]=z;ne1[id]=po1[x];po1[x]=id;
id++;
to1[id]=x;bh[id]=z;ne1[id]=po1[y];po1[y]=id;
}
int deep[maxn];//深度
bool vis[maxn];//标记点是否访问
int fa[maxn];//父亲
vector<int> js[maxn],js1[maxn],js2[maxn];
int mk[maxn],ans[maxn],tong[maxn<<1];
//mk[i]:以i为起点的询问个数 ans[i]:询问i的答案
int gf(int x)
{
if (fa[x]==x) return x;
fa[x]=gf(fa[x]); return fa[x];
}
inline void tarjan(int x)
{
fa[x]=x;
vis[x]=true;
for (int i=po[x];i;i=ne[i])
{
if (vis[to[i]]) continue;
deep[to[i]]=deep[x]+1;
if (deep[to[i]]>maxde) maxde=deep[to[i]];
tarjan(to[i]);
fa[to[i]]=x;//合并
}
for (int i=po1[x];i;i=ne1[i])
if (!vis1[i]&&vis[to1[i]])
{
vis1[i]=vis1[i^1]=1;//标记
a[bh[i]].lca=gf(to1[i]);//lca
a[bh[i]].len=deep[x]+deep[to1[i]]-(deep[a[bh[i]].lca]<<1);//算出len
}
}
void dfs(int x)
{//deep[s]=deep[i]+w[i]
//cout<<x<<" ";
int now,pre;
now=deep[x]+w[x];
if (now<=maxde) pre=tong[now];//记录目前的
for (int i=po[x];i!=0;i=ne[i]) if (deep[to[i]]>deep[x]) dfs(to[i]);
tong[deep[x]]+=mk[x];//把以点x为起点的加进去
if (now<=maxde) ans[x]+=tong[now]-pre;差值=ans
for (int i=js[x].size()-1;i>=0;i--) --tong[js[x][i]];//因为在lca处就往下走了,不会网上传答案
}
void dfs2(int x)
{//a[i].len-deep[a[i].v]=w[i]-deep[i]
int now=w[x]-deep[x]+N,pre;
pre=tong[now];
for (int i=po[x];i;i=ne[i]) if (deep[to[i]]>deep[x]) dfs2(to[i]);
for (int i=js2[x].size()-1;i>=0;i--) ++tong[js2[x][i]+N];//记左边的
ans[x]+=tong[now]-pre;
for (int i=js1[x].size()-1;i>=0;i--) --tong[js1[x][i]+N];
}
int main()
{
n=read();m=read();id=1;
for (int i=1;i<n;i++) add(read(),read());
for (int i=1;i<=n;i++) w[i]=read();
for (int i=1;i<=m;i++)
{
a[i].u=read();a[i].v=read();
if (a[i].u!=a[i].v) add_q(a[i].u,a[i].v,i);
else {a[i].lca=a[i].u;a[i].len=0;}
}
deep[1]=1;
tarjan(1);
/*for (int i=1;i<=m;i++)
{
printf("%d %d\n",a[i].lca,a[i].len);
}*/

for (int i=1;i<=m;i++)
{
++mk[a[i].u];
js[a[i].lca].push_back(deep[a[i].u]);
}
dfs(1);
//for (int i=1;i<=n;i++) printf("%d ",ans[i]);
memset(tong,0,sizeof(tong));
for (int i=1;i<=m;i++)
{
int f1=a[i].len-deep[a[i].v];
js1[a[i].lca].push_back(f1);
js2[a[i].v].push_back(f1);
}
dfs2(1);
for (int i=1;i<=m;i++)
{
if (deep[a[i].u]-deep[a[i].lca]==w[a[i].lca]) --ans[a[i].lca];
}

for (int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}

P1850 换教室

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
int n,m,v,e;//n 表示这个学期内的时间段的数量;m 表示牛牛最多可以申请更换多少节课程的教室;v 表示牛牛学校里教室的数量;e表示牛牛的学校里道路的数量。
int c[2010],d[2010];
double k[2010];
double f[310][310];
double dp[2010][2010][2];
//dp[i][j][0]表示选了前i节课的教室,申请了换j间,0表示没申请换教室,1表示申请了换教室
int X,Y,Z,mm;
int main()
{
n=read();m=read();v=read();e=read();
for (int i=1;i<=n;i++) c[i]=read();
for (int i=1;i<=n;i++) d[i]=read();
for (int i=1;i<=n;i++) scanf("%lf",&k[i]);
for (int i=1;i<=v;i++)
for (int j=1;j<=v;j++) f[i][j]=2333333333.0;
for (int i=1;i<=e;i++)
{
X=read();Y=read();Z=read();
f[X][Y]=min(f[X][Y],Z*1.0);//连边
f[Y][X]=min(f[Y][X],Z*1.0);
}
for (int i=1;i<=v;i++) f[i][i]=0.0;
for (int kk=1;kk<=v;kk++)
for (int i=1;i<=v;i++)
if (kk!=i)
{
for (int j=1;j<=v;j++)
if (i!=j&&j!=kk&&f[i][kk]+f[kk][j]<f[i][j]) f[i][j]=f[i][kk]+f[kk][j];
}//预处理两两教室间的距离
for (int i=0;i<=n;i++)//预处理
for (int j=0;j<=m;j++) dp[i][j][1]=111111111.0,dp[i][j][0]=1111111111.0;
dp[1][0][0]=0.0;
dp[1][1][1]=0.0;
for (int i=2;i<=n;i++)
{
mm=min(m,i);
dp[i][0][0]=dp[i-1][0][0]+1.0*f[c[i-1]][c[i]];
for (int j=1;j<=mm;j++)
{
dp[i][j][0]=min(dp[i-1][j][0]+1.0*f[c[i-1]][c[i]] ,
dp[i-1][j][1]+f[c[i-1]][c[i]]*(1.0-k[i-1])+1.0*f[d[i-1]][c[i]]*k[i-1]);
//没有申请换教室(2种情况:上节课申请了换教室和上节课没申请换教室
dp[i][j][1]=min(dp[i-1][j-1][0]+f[c[i-1]][d[i]]*k[i]+f[c[i-1]][c[i]]*(1.0-k[i]),
dp[i-1][j-1][1]+f[c[i-1]][c[i]]*(1.0-k[i])*(1.0-k[i-1])+f[c[i-1]][d[i]]*(1.0-k[i-1])*k[i]+f[d[i-1]][c[i]]*(1.0-k[i])*k[i-1]+f[d[i-1]][d[i]]*k[i]*k[i-1]);
//申请了换教室:上节课没申请换教室和上节课申请了换教室

}
}
double ans=dp[n][0][0];
for (int i=1;i<=m;i++) //找答案
{
ans=min(min(dp[n][i][0],dp[n][i][1]),ans);
}
printf("%.2lf",ans);
return 0;
}

P2822 组合数问题

全部预处理出来。
组合数的递推式可以自己推。
n个物品中取m个物品,若不取这个物品,则从n-1,m推过来,若取这个物品则从n-1,m-1推过来。
所以 $f[i][j]=f[i-1][j-1]+f[i-1][j]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<iostream>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
long long f[2011][2011];
long long h[2011],l[2011];
long long ff[2011][2011];
long long n,m,k,t,i,j;
int main()
{
scanf("%d%d",&t,&k);
f[0][0]=1;//初始化
for (i=1;i<=2001;i++)
{ f[i][0]=1;
for (j=1;j<=i;j++)
{
f[i][j]=(f[i-1][j-1]+f[i-1][j])%k;//递推求组合数,记得去模!
if (f[i][j]==0) //是k的倍数
{
h[i]++;//统计,h[i]是存第i行有多少个符合条件的组合数
}
ff[i][j]=ff[i-1][j]+h[i];//ff[i][j]是存对于n=i,m=j时候的方案数的
if (j==i) ff[i][j]=h[i]+ff[i-1][j-1];//特判一下
}
}
while (t--)
{
scanf("%d%d",&n,&m);//读入
if (m>n) m=n;//题目说明了0 <= j <= min(i,m),也就是m应要<=n;
printf("%d\n",ff[n][m]);//输出
}
return 0;
}

P2827 蚯蚓

开始用优先队列搞,然后发现太慢了.然后就(看了题解)知道每一种蚯蚓都具有单调性

以下说明来自题解

  • 我们会发现蚯蚓的切割具有单调性:一只蚯蚓切割后会分为 $\lfloor px \rfloor$和$x - \lfloor px \rfloor$ 两个部分,对于其中的任意一个部分,在某一时刻切割出的那只蚯蚓必然会比在它之后切割出来的蚯蚓要长
  • 我们用反证法对此予以证明:
  • 设某一时刻被选出的某只蚯蚓切割前的长度为 $a_i$,经过 $N$ 秒后,假设存在一只之前未被切割过的蚯蚓这一秒切割完后长度最大,我们记其NN秒前的长度为 $a_j$,那么 $a_i$, $a_j$必然要满足(我们先只考虑切割出的$\lfloor px \rfloor$ 那部分蚯蚓,$x - \lfloor px \rfloor$ 同理):
  • $a_i \times p + N \times q \le (a_j + N \times q) \times pai×p+N×q≤(aj+N×q)×p$
  • 分配后得到 $a_i \times p + N \times q \le a_j \times p + N \times q \times p$
  • 又因为 $N$ 秒前长度为 $a_i$ 的蚯蚓被选出,所以那一时刻满足 $a_i \ge a_j$,而 $p$ 的取值范围为 $0 < p < 10<p<1$,所以必然满足
  • $a_i \times p + N \times q > a_j \times p + N \times q \times p$
  • 与之前的假设矛盾,因此上述情况不可能存在,我们证得蚯蚓的切割具有单调性
  • 考虑记录三个队列,分别存储未切割过的蚯蚓和切割成的两只蚯蚓,每次将蚯蚓插入对应的队尾。根据我们上面推论得出的单调性,每次取出三个队头的最大值即可,蚯蚓长度的增加和上述堆做法的处理方式相同,这样的总复杂为 $O(n + m)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long read()
{
char s;
long long k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
const int maxn=1e5+20;
long long n,m,q,u,v,t;
long long x1,x2,x3;
long long a[maxn],x,y;
queue<long long> q1,q2,q3;
bool cmp(long long A,long long B)
{
return A>B;
}
int main()
{
n=read();m=read();q=read();u=read();v=read();t=read();
for (ll i=1;i<=n;i++) a[i]=read();
sort(a+1,a+n+1,cmp);
for (ll i=1;i<=n;i++) q1.push(a[i]);
for (ll i=1;i<=m;i++)
{
if (!q1.empty()) x1=q1.front();else x1=-210322333333333;
if (!q2.empty()) x2=q2.front();else x2=-210322333333333;
if (!q3.empty()) x3=q3.front();else x3=-210322333333333;
if (x1>x2&&x1>x3)
{
x=x1;
q1.pop();
} else
if (x2>x3)
{
x=x2;
q2.pop();
} else
{
x=x3;
q3.pop();
}
x+=q*(i-1);
if (i%t==0) printf("%lld ",x);
y=x*u*1.0/(1.0*v);
x-=y;
y-=q*i;
x-=q*i;
q2.push(y);
q3.push(x);
}
printf("\n");
x=0;
for (int i=1;i<=n+m;i++)
{
if (!q1.empty()) x1=q1.front();else x1=-210322333333333;
if (!q2.empty()) x2=q2.front();else x2=-210322333333333;
if (!q3.empty()) x3=q3.front();else x3=-210322333333333;
if (x1>x2&&x1>x3)
{
x=x1;
q1.pop();
} else
if (x2>x3)
{
x=x2;
q2.pop();
} else
{
x=x3;
q3.pop();
}
x+=q*m;
if (i%t==0)
{
printf("%lld ",x);
}
}
return 0;
}

P2831 愤怒的小鸟

开始解方程解错了(看成了y=a^x+b)
然后10分
然后解对了方程,95分
看了下前面部分,没错
难道是dp错了?!
凸(艹皿艹 ),真的是dp错了
1110可以由0011转移过来
然而我写的是1110-0011(二进制)
变成了1011和0011可以转移到1110,
哇,这错了还有95分,noip的数据真是太水了
这道题范围挺小的(所以dfs可以骗95分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const int M=(1<<18);
int T,n,m,id,M1;
int Map[20];
double x[20],y[20];
double a[430],b[430];
int bj[430];
int f[M+10];
int f1;
int main()
{
T=read();
Map[1]=1;
for (int i=2;i<=19;i++) Map[i]=Map[i-1]<<1;
while (T--)
{
memset(f,1,sizeof(f));
memset(bj,0,sizeof(bj));
f[0]=0;
id=0;
f1=0;
n=read();m=read();
M1=(1<<n)-1;
for (int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
for (int i=1;i<=n;i++)
{
for (int j=i+1;j<=n;j++)
{
if (fabs(x[i]-x[j])<=0.0000000000001) continue;//同一列的情况
id++;
a[id]=(y[j]*x[i]-y[i]*x[j])/(x[j]*x[i]*(x[j]-x[i]));
b[id]=(y[i]/x[i]-a[id]*x[i]);//求出a,b
if (a[id]>=-0.000000001) //a要<0,然后uoj卡精度
{
id--;
continue;
}
bj[id]|=Map[i];
bj[id]|=Map[j];
for (int k=1;k<=n;k++)
{
if (k==i||k==j) continue;
if (fabs(a[id]*x[k]*x[k]+b[id]*x[k]-y[k])<=0.0000000000001)
bj[id]|=Map[k];
}//标记第id根抛物线可以打掉多少个点
f1|=bj[id];
}
id++;
bj[id]=Map[i];
}
for (int i=1;i<=id;i++)
{
for (int j=M1-bj[i];j>=0;j--)
f[j|bj[i]]=min(f[j|bj[i]],f[j]+1);//dp转移,就是一个背包
}
printf("%d\n",f[M1]);
}
return 0;
}