【解题报告】NOIP2017

Day1

T1 小凯的疑惑

思路

这个是当年选手最后悔的也是大部分人能猜出来但是无法严格证明的题目

我来证明一下

好吧，我不会

但我们直接打表找规律，发现答案就是 ab−a−bab-a-b

1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;
long long a,b;
int main()
{
	cin>>a>>b;
	cout<<a*b-a-b<<endl;
	return 0;
}

T2 时间复杂度

思路

巨大模拟

字符串处理

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
string a,b;
int c,d,e,f[30],g[30],h,k,l[105],m,n,T;
void init()
{
	c=d=m=n=e=h=k=0;   
    memset(f,0,sizeof(f));
	memset(l,0,sizeof(l));
}
int main()
{
    cin>>T;
    while(T>0)
    {
    	T--;
    	init();
		while(b[0]!='O')
		{
			a=b;
			cin>>b;
		}
        for(int i=0;i<a.length();i++) 
		c=c*10+a[i]-'0'; 
        for(int i=4;i<b.length()-1;i++) 
		d=d*10+b[i]-'0';
        while(c>0)
        {
            c--;
			cin>>a;  
            if(a[0]=='F')   
            {
                e++;
				cin>>a; 
                if(f[a[0]-96]) 
				e=-1;    
                else
				{
					f[a[0]-96]=1;
					g[e]=a[0]-96; 
				}
                cin>>a>>b;      
                if(a[0]!='n'&&b[0]=='n'&&k==0) 
				{
					h++;
					l[e]=1;
				}   
				else if(((a.length()==b.length()&&a>b)||(a.length()>b.length())||(a[0]=='n'&&b[0]!='n'))&&k==0)
				{
					k=1;
					n=e;
				}
            }
			else
            {
                m=max(m,h);
				f[g[e]]=0;  
                if(l[e]==1) 
				{
					h--;
					l[e]=0;    
				}
                e--; 
                if(n>0&&e<n)
                {
                	k=0;
                	n=0;
				}
            }
            if(e==-1) 
			{
				cout<<"ERR"<<'\n';
				c=-1;
			}
        }
        if(e>0)
        cout<<"ERR"<<'\n';
        if(e==0&&m==d) 
		cout<<"Yes"<<'\n';
        if(e==0&&m!=d) 
		cout<<"No"<<'\n'; 
    }
    return 0;
}

T3 逛公园

思路

用 dfs(x,len)dfs(x,len) 表示到第 xx 个点 ，现在还可以走 lenlen 个距离

所以 dfs(x,len)=dfs(y,dis[x]+len−dis[y]−z)dfs(x,len)=dfs(y,dis[x]+len-dis[y]-z )

其中 y∈son(x)y \in son(x)

我们标记走过的节点，如果第第二次经过的话，也就是有一个零环，那我们就返回负一

然后我们枚举下一个位置，看是否能不能继续走，如果找到零环的话那就返回呗

如果找到的话，说明找到了第一个点，我们建的是反图，要从后往前走

然后就用死了的spfa

好难啊

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#define int long long
using namespace std;
const int maxn=100005;
int T;
int dis[maxn],f[maxn][51];
int n,m,k,p;
bool vis[maxn][51];
struct node{
	int to,value;
};
vector<node> g1[maxn],g2[maxn];
int dfs(int x,int len)
{
	int ans=0;
	if(len<0||len>k)
	return 0;
	if(vis[x][len])
	{
		vis[x][len]=false;
		return -1;
	}
	if(f[x][len]!=-1) 
	return f[x][len];
	vis[x][len]=true;
	for(int i=0;i<g2[x].size();i++)
	{
		int y=g2[x][i].to;
		int z=g2[x][i].value;
		int val=dfs(y,dis[x]+len-dis[y]-z);
		if(val==-1)
		{
			vis[x][len]=false;
			return -1;
		}
		ans=(ans+val)%p;
	}
	vis[x][len]=false;
	if(x==1&&len==0) 
	ans++;
	f[x][len]=ans;
	return ans;
}
void spfa()
{
	memset(dis,0x3f3f3f,sizeof(dis));
	memset(f,-1,sizeof(f));
	queue<int> q;
	q.push(1);
	dis[1]=0;
	while(q.size())
	{
		int x=q.front(); 
		q.pop();
		for(int i=0;i<g1[x].size();i++)
		{
			int y=g1[x][i].to;
			int z=g1[x][i].value;
			if(dis[y]>dis[x]+z)
			{
				dis[y]=dis[x]+z;
				q.push(y);
			}
		}
	}
}

int sol()
{
	cin>>n>>m>>k>>p;
	for(int i=1;i<=n;i++)
	{
		g1[i].clear(); 
		g2[i].clear();
	}
    while(m--)
	{
    	int x,y,z;
    	cin>>x>>y>>z;
        g1[x].push_back(node{y,z});
        g2[y].push_back(node{x,z});
    }
	spfa();
	int ans=0;
	for(int i=0;i<=k;i++)
	{
		int val=dfs(n,i);
		if(val==-1) 
		return -1;
		ans=(ans+val)%p;
	}
	return ans;
}
signed main()
{
	cin>>T;
	while(T--) 
	cout<<sol()<<'\n';
	return 0;
}

Day2

T1 奶酪

思路

球相切的判定以及并查集，没了

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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
struct node{
	long long high,low;
	long long x,y,z;
};
long double dist(node p,node q)
{
	return (long double)sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)+(p.z-q.z)*(p.z-q.z));
}
//并查集
int f[100010];
int get(int x)
{
	return f[x]=(x==f[x]? x:get(f[x]));
}
void merge(int x,int y)
{
	f[get(x)]=get(y);
}
void init()
{
	for(int i=1;i<=100000;i++)
	f[i]=i;
}
//并查集
int T; 
int main()
{
	cin>>T;
	while(T--)
	{
		init();
		long long n,h,r;
		cin>>n>>h>>r;
		node a[1005];
		for(int i=1;i<=n;i++)
		cin>>a[i].x>>a[i].y>>a[i].z; 
		int highest[1005]={0};
		int tot1=0;
		int lowest[1005]={0};
		int tot2=0; 
		for(int i=1;i<=n;i++)
		{
			a[i].high=a[i].z+r;
			a[i].low= a[i].z-r;
			if(a[i].high>=h)
			{
				++tot1;
				highest[tot1]=i;
			}
			if(a[i].low<=0)
			{
				++tot2;
				lowest[tot2]=i;
			}
			for(int j=i;j<=n;j++)
			{
				if(dist(a[i],a[j])<=2*r)
				merge(i,j);
			}
		}
		bool flag=false;
		for(int i=1;i<=tot1;i++)
		{
			for(int j=1;j<=tot2;j++)
			{
				if(get(highest[i])==get(lowest[j]))
				{
					flag=true;
					cout<<"Yes"<<endl;
					break;
				}
			}
			if(flag) break;
		}
		if(flag) continue;
		else
		cout<<"No"<<endl;
	}
	return 0;
}

T2 宝藏

思路

状态压缩DP或者模拟退火

设 f[s]f[s] 是表示在状态 ss 的时候，使得这些点满足要求的最小的代价

所以有

f[1<<(j−1)∣s]=f[s]+dis[i]×G[i][j]f[1<<(j-1)|s]=f[s]+dis[i]\times G[i][j]

其中 G[i][j]G[i][j] 表示 i,ji,j 建的距离

dis[i]dis[i] 表示根节点到 ii​​ 的距离

然后我们枚举每一个点是不是会被选，然后枚举就好了，对每个点为根进行dfs和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
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>
#define int long long
using namespace std;
const int maxn=15;
const int INF=1e9;
int n,m,maxx;
int g[maxn][maxn];
int dis[maxn],ans=INF;
int f[maxn][1<<maxn][maxn];
inline void dfs(int s,int sum,int dep)
{
	if(sum>=ans)
	return ;
	if(s==maxx)
	{
		ans=sum;
		return ;
	}
	for(int i=1;i<=n;i++)
	{
		if(!(1<<(i-1)&s))
		continue;
		for(int j=1;j<=n;j++)
		{
			if(!(1<<(j-1)&s)&&g[i][j]<INF)
			{
				if(f[j][1<<(j-1)|s][dep+1]<=sum+dis[i]*g[i][j])
				continue;
				f[j][1<<(j-1)|s][dep+1]=sum+dis[i]*g[i][j];
				dis[j]=dis[i]+1;
				dfs(1<<(j-1)|s,f[j][1<<(j-1)|s][dep+1],dep+1);
			}
		}
	}
}
signed main()
{
	cin>>n>>m;
	maxx=(1<<n)-1;
	memset(g,0x3f3f3f,sizeof(g));
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		g[x][y]=g[y][x]=min(g[x][y],z);
	}
	for(int i=1;i<=n;i++)
	{
		memset(dis,0,sizeof(dis));
		memset(f,0x3f3f3f,sizeof(f));
		dis[i]=1;
		dfs(1<<(i-1),0,0);
	}
	cout<<ans<<'\n';
	return 0;
}

T3 列队

思路

我们可以用动态开点线段树

我们对 nn 行除去最后一列建立线段树，编号为 11 到 n−1n-1 ，最后一行为 00 ，然后最后一列是编号为 nn

这样我们每次走人的时候，就只用操作每一行的末尾和每一列的了

不是特别懂

但是前面三十分似乎很好拿

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#define int long long
using namespace std;
const int maxn=300005;
int n,m,q;
int mx;
int cnt;
int root[maxn];
vector <int> g[maxn];
struct node{
	int ls,rs,tot;
}t[maxn<<4];
int upquery(int &p,int l,int r,int k)
{
	if(!p)
	p=++cnt;//开点 
	t[p].tot++;//这个数的结点加一个 
	if(l==r) return l;//如果找到了，返回 
	int mid=(l+r)>>1;
	int lsize=mid-l+1;//左子树的大小 
	if(t[p].ls)//如果有左子树的话 
	lsize-=t[t[p].ls].tot;//那就右子树等于总的减去左子树的大小 
	if(lsize>=k)//如果右子树的大小大于k的话，说明要找的在左子树 
	return upquery(t[p].ls,l,mid,k);//那么我们就继续往下找，直到找到为止 
	else
	{
		k-=lsize;//如果小于的话，我们就继续找，直到找到为止 
		return upquery(t[p].rs,mid+1,r,k);
	}
}
signed main()
{
	cin>>n>>m>>q;
	mx=max(n,m)+q;
	for(int i=1;i<=q;i++)
	{
		int x,y;
		cin>>x>>y;
		if(y==m)
		{
			int pos=upquery(root[n+1],1,mx,x);//为第n+1颗树，然后从1到max，找到x的位置 
			int id;
			if(pos<=n)//如果这个位置小于n的话 
			id=pos*m;//那么他就在m行的这个位置 
			else//反之 
			id=g[n+1][pos-n-1];//他就在另一个位置 
			g[n+1].push_back(id);//把这个人加回去 
			cout<<id<<'\n';//好，输出 
		}
		else
		{
			int pos=upquery(root[x],1,mx,y);//如果不在第m列呢？ 
			int idx,idy;
			if(pos<m)//那我们就找到一个位置，也就是y 
			idx=x*m-m+pos;//这样就是他横坐标的编号 
			else
			idx=g[x][pos-m];//否则和上面同理 
			pos=upquery(root[n+1],1,mx,x);
			if(pos<=n)//然后就是纵坐标的编号 
			idy=pos*m;//同理 
			else
			idy=g[n+1][pos-n-1];
			g[x].push_back(idy);
			g[n+1].push_back(idx);//两个都插回去 
			cout<<idx<<'\n';//横坐标的编号就是它的序号 
		}
	}
	return 0;
}