[原创]“玲珑杯”ACM比赛 Round #18 【4/5】 [待补-splay维护256位二进制标记]
2017-07-15 23:48:58 Tabris_ 阅读数:339
博客爬取于2020-06-14 22:39:40
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。https://blog.csdn.net/qq_33184171/article/details/75194944
题目链接:http://www.ifrog.cc/acm/contest/1020
1143 计算几何你瞎暴力 —————————————————————————————————————————— 观察数据范围,发现点只有1111 11个,那么可以记录每种点的个数,然后平方枚举计数即可,
(话说我当时为什么要写一个树状数组…用数组的话 多么简单…最后处理下前缀和就行了啊)
–
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 # include <bits/stdc++.h> typedef long long int LL; using namespace std; # define abs(x) ((x)>0?(x):-(x)) const int N = 2222+7; const int MOD = 1e9+7; const int INF = (~(1<<31)); /*********************************************/ int sum[1111]; LL zero = 0; void update(int i,LL v){ if(i==0) {zero+=v; return ;} for(;i<111;i+=(i&-i)) sum[i]+=v; } LL getSum(int i){ LL ans = 0; for(;i;i-=(i&-i)) ans+=sum[i]; return ans; } LL a[11][11][11]; struct node { int x,y,z; }b[11*11*11*10]; int l = 0; void solve(){ for(int i=1;i<=l;i++){ update(0,(a[b[i].x][b[i].y][b[i].z]-1)*a[b[i].x][b[i].y][b[i].z]/2); for(int j=i+1;j<=l;j++){ update(abs(b[i].x-b[j].x)+abs(b[i].y-b[j].y)+abs(b[i].z-b[j].z), a[b[i].x][b[i].y][b[i].z]*a[b[j].x][b[j].y][b[j].z]); } } } int main(){ for(int i=0;i<=10;i++)for(int j=0;j<=10;j++)for(int k=0;k<=10;k++) b[++l].x=i,b[ l].y=j,b[ l].z=k; int _,n,q;scanf("%d",&_); while(_--){ scanf("%d%d",&n,&q); zero = 0; memset(sum,0,sizeof(sum)); memset(a,0,sizeof(a)); for(int i=1,x,y,z;i<=n;i++){ scanf("%d%d%d",&x,&y,&z); a[x][y][z]++; } solve(); for(int i=1,x;i<=q;i++){ scanf("%d",&x); if(x>50) x=50; printf("%lld\n",getSum(x)+zero); } } return 0; }
1144 数论你还会快速幂 —————————————————————————————————————————— 要注意k为0的情况 所有i k = 0 i^k = 0 i k = 0 所以答案就是n % p n\%p n % p
首先有( p + i ) k ≡ ( i ) k m o d p (p+i)^k \equiv (i)^k \mod p ( p + i ) k ≡ ( i ) k mod p
然后发现存在长度为p的循环节 然后打表找规律发现 对于一般 情况下一段循环节队结果的贡献是0的 如果k为p-1的倍数。则除[ i % p = 0 ] [i\%p=0] [ i % p = 0 ] 时贡献为0 其他情况下贡献是1
由费马小定理可知a p − 1 ≡ 1 m o d p a^{p-1}\equiv 1 \mod p a p − 1 ≡ 1 mod p 所以这里有a k ≡ 1 m o d p a^{k}\equiv 1 \mod p a k ≡ 1 mod p
而由于有0 ≤ n − p ≤ 100 0\le n-p \le100 0 ≤ n − p ≤ 100 所以不成一个循环节的部分暴力就行了. 成循环节的部分 分类讨论下即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 # include <bits/stdc++.h> typedef long long int LL; using namespace std; # define abs(x) ((x)>0?(x):-(x)) const int N = 1e6+7; const int MOD = 1e9+7; const int INF = (~(1<<31)); /*********************************************/ LL qc(LL a,LL b,LL c){ LL res = 0; while(b){ if(b&1) res=(res+a)%c; b>>=1,a=(a+a)%c; } return res; } LL qmod(LL a,LL b,LL c) { LL res = 1ll; while(b) { if(b&1) res=qc(res,a,c); b>>=1,a=qc(a,a,c); } return res; } int main() { LL n,k,p; int _; scanf("%d",&_); while(_--) { scanf("%lld%lld%lld",&n,&k,&p); if(k == 0){ printf("%lld\n",n%p); continue; } LL t = n,sum = 0; n %= p; for(LL i=1; i<=n; i++) { sum+=qmod(i,k,p); sum%=p; } if( k%(p-1) != 0 ) { printf("%lld\n",sum%p); } else { t/=p; sum += qc( (p-1), t , p); printf("%lld\n",sum%p); // puts("--"); } } return 0; }
1146 图论你先敲完模板 —————————————————————————————————————————— 首先考虑暴力做,有一个O ( n 2 ) O(n^2) O ( n 2 ) 的dp,d p [ i ] = m i n { d p [ j ] + 2 x [ i ] − x [ j ] ∥ j ∈ [ 1 , i ) } + a dp[i] = min\{dp[j]+2^{x[i]-x[j]}\|j\in[1,i)\}+a d p [ i ] = min { d p [ j ] + 2 x [ i ] − x [ j ] ∥ j ∈ [ 1 , i )} + a
但是考虑到2 x [ i ] − x [ j ] 2^{x[i]-x[j]} 2 x [ i ] − x [ j ] 增长极快,所以我只要向左找至多 60个就行了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 # include <bits/stdc++.h> typedef long long int LL; using namespace std; # define abs(x) ((x)>0?(x):-(x)) const int N = 1e6+7; const int MOD = 1e9+7; const int INF = (~(1<<31)); /*********************************************/ LL n,a; LL x[N]; LL dp[N]; int main(){ int _;scanf("%d",&_); while(_--){ scanf("%lld%lld",&n,&a); for(int i=1;i<=n;i++){ scanf("%lld",&x[i]); } dp[1]=0; for(int i=2;i<=n;i++){ dp[i]=dp[i-1]+a+(1ll<<(x[i]-x[i-1])); for(int j=i-1;j;j--){ if(x[i]-x[j]>60) break; dp[i]=min(dp[i],dp[j]+a+(1ll<<(x[i]-x[j]))); } } printf("%lld\n",dp[n]); } return 0; }
1147 最后你还是AK了 —————————————————————————————————————————— 考虑每条边对结果的贡献, 最大化的利用的就是把a,b放到边的左右两边 ,且使最小时最大就行了,这就是这条边贡献的倍数
就按照边的贡献倍数最大的加最大的c[i] ,次大的加次大的c[i] …就行了
可以dfs一边处理 出每条边的贡献倍数,
然后贪心加过去就好了
然后注意这个爆栈的问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 //#pragma comment(linker, "/STACK:102400000,102400000") # define OPENSTACK # include <bits/stdc++.h> typedef long long int LL; using namespace std; # define abs(x) ((x)>0?(x):-(x)) const int N = 111111+7; /*********************************************/ int n,k; struct edge{ int to,next,w; }G[N<<1]; int head[N],tot; void add(int u,int v,int w){ G[tot].w=w,G[tot].to=v,G[tot].next=head[u],head[u]=tot++; } struct node { int w,x; }e[N]; int l; int dp[N]; void dfs(int u,int f=0,int w=0){ dp[u]=1; for(int i=head[u],to,w;i != -1;i=G[i].next){ to = G[i].to; w = G[i].w; if(to == f) continue ; dfs(to,u,w); dp[u]+=dp[to]; } e[++l].w =w; e[ l].x =min(dp[u],n-dp[u]); } bool cmp(node a,node b){return a.x>b.x;} bool cmp2(int a,int b){return a>b;} int c[N]; int main(){ #ifdef OPENSTACK int size = 64 << 20; // 64MB char *p = (char*)malloc(size) + size; #if (defined _WIN64) or (defined __unix) __asm__("movq %0, %%rsp\n" :: "r"(p)); #else __asm__("movl %0, %%esp\n" :: "r"(p)); #endif #endif int _;scanf("%d",&_); while(_--){ tot = l = 0;memset(head,-1,sizeof(head)); scanf("%d%d",&n,&k); for(int i=2,u,v,w;i<=n;i++){ scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } for(int i=1;i<=k;i++) scanf("%d",&c[i]); dfs(1); sort(e+1,e+l+1,cmp); // for(int i=0;i<=l;i++) printf("%d %d\n",e[i].w,e[i].x); sort(c+1,c+k+1,cmp2); for(int i=1;i<=k;i++) e[i].w+=c[i]; LL ans = 0; for(int i=1;i<l;i++){ // printf("%d %d\n",e[i].w,e[i].x); ans+=1LL*e[i].w*e[i].x; } printf("%lld\n",ans); } #ifdef OPENSTACK exit(0); #else return 0; #endif }
1148 数据结构你干瞪眼啊 —————————————————————————————————————————— 虽然以我的能力几乎不可能在现场调完这道题,但是还是嘴巴了下
当时考虑了256个颜色就可以用4个64位整形或者长度为256的bitset维护
由于有了区间翻转,所以一定要用splay
对于方阵的处理 可以建立n个splay (后来题解说可以仅简历一个splay,因为每次操作区间都是在一行内的连续区间)
所以对我来说难点就是处理二进制标记上,不是很好处理啊,码力不够啊…