本文主要是介绍20130830组队赛-Regionals 2012, Asia - Jakarta，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天的题目有几道水题，还有图论，计算等等
A. Grandpa's Walk
算是一道水题吧，就是搜索，比赛的时候没有写，后来写的时候咋都不出样例，奇了怪了。找了好久，竟然是两个地方
写错变量名字了，。题目就是从一个点（这个点周围的点都必须小于等于这个点的高度）开始DFS，一直找比他低的
点，一直找到没有可延伸的了那么就是一条最长路径了。
#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;
int gcd(int n,int m)
{if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);
}
int lcm(int n,int m)
{if(n<m) swap(n,m);return n/gcd(n,m)*m;
}
#define N 55
int prime[N];
struct node
{int x, y;
};
bool cmp(const node & a, const node & b)
{return a.x > b.x;
}
void getPrime();
void bash();
void wzf();
void SG();
int QuickMod(int a, int b, int n);
int mp[N][N];
int vis[N][N];
int t;
int n, m;
int inmap(int x, int y)
{if(x < 0 || x >= n || y < 0 || y >= m)return false;return true;
}
int dir[4][2] = {{-1,0}, {0, 1}, {1, 0}, {0, -1}};
int MAX = 0;
void DFS(int x, int y)
{int flag = 0;for(int i = 0; i < 4; ++i){int xx = x+ dir[i][0];int yy = y + dir[i][1];if(inmap(xx, yy)&&mp[xx][yy] < mp[x][y]){flag = 1;DFS(xx, yy);}}if(flag == 0)MAX++;
}
int main()
{scanf("%d", &t);int cnt = 0;while(t--){cnt++;MAX = 0;mem(mp, 0);mem(vis, 0);scanf("%d%d", &n, &m);for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j)scanf("%d", &mp[i][j]);int fp = 0;for(int i = 0; i < n; ++i){for(int j = 0; j < m; ++j){fp = 0;for(int k = 0; k < 4; ++k){int xx = i+dir[k][0];int yy = j+dir[k][1];if(inmap(xx, yy) && mp[xx][yy] > mp[i][j]){fp = 1;break;}}if(fp == 0){DFS(i, j);}}}printf("Case #%d: %d\n", cnt, MAX);}return 0;
}int QuickMod(int a,int b,int n)
{int r = 1;while(b){if(b&1)r = (r*a)%n;a = (a*a)%n;b >>= 1;}return r;
}void getPrime()
{memset(prime, 0, sizeof(prime));prime[0] = 1;prime[1] = 1;for(int i = 2; i < N; ++i){if(prime[i] == 0){for(int j = i+i; j < N; j+=i)prime[j] = 1;}}
}void bash(int n, int m)
{if(n%(m+1) != 0)printf("1\n");elseprintf("0\n");
}void wzf(int n, int m)
{if(n > m)swap(n, m);int k = m-n;int a = (k * (1.0 + sqrt(5.0))/2.0);if(a == n)printf("0\n");elseprintf("1\n");
}int numsg[N];
void SG(int n)
{int sum = 0;for(int i=0; i < n; i++){scanf("%d",&numsg[i]);sum ^= numsg[i];}if(sum == 0)printf("No\n");else{printf("Yes\n");for(int i = 0; i < n; i++){int s = sum ^ numsg[i];if(s < numsg[i])printf("%d %d\n", numsg[i], s);//从有num[i]个石子的堆后剩余s个石子}}
}
C. Stop Growing!
C题一开始就被纷纷水过，我也来写了，也没什么就是计算....
#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;
int gcd(int n,int m)
{if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);
}
int lcm(int n,int m)
{if(n<m) swap(n,m);return n/gcd(n,m)*m;
}
#define N 10000007
int prime[N];
struct node
{int x, y;
};
bool cmp(const node & a, const node & b)
{return a.x > b.x;
}
void getPrime();
void bash();
void wzf();
void SG();
int QuickMod(int a, int b, int n);int num[6][2];
int M;
int main()
{int t;scanf("%d", &t);int cnt = 0;while(t--){cnt++;mem(num, 0);int sum1 = 0, sum2 = 0;for(int i = 1; i <= 5; ++i){scanf("%d", &num[i][0]);sum1 += num[i][0];}scanf("%d", &M);if(sum1 >= M){printf("Case #%d: 0\n", cnt);continue;}int fp = 0;int ans = 0;while(1){ans ++;fp = 1-fp;sum2 = 0;for(int i = 1; i <= 5; ++i){if(i == 5)num[i][fp] = num[i][1-fp] + num[1][1-fp];elsenum[i][fp] = num[i][1-fp] + num[i+1][1-fp];sum2 += num[i][fp];}if(sum2 >= M){printf("Case #%d: %d\n", cnt, ans);break;}if(sum2 <= sum1){printf("Case #%d: -1\n", cnt);break;}sum1 = sum2;}}return 0;
}
int QuickMod(int a,int b,int n)
{int r = 1;while(b){if(b&1)r = (r*a)%n;a = (a*a)%n;b >>= 1;}return r;
}void getPrime()
{memset(prime, 0, sizeof(prime));prime[0] = 1;prime[1] = 1;for(int i = 2; i < N; ++i){if(prime[i] == 0){for(int j = i+i; j < N; j+=i)prime[j] = 1;}}
}void bash(int n, int m)
{if(n%(m+1) != 0)printf("1\n");elseprintf("0\n");
}void wzf(int n, int m)
{if(n > m)swap(n, m);int k = m-n;int a = (k * (1.0 + sqrt(5.0))/2.0);if(a == n)printf("0\n");elseprintf("1\n");
}int numsg[N];
void SG(int n)
{int sum = 0;for(int i=0; i < n; i++){scanf("%d",&numsg[i]);sum ^= numsg[i];}if(sum == 0)printf("No\n");else{printf("Yes\n");for(int i = 0; i < n; i++){int s = sum ^ numsg[i];if(s < numsg[i])printf("%d %d\n", numsg[i], s);//从有num[i]个石子的堆后剩余s个石子}}
}
H. Alien Abduction
这道题目我交了，题目就是长了一点，不过读懂了是蛮简单的，就是给出N个人的初始坐标，在给出Q个飞船的捕捉时
的情况，按照飞船的捕捉能力，统计在能力范围内的人，并通过给出的公式计算人被放回时候的坐标。经过Q个飞船
的操作，问你最后这N个人分别处于那些位置。就是按照题目给出的公式计算。不过judge error了，不知道为什么，
看了以前提交的也是judge error。这道题目的时限是10秒。可以写...
#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 ll long long
#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;int gcd(int n,int m)
{if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);
}
int lcm(int n,int m)
{if(n<m) swap(n,m);return n/gcd(n,m)*m;
}
#define maxn 10000007
int prime[maxn];
void getPrime();
void bash();
void wzf();
void SG();
int QuickMod(int a, int b, int n);struct node
{ll x, y;
} ren[50005];
struct chuan
{ll X, Y;ll E, a, b, c, d, e, f;
} num[50005];
int t;
int N, Q, W, H;int main()
{scanf("%d", &t);int cnt = 0;while(t--){cnt++;scanf("%d%d%d%d", &N, &Q, &W, &H);for(int i = 1; i <= N; ++i)scanf("%lld%lld", &ren[i].x, &ren[i].y);for(int i = 1; i <= Q; ++i)scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld", &num[i].X, &num[i].Y, &num[i].E, &num[i].a, &num[i].b, &num[i].c,&num[i].d, &num[i].e, &num[i].f);for(int i = 1; i <= Q; ++i){for(int j = 1; j <= N; ++j){ll tmp = (abs(num[i].X - ren[j].x) + abs(num[i].Y - ren[j].y));if(tmp <= num[i].E){//cout << "****: " << ren[j].x << ' ' << ren[j].y << endl;ll xx = ((ren[j].x*num[i].a) + (ren[j].y*num[i].b) + (j*num[i].c))%W;ll yy = ((ren[j].x*num[i].d) + (ren[j].y*num[i].e) + (j*num[i].f))%H;ren[j].x = xx;ren[j].y = yy;}}}printf("Case #%d:\n", cnt);for(int i = 1; i <= N; ++i){printf("%lld %lld\n", ren[i].x, ren[i].y);}}return 0;
}
int QuickMod(int a,int b,int n)
{int r = 1;while(b){if(b&1)r = (r*a)%n;a = (a*a)%n;b >>= 1;}return r;
}void getPrime()
{memset(prime, 0, sizeof(prime));prime[0] = 1;prime[1] = 1;for(int i = 2; i < N; ++i){if(prime[i] == 0){for(int j = i+i; j < N; j+=i)prime[j] = 1;}}
}void bash(int n, int m)
{if(n%(m+1) != 0)printf("1\n");elseprintf("0\n");
}void wzf(int n, int m)
{if(n > m)swap(n, m);int k = m-n;int a = (k * (1.0 + sqrt(5.0))/2.0);if(a == n)printf("0\n");elseprintf("1\n");
}int numsg[maxn];
void SG(int n)
{int sum = 0;for(int i=0; i < n; i++){scanf("%d",&numsg[i]);sum ^= numsg[i];}if(sum == 0)printf("No\n");else{printf("Yes\n");for(int i = 0; i < n; i++){int s = sum ^ numsg[i];if(s < numsg[i])printf("%d %d\n", numsg[i], s);//从有num[i]个石子的堆后剩余s个石子}}
}
J. Perfect Matching
给你N个字符串，然后两两组合，问你可以组成多少个回文串。1000个字符串，会超吧，有TLE的，所以我写的时候，我就直接加了一个判断，就是拿到两个字符串之后，先判断一下第一个字符串的首字母和第二个字符串的最后一个字符串是否相同，是的话在进行回文串判断，743ms,好像是用时最少的一个，可能样例里面这样的情况比较多吧，
全被直接卡掉了：
#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;
int gcd(int n,int m)
{if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);
}
int lcm(int n,int m)
{if(n<m) swap(n,m);return n/gcd(n,m)*m;
}
#define N 10000007
int prime[N];
struct node
{int x, y;
};
bool cmp(const node & a, const node & b)
{return a.x > b.x;
}
void getPrime();
void bash();
void wzf();
void SG();
int QuickMod(int a, int b, int n);int t;
string str[1001];
int n;
int main()
{scanf("%d", &t);int cnt = 0;while(t--){cnt ++;scanf("%d", &n);for(int i = 0; i < n; ++i)cin >> str[i];int ans = 0;for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){int lenb = str[j].length();if(i!=j && str[i][0] == str[j][lenb-1]){string now = str[i]+str[j];int len = now.length();int k, kk, flag = 0;for(k = 0, kk = len-1; k < kk; ++k, --kk){if(now[k] != now[kk]){flag = 1;break;}}if(flag == 0){ans++;}}}}printf("Case #%d: %d\n", cnt, ans);}return 0;
}
int QuickMod(int a,int b,int n)
{int r = 1;while(b){if(b&1)r = (r*a)%n;a = (a*a)%n;b >>= 1;}return r;
}void getPrime()
{memset(prime, 0, sizeof(prime));prime[0] = 1;prime[1] = 1;for(int i = 2; i < N; ++i){if(prime[i] == 0){for(int j = i+i; j < N; j+=i)prime[j] = 1;}}
}void bash(int n, int m)
{if(n%(m+1) != 0)printf("1\n");elseprintf("0\n");
}void wzf(int n, int m)
{if(n > m)swap(n, m);int k = m-n;int a = (k * (1.0 + sqrt(5.0))/2.0);if(a == n)printf("0\n");elseprintf("1\n");
}int numsg[N];
void SG(int n)
{int sum = 0;for(int i=0; i < n; i++){scanf("%d",&numsg[i]);sum ^= numsg[i];}if(sum == 0)printf("No\n");else{printf("Yes\n");for(int i = 0; i < n; i++){int s = sum ^ numsg[i];if(s < numsg[i])printf("%d %d\n", numsg[i], s);//从有num[i]个石子的堆后剩余s个石子}}
}
这篇关于20130830组队赛-Regionals 2012, Asia - Jakarta的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
