2017-10-湖南套题1

复杂度m*logn是可以通过的，可以考虑每次询问时二分查找

题目要求所有的线段没有交点，那么肯定是最靠近原点的两点连线，次靠近的。。。像这样：最下面是①号线，向上递增

对于每次询问的(px,py),可以发现，在x=px这条直线上，对于每条线段的y是单调递增的，就可以二分是第几条线段的y>=px

第i条可以，那么[1,i]条均可以，即可以有i个交点

 1 #include <algorithm>
 2 #include <cstdio>
 3 
 4 #define dou double
 5 
 6 const int N(1e5+5);
 7 struct ZhiXian {
 8     double k,b;
 9 }y[N];
10 
11 dou a[N],b[N],px,py;
12 int n,m,ans[N];
13 
14 int L,R,Mid;
15 inline bool check(int x)
16 {
17     return (px*y[x].k+y[x].b)<=py;
18 }
19 inline int erfen()
20 {
21     int ret=0;
22     for(L=0,R=n; L<=R; )
23     {
24         Mid=L+R>>1;
25         if(check(Mid))
26         {
27             ret=Mid;
28             L=Mid+1;
29         }
30         else R=Mid-1;
31     }
32     return ret;
33 }
34 
35 int Presist()
36 {
37     freopen("geometry.in","r",stdin);
38     freopen("geometry.out","w",stdout);
39     scanf("%d",&n);
40     for(int i=1; i<=n; ++i) scanf("%lf",a+i);
41     for(int i=1; i<=n; ++i) scanf("%lf",b+i);
42     std::sort(a+1,a+n+1);std::sort(b+1,b+n+1);
43     for(int i=1; i<=n; ++i)
44         y[i].b=b[i],y[i].k=-b[i]/a[i];
45     scanf("%d",&m);
46     for(; m--; )
47     {
48         scanf("%lf%lf",&px,&py);
49         printf("%d
",erfen());
50     }
51     return 0;
52 }
53 
54 int Aptal=Presist();
55 int main(int argc,char**argv){;}

 1 #include <cstdio>
 2 
 3 inline void read(int &x)
 4 {
 5     x=0; register char ch=getchar();
 6     for(; ch>'9'||ch<'0'; ) ch=getchar();
 7     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
 8 }
 9 const int N(24);
10 int n,a[N],b[N];
11 
12 int Presist()
13 {
14 //    freopen("cashier.in","r",stdin);
15 //    freopen("cashier.out","w",stdout);
16     int t; read(t);
17     for(int i,j,k,x,y; t--; )
18     {
19         int ans=0;
20         for(i=0; i<24; ++i) read(a[i]);
21         for(i=0; i<24; ++i) read(b[i]);
22         for(x,y,j,k,i=0; i<24; ++i)
23         {
24             for(j=i,x=0; a[i]>0&&++x<8; --j)
25             {
26                 if(j<0) j+=N;
27                 if(!b[j]) continue;
28                 if(b[j]>=a[i])
29                 {
30                     ans+=a[i];b[j]-=a[i];
31                     for(k=(j+1)%N,y=0; ++y<8; ++k,k%=N)
32                         if(k!=i) a[k]-=a[i]; a[i]=0;
33                 }
34                 else
35                 {
36                     ans+=b[j]; a[i]-=b[j];
37                     for(k=(j+1)%N,y=0; ++y<8; ++k,k%=N)
38                         if(k!=i) a[k]-=b[j];
39                 }
40             }
41             if(a[i]>0) { ans=-1; goto print; }
42         }
43         /*for(x,y,j,k,i=0; i<8; ++i)
44         {
45             for(j=i,x=0; a[i]>0&&++x<8; --j,j+=N,j%=N)
46             {
47                 if(!b[j]) continue;
48                 if(b[j]>=a[i])
49                 {
50                     ans+=a[i];b[j]-=a[i];
51                     for(k=j+1,y=0; ++y<8; ++k,k+=N,k%=N)
52                         if(k!=i) a[k]-=a[i]; a[i]=0;
53                 }
54                 else
55                 {
56                     ans+=b[j]; a[i]-=b[j];
57                     for(k=j+1,y=0; ++y<8; ++k,k+=N,k%=N)
58                         if(k!=i) a[k]-=b[j];
59                 }
60             }
61             if(a[i]>0) { ans=-1; goto print; }
62         }*/
63         print:printf("%d
",ans);
64     }
65     return 0;
66 }
67 
68 int Aptal=Presist();
69 int main(int argc,char**argv){;}

贪心45分，对与一个ai,从i向前找至多7个位置，直至可以把a[i]更新为0，每使用一次b[j]，向后更新8个a[k]，（每个人可以连续工作八小时）。。。然而这样会有许多问题

差分约束，

设sum[i]表示使用的最小的b的前缀和，则ans=sum[23]

sum[i]需要满足 (i>7) sum[i]-sum[i-8]>=a[i] ,0<=sum[i]-sum[i-1]<=b[i]（i==0是特判向源点连）

　　　　　　　　(i<8) sum[23]-sum[i+16]+sum[i]>=a[i]

求最小值出现负环表示无解

 1 #include <cstring>
 2 #include <cstdio>
 3 #include <queue>
 4 
 5 #define max(a,b) (a>b?a:b)
 6 
 7 inline void read(int &x)
 8 {
 9     x=0; register char ch=getchar();
10     for(; ch>'9'||ch<'0'; ) ch=getchar();
11     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
12 }
13 const int N(24);
14 int n,a[N],b[N];
15 
16 int head[N+5],sumedge;
17 struct Edge {
18     int v,next,w;
19     Edge(int v=0,int next=0,int w=0):v(v),next(next),w(w){;}
20 }edge[N*N];
21 
22 inline void ins(int u,int v,int w)
23 {
24     edge[++sumedge]=Edge(v,head[u],w); head[u]=sumedge;
25 }
26 
27 bool inq[N+5];
28 int sum[N+5],cnt[N+5];
29 bool SPFA()
30 {
31     std::queue<int>que;
32     for(int i=0; i<N; ++i)
33         inq[i]=cnt[i]=0,sum[i]=- 0x7fffffff;
34     sum[N]=0;     que.push(N);
35     for(int u,v; !que.empty(); )
36     {
37         u=que.front(); que.pop(); inq[u]=0;
38         for(int i=head[u]; i; i=edge[i].next)
39         {
40             v=edge[i].v;
41             if(sum[v]<sum[u]+edge[i].w)
42             {
43                 sum[v]=sum[u]+edge[i].w;
44                 if(++cnt[v]>N) return 0;
45                 if(!inq[v]) inq[v]=1,que.push(v);
46             }
47         }
48     }
49     return 1;
50 }
51 
52 int L,R,Mid;
53 inline bool check(int x)
54 {
55     memset(edge,0,sizeof(edge));
56     memset(head,0,sizeof(head));
57     sumedge=0;
58     for(int i=0; i<24; ++i)
59     {
60         if(i>=8) ins(i-8,i,a[i]);
61         else ins(i+16,i,a[i]-x);
62         if(i) ins(i-1,i,0),ins(i,i-1,-b[i]);
63         else ins(N,i,0),ins(i,N,-b[i]);
64     }
65     ins(N,23,x),ins(23,N,-x);
66     return SPFA();
67 }
68 
69 int Presist()
70 {
71     freopen("cashier.in","r",stdin);
72     freopen("cashier.out","w",stdout);
73     int t; read(t);
74     for(int i,j,k,x,y; t--; )
75     {
76         int ans=-1;L=0,R=0;
77         for(i=0; i<24; ++i) read(a[i]),L=max(L,a[i]);
78         for(i=0; i<24; ++i) read(b[i]),R+=b[i];
79         for(; L<=R; )
80         {
81             Mid=L+R>>1;
82             if(check(Mid))
83             {
84                 R=Mid-1;
85                 ans=Mid;
86             }
87             else L=Mid+1;
88         }
89         printf("%d
",ans);
90     }
91     return 0;
92 }
93 
94 int Aptal=Presist();
95 int main(int argc,char**argv){;}

 1 #include <cstdio>
 2 
 3 #define LL long long
 4 const int mod(1e9+7);
 5 const int N(50005);
 6 long long val[N];
 7 
 8 int Presist()
 9 {
10     freopen("game.in","r",stdin);
11     freopen("game.out","w",stdout);
12     int n,m;    scanf("%d%d",&n,&m);
13     for(int i=1; i<=n; ++i) scanf("%I64d",val+i);
14     for(int oo,a,b,c; m--; )
15     {
16         scanf("%d%d%d",&oo,&a,&b);
17         if(oo==1)
18         {
19             scanf("%d",&c);
20             for(int i=a; i<=b; ++i)
21             {
22                 val[i]+=c;
23                 for(; val[i]<0; ) val[i]+=mod;
24                 for(; val[i]>=mod; ) val[i]-=mod;
25             }
26         }
27         else if(oo==2)
28             for(int i=a; i<=b; ++i)
29             {
30                 val[i]*=-1;
31                 for(; val[i]<0; ) val[i]+=mod;
32                 for(; val[i]>=mod; ) val[i]-=mod;
33             }
34         else
35         {
36             scanf("%d",&c);LL ans=0;
37             for(int i=a; i<=b; ++i)
38             {
39                 ans+=val[i];
40                 for(; ans<0; ) ans+=mod;
41                 for(; ans>=mod; ) ans-=mod;
42             }
43             printf("%I64d
",ans);
44         }
45     }
46     return 0;
47 }
48 
49 int Aptal=Presist();
50 int main(int argc,char**argv){;}

20分，最暴力的暴力。（线段树炸了）

k比较小，所以线段树每个节点维护一个区间答案记为f[i]

考虑一段区间i,左边取j个右边就取i-j个答案是每个方案的左边乘右边的和。

就是i左儿子f[j]和右边的f[i-j] 所以f[i]=Σ(j=0~i) lc f[j]*rc f[i-j]

考虑取反操作，i是奇数就取反，偶数无影响(因为是相乘)

考虑区间加，开始f[i] 是 a1*a2……an 后来是(a1+c)*(a2+c)……(an+c)

考虑类似二项式定理,当上述a1~an n个方案如果取了j个了，分别为al1,al2……alj

那考虑最后答案，如果已经选了j个方案是(al1+c)(al2+c)……(alj+c)再还能选i-j个最后答案是C(len-i,i-j)*f[j]*c^(i-j)

复杂度 O(k^2*nlogn)

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #define MOD 1000000007
  4 #define N 100005
  5 typedef long long LL;
  6 using namespace std;
  7 struct Node
  8 {
  9     LL f[11];
 10 } node[N * 4];
 11 LL a[N], lazy1[N * 4];
 12 bool lazy2[N * 4];
 13 LL C[N][11];
 14 
 15 Node merge(Node lc, Node rc)
 16 {
 17     Node o;
 18     o.f[0] = 1;
 19     for (int i = 1; i <= 10; i++)
 20     {
 21         o.f[i] = 0;
 22         for (int j = 0; j <= i; j++)
 23             o.f[i] = (o.f[i] + lc.f[j] * rc.f[i - j] % MOD) % MOD;
 24     }
 25     return o;
 26 }
 27 
 28 void build(int o, int l, int r)
 29 {
 30     if (l == r)
 31     {
 32         for (int i = 0; i <= 10; i++) node[o].f[i] = 0;
 33         node[o].f[0] = 1;
 34         node[o].f[1] = (a[l] % MOD + MOD) % MOD;
 35         return ;
 36     }
 37     int mid = (l + r) >> 1;
 38     build(o * 2, l, mid);
 39     build(o * 2 + 1, mid + 1, r);
 40     node[o] = merge(node[o * 2], node[o * 2 + 1]);
 41     return ;
 42 }
 43 
 44 void update1(int o, int l, int r, int c)
 45 {
 46     int len = r - l + 1;
 47     LL ff[11];
 48     for (int i = 0; i <= 10; i++) ff[i] = node[o].f[i];
 49     for (int i = 1; i <= 10; i++)
 50     {
 51         node[o].f[i] = 0;
 52         LL t = 1;
 53         for (int j = 0; j <= i; j++)
 54         {
 55             LL tmp = ff[i - j] * C[len - (i - j)][j] % MOD * t % MOD;
 56             node[o].f[i] = (node[o].f[i] + tmp) % MOD;
 57             t = t * c % MOD;
 58         }
 59     }
 60     return ;
 61 }
 62 
 63 void push_down(int o, int l, int r)
 64 {
 65     int mid = (l + r) >> 1;
 66     if (lazy1[o])
 67     {
 68         if (lazy2[o * 2])
 69             lazy1[o * 2] = (lazy1[o * 2] + MOD - lazy1[o]) % MOD;
 70         else
 71             lazy1[o * 2] = (lazy1[o * 2] + lazy1[o]) % MOD;
 72         if (lazy2[o * 2 + 1])
 73             lazy1[o * 2 + 1] = (lazy1[o * 2 + 1] + MOD - lazy1[o]) % MOD;
 74         else
 75             lazy1[o * 2 + 1] = (lazy1[o * 2 + 1] + lazy1[o]) % MOD;
 76         update1(o * 2, l, mid, lazy1[o]);
 77         update1(o * 2 + 1, mid + 1, r, lazy1[o]);
 78         lazy1[o] = 0;
 79     }
 80     if (lazy2[o])
 81     {
 82         lazy2[o * 2] ^= 1;
 83         lazy2[o * 2 + 1] ^= 1;
 84         for (int j = 1; j <= 10; j += 2)
 85         {
 86             node[o * 2].f[j] = MOD - node[o * 2].f[j];
 87             node[o * 2 + 1].f[j] = MOD - node[o * 2 + 1].f[j];
 88         }
 89         lazy2[o] = 0;
 90     }
 91 }
 92 
 93 void modify1(int o, int l, int r, int ll, int rr, int c)
 94 {
 95     if (ll <= l && rr >= r)
 96     {
 97         if (lazy2[o]) lazy1[o] = (lazy1[o] + MOD - c) % MOD;
 98         else lazy1[o] = (lazy1[o] + c) % MOD;
 99         update1(o, l, r, c);
100         return ;
101     }
102     int mid = (l + r) >> 1;
103     push_down(o, l, r);
104     if (ll <= mid) modify1(o * 2, l, mid, ll, rr, c);
105     if (rr > mid) modify1(o * 2 + 1, mid + 1, r, ll, rr, c);
106     node[o] = merge(node[o * 2], node[o * 2 + 1]);
107     return ;
108 }
109 
110 void modify2(int o, int l, int r, int ll, int rr)
111 {
112     if (ll <= l && rr >= r)
113     {
114         for (int i = 1; i <= 10; i += 2) node[o].f[i] = MOD - node[o].f[i];
115         lazy2[o] ^= 1;
116         return ;
117     }
118     int mid = (l + r) >> 1;
119     push_down(o, l, r);
120     if (ll <= mid) modify2(o * 2, l, mid, ll, rr);
121     if (rr > mid) modify2(o * 2 + 1, mid + 1, r, ll, rr);
122     node[o] = merge(node[o * 2], node[o * 2 + 1]);
123     return ;
124 }
125 
126 Node query(int o, int l, int r, int ll, int rr)
127 {
128     if (ll <= l && rr >= r)
129         return node[o];
130     int mid = (l + r) >> 1;
131     push_down(o, l, r);
132     if (rr <= mid) return query(o * 2, l, mid, ll, rr);
133     if (ll > mid) return query(o * 2 + 1, mid + 1, r, ll, rr);
134     Node lc = query(o * 2, l, mid, ll, rr);
135     Node rc = query(o * 2 + 1, mid + 1, r, ll, rr);
136     return merge(lc, rc);
137 }
138 
139 int main(int argc, char ** argv)
140 {
141     freopen("game.in", "r", stdin);
142     freopen("game.out", "w", stdout);
143     int n, m;
144     scanf("%d %d", &n, &m);
145     C[0][0] = 1;
146     for (int i = 1; i <= n; i++)
147     {
148         C[i][0] = 1;
149         for (int j = 1; j <= 10; j++)
150             C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
151     }
152     for (int i = 1; i <= n; i++)
153         scanf("%d", &a[i]);
154     build(1, 1, n);
155     for (int i = 1; i <= m; i++)
156     {
157 
158         int l, r, opt;
159         scanf("%d%d%d",&opt, &l, &r);
160         if (opt == 1)
161         {
162             int c;
163             scanf("%d", &c);
164             c = (c % MOD + MOD) % MOD;
165             modify1(1, 1, n, l, r, c);
166         }
167         else if (opt == 2)
168         {
169             modify2(1, 1, n, l, r);
170         }
171         else
172         {
173             int k;
174             scanf("%d", &k);
175             Node o = query(1, 1, n, l, r);
176             printf("%d
", o.f[k] % MOD);
177         }
178     }
179     return 0;
180 }

std

——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。