老妈送来了防寒补给就很棒，再也不用晚上盖两层毛巾被了，再也不用担心晚上自动把毛巾被$split$了
还有一些好吃的耶叶
T1 小L的疑惑
考场上疑惑的切掉了
直接把$a$排序然后处理前缀和的过程中判断和下一个的数的差就行
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=1e5+5;
15 int n,a[NN];
16 namespace WSN{
17 inline short main(){
18 freopen("math.in","r",stdin);
19 freopen("math.out","w",stdout);
20 n=read();
21 for(int i=1;i<=n;i++) a[i]=read();
22 sort(a+1,a+n+1);int sum=0;
23 for(int i=1;i<=n;i++){
24 if(a[i]-sum>1){
25 printf("%lld\n",sum+1);
26 return 0;
27 }
28 sum+=a[i];
29 }
30 printf("%lld\n",sum+1);
31 return 0;
32 }
33 }
34 signed main(){return WSN::main();}
View Code
T2 小L的数列
一眼矩阵快速幂，然后就开始刚他
发现计算的时候是连乘，非常不爽那么考虑对指数快速幂
找到每一个$f_1...f_k$的对应指数然后就可以计算了
转移矩阵是一个类似这样的，拿$k=4$举例
$\begin{vmatrix}b_1 &b_2 &b_3 &b_4 \\ 1 &0 &0 &0 \\ 0 &1 &0 &0 \\ 0 &0 &1 &0 \end{vmatrix}$
然后你就会陷入无尽的痛苦中，为啥它小点对，大点不对啊
你开始怀疑自己，甚至否认了转移矩阵，然后突然发现了一件事情：对指数矩阵快速幂
$\huge{?}$
$\huge{!}$
$a^b\equiv a^{ b\mod \phi (p)}(\mod p)$
然后就被卡常了。。。。。。
然后就$\textit{%:pragma GCC optimize(2)}$了。。。。。。
1 %: pragma GCC optimize(2)
2 #include<bits/stdc++.h>
3 #define int long long
4 using namespace std;
5 namespace AE86{
6 inline int read(){
7 int x=0,f=1;char ch=getchar();
8 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
9 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
10 }inline void write(int x,char opt='\n'){
11 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
12 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
13 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
14 }using namespace AE86;
15 const int KK=205,mod=998244353;
16 int n,k,b[KK],f[KK];
17 inline int qmo(int a,int b,int ans=1){
18 int c=mod; a%=c;
19 while(b){
20 if(b&1) ans=ans*a%c;
21 b>>=1; a=a*a%c;
22 }
23 return ans;
24 }
25 namespace Matrix{
26 struct Ma{
27 int m[KK][KK];
28 Ma(){memset(m,0,sizeof(m));}
29 inline void pre(){for(int i=1;i<=k;i++)m[i][i]=1;}
30 };
31 inline Ma muls(Ma a,Ma b){
32 Ma c;
33 for(int i=1;i<=k;i++)
34 for(int j=1;j<=k;j++)
35 for(int u=1;u<=k;u++)
36 c.m[i][j]=(c.m[i][j]+a.m[i][u]*b.m[u][j]%(mod-1))%(mod-1);
37 return c;
38 }
39 }using namespace Matrix;
40 int dp[KK],c[KK];
41 inline void mul(int a[KK],Ma b){
42 memset(c,0,sizeof(c));
43 for(int i=1;i<=k;i++)
44 for(int j=1;j<=k;j++)
45 c[i]=(c[i]+a[j]*b.m[j][i]%(mod-1))%(mod-1);
46 memcpy(a,c,sizeof(c));
47 }
48 namespace WSN{
49 inline short main(){
50 freopen("seq.in","r",stdin);
51 freopen("seq.out","w",stdout);
52 n=read(); k=read();
53 for(int i=1;i<=k;i++) dp[i]=b[i]=read();
54 for(int i=1;i<=k;i++) f[i]=read();
55 Ma g;
56 for(int i=1;i<=k;i++){
57 g.m[1][i]=b[i];
58 if(i+1<=k) g.m[i+1][i]=1;
59 }
60 int b=n-k-1;
61 if(n<=k){ write(f[n]);return 0;}
62 while(b){
63 if(b&1) mul(dp,g);
64 b>>=1; g=muls(g,g);
65 }
66 int tmp=1;
67 for(int i=1;i<=k;i++){
68 tmp=tmp*qmo(f[k-i+1],dp[i])%mod;
69 } write(tmp);
70 return 0;
71 }
72 }
73 signed main(){return WSN::main();}
View Code
T3 连边
多源$dijkstra$处理出每个黑点为原点的到每个白点的最短路，然后考虑把重复的部分删掉就行了
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=1e5+5,MM=2e5+5,inf=1e18;
15 int n,m,seg[NN];
16 struct SNOW{int to,val,next;}e[MM<<1];int head[NN],rp;
17 inline void add(int x,int y,int z){
18 e[++rp]=(SNOW){y,z,head[x]};head[x]=rp;
19 e[++rp]=(SNOW){x,z,head[y]};head[y]=rp;
20 }
21 struct node{
22 int id,data;
23 friend bool operator<(node a,node b){
24 return a.data>b.data;
25 }
26 };priority_queue<node> Q;
27 int dis[NN];bool vis[NN];
28 inline void dij(){
29 for(int i=1;i<=n;i++) dis[i]=inf,vis[i]=0;
30 for(int i=1;i<=n;i++) if(seg[i])
31 Q.push(node{i,0}),dis[i]=0;
32 while(!Q.empty()){
33 int x=Q.top().id,y=Q.top().data;Q.pop();
34 if(!vis[x]){ vis[x]=1;
35 for(int i=head[x];i;i=e[i].next)
36 if(dis[e[i].to]>dis[x]+e[i].val)
37 Q.push(node{e[i].to,dis[e[i].to]=dis[x]+e[i].val});
38 }
39 }
40 }
41 int ans,sheng[NN];
42 namespace WSN{
43 inline short main(){
44 freopen("minimum.in","r",stdin);
45 freopen("minimum.out","w",stdout);
46 n=read(); m=read();
47 for(int i=1;i<=n;i++) seg[i]=read();
48 for(int i=1,x,y,z;i<=m;i++)
49 x=read(),y=read(),z=read(),add(x,y,z);
50 dij();
51 for(int i=1;i<=n;i++) if((!seg[i])&&dis[i]>=inf) return puts("impossible"),0;
52 for(int i=1;i<=n;i++){
53 if(seg[i]) continue;
54 for(int j=head[i];j;j=e[j].next){
55 int y=e[j].to,val=e[j].val; if(seg[y]) continue;
56 if(dis[y]==dis[i]+val) sheng[y]=max(sheng[y],dis[i]);
57 }
58 }
59 for(int i=1;i<=n;i++) ans+=dis[i]-sheng[i];
60 write(ans);
61 return 0;
62 }
63 }
64 signed main(){return WSN::main();}
View Code
T4 小L的有向图
对于一种拓扑序$p$，可以求出原图有几条边可以被这个拓扑序满足，假设有$k$条，对答案的贡献就是$2^k$
用状压$dp$计算，每次新加入一个点有几条和这个点有关的边被满足了
时间复杂度$O(2^n n)$
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=23,mod=998244353;
15 int n,m,U,dp[1<<NN],pw[500],g[1<<NN];
16 namespace WSN{
17 inline short main(){
18 freopen("topology.in","r",stdin);
19 freopen("topology.out","w",stdout);
20 n=read();m=read(); U=(1<<n)-1; pw[0]=dp[0]=1;
21 for(int i=1,x,y;i<=m;i++)
22 x=read(),y=read(),g[y]|=(1<<x-1),pw[i]=(pw[i-1]<<1)%mod;
23 for(int s=0;s<=U;s++){
24 for(int i=1;i<=n;i++) if(!(s&(1<<i-1))){
25 int k=__builtin_popcount(s&g[i]);
26 (dp[s|(1<<i-1)]+=dp[s]*pw[k]%mod)%=mod;
27 }
28 }
29 write(dp[U]);
30 return 0;
31 }
32 }
33 signed main(){return WSN::main();}
View Code
由于最后的两道题过于不符合$T3,T4$水平，于是乎。。。。