20130831组队赛-(Kuala Lumpur Site) Asia Regional 2011

本文主要是介绍20130831组队赛-(Kuala Lumpur Site) Asia Regional 2011，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A：Smooth Visualization

 

就是一个转换吧，给你一个数字，按照题目给出的表达形式会形成一个不圆滑的锯齿，为了使得锯齿看起来更圆滑一

点，那么对于相邻的两个数字，如果其差值大于1，那么在这两个数字之间插入其中间应该拥有的数字，这样就可以形

成圆滑的锯齿，唉，WA了一次，是那个测试的时候加的一个换行符没有去掉，太粗心了.....

 

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <stack>
#include <ctime>
#include <list>
#define INF 0x7fffffff
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
char num[1000];
#define N 10000007
char ans[7][1000];int A[1000];
int B[1000];
int main()
{int t;scanf("%d", &t);while(t--){mem(num, 0);mem(A, 0);mem(B, 0);scanf("%s", num);int len = strlen(num);int now = 1;int MAX = -INF;for(int i = 0; i < len; ++i){A[i] = num[i]-'0';if(A[i] > MAX)MAX = A[i];}B[0] = A[0];for(int i = 1; i < len; ++i){if((A[i] - A[i-1])> 1){for(int k = A[i-1] + 1; k < A[i]; ++k)B[now++] = k;}else if((A[i-1] - A[i]) > 1){for(int k = A[i-1] - 1; k > A[i]; --k)B[now++] = k;}B[now++] = A[i];}mem(ans, 0);for(int i = 0; i < MAX; ++i){for(int j = 0; j < now; ++j){if(B[j] >= (MAX-i))ans[i][j] = '+';elseans[i][j] = '*';}}for(int i = 0; i < MAX; ++i){printf("%s", ans[i]);printf("\n");}}return 0;
}

 

H:Robotic Traceur

就是给你N个点一个机器人位于一个点上，他要到达另外一个点上，每次移动的距离要不大于两腿长度之和。问你最小

的移动次数是多少？

我是直接从起点开始BFS，每次都保存可以连接到当前点的点，一层一层的向下计算，直到遇到终点，那么就输出此时

递增的步数即可，写了蛮久，那个计数的位置写错了：

 

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <stack>
#include <ctime>
#include <list>
#define INF 0x7fffffff
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{double x, y;int sum;int lp;
} num[1050];
int n, st, ed;
double L1, L2;
int vis[1050];double dis(node a, node b)
{return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
int ans = 0;
int BFS(int st)
{queue<node> Q;Q.push(num[st]);vis[st] = 1;while(!Q.empty()){node tt;tt = Q.front();Q.pop();for(int i = 1; i <= n; ++i){if(dis(num[i], tt) <= (L1+L2) && !vis[i]){num[i].sum = tt.sum + 1;if(i == ed)return 1;Q.push(num[i]);vis[i] = 1;}}}return 0;
}
int main()
{int t;scanf("%d", &t);while(t--){mem(num, 0);scanf("%d%d%d%lf%lf", &n, &st, &ed, &L1, &L2);for(int i = 1; i <= n; ++i){scanf("%lf%lf", &num[i].x, &num[i].y);num[i].lp = i;num[i].sum = 0;}ans = 0;mem(vis, 0);if(BFS(st))printf("%d\n", num[ed].sum);elseprintf("Impossible\n");}return 0;
}

 

G：Writings on the Wall

 

用到了KMP，可是我的想法有问题，一直TLE，还在想怎么改：

 

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <stack>
#include <ctime>
#include <list>
#define INF 0x7fffffff
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;#define N 50005
char A[N];
char B[N];
char KAOBEI[N];
int next[N];
int num[N];
int st;
int la, lb;
void getnext(int m)
{int i, j;next[1] = 0;j = 0;for(i = 2; i <= m; ++i){while(j > 0 && A[st+j+1] != A[st+i])j = A[st+j];if(A[st+j+1] == A[st+i])j++;next[i] = j;}
}
int KMP(int m)
{int pos = 1;int i, j, k;getnext(m);i = pos, k = 0, j = 0;while(i <= lb){while(j > 0 && A[st+j+1] != B[i])j = next[j];if(A[st+j+1] == B[i]){j ++;if(j == m)return i-m+1;}i++;}return -1;
}int t;
int ans;
int main()
{scanf("%d", &t);while(t--){mem(A, 0);mem(B, 0);mem(num, 0);ans = 1;scanf("%s%s", A+1, B+1);la = strlen(A+1);lb = strlen(B+1);int numlen = 1;for(int i = 1; i <= la; ++i){if(A[i] == B[1])num[numlen++] = i;}for(int i = 1; i < numlen; ++i){if((la - num[i] +1 <= lb)){st = num[i];int lp = la-num[i];int tp = KMP(lp);//cout << "tp: " << tp << endl;if(tp != -1)ans++;}}printf("%d\n", ans);}return 0;
}

 

 

 

这篇关于20130831组队赛-(Kuala Lumpur Site) Asia Regional 2011的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---