noip 2013

  • P1965 转圈游戏
  • P1966 火柴排队
  • P1967 货车运输
  • P1969 积木大赛
  • P1970 花匠
  • P1979 华容道

    P1965 转圈游戏

    模拟
    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
    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<cstring>
    #include<map>
    #include<set>
    #include<list>
    #include<cmath>
    #include<vector>
    #include<algorithm>
    using namespace std;
    long long n,m,k,x,sum,ans;//n个人,走m位置,10^k个循环,位置x
    void pow()//10的k次方
    {
    sum=10;ans=m;
    while (k!=0)
    {
    if (k%2==1) ans=ans*sum%n;
    sum=sum*sum%n;
    k/=2;
    }
    return;
    }
    int main()
    {
    scanf("%lld%lld%lld%lld",&n,&m,&k,&x);
    pow();
    long long xx;
    xx=(x%n+ans)%n;
    cout<<xx;
    //printf("%lld",(x%n+ans)%n);
    return 0;
    }

P1966 火柴排队

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
#include<map>
#include<set>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct note
{
int x;
int d;
} a[100100];
note b[100100];
int f[100100];
int s[100100];
int sum,i;
const int p=99999997;
bool cmp(const note &aa,const note &bb)
{
if (aa.d>bb.d) return true;
else return false;
}

void qh(int x)//向下求和
{
while (x>0)
{
sum+=s[x];
sum%=p;
x-=x&(-x);
}
}
void xg(int x)//向上修改
{
while (x<=100000)
{
s[x]++;
x+=x&(-x);
}
}
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&a[i].d);
a[i].x=i;
}
for (i=1;i<=n;i++)
{
scanf("%d",&b[i].d);
b[i].x=i;
}
sort(a+1,a+n+1,cmp);//排序
sort(b+1,b+n+1,cmp);
for (i=1;i<=n;i++) f[a[i].x]=b[i].x;
for (i=n;i>=1;i--)
{
qh(f[i]);
xg(f[i]);
}
cout<<sum;
return 0;
}

P1967 货车运输

先求出最大生成树(其实就是最小生成树改个符号)
(因为最大瓶颈路径一定存在于最大生成树中)
然后用倍增求最小值.
因为图不一定是联通的,所以说搞个并查集维护2个点在不在一个集合,不在一个集合就输出-1

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#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,X,Y,Z;

struct node
{
int u,v,w;
} a[100010];
int lb;
int fa[10010];

int to[20010],w[20010],ne[20010],po[10010];
int id,Log,T;
int f[15][10010];//lca
int M[15][10010];//min
int deep[10010];

void add(int x,int y,int z)//最初加边
{
a[++lb].u=x;
a[lb].v=y;
a[lb].w=z;
}
bool cmp(node aa,node bb)
{
return aa.w>bb.w;
}
inline int gf(int x)
{
if (fa[x]==x) return x;
return fa[x]=gf(fa[x]);
}
void Add(int x,int y,int z)//重新建图加边
{
id++;
to[id]=y;w[id]=z;ne[id]=po[x];
po[x]=id;
}

void dfs(int x,int Fa)
{
X=gf(x);
deep[x]=deep[Fa]+1;//记录深度
for (int i=po[x];i;i=ne[i])
{
if (to[i]==Fa) continue;
f[0][to[i]]=x;
M[0][to[i]]=w[i];
Y=gf(to[i]);
fa[Y]=fa[X];

dfs(to[i],x);
}
}//扫一遍,求出每个节点的父节点
int lca(int x,int y)//求x到y的min
{
if (deep[x]<deep[y])
{
int TT=x;
x=y;
y=TT;
}//使x的深度>=y
int Min=1000000;
for (int i=0;i<Log;i++)
{
if (((deep[x]-deep[y])>>i)&1)
{
Min=min(Min,M[i][x]);
x=f[i][x];
}
}//使两者深度相同
if (x==y) return Min;
for (int i=Log-1;i>=0;i--)
{
if (f[i][x]!=f[i][y]&&f[i][x]!=-1&&f[i][y]!=-1)
{
Min=min(Min,M[i][y]);
Min=min(Min,M[i][x]);//更新Min
x=f[i][x];
y=f[i][y];
}
}//往上跳
if (x==y) return Min;
return min(Min,min(M[0][x],M[0][y]));
}
int main()
{
n=read();m=read();
for (int i=1;i<=m;i++)
{
X=read();Y=read();Z=read();
add(X,Y,Z);
}
sort(a+1,a+lb+1,cmp);
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=1;i<=lb;i++)
{
X=gf(a[i].u);
Y=gf(a[i].v);
if (X==Y) continue;
fa[X]=Y;
Add(a[i].u,a[i].v,a[i].w);
Add(a[i].v,a[i].u,a[i].w);
}//最大生成树

int nn=n;
while (nn)
{
nn/=2;
Log++;
}
for (int i=1;i<=n;i++) fa[i]=i;
memset(f,-1,sizeof(f));
memset(M,1,sizeof(M));
for (int i=1;i<=n;i++)
{
if (fa[i]==i) dfs(i,0);
}
for (int i=1;i<=Log;i++)
{
for (int j=1;j<=n;j++)
{
if (f[i-1][j]==-1) continue;
f[i][j]=f[i-1][f[i-1][j]];
if (f[i][j]==-1) continue;
M[i][j]=min(M[i-1][j],M[i-1][f[i-1][j]]);
}
}//预处理lca和min

T=read();
while (T--)
{
X=read();
Y=read();
if (gf(X)!=gf(Y))
{
printf("-1\n");
continue;
}
printf("%d\n",lca(X,Y));
}//询问
return 0;
}

P1969 积木大赛

楼下那种方法很简单。
我来说一种比较无聊的方法.
用并查集
最好的理解方法是把代码给模拟一遍。
这是一个图(图略)
2 3 4 1 2
论一块积木可以铺多长,也就是在这一行中,一直向左右两边延伸直到遇到一个大厦没有这么多层。
于是我们可以选择从上往下堆。
首先,我们将大厦高度从小到大排,记得存下每一积木原本的序号。
然后我们从最高的开始堆,我们每次都要将有这么积木都堆一块砖,
不过,相邻的两块可以一起堆,这时候,我们就将这2个大厦合并成起来,一起堆(所以接下来更矮的楼层也能一起堆),合并之后将要堆的大厦数量-1。如果旁边的大厦没有这么高的话,就不要合并(也就是代码中爸爸为空的,因为如果有这么高的话就会有爸爸)。
每堆一层都要加上需要的砖的块数。
最后输出结果。

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
/*
ID: ylx14271
PROG: 积木大赛
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int f[100010];
int n;
int i,j;
struct node
{
int b;
int x;
}a[100010];
int sum,num;
int p,k;
bool comp(const node &xx,const node &yy)
{
if (xx.x>yy.x) return true; else
if (xx.x==yy.x&&xx.b<yy.b) return true;
else return false;
}
int gf(int x)//并查集之找爸爸
{
return f[x]==x?x:f[x]=gf(f[x]);
}
void u(int x,int y)//合并
{
int fx=gf(x);
int fy=gf(y);
if (!fx||!fy) return;//有一幢大厦高度没有达到目前搜的高度(就是目前爸爸为空)
num--;//这层要堆的积木块数记得-1
if (fx!=fy) f[fx]=fy;//合并
return;
}
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&a[i].x);
a[i].b=i;//原本的序号
}
sort(a+1,a+n+1,comp);
k=1;
sum=0;
for (i=a[1].x;i;i--)//模拟从上往下堆积木
{
while (a[k].x==i)//积木刚好是这个高度
{
f[a[k].b]=a[k].b;//爸爸赋值为自己
num++;//这层要堆的积木+1
u(a[k].b-1,a[k].b);//和左边的合并
u(a[k].b+1,a[k].b);//和右边的合并
k++;//目前搜的第k座大厦
}
sum+=num;//统计积木数
}
cout<<sum;
return 0;
}

送一份楼下的贪心解法
第i个积木若最后的高度要大于i-1个积木,那么就需要多做两高度值之差的次数
应为与i-1个积木高度相同(或小于i-1个积木高度)的部分可以与i-1个积木一同做不需加多余的次数。

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
/*
ID: redbag
PROG: 1
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int n,a,s,i,x;
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&a);
s=s+max(0,a-x);
x=a;
}
cout<<s;
return 0;
}

P1970 花匠

下面这段话来自洛谷。
首先,我们要知道的是,比如题目给出的5 3 2 1 2,我们不难看出5 1 2,3 1 2,2 1 2,与其并没有半毛钱区别,所以,其实5 3 2这一段和单单一个数没什么差别。
知道这一点就好做了,考虑它的下降上升趋势,如果出现转折(比如题解的1,我们可以把它理解成一个波的转折点),那么就可以改变需要寻找的趋势继续做。
每次记录上一次的趋势,如果上一次是上升,下一次就是下降了2333,结果记得+1(这个很容易理解吧233)。
扯了半天其实这就是一个求波峰的题。

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

/*
ID: ylx14271
PROG: 花匠
LANG: C++
*/
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int a[1000010],n,i,t,s;
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
t=0;
for (i=2;i<=n;i++)
if (a[i]>a[i-1]&&t!=1)//上升
{
t=1;//标记
s++;
} else
if (a[i]<a[i-1]&&t!=-1)//下降
{
t=-1;
s++;
}
cout<<s+1;
return 0;
}

P1979 华容道