noip2012day2

T1

裸的数论题 将题目意思转化为ax+by=1求最小X的值

直接套用扩展欧几里得的板子

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,x,y;
ll read(){
    ll sum=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        sum=(sum<<3)+(sum<<1)+ch-'0';
        ch=getchar();
    }
    return sum*f;
}
void exgcd(ll a,ll b,ll&x,ll&y)
{
    if(b==0){
        x=1;y=0;
        return ;
    }
    exgcd(b,a%b,x,y);
    ll t;
    t=x; x=y; y=t-(a/b)*y;
}
int main(){
    a=read();
    b=read();;
    exgcd(a,b,x,y);
    cout<<(x%b+b)%b;
    return 0;
}

T2

线段树区间修改，区间查询的题目，当然也可以用前缀数组加上二分答案来做

下面只给出二分答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000050;
int n,m,s[N],t[N];
ll r[N],d[N],c[N],sum[N];
ll read(){
    ll sum=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        sum=(sum<<3)+(sum<<1)+ch-'0';
        ch=getchar();
    }
    return sum*f;
}
int check(int len){
    memset(c,0,sizeof(c));
    for(int i=1;i<=len;i++)
    {
      c[s[i]]+=d[i];c[t[i]+1]-=d[i];
    }
    for(int i=1;i<=n;i++){
      sum[i]=sum[i-1]+c[i];
      if(sum[i]>r[i])return 0;
    }
    return 1;  
}
int main(){
//    freopen("classroom.in","r",stdin);
//    freopen("classroom.out","w",stdout);
     n=read();
     m=read();
     for(int i=1;i<=n;i++)
     r[i]=read();
     for(int i=1;i<=m;i++)
     {
         d[i]=read();
         s[i]=read();
         t[i]=read();
     }
     int  l=1,r=m,mid;
     while(l<=r)
     {
         mid=l+(r-l)/2;
         if(check(mid)){
             l=mid+1;
         }
         else{
             r=mid-1;
         }
     }
     if(r==m)cout<<0;
     else cout<<-1<<endl<<l;
     return 0;
}

T3

60分未完