[原创]“玲珑杯”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 计算几何你瞎暴力

——————————————————————————————————————————
观察数据范围，发现点只有111111个，那么可以记录每种点的个数，然后平方枚举计数即可，

(话说我当时为什么要写一个树状数组…用数组的话 多么简单…最后处理下前缀和就行了啊)

–

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的情况 所有ik=0i^k = 0 所以答案就是n%pn\%p

首先有(p+i)k≡(i)kmod  p(p+i)^k \equiv (i)^k \mod p

然后发现存在长度为p的循环节 然后打表找规律发现
对于一般情况下一段循环节队结果的贡献是0的
如果k为p-1的倍数。则除[i%p=0][i\%p=0]时贡献为0 其他情况下贡献是1

由费马小定理可知ap−1≡1mod  pa^{p-1}\equiv 1 \mod p 所以这里有ak≡1mod  pa^{k}\equiv 1 \mod p

而由于有0≤n−p≤1000\le n-p \le100 所以不成一个循环节的部分暴力就行了.
成循环节的部分 分类讨论下即可

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(n2)O(n^2)的dp,
dp[i]=min{dp[j]+2x[i]−x[j]∥j∈[1,i)}+adp[i] = min\{dp[j]+2^{x[i]-x[j]}\|j\in[1,i)\}+a

但是考虑到2x[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,因为每次操作区间都是在一行内的连续区间)

所以对我来说难点就是处理二进制标记上,不是很好处理啊,码力不够啊…