;
t:=x;
x:=y;
y:=t-(a div b)*y;
end;
end;
begin
readln(a,b);
d:=b;
gcd(a,b);
writeln((x mod d+d) mod d);
end.
【D2T2】
P1782借教室 Accepted 标签：[显示标签]
描述
在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。
面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来n天的借教室信息，其中第i天学校有ri个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为dj,sj,tj，表示某租借者需要从第sj天到第tj天租借教室（包括第sj天和第tj天），每天需要租借dj个教室。
我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供dj个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。
借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。
现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。
格式
输入格式
第一行包含两个正整数n,m，表示天数和订单的数量。
第二行包含n个正整数，其中第i个数为ri，表示第i天可用于租借的教室数量。
接下来有m行，每行包含三个正整数dj,sj,tj，表示租借的数量，租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。
输出格式
如果所有订单均可满足，则输出只有一行，包含一个整数0。否则（订单无法完全满足）输出两行，第一行输出一个负整数-1，第二行输出需要修改订单的申请人编号。
样例1
样例输入1[复制]
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
样例输出1[复制]
-1
2
限制
每个测试点1s
提示
对于10%的数据，有1≤ n,m≤ 10；
对于30%的数据，有1≤ n,m≤1000；
对于70%的数据，有1≤ n,m≤ 10^5；
对于100%的数据，有1≤n,m≤10^6,0≤ri,dj≤10^9,1≤sj≤tj≤n。
来源
Noip2012提高组复赛Day2T2
【分析】一眼题。但是线段树会T。（这个用zkw貌似很麻烦？@syc1999）其实二分加判定就行了233。
不想用凌神的标号法了，直接memset水过。
【代码】
#include
#include
#define N 1000005 using namespace std; int P[N],a[N],num[N],L[N],R[N],n,m,i,ans; inline int Read() { char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar()); int x=0;for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x; } inline int check(int D) { memset(P,0,sizeof(P)); for (int i=1;i<=D;i++) P[L[i]]-=num[i],P[R[i]+1]+=num[i]; for (int i=1;i<=n;i++) if ((P[i]+=P[i-1])+a[i]<0) return 0; return 1; } inline int erfen() { int l=1,r=m+1; while (l!=r) { int mid=(l+r)>>1; if (check(mid)) l=mid+1;else r=mid; } if (r==m+1) return 0;return r; } int main() { n=Read();m=Read(); for (i=1;i<=n;i++) a[i]=Read(); for (i=1;i<=m;i++) num[i]=Read(),L[i]=Read(),R[i]=Read(); ans=erfen(); if (ans) printf("-1\n%d",ans);else printf("0"); return 0; }
【D2T3疫情控制】
P1783疫情控制 Accepted 标签：[显示标签]
描述
H国有n个城市，这n个城市用n-1条双向道路相互连通构成一棵树，1号城市是首都，也是树中的根节点。
H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。
现在，在H国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。
请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。
格式
输入格式
第一行一个整数n，表示城市个数。
接下来的n-1行，每行3个整数，u、v、w，每两个整数之间用一个空格隔开，表示从城市u到城市v有一条长为w的道路。数据保证输入的是一棵树，且根节点编号为1。
接下来一行一个整数m，表示军队个数。
接下来一行m个整数，每两个整数之间用一个空格隔开，分别表示这m个军队所驻扎的城市的编号。
输出格式
共一行，包含一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。
样例1
样例输入1[复制]
4
1 2 1
1 3 2
3 4 3
2
2 2
样例输出1[复制]
3
限制
每个测试点2s
提示
保证军队不会驻扎在首都。
对于20%的数据，2≤ n≤ 10；
对于40%的数据，2 ≤n≤50，0
对于60%的数据，2 ≤ n≤1000，0
对于80%的数据，2 ≤ n≤10,000；
对于100%的数据，2≤m≤n≤50,000，0
来源
Noip2012提高组复赛Day2T3
【过程】这道题调到吐血。
前几天盯上了此题。开始自己的方法连官方数据都没过。于是开始借鉴别人的想法。网上的想法大同小异，后来我越改越混乱，越改越没有主见。好不容易过了官方数据，VJ上WA了5个点后弃疗。
一直放在那里，今天才发现的=自己仔细想了想方法，应该完美了，开始改。
结果一阵猛调还是和前几天的一样。开始和网上的拍。连续找了2个代码（都是百度搜索前几位）都是秒拍出错，而且= =出错的是他们。。。于是我找来了哲教的代码。
又是秒拍？定睛一看，哲教，呵呵。他表示无压力改好给我。
过了一会了拍出了错误。激动ing：哲教，你逗我？
他表示：我知道哪里错了，但不屑和你这只??说。。。
于是我又开始漫长的找其他代码对拍。总算找到一个代码和我飞起。。。于是立刻调大数据，5分钟后。。。
2333，出来了！果然是我错了！
你瞧为什么错了？在调用倍增的时候语句打反了。
嘻嘻，官方数据，你是有多弱啊2333。。。
【思路】最后还是自己想的2333.
二分+判定是肯定要的。
贪心的想，把所有军队移到1的所有儿子那里。我们称1的儿子为“目标点”。
先倍增预处理，求出每个军队是否能跑到根节点。
如果不能，那么算出他向上跑到哪里，在那儿打个标记。（能的等会再说）
然后dfs一遍。如果一个点的所有子节点都打上了标记，那么它也打上标记。
这样，我们就知道一些目标点已经不需要军队过去（就是已经被打上了标记的）。
之后就是贪心思想了，扫描每一个可以到根的军队。
如果它不能从根回到自己经过的目标点而且那个目标点需要军队驻扎的话，就把军队停在那里。
为什么是停在那里呢？证明见下。
否则就把这只军队加入数组p，其值为它到根节点后剩下的时间。
把需要军队的目标点塞入数组q，其值是它与1的距离。
然后对于p和q，先排序，再从小往大匹配。
对于当前的军队，先判断它走出来的目标点是否已经有军队了。
如果没有的话，显然要他去