NOIP模拟赛 -10.25

思路：二分检验

　　　我的二分姿势没法检验到0

　　　0需要特判一下

 1 #include <cstdio>
 2 #include <cctype>
 3 #include <algorithm>
 4 #define min(a,b) a<b?a:b
 5 
 6 typedef long long LL;
 7 
 8 const int MAXN=100010;
 9 
10 int n;
11 
12 LL sum;
13 
14 struct node {
15     int x,y;
16     friend inline bool operator < (node x,node y) {
17         return x.y<y.y;
18     }
19 };
20 node e[MAXN];
21 
22 inline void read(int&x) {
23     int f=1;register char c=getchar();
24     for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());
25     for(;isdigit(c);x=x*10+c-48,c=getchar());
26     x=x*f;
27 }
28 
29 bool check(int x) {
30     int Time=x;
31     for(int i=1;i<=n;++i) {
32         if(Time+e[i].x>e[i].y) return false;
33         Time+=e[i].x;
34     }
35     return true;
36 }
37 
38 int hh() {
39     freopen("manage.in","r",stdin);
40     freopen("manage.out","w",stdout);
41     read(n);
42     
43     for(int i=1; i<=n; ++i) 
44       read(e[i].x),read(e[i].y),sum+=(LL)e[i].x;
45     
46     std::sort(e+1,e+1+n);
47     int l=0,r=e[1].y-e[1].x+1;
48     while(l+1<r) {
49         int mid=(l+r)>>1;
50         if(check(mid)) l=mid;
51         else r=mid;
52     }
53     
54     if(!l) {
55         int tot=0;
56         for(int i=1; i<=n; ++i)
57           if(tot+e[i].x>e[i].y) {
58               printf("-1
");
59               goto END;
60           }
61           else tot+=e[i].x;
62     }
63     
64     printf("%d
",l);
65 END:
66     return 0;
67 }
68 
69 int sb=hh();
70 int main(int argc,char**argv) {;}

代码

思路：51 Nod 原题组合数取模

　　　题解：http://www.cnblogs.com/whistle13326/p/7569520.html

 1 #include <cctype>
 2 #include <cstdio>
 3 #define mod 998244353
 4 
 5 typedef long long LL;
 6 
 7 const int MAXN=1000010;
 8 
 9 int n,sum;
10 
11 int c[MAXN];
12 
13 LL fact[MAXN];
14 
15 inline void read(int&x) {
16     int f=1;register char c=getchar();
17     for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());
18     for(;isdigit(c);x=x*10+c-48,c=getchar());
19     x=x*f;
20 }
21 
22 inline LL quick_pow(LL a,LL k) {
23     LL ret=1;
24     while(k) {
25         if(k&1) ret=(ret*a)%mod;
26         k>>=1;
27         a=(a*a)%mod;
28     }
29     return ret%mod;
30 }
31 
32 inline LL C(int a,int b) {
33     return fact[a]*quick_pow(fact[b]*fact[a-b]%mod,mod-2)%mod;
34 }
35 
36 inline void Factorial() {
37     fact[0]=1;
38     for(int i=1;i<=MAXN;++i)
39       fact[i]=(fact[i-1]*i)%mod;
40 }
41 
42 int hh() {
43     freopen("qiang.in","r",stdin);
44     freopen("qiang.out","w",stdout);
45     
46     Factorial();
47     read(n);
48     for(int i=1;i<=n;++i) read(c[i]),sum+=c[i];
49     
50     LL ans=1;
51     for(int i=n;i;--i) {
52         ans=(ans*C(sum-1,c[i]-1))%mod;
53         sum-=c[i];
54     }
55     printf("%I64d
",ans);
56     return 0;
57 }
58 
59 int sb=hh();
60 int main(int argc,char**argv) {;}

代码

思路：这还是NOIP么怎么像是树套树！！！

　　　我打的两颗线段树的暴力只有20分

　　据说std是树状数组 + 分块 !!

　　　unsigned long long 只能用 llu 输出

　　　cout 肯定超时

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cmath>
  5 using namespace std;
  6 typedef unsigned long long LL;
  7 #define lowbit(x) ((x)&-(x))
  8 int n;
  9 int a[100005];
 10 LL c[100005];
 11 int L[100005],R[100005];
 12 int Q;
 13 int t[405][100005];
 14 int belong[100005];// (i-1)/B+1
 15 LL sum[405];
 16 int B,NUM;
 17 void add(int x,LL d){
 18     while(x<=n){
 19         c[x]+=d;
 20         x+=lowbit(x);
 21     }
 22 }
 23 LL ask(int x){
 24     LL ret=0;
 25     while(x){
 26         ret+=c[x];
 27         x-=lowbit(x);
 28     }
 29     return ret;
 30 }
 31 int main(){
 32     freopen("sum.in","r",stdin);
 33     freopen("sum.out","w",stdout);
 34     scanf("%d",&n);
 35     for(int i=1;i<=n;i++){
 36         scanf("%d",&a[i]);
 37     }
 38     for(int i=1;i<=n;i++){
 39         scanf("%d%d",&L[i],&R[i]);
 40     }
 41     B=sqrt(n)+1;
 42 //  printf("#%d
",B);
 43     NUM=(n-1)/B+1;
 44     for(int i=1;i<=n;i++) belong[i]=(i-1)/B+1;
 45     for(int i=1;i<=n;i++) c[i]=a[i];
 46     for(int i=1;i<=n;i++){
 47         if(i+lowbit(i)<=n){
 48             c[i+lowbit(i)]+=c[i];
 49         }
 50     }
 51     for(int i=1;i<=n;i++){
 52         t[belong[i]][L[i]]++;
 53         t[belong[i]][R[i]+1]--;
 54     }
 55     for(int i=1;i<=NUM;i++){
 56         for(int j=1;j<=n;j++){
 57             t[i][j]+=t[i][j-1];
 58             sum[i]+=t[i][j]*1ULL*a[j];
 59         }
 60     }
 61     scanf("%d",&Q);
 62     while(Q--){
 63         int type,x,y;
 64         scanf("%d%d%d",&type,&x,&y);
 65         if(type==1){
 66             for(int i=1;i<=NUM;i++){
 67                 sum[i]-=t[i][x]*1ULL*a[x];
 68                 sum[i]+=t[i][x]*1ULL*y;
 69             }
 70             add(x,-a[x]);
 71             a[x]=y;
 72             add(x,a[x]);
 73         }else{
 74             int Ln,Rn;
 75             Ln=belong[x],Rn=belong[y];
 76             LL ans=0;
 77             if(Ln==Rn){
 78                 for(int i=x;i<=y;i++){
 79                     ans+=ask(R[i])-ask(L[i]-1);
 80                 }
 81             }else{
 82                 for(int i=Ln+1;i<Rn;i++) ans+=sum[i];
 83                 int lim;
 84                 lim=Ln*B;
 85                 lim=min(lim,y);
 86                 for(int i=x;i<=lim;i++){
 87                     ans+=ask(R[i])-ask(L[i]-1);
 88                 }
 89                 lim=(Rn-1)*B+1;
 90                 lim=max(lim,x);
 91                 for(int i=lim;i<=y;i++){
 92                     ans+=ask(R[i])-ask(L[i]-1);
 93                 }
 94             }
 95             printf("%llu
",ans);
 96         }
 97     }
 98     fclose(stdout);
 99     return 0;
100 }

代码