Preface
队内赛被吊打了呜呜呜，F死命贪心贪到天昏地暗，直接后面两题一眼没看
其实后面对拍大概知道贪心是有问题的了，但以为可以用分类讨论来避免掉所以没去写DP（他其实什么都知道，只是不想面对罢了）
感觉DP还是一如既往地是我的弱项的说，还得好好练习的说
G和H其实比较常规，补题的时候一下就写过了，不过H的技巧还是很有意思的，狠狠地学习了一手
A 计算行列式
Prob
给定一个三阶矩阵，计算它的行列式
Tutorial
签到
Code
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int a[3][3];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (i=0;i<3;++i) for (j=0;j<3;++j) scanf("%d",&a[i][j]);
int ret=a[0][0]*a[1][1]*a[2][2]; ret+=a[0][1]*a[1][2]*a[2][0]; ret+=a[0][2]*a[1][0]*a[2][1];
ret-=a[0][2]*a[1][1]*a[2][0]; ret-=a[0][1]*a[1][0]*a[2][2]; ret-=a[0][0]*a[1][2]*a[2][1];
return printf("%d",ret),0;
}
B 找到最小的数
Prob
给定一个正整数\(a\)，求一个最小的正整数\(x\)，满足\(x\)至少有四个因数，且其中任意两个因数的差大于等于\(a\)
\(a\le 10^4\)
Tutorial
考虑最小的因数一定是\(1\)，然后我们就要找一个最小的且大于等于\(1+a\)的质数\(p_1\)
不难发现还要找一个最小的且大于等于\(p_1+a\)的质数\(p2\)
然后显然\(p_1\times p_2\)就是答案了，前面因为预处理质数的范围搞小了，WA了好几发（反正没罚时）
Code
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,a,pri[N],cnt; bool vis[N];
inline void init(CI n)
{
for (RI i=2;i<=n;++i)
{
if (!vis[i]) pri[++cnt]=i;
for (RI j=1;j<=cnt&&i*pri[j]<=n;++j)
if (vis[i*pri[j]]=1,i%pri[j]==0) break;
}
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t),init(100000);t;--t)
{
scanf("%d",&a); int p1=pri[lower_bound(pri+1,pri+cnt+1,a+1)-pri];
int p2=pri[lower_bound(pri+1,pri+cnt+1,p1+a)-pri];
printf("%lld\n",1LL*p1*p2);
}
return 0;
}
C A very easy problem of sequence
Prob
给一个长度为\(n\)的序列\(a_i\)，要求构造一个序列\(b_i\)满足：
- \(\forall i\in[1,n],b_i\le a_i\)
- \(\exist k\in [1,n]\)，当\(i\in[1,k)\)时，满足\(b_i\le b_{i+1}\)；当\(i\in[k,n)\)时，\(b_i\ge b_{i+1}\)
最大化\(\sum_{i=1}^n b_i\)
\(n\le 5\times 10^5\)
Tutorial
刚开始看错题了码了个树状数组维护的版本，后面及时悔悟发现直接单调栈就行了
考虑预处理出\(lans_i,rans_i\)分别表示让\([1,i]\)中\(b_j\)单调不降的最大和，\([i,n]\)中\(b_j\)单调不升的最大和，答案显然为\(\max_\limits{1\le i\le n} lans_i+rans_i-a_i\)
对于\(lans_i\)的转移，显然我们就是要找到它左边的第一个小于它的元素\(a_j\)，然后有形如下的转移：
用单调栈维护转移位置即可，\(rans_i\)的情况类似
Code
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
int n,a[N],stk[N],top,L[N],R[N]; long long lans[N],rans[N],ans;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=1;i<=n;++i)
{
while (top&&a[stk[top]]>a[i]) --top;
L[i]=stk[top]; stk[++top]=i;
}
for (stk[top=0]=n+1,i=n;i>=1;--i)
{
while (top&&a[stk[top]]>a[i]) --top;
R[i]=stk[top]; stk[++top]=i;
}
for (i=1;i<=n;++i) lans[i]=lans[L[i]]+1LL*a[i]*(i-L[i]);
for (i=n;i>=1;--i) rans[i]=rans[R[i]]+1LL*a[i]*(R[i]-i);
for (i=1;i<=n;++i) ans=max(ans,lans[i]+rans[i]-a[i]);
return printf("%lld",ans),0;
}
D 蛋时间II
Prob
\(n\)个人坐在一个环形桌子上等着吃饭，一共有\(n\)道菜且每个人面前刚好有一道菜，每个人可以吃到他面前以及与其相邻的人面前的菜
这\(n\)道菜中有\(k\)道撒了某种香料，而每个人对香料有一个接受程度\(a_i\in\{0,1\}\)
- 若\(a_i=0\)，说明他不爱吃香料，那么他的愉悦度定义为所有能吃到的没撒香料的菜肴个数
- 若\(a_i=1\)，说明他爱吃香料，那么他的愉悦度定义为所有能吃到的菜肴个数
求出所有可能的上菜方案中，所有人的总愉悦度最大值
\(n\le 2\times 10^5\)
Tutorial
一眼贪心，考虑处理出每个位置\(i\)上的菜会被几个不吃香料的人吃到，记为\(c_i\)
显然我们找出所有的\(c_i\)然后排个序，从大到小把所有没有香料的菜放在该处即可
Code
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,k,a[N],c[N],ans,num;
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d%d",&n,&k),i=1;i<=n;++i)
scanf("%d",&a[i]),num+=a[i];
for (a[0]=a[n],a[n+1]=a[1],i=1;i<=n;++i)
for (j=-1;j<=1;++j) c[i]+=a[i+j]==0;
for (sort(c+1,c+n+1),i=1;i<=n-k;++i) ans+=c[n-i+1];
return printf("%d",ans+num*3),0;
}
E Redcrown's math problem II
Prob
给定\(5\)个长度为\(n\)的数组\(A,B,C,D,E\)，求：
对\(998244353\)取模的值，其中\(\operatorname{med}(a,b,c,d,e)\)表示\(\{a,b,c,d,e\}\)的中位数
\(n\le 10^5\)
Tutorial
显然是分别考虑每个数的贡献，假设当前枚举的是\(A\)中的某个\(a_i\)
那么我们分别枚举\(B,C,D,E\)中哪两个是大于\(a_i\)的，哪两个是小于\(a_i\)的，然后查询就直接二分一下即可
但是直接做会有重复的数很难处理，那么我们直接把所有相同的数看作不同即可
具体的，可以用一个二元组\((x,i)\)来记录值和对应在哪个数组中，也可以像我一样直接把每个数变成\(5\times x+i\)，其实道理是一样的
总复杂度\(O(n\log n)\)，还有个枚举状态的复杂度，实际跑起来还是挺紧的
Code
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=998244353;
int n,a[5][N],id[5],ans;
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j,k,s; for (scanf("%lld",&n),i=0;i<5;++i)
for (j=1;j<=n;++j) scanf("%lld",&a[i][j]),a[i][j]=5LL*a[i][j]+i;
for (i=0;i<5;++i) sort(a[i]+1,a[i]+n+1);
for (i=0;i<5;++i) for (s=0;s<(1<<4);++s)
{
int cur=0; for (j=0;j<4;++j) if ((s>>j)&1) ++cur;
if (cur!=2) continue; cur=0;
for (j=0;j<5;++j) if (i!=j) id[j]=(s>>cur)&1,++cur;
for (j=1;j<=n;++j)
{
int ret=1; for (k=0;k<5;++k) if (i!=k)
{
int coef=lower_bound(a[k]+1,a[k]+n+1,a[i][j])-a[k]-1;
if (id[k]) coef=n-coef; ret=1LL*ret*coef%mod;
}
inc(ans,1LL*ret*((a[i][j]-i)/5LL)%mod);
}
}
return printf("%lld",ans),0;
}
F Orange Loves Addition
Prob
对于一个加法式子\(x+y=z:(c)\)，\(c\)表示其中进位的次数
给出\(x\)和\(c\)的值，求一个最小的正整数\(y\)使得上式成立
多组数据，数据组数\(n\le 10^5\)，\(1\le x\le 10^9,0\le c\le 9\)
Tutorial
DP战俘闪总出列！
考虑用状态\(f_{i,j,0/1}\)表示从低位到高位处理了前\(i\)位，其中前\(i-1\)位已经进位了\(j\)次，第\(i\)位是否进位的最小的\(y\)
转移的时候就讨论下这一位是否要进位即可，其中\(d_i\)表示给\(x\)分解后的第\(i\)位：
不过要注意一些转移的细节，比如这一位上原来等于\(9\)了，就没法从前一位进位的状态转移到这一位不进位的状态
同理如果这一位上原来等于\(0\)，就没法从前一位不进位的状态转移到这一位进位的状态
然后最后枚举的时候多枚举点长度避免最后的讨论，答案就是\(\min(f_{18,c,0},f_{18,c-1,1})\)
不过要注意特判\(c=0\)的情况，总复杂度\(O(n\times 18^2)\)
Code
#include<cstdio>
#include<iostream>
#define int unsigned long long
#define RI register int
#define CI const int&
using namespace std;
const int INF=1e18;
int t,x,c,d[19],pw[19],f[19][10][2];
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (pw[0]=i=1;i<20;++i) pw[i]=pw[i-1]*10LL;
for (scanf("%llu",&t);t;--t)
{
RI i; scanf("%llu%llu",&x,&c);
for (i=0;i<19;++i) d[i]=x/pw[i]%10;
if (!c)
{
for (i=0;d[i]==9;++i); putchar('1');
while (i--) putchar('0'); putchar('\n'); continue;
}
for (i=0;i<19;++i) for (j=0;j<10;++j) f[i][j][0]=f[i][j][1]=INF;
f[0][0][0]=0; f[0][0][1]=d[0]?10-d[0]:INF;
for (i=1;i<19;++i) for (j=0;j<=c;++j)
f[i][j][0]=min(f[i-1][j][0],j?(d[i]!=9?f[i-1][j-1][1]:INF):INF),
f[i][j][1]=min(d[i]?f[i-1][j][0]+(10-d[i])*pw[i]:INF,j?f[i-1][j-1][1]+(9-d[i])*pw[i]:INF);
printf("%llu\n",min(f[18][c][0],f[18][c-1][1]));
}
return 0;
}
G A very very easy problem of bracket sequences
Prob
有一个长度为\(n\)的括号序列，其中每个位置具体的填法未知
给出了\(q\)组限制，每组限制给出了某个区间\([l_i,r_i]\)中左括号个数和右括号个数的差值\(c_i\)
判断是否存在某个合法的括号序列满足所有限制
\(n\le 3000\and 2|n,q\le\min(C_{n+1}^2,5\times 10^5)\)
Tutorial
括号序列先转化成\(1,-1\)序列，然后这个区间操作一眼前缀和操作
因此我们只要判断是否存在一组合法的前缀和\(s_i\)的值即可
此时不难发现一组限制\(l,r,c\)等价为\(s_r-s_{l-1}=c\)
当然由于括号序列本身的性质，我们还要填上两个条件：
- \(s_0=s_n=0\)，并且对于\(i\in(0,n)\)，满足\(s_i\ge 0\)
- 对于\(i\in [1,n]\)，满足\(|s_{i-1}-s_i|=1\)
不等式组的合法性问题显然就是个差分约束的模型，那个相等的限制我们很容易想到转化成两个不等号来松弛，但绝对值要怎么处理
其实直接放松成\(-1\le s_{i-1}-s_i\le 1\)即可，虽然这样最后可能会跑出\(s_{i-1}=s_i\)的情况
不过其实考虑这种情况的实际意义就是这一位上可以任意选择，根据性质我们知道这样的位置一定是成偶数对出现的，因此最后匹配的时候我们从存在一种填法使得它们满足限制
所以直接跑模型即可，当所有数都大于等于\(0\)时要建大于等于的边跑最长路，如果存在正环就无解
还要注意下SPFA判环的时候如果用每个点入队次数大于\(n\)作为跳出条件的话是会被卡成\(O(nm)\)的
正确的做法应该是记录下从起点到某个点的最短路一共经过了几条边，当这个边数超过\(n\)时跳出，这样的复杂度就是对的了
Code
#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#define RI register int
#define CI const int&
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=3005,INF=1e9;
int n,q,l,r,c,s,dis[N],in[N]; bool vis[N];
vector <pi> v[N]; queue <int> Q;
inline bool SPFA(CI st)
{
for (RI i=0;i<=st;++i) dis[i]=-INF;
dis[st]=0; vis[st]=1; Q.push(st);
while (!Q.empty())
{
int now=Q.front(); Q.pop(); vis[now]=0;
for (auto [to,w]:v[now]) if (dis[to]<dis[now]+w)
{
dis[to]=dis[now]+w; in[to]=in[now]+1;
if (in[to]>s) return 0;
if (!vis[to]) Q.push(to),vis[to]=1;
}
}
return 1;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d",&n,&q),s=n+1,i=0;i<=n;++i) v[s].pb(pi(i,0));
for (v[0].pb(pi(s,0)),v[n].pb(pi(s,0)),i=1;i<=q;++i)
scanf("%d%d%d",&l,&r,&c),v[l-1].pb(pi(r,c)),v[r].pb(pi(l-1,-c));
for (i=1;i<=n;++i) v[i-1].pb(pi(i,-1)),v[i].pb(pi(i-1,-1));
return puts(SPFA(s)?"YES":"NO"),0;
}
H Count Reachable Pairs!
Prob
给定一个\(n\)个点\(m\)条边的无向图，其中每条边有边权\(w_j\)
同时给出一个数\(k\)以及\(q\)次询问，每次询问给出\(p_i\)，要求统计出满足一下两个条件的二元组\((u,v)\)的个数：
- \(1\le u<v\le n\)
- 在只经过\(w_j\oplus p_i<k\)的边时，\(u\)和\(v\)连通
\(n,m,q\le 10^5,p_i,w_j,k<2^{30}\)
Tutorial
可用的边满足某个性质的连通性问题，一眼线段树分治维护带撤销并查集，但是要怎么把一条边划分成若干个区间呢
涉及进制的问题很容易想到0/1Trie，考虑把所有的询问的\(p_i\)插入0/1Trie中，然后对于考虑一条边\(w_j\)，满足\(w_j\oplus p_i<k\)的点有什么性质
我们要注意到0/1Trie上一段区间是形如\(0110****\)的形式的，即前面某些位已经确定，后面的位都可以任取
考虑把小于号换成等号，比如当\(k=10011000\)时，可以划分成\(w_j\oplus p_i=0*******,w_j\oplus p_i=1000****,w_j\oplus p_i=10010***\)这三个区间中
此时直接把\(w_j\)移到右边即可得到\(p_i\)对应的区间了，显然是\(O(\log k)\)级别的
然后在0/1Trie上跑线段树分治即可，和在一般的线段树上并无区别，不过要注意重复的点的处理（这个样例有给可以说是非常良心了）
总复杂度\(O(n\log k)\)
Code
#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=100005,P=30;
struct Data
{
int x,y,szy;
inline Data(CI X=0,CI Y=0,CI SZY=0)
{
x=X; y=Y; szy=SZY;
}
}stk[N*P]; int n,m,k,x[N],y[N],z[N],q,p,top,fa[N],sz[N]; long long ret,ans[N];
inline int getfa(CI x)
{
return fa[x]!=x?getfa(fa[x]):x;
}
inline long long C2(CI x)
{
return 1LL*x*(x-1)/2LL;
}
inline void merge(int x,int y)
{
x=getfa(x); y=getfa(y); if (x==y) return;
if (sz[x]>sz[y]) swap(x,y); stk[++top]=Data(x,y,sz[y]);
fa[x]=y; ret-=C2(sz[x]); ret-=C2(sz[y]); sz[y]+=sz[x]; ret+=C2(sz[y]);
}
inline void revoke(CI tmp)
{
while (top>tmp)
{
int x=stk[top].x,y=stk[top].y,szy=stk[top].szy;
--top; fa[x]=x; ret-=C2(sz[y]); sz[y]=szy; ret+=C2(sz[x]); ret+=C2(sz[y]);
}
}
class Trie
{
private:
int ch[N*P][2],tot; vector <int> id[N*P]; vector <pi> v[N*P];
public:
inline Trie() { tot=1; }
inline void insert(CI x,CI num,CI now=1,CI y=P-1)
{
if (!~y) return id[now].push_back(num); int d=(x>>y)&1;
if (!ch[now][d]) ch[now][d]=++tot; insert(x,num,ch[now][d],y-1);
}
inline void apply(CI now,const pi& it)
{
v[now].push_back(it);
}
inline void solve(CI k,CI w,const pi& it,CI now=1,CI y=P-1)
{
if (!~y||!now) return; int d=(k>>y)&1;
if (d) apply(ch[now][(w>>y)&1],it);
solve(k,w,it,ch[now][d^((w>>y)&1)],y-1);
}
inline void travel(CI now=1,CI y=P-1)
{
if (!now) return; int tmp=top; for (auto [x,y]:v[now]) merge(x,y);
if (!~y)
{
for (int it:id[now]) ans[it]=ret; return revoke(tmp);
}
travel(ch[now][0],y-1); travel(ch[now][1],y-1); revoke(tmp);
}
}T;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d%d",&n,&m,&k),i=1;i<=m;++i)
scanf("%d%d%d",&x[i],&y[i],&z[i]);
for (scanf("%d",&q),i=1;i<=q;++i) scanf("%d",&p),T.insert(p,i);
for (i=1;i<=m;++i) T.solve(k,z[i],pi(x[i],y[i]));
for (i=1;i<=n;++i) fa[i]=i,sz[i]=1;
for (T.travel(),i=1;i<=q;++i) printf("%lld\n",ans[i]);
return 0;
}
Postscript
这场纯被吊打，希望下场发挥好点吧呜呜呜