沈阳企业做网站,关于微网站策划ppt怎么做,开发一款app软件可以赚多少钱,设计师网盘题意#xff1a;
观众席围成一圈。列的总数是300#xff0c;编号为1–300#xff0c;顺时针计数#xff0c;我们假设行的数量是无限的。将有N个人去那里。他对这些座位提出了要求#xff1a;这意味着编号A的顺时针X距离坐着编号B。例如#xff1a;A在第4列#xff0c;X…题意
观众席围成一圈。列的总数是300编号为1–300顺时针计数我们假设行的数量是无限的。将有N个人去那里。他对这些座位提出了要求这意味着编号A的顺时针X距离坐着编号B。例如A在第4列X是2那么B必须在第6列642。现在你的任务是判断请求是否正确。
题目
In 12th Zhejiang College Students Games 2007, there was a new stadium built in Zhejiang Normal University. It was a modern stadium which could hold thousands of people. The audience Seats made a circle. The total number of columns were 300 numbered 1–300, counted clockwise, we assume the number of rows were infinite. These days, Busoniya want to hold a large-scale theatrical performance in this stadium. There will be N people go there numbered 1–N. Busoniya has Reserved several seats. To make it funny, he makes M requests for these seats: A B X, which means people numbered B must seat clockwise X distance from people numbered A. For example: A is in column 4th and X is 2, then B must in column 6th (642). Now your task is to judge weather the request is correct or not. The rule of your judgement is easy: when a new request has conflicts against the foregoing ones then we define it as incorrect, otherwise it is correct. Please find out all the incorrect requests and count them as R.
Input
There are many test cases: For every case: The first line has two integer N(1N50,000), M(0M100,000),separated by a space. Then M lines follow, each line has 3 integer A(1AN), B(1BN), X(0X300) (A!B), separated by a space.
Output
For every case: Output R, represents the number of incorrect request.
Sample Input
10 10 1 2 150 3 4 200 1 5 270 2 6 200 6 5 80 4 7 150 8 9 100 4 8 50 1 7 100 9 2 100
Sample Output
2
Hint
Hint: PS the 5th and 10th requests are incorrect
思路
1.由于题中明确给出编号A的顺时针X距离坐着编号B故x300当我们用并查集找到一个祖宗节点时我们可以将该点看作原点将圈拉成直线看待。即可忽略成环。
2.b-a, a离”原点更近“
int f(int x)
{if(x!dp[x]){int tdp[x];/*因为在递归找祖先的过程中dp[x]的值会改变而我们我们只需要找到距离x最近的点即可得到dp[x]到祖宗节点的距离。所以要记录t的值*/dp[x]f(dp[x]);num[x]num[t];}return dp[x];
}dp[b]-dp[a] dp[v]u;num[v]num[a]x-num[b];AC代码
#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
const int M5e410;
int dp[M],num[M];
int f(int x)
{if(x!dp[x]){int tdp[x];dp[x]f(dp[x]);/*因为在递归找祖先的过程中dp[x]的值会改变而我们我们只需要找到距离x最近的点即可得到dp[x]到祖宗节点的距离。所以要记录t的值*/num[x]num[t];}return dp[x];
}
bool dfs(int a,int b,int x)
{int uf(a),vf(b);/*a-u,b-v*/if(uv){if(num[a]x!num[b])/*b-a,又起点为父节点*/return true;return false;}dp[v]u;num[v]num[a]x-num[b];return false;
}
int main()
{int m,n;while(~scanf(%d%d,m,n)){int ans0;for(int i0;im;i){dp[i]i;num[i]0;}while(n--){int a,b,x;/*设起点为祖宗节点则都指向起点b-a*/scanf(%d%d%d,a,b,x);if(dfs(a,b,x))ans;}printf(%d\n,ans);}return 0;
}
