T1 同余方程

一道拓展欧几里得的模板题，比较简单

#include
    
     #include
     
      #include
      
       using namespace std;typedef long long ll;ll A, B;ll x, y;ll Tmp;void Exgcd(ll a, ll b){    if(b == 0)    {        x = 1; y = 0; return ;    }    Exgcd(b, a%b);    Tmp = x;    x = y;    y = Tmp - a/b * y;}int main(){//  freopen("mod.in","r",stdin);//  freopen("mod.out","w",stdout);    scanf("%lld%lld", &A, &B);    Exgcd(A, B);    if(x < 0) printf("%lld", (x+B) % B);    else printf("%lld", x%B);    return 0;}
      
     
    

T2 借教室

这道题读一遍下来第一反应是求前缀和和暴力枚举每一份订单是否满足要求，感觉能拿到30—40分的样子，然后思考了一下，想到了二分的做法，二分的终点是left。考试的时候悲催的前缀和写错了，只拿了5分。

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;const int MAXN = 1e6+5;int n, m;int sta[MAXN], end[MAXN], num[MAXN], d[MAXN], r[MAXN], num2[MAXN]; int check(int x){    memset(d, 0, sizeof(d));    for(int i = 1; i <= x; i++)    {        d[sta[i]] += num[i];        d[end[i]+1] -= num[i];    }    for(int i = 1; i <= n; i++)    {        num2[i] = num2[i-1] + d[i];        if(num2[i] > r[i]) return 0;    }    return 1;}int main(){//  freopen("classroom.in","r",stdin);//  freopen("classroom.out","w",stdout);    scanf("%d%d", &n, &m);    for(int i = 1; i <= n; i++)        scanf("%lld", &r[i]);    for(int i = 1; i <= m; i++)        scanf("%d%d%d", &num[i], &sta[i], &end[i]);    if(check(m))    {        printf("0");        return 0;    }    int left = 1, right = m;    while(left < right)    {        int mid = (right + left) / 2;        if(check(mid)) left = mid + 1;        else right = mid;    }    printf("-1\n%d", left);    return 0;}