【解题报告】NOIP2013

Day1

T1 转圈游戏

思路

我们手模发现，就是 x+m×10k mod nx+m \times 10^k \space mod \space n

然后一个快速幂就没了，开 long long

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int n,m,k,x;
long long ksm(long long a,long long b,int p)
{
	long long ans=1%p;
	for( ;b;b>>=1)
	{
		if(b&1)
		ans=(long long)ans*a%p;
		a=(long long)a*a%p; 
	}
	return ans;
}
int main()
{
	cin>>n>>m>>k>>x;
	cout<<(ksm(10,k,n)*m%n+x%n)%n<<endl;
	return 0;
}

T2 火柴排队

思路

值域树状数组

我们要使得 ∑(ai−bi)2\sum (a_i-b_i)^2 最小

变形一下
∑(ai2+2aibi+bi2)=∑(ai2+bi2)+∑2aibi \sum (a_i^2+2a_ib_i+b_i^2) \\= \sum (a_i^2+b_i^2)+\sum2a_ib_i
我们发现 ∑(ai2+bi2)\sum (a_i^2+b_i^2) 是一个定值，所以我们只需要让 ∑2aibi\sum 2a_ib_i 最小就好了

如何让两个数列的 2aibi2a_ib_i 最小呢

我们可以让两个序列中的数字各自标上排名

然后如果两个数列的数字的排名相对应，我们就可以让它最小

比如说

2 3 1 4

3 2 1 4

我们只需要交换一次

再比如

1 3 4 2

1 7 2 4

我们让他们对应，也就是将第二个序列中的 7 2 4 变成 4 7 2 ，交换两次

那我们就以第一个数列为基准，对于这个数列我们就可以离散化一下，表示排名，然后建立两个数列间的类似于最长公共子序列的 O(n2)O(n^2) 的做法的方法来建立一一映射的关系

值域树状数组求逆序对即可

这样就做完了

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=500005;
const int mod=99999997;
int tree[maxn],rank[maxn],n;
long long ans;
struct point{
	int num,val;
}a[maxn],b[maxn];
int lowbit(int x)
{
	return x&(-x);
}
bool cmp(point q,point w)
{
	if(q.val==w.val)
	return q.num<w.num;
	return q.val<w.val;
}
void add(int x,int y)
{
	for( ;x<=n;x+=lowbit(x)) tree[x]+=y,tree[x]%=mod;
}
int ask(int x)
{
	int ans=0;
	for( ;x;x-=lowbit(x)) ans+=tree[x],ans%=mod;
	return ans;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].val;
		a[i].num=i;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>b[i].val;
		b[i].num=i;
	}
	sort(a+1,a+1+n,cmp);
	sort(b+1,b+1+n,cmp);
	for(int i=1;i<=n;i++)
	rank[a[i].num]=b[i].num;
	for(int i=1;i<=n;i++)
	{
		add(rank[i],1);
		ans+=(i-ask(rank[i]));
		ans%=mod;
	}
	cout<<ans<<endl;
	return 0;
}

T3 货车运输

思路

最大生成树 + LCA

我们要求的是每一条路径中最小边的最大值，这个最大值肯定会加入最大生成树，所以我们做一个最大生成树

然后，对于这棵树，我们倍增预处理每一条边到自己的 kk 级祖先的答案，然后我们用倍增 lcalca 来合并答案

然后就没了

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath> 
using namespace std; 

const int maxn=10005;
const int INF=999999999;

struct edge1{  
    int x,y,dis;
}ed1[50005]; 
struct edge2{
    int to,next,w;
}ed2[100005];
int cnt,n,m,head[maxn],deep[maxn],f[maxn],fa[maxn][21],w[maxn][21];
bool vis[maxn]; 
void add_edge(int from, int to, int w)
{
    ed2[++cnt].next=head[from];
    ed2[cnt].to=to;
    ed2[cnt].w=w;
    head[from]=cnt;
    return ;
}

bool cmp(edge1 x, edge1 y)
{
    return x.dis>y.dis; //将边权从大到小排序 
}

int find(int x)
{
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}

void kruskal()
{
    sort(ed1+1,ed1+m+1,cmp); 
    for(int i=1;i<=n;i++)
    f[i]=i;
    for(int i=1; i<=m; i++)
    if(find(ed1[i].x)!=find(ed1[i].y))
	{
        f[find(ed1[i].x)]=find(ed1[i].y);
        add_edge(ed1[i].x, ed1[i].y, ed1[i].dis);
        add_edge(ed1[i].y, ed1[i].x, ed1[i].dis); 
    }
    return ;
}

void dfs(int node)
{
    vis[node]=true;
    for(int i=head[node]; i; i=ed2[i].next)
	{
        int to=ed2[i].to;
        if(vis[to]) continue;
        deep[to]=deep[node]+1;
        fa[to][0]=node;
        w[to][0]=ed2[i].w;
        dfs(to);
    }
    return ;
}

int lca(int x, int y)
{
    if(find(x)!=find(y)) return -1;
    int ans=INF;
    if(deep[x]>deep[y]) swap(x,y);
    for(int i=20; i>=0; i--)
        if(deep[fa[y][i]]>=deep[x])
		{
            ans=min(ans, w[y][i]);
            y=fa[y][i];
        }
    if(x==y) return ans;
    for(int i=20; i>=0; i--)
        if(fa[x][i]!=fa[y][i])
		{
            ans=min(ans, min(w[x][i], w[y][i]));
            x=fa[x][i]; 
            y=fa[y][i];
        }
    ans=min(ans, min(w[x][0], w[y][0]));
    return ans;
}

int main()
{
    int x,y,z,q;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
	{
        cin>>x>>y>>z;
        ed1[i].x=x;
        ed1[i].y=y;
        ed1[i].dis=z;
    }
    kruskal();
    for(int i=1;i<=n;i++)
        if(!vis[i])
		{
            deep[i]=1; 
            dfs(i);
            fa[i][0]=i;
            w[i][0]=INF;
        }
    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
		{
            fa[j][i]=fa[fa[j][i-1]][i-1]; 
            w[j][i]=min(w[j][i-1], w[fa[j][i-1]][i-1]);
        }
    cin>>q;
    for(int i=1; i<=q; i++)
	{
		cin>>x>>y;
        cout<<lca(x,y)<<endl;
    }
    return 0;
}

Day2

T1 积木大赛

思路

贪心

每往后走一个，想着把前面所有的填到跟他一个高度，这样就是最小填的次数

别忘了加最开始的第一堆积木的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int n,a[100005];
long long ans=0;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)     
    cin>>a[i];
    for(int i=2;i<=n;i++)     
    if(a[i]>a[i-1]) 
    ans+=a[i]-a[i-1];
    cout<<ans+a[1];
    return 0;
}

T2 花匠

思路

真的贪心，假的DP

求一个最长波浪形子序列

贪心策略是，每个连续上升或者下降的子序列中，只有一个能选，所以我们直接统计一下波浪的数量，然后加上第一个就好了

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int n;
int fro,pro=0;
int ans;
int main()
{
	cin>>n;
	cin>>fro;
	for(int i=2;i<=n;i++)
	{
		int x;
		cin>>x;
		if(x==fro)
		continue;
		if(pro!=1&&x>fro)//上升 
		{
			ans++;
			pro=1;
		}
		else if(pro!=2&&x<fro)
		{
			ans++;
			pro=2;
		}
		fro=x;
	}
	ans++;
	cout<<ans<<'\n';
	return 0;
}

T3 华容道

BFS搜索加暴力巨恶心卡常

但说实话，正解我不会

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <deque>
using namespace std;
const int maxn=35;
inline 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-'0';
		c=getchar();
	}
	return x*f;
}
inline void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
struct node{
	int x,y,ddx,ddy,st;
};
int n,m,T;
int a[maxn][maxn];
bool vis[maxn][maxn][maxn][maxn];
int dx[]={0,0,1,0,-1};
int dy[]={0,1,0,-1,0};

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>T;
	for(register int i=1;i<=n;i++)
	{
		for(register int j=1;j<=m;j++)
		cin>>a[i][j];
	}
	while(T--)
	{
		deque <node> q;
		bool flag=false;
		memset(vis,false,sizeof(vis));
		int ex,ey,sx,sy,tx,ty;
		cin>>ex>>ey>>sx>>sy>>tx>>ty;

		node now;
		now=(node){sx,sy,ex,ey,0};
		vis[ex][ey][sx][sy]=true;
		q.push_back(now);
		while(q.size())
		{
			now=q.front();
			q.pop_front();
			int x=now.x;
			int y=now.y;
			int lx=now.ddx;
			int ly=now.ddy;
			if(x==tx&&y==ty) 
			{
				flag=true;
				cout<<now.st<<'\n';
				break;
			}
			
			int fx=lx+0,fy=ly+1;
			int vx,vy;
			if(fx<n||fy<m||fx>1||fy>1)
			{
				vx=x,vy=y;
				if(x==fx&&y==fy)
				vx=lx,vy=ly;
				if(a[fx][fy]&&!vis[fx][fy][vx][vy])
				{
					vis[fx][fy][vx][vy]=true;
					node nt;
					nt=(node){vx,vy,fx,fy,now.st+1};
					q.push_back(nt);
				}
			}
			
			fx=lx+1,fy=ly+0;
			if(fx<n||fy<m||fx>1||fy>1)
			{
				vx=x,vy=y;
				if(x==fx&&y==fy)
				vx=lx,vy=ly;
				if(a[fx][fy]&&!vis[fx][fy][vx][vy])
				{
					vis[fx][fy][vx][vy]=true;
					node nt;
					nt=(node){vx,vy,fx,fy,now.st+1};
					q.push_back(nt);
				}
			}
			
			fx=lx+0,fy=ly-1;
			if(fx<n||fy<m||fx>1||fy>1)
			{
				vx=x,vy=y;
				if(x==fx&&y==fy)
				vx=lx,vy=ly;
				if(a[fx][fy]&&!vis[fx][fy][vx][vy])
				{
					vis[fx][fy][vx][vy]=true;
					node nt;
					nt=(node){vx,vy,fx,fy,now.st+1};
					q.push_back(nt);
				}
			}
			
			fx=lx-1,fy=ly+0;
			if(fx<n||fy<m||fx>1||fy>1)
			{
				vx=x,vy=y;
				if(x==fx&&y==fy)
				vx=lx,vy=ly;
				if(a[fx][fy]&&!vis[fx][fy][vx][vy])
				{
					vis[fx][fy][vx][vy]=true;
					node nt;
					nt=(node){vx,vy,fx,fy,now.st+1};
					q.push_back(nt);
				}
			}
		}
		if(!flag) 
		cout<<-1<<'\n';
	}
	return 0;
}