noip2017

day1

T1 小凯的疑惑

题意

小凯手中有两种面值的金币,其面值分别为a,b,两种面值均为正整数且彼此互质。每种金币小凯都有无数个。在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中,最贵的价值是多少?注意:输入数据保证存在小凯无法准确支付的商品。

分析

最直接的方式是打表找规律,得出答案就是$a\times b -a -b$的结论,输出即可。

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll a,b;
scanf("%lld%lld",&a,&b);
printf("%lld\n",a*b-a-b);
return 0;
}

T2 时间复杂度

题意

小明正在学习一种新的编程语言 A++,刚学会循环语句的他激动地写了好多程序并给出了他自己算出的时间复杂度,可他的编程老师实在不想一个一个检查小明的程序,于是你的机会来啦!下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。

A++语言的循环结构如下:

1
2
3
4
5
F i x y
循环体
E

其中“F i x y”表示新建变量 (i 变量 i 不可与未被销毁的变量重名)并初始化为 x,然后判断 i 和 y 的大小关系,若 i 小于等于 y 则进入循环,否则不进入。每次循环结束后 i 都会被修改成 i +1,一旦 i 大于 y 终止循环。

x 和 y 可以是正整数(x 和 y 的大小关系不定)或变量 n。n 是一个表示数据规模的变量,在时间复杂度计算中需保留该变量而不能将其视为常数,该数远大于100。

E”表示循环体结束。循环体结束时,这个循环体新建的变量也被销毁。

注:本题中为了书写方便,在描述复杂度时,使用大写英文字母“O”表示通常意义下“Θ”的概念。

分析

这题还是比较好想的(其实就是模拟)

先读入,然后对于循环体考虑建图,从内层循环向外建图,每次找到一个没有入度的点即为某个循环的最内层,沿着图遍历出一条链(因为一个循环只能从属于一个上级循环,所以一定是一条链),然后对这条链反向遍历,更新答案。

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 <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <climits>
#include <cassert>
#include <cctype>
using namespace std;
inline int readint()
{
char c;int tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
inline void writeout(int x)
{
if(x==0) {putchar('0');return;}
if(x<0) {putchar('-');x=-x;}
static char s[21];int idx=0;
while(x>0) s[++idx]=x%10+'0',x/=10;
while(idx) putchar(s[idx--]);
}
const int maxn=100+5;
const int inf=105;
int t,L,w,tp=0,siz=0,in[maxn],idx=0;
int hd[maxn],nxt[maxn<<1],eg[maxn<<1],tot=0;
void addedge(int u,int v)
{eg[++tot]=v;nxt[tot]=hd[u];hd[u]=tot;in[v]++;}
char s[21];
bool tag=false,vis[31],OK=false;
struct StackInfo{
int typ,nam,cop,l,r,ns,sz,ed;
void ini(){typ=nam=cop=l=r=ns=sz=ed=0;}
};
StackInfo ss[maxn];
void ko(){printf("ERR\n");}
void ok(){printf("Yes\n");}
void nok(){printf("No\n");}
vector<int > rfl[maxn],tz;
vector<int > Chain;
int Ns[maxn];
int main()
{
scanf("%d",&t);
for(int z=0;z<t;z++){
OK=true;tp=0,idx=0,siz=0;
memset(hd,-1,sizeof(hd));
memset(nxt,-1,sizeof(nxt));
memset(eg,0,sizeof(eg));
memset(in,0,sizeof(in));
memset(vis,0,sizeof(vis));
tz.clear();
tot=0;
for(int i=0;i<maxn;i++) ss[i].ini();
for(int i=0;i<maxn;i++) rfl[i].clear();
scanf("%d",&L);
scanf("%s",s);
tag=false;
if(strcmp(s,"O(1)")==0) tag=true;
else {
w=0;int idx=4,len=strlen(s);
while(idx<len && s[idx]>='0' && s[idx]<='9') w=w*10+s[idx]-'0',idx++;
}
for(int i=0;i<L;i++){
scanf("%s",s);
if(s[0]=='F'){
tp++;idx++;
tz.push_back(idx);
rfl[tp].push_back(idx);
siz=max(siz,idx);
scanf("%s",s);
ss[idx].nam=s[0]-'a'+1;
if(vis[s[0]-'a'+1] && OK) {ko();OK=false;}
vis[ss[idx].nam]=true;
scanf("%s",s);
if(s[0]=='n') ss[idx].l=inf;
else {
int len=strlen(s),ix=0;
while(ix<len && s[ix]>='0' && s[ix]<='9') ss[idx].l=ss[idx].l*10+s[ix]-'0',ix++;
}
scanf("%s",s);
if(s[0]=='n') ss[idx].r=inf;
else {
int len=strlen(s),ix=0;
while(ix<len && s[ix]>='0' && s[ix]<='9') ss[idx].r=ss[idx].r*10+s[ix]-'0',ix++;
}
if(ss[idx].l>ss[idx].r) ss[idx].sz=0;
else if(ss[idx].l==ss[idx].r) ss[idx].sz=1;
else if(ss[idx].l==inf || ss[idx].r==inf) {ss[idx].sz=1,ss[idx].ns=1;}
else ss[idx].sz=1;
}else if(s[0]=='E'){
if(!OK) continue;
if(tz.size()==0) {ko();OK=false;continue;}
int id=tz.back();
vis[ss[id].nam]=false;
ss[id].ed=1;
for(int j=0;j<(int)rfl[tp-1].size();j++){
if(ss[rfl[tp-1][j]].ed==0){
addedge(rfl[tp-1][j],id);
}
}
tp--;tz.pop_back();
}
}
if(!OK) continue;
if(tp!=0) {ko();continue;}
int ans=0;
for(int i=1;i<=siz;i++) {
if(in[i]==0) {
Chain.clear();memset(Ns,0,sizeof(Ns));
int tmp=i;Chain.push_back(tmp);
while(~hd[tmp]) Chain.push_back(eg[hd[tmp]]),tmp=eg[hd[tmp]];
for(int j=(int)Chain.size()-1;j>=1;j--) {
int v=Chain[j];
Ns[v]+=ss[v].ns;Ns[v]*=ss[v].sz;
Ns[Chain[j-1]]+=Ns[v];
}
Ns[Chain[0]]+=ss[Chain[0]].ns;
ans=max(ans,Ns[Chain[0]]);
}
}
if(tag){
if(ans==0) ok();
else nok();
}else{
if(w==ans) ok();
else nok();
}
}
return 0;
}

T3 逛公园

day2

T1 奶酪

题意

现有一块大奶酪,它的高度为 h,它的长度和宽度我们可以认为是无限大的,奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系, 在坐标系中,奶酪的下表面为z = 0,奶酪的上表面为z = h。

现在, 奶酪的下表面有一只小老鼠 Jerry, 它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交,则 Jerry 可以从其中一个空洞跑到另一个空洞,特别地,如果一个空洞与下表面相切或是相交, Jerry 则可以从奶酪下表面跑进空洞; 如果一个空洞与上表面相切或是相交, Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道, 在不破坏奶酪的情况下,能否利用已有的空洞跑到奶酪的上表面去?

空间内两点$P_1(x_1,y_1,z_1),P_2(x_2,y_2,z_2)$的距离公式如下:

$dis(P_1,P_2)=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^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
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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cctype>
#include <climits>
#include <cassert>
using namespace std;
typedef long long ll;
typedef pair<int ,int > pii;
typedef pair<int ,ll> pil;
typedef pair<ll,int > pli;
typedef pair<ll,ll> pll;
#define MP make_pair
#define fir first
#define sec second
inline int readInt()
{
char c;int tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
inline ll readLL()
{
char c;ll tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
const double eps=1e-6;
struct ball{
double x,y,z;
ball(double x=0,double y=0,double z=0): x(x),y(y),z(z) {}
};
const int maxn=1000+5;
ball b[maxn];
int T,n;
double h,R,W[maxn*maxn];
int ST,ED,hd[maxn<<1],eg[maxn*maxn],nxt[maxn*maxn],tot=0;
void addedge(int u,int v,double cost)
{
eg[++tot]=v;nxt[tot]=hd[u];W[tot]=cost;hd[u]=tot;
eg[++tot]=u;nxt[tot]=hd[v];W[tot]=cost;hd[v]=tot;
}
double pf(double x){return x*x;}
double Dis(int A,int B)
{
return sqrt(pf(b[A].x-b[B].x)+pf(b[A].y-b[B].y)+pf(b[A].z-b[B].z));
}
bool inque[maxn<<1];
int q[maxn<<1];
double dis[maxn<<1];
void spfa(int st,int ed)
{
int N=n+2;
int head=0,tail=0;
memset(inque,0,sizeof(inque));
inque[st]=true;q[head]=st;
for(int i=0;i<maxn;++i) dis[i]=1e60;
dis[st]=0;
while(head<=tail){
int v=q[head%N];head++;
for(int i=hd[v];~i;i=nxt[i]){
int u=eg[i];
if(dis[v]!=1e60 && dis[u]>dis[v]+W[i]){
dis[u]=dis[v]+W[i];
if(!inque[u]){
tail++;q[tail%N]=u;
}
}
}
}
}
int main()
{
scanf("%d",&T);
for(int z=0;z<T;++z)
{
memset(hd,-1,sizeof(hd));
memset(nxt,-1,sizeof(nxt));
for(int j=0;j<maxn*maxn;++j) W[j]=0;
tot=0;
scanf("%d%lf%lf",&n,&h,&R);
ST=0,ED=n+1;
for(int i=1;i<=n;++i) scanf("%lf%lf%lf",&b[i].x,&b[i].y,&b[i].z);
for(int i=1;i<=n;++i){
if(b[i].z<=R) addedge(ST,i,b[i].z);
}
double tmp=0;
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
tmp=Dis(i,j);
if(tmp<=2*R) addedge(i,j,tmp);
}
}
for(int i=1;i<=n;++i){
if(b[i].z+R>=h) addedge(i,ED,h-b[i].z);
}
spfa(ST,ED);
if(dis[ED]!=1e60) printf("Yes\n");
else printf("No\n");
}
return 0;
}

T2 宝藏

T3 列队