hdu 5288
题意:f (L,R)表示下标i在区间内且除了a[i]本身,区间内的其他数都不能整除a[i],这样的数的个数。现在给出n,和a[1]~a[n],求∑i=1~n∑j=i~n f (i,j) mod (10^9+7)。
做法:定义L[i]表示在a[i]左边第一个整除的数的下标,R[i]表示在a[i]右边第一个整除的数的下标,则ans += (R[i] - i) * (i - L[i])。pre[i]表示 数i上一次出现的位置
求R[i]:从左到右访问每一个位置i,并用pre[i]标记,对于每一个数a[i],看其倍数是否在其之前出现,如果已经出现,那么已经出现的那个数,它的R[i]就是min(R[i],i)。同理求出L[i]。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 10 using namespace std;11 12 #define LL long long13 #define eps 1e-814 #define inf 0x3f3f3f3f15 #define N 20001016 #define Max 1001017 #define M 40002018 #define mod 100000000719 20 int L[N], R[N],a[N], pre[N];21 int main(){22 int n;23 while(scanf("%d", &n) != EOF){24 memset(pre, 0, sizeof pre);25 for(int i = 1; i <= n; ++i){26 scanf("%d", &a[i]);27 L[i] = 0, R[i] = n + 1;28 for(int j = a[i]; j < Max; j += a[i]){29 if(pre[j] && R[pre[j]] == n + 1) R[pre[j]] = i;30 }31 pre[a[i]] = i;32 }33 memset(pre, 0, sizeof pre);34 for(int i = n; i > 0; --i){35 for(int j = a[i]; j < Max; j += a[i]){36 if(pre[j] && L[pre[j]] == 0) L[pre[j]] = i;37 }38 pre[a[i]] = i;39 }40 LL ans = 0;41 for(int i = 1; i <= n; ++i){42 ans += (LL)(i - L[i]) * (LL)(R[i] - i);43 ans %= mod;44 }45 printf("%I64d\n", ans);46 }47 return 0;48 }
hdu 5289
题意:问有多少个区间满足 区间最大 - 区间最小 < k。
做法:枚举左端点,二分右端点,用st算法求区间最大最小。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 10 using namespace std;11 12 #define LL long long13 #define eps 1e-814 #define inf 0x3f3f3f3f15 #define N 10001016 #define M 40002017 #define mod 100000000718 #define lson l, m, rt << 119 #define rson m + 1, r, rt << 1 | 120 21 int mi[N][20], mx[N][20], a[N], n;22 void RMQ_init(){23 for(int i = 1; i <= n; ++i) mi[i][0] = mx[i][0] = a[i];24 for(int j= 1; (1 << j) <= n + 1; ++j)25 for(int i = 1; i + (1 << j) - 1 <= n; ++i)26 mi[i][j] = min(mi[i][j-1], mi[i + (1 << (j-1))][j-1]),27 mx[i][j] = max(mx[i][j-1], mx[i + (1 << (j-1))][j-1]);28 }29 void query(int L, int R, int &Max, int &Min){30 int k = 0;31 while((1 << (k+1)) <= R - L + 1) k++;32 Max = max(mx[L][k], mx[R - (1< '9') ch = getchar();38 while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();39 return x;40 }41 int main(){42 int cas, k;43 scanf("%d", &cas);44 while(cas--){45 scanf("%d%d", &n, &k);46 for(int i = 1; i <= n; ++i)47 a[i] = read_int();48 RMQ_init();49 LL ans = 0;50 for(int i = 1; i <= n; ++i){51 int Max, Min, L = i, R = n;52 while(L < R){53 int mid = (L + R) >> 1;54 Min = inf, Max = -inf;55 query(i, mid, Max, Min);56 if(Max - Min >= k)57 R = mid;58 else L = mid + 1;59 }60 Min = inf, Max = -inf;61 query(i, L, Max, Min);62 if(Max - Min >= k)63 L--;64 ans += (L - i + 1);65 }66 printf("%I64d\n", ans);67 }68 return 0;69 }
hdu 5191
题意:有n种糖果,每种有ai个,要分给两个人,每个糖果可以分或者不分,问你有多少种方案,使得两个人分得的糖果一样多。
做法:dp[i][j]表示前 i 种糖果,第一个人比第二个人多 j 个糖果的方案数。考虑dp[i][j] 对 dp[i+1][..]的影响,则设分给第一个人 x 个,第二个人 y 个,只要 x + y <= a[i+1],都在计算范围内,则dp[i][j] 对 dp[i+1][j]的贡献有 a[i+1] / 2次,对 dp[i+1][j+1]的贡献是(a[i+1] - 1)/2次。dp[i][j]对dp[i+1][..]的贡献按照a[i+1]的奇偶性不同会呈现一种类似等差数列的方式。然后算一算就好了。。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 11 #define inf 0x3f3f3f3f12 #define eps 1e-613 #define MP make_pair14 #define LL long long15 #define N 40001016 #define M 20002017 #define mod 100000000718 19 int a[220];20 int dp[2][N<<1], p[N<<1];21 void add(int &x, int y){22 x = x + y;23 if(x >= mod) x -= mod;24 if(x < 0) x += mod;25 }26 void cal(int i, int v, int x){27 if(v & 1){28 add(p[i-v], x), add(p[i+1], -x);29 add(p[i+3], -x), add(p[i+v+4], x);30 31 add(p[i-v+1], x), add(p[i+2], mod-2*x);32 add(p[i+v+3], x);33 }34 else{35 add(p[i-v], x), add(p[i+2], mod-2*x);36 add(p[i+v+4], x);37 38 add(p[i-v+1], x), add(p[i+1], -x);39 add(p[i+3], -x), add(p[i+v+3], x);40 }41 }42 int main(){43 int cas;44 scanf("%d", &cas);45 while(cas--){46 int n;47 scanf("%d", &n);48 for(int i = 0; i < n; ++i)49 scanf("%d", &a[i]);50 memset(dp, 0, sizeof dp);51 memset(p, 0, sizeof p);52 int all = 0, cur = 1, pre = 0;53 dp[0][N] = 1;54 for(int i = 0; i < n; ++i){55 all += a[i];56 for(int j = N - all - 2; j <= N + all + 2; ++j)57 dp[cur][j] = p[j] = 0;58 for(int j = N - all; j <= N + all; ++j){59 if(dp[pre][j] == 0) continue;60 cal(j, a[i], dp[pre][j]);61 }62 int val = 0, sum = 0;63 for(int j = N - all; j <= N + all; j += 2){64 add(val, p[j]);65 add(sum, val);66 dp[cur][j] = sum;67 }68 val = sum = 0;69 for(int j = N - all + 1; j < N + all + 1 ; j += 2){70 add(val, p[j]);71 add(sum, val);72 dp[cur][j] = sum;73 }74 cur ^= 1, pre ^= 1;75 }76 printf("%d\n", dp[pre][N]);77 }78 return 0;79 }
hdu 5294
做法:求最短路,总边数 - 最少边数的最短路 的边数 即为第二个问答案。在所有的最短路的边上 构每条边流量为1的新图,求最大流即为第一个问的答案
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 10 using namespace std; 11 12 #define LL long long 13 #define eps 1e-8 14 #define inf 0x3f3f3f3f 15 #define N 5010 16 #define M 120020 17 #define mod 1000000007 18 19 struct edge { 20 int u, v, cap, flow, nxt; 21 void set(int _u, int _v, int _cap, int _flow, int _nxt) { 22 u = _u, v = _v, cap = _cap, flow = _flow, nxt = _nxt; 23 } 24 }; 25 26 struct dinic { 27 int s, t, fst[N], cc, d[N], cur[N]; 28 edge e[M]; 29 void init() { 30 memset(fst, -1, sizeof(fst)); 31 cc = 0; 32 } 33 void add(int u, int v, int cap) { 34 e[cc].set(u, v, cap, 0, fst[u]), fst[u] = cc++; 35 e[cc].set(v, u, 0, 0, fst[v]), fst[v] = cc++; 36 } 37 bool bfs() { 38 memset(d, -1, sizeof(d)); 39 queue q; 40 d[s] = 0, q.push(s); 41 while(!q.empty()) { 42 int u = q.front(); q.pop(); 43 for(int i = fst[u]; ~i; i = e[i].nxt) { 44 int v = e[i].v; 45 if(d[v] == -1 && e[i].cap > e[i].flow) { 46 d[v] = d[u] + 1; 47 q.push(v); 48 } 49 } 50 } 51 return d[t] != -1; 52 } 53 int dfs(int x, int a) { 54 if(x == t || a == 0) return a; 55 int f, flow = 0; 56 for(int &i = cur[x]; ~i; i = e[i].nxt) { 57 if(i == inf) i = fst[x]; 58 if(i == -1) break; 59 int v = e[i].v; 60 if(d[v] == d[x] + 1 && (f = dfs(v, min(a, e[i].cap - e[i].flow))) > 0) { 61 a -= f, e[i ^ 1].flow -= f; 62 e[i].flow += f, flow += f; 63 if(!a) break; 64 } 65 } 66 return flow; 67 } 68 int go(int s, int t) { 69 this -> s = s, this -> t = t; 70 int flow = 0; 71 while(bfs()) { 72 memset(cur, 0x3f, sizeof(cur)); 73 flow += dfs(s, inf); 74 } 75 return flow; 76 } 77 }go; 78 int fst[N], vv[M], nxt[M], cost[M], e; 79 void init(){ 80 memset(fst, -1, sizeof fst); 81 e = 0; 82 } 83 void add(int u, int v, int c){ 84 vv[e] = v, nxt[e] = fst[u], cost[e] = c, fst[u] = e++; 85 } 86 int d[N], n; 87 bool vis[N]; 88 void spfa(){ 89 memset(d, 0x3f, sizeof d); 90 memset(vis, 0, sizeof vis); 91 queue q; 92 q.push(1); d[1] = 0, vis[1] = 1; 93 while(!q.empty()){ 94 int u = q.front(); q.pop(); 95 vis[u] = 0; 96 for(int i = fst[u]; ~i; i = nxt[i]){ 97 int v = vv[i], c = cost[i]; 98 if(d[v] > d[u] + c){ 99 d[v] = d[u] + c;100 if(!vis[v]) vis[v] = 1, q.push(v);101 }102 }103 }104 }105 vector g[N];106 int bfs(){107 memset(d, 0x3f, sizeof d);108 queue q;109 d[1] = 0, vis[1] = 1;110 q.push(1);111 while(!q.empty()){112 int u = q.front(); q.pop();113 for(int i = 0; i < g[u].size(); ++i){114 int v = g[u][i];115 if(!vis[v])116 d[v] = d[u] + 1, vis[v] = 1, q.push(v);117 }118 }119 return d[n];120 }121 int main(){122 int m;123 while(scanf("%d%d", &n, &m) != EOF){124 init();125 for(int i = 0; i < m; ++i){126 int u, v, c;127 scanf("%d%d%d", &u, &v, &c);128 add(u, v, c), add(v, u, c);129 }130 spfa();131 go.init();132 for(int i = 1; i <= n; ++i)133 g[i].clear();134 for(int i = 1; i <= n; ++i)135 for(int j = fst[i]; ~j; j = nxt[j]){136 int v = vv[j], c = cost[j];137 if(d[v] == d[i] + c){138 go.add(i, v, 1);139 g[i].push_back(v);140 }141 }142 printf("%d %d\n", go.go(1, n), m - bfs());143 }144 return 0;145 }
hdu 5295
题意:给出AB、BC、CD、DA、EF的长度,求一个合法的A、B、C、D的坐标。
一张不知道哪里来的图。
做法:固定BC,然后求出A'和G点的坐标,再求出A和D的坐标。。注意有精度误差。eps最好是1e-5或者1e-4。还有注意圆重合、内切、外切的情况。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 11 #define inf 0x3f3f3f3f12 #define eps 1e-413 #define pii pair 14 #define MP make_pair15 #define LL long long16 #define N 10001017 #define M 20002018 #define mod 100000000719 20 int dcmp( double x ){21 if( fabs( x ) < eps ) return 0;22 return x < 0 ? -1 : 1;23 }24 struct point{25 double x, y;26 point( double x = 0, double y = 0 ) : x(x), y(y) {}27 point operator + ( const point &b ) const{28 return point( x + b.x, y + b.y );29 }30 point operator - ( const point &b ) const{31 return point( x - b.x, y - b.y );32 }33 point operator * ( const double &k ) const{34 return point( x * k, y * k );35 }36 point operator / ( const double &k ) const{37 return point( x / k, y / k );38 }39 bool operator < ( const point &b ) const{40 return dcmp( x - b.x ) < 0 || dcmp( x - b.x ) == 0 && dcmp( y - b.y ) < 0;41 }42 bool operator == ( const point &b ) const{43 return dcmp( x - b.x ) == 0 && dcmp( y - b.y ) == 0;44 }45 double len(){46 return sqrt( x * x + y * y );47 }48 void out(){49 printf("%.8lf %.8lf\n", x, y);50 }51 };52 void circle_cross( point a, double ra, point b, double rb, point &v1, point &v2 ){53 if(a == b && dcmp(ra - rb) == 0){54 v1 = a + point(0, ra);55 v2 = a - point(0, ra);56 return ;57 }58 double d = ( a - b ).len();59 if(dcmp(d + min(ra, rb) - max(ra, rb)) == 0){60 if(ra > rb) swap(ra, rb), swap(a, b);61 v1 = v2 = a + (a - b) / d * ra;62 return ;63 }64 if(dcmp(d - ra - rb) == 0){65 v1 = v2 = a + (b - a) / d * ra;66 return ;67 }68 double da = ( ra * ra + d * d - rb * rb ) / ( 2 * ra * d );69 double aa = atan2( (b-a).y, (b-a).x );70 double rad = acos( da );71 v1 = point( a.x + cos( aa - rad ) * ra, a.y + sin( aa - rad ) * ra );72 v2 = point( a.x + cos( aa + rad ) * ra, a.y + sin( aa + rad ) * ra );73 }74 75 double ab, bc, cd, da, ef;76 point a, b, c, d;77 void solve(){78 c = point(0, 0), b = point(bc, 0);79 point a2, tmp;80 circle_cross(c, da, b, 2*ef, a2, tmp);81 point g = a2 - c + b;82 circle_cross(c, cd, g, ab, d, tmp);83 a = d - g + b;84 a.out(), b.out(), c.out(), d.out();85 }86 int main(){87 //freopen("tt.txt", "r", stdin);88 int cas, kk = 1;89 scanf("%d", &cas);90 while(cas--){91 printf("Case #%d:\n", kk++);92 scanf("%lf%lf%lf%lf%lf", &ab, &bc, &cd, &da, &ef);93 solve();94 }95 return 0;96 }
hdu5297
题意:给你n 和 r。求出从1开始,去除掉所有能够写成a^b(2 <= b <= r)的数后的第n个数的值。
做法:先预处理出5 - 60以内的所有素数次方。对于每次询问,二分答案。对于2次方和3次方,可以用容斥去掉。然后再处理其他<=r 的次方 的数。有几个坑点。
1.2^2^5、2^3^5、3^2^5、3^3^5……2^2^7、2^3^7、3^2^7、3^3^7……等在预处理的时候不要算进去,因为会在用容斥处理了2次方和3次方的时候去掉了。
2.2^5^7、2^5^11、3^5^7有可能被减去两次,要加回来。
3.二分完答案后一定要再check一下,有可能这个答案刚好是一个要被删的数。
我是按照题解说的做的。还有用莫比乌斯做的(看不懂),以及直接容斥过的(不会精度误差吗)。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 9 using namespace std; 10 11 #define LL long long 12 #define eps 1e-8 13 #define N 210 14 #define M 20020 15 16 int prime[N], tot; 17 bool vis[N]; 18 const LL Max = 2 * 1e18, Lar = 1e18; 19 const LL a35 = 1LL << 35, a55 = 1LL << 55, b35 = 50031545098999707LL; 20 LL a[30][5000]; 21 LL qpow(LL x, int k){ 22 LL ret = 1; 23 while(k){ 24 if(k & 1){ 25 double val = (double)ret * x; 26 if(val > Max) 27 return Max + 1; 28 ret *= x; 29 } 30 x *= x; 31 k >>= 1; 32 } 33 return ret; 34 } 35 bool check2(int j){ 36 int tmp = sqrt(j+0.5); 37 if(tmp * tmp == j) return 1; 38 tmp = pow(j +0.5, 1.0/3); 39 for(int i = tmp - 10; i < tmp + 11; ++i) 40 if(i * i * i == j) return 1; 41 return 0; 42 } 43 int b[20]; 44 void init(){ 45 for(int i = 2; i < 60; ++i){ 46 if(!vis[i]) prime[++tot] = i; 47 for(int j = i + i; j < 60; j +=i) 48 vis[j] = 1; 49 } 50 for(int i = 3; i <= tot; ++i){ 51 int cnt = 0, j = 2; 52 while(1){ 53 LL tmp = qpow(j, prime[i]); 54 if(tmp > Max) break; 55 j++, a[i][cnt++] = tmp; 56 while(check2(j)) j++; 57 } 58 b[i] = cnt; 59 } 60 } 61 62 LL n; int r; 63 bool check(LL x){ 64 if(x < 60 && !vis[x]) return 0; 65 LL ret = x, cnt = 0; 66 while(ret % 2 == 0) ret /= 2, cnt++; 67 if(ret == 1 && cnt <= r) return 1; 68 ret = x, cnt = 0; 69 while(ret % 3 == 0) ret /= 3, cnt++; 70 if(ret == 1 && cnt <= r) return 1; 71 for(int i = 3; i <= tot; ++i){ 72 if(prime[i] > r) break; 73 int L = 0, R = b[i]; 74 while(L < R){ 75 int mid = (L + R) >> 1; 76 if(a[i][mid] < n) 77 L = mid + 1; 78 else R = mid; 79 } 80 if(a[i][L] == x) return 1; 81 } 82 return 0; 83 } 84 LL x, y, z; 85 LL f(LL val){ 86 LL temp = val; 87 x = pow(val+0.5, 1.0/2), y = pow(val+0.5, 1.0/3), z = pow(val+0.5, 1.0/6); 88 if(2 <= r) temp -= x; 89 if(3 <= r) temp -= y, temp += z; 90 for(int i = 3; i <= tot; ++i){ 91 if(prime[i] > r) break; 92 int L = upper_bound(a[i], a[i]+b[i], val) - a[i]; 93 if(L == 0) break; 94 temp -= L; 95 } 96 if(val >= a35 && r >= 7) temp++; 97 if(val >= a55 && r >= 11) temp++; 98 if(val >= b35 && r >= 7) temp++; 99 return temp;100 }101 int main(){102 //freopen("1010.in", "r", stdin);103 //freopen("tt.txt", "w", stdout);104 init();105 int cas;106 scanf("%d", &cas);107 while(cas--){108 109 scanf("%I64d%d", &n, &r);110 LL L = n, R = n + 10000000000;111 while(L < R){112 LL mid = (L + R) >> 1;113 if(f(mid) < n)114 L = mid + 1;115 else R = mid;116 }117 //cout < << endl;118 while(check(L))119 L++;120 printf("%I64d\n", L);121 }122 return 0;123 }
hdu5298
题意:给一些平面和球的方程,要进行染色(红色和黄色)、以及一些要染成黄色的点(点所在的区域要染成黄色),有q个询问,每次询问一个点,问你这个点在的区域是什么颜色。
做法:首先,如果没有给出要染成黄色的点,那么询问的答案就是both。如果给出了黄色的点,那么染色方案就确定了,接下来输入要染成黄色的点 有没有冲突,有冲突就impossible。没有就可以回答询问了。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 9 using namespace std; 10 11 #define LL long long 12 #define eps 1e-8 13 #define N 210 14 #define M 20020 15 16 int prime[N], tot; 17 bool vis[N]; 18 const LL Max = 2 * 1e18, Lar = 1e18; 19 const LL a35 = 1LL << 35, a55 = 1LL << 55, b35 = 50031545098999707LL; 20 LL a[30][5000]; 21 LL qpow(LL x, int k){ 22 LL ret = 1; 23 while(k){ 24 if(k & 1){ 25 double val = (double)ret * x; 26 if(val > Max) 27 return Max + 1; 28 ret *= x; 29 } 30 x *= x; 31 k >>= 1; 32 } 33 return ret; 34 } 35 bool check2(int j){ 36 int tmp = sqrt(j+0.5); 37 if(tmp * tmp == j) return 1; 38 tmp = pow(j +0.5, 1.0/3); 39 for(int i = tmp - 10; i < tmp + 11; ++i) 40 if(i * i * i == j) return 1; 41 return 0; 42 } 43 int b[20]; 44 void init(){ 45 for(int i = 2; i < 60; ++i){ 46 if(!vis[i]) prime[++tot] = i; 47 for(int j = i + i; j < 60; j +=i) 48 vis[j] = 1; 49 } 50 for(int i = 3; i <= tot; ++i){ 51 int cnt = 0, j = 2; 52 while(1){ 53 LL tmp = qpow(j, prime[i]); 54 if(tmp > Max) break; 55 j++, a[i][cnt++] = tmp; 56 while(check2(j)) j++; 57 } 58 b[i] = cnt; 59 } 60 } 61 62 LL n; int r; 63 bool check(LL x){ 64 if(x < 60 && !vis[x]) return 0; 65 LL ret = x, cnt = 0; 66 while(ret % 2 == 0) ret /= 2, cnt++; 67 if(ret == 1 && cnt <= r) return 1; 68 ret = x, cnt = 0; 69 while(ret % 3 == 0) ret /= 3, cnt++; 70 if(ret == 1 && cnt <= r) return 1; 71 for(int i = 3; i <= tot; ++i){ 72 if(prime[i] > r) break; 73 int L = 0, R = b[i]; 74 while(L < R){ 75 int mid = (L + R) >> 1; 76 if(a[i][mid] < n) 77 L = mid + 1; 78 else R = mid; 79 } 80 if(a[i][L] == x) return 1; 81 } 82 return 0; 83 } 84 LL x, y, z; 85 LL f(LL val){ 86 LL temp = val; 87 x = pow(val+0.5, 1.0/2), y = pow(val+0.5, 1.0/3), z = pow(val+0.5, 1.0/6); 88 if(2 <= r) temp -= x; 89 if(3 <= r) temp -= y, temp += z; 90 for(int i = 3; i <= tot; ++i){ 91 if(prime[i] > r) break; 92 int L = upper_bound(a[i], a[i]+b[i], val) - a[i]; 93 if(L == 0) break; 94 temp -= L; 95 } 96 if(val >= a35 && r >= 7) temp++; 97 if(val >= a55 && r >= 11) temp++; 98 if(val >= b35 && r >= 7) temp++; 99 return temp;100 }101 int main(){102 //freopen("1010.in", "r", stdin);103 //freopen("tt.txt", "w", stdout);104 init();105 int cas;106 scanf("%d", &cas);107 while(cas--){108 109 scanf("%I64d%d", &n, &r);110 LL L = n, R = n + 10000000000;111 while(L < R){112 LL mid = (L + R) >> 1;113 if(f(mid) < n)114 L = mid + 1;115 else R = mid;116 }117 //cout < << endl;118 while(check(L))119 L++;120 printf("%I64d\n", L);121 }122 return 0;123 }