湖南集训DAY6

先排序因为题目保证一定存在一种情况使得线段两两不相交如下图

我们观察可以发现如果一个点与(0,0)，连线如果线段与第i条线段相交那么一定会与第i-1条线段相交

那么就可以二分判断这条线段与多少条已知线段相交

 1 #include <cstdio>
 2 #include <cctype>
 3 #include <algorithm>
 4 
 5 const int MAXN=100010;
 6 
 7 int n,m,xx,yy;
 8 
 9 int x[MAXN],y[MAXN];
10 
11 inline void read(int&x) {
12     int f=1;register char c=getchar();
13     for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());
14     for(;isdigit(c);x=x*10+c-48,c=getchar());
15     x=x*f;
16 }
17 
18 bool check(int p) {
19     double k=(double)y[p]/x[p];
20     double _y=(double)-k*xx+y[p];
21     if(yy<_y) return true;
22     else return false;
23 }
24 
25 int hh() {
26     freopen("geometry.in","r",stdin);
27     freopen("geometry.out","w",stdout);
28     
29     read(n);
30     for(int i=1;i<=n;++i) read(x[i]);
31     for(int i=1;i<=n;++i) read(y[i]);
32     std::sort(x+1,x+1+n);
33     std::sort(y+1,y+1+n);
34     read(m);
35     for(int i=1;i<=m;++i) {
36         read(xx);read(yy);
37         int l=0,r=n+1,ans=0;
38         while(l+1<r) {
39             int mid=(l+r)>>1;
40             if(check(mid)) r=mid;
41             else l=mid;
42         }
43         ans+=l;
44         printf("%d
",ans);
45     }
46     return 0;
47 }
48 
49 int sb=hh();
50 int main(int argc,char**argv) {;}

代码

差分约束

记录前缀和S[i],i>=8时首先要满足条件 s[i]-s[i-8]>=a[i]

0<=s[i]-s[i-1]<=b[i]

当i<8时有s[23]-s[16+i]+s[i]>=a[i]

因为第三个式子不满足差分约束形式，可以看出s[23]有单调性，可以二分…所以可以二分答案当常量处理

Spfa负环则无解

还有一种网络流做法，表示很懵逼。

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <queue>
 4 using namespace std;
 5 
 6 #define N 33
 7 
 8 struct edge{
 9     int t, n, l;
10 }e[N * N];
11 
12 int h[N];
13 int tote;
14 
15 void adde(int u, int v, int l) {
16     e[++tote].t = v;
17     e[tote].l = l;
18     e[tote].n = h[u];
19     h[u] = tote;
20     return ;
21 }
22 
23 int d[N];
24 bool inq[N];
25 
26 bool spfa() {
27     queue<int> Q;
28     for (int i = 0; i <= 24; i++) d[i] = -1e9, inq[i] = false;
29     d[0] = 0; inq[0] = true; Q.push(0);
30     while (!Q.empty()) {
31         int u = Q.front(); Q.pop(); inq[u] = false;
32         if (d[u] > 1000) return false;
33         for (int i = h[u]; i; i = e[i].n) {
34             int v = e[i].t, l = e[i].l;
35             if (d[v] < d[u] + l) {
36                 d[v] = d[u] + l;
37                 if (!inq[v]) {
38                     inq[v] = true;
39                     Q.push(v);
40                 }
41             }
42         }
43     }
44     return true;
45 }
46 
47 int a[30], b[30];
48 
49 bool solve(int ans) {
50     for (int i = 0; i <= 24; i++) h[i] = 0;
51     tote = 0;
52     for (int i = 9; i <= 24; i++) adde(i - 8, i, a[i]);
53     for (int i = 1; i <= 8; i++) adde(i + 16, i, a[i] - ans);
54     for (int i = 1; i <= 24; i++) adde(i - 1, i, 0);
55     for (int i = 1; i <= 24; i++) adde(i, i - 1, -b[i]);
56     adde(0, 24, ans); adde(24, 0, -ans);
57     return spfa();
58 }
59 
60 int main(int argc, char ** argv) {
61     freopen("cashier.in", "r", stdin);
62     freopen("cashier.out", "w", stdout);
63     int test;
64     scanf("%d", &test);
65     for (int i = 1; i <= test; i++) {
66         for (int i = 1; i <= 24; i++) scanf("%d", &a[i]);
67         for (int i = 1; i <= 24; i++) scanf("%d", &b[i]);
68         int ans = 0;
69         while (true) {
70             if (++ans > 1000) {
71                 ans = -1; break;
72             }
73             if (solve(ans)) break;
74         }
75         printf("%d
", ans);
76     }
77     fclose(stdin);
78     fclose(stdout);
79     return 0;
80 }

代码

线段树

部分分可以dp f[i][j]表示前i个数选了j个的答案

f[i][j]=f[i-1][j]+f[i-1][j-1]*a[i] (i选不选)

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

直接给std吧。