【noip2012 提高组 day2】

A. 【NOIP2012 提高组 day2】同余方程

一道水题，用拓展欧几里得来计算，最后x的值要x=(x%b+b)%b;来取得非负最小值。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 ll a,b,x,y;
 6 
 7 ll exgcd(ll a,ll b,ll &x,ll &y){
 8     if(!b){
 9         x=1,y=0;
10         return a;
11     }
12     ll d=exgcd(b,a%b,x,y);
13     ll z=x;x=y;y=z-y*(a/b);
14     return d;
15 }
16 
17 int main(){
18     scanf("%lld%lld",&a,&b);
19     exgcd(a,b,x,y);
20     x=(x%b+b)%b;
21     printf("%lld",x);
22 }

B. 【NOIP2012 提高组 day2】借教室

思路：先初始化sum数组即每天一共要花费的教室数量。

1     for(int i=1;i<=n;i++) ne[i]=read();
2     for(int i=1;i<=m;i++){
3         d[i]=read(),l[i]=read(),r[i]=read();
4         sum[l[i]]+=d[i],sum[r[i]+1]-=d[i];
5     }
6     for(int i=1;i<=n;i++){
7         sum[i]+=sum[i-1];
8     }

然后从第一天开始循环，遇到不合法的情况就开始二层循环m个询问从后往前

遇到一个包含此天的就减去教室数量知道满足条件，这时候的j就表示一直到第j个询问刚好不满足条件

然后不断更新j 的下限；

最后输出

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 const int N=1e6+5;
 6 ll n,m;
 7 ll ne[N],d[N],l[N],r[N],sum[N];
 8 
 9 inline ll read(){
10     ll x=0,f=1;
11     char s=getchar();
12     while(!isdigit(s)) f*=(s=='-')? 1:1,s=getchar();
13     do x=(x<<1)+(x<<3)+(s^48),s=getchar();
14     while(isdigit(s));
15     return x*f;
16 }
17 
18 int main(){
19     n=read(),m=read();
20     for(int i=1;i<=n;i++) ne[i]=read();
21     for(int i=1;i<=m;i++){
22         d[i]=read(),l[i]=read(),r[i]=read();
23         sum[l[i]]+=d[i],sum[r[i]+1]-=d[i];
24     }
25     for(int i=1;i<=n;i++){
26         sum[i]+=sum[i-1];
27     }
28     int anss=1e9;
29     for(int i=1;i<=n;i++){
30         if(sum[i]>ne[i]){
31             ll k=sum[i];
32             int j;
33             for(j=m;j>=1;j--){
34                 if(l[j]<=i && r[j]>=i){
35                     k-=d[j];
36                     if(k<=ne[i]) break;
37                 }
38             }
39             anss=min(anss,j);
40             if(anss==1) break;
41         }
42     }
43     if(anss==1e9) printf("0");
44     else printf("%d
%d",-1,anss);
45     return 0;    
46 }

C. 【NOIP2012 提高组 day2】疫情控制

。。。待