有点想做一些多校的题目练手。发现有一场是杜教出的?来体验一下被虐的快感~~
Expression
给定一个表达式,运算符包括加减乘。每次可以选择两个数执行运算。求所有运算顺序得到的结果之和。答案对
取模。
![]()
比较明显的区间DP。设为第
到
个数所有运算顺序结果的和,则有
其中是与
位置后的运算符有关的转移函数。
上述式子中组合数的意义是,我们将左区间和右区间并起来时,考虑到左右区间各选择一个结果,产生新的结果方式有
种。
考虑加法运算,相当于在左右区间分别选择一个结果相加,即。那么左区间的某一结果
对于答案的贡献是
,同理右区间的某一结果
对于答案的贡献是
,故此时
减法运算类似。
再考虑乘法运算,相当于在左区间和右区间分别选择一个结果相乘,即。我们可以化简化一下式子,
。故此时
时间复杂度。
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 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define lowbit(x) (x)&(-x) #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=105; const int mo=(int)(1e9)+7; int a[maxn]; char s[maxn]; LL fac[maxn]; LL C[maxn][maxn]; LL f[maxn][maxn]; inline void add(LL& x,LL v) {x=(x+v)%mo;} int main() { fac[0]=1; REP(i,1,100) fac[i]=fac[i-1]*i%mo; REP(i,0,100) C[i][0]=1; REP(i,1,100) REP(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo; int n; while(scanf("%d",&n)==1) { REP(i,1,n) scanf("%d",&a[i]); scanf("%s",s+1); REP(p,0,n-1) REP(i,1,n-p) { int j=i+p; if(i==j) f[i][j]=a[i]; else { f[i][j]=0; REP(k,i,j-1) { if(s[k]=='+') add(f[i][j],C[j-i-1][k-i]*((f[i][k]*fac[j-k-1]+f[k+1][j]*fac[k-i])%mo)); if(s[k]=='-') add(f[i][j],C[j-i-1][k-i]*((f[i][k]*fac[j-k-1]+(mo-f[k+1][j])*fac[k-i])%mo)); if(s[k]=='*') add(f[i][j],C[j-i-1][k-i]*(f[i][k]*f[k+1][j]%mo)); } } } printf("%lld\n",f[1][n]); } return 0; } |
Hack it!
定义字符串
的哈希函数
。构造两个等长的合法括号序列
,长度
,满足
。其中
。保证数据随机。
![]()
GCD Tree
有一个带权完全图,点编号为
到
。边
的权值为
。求图的最大生成树。
测试数据约
组。
![]()
本来以为这题有一些结论的,没想到是这么暴力的方法~
考虑按边权从大到小枚举边,设现在枚举到,考虑边
,且
,那么这条边可以用
和
两条边等效替代。于是我们只要考虑
和
的倍数连边的情况。换言之,我们只需考虑
是
的倍数的边
。
根据调和级数,有条这样的边。用LCT动态维护最大生成树即可。维护时记录一下答案,即可
回答询问。
时间复杂度。
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 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ #define LC ch[x][0] #define RC ch[x][1] const int maxn=(int)(2e6); const int INF=(int)(1e9); int ch[maxn][2],fa[maxn]; int siz[maxn],flip[maxn]; int val[maxn],mi[maxn]; bool rt[maxn]; inline void rev(int x) { flip[x]^=1; swap(LC,RC); } inline void pd(int x) { if(flip[x]) { if(LC) rev(LC); if(RC) rev(RC); flip[x]=0; } } inline void pu(int x) { siz[x]=siz[LC]+siz[RC]+1; mi[x]=x; if(val[mi[LC]]<val[mi[x]]) mi[x]=mi[LC]; if(val[mi[RC]]<val[mi[x]]) mi[x]=mi[RC]; } inline int dir(int x) {return ch[fa[x]][1]==x;} inline void rot(int x) { int d=dir(x)^1,p=fa[x]; ch[p][d^1]=ch[x][d]; fa[ch[x][d]]=p; fa[x]=fa[p]; if(rt[p]) rt[p]=0,rt[x]=1; else ch[fa[p]][dir(p)]=x; ch[x][d]=p;fa[p]=x;pu(p); } int stk[maxn],top; inline void splay(int x) { stk[top=1]=x; for(int p=x;!rt[p];stk[++top]=p=fa[p]); for(;top;pd(stk[top--])); while(!rt[x]) { if(rt[fa[x]]) rot(x); else if(dir(fa[x])!=dir(x)) rot(x),rot(x); else rot(fa[x]),rot(x); } pu(x); } inline int access(int x) { int p=0; for(;x;x=fa[p=x]) { splay(x); rt[RC]=1;rt[RC=p]=0; pu(x); } return p; } inline void rto(int x) { access(x);splay(x);rev(x); } inline int findroot(int x) { access(x);splay(x); while(LC) x=LC; return x; } inline void link(int a,int x) { rto(x);fa[x]=a;access(x); } inline void cut(int a,int x) { rto(a);access(x);splay(x); fa[LC]=fa[x];fa[x]=0; rt[LC]=1;LC=0;pu(x); } struct edge { int next,st,ed; }; int fr[maxn]; edge e[maxn]; int tote=0; inline void addedge(int u,int v) { ++tote; e[tote].next=fr[u];fr[u]=tote;e[tote].st=u;e[tote].ed=v; } LL res[maxn]; int main() { int n=(int)(1e5); val[0]=INF; memset(fr,-1,sizeof(fr)); REP(i,1,n) REP(j,2,n) { if(i*j>n) break; addedge(i*j,i); } REP(x,1,n+tote) { fa[x]=LC=RC=flip[x]=0; rt[x]=siz[x]=1;mi[x]=x; if(x>n) val[x]=e[x-n].ed; else val[x]=INF; } LL now=0; REP(u,1,n) { RAL(i,u) { int v=e[i].ed; if(findroot(u)!=findroot(v)) { link(u,n+i);link(v,n+i); now+=val[n+i]; } else { rto(u);access(v);splay(v); if(val[mi[v]]<val[n+i]) { now+=val[n+i]-val[mi[v]]; int k=mi[v]; cut(e[k-n].st,k);cut(e[k-n].ed,k); link(u,n+i);link(v,n+i); } } } res[u]=now; } while(scanf("%d",&n)==1) printf("%lld\n",res[n]); return 0; } |
Too Simple
有
组函数
。定义域和值域均为
的整数。现给定部分函数,求有多少种合法的函数序列,满足对于
,
。答案对
取模。
![]()
考虑这些函数,必定都是一对一的,而不会是多对一的。因为若有函数多对一,那么多个值就会映射到同一个值,最后不可能满足条件。所以这些函数实际上都是置换。
接下来我们分情况讨论。
如果所有函数都已经给定,我们只需将它们代入验证即可。
如果存在函数是未知的,我们只要确定个函数,就能唯一地确定余下的一个函数。所以我们可以自由地决策
个函数,其中
是未知的函数数量。故答案为
。
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 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define lowbit(x) (x)&(-x) #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=105; const int mo=(int)(1e9)+7; int a[maxn][maxn],b[maxn][maxn]; LL fac[maxn]; bool vis[maxn]; int n,m; LL pow_mod(LL b,LL p,LL k) { LL res=1; for(;p;p>>=1) { if(p&1) res=res*b%mo; b=b*b%mo; } return res; } void solve() { int cnt=0; bool flag=1; REP(i,1,m) { memset(vis,0,sizeof(vis)); REP(j,1,n) { read(a[i][j]); if(a[i][j]==-1) { cnt++; break; } if(vis[a[i][j]]) flag=0; vis[a[i][j]]=1; } } if(!flag) { printf("0\n"); return; } if(cnt>=1) printf("%lld\n",pow_mod(fac[n],cnt-1,mo)); else { REP(i,1,n) b[m+1][i]=i; PER(i,m,1) REP(j,1,n) b[i][a[i][j]]=b[i+1][j]; REP(i,1,n) if(b[1][i]!=i) { printf("0\n"); return; } printf("1\n"); } } int main() { fac[0]=1; REP(i,1,100) fac[i]=fac[i-1]*i%mo; while(scanf("%d%d",&n,&m)==2) solve(); return 0; } |
Arithmetic Sequence
定义序列
是
等差的,当且仅当存在
满足,对任意
有
,对任意
有
。
现给定序列
,求有多少区间
时
等差的。
![]()
不妨分成两种情况讨论。
时,我们就是要找序列中有多少个公差为
的等差数列。求出所有极长等差数列统计一下答案。
时,对于每个位置
,处理一下左边和右边分别可以延伸到的位置,乘法原理统计答案。
时间复杂度。
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 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define lowbit(x) (x)&(-x) #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=(int)(1e5)+5; int a[maxn],l[maxn],r[maxn]; int main() { int n,p,q; while(scanf("%d",&n)==1) { LL res=0; scanf("%d%d",&p,&q); REP(i,1,n) scanf("%d",&a[i]); if(p==q) { int cnt=1; REP(i,2,n) { if(a[i-1]+p==a[i]) cnt++; else res+=1ll*cnt*(cnt-1)/2,cnt=1; } res+=1ll*cnt*(cnt-1)/2+n; } else { REP(i,2,n) { if(a[i-1]+p==a[i]) l[i]=l[i-1]+1; else l[i]=0; } PER(i,n-1,1) { if(a[i]+q==a[i+1]) r[i]=r[i+1]+1; else r[i]=0; } REP(i,1,n) res+=1ll*(l[i]+1)*(r[i]+1); } printf("%lld\n",res); } return 0; } |
Persistent Link/cut Tree
有
棵树。
仅有一个点
。
的构造方式如下:选择两棵树
,在
中的
和
中的
连一条长度为
的边。若
有
个点,将
中所有点的编号加上
。
对于任意
,若
有
个点,求
。答案对
取模。
测试数据约
组。
。
Travelling Salesman Problem
有一个
的网格。每个格子里有一个非负整数。现要从
走到
,每次可以从一个格子走到一个相邻的格子,同一个格子不能经过两次。最大化经过格子的权值之和。输出路径。
![]()
和
若有一个是奇数,我们就可以遍历整个棋盘。因为权值非负,直接遍历棋盘即可。
接着和
均为偶数的情况我就不会啦~~
[UPD] 杜教的题太神啦。我们考虑棋盘的黑白染色,不妨设是黑色,故
也是黑色。考虑一条路径,因为路径上的颜色一定时交替的,所以黑色恰好比白色多一格。又因为棋盘上黑白格子数目相等,所以一定有一个白格没有经过。于是我们不经过权值最小的白格就好了。构造比较显然,但是考虑的情况较多,FST好题。
时间复杂度。
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 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define lowbit(x) (x)&(-x) #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=105; int a[maxn][maxn]; int main() { int n,m; while(scanf("%d%d",&n,&m)==2) { int tot=0,mx=0,my=0; a[0][0]=10005; REP(i,1,n) REP(j,1,m) { scanf("%d",&a[i][j]); tot+=a[i][j]; if((i+j)&1 && a[i][j]<a[mx][my]) { mx=i;my=j; } } if(n&1) { printf("%d\n",tot); int f=0; REP(i,1,n) { REP(j,1,m-1) { if(f) putchar('L'); else putchar('R'); } if(i!=n) putchar('D');f^=1; } putchar('\n'); } else if(m&1) { printf("%d\n",tot); int f=0; REP(i,1,m) { REP(j,1,n-1) { if(f) putchar('U'); else putchar('D'); } if(i!=m) putchar('R');f^=1; } putchar('\n'); } else { int f=0,k=0,nx=1,ny=1; printf("%d\n",tot-a[mx][my]); if(mx>=3) for(nx=1;nx<=mx-2;nx++) { REP(j,1,m-1) { if(f) putchar('L'); else putchar('R'); } putchar('D');f^=1; } k=0;if(f) my=m-my+1; REP(i,1,m) { if(i!=my) { if(k) putchar('U'),nx--; else putchar('D'),nx++;k^=1; } if(i<m) { if(f) putchar('L'); else putchar('R'); } } if(nx!=n) putchar('D');nx++;f^=1; for(;nx<=n;nx++) { REP(j,1,m-1) { if(f) putchar('L'); else putchar('R'); } if(nx!=n) putchar('D');f^=1; } putchar('\n'); } } return 0; } |
Goldbach's Conjecture
令
为
所有约数的和。我们称
是一个好数,当且仅当
中的所有整数均可以表示为
的某些约数之和。
询问一个偶数
是否可以表示成两个好数之和。输出方案。
测试数据约
组。
![]()
Sometimes Naive
有
个点的树。点
的权值为
。现要求支持两种操作:
1 u w: 将点
的权值修改为
。
2 u v:求
。若路径
与路径
有交点,
,否则
。答案对
取模。
![]()