本文主要是介绍CF 237,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
http://codeforces.com/contest/404/problem/B
给一个a*a的正方形,起点在(0,0),每隔d米有一处提供水的地方,给出询问n,问前n处提供水的地点的坐标。
简单的模拟题,由于做的时间太长,导致C题没来得及做。
By 12120501045, contest: Codeforces Round #237 (Div. 2), problem: (B) Marathon, Accepted, #
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;int main()
{double a,d;int n;while(~scanf("%lf %lf",&a,&d)){scanf("%d",&n);double x = 0, y = 0;double L = 4*a;double tmp;int t;double res;double sh;for(int k = 1; k <= n; k++){if( y == 0){tmp = a-x;if(tmp >= d){printf("%.10lf 0.0000000000\n",x+d);x = x+d;y = 0;}else{res = d-tmp;t = res/L;sh = res-t*L;if(sh <= a){x = a;y = sh;printf("%.10lf %.10lf\n",x,y);}else if(sh > a && sh <= 2*a){x = 2*a-sh;y = a;printf("%.10lf %.10lf\n",x,y);}else if(sh > 2*a && sh <= 3*a){x = 0;y = 3*a-sh;printf("0.0000000000 %.10lf\n",y);}else if(sh > 3*a && sh <= 4*a){x = sh-3*a;y = 0;printf("%.10lf 0.0000000000\n",x);}}}else if(x == a){tmp = a-y;if(tmp >= d){printf("%.10lf %.10lf\n",a,y+d);x = a;y = y+d;}else{double res = d-tmp;int t = res/L;double sh = res-t*L;if(sh <= a){x = a-sh; y = a;printf("%.10lf %.10lf\n",x,y);}else if(sh > a && sh <= 2*a){x = 0; y = 2*a-sh;printf("0.0000000000 %.10lf\n",y);}else if(sh > 2*a && sh <= 3*a){x = sh-2*a; y = 0;printf("%.10lf 0.0000000000\n",x);}else if(sh > 3*a && sh <= 4*a){x = a;y = sh-3*a;printf("%.10lf %.10lf\n",x,y);}}}else if(y == a){tmp = x;if(tmp >= d){printf("%.10lf %.10lf\n",x-d,a);x = x-d;y = a;}else{double res = d-tmp;int t = res/L;double sh = res-t*L;if(sh <= a){x = 0; y = a-sh;printf("0.0000000000 %.10lf\n",y);}else if(sh > a && sh <= 2*a){x = sh-a; y = 0;printf("%.10lf 0.0000000000\n",x);}else if(sh > 2*a && sh <= 3*a){x = a; y = sh-2*a;printf("%.10lf %.10lf\n",x,y);}else if(sh > 3*a && sh <= 4*a){x = 4*a-sh; y = a;printf("%.10lf %.10lf\n",x,y);}}}else if(x == 0){tmp = y;if(tmp >= d){printf("0.0000000000 %.10lf\n",tmp-d);x = 0; y = tmp-d;}else{double res = d-tmp;int t = res/L;double sh = res-t*L;if(sh <= a){x = sh; y = 0;printf("%.10lf 0.0000000000\n",x);}else if(sh > a && sh <= 2*a){x = a; y = sh-a;printf("%.10lf %.10lf\n",x,y);}else if(sh > 2*a && sh <= 3*a){x = 3*a-sh; y = a;printf("%.10lf %.10lf\n",x,y);}else if(sh > 3*a && sh <= 4*a){x = 0; y = 4*a-sh;printf("0.0000000000 %.10lf\n",y);}}}}}return 0;
}
http://codeforces.com/problemset/problem/404/C
题意:给出n个点和每个点最多连的边数k。接下来输入每个点到某一个点的最短距离(两点相连距离为1),构建一个无向图,满足上述距离。
注意到距离为0的点只能有一个,那边是源点。这个图的边数最少是n-1条边,然后按距离源点从小到大加边就OK。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;const int INF = 0x3f3f3f3f;vector <int> dis[100010]; //dis[i]存距离源点为i的点
vector <pair <int,int> > ans;int n,k;
int maxdis;int main()
{while(~scanf("%d %d",&n,&k)){maxdis = -1;int x;for(int i = 0; i <= n; i++){dis[i].clear();ans.clear();}for(int i = 1; i <= n; i++){scanf("%d",&x);maxdis = max(maxdis,x);dis[x].push_back(i);}if(dis[0].size()!= 1){printf("-1\n");return 0;}for(int i = 1; i <= maxdis; i++){int index = 0; //初始化,index为距离是i-1的第一个点int cnt = (i!=1); //cnt记录index发出去的边数,i!=1时为1,。for(int j = 0; j < (int)dis[i].size(); j++){if(cnt == k){index++;cnt = (i!=1);}if(index == (int)dis[i-1].size()){printf("-1\n");return 0;}ans.push_back( make_pair(dis[i-1][index], dis[i][j]));cnt++;}}printf("%d\n",n-1);for(int i = 0; i < (int)ans.size(); i++)printf("%d %d\n",ans[i].first, ans[i].second);}return 0;}
这篇关于CF 237的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!