NOIP2017TG Solution

\(Naive\)选手爆零记

NOIP2017 D1T1小凯的疑惑

luogu P2737麦香牛块Beef McNuggets 原题弱化版。

数论题,个人感觉并没有什么意义(在NOIP上考)既不考查代码能力,也只会增加其他人的翻车几率(逃 代码如下:

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

这边给出证明。

定理: 对于正整数\(p,q\)满足\(gcd(p,q)=1\),我们有\(px+qy=n\)无非负整数解的最大正整数\(n\)\(pq−p−q\). 证明如下:

我们首先利用反证法, 证明\(px + qy \ne pq - p - q\): 我们假设存在正整数\(x\)\(y\)使得\(px + qy = pq - p - q\), 则有

\[px + qy = pq - p - q\] \[p(x + 1) + q(y + 1) = p\] \[\because gcd(p, q) = 1,p | q(y + 1)\] \[\therefore p | y + 1 \] 同理, \[q | x + 1\] 接着我们令\(y + 1 = pj\),$ x + 1 = qk$. 则有

\[pqk + qpj = pq \] \[pq(j + k) = pq\] 注意到\(x, y \ge 0\), 我们有\(y + 1 \ge 1\)\(x + 1 \ge 1\), 因而\(j \ge 1\)\(k \ge 1\). 因而\(j + k \ge 2\), 因而假设不成立.

得证.

证明转自

NOIP2017 D1T2时间复杂度

看到这道题就心疼,NOIP的时候并没有写出来,可能是因为并没有学栈的原因,所以当时没有写出来,今天学长们讲了栈,我就来把这道题A了 学长们还说递归可以A来着,好像还很简单 思路: 好像并没有什么思路,就是遇到\(F\)就就压栈,遇到\(E\)就把最上层的栈弹出,大概像循环嵌套,括号匹配,表达式求值都可以用栈实现吧! 传送门NOIP2013普及组 表达式求值,NOIP2005提高组T4 等价表达式(毒瘤题,数据很鬼畜) 代码如下

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
char ans[11][20],e[11][110][110];
int T,judge[1<<9],deepth,is[1<<9],top,maxdeepth,fff,ff;
//ff是一个标记,来记录是否有重读的变量
//fff也是一个标记,用于记录一个循环的初始值大于结束值的请况
//top表示当前栈指向哪一层
//maxdeepth用来记录此程序的循环嵌套的最大层数
//deepth用于更新
long long num[11][110][5],x;
int L,a,b,len,lennum,realdeepth;
//realdeepth就是输入所给的复杂度
struct node{int is,isdi,deep;}st[11][110];
//一个手写结构体的栈,用来记录状态
int main(){
//freopen("complexity.in","r",stdin);
//freopen("complexity.out","w",stdout);
scanf("%d",&T);
for(int i=1;i<=T;i++){
scanf("%d",&L);getchar();len=0;realdeepth=0;
while(true){
char s=getchar();
if(s=='\n')break;
if(s>='0'&&s<='9')realdeepth=realdeepth*10+s-'0';//算realdeepth
ans[i][++len]=s;
}
//memset(st,0,sizeof(st));
memset(judge,0,sizeof(judge));
memset(is,0,sizeof(is));
ff=0;top=0;maxdeepth=0;deepth=0;fff=1;a=0;b=0;
//每一组数据都要初始化所有的标记,不要忘
for(int j=1;j<=L;j++){
len=0;x=0;lennum=0;
while(true){
char s=getchar();
if(s!='\n'){
if(s>='0'&&s<='9')e[i][j][++len]=s,x=x*10+s-'0';
else if((s>='a'&&s<='z'&&s!='n')||(s<='Z'&&s>='A'))e[i][j][++len]=s;
else if(s=='n')e[i][j][++len]=s,x=1<<30;//n就标记为(1<<30)
else if(s==' '){
e[i][j][++len]=s;
if(x)num[i][j][++lennum]=x,x=0;
//我是直接把循环中的两个值提取出来了,用整形来存比较好用
}
}
else if(s=='\n'){
if(x)num[i][j][++lennum]=x,x=0;
break;
}
}
if(e[i][j][1]=='E')a++;//预判ERR
else if(e[i][j][1]=='F')b++;
}
if(a!=b){printf("ERR\n");continue;}
for(int j=1;j<=L;j++){
if(e[i][j][1]=='F'){
st[i][++top].isdi=e[i][j][3];
st[i][top].deep=deepth;//记录入栈时的deepth
if(judge[e[i][j][3]])ff=1;//重复就记录
else judge[e[i][j][3]]=1;//标记变量
if(ff)break;//退出循环
if(num[i][j][1]!=(1<<30)){//判断两个变量的初始值和末状态值
if(num[i][j][2]>=num[i][j][1]&&num[i][j][2]!=(1<<30))st[i][top].is=1;
else if(num[i][j][2]<num[i][j][1]&&num[i][j][2]!=(1<<30))st[i][top].is=-1;
//记录一个循环的初始值大于结束值的请况,且is=-1
else if(num[i][j][2]==(1<<30))st[i][top].is=2;//不是常数的话is为2
}
else if(num[i][j][1]==(1<<30)){
if(num[i][j][2]!=(1<<30))st[i][top].is=-1;//同理
else if(num[i][j][2]==(1<<30))st[i][top].is=1;
}
if(st[i][top].is==-1)fff--;
//把标记--,应为有可能多层都是不合法的循环(我一开始就是被这个坑了,结果debug了好长时间)
if(st[i][top].is==2&&fff==1)deepth++;//合法就更新deepth
maxdeepth=max(maxdeepth,deepth);//看是否可以更新maxdeepth
}
else if(e[i][j][1]=='E'){
if(st[i][top].is==-1)fff++;
judge[st[i][top].isdi]=0;
deepth=st[i][top].deep;
top--;
//还原所有的标记,有点像递归回溯
}
}
if(ff){printf("ERR\n");continue;}
if(ans[i][3]=='n'){
if(realdeepth==maxdeepth)printf("Yes\n");
else printf("No\n");
}
else if(ans[i][3]>='0'&&ans[i][3]<='9'){
if(maxdeepth==0)printf("Yes\n");
else printf("No\n");
}
//最后判断输出就没有什么好说的了
}
return 0;
}

NOIP2017 D2T1奶酪

这题嘛其实跟luogu上的一道题很像,因为被那道题卡了很久所以NOIp一下就想到了,但那道题是一个二维的,这个题改成了三维,这个几乎上是没有什么影响的,就是距离公式变了而已,还有就是那道题是要构造最小生成树,而NOIp的这道只用判断两个边界是否联通就好了,其实NOIp的比luogu上的这道还好写一些传送门 P1783 海滩防御

主要思路

将所有点都存入一个数组,然后把两个边界都存进去,然后跑一个\(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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#define ll long long
using namespace std;
int T,n,h,r,fa[1100];
struct node{int x,y,z;}t[21][1100];
int findx(int x){
if(fa[x]==x)return fa[x];
return fa[x]=findx(fa[x]);//并查集压缩路径(mmp考试的时候太紧张了把压缩路径敲掉了,直接return findx(fa[x])掉了50分还是60分,心疼啊!!所以压缩路径一定不能掉)
}
void mergex(int x,int y){fa[findx(x)]=findx(y);}//合并函数
double dis(int x,int y,int z,int x2,int y2,int z2){
ll disx,disy,disz;
disx=(ll)(x-x2)*(x-x2);disy=(ll)(y-y2)*(y-y2);disz=(ll)(z-z2)*(z-z2);
return sqrt(disx+disz+disy);
}
//这个是求两点之间距离的函数,值得一提的是这个函数要用到开方,但是开方的运算量是很大的,也就是常数很大,要是出题人搞几组毒瘤数据估计又要死一片(比如说我),所以你可以改成return 一个乘积,代码我也会贴到下面(不过是我高二学长的)
int main(){
//freopen("cheese.in","r",stdin);
//freopen("cheese.out","w",stdout);
scanf("%d",&T);
for(int i=1;i<=T;i++){
scanf("%d%d%d",&n,&h,&r);
for(int j=0;j<=n+1;j++)fa[j]=j;
for(int j=1;j<=n;j++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
t[i][j].x=x;t[i][j].y=y;t[i][j].z=z;
}t[i][n+1].z=h;
for(int j=0;j<=n+1;j++)
for(int k=0;k<=n+1;k++){
int x,y,z,x2,y2,z2,disr=r*2;
x=t[i][j].x;y=t[i][j].y;z=t[i][j].z;
x2=t[i][k].x;y2=t[i][k].y;z2=t[i][k].z;
if(j==0||j==n+1){x=x2,y=y2;disr=r;}//边界特判
if(k==0||k==n+1){x2=x,y2=y;disr=r;}//边界特判
double dist=dis(x,y,z,x2,y2,z2);
if(dist<=disr)mergex(j,k);//如果可以就合并然后
}
if(findx(0)==findx(n+1))printf("Yes\n");//如果联通就输出
else printf("No\n");
}
return 0;
}

PS:我这个代码一看就很low,也很慢跑了800多ms,下面再来看看我学长的代码,这个只跑了150ms

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int maxn = 1e4;
typedef long long ll;
struct Point {
int x, y, z;
void read() {
scanf("%d%d%d", &x, &y, &z);
}
}p[maxn];
struct MFS {
int fa[maxn];
void clear(int x) {
for (int i = 1; i <= x; i++) fa[i] = i;
}
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
if (find(x) == find(y)) return;
fa[find(x)] = find(y);
}
}s;
ll dis(Point a, Point b) {
ll x = (ll)a.x - b.x;
ll y = (ll)a.y - b.y;
ll z = (ll)a.z - b.z;
return x * x + y * y + z * z;
}
int main() {
//freopen("cheese.in", "r", stdin);
//freopen("cheese.out", "w", stdout);
int T; scanf("%d", &T);
while (T--) {
int n, h, r; scanf("%d%d%d", &n, &h, &r);
int S = n + 1, T = n + 2;
ll R = ((ll)r * 2) * ((ll)r * 2);
s.clear(n + 2);
for (int i = 1; i <= n; i++) {
p[i].read();
if ((ll)p[i].z - r <= 0) s.merge(i, S);
if ((ll)p[i].z + r >= h) s.merge(i, T);
}
bool suc = false;
for (int i = 1; i <= n && !suc; i++)
for (int j = i + 1; j <= n && !suc; j++)
if (dis(p[i], p[j]) <= R) {
s.merge(i, j);
if (s.find(S) == s.find(T)) suc = true;
}
if (s.find(S) == s.find(T)) suc = true;
if (suc) printf("Yes\n");
else printf("No\n");
}
return 0;
}
/*
5
1 6 4293
3 3 -2
1 9 866
-4 4 3
1 9 3171
2 0 -3
1 10 1940
1 0 -5
1 8 4150
1 0 -4
*/

一看就很高端,还把最小生成树(MFS)封装了,我也不是很懂,dalao就看看把!!! ## D2T2 宝藏 这道题一看就应该是状压DP,这道题的题目就不多赘述了 用dp[i]来表示状态i下的最优方案,dis[j]表示j到根节点的距离(题目中所描述的K)用dfs来更新答案,下面直接上代码,代码附注释

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define inf 2147483647
using namespace std;
int dp[1<<13],dis[15],G[15][15],isG[15][15],n,m,ans=inf;
//isG表示x,y之间是否有边
//点只有十二个直接上邻接矩阵即可
void insert(int x,int y,int w){G[x][y]=w;G[y][x]=w;isG[x][y]=1;isG[y][x]=1;}
//插边函数
void dfs(int x){
for(int i=1;i<=n;i++){
//枚举你所选点集中的每个点
if((1<<(i-1))&x){
for(int j=1;j<=n;j++){
if(!(1<<(j-1)&x)&&isG[i][j])
//判断能否选
if(dp[1<<(j-1)|x]>dp[x]+dis[i]*G[i][j]){
//有没有更新的必要
int temp=dis[j];
dis[j]=dis[i]+1;
dp[1<<(j-1)|x]=dp[x]+dis[i]*G[i][j];
dfs(1<<(j-1)|x);
dis[j]=temp;
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
memset(G,63,sizeof(G));//赋较大初值
for(int i=1;i<=m;i++){
int x,y,w;scanf("%d%d%d",&x,&y,&w);
if(w<G[x][y])insert(x,y,w);
}
for(int i=1;i<=12;i++){
memset(dis,63,sizeof(dis));
for(int j=1;j<=(1<<n)-1;j++)dp[j]=inf;
//每枚举一遍根节点就重置一遍
dis[i]=1;dp[1<<(i-1)]=0;
dfs(1<<(i-1));
ans=min(ans,dp[(1<<n)-1]);//看答案是否能更新
}
printf("%d",ans);
return 0;
}