狗狗40題~（Volume B），狗狗volume
H - Sorting Slides
應該是個二分匹配的模板題的，但我還不會寫 = =
其實數據規模很小，就用貪心的方法就水過了（沒加vis判沖突wa了幾發，從此開始艱難的沒有1A 的生活
）
![]()
1 #include <stdio.h>
2 #include <cstring>
3 #include <cstdlib>
4 #include <algorithm>
5 #include <cmath>
6
7 using namespace std;
8 #define lson o<<1
9 #define rson o<<1|1
10 #define max(a,b) (a)>(b)?(a):(b)
11 #define min(a,b) (a)<(b)?(a):(b)
12 #define INF 200000000
13 typedef long long ll;
14 struct slide{
15 int x1,x2,y1,y2;
16 }rec[50];
17 int g[100][100],d[100],ans[50],vis[100];
18 int main(){
19 //freopen("r.in","r",stdin);freopen("r.out","w",stdout);
20 int n,cs=1;
21 while(scanf("%d",&n) && n){
22 for(int i=0;i<n;i++)scanf("%d%d%d%d",&rec[i].x1,&rec[i].x2,&rec[i].y1,&rec[i].y2);
23 int x,y;
24 memset(d,0,sizeof d);
25 memset(g,0,sizeof g);
26 memset(vis,0,sizeof vis);
27 memset(ans,-1,sizeof ans);
28 for(int i=0;i<n;i++){
29 scanf("%d%d",&x,&y);
30 for(int j=0;j<n;j++)if(x<rec[j].x2&&x>rec[j].x1&&y<rec[j].y2&&y>rec[j].y1){
31 g[i][j+n]=1;d[i]++;
32 d[j+n]++;
33 }
34 }
35 int flag=1;
36 while(flag){
37 int i,j,i0,j0;
38 flag=0;
39 for(i=0;i<n;i++)if(!vis[i]&&d[i]==1)
40 {flag=1;break;}
41 if(flag){
42 for(j=n;j<2*n;j++)if(!vis[j]&&g[i][j])break;
43 i0=i,j0=j;
44 ans[j0-n]=i0;
45 vis[i0]=vis[j0]=1;
46 g[i0][j0]=0;d[i0]--;d[j0]--;
47 for(i=0;i<n;i++)if(g[i][j0])d[i]--,g[i][j0]=0;
48 continue;
49 }
50 for(j=n;j<2*n;j++)if(!vis[j]&&d[j]==1)
51 {flag=1;break;}
52 if(flag){
53 for(i=0;i<n;i++)if(!vis[i]&&g[i][j])break;
54 i0=i;j0=j;
55 ans[j0-n]=i0;
56 vis[i0]=vis[j0]=1;
57 g[i0][j0]=0;d[i0]--;d[j0]--;
58 for(j=n;j<2*n;j++)if(g[i0][j])d[j]--,g[i0][j]=0;
59 continue;
60 }
61 }
62 int cnt=0;
63 printf("Heap %d\n",cs++);
64 for(int i=0;i<n;i++)if(ans[i]>=0)
65 {if(cnt)printf(" ");printf("(%c,%d)",'A'+i,ans[i]+1);cnt++;}
66 if(!cnt)printf("none");
67 printf("\n\n");
68 }
69 return 0;
70 }
View Code
A - Triangle Encapsulation
水題，暴搜の
![]()
1 #include <stdio.h>
2 #include <cstring>
3 #include <cstdlib>
4 #include <algorithm>
5 #include <cmath>
6
7 using namespace std;
8 #define lson o<<1
9 #define rson o<<1|1
10 #define max(a,b) (a)>(b)?(a):(b)
11 #define min(a,b) (a)<(b)?(a):(b)
12 #define INF 200000000
13
14 typedef long long ll;
15 struct point {
16 int x,y;
17 struct point operator -(const struct point b){
18 struct point c;
19 c.x=x-b.x;c.y=y-b.y;
20 return c;
21 }
22 }p[5];
23 int cmp(struct point a,struct point b){
24 if(a.y-b.y)return a.y>b.y;
25 return a.x<b.x;
26 }
27 int g[20][20];
28 int cross(struct point a,struct point b){
29 return a.x*b.y-a.y*b.x;
30 }
31 int main(){
32 //freopen("r.in","r",stdin);freopen("r.out","w",stdout);
33 printf("Program 4 by team X\n");
34 while(scanf("%d%d",&p[0].x,&p[0].y)!=EOF){
35 for(int i=1;i<3;i++)scanf("%d%d",&p[i].x,&p[i].y);
36 struct point pi;
37 memset(g,0,sizeof g);
38 int xmin=18,ymin=18,ymax=0,xx[20]={0};
39 for(pi.x=-9;pi.x<=9;pi.x++)
40 for(pi.y=-9;pi.y<=9;pi.y++){
41 int c1=0,c2=0;
42 for(int i=0;i<3;i++){
43 if(cross(pi-p[i],pi-p[(i+1)%3])<0)c1++;
44 if(cross(pi-p[i],pi-p[(i+1)%3])>0)c2++;
45 }
46 if(c1==3||c2==3){
47 g[pi.x+9][pi.y+9]=1;
48 xmin=min(xmin,pi.x+9);
49 xx[pi.y+9]=max(xx[pi.y+9],pi.x+9);
50 ymin=min(ymin,pi.y+9);
51 ymax=max(ymax,pi.y+9);
52 }
53 }
54 int x,y;
55 for(y=ymax;y>=ymin;y--){
56 for(x=xmin;x<=xx[y];x++){
57 if(x>xmin)printf(" ");
58 if(g[x][y])printf("(%2d,%3d)",x-9,y-9);
59 else printf(" ");
60 }
61 printf("\n");
62 }
63 printf("\n");
64 }
65 printf("End of program 4 by team X\n");
66 return 0;
67 }
View Code
G - Reflections
幾何題。解析算錯很多次，其實就是算交點和關於直線對稱。用向量點積和叉積不容易錯。
![]()
1 #include <stdio.h>
2 #include <cstring>
3 #include <cstdlib>
4 #include <algorithm>
5 #include <cmath>
6 #include <utility>
7
8 using namespace std;
9 #define lson o<<1
10 #define rson o<<1|1
11 #define max(a,b) (a)>(b)?(a):(b)
12 #define min(a,b) (a)<(b)?(a):(b)
13 #define INF 200000000
14 #define eps 1e-6
15
16 typedef long long ll;
17 int n,ans[30],cur;
18 struct point{
19 double x,y;
20 };
21 struct circle{
22 double x,y,r;
23 }cir[30];
24 struct line{
25 double x0,y0,dx,dy;
26 }ori;
27 int sgn(double x){
28 if(x>eps)return 1;
29 if(x<-eps)return -1;
30 return 0;
31 }
32 pair <double,int> inter(struct line now){
33 double a,b,c,del,t1,t2,t=-1;
34 int use=-1;
35 for(int i=1;i<=n;i++){
36 a=now.dx*now.dx+now.dy*now.dy;
37 b=now.dx*(now.x0-cir[i].x)+now.dy*(now.y0-cir[i].y);
38 c=(now.x0-cir[i].x)*(now.x0-cir[i].x)+(now.y0-cir[i].y)*(now.y0-cir[i].y)-cir[i].r*cir[i].r;
39 del=b*b-a*c;
40 if(sgn(del)<=0)continue;
41 t1=(-b-sqrt(del))/a;
42 t2=(-b+sqrt(del))/a;
43 if(sgn(t1)>0){
44 if(t==-1||t>t1)t=t1,use=i;
45 }
46 else if(sgn(t2)>0){
47 if(t==-1||t>t2)t=t2,use=i;
48 }
49 }
50 return make_pair(t,use);
51 }
52 void work(struct line now){
53 if(cur>10)return;
54 double t=inter(now).first;
55 if(t<=0)return;
56 int i0=ans[cur++]=inter(now).second;
57
58 /* 求對稱射線 */
59 double x,y,xx,yy;
60 x=now.x0+t*now.dx;
61 y=now.y0+t*now.dy;
62 if(sgn(now.dy*(x-cir[i0].x)-now.dx*(y-cir[i0].y))==0){
63 now.x0=x;now.y0=y;
64 now.dx=-now.dx;now.dy=-now.dy;
65 work(now);
66 return;
67 }
68 xx=-((x-cir[i0].x)*now.dx+(y-cir[i0].y)*now.dy)/cir[i0].r;
69 yy=((x-cir[i0].x)*now.dy-(y-cir[i0].y)*now.dx)/cir[i0].r;
70 now.x0=x;now.y0=y;
71 now.dx=(xx*(x-cir[i0].x)-yy*(y-cir[i0].y))/cir[i0].r;
72 now.dy=(xx*(y-cir[i0].y)+yy*(x-cir[i0].x))/cir[i0].r;
73 work(now);
74 }
75
76 int main(){
77 //freopen("r.in","r",stdin);freopen("r.out","w",stdout);
78 int cs=1;
79 while(scanf("%d",&n) && n){
80 int i;
81 for(i=1;i<=n;i++)scanf("%lf%lf%lf",&cir[i].x,&cir[i].y,&cir[i].r);
82 scanf("%lf%lf%lf%lf",&ori.x0,&ori.y0,&ori.dx,&ori.dy);
83 cur=0;
84 work(ori);
85 printf("Scene %d\n",cs++);
86 for(i=0;i<cur&&i<10;i++)printf("%d ",ans[i]);
87 if(cur>10)printf("...\n\n");
88 else printf("inf\n\n");
89 }
90 return 0;
91 }
View Code
C - Robbery
一開始有點不敢寫，想了一下其實每個時間點只和前後兩個點有關，所以正著跑一次再倒著check一遍就確定了。
![]()
1 #include <stdio.h>
2 #include <cstring>
3 #include <cstdlib>
4 #include <algorithm>
5 #include <cmath>
6
7 using namespace std;
8 #define lson o<<1
9 #define rson o<<1|1
10 #define max(a,b) (a)>(b)?(a):(b)
11 #define min(a,b) (a)<(b)?(a):(b)
12 #define INF 200000000
13
14 typedef long long ll;
15 int w,h,T,n;
16 int g[105][105][105];
17 struct message{
18 int t,l,u,r,d;
19 }mes[105];
20 struct answer{
21 int t,x,y;
22 }ans[105];
23 int cmp(struct message a,struct message b){
24 return a.t<b.t;
25 }
26 void direct(){
27 int k=0;
28 memset(g,-1,sizeof g);
29 memset(g[1],0,sizeof g[1]);
30 for(int t=1;t<=T;t++){
31 //to expand reachable area.
32 if(t>1)
33 for(int i=1;i<=h;i++)
34 for(int j=1;j<=w;j++)if(!g[t-1][i][j]){
35 g[t][i][j]=0;
36 if(i>1)g[t][i-1][j]=0;
37 if(j>1)g[t][i][j-1]=0;
38 if(i<h)g[t][i+1][j]=0;
39 if(j<w)g[t][i][j+1]=0;
40 }
41 //to receive the messge.
42 for(;k<n&&mes[k].t==t;k++){
43 for(int i=mes[k].u;i<=mes[k].d;i++)
44 for(int j=mes[k].l;j<=mes[k].r;j++)
45 g[t][i][j]=-1;
46 }
47
48 }
49 }
50 void inverse(){
51 int k=n-1;
52 for(int t=T-1;t>0;t--){
53 for(int i=1;i<=h;i++)
54 for(int j=1;j<=w;j++)if(!g[t][i][j]){
55 if(!g[t+1][i][j])continue;
56 if(i>1&&!g[t+1][i-1][j])continue;
57 if(j>1&&!g[t+1][i][j-1])continue;
58 if(i<h&&!g[t+1][i+1][j])continue;
59 if(j<w&&!g[t+1][i][j+1])continue;
60 g[t][i][j]=-1;
61 }
62 }
63 }
64 int main(){
65 //freopen("r.in","r",stdin);freopen("r.out","w",stdout);
66 int cs=1;
67 while(scanf("%d%d%d",&w,&h,&T) && w){
68 scanf("%d",&n);
69 for(int i=0;i<n;i++)
70 scanf("%d%d%d%d%d",&mes[i].t,&mes[i].l,&mes[i].u,&mes[i].r,&mes[i].d);
71 sort(mes,mes+n,cmp);
72 direct();
73 inverse();
74 printf("Robbery #%d:\n",cs++);
75 int res=0,flag=1;
76 for(int t=1;t<=T;t++){
77 int cn=0,x,y;
78 for(int i=1;i<=h;i++)
79 for(int j=1;j<=w;j++)if(!g[t][i][j])x=i,y=j,cn++;
80 if(!cn){flag=0;break;}
81 if(cn==1)ans[res].t=t,ans[res].x=x,ans[res++].y=y;
82 }
83 if(!flag)printf("The robber has escaped.\n\n");
84 else{
85 if(!res)printf("Nothing known.\n\n");
86 else{
87 for(int i=0;i<res;i++)printf("Time step %d: The robber has been at %d,%d.\n",ans[i].t,ans[i].y,ans[i].x);
88 printf("\n");
89 }
90 }
91 }
92 return 0;
93 }
View Code
E - Triangle War
狀壓dp，極大極小算法。
另外有個坑點是每次把能取的三角形位置都取完不一定是最優策略。。
![]()
1 #include <stdio.h>
2 #include <cstring>
3 #include <cstdlib>
4 #include <algorithm>
5 #include <cmath>
6
7 using namespace std;
8 #define lson o<<1
9 #define rson o<<1|1
10 #define max(a,b) (a)>(b)?(a):(b)
11 #define min(a,b) (a)<(b)?(a):(b)
12 #define INF 200000000
13
14 typedef long long ll;
15 int edge[15][15],tri[10]={7,152,52,352,34304,3200,71680,12544,155648};
16 int dp[1<<18];
17 int check(int sta){
18 int ans=0;
19 for(int i=0;i<9;i++)if((sta&tri[i])==tri[i])ans++;
20 return ans;
21 }
22 void dfs(){
23 int s=(1<<18)-1;
24 dp[s]=0;
25 for(s=s-1;s>=0;s--){
26 int ori=check(s),cn,maxdp=-10;
27 for(int i=0;i<18;i++)if(!((1<<i)&s)){
28 int to=(1<<i)|s;
29 int temp=check(to)-ori;
30 if(temp)temp+=dp[to];
31 else temp-=dp[to];
32 maxdp=max(maxdp,temp);
33 }
34 dp[s]=maxdp;
35 }
36 }
37 int main(){
38 //freopen("r.in","r",stdin);freopen("r.out","w",stdout);
39 int t,gm,G;
40 edge[1][2]=1;edge[1][3]=1<<1;
41 edge[2][3]=1<<2;edge[2][4]=1<<3;edge[2][5]=1<<4;
42 edge[3][5]=1<<5;edge[3][6]=1<<6;
43 edge[4][5]=1<<7;edge[4][7]=1<<9;edge[4][8]=1<<10;
44 edge[5][6]=1<<8;edge[5][8]=1<<11;edge[5][9]=1<<12;
45 edge[6][9]=1<<13;edge[6][10]=1<<14;
46 edge[7][8]=1<<15;edge[8][9]=1<<16;edge[9][10]=1<<17;
47 dfs();
48 scanf("%d",&t);
49 while(t--){
50 scanf("%d",&G);
51 for(gm=1;gm<=G;gm++){
52 int m,sta=0,u,v,turn=0;
53 int a[2]={0};
54 scanf("%d",&m);
55 for(int i=1;i<=m;i++){
56 scanf("%d%d",&u,&v);
57 int ori=check(sta);
58 sta+=edge[u][v];
59 ori=check(sta)-ori;
60 a[turn]+=ori;
61 if(!ori)turn=!turn;
62 }
63 printf("Game %d: ",gm);
64 a[turn]+=dp[sta];
65 if(a[0]>a[1])printf("A wins.\n");
66 else printf("B wins.\n");
67 }
68 if(t)printf("\n");
69 }
70 return 0;
71 }
View Code
D - Dreisam Equations
就是暴力加表達式計算。（一直SegmentationFault不明所以，發現是代表符號的值取的不好會和數值沖突=_=）
![]()
1 #include <stdio.h>
2 #include <cstring>
3 #include <cstdlib>
4 #include <algorithm>
5 #include <cmath>
6 #include <stack>
7
8 using namespace std;
9 #define lson o<<1
10 #define rson o<<1|1
11 #define max(a,b) (a)>(b)?(a):(b)
12 #define min(a,b) (a)<(b)?(a):(b)
13 #define INF 200000000
14 #define zuokuo 200000000
15 #define youkuo 200000001
16 #define kong 200000009
17 #define jia -200000000
18 #define jian -200000001
19 #define cheng -200000002
20
21 typedef long long ll;
22 char eq[1000];
23 int q[1000],res;
24 int lf;
25 stack <int> a;
26 stack <int> s;
27 int solve(int cur){
28 if(cur==res){
29 while(!a.empty())a.pop();
30 while(!s.empty())s.pop();
31 for(int i=0;i<res;i++){
32 if(q[i]>-200000000&&q[i]<200000000){
33 if(s.empty()||s.top()==zuokuo)a.push(q[i]);
34 else{
35 int u=a.top();a.pop();
36 if(s.top()==jia)a.push(u+q[i]);
37 if(s.top()==jian)a.push(u-q[i]);
38 if(s.top()==cheng)a.push(u*q[i]);
39 s.pop();
40 }
41 }
42 else if(q[i]==youkuo){
43 if(s.empty()||s.top()!=zuokuo)return 0;
44 s.pop();
45 if(s.empty()||s.top()==zuokuo)continue;
46 int u=a.top();a.pop();
47 int v=a.top();a.pop();
48 if(s.top()==jia)a.push(v+u);
49 if(s.top()==jian)a.push(v-u);
50 if(s.top()==cheng)a.push(v*u);
51 s.pop();
52 }
53 else s.push(q[i]);
54 }
55 if(a.top()==lf)return 1;
56 else return 0;
57 }
58 if(q[cur]!=kong)return solve(cur+1);
59 for(int i=cheng;i<=jia;i++){
60 q[cur]=i;
61 if(solve(cur+1))return 1;
62 q[cur]=kong;
63 }
64 return 0;
65 }
66 int main(){
67 int cs=1;
68 while(gets(eq) && eq[0]!='0'){
69 sscanf(eq,"%d",&lf);
70 res=0;
71 int i;
72 for(i=0;eq[i]!='=';i++);
73 for(i++;eq[i]!='\0';i++){
74 for(;eq[i]==' ';i++);
75 if(eq[i]=='('){q[res++]=zuokuo;continue;}
76 if(eq[i]==')'){q[res-1]=youkuo;q[res++]=kong;continue;}
77 int num=0;
78 while(eq[i]>='0'&&eq[i]<='9'){
79 num=num*10+eq[i]-'0';
80 i++;
81 }
82 q[res++]=num;
83 q[res++]=kong;
84 i=i-1;
85 }
86 res=res-1;
87
88 printf("Equation #%d:\n",cs++);
89 if(solve(0)==0)printf("Impossible\n\n");
90 else{
91 printf("%d=",lf);
92 for(int i=0;i<res;i++){
93 if(q[i]==zuokuo)printf("(");
94 else if(q[i]==youkuo)printf(")");
95 else if(q[i]==jia)printf("+");
96 else if(q[i]==jian)printf("-");
97 else if(q[i]==cheng)printf("*");
98 else printf("%d",q[i]);
99 }
100 printf("\n\n");
101 }
102
103 }
104 return 0;
105 }
View Code
狗狗正常體溫
必須迅速去找獸醫
一般狗狗的體溫是38～39度
小型犬和幼犬會更高一些
但絕對不可能到40度
感覺貌似犬瘟熱 你觀察下它會不會腹瀉
如果腹瀉的話 那一定要去看醫生 80％是犬瘟熱.
以下是資料 你可以參考下
犬瘟熱
犬瘟熱：
犬瘟熱是犬科動物中的高度致死性傳染病，平均死亡率高達70%到;80%,特別是幼犬而言死亡率高達90%以上。
病毒存在於病犬的鼻液、唾液、淚液、血液、尿及糞便中,可通過直接接觸、噴嚏飛沫、被污染的用具而播。
[症狀]：
潛伏期一星期左右，發病早期表現為發熱40到41度、倦怠、厭食、可能有嘔吐.經3到4天後出現緩解期，體溫、精神、食欲都接近正常.
在維持2--3天後,病犬再次發熱並有較多眼淚、眼屎、膿鼻涕、咳嗽、結膜炎、角膜潰瘍等上呼吸道症狀明顯.隨著病情的進一步發展,出現消化道症狀,嘔吐、腹瀉。
神經症狀的出現一般在病後1--3周左右.表現為陣發性抽搐、口吐白沫、空嚼、步態不穩、沖撞等.隨著病情遷延,可見足墊增厚,部分幼犬有腹股溝膿胞.
一般出現神經症狀後,絕大部分患犬預後不良.
[治療]：
1、犬瘟熱單克隆抗體肌注1.0ml/kg是目前最有效的治療手段
2、利巴韋林注射液10.0mg/kg靜滴以抑制病毒或用中藥安宮牛黃丸口服
3、防止繼發感染,使用頭孢曲松20.0mg/kg,氨苄西林注射劑20.0mg/kg肌注以及牧特靈、保得勝、速諾等廣譜高效抗菌素,對付細菌感染,降低死亡率
4、輸液以糾正肌體脫水及酸鹼紊亂
5、能量合劑及多種維生素
6、有呼吸功能衰竭者采取強心利尿,止咳平喘.如選用氨茶鹼、丹參注射液、喘定等
7、有神經症狀的病犬可給予安定、氯丙嗪等
8、提高機體免役力:在輸液中加入犬血球蛋白、肌注轉移因子、犬干擾素
9、給予易消化、高營養食物進一步提高機體抗病及恢復能力，可以添加維康,速補劑、加拿大營養膏、美國in等營養品
犬瘟熱康復犬一般具有終生免疫力.預防犬瘟熱的最佳方法是預防接
狗狗耳朵得了皮囊炎，說是螨蟲引起的，打針了也噴藥了，沒給吃的藥問吃些什藥好的快
B族維生素是必不可少的，我用的是人用的復合維生素B片（嚴重是一天6片後期2片）。因為在用藥的過程中GG的皮膚免疫系統和體表環境會受到嚴重的破壞，而B族維生素是恢復它們皮膚免疫能力所必須的藥品。藥浴是一項很重要的治療手段，推薦用威路士皮膚消毒水來治療螨蟲和皮膚真菌感染極為有效。威路士皮膚消毒水性情溫和不傷害皮膚，能很好的止癢和殺滅螨蟲。保持家裡的環境衛生，最好不好用墊子，用墊子的，要每星期拿出去暴曬或用雙甲米浸泡消毒。1. 用藥—建議是買西安揚森的斯皮仁諾39.00元4粒，藥店沒有，就買<易啟康.伊曲康膠囊>(只要是抗真菌的都可以)價格是39.00元一盒只有7顆，用人量的1/4，注意一定要多喝水。7天一療程，停藥。復合維生素B片1.50元,一天三次,一次2片。第三天，GG的紅腫之處會有白色的硬皮,真菌已經開始被破壞了。2. 藥浴----第一階段要注意GG的衛生，用威路士皮膚消毒水稀釋100倍每天洗澡，每次20分鐘。連用4天。3. 針劑----通滅和速諾，都是進口藥，效果不錯！通滅一星期一次，打四次；速諾連打三天 ；都是每公斤0.1毫升用藥。 4.傷口消毒----傷口周圍也是病菌滋生的場所,要大面積的用威露士消毒. 如有膿包的話,用雙氧水清洗,直到沒有泡沫,擦碘酊幾分鐘後擦藥膏(硫磺軟膏與紅霉素1:1混合)第二階段：在吃易曲康四天後，用硫磺藥皂給GG洗澡，用威露士和膚陰潔交替塗搽患處，每隔2-3就交替一次，避免病菌有抗藥性。記得給GG滴耳螨油，有螨蟲肯定有病菌的。干淨也要滴，等你發現有問題時就晚了。到了第7天，易曲康停藥後喂食先鋒6號15.00元一盒，人量的1/2。這個階段什麼結束？如果看到GG的包包變成黑色或灰色，這個時候要勤洗藥浴，一定要保持住勝利果實。第三階段：進入維護期，停先鋒6號，吃這麼多藥對GG的身體是有傷害的。開始進入病後機理調養，這個時候用消炎殺螨膏13.00元、威迪軟膏50.00元、886/887各15.00元、威露士消毒水630ML 26.00、膚陰潔、舒膚軟膏16.00。有些是本來家裡用剩的，正好可以統統用完，有些是新買的。每種藥外用不要超過4天，用久了會有抗藥性。第5天傷口就結枷了，期間用溫水洗干淨身上掉落的毛發,再用稀釋的威露士洗5分鐘。第12天，傷口的枷全部掉了。
