CXJY-Day 3

Author Avatar
Axell Jul 31, 2019
  • Read this article on other devices

FLAG: T2还不会做，记得填坑

锻炼（exercise）

【题目描述】

小A作为一个游戏高手，但是平日里却缺乏一些必要的锻炼，而为了锻炼的积极性，它号召了n个一起玩游戏的朋友陪他一起锻炼。
他们准备在一张n个点m条边的无向连通图中进行他们的锻炼，第i个人的目标是从第1个点跑到第i个点，因为他们并不是很想锻炼，所以他们会选择最短的道路跑到目的地。
但是第二天，他们惊奇地发现所有边竟然都增长了1米，在接下来的时间里，他们发现每一天每条边都增长了1米，所以他们想要知道，在计划的T天里，他们总共要跑的距离之和。

【输入数据】

三个整数n,m,T表示图中节点个数，边数，总共的天数。
接下来m行，每行三个整数Xi,Yi,Di表示Xi与Yi之间有一条长度为Di米的边。

【输出数据1】

一个整数ans，表示在T天里，所有人跑的距离之和，答案要对(1e9+7)取模。

【样例输入1】

2 1 597855229 
1 2 1

【样例输出2】

469240783

【样例输入2】

5 6 0
1 2 1
2 3 2
1 5 1
1 3 2
1 4 4
3 4 1

【样例输出】

7

【数据范围】

对于30%的数据，$n≤50,T≤100$。
对于60%的数据，$n≤50$。
对于100%的数据，$n≤2500,m≤5000, 0≤T≤1e9,Di≤800000$。

【后记】

什么？你问我小A的锻炼效果？
作为游戏中的第一人，他当然也是要在这次锻炼里当做那个终点为1号节点的人啦。
训练效果肯定是很显著的啦。

题解

可以用$dis[i][j]$表示从1到达i点，经过j条边所需费用
直接分层dp即可
然后可以发现一开始是j较大处比较优，然后逐渐j减小，因此可以发现每个$dis[i][j]$对应直接坐标系中的一条直线$y=ax+b,a=j,b=dis[i][j]$
题目所求的就是对于$1<=i<=t$,所有直线的纵坐标最小值之和，可以发现每次选中的就是最底下的一圈，即一个凸包
凸包用单调栈维护即可，具体还是看代码把
注意很多地方要强转long long

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node{
	int Next,y,v;
}Pth[10005];
struct seg{
	ll a,b;
}st[2505];
int head[2505],cnt;
void add(int x,int y,int v){
	cnt++;
	Pth[cnt]={head[x],y,v};
	head[x]=cnt;
}
int n,m,t;
ll dis[2505][2505],dig[2505],INF=0x3f3f3f3f3f3f3f3fLL,ans,mod=1e9+7;
int top;

void dp(){
	for (int i=1;i<=n;++i){
		for (int j=0;j<n;++j){
			dis[i][j]=INF;
		}
	}
	dis[1][0]=0;
	for (int i=0;i<n;++i){
		for (int j=1;j<=n;++j){
			for (int ii=head[j];ii;ii=Pth[ii].Next){
				int y=Pth[ii].y;
				dis[y][i+1]=min(dis[y][i+1],dis[j][i]+Pth[ii].v);
			}
		}
	}
}

ll calc(int s1,ll a,ll b){
	ll l1=st[s1].b-b;
	ll l2=a-st[s1].a;
	return (ll)ceil((double)l1/l2);
}

int main(){
	freopen("exercise.in","r",stdin);
	freopen("exercise.out","w",stdout);
	cin>>n>>m>>t;
	for (int i=1;i<=m;++i){
		int x,y,d;
		scanf("%d%d%d",&x,&y,&d);
		add(x,y,d);add(y,x,d);
	}
	dp();
	for (int i=2;i<=n;++i){
		top=0;
		for (int j=n-1;j>=0;--j){
			if (dis[i][j]==INF) continue;
			if (top==0){
				st[++top]={j,dis[i][j]};
				dig[top]=0;
			}else{
				while (top>=1 && calc(top,j,dis[i][j])<=dig[top]) top--;
				st[++top]={j,dis[i][j]};
				if (top>=2) dig[top]=calc(top-1,j,dis[i][j]);
				else dig[top]=0;
			}
		}
		int last=0;
		dig[top+1]=INF;
		for (int i=1;i<=top;++i){
			ll l=dig[i],r=dig[i+1]-1;
			if (l>t) break;
			r=min(r,(ll)t);
			ll tt=(ll)(l+r)*(r-l+1)/2; tt%=mod;
			ans+=tt*st[i].a%mod+(ll)(r-l+1)*st[i].b%mod;
			ans%=mod;
		}
	}
	cout<<ans<<endl;
	return 0;
}

大佬的计算（calc）

【题目描述】

小A还在玩他的游戏，但是小B却在认真地学习，有一天，小A拿着一个问题去问小B：给定一个区间，求每一个区间的最大值之和。
小B马上回答了这个问题，并给了小A这个问题的加强版，但是小A最近的时间都荒废在游戏上面去了，导致他居然不会这个问题，所以他想要让你帮他来回答。
问题是：
给定一个长度为n的序列A，求对于$i<j,Max(A_i \dots A_j)*(A_i\&A_j=A_i|A_i\&A_j=A_j)$。
$Max(Ai,…,Aj)$的意思就是这些数的最大值。
&，|的含义和c++中符号的含义相同。

【输入数据】

一个整数n，表示序列的长度。
下一行n个整数，表示序列。

【输出数据】

一个整数表示答案。

【样例输入】

5 
2 3 7 4 1

【样例输出】

38

【数据范围】

对于20%的数据，$n≤1000$。
对于另20%的数据，保证对于任意i,j均成立。
对于另20%的数据，$Ai<2^7$。
对于另10%的数据，$Ai=i\%2^{14}$。
对于100%的数据，$n≤100000，Ai<2^{14}$。

题解

20% 暴力+ST表
+20% 所有区间都对答案有贡献，即用单调栈求出每个点左右第一个比自己大的数，区间数乘上该点值即可。
+20% 找到总区间的最大值，把序列分成左右两部分，先递归较小的一段，分治求出该段中的答案，然后向另一边递归，求出以最大值为贡献的答案数，累加即可（dsu on the tree）
+10% 打表，求出$x=2^{14}$整数倍时的答案，求值时用前面的答案加上剩下暴力求解即可
100% 把$A_i$分成前7位和后7位，按上一种情况做即可

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

template <class T>void Max(T &x,T y){
    if(x<y)x=y;
}

#define M 100005

int n,A[M];

struct STable{

    int num[M][20],lg2[M];

    void Init(){
        memset(num,0,sizeof(num));
        lg2[0]=-1;
        for(int i=1;i<=n;i++)num[i][0]=i,lg2[i]=lg2[i>>1]+1;
        for(int i=0;i+1<20;i++){
            for(int j=1;j<=n;j++){
                if(j+(1<<i)>n){num[j][i+1]=num[j][i];continue;}
                int p1=num[j][i],p2=num[j+(1<<i)][i];
                if(A[p1]>A[p2])num[j][i+1]=p1;
                else num[j][i+1]=p2;
            }
        }
    }

    int Query(int l,int r){
        int lg=lg2[r-l+1];
        int p1=num[l][lg],p2=num[r-(1<<lg)+1][lg];
        return A[p1]>A[p2]?p1:p2;
    }

}ST;

vector<int>fa[1<<7],sn[1<<7];

void Add_edge(int f,int s){
    sn[f].push_back(s);
    fa[s].push_back(f);
}

void Init(){
//  cout<<"Y"<<endl;
    for(int i=0;i<(1<<7);i++){
        Add_edge(i,0);
        for(int j=i;j;j=(j-1)&i)
            Add_edge(i,j);
    }
}

int C[3][(1<<14)];

void Add(int a,int b,int v){
    for(int i=0,up=fa[a].size();i<up;i++)C[0][(fa[a][i]<<7)|b]+=v;
    for(int i=0,up=sn[a].size();i<up;i++)C[1][(sn[a][i]<<7)|b]+=v;
//  cout<<a<<" "<<b<<" "<<v<<endl;
    C[2][(a<<7)|b]+=v;
}

long long ans;

void Ask_fa(int a,int b,int v){
    for(int i=0,up=fa[b].size();i<up;i++)
        ans+=1ll*v*C[1][(a<<7)|fa[b][i]];
}

void Ask_sn(int a,int b,int v){
    for(int i=0,up=sn[b].size();i<up;i++)
        ans+=1ll*v*C[0][(a<<7)|sn[b][i]];
}

void DFS(int L,int R){
    if(L>=R){
        for(int i=L;i<=R;i++){
            Add(A[i]>>7,A[i]&127,1);
            int mx=A[i];
            for(int j=i+1;j<=R;j++){
                Max(mx,A[j]);
                int x=A[i]&A[j];
                if(x==A[i]||x==A[j])ans+=mx;            
            }
        }
        return;
    }
    int p=ST.Query(L,R),mid=(L+R)>>1;
    if(p<=mid){
        DFS(L,p-1);
        for(int i=L;i<=p-1;i++)Add(A[i]>>7,A[i]&127,-1);
        DFS(p+1,R);
        for(int i=L;i<=p;i++)Ask_sn(A[i]>>7,A[i]&127,A[p]);
        for(int i=L;i<=p-1;i++)ans-=1ll*A[p]*C[2][A[i]];
        Add(A[p]>>7,A[p]&127,1);
        for(int i=L;i<=p-1;i++)Ask_fa(A[i]>>7,A[i]&127,A[p]);
        for(int i=L;i<=p-1;i++)Add(A[i]>>7,A[i]&127,1);
    }else{
        DFS(p+1,R);
        for(int i=p+1;i<=R;i++)Add(A[i]>>7,A[i]&127,-1);
        DFS(L,p-1);
        for(int i=p;i<=R;i++)Ask_sn(A[i]>>7,A[i]&127,A[p]);
        for(int i=p+1;i<=R;i++)ans-=1ll*A[p]*C[2][A[i]];
        Add(A[p]>>7,A[p]&127,1);
        for(int i=p+1;i<=R;i++)Ask_fa(A[i]>>7,A[i]&127,A[p]);
        for(int i=p+1;i<=R;i++)Add(A[i]>>7,A[i]&127,1);
    }
}

int main(){
    freopen("calc.in","r",stdin);
    freopen("calc.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&A[i]);
    ST.Init();
    Init();
    DFS(1,n);
    printf("%lld\n",ans);
    return 0;
}

自走棋（chess）

【题目描述】

小A最近沉迷自走棋，但是他玩的自走棋十分的奇怪，棋子在n*m的方形的棋盘上自己走，其中有k个空位，如果棋子走上去就死了，棋子的目标是从左上角走到右下角，走到的话就获胜了，如果两方棋子碰到一起则会触发战斗。
在一句对局中，小A有一个棋子疑似打假赛，在起点一直不动，而他的其他棋子与对方的棋子进行着激烈的战斗，最后，小A居然只剩下了这一个棋子，所以这枚棋子也开始动了，而对方的棋子也全部阵亡，只需要这个棋子走到右下角，小A就能得到胜利，但是对方的一个棋子对这个棋子释放了亡语：地缚神的诅咒，使得这个棋子只能往右或者往下走，因为这局基本已经稳赢了，所以小A想要知道他的棋子有多少种行走的方案能够使其获得最后的胜利。

【输入数据】

第一行三个整数n,m,k,表示棋盘大小，空位数量。
接下来k行每行两个整数x,y,表示一个空位的坐标。

【输出数据】

输出一个整数表示方案个数，对(1e9+7)取模。

【样例输入1】

3 4 2
2 2
2 3

【样例输出1】

2

【样例输入2】

100 100 3
15 16
16 15
99 88

【样例输出2】

545732279

【数据范围】

对于20%的数据，$1≤n,m,k≤8$。
对于40%的数据，$1≤n,m≤1000$。
对于另20%的数据，$1≤n≤2$。
对于100%的数据，$1≤n,m≤100000,1≤k≤1000$。
起点和终点一定不会是空位。

题解

40% 暴力DP计算即可
+20% 直接想一想或者DP
100% $dp[i]$表示没有经过空格，到达第i个空格的方案数，把$（1，1）$和$（n，n）$也看成空格
计算$dp[i]$时，从$dp[j]$转移来时，$dp[i]=C_{x_i+y_i-2}^{x_i-1}-dp[j]*C_{x_i-x_j+y_i-y_j}^{y_i-y_j}$（即到达i点的总方案数减掉经过一个空格的方案数），先对点按x,y排序

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node{
    int x,y;
}a[1005];
bool cmp(node x,node y){
    if (x.x==y.x) return x.y<y.y;
    return x.x<y.x;
}
ll dp[1005],mod=1e9+7,p[200005];
int n,m,k;

ll power(ll a,int b){
    ll ret=1;
    while (b){
        if (b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
ll inv(ll t){return power(t,mod-2);}
ll C(int n,int m){
    return p[n]*inv(p[m])%mod*inv(p[n-m])%mod;
}

int main(){
    freopen("chess.in","r",stdin);
    freopen("chess.out","w",stdout);
    cin>>n>>m>>k;
    p[0]=1;
    for (int i=1;i<=n+m;++i) p[i]=p[i-1]*i%mod;
    for (int i=1;i<=k;++i){
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    a[k+1]={n,m};
    k+=1;
    sort(a+1,a+k+1,cmp);
    for (int i=1;i<=k;++i){
        for (int j=1;j<i;++j){
            if (a[i].x>=a[j].x && a[i].y>=a[j].y){
                dp[i]+=dp[j]*C(a[i].x-a[j].x+a[i].y-a[j].y,a[i].y-a[j].y);
                dp[i]%=mod;
            }
        }
        dp[i]=(C(a[i].x+a[i].y-2,a[i].x-1)-dp[i])%mod;
        if (dp[i]<0) dp[i]+=mod;
    }
    cout<<dp[k]<<endl;
    return 0;
}

其他

因数和，因数个数

$a=b_1^{p_1}*b_2^{p_2}* \dots *b_n^{p_n}$

因数个数
$(p_1+1)*(p_2+1)* \dots *(p_n+1)$

因数和
$(1+b_1^1+b_1^2+ \dots +b_1^{p_1})* \dots *(1+b_n^1+b_n^2+ \dots +b_n^{p_n})$

$gcd(a,b)=gcd(b,a mod b)$

int gcd(int a,int b){
    if (!b) return a;
    return gcd(b,a%b);
}

扩展欧几里得

$ax+by=c$有整数解的充要条件是$gcd(a,b)|c$

ll exgcd(ll a,ll b,ll &x,ll &y){
    if (!b){x=1;y=0;return a;}
    ll d=exgcd(b,a%b,x,y);
    ll z=x;x=y;y=z-y*(a/b);
    return d;
}

类欧几里得算法

给定n,a,b,c,求$f(n,a,b,c)=\sum _{i=0}^n \lfloor \frac{ai+b}{c} \rfloor$
类欧几里得

费马小定理

$$a^{p-1}=1 \mod p$$

欧拉定理

对于正整数n,令q(n)表示比n小的与n互质的数的个数，有 $$gcd(a,n)=1,a^{\varphi(n)} = 1(mod n)$$ 其中(n)称为欧拉函数。

中国剩余定理

质数

线性基

其他

  • Lacus定理

  • 矩阵乘法

  • 高斯消元

  • 线性基

  • Perm 排列计数

  • BZOJ4403 序列统计

  • BJWC2011 元素

  • BZOJ2844

  • luogu3292 SCOI2016 幸运数字

  • BZOJ2115 WC2011 Xor

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/cxjy-day-3/

Powered by Hexo
Theme - Material