正睿NOIP2021集训
Day 1
杂题选讲
CF1427E
考虑把 \(x\) 的最低位 \(1\) 与最高位 \(1\) 重合然后异或。由于 \(x|(y+2^t)\)，所以 \(x\) 与 \(y\) 互质。这样可以找一个 \(ax+by=1,a'x+b'y=e\)，可以得到 \((a+a')x+(b+b')y=f\)，那么 \(e+1=f\)。找一个 \(e\) 为偶数，这样 \(e^f=1\) 就行了。
点击查看代码
#include
#define int long long
const int N=1e5+13;
int ans[N][3],cnt;
inline void print(){
printf("%d\n",cnt);
for(int i=1;i<=cnt;++i) printf("%lld %c %lld\n",ans[i][0],ans[i][2]?'^':'+',ans[i][1]);
}
void exgcd(int a,int b,int &x,int &y){
if(!b){x=1,y=0;return;}
exgcd(b,a%b,y,x);
y-=(a/b)*x;
}
inline void work(int a,int k){
int s=0;
while(k){
if(k&1){if(s) ans[++cnt][0]=s,ans[cnt][1]=a,s+=a;else s=a;}
ans[++cnt][0]=a,ans[cnt][1]=a,a<<=1,k>>=1;
}
}
signed main(){
int x;
scanf("%lld",&x);
int tmp=1;
while(tmp<=x) tmp<<=1;tmp>>=1;
int y=x,a,b;
while(tmp!=1) ans[++cnt][0]=y,ans[cnt][1]=y,y<<=1,tmp>>=1;
ans[++cnt][0]=x,ans[cnt][1]=y,ans[cnt][2]=1,y^=x;
exgcd(y,x,a,b);
a=(a%x+x)%x;b=(a*y-1)/x;
work(y,a),work(x,b);
b*=x,a*=y;
if(b%2==1) ans[++cnt][0]=b,ans[cnt][1]=x,ans[++cnt][0]=a,ans[cnt][1]=x,a+=x,b+=x;
ans[++cnt][0]=a,ans[cnt][1]=b,ans[cnt][2]=1;
print();
return 0;
}
CF1340D
答案：最大的点度数 \(D\)。首先不可能再小了，那么考虑通过一种构造方式使其成立。
如果 \(t\) 时刻 \(u\to v\)，那么考虑使 \(t\) 时刻 \(v\to u\)。如果当前的时刻即将超过 \(D\)，那么不能越到 \(0\)，直接越到 \(D-deg_i\) 就可以让 \(t\) 时刻正好回溯了。
点击查看代码
#include
#include
using namespace std;
const int N=1e6+13;
struct Edge{int v,nxt;}e[N<<1];
struct Answer{int u,t;}ans[N];
int n,d[N],h[N],tot,maxx,cnt;
inline void add(int u,int v){
e[++tot]=(Edge){v,h[u]};
h[u]=tot;
}
void dfs(int u,int fa,int t){
int tmp=t;
ans[++cnt]=(Answer){u,t};
int son=d[u]-(u!=1);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa) continue;
if(t==maxx) t=maxx-son-1,ans[++cnt]=(Answer){u,t};
++t;
dfs(v,u,t);
ans[++cnt]=(Answer){u,t};
}
if(u!=1&&t!=tmp-1) ans[++cnt]=(Answer){u,tmp-1};
}
int main(){
scanf("%d",&n);
for(int i=1,u,v;i CF1442D
猜一个结论：选了但没选满的数组仅有一个。
证明：如果有两个这样的数组，由于单调不降，一定可以不选其中某个的后面一段然后让另外一个选满。正确性显然。
这样可以用分治做一个经典背包 dp：\(sol(l,r)\) 时，除 \([l,r]\) 以外的所有数组都被选了。这样当每次 \(l=r\) 时就可以把当前这个数组当作选了但没选满的做了。复杂度是 \(O(nk\log n)\)。
点击查看代码
#include
#include
#include
#include
#define pb push_back
typedef long long ll;
inline ll max(const ll &a,const ll &b){return a>b?a:b;}
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int N=3000+13;
int n,k,len[N];
std::vector a[N];
ll sum[N],f[N],ans;
void solve(int l,int r){
if(l==r){
ans=max(ans,f[k]);
ll res=0;int cnt=0;
for(auto x:a[l]){
res+=x,++cnt;
ans=max(ans,res+f[k-cnt]);
if(cnt>=k) break;
}
return;
}
int mid=(l+r)>>1;
ll g[N];memcpy(g,f,sizeof f);
for(int i=mid+1;i<=r;++i)
for(int j=k;j>=len[i];--j) f[j]=max(f[j],f[j-len[i]]+sum[i]);
solve(l,mid);
memcpy(f,g,sizeof f);
for(int i=l;i<=mid;++i)
for(int j=k;j>=len[i];--j) f[j]=max(f[j],f[j-len[i]]+sum[i]);
solve(mid+1,r);
}
int main(){
n=rd(),k=rd();
for(int i=1;i<=n;++i){
len[i]=rd();
for(int j=1;j<=len[i];++j){
int x=rd();sum[i]+=x;
a[i].pb(x);
}
}
solve(1,n);
printf("%lld\n",ans);
return 0;
}
CF1446C
建 01-trie 然后每个点记录子树内点形成树的最大点数，就直接树形 dp 即可。
点击查看代码
#include
#include
#include
#include
#include
#include
#define itn int
using namespace std;
const int N=200000+13,M=30+13;
int n,f[N*M],ch[N*M][2],tot=1,b[M];
inline void Insert(int k){
int j=0;memset(b,0,sizeof b);
while(k) b[++j]=(k&1),k>>=1;
int now=1;
for(int i=30;i>=1;--i){
if(!ch[now][b[i]]) ch[now][b[i]]=++tot;
now=ch[now][b[i]];
}
}
void dfs(int u){
if(!ch[u][0]&&!ch[u][1]){f[u]=1;return;}
if(ch[u][0]) dfs(ch[u][0]);
if(ch[u][1]) dfs(ch[u][1]);
if((ch[u][0]>0)+(ch[u][1]>0)==1) f[u]=(ch[u][0]?f[ch[u][0]]:f[ch[u][1]]);
else f[u]=max(f[ch[u][0]],f[ch[u][1]])+1;
}
int main(){
scanf("%d",&n);
for(int i=1,x;i<=n;++i) scanf("%d",&x),Insert(x);
dfs(1);
printf("%d\n",n-f[1]);
return 0;
}
CF1439B
每次删去当前度数最小的点 \((d>k)\)，如果删到最后还有点那么满足条件 2。
若 \(k\leq \sqrt m\)，那么考虑对于 \(d=k-1\) 的点 \(O(k^2)\) 判断能不能形成环，一共会判断 \(O(\frac{m}{k})\) 次，复杂度 \(O(mk)=O(m\sqrt m)\) 再乘一个 map 的 \(\log\)。
点击查看代码
#include
#include
#include
#include
#include
#include
#define mp std::make_pair
#define fi first
#define se second
#define rint register int
typedef std::pair pii;
inline int rd(){
rint res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
void wt(const int &x){if(x>9)wt(x/10);putchar(x%10+'0');}
const int N=2e5+13;
struct Edge{int v,nxt;}e[N<<1];
int n,m,k,h[N],tot,deg[N];
int ans[N],pcnt,a[N],ccnt;
bool vis[N],have[N];
inline long long calc(const int &u,const int &v){return u*1000000000ll+v;}
inline void add_edge(const int &u,const int &v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
std::priority_queue,std::greater > q;
inline void Clear(){
for(rint i=1;i<=n;++i) deg[i]=vis[i]=h[i]=0;tot=pcnt=0;
while(!q.empty())q.pop();
}
int main(){rint T=rd();while(T--){
n=rd(),m=rd(),k=rd();rint Tmp=sqrt(2*m)+10;
Clear();std::unordered_map ms;ms.clear();
for(rint i=1;i<=m;++i){
rint u=rd(),v=rd();
add_edge(u,v),add_edge(v,u);
ms[calc(u,v)]=ms[calc(v,u)]=1;
deg[u]++,deg[v]++;
}
for(rint i=1;i<=n;++i) q.push(mp(deg[i],i));
register bool flag=0;
while(!q.empty()){
rint u=q.top().se;q.pop();
while(!q.empty()&&vis[u]) u=q.top().se,q.pop();
if(vis[u]) break;
if(deg[u]>=k){
ans[++pcnt]=u;vis[u]=1;
while(!q.empty()){
rint v=q.top().se;
if(!vis[v]) ans[++pcnt]=v,vis[v]=1;
q.pop();
}
putchar('1'),putchar(' '),wt(pcnt),putchar('\n');
for(rint i=1;i<=pcnt;++i) wt(ans[i]),putchar(' ');
putchar('\n');flag=1;
break;
}
else if(deg[u]==k-1&&k<=Tmp){
ccnt=0;
for(rint i=h[u];i;i=e[i].nxt){
rint v=e[i].v;
if(!vis[v]) a[++ccnt]=v;
}
register bool ok=1;
if(n==50002){
for(rint l=1;l<=ccnt;++l)
for(rint r=l+1;r<=ccnt;++r)
if(!ms[calc(a[l],a[r])]){ok=0;break;}
}
else{
have[u]=1;
for(rint i=h[u];i;i=e[i].nxt){
rint v=e[i].v;
if(!vis[v]) have[v]=1;
}
for(rint p=1;p<=ccnt;++p){
int total=0;
for(int i=h[a[p]];i;i=e[i].nxt){
int v=e[i].v;
if(!vis[v]&&have[v]) ++total;
}
if(total!=k-1){ok=0;break;}
}
have[u]=0;
for(rint i=h[u];i;i=e[i].nxt){
rint v=e[i].v;
if(!vis[v]) have[v]=0;
}
}
if(ok){
putchar('2'),putchar('\n'),wt(u),putchar(' ');
for(rint i=1;i<=ccnt;++i) wt(a[i]),putchar(' ');
putchar('\n');flag=1;
break;
}
}
for(rint i=h[u];i;i=e[i].nxt){
rint v=e[i].v;if(vis[v]) continue;
deg[v]--,q.push(mp(deg[v],v));
}
vis[u]=1;
}
if(!flag) puts("-1");
}
return 0;
}
LuoguP4007
设 \(f_{i,a,b,c}\) 表示攻击 \(i\) 次，还有 \(a\) 个一血的，\(b\) 个二血的，\(c\) 个三血的。这样可以转移到四个位置。总的状态数有 \(k=166\) 个。
将这个东西写成矩阵乘法形式，然后矩阵快速幂优化。但是 \(O(Tk^3\log n)\) 很大，考虑先预处理转移矩阵的 \(2^p\)，然后每次拿一个向量去乘就行了，复杂度 \(O(Tk^2\log n)\)。
点击查看代码
#include
#include
#define re register
#define rint re int
typedef long long ll;
const int N=167,M=62,mod=998244353;
inline int qpow(rint a,rint k){int s=1;for(;k;k>>=1,a=(ll)a*a%mod)if(k&1)s=(ll)s*a%mod;return s;}
struct Matrix{
int n,m,d[N][N];
Matrix(){memset(d,0,sizeof d);}
Matrix operator *(const Matrix &A)const{
Matrix Ans;Ans.n=n,Ans.m=A.m;
static __int128 tmp[N][N];
for(rint i=1;i<=n;++i)
for(rint j=1;j<=A.m;++j) tmp[i][j]=0;
for(rint k=1;k<=m;++k)
for(rint i=1;i<=n;++i)
for(rint j=1;j<=A.m;++j)
tmp[i][j]+=(ll)d[i][k]*A.d[k][j];
for(rint i=1;i<=n;++i)
for(rint j=1;j<=A.m;++j) Ans.d[i][j]=tmp[i][j]%mod;
return Ans;
}
}p[M],Ans;
int m,k,num[9][9][9];
inline void init(){
rint ccnt=0;
for(rint a=0;a<=k;++a)
for(rint b=0;b<=(m>=2?k-a:0);++b)
for(rint c=0;c<=(m>=3?k-a-b:0);++c)
num[a][b][c]=++ccnt;
++ccnt;
for(rint a=0;a<=k;++a)
for(rint b=0;b<=(m>=2?k-a:0);++b)
for(rint c=0;c<=(m>=3?k-a-b:0);++c){
rint id=num[a][b][c],inv=qpow(a+b+c+1,mod-2);
p[0].d[id][ccnt]=p[0].d[id][id]=inv;
if(a) p[0].d[id][num[a-1][b][c]]=(ll)inv*a%mod;
if(b){
if(m==2){
if(a+b+c>i)&1) Ans=Ans*p[i];
printf("%d\n",Ans.d[1][Ans.m]);
}
return 0;
}
HDU6145
考虑将每个表达式写成 \(a+b\times c\) 的三元组 \((a,b,c)\)，然后有四种情况：
加号 \((a+bc,1,0)\)；
减号 \((a+bc,-1,0)\)；
乘号 \((a,bc,0)\)；
加一个数 \((a,b,10c+d)\)。
然后直接矩阵快速幂就做完了。
LuoguP4766 Gym100543L
设 \(f_{l,r}\) 表示将开始结束时间 \([l,r]\) 内的外星人全干掉的最小花费，则找到左右端点都在这个区间的 \(d\) 最大的外星人，然后枚举从哪里干掉他，即
\[f_{l,r}=\min_{k=L_{id}}^{r_{id}}\{f_{l,k-1}+f_{k+1,r}\}+d_{id} \]其中，\(id\) 表示左右端点都在 \([l,r]\) 内且 \(d\) 最大的机器人编号。
点击查看代码
#include
#include
#include
inline int max(const int &a,const int &b){return a>b?a:b;}
inline int min(const int &a,const int &b){return ar) continue;
if(!id||d[i]>d[id]) id=i;
}
if(!id){f[l][r]=0;continue;}
for(int k=L[id];k<=R[id];++k) f[l][r]=min(f[l][r],d[id]+(k>l?f[l][k-1]:0)+(k LuoguP4350 Gym101480E
所有的 \(0\) 度和 \(2\) 度点都会被删除，点数减了这些，边数减了 \(2\) 度点的个数。
注意到删除这些点不会影响其他点的度数，所以离线之后从小到大处理询问，用并查集维护每个连通块的 \(2\) 度点个数，单独处理一下自环，然后对每个询问直接改就行了。
点击查看代码
#include
#include
#include
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int N=3e5+13;
struct edge{
int u,v,w;
bool operator <(const edge &a)const{return w>a.w;}
}E[N];
struct ques{
int v,id;
bool operator <(const ques &a)const{return v>a.v;}
}a[N];
int n,m,q,b[N],Fa[N],deg[N],cnt[N],siz[N],cntcir,ans[N][2];
bool is[N];
int Find(int x){return Fa[x]==x?x:Fa[x]=Find(Fa[x]);}
inline void work(int u,int v){
int x=Find(u),y=Find(v);
--b[deg[u]],--b[deg[v]];
if(deg[u]==2) --cnt[x];if(is[x]) is[x]=0,--cntcir;
if(deg[v]==2) --cnt[y];if(is[y]) is[y]=0,--cntcir;
++deg[u],++deg[v];
++b[deg[u]],++b[deg[v]];
if(deg[u]==2) ++cnt[x];
if(deg[v]==2) ++cnt[y];
if(x!=y) Fa[y]=x,siz[x]+=siz[y],cnt[x]+=cnt[y];
if(cnt[x]==siz[x]) is[x]=1,++cntcir;
}
int main(){
n=rd(),m=rd();
for(int i=1;i<=m;++i) E[i].u=rd(),E[i].v=rd(),E[i].w=rd();
q=rd();
for(int i=1;i<=q;++i) a[i].v=rd(),a[i].id=i;
std::sort(E+1,E+m+1);
std::sort(a+1,a+q+1);
for(int i=1;i<=n;++i) Fa[i]=i,siz[i]=1;
b[0]=n;
for(int i=1,j=1;i<=q;++i){
while(j<=m&&E[j].w>=a[i].v) work(E[j].u,E[j].v),++j;
ans[a[i].id][0]=n-b[0]-b[2]+cntcir,ans[a[i].id][1]=j-1-b[2]+cntcir;
}
for(int i=1;i<=q;++i) printf("%d %d\n",ans[i][0],ans[i][1]);
return 0;
}
LuoguP4748 Gym101620J
首先，\((k+1)|n\)。若 \(k\) 是答案，那么子树大小是 \(\frac{n}{k+1}\) 的个数是 \(k+1\)，复杂度是 \(O(n\log \log n)\)。
点击查看代码
#include
#include
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int N=1e6+13;
struct Edge{int v,nxt;}e[N<<1];
int n,h[N],tot,siz[N],b[N];
inline void add_edge(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
void dfs(int u,int fa){
siz[u]=1;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==fa) continue;
dfs(v,u);siz[u]+=siz[v];
}
b[siz[u]]++;
}
int main(){
n=rd();
for(int i=1;i LuoguP4750 Gym101620L
注意到正方形坐标最多只有 \(2000\)，所以考虑差分，分别对两种正方形做差分（其中第二种情况相当于是将坐标轴转 \(45\degree\)）。第一种情况统计格子数就行，第二种分成四个三角形统计就行了。
AGC052B
考虑边权转点权：每个点维护到根路径的边权异或和。这样上面那个操作就变成了交换两个点点权，这样就有一个 \(O(n^2)\) 的做法，枚举根，判断初始状态和结束状态的点权集合是否相同。
考虑优化，设 \(a_u\) 表示的是 \(u\) 到 \(1\) 的路径异或和，那么如果当前以 \(rt\) 为根，当前的路径异或和是 \(a_u\oplus a_{rt}\)。所以考虑直接把 \(1\) 作为根求出开始和结束状态的结合 \(S,T\)，那么如果可行，一定是 \(S\) 里所有数异或了某个 \(a_i\) 之后得到的集合与 \(T\) 相等。这样的话，将 \(S,T\) 里所有数异或起来，得到的应该是 \(n\) 个 \(a_{rt}\) 异或的结果。又因为 \(n\) 是奇数，所以结果就是 \(a_{rt}\)。查一下这个结果是否在 \(S\) 中出现，然后直接异或起来判断一下两个集合是否相等就做完了。
Loj3140
暴力的话就是建三个竞赛图，缩点之后一定是一条链，最前面的强连通分量里的就能赢。然后考虑把他们放到排列上，每个人的 \(\min\) 到 \(\max\) 区间加一，然后找分割线（最小的值为 \(0\) 的点）大概就行了。
LuoguP5307
由于 \(\lfloor\frac{n}{1}\rfloor\ldots\lfloor\frac{n}{n}\rfloor\)，一共只有 \(O(\sqrt n)\) 种取值，所以直接设 \(f_{i,j,k}\) 表示走到 \((i,j)\)，再乘 \(k\) 就超过 \(n\) 的路径数，然后直接转移到 \(\lceil\frac{k}{a}\rceil\) 即可。空间过大，滚一下 \(i\) 维就可以了。
LuoguP7207
对于 \(A\) 集合中最大的 \(u\)，找到 \(B\) 集合中最小的 \(v\)，使得 \(u\&v=u\)，这样 \(B\) 集合下面这一些就都可以和 \(A\) 集合下面这些匹配，然后继续递归下去，复杂度 \(O(n)\)。
[COCI2019-2020] Pastiri
每次对最深的关键点找，从这个点开始向上跳，一直跳到不能跳（再跳就没法守卫这个关键点了）为止，并且把子树全部删除。如果此时还有其他点也能被守卫，那么把这个关键点到守卫点的路径也删除。总复杂度是 \(O(n)\)。
[COCI2019-2020] Semafor
朴素的做法是以 \(k\) 次为单位，构造一个 \(2^{10}\times 2^{10}\) 的矩阵，然后做矩阵快速幂。但是这样复杂度太大，考虑那个 \(k\) 的限制二进制每一位是独立的，最终的贡献只与 \(\operatorname{popcount}\) 有关，所以可以先对 \(11\times 11\) 的矩阵求一个 \(k\) 限制的贡献，然后再求具体数的答案，这样矩阵大小就只有 \(100\times 100\) 了。
AGC043B
注意到答案只有 \(0,1,2\)。将所有数减一，如果存在 \(1\)，那么答案只能是 \(0,1\)，并且 \(0\) 和 \(2\) 就可以视为等价；如果不存在 \(1\)，那么答案只能是 \(0,2\)。这就转化成每一步是异或的贡献，然后用 Lucas 算一个组合数就行了。
AGC044B
以边界为原点跑最短路，这样所有答案的和的复杂度是 \(O(n^3)\)。每次走一个点，答案加上这个点的 \(dis\)，然后从这个点出发更新其他点。这一部分的总复杂度也是上面的 \(O(n^3)\)，就做完了。
AGC045B
可以把 \(0\) 视作 \(-1\)，这样做一个前缀和之后，极差就是区间个数差的最大值。朴素的做法是枚举最大值，然后贪心地让最小值更大一些。
现在考虑先把所有 ? 变成 \(-1\)，假设这样的最大值是 \(s\)，那么如果要通过修改一个 -1 变成 1 使 \(s+2\)，那么最小值此时最多加 \(2\)，显然不会更优。所以最终只需要 check 一下最大值为 \(s\) 和 \(s+1\) 的情况就行了。
AGC045C
不妨设 \(A\geq B\)，可以通过 \(0,1\) 交换的方式交换 \(A,B\)。
对于每个串判断它能不能变换成全 \(0\)。如果有连续 \(A\) 个 \(0\) 就合法，另外，把连续的 \(B\) 个 \(1\) 都变成 \(0\) 之后有连续 \(A\) 个 \(0\) 就合法。
然后直接设 \(f_{i,j,0/1}\) 表示搞了 \(i\) 位，当前位为 \(0/1\)，当前后缀去掉连续 \(B\) 个 \(1\) 之后有连续多少个 \(0\)。朴素的转移是 \(O(n^3)\)，前缀和优化至 \(O(n^2)\) 就做完了。
CF1458C
先随机几次找好点（不能有返祖边），如果随机 \(100\) 次找不到直接退出。找到一个就能推出其他的。子树内不能有超过一条返祖边，如果有一条，那么返祖边指向的点是好点，这个点就是好点。
CF1444D
猜一个结论：只要满足 \(h=v\) 且横竖两个方向都能分成长度和相等的两组，就有解。
证明大概就是给线段排个序，然后按顺序放，使得在某一边放的时候一直都不会超过对角线，所以就不可能相交了。
点击查看代码
#include
#include
#include
#include
const int N=1000+13,M=5e5+13;
int n,m,sumx,sumy,a[N],b[N],x0[N],x1[N],y0[N],y1[N],tx0,tx1,ty0,ty1;
int cnt,ans[N][2];
std::bitset dp[N];
inline bool init(){
for(int i=1;i<=n;++i) dp[i]=(dp[i-1]|(dp[i-1]<>1]) return 0;
int sum=(sumx>>1);
for(int i=n;i;--i)
if(sum>=a[i]&&dp[i-1][sum-a[i]]) sum-=a[i],x1[++tx1]=a[i];
else x0[++tx0]=a[i];
for(int i=1;i<=n;++i) dp[i]=(dp[i-1]|(dp[i-1]<>1]) return 0;
sum=(sumy>>1);
for(int i=n;i;--i)
if(sum>=b[i]&&dp[i-1][sum-b[i]]) sum-=b[i],y1[++ty1]=b[i];
else y0[++ty0]=b[i];
return 1;
}
inline void solve(){
if(tx1<=ty1){
std::sort(x0+1,x0+tx0+1,std::greater());
std::sort(x1+1,x1+tx1+1,std::greater());
std::sort(y0+1,y0+ty0+1);
std::sort(y1+1,y1+ty1+1);
int nowx=0,nowy=0,i0=1,i1=1,j0=1,j1=1;
while(n--){
if(i1<=tx1) nowx+=x1[i1++];
else nowx-=x0[i0++];
ans[++cnt][0]=nowx,ans[cnt][1]=nowy;
if(j1<=ty1) nowy+=y1[j1++];
else nowy-=y0[j0++];
ans[++cnt][0]=nowx,ans[cnt][1]=nowy;
}
}
else{
std::sort(x0+1,x0+tx0+1);
std::sort(x1+1,x1+tx1+1);
std::sort(y0+1,y0+ty0+1,std::greater());
std::sort(y1+1,y1+ty1+1,std::greater());
int nowx=0,nowy=0,i0=1,i1=1,j0=1,j1=1;
while(n--){
if(j1<=ty1) nowy+=y1[j1++];
else nowy-=y0[j0++];
ans[++cnt][0]=nowx,ans[cnt][1]=nowy;
if(i1<=tx1) nowx+=x1[i1++];
else nowx-=x0[i0++];
ans[++cnt][0]=nowx,ans[cnt][1]=nowy;
}
}
}
inline void print(){
puts("Yes");
for(int i=1;i<=cnt;++i) printf("%d %d\n",ans[i][0],ans[i][1]);
}
int main(){dp[0][0]=1;int T;scanf("%d",&T);while(T--){
tx0=tx1=ty0=ty1=sumx=sumy=cnt=0;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),sumx+=a[i];
scanf("%d",&m);
for(int i=1;i<=m;++i) scanf("%d",&b[i]),sumy+=b[i];
if(n!=m||(sumx&1)||(sumy&1)||!init()){puts("No");continue;}
solve();
print();
}
return 0;
}
Day 2
Test 1
point: \(60+10+0+100=170\)
rk: \(35\)
stO zrz CCCCOrz！
A
设 \(s=a+b\)，那么首先可以通过开始结束状态的 \(s\) 是否相等来判断是否有解。
如果相等，此时其实只需要使 \(a\) 变成 \(c\) 即可。
考虑 \(k\) 次操作之后，\(a'=2^ka-ts\)，其中 \(t\in [ 0,2^k)\)，所以 \(2^k>p\) 一定有解。这样就只需要枚举 \(k\)，判断 \(\frac{c-2^ka}{s}\) 是否小于 \(2^k\) 即可。复杂度 \(O(q\log p)\)。
赛时：最后一步用 exgcd 判断的，所以多一个 \(\log\) 被卡到 \(60pts\)……正睿机子实在是有点慢。
点击查看代码
#include
#include
#define re register
#define rint re int
typedef long long ll;
inline void swap(int &x,int &y){x^=y^=x^=y;}
inline int rd(){
rint res=0;re char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
void wt(rint x){if(x>9)wt(x/10);putchar(x%10+'0');}
int p,q;
inline int qpow(int a,int k){int s=1;for(;k;k>>=1,a=(ll)a*a%p)if(k&1)s=(ll)s*a%p;return s;}
void exgcd(const int &a,const int &b,re ll &x,re ll &y){
if(!b){x=1,y=0;return;}
exgcd(b,a%b,y,x);
y-=(a/b)*x;
}
signed main(){
p=rd(),q=rd();
while(q--){
rint a=rd(),b=rd(),c=rd(),d=rd();
if((a+b)%p!=(c+d)%p){puts("-1");continue;}
if(a==c){puts("0");continue;}
if(p==2){puts("1");continue;}
rint ans=1;ll x=a,y=1;
int ni=qpow((a+b)%p,p-2);
while(ans<=31){
y*=2,x=y*a%p;
rint tmp=(ll)ni*((x-c)%p+p)%p;
if(tmp B
首先考虑 \(n\leq 25\) 的情况，因为 \(k=n-2\)，找到两个和相等的集合，将他们重合的部分和剩下的其他数都删去就行了。
考虑 \(n>25\) 时，其实只需要考虑最后 \(25\) 个数。贪心地放前面 \(n-25\) 个数，使其最后的两个集合的差 \(x\) 的绝对值 \(\leq W\)。然后由于数据随机，所以后面的那 \(25\) 个数的所有子集几乎一定会出现差为 \(x\) 的，然后就把剩下的数删去就行了。
赛时：完全不会，连 \(n\leq 25\) 的部分分都没写出来。
点击查看代码
#include
#include
#define lowbit(x) (x&-x)
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int N=2e5+13,M=(1<<25)+13;
int n,k,a[N],b[M],ans1[N],ans2[N];
int ms[M];
inline void solve1(){
for(int i=0;i>i)&1),r2=((a2>>i)&1);
if(!(r1^r2)) continue;
if(r1) ans1[++cnt1]=i+1;
else ans2[++cnt2]=i+1;
}
printf("%d ",cnt1);for(int i=1;i<=cnt1;++i) printf("%d ",ans1[i]);puts("");
printf("%d ",cnt2);for(int i=1;i<=cnt2;++i) printf("%d ",ans2[i]);puts("");
}
inline void solve2(){
int now=0,cnt1=0,cnt2=0;
for(int i=26;i<=n;++i){
if(now<=0) ans1[++cnt1]=i,now+=a[i];
else ans2[++cnt2]=i,now-=a[i];
}
for(int i=0;i<25;++i) b[1<0&&b[s]+now<(1<<25)&&ms[b[s]+now]){a1=s,a2=ms[b[s]+now];break;}
if(b[s]-now>0&&b[s]-now<(1<<25)&&ms[b[s]-now]){a2=s,a1=ms[b[s]-now];break;}
ms[b[s]]=s;
}
if(!a1) return puts("-1"),void();
// std::swap(a1,a2);
for(int i=0;i<25;++i){
bool r1=((a1>>i)&1),r2=((a2>>i)&1);
if(!(r1^r2)) continue;
if(r1) ans1[++cnt1]=i+1;
else ans2[++cnt2]=i+1;
}
printf("%d ",cnt1);for(int i=1;i<=cnt1;++i) printf("%d ",ans1[i]);puts("");
printf("%d ",cnt2);for(int i=1;i<=cnt2;++i) printf("%d ",ans2[i]);puts("");
}
int main(){
n=rd(),k=rd();
for(int i=1;i<=n;++i) a[i]=rd();
if(n<=25) solve1();
else solve2();
return 0;
}
C
分析一下什么情况下一个点的工资能被算出。
首先，如果一个点有兄弟，那么这两个点在任何询问中都同时出现，不可能算出。
如果这个点的子树 \(siz\geq k+1\)，那么可以用父亲子树 \(-\) 自己子树来得到答案；
如果这个点的子树 \(siz\leq k\)，那么需要满足以下条件：
-
它是叶子
-
它的父亲只有它一个儿子
-
它父亲的父亲至少有 \(k\) 个儿子
-
它父亲的父亲的其他子树要么 \(siz\geq k+1\)，要么是叶子
这样可以通过父亲的父亲的子树 \(-\) 父亲的父亲的儿子 \(-\) 父亲的父亲的其他子树来得到答案。没有其他情况了。
现在考虑用树形 dp 来计算答案。设 \(dp_i\) 表示 \(i\) 及其子树内一共最多能知道几个点。
对于第一种情况，如果一个儿子 \(v\) 的 \(siz\geq k+1\)，那么可以 \(dp_u=\max(dp_u,dp_v+1)\)；
对于第二种情况，首先当前点儿子个数 \(\geq k\)，然后考虑删完了之后只有一个，\(siz=2\) 的子树，剩下的都是 \(siz\geq k+1\) 或叶子。可以把 \(dp=0\) 的子树删成叶子，然后留一个 \(siz\geq 2\) 的就行了。反正就是只要有 \(k\) 个儿子并且里边有至少一个 \(dp=0,siz\geq 2\) 的就能把所有儿子 \(dp\) 值相加了。
赛时：没时间看也没时间想，暴力也不会做。
点击查看代码
#include
#include
inline int max(const int &a,const int &b){return a>b?a:b;}
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int N=8e5+13;
struct Edge{int v,nxt;}e[N<<1];
int n,k,h[N],tot,siz[N],dp[N];
inline void add_edge(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
inline void Clear(){
for(int i=1;i<=n;++i) h[i]=dp[i]=0;tot=0;
}
void dfs(int u){
siz[u]=1;int son=0,sum=0;bool flag=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
dfs(v);
siz[u]+=siz[v],++son,sum+=dp[e[i].v];
if(siz[v]>=2&&!dp[v]) flag=1;
if(siz[v]>=k+1) dp[u]=max(dp[u],dp[v]+1);
}
dp[u]=max(dp[u],sum+(flag&&son>=k));
}
int main(){int T=rd();while(T--){
n=rd(),k=rd();
Clear();
for(int i=2;i<=n;++i){
int x=rd();
add_edge(x,i);
}
dfs(1);
printf("%d\n",dp[1]);
}
return 0;
}
D
诈骗题，直接 dp。设 \(f_i\) 表示从 \(i\) 后面截断的乘积之和。
\[\begin{aligned} f_0&=1\\ f_i&=\sum_{j=0}^{i-1}f_j(s_i-10^{i-j}s_j)\\ &=s_i\sum_{j=0}^{i-1}f_j-10^i\sum_{j=0}^{i-1}10^{-j}s_j \end{aligned} \]然后就前缀和分别记录这两项就 \(O(n)\) 了。
赛时：过了。
点击查看代码
#include
typedef long long ll;
const int N=2e5+13,mod=998244353;
int n,s[N],f[N],mul[N];
char in[N];
inline void init(){
mul[0]=1;
for(int i=1;i<=n;++i) mul[i]=(ll)mul[i-1]*10%mod;
}
inline int calc(int l,int r){return (s[r]-(ll)s[l-1]*mul[r-l+1]%mod+mod)%mod;}
int main(){
scanf("%d",&n);init();
scanf("%s",in+1);
for(int i=1;i<=n;++i) s[i]=((ll)s[i-1]*10+(in[i]-'0'))%mod;
int g=0,h=0;
for(int i=1;i<=n;++i){
f[i]=(s[i]+((ll)s[i]*g%mod-(ll)h*10%mod+mod)%mod)%mod;
g=(g+f[i])%mod;
h=((ll)h*10%mod+(ll)f[i]*s[i]%mod)%mod;
}
printf("%d\n",f[n]);
return 0;
}
Day 3
Test 2
point: \(100+100+0+30=230\)
rk: \(31\)
A
胡乱搜一下，用康托展开或者 unordered_map 记录点是否经过就做完了。可以一开始先多源 bfs 预处理所有点的答案，也可以先预处理边，每次跑个bfs就行了。
赛时：过了。
点击查看代码
#include
#include
#include
#include
#include
#define pb push_back
#define re register
#define rint re int
#define mp std::make_pair
#define fi first
#define se second
typedef std::pair pii;
inline void swap(int &x,int &y){x^=y^=x^=y;}
const int N=370000+13;
bool ms[N],vis[N];
inline bool check(int *a){
return a[1]+a[2]+a[3]==15&&a[4]+a[5]+a[6]==15&&a[7]+a[8]+a[9]==15&&
a[1]+a[4]+a[7]==15&&a[2]+a[5]+a[8]==15&&a[3]+a[6]+a[9]==15&&
a[1]+a[5]+a[9]==15&&a[3]+a[5]+a[7]==15;
}
int mul[10],d[10];
inline int calc(int *a){
int res=1,s[10];
for(int i=1;i<=9;++i){
s[i]=0;
for(int j=i+1;j<=9;++j) s[i]+=(a[j] g[N];
inline void init(){
mul[0]=1;
for(rint i=1;i<=8;++i) mul[i]=mul[i-1]*i;
rint cnt=0;
for(rint i=1;i<=9;++i) d[i]=i;
do{
++cnt;
if(check(d)) ms[cnt]=1;
for(int i=1;i<=8;++i){
if(i==3||i==6) continue;
memcpy(c,d,sizeof d);
swap(c[i],c[i+1]);
g[cnt].pb(calc(c));
}
for(int i=1;i<=6;++i){
memcpy(c,d,sizeof d);
swap(c[i],c[i+3]);
g[cnt].pb(calc(c));
}
}while(std::next_permutation(d+1,d+10));
}
std::queue Q;
inline int bfs(rint st){
while(!Q.empty()) Q.pop();
Q.push(mp(st,0));vis[st]=1;
while(!Q.empty()){
rint u=Q.front().fi,d=Q.front().se;Q.pop();
if(ms[u]) return d;
for(auto v:g[u])
if(!vis[v]) vis[v]=1,Q.push(mp(v,d+1));
}
return -1;
}
int a[10];
int main(){//freopen("a.in","r",stdin);freopen("a.out","w",stdout);
init();rint T;scanf("%d",&T);while(T--){
memset(vis,0,sizeof vis);
for(rint i=1;i<=9;++i) scanf("%d",&a[i]);
printf("%d\n",bfs(calc(a)));
}
return 0;
}
B
xor 的直接建个trie树做就行。然后另两个的做法大概是，考虑加入一个数的时候把它的所有子集也加进来，如果已经加了就不用重复加，这样因为值域是 \(2^{20}\) 的所以复杂度是对的。然后就直接按位贪心就行了。
赛时：过了。我的做法是，建完trie树之后，从下往上把每个 \(1\) 子树向 \(0\) 子树合并。因为每个点的父亲个数是 \(\log\) 的，所以复杂度也是有保证的。离线下来之后trie树上每个点记录走到这个点的时间最小值，然后每次进来的时候，以 \(and\) 为例，如果这一位是 \(1\) 那么尽量往 \(1\) 走（最小值 \(<\) 当前询问时间），否则直接往 \(0\) 走（即 \(0,1\) 合并）就行了。
点击查看代码
#include
#include
#include
inline int min(const int &a,const int &b){return a9)wt(x/10);putchar(x%10+'0');}
const int N=(1<<20)+13,M=20+13;
struct Trie{
int ch[N<<1][2],dat[N<<1],fa[N<<1],a[M],tot;
Trie(){tot=1;memset(dat,0x3f,sizeof dat);}
inline void insert(int x,int k){
for(int i=0;i<20;++i) a[i]=((x>>i)&1);
int p=1;
for(int i=19;i>=0;--i){
if(!ch[p][a[i]]) ch[p][a[i]]=++tot,fa[tot]=p;
p=ch[p][a[i]];
}
while(p!=1)
dat[p]=min(dat[p],k),p=fa[p];
}
int merge(int p,int q){
if(!q) return p;
if(!p) p=++tot;
dat[p]=min(dat[p],dat[q]);
ch[p][0]=merge(ch[p][0],ch[q][0]);
ch[p][1]=merge(ch[p][1],ch[q][1]);
return p;
}
void dfs(int p){
if(!p) return;
if(ch[p][0]) dfs(ch[p][0]);
if(ch[p][1]) dfs(ch[p][1]);
ch[p][0]=merge(ch[p][0],ch[p][1]);
}
inline int query(int x,int k){
for(int i=0;i<20;++i) a[i]=((x>>i)&1);
int p=1,res=0;
for(int i=19;i>=0;--i){
if(ch[p][a[i]^1]&&k>dat[ch[p][a[i]^1]]) p=ch[p][a[i]^1],res|=(1<>i)&1);
int p=1,res=0;
for(int i=19;i>=0;--i){
if(a[i]&&k>dat[ch[p][1]]) p=ch[p][1],res|=(1<>i)&1);
int p=1,res=0;
for(int i=19;i>=0;--i){
if(a[i]) res|=(1<dat[ch[p][1]]) p=ch[p][1],res|=(1< C
首先，如果只有一个黑点，那么考虑一个树形 dp：\(f_u\) 表示把 \(u\) 的子树全搞完的最小时间。那么对于 \(u\) 的所有儿子，肯定是第一步走 \(f\) 值最大的那个儿子，依次类推。
如果有两个点，那么需要多考虑的是这两个点之间的这条路径。不难发现一个单调性：假设从某个黑点 \(u\) 出发到 \(v\)，那么 \(u\) 的答案肯定是越来越大的，而 \(v\) 的答案是越来越小的。这样就可以二分分界点找到这两个答案最接近的点，然后 check 的时候就做上面那个树形 dp 就行了。
赛时：第一个 dp 差不多能想出来，但是没时间写和想后面的了。前面花的时间太多，分配的不好。
点击查看代码
#include
#include
#include
#include
#define pb push_back
inline int max(const int &a,const int &b){return a>b?a:b;}
inline int min(const int &a,const int &b){return a s;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==fa||v==novis) continue;
s.pb(dfs(v,u,novis));
}
std::sort(s.begin(),s.end(),std::greater());
int res=-1;
for(int i=0,l=s.size();i>1;
int endx=a[mid],endy=a[mid-1],ansx,ansy;
ans=min(ans,max(ansx=dfs(x,0,endy),ansy=dfs(y,0,endx)));
if(ansx D
考虑离线之后从小到大加入点，用并查集维护连通块，每个连通块用一个动态开点权值线段树来维护 \(k|cnt_i\) 的 \(i\) 的个数。然后每次加一个点可能会合并连通块，这时候就把这两个连通块的线段树合并起来，在叶子节点重新统计一下就行。在最外部开一个堆来维护答案，按理说应该使用一个可删除的堆，set 也可以。但是其实可以只加入不删除，每次弹出堆顶的时候判一下这个答案是不是当前点的最新答案即可，复杂度大概是 \(1\log\) 的。
赛时：最后半小时冲了这个做法，然后因为有一些细节问题没处理好，最终只获得了 30pts。
点击查看代码
#include
#include
#include
#include
#include
#include
#define mp std::make_pair
#define fi first
#define se second
#define pb push_back
typedef std::pair pii;
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int N=2e5+13,M=5e5+13,logN=24;
struct Edge{int v,nxt;}e[M<<1];
int h[N],tot;
inline void add_edge(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
int n,m,k,q,a[N],b[N],B[N];
struct Ques{
int v,p,id;
std::vector g;
bool operator <(const Ques &a)const{return v>1)
inline void refresh(int p){t[p].siz=t[ls(p)].siz+t[rs(p)].siz;}
void update(int &p,int l,int r,int x){
if(!p) p=++pcnt;
if(l==r){
t[p].dat++;
if(t[p].dat%k==0) t[p].siz=1;
else t[p].siz=0;
return;
}
x<=mid?update(ls(p),l,mid,x):update(rs(p),mid+1,r,x);
refresh(p);
}
int merge(int p,int q,int l,int r){
if(!p||!q) return p|q;
if(l==r){
t[p].dat+=t[q].dat;
if(t[p].dat%k==0) t[p].siz=1;
else t[p].siz=0;
return p;
}
ls(p)=merge(ls(p),ls(q),l,mid);
rs(p)=merge(rs(p),rs(q),mid+1,r);
refresh(p);
return p;
}
bool vis[N],open[N];
int res[N],top[N],rt[N],tt,d[N];
std::priority_queue st;
std::queue Q;
int Find(int x){return top[x]==x?x:top[x]=Find(top[x]);}
inline void add(int u){
open[u]=1;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v,x=Find(v);if(x==u||!open[v]) continue;
rt[u]=merge(rt[u],rt[x],1,tt);
top[x]=u;
}
update(rt[u],1,tt,b[u]);
res[u]=t[rt[u]].siz,st.push(mp(res[u],u));
}
int ans[N];
int main(){
// freopen("data_d.in","r",stdin);
// freopen("data_d.out","w",stdout);
n=rd(),m=rd(),k=rd();
for(int i=1;i<=n;++i) a[i]=rd();
for(int i=1;i<=n;++i) b[i]=rd(),B[i]=b[i];
std::sort(B+1,B+n+1);tt=std::unique(B+1,B+n+1)-B-1;
for(int i=1;i<=n;++i) b[i]=std::lower_bound(B+1,B+tt+1,b[i])-B;
for(int i=1;i<=m;++i){
int u=rd(),v=rd();
add_edge(u,v),add_edge(v,u);
}
q=rd();
for(int i=1;i<=q;++i){
c[i].v=rd(),c[i].p=rd(),c[i].id=i;
for(int j=1;j<=c[i].p;++j){
int x=rd();
c[i].g.pb(x);
}
}
std::sort(c+1,c+q+1);
for(int i=1;i<=n;++i) d[i]=top[i]=i;
std::sort(d+1,d+n+1,cmp);
for(int i=1,j=1;i<=q;++i){
while(j<=n&&a[d[j]]<=c[i].v) add(d[j]),++j;
for(auto v:c[i].g) vis[Find(v)]=1;
while(!st.empty()){
int u=st.top().se,tmp=st.top().fi;
if(top[u]==u&&res[u]==tmp){
if(!vis[u]){
ans[c[i].id]=tmp;
break;
}
Q.push(mp(tmp,u));
}
st.pop();
}
while(!Q.empty()) st.push(Q.front()),Q.pop();
for(auto v:c[i].g) vis[top[v]]=0;
}
for(int i=1;i<=q;++i) printf("%d\n",ans[i]);
return 0;
}
Day 4
Test 3
point: \(100+70+100+0=270\)
rk: \(30\)
stO qyc ShanLunJiaJian Orz!
A
直接暴力算每一种染色方案，可以考虑状压然后递推。如果预处理 \(popcount\) 就能直接做到 \(O(2^n)\)。
赛时：直接 \(O(n2^n)\) 过了。
点击查看代码
#include
#include
#include
#define rint register int
#define lowbit(x) (x&-x)
inline int rd(){
rint res=0;register char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
void wt(rint x){if(x>9)wt(x/10);putchar(x%10+'0');}
const int N=25,M=(1<<25)+13;
int n,m,f[M],ans[N*N],ms[M];
bool g[N][N];
inline void init(){for(int i=0;i B
式子大概是考虑一个莫比乌斯反演，然后就是算每个数在区间里的倍数个数。可以离线下来直接做，维护有某个因数的所有数个数的前缀和，把询问差分做，统计的时候枚举因数再乘以一个莫比乌斯系数就做完了。
赛时：由于值域上界开小，有一个点 RE 被卡了 30pts。非常智障。
点击查看代码
#include
#include
#include
inline int max(const int &a,const int &b){return a>b?a:b;}
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
void wt(int x){if(x>9)wt(x/10);putchar(x%10+'0');}
const int N=7e5+13;
struct Ques{
int pos,x,id,op;
bool operator <(const Ques &a)const{return pos C
我愿称之为区间dp神题。
首先可以想到一个很基础的区间 dp，设 \(dp_{l,r,i}=0/1\) 表示 \([l,r]\) 区间内 \(i\) 能否最终获胜。这样可以把区间分成两部分，得到转移：
\[dp_{l,r,i}=\operatorname{Any} _ {l\leq j复杂度是 \(O(n^4)\)。其中，\(\operatorname{Any}\) 表示的是所有满足条件的数中有没有 \(1\)。
接下来考虑把每个人能打败的人压成一个 bitset，然后把 \(dp\) 的最后一维也压成一个 bitset，这样上式就可以写成：
复杂度是 \(O(\frac{n^4}{w})\)。
注意到转移的式子 \(e_i \& f_{l,i-1}\) 其实只有 \(O(n^2)\) 中状态，所以考虑在 dp 过程中顺带更新这些状态，设前后两种类型分别为 \(g_{l,r,0/1}\)，其中 \(g_{l,r,0}=e_r\& f_{l,r-1},g_{l,r,1}=e_l\& f_{l+1,r}\)，这样上面的转移可以写成：
\[f_{l,r,i}=g_{l,i,0}\operatorname{and}g_{i,r,1} \]复杂度是 \(O(n^3)\)。
把 \(g_{l,r,0}\) 的 \(r\) 那一维和 \(g_{l,r,1}\) 的 \(l\) 那一维都提出来压成 bitset，再滚一下数组就 \(O(\frac{n^3}{w})\) 冲过去了。
赛时：上面这个过程 2h 完成最后冲过去了。
点击查看代码
#include
#include
#include
#define pb push_back
#define rint register int
void wt(rint x){if(x>9)wt(x/10);putchar(x%10+'0');}
const int N=2000+13;
int n;
char in[N];
std::bitset f[2][N],g[N][2],e[N];
int main(){
// freopen("ex_C4.in","r",stdin);
// freopen("c.out","w",stdout);
scanf("%d",&n);getchar();
for(rint i=1;i<=n;++i) e[i].reset(),f[0][i].reset(),f[1][i].reset();
for(rint i=1;i<=n;++i){
for(rint j=1;j<=n;++j) in[j]=getchar();
for(rint j=1;j<=n;++j){
if(i==j) continue;
if(in[j]=='1') e[i][j]=1;
}
getchar();
}
for(rint i=1;i<=n;++i) f[1][i][i]=1;
for(rint len=2;len<=n;++len){
for(rint l=1;l<=n;++l){
int r=l+len-1;if(r>n) continue;
f[len&1][l]=(g[l][0]&g[r][1]);
f[len&1][l][l]=(e[l]&f[(len-1)&1][l+1]).any();
f[len&1][l][r]=(e[r]&f[(len-1)&1][l]).any();
g[l][0][r]=(g[l][0][r]|f[len&1][l][r]);
g[r][1][l]=(g[r][1][l]|f[len&1][l][l]);
}
}
for(rint i=1;i<=n;++i)
if(f[n&1][1][i]){
wt(i);
if(i!=n) putchar(' ');
}
return 0;
}
D
不会，待补。
Day 5
Test 4
point: \(100+100+0+0=200\)
rk: \(64\)
A
值最小就是把 \(a,b\) 排序之后相应乘起来。最小操作次数就是点数减去环的数量。
赛时：过了。
点击查看代码
#include
#include
#include
#include
typedef long long ll;
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
std::unordered_map ms,pos;
const int N=3e5+13,mod=998244353;
int n,a[N],b[N],c[N],d[N],fa[N];
bool vis[N];
void dfs(int u){vis[u]=1;if(!vis[fa[u]]) dfs(fa[u]);}
int main(){
ms.clear(),pos.clear();
n=rd();int type=rd(),ans=0;
for(int i=1;i<=n;++i) a[i]=rd(),c[i]=a[i],ans=(ans+(ll)a[i]*a[i]%mod)%mod;
for(int i=1;i<=n;++i) b[i]=rd(),d[i]=b[i],ans=(ans+(ll)b[i]*b[i]%mod)%mod,pos[b[i]]=i;
std::sort(c+1,c+n+1),std::sort(d+1,d+n+1);
for(int i=1;i<=n;++i) ans=(ans-2ll*c[i]*d[i]%mod+mod)%mod,ms[c[i]]=pos[d[i]];
printf("%d ",ans);
if(!type) return 0;
for(int i=1;i<=n;++i) fa[i]=ms[a[i]];
int cnt=0;
for(int i=1;i<=n;++i)
if(!vis[i]) dfs(i),++cnt;
printf("%d\n",n-cnt);
return 0;
}
B
考虑维护一个主教的两种斜线，然后每一种向另一种相交的是一个区间，直接用数据结构维护或者前缀和就行了。
赛时：过了。
点击查看代码
#include
#include
typedef long long ll;
inline int min(const int &a,const int &b){return a>1,l2=(n-x+1+y)>>1;
if(!vis[t][1][l1]){
int l=min(n-x,y-1),r=min(x-1,n-y);
res+=l+r+1-(T[t][0].sum(l2+r)-T[t][0].sum(l2-l-1));
vis[t][1][l1]=1,T[t][1].add(l1,1);
}
if(!vis[t][0][l2]){
int l=min(x-1,y-1),r=min(n-x,n-y);
res+=l+r+1-(T[t][1].sum(l1+r)-T[t][1].sum(l1-l-1));
vis[t][0][l2]=1,T[t][0].add(l2,1);
}
}
printf("%lld\n",(ll)n*n-res);
return 0;
}
C
这是一个基环树森林，首先考虑使用树形dp计算不在环上的点的答案，大概是
\[f_i=p_i+(1-p_i)(1-\prod_{j\in son(i)}(1-q_jf_j)) \]然后考虑环上的每个点，枚举他前面哪条边断了的贡献，即
\[\sum_{j=i-n+1}^i (1-\prod_{k=j}^{i}(1-f_k))(\prod_{k=j}^{i-1}q_k)(1-q_{j-1}) \]还有所有边都没断的贡献，即
\[(1-\prod_{k=i-n+1}^{i}(1-f_k))(\prod_{k=i-n+1}^{i-1}q_k) \]断环成链，动态维护 \(\sum_{j=i-n+1}^i(\prod_{k=j}^i(1-f_k))\) 和 \(\sum_{j=i-n+1}^i(\prod_{k=j}^{i-1}q_k)(1-q_{j-1})\) 即可。
赛时：不会。
D
不会，待补。
赛时：30pts 暴力由于数组没清空爆零了。
Day 6
Test 5
point: \(100+10+15+0=125\)
rk: \(30\)
A
考虑 \(q\) 中的每个下降段，设其长度为 \(l\)，相当于是在剩下的里边任选 \(l-1\) 个，最后选那个最小的。由于一定是从大往小取，所以不需要管顺序，这部分的贡献就是一个组合数。
每次修改会修改两个点的值，暴力判断一下这两个点会改变哪些下降段。由于改变是 \(O(1)\) 的，所以直接拿 set 维护每个下降段的开头，每次暴力查前驱后继就行了。复杂度是 \(O(n\log n)\)。
赛时：1h30min 通过。
点击查看代码
#include
#include
#include
typedef long long ll;
inline void swap(int &x,int &y){x^=y^=x^=y;}
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
void wt(int x){if(x>9)wt(x/10);putchar(x%10+'0');}
const int N=3e5+13,mod=1e9+7;
inline int qpow(int a,int k){int s=1;for(;k;k>>=1,a=(ll)a*a%mod)if(k&1)s=(ll)s*a%mod;return s;}
int n,m,q[N],mul[N],invmul[N];
std::set t;
std::set::iterator it;
inline void init(){
mul[0]=invmul[0]=1;
for(int i=1;i<=n;++i) mul[i]=(ll)mul[i-1]*i%mod;
invmul[n]=qpow(mul[n],mod-2);
for(int i=n-1;i;--i) invmul[i]=(ll)invmul[i+1]*(i+1)%mod;
}
inline int C(int n,int m){return (ll)mul[n]*invmul[m]%mod*invmul[n-m]%mod;}
int main(){
// freopen("ex_a3.in","r",stdin);
// freopen("a.out","w",stdout);
n=rd(),m=rd();
init();
for(int i=1;i<=n;++i) q[i]=rd();
int ans=1;
for(int i=1,j;i<=n;i=j+1){
t.insert(i);
j=i;
while(jv) swap(u,v);
int tmpu=q[u],tmpv=q[v];
it=t.upper_bound(u);
int r=(*it)-1,l=*(--it);
if(u==l&&u!=1&&tmpvq[u-1]){
ans=(ll)ans*qpow(C(n-l,r-l),mod-2)%mod;
t.insert(u);
ans=(ll)ans*C(n-l,(u-1)-l)%mod*C(n-u,r-u)%mod;
l=u;
}
it=t.upper_bound(u);
if(u==r&&q[u+1]u&&q[u+1]>tmpv){
ans=(ll)ans*qpow(C(n-l,r-l),mod-2)%mod;
t.insert(u+1);
ans=(ll)ans*C(n-l,u-l)%mod*C(n-(u+1),r-(u+1))%mod;
}
q[u]=tmpv;
it=t.upper_bound(v);
r=(*it)-1,l=*(--it);
if(v==l&&tmpuq[v-1]){
ans=(ll)ans*qpow(C(n-l,r-l),mod-2)%mod;
t.insert(v);
ans=(ll)ans*C(n-l,(v-1)-l)%mod*C(n-v,r-v)%mod;
l=v;
}
it=t.upper_bound(v);
if(v==r&&v!=n&&q[v+1]v&&q[v+1]>tmpu){
ans=(ll)ans*qpow(C(n-l,r-l),mod-2)%mod;
t.insert(v+1);
ans=(ll)ans*C(n-l,v-l)%mod*C(n-(v+1),r-(v+1))%mod;
}
q[v]=tmpu;
wt(ans),putchar('\n');
}
}
return 0;
}
B
如果使用欧拉回路来求，这样在中间的每两条边都经过同一个点，标成不同的颜色。但是第一条边和最后一条边不一定可以标成不同的颜色。所以首先判断，如果一个连通块都是偶度点，但是有奇数条边，那么直接无解。否则，把奇度点向超级源点建一条边，从超级源点开始跑，这样超级源点没有那个限制，不必要求首尾颜色相同，这样直接根据欧拉回路定色就行了。
赛时：不会欧拉回路，也没思考出无解的情况，打了原始的 \(10\) 分暴力。
点击查看代码
#include
#include
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int N=2e6+13;
struct Edge{int v,nxt;}e[N<<2];
int n,m,h[N],tot=1,a[N],cnt,deg[N];
bool vis[N],ans[N];
inline void add_edge(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
void dfs(int u){
for(int &i=h[u];i;i=e[i].nxt){
int v=e[i].v,j=(i>>1);
if(vis[j]) continue;
vis[j]=1,dfs(v);
a[++cnt]=j;
}
}
int main(){
n=rd(),m=rd();
for(int i=1;i<=m;++i){
int u=rd(),v=rd();
add_edge(u,v),add_edge(v,u);
deg[u]++,deg[v]++;
}
for(int i=1;i<=n;++i)
if(deg[i]&1) add_edge(i,n+1),add_edge(n+1,i);
dfs(n+1);
for(int i=1;i<=cnt;++i) ans[a[i]]=(i&1);
for(int i=1;i<=n;++i){
cnt=0;dfs(i);
if(cnt&1) return puts("-1"),0;
for(int j=1;j<=cnt;++j) ans[a[j]]=(j&1);
}
for(int i=1;i<=m;++i) putchar(ans[i]?'1':'0'),putchar(' ');
return 0;
}
C
考虑求出每一个点的“前后缀线性基”，也就是从根出发 dfs，退出某个点的时候将其加入线性基。这样两次 dfs（第二次是反着遍历儿子）之后，两次的线性基的并就是一个点到不了的所有点的集合构成的线性基。
如果直接这样做，复杂度是 \(O(n\log^2 v)\)，卡卡常或许能过。但是可以发现，其实两次 dfs 都只会产生 \(O(\log v)\) 种线性基（满了就不能再插了），所以可以先预处理出每两种之间的并的答案，这样做复杂度 \(O(n\log v+\log^4 v)\) 可以通过。
注意：最后处理的时候，一定注意到底求了多少个线性基。
赛时：最后 20min 想了一个 \(3\log\) 的树剖线段树分治，冲完了但是挂了。只拿了 15pts 最低暴力分。
点击查看代码
#include
#include
#include
#include
#define pb push_back
typedef long long ll;
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
void wt(ll x){if(x>9)wt(x/10);putchar(x%10+'0');}
inline ll llrd(){
ll res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int N=4e5+13,M=62+13;
struct Onbase{
ll p[M];
inline void clear(){memset(p,0,sizeof p);}
Onbase(){clear();}
inline bool insert(ll x){
for(int i=60;i>=0;--i){
if(!((x>>i)&1)) continue;
if(!p[i]) return p[i]=x,1;
x^=p[i];
if(!x) break;
}
return 0;
}
inline ll query(){
ll res=0;
for(int i=60;i>=0;--i)
if((res^p[i])>res) res^=p[i];
return res;
}
}now,b1[M],b2[M],b3[M][M];
Onbase merge(Onbase A,Onbase B){
for(int i=0;i<=60;++i)
if(B.p[i]) A.insert(B.p[i]);
return A;
}
std::vector e[N];
int n,cnt,a1[N],a2[N];
ll b[N];
void dfs1(int u,int fa){
a1[u]=cnt;
for(int i=0,l=e[u].size();i=0;--i){
int v=e[u][i];if(v==fa) continue;
dfs2(v,u);
}
if(now.insert(b[u])) ++cnt,b2[cnt]=now;
}
int main(){
// freopen("ex_c3.in","r",stdin);
// freopen("cc.out","w",stdout);
n=rd();
for(int i=1;i<=n;++i) rd();
for(int i=1;i<=n;++i) b[i]=llrd();
for(int i=1;i D
首先考虑这个答案应该等于什么：
在原图上求出每个点的度数 \(d_i\)，对于反图的每个连通块，如果有某个连通块每个点的 \(d_i\) 之和为奇数，那么无解（因为每加一条边都会改变两个点度数的奇偶性，所以无论如何也没法全变成偶数）。
在这个联通块中任意找一个生成树，那么不在树上的边随便选，对于每一种选择，在树上的边只有一种选择方式对应使得所有点度数为偶数。注意到这一点后，我们设反图边数为 \(e\)，连通块数为 \(c\)，那么答案就是 \(2^{e-(n-c)}=2^{e-n+c}\)。
现在考虑如何求出 \(e\) 和 \(c\)。注意到题目中的加边操作是给一个矩形加 \(1\) 或者赋值成 \(1\)，把它差分之后从下到上做扫描线，扫到 \(i\) 的时候，线段树叶子节点所有的 \(0\) 就表示还没有连边。
考虑 Boruvka 算法：每一轮从每个连通块向另一个点连边，轮次至多有 \(O(\log n)\)。在维护区间最小值的同时，维护一个区间取到最小值时的 \(2\) 个不同的连通块编号，其中一定有一个与 \(i\) 的连通块编号不同。连通块就使用并查集维护就行，这样做每一轮直到没有边可以连，最后统计 find(i)=i 的点数就是连通块个数。
点击查看代码
#include
#include
#include
#define pb push_back
typedef long long ll;
inline int min(const int &a,const int &b){return a>=1,a=(ll)a*a%mod)if(k&1)s=(ll)s*a%mod;return s;}
int n,m,Fa[N],deg[N];
struct Node{int l,r,k;};
std::vector e[N];
int Find(int x){return Fa[x]==x?x:Fa[x]=Find(Fa[x]);}
struct SegTree{int l,r,tag,dat,minn,p1,p2;}t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((t[p].l+t[p].r)>>1)
inline void refresh(int p){
static int b[5],cnt;
t[p].minn=min(t[ls].minn,t[rs].minn);
t[p].dat=cnt=0;
if(t[ls].minn==t[p].minn) b[++cnt]=t[ls].p1,b[++cnt]=t[ls].p2,t[p].dat+=t[ls].dat;
if(t[rs].minn==t[p].minn) b[++cnt]=t[rs].p1,b[++cnt]=t[rs].p2,t[p].dat+=t[rs].dat;
t[p].p1=t[p].p2=b[1];
for(int i=2;i<=cnt;++i)
if(b[i]!=b[1]){t[p].p2=b[i];break;}
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r,t[p].tag=0;
if(l==r){
t[p].dat=1,t[p].minn=0;
t[p].p1=t[p].p2=Find(l);
return;
}
build(ls,l,mid),build(rs,mid+1,r);
refresh(p);
}
inline void pushup(int p,int k){t[p].minn+=k,t[p].tag+=k;}
inline void pushdown(int p){
if(!t[p].tag) return;
pushup(ls,t[p].tag),pushup(rs,t[p].tag);t[p].tag=0;
}
void update(int p,int l,int r,int k){
if(l<=t[p].l&&t[p].r<=r) return pushup(p,k);
pushdown(p);
if(l<=mid) update(ls,l,r,k);
if(r>mid) update(rs,l,r,k);
refresh(p);
}
int query(int p,int x){
if(t[p].l==t[p].r) return t[p].minn;
pushdown(p);
return x<=mid?query(ls,x):query(rs,x);
}
int main(){
n=rd(),m=rd();
for(int i=1;i<=m;++i){
int x1=rd(),x2=rd(),y1=rd(),y2=rd();
e[x1].pb((Node){y1,y2,1});
if(x2>1)-n;
for(int i=1;i<=n;++i) res+=(Find(i)==i);
printf("%d\n",qpow(2,res%(mod-1)));
return 0;
}
Day 7
Test 6
point: \(100+0+30+0=130\)
rk: \(70\)
垃圾比赛！傻逼出题人！
A
差分之后扫描线，开两个 set，一个维护当前最大的 \(k\) 个或不到 \(k\) 个，另一个维护当前还在时间范围内，但排不进前 \(k\) 大的。这样每个操作就搞一搞就完事了。
赛时：过了。
点击查看代码
#include
#include
#include
#include
#include
typedef long long ll;
inline ll max(const ll &a,const ll &b){return a>b?a:b;}
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
inline void print(char *s){
int l=strlen(s);
for(int i=0;i9)wt(x/10);putchar(x%10+'0');}
const int N=3e5+13;
struct Node{
int pos,val;bool op;
bool operator <(const Node &a)const{return pos t,tt;
std::multiset::iterator it;
ll sum;int cnt;
inline void add(Node x){
if(x.op){
if(cntv){
it=t.find(v);t.erase(it);
tt.insert(v),t.insert(x.val),sum+=x.val-v;
}
else tt.insert(x.val);
}
}
else{
it=tt.find(x.val);
if(it!=tt.end()) tt.erase(it);
else{
if(cnt B
考虑同一个学校的两个点连边，然后 \(1\to2,3\to4\ldots 2k-1\to 2k\) 这样连边，这样连出来的一定是一个二分图（因为没有奇环）。直接跑二分图染色就行了。
赛时：图可能不连通，跑染色只从 \(1\) 开始跑的，挂成了 \(0\) 分……
点击查看代码
#include
#include
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int N=1e6+13;
struct Edge{int v,nxt;}e[N<<1];
int n,h[N],tot,col[N];
inline void add_edge(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
void dfs(int u,int c){
col[u]=c;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(!col[v]) dfs(v,3-col[u]);
}
}
int main(){
n=rd();
for(int i=1;i<=n;++i){
int x=rd(),y=rd();
add_edge(x,y),add_edge(y,x);
}
for(int i=1;i<=(n<<1);i+=2) add_edge(i,i+1),add_edge(i+1,i);
for(int i=1;i<=(n<<1);++i)
if(!col[i]) dfs(i,1);
for(int i=1;i<=(n<<1);++i) putchar(col[i]==1?'X':'Y');
return 0;
}
C
先把 \(a\) 数组排序，这样 \(a\) 大的一定选的长度更短，所以考虑一个 dp：设 \(dp_{i,j,k}\) 表示当前长度为 \(i\)，已经选了 \(j\) 个数，当前层剩余叶子节点数 \(k\) 个的答案。转移就是
\[dp_{i,j,k}=\left\{ \begin{aligned} \min(dp_{i-1,j,\lceil\frac{k}{2}\rceil},dp_{i,j-1,k+1})&,k然后下面这个转移可以先统计一个后缀 \(\min\)，就可以做到 \(O(Tn^2l)\)，卡卡常可以通过。
赛时：交了一发 60pts 暴力，第二发 60pts 常数太大 T 了，然后 \(60\to 30\)……
点击查看代码
#include
#include
#include
#include
typedef long long ll;
inline ll min(const ll &a,const ll &b){return a());
for(int i=1;i<=n;++i) s[i]=s[i-1]+a[i];
memset(f,0x3f,sizeof f);memset(g,0x3f,sizeof g);
ll ans=LLINF;
f[0][0][1]=0;
for(int k=(n-1)/2+1;k<=n;++k) g[0][0]=min(g[0][0],f[0][0][k]);
for(int i=1;i<=m;++i){
for(int j=0;j<=n;++j){
for(int k=0;k<=n;++k){
if(k==n) f[i][j][k]=g[i-1][j];
else if(!(k&1)) f[i][j][k]=f[i-1][j][k>>1];
if(j) f[i][j][k]=min(f[i][j][k],f[i][j-1][k+1]+(ll)i*a[j]);
}
for(int k=(n-1)/2+1;k<=n;++k) g[i][j]=min(g[i][j],f[i][j][k]);
}
for(int j=0;j<=n;++j) ans=min(ans,f[i][n][j]);
}
printf("%lld\n",ans);
}
return 0;
}
D
Day 8
Test 7
point: \(100+70+50+30=250\)
rk: \(59\)
A
形状类似线段树，维护每一层最小的次大值，从大到小判一下每个数能大于哪一层的次大值就行了。
赛时：用 set 维护的每个数，实际上不需要，过了。
点击查看代码
#include
#include
#include
#include
inline int max(const int &a,const int &b){return a>b?a:b;}
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
void wt(int x){if(x>9)wt(x/10);putchar(x%10+'0');}
const int N=20,M=(1<<19)+13;
int n,p[M],d[M],mx1[M],mx2[M],ans[M],ms[M];
std::set t;
int main(){
n=rd();
for(int i=(1<mx1[rs]) mx1[i]=mx1[ls],mx2[i]=max(mx2[ls],mx1[rs]);
else mx1[i]=mx1[rs],mx2[i]=max(mx1[ls],mx2[rs]);
ans[mx1[i]]=d[i];
}
for(int i=1;i<=(1< del;del.clear();
for(std::set::iterator it=t.end();it!=t.begin();){
--it;
int p=*(it);
if(p>d[i])!=i) ans[p]=max(ans[p],d[i]),del.push_back(p);
}
for(auto p:del) t.erase(p);
}
for(int i=1;i<=(1< B
那个逆序对就是扯淡。
计算树上距离为 \(k\) 的点对数量，可以使用长链剖分（按高度合并）。
这题启发式合并和点分治都被卡 $\log $ 了。
赛时：被卡 \(\log\) 了。
C
基环树，树的部分直接树形 dp 求出最长的和子树内最长路径，环上首先断掉 \([a_1,a_m]\) 这条边，然后求一个前后缀到 \(a_1\) 和 \(a_m\) 的最长路 \(pre1_i,suf1_i\)，再求一个内部的最长路 \(pre2_i,suf2_i\)，枚举环上断掉第 \(i\) 条边，答案就是 \(\max(pre2_i,suf2_{i+1},pre1_i+suf1_{i+1}+1)\)。或者也可以把那个式子写开，发现就是一个单调队列的形式，直接优化一下 dp 就行了。
赛时：找环找错了，\(100\to 70\)。
点击查看代码
#include
#include
#include
inline int max(const int &a,const int &b){return a>b?a:b;}
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
void wt(int x){if(x<0)putchar('-'),x=-x;if(x>9)wt(x/10);putchar(x%10+'0');}
const int N=5e5+13;
struct edge{int u,v;}E[N];
struct Edge{int v,nxt;}e[N<<1];
int n,h[N],tot=1,ans[N],a[N],b[N],d[N],cnt,dd[N],maxd[N];
int pre1[N],pre2[N],suf1[N],suf2[N];
bool vis[N],incircle[N],is[N];
inline void add_edge(int u,int v){
e[++tot]=(Edge){v,h[u]};h[u]=tot;
e[++tot]=(Edge){u,h[v]};h[v]=tot;
++d[u],++d[v];
}
void dfs_circle(int u,int pre,int t,bool flag){
if(!flag&&u==t) return;
a[++cnt]=u;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if((i>>1)==pre||!is[v]) continue;
b[cnt+1]=(i>>1),dfs_circle(v,i>>1,t,0);
break;
}
}
inline void find_circle(){
std::queue q;while(!q.empty()) q.pop();
for(int i=1;i<=n;++i) is[i]=incircle[i]=1;
for(int i=1;i<=n;++i)
if(d[i]==1) q.push(i);
while(!q.empty()){
int u=q.front();q.pop();is[u]=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;incircle[i>>1]=0;
if(is[v]&&(--d[v])==1) q.push(v);
}
}
int now=0;
for(int i=1;i<=n;++i)
if(is[i]){now=i;break;}
dfs_circle(now,0,now,1);
}
void init(int u,int fa){
int mx1=0,mx2=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(is[v]||v==fa) continue;
init(v,u);maxd[u]=max(maxd[u],maxd[v]);
if(dd[v]+1>mx1) mx2=mx1,mx1=dd[v]+1;
else if(dd[v]+1>mx2) mx2=dd[v]+1;
}
dd[u]=mx1;
maxd[u]=max(maxd[u],mx1+mx2);
}
int main(){
// freopen("in.in","r",stdin);
// freopen("in.out","w",stdout);
n=rd();
for(int i=1;i<=n;++i) E[i].u=rd(),E[i].v=rd(),add_edge(E[i].u,E[i].v);
find_circle();
for(int i=1;i<=n;++i)
if(!incircle[i]) ans[i]=-1;
for(int i=1;i<=cnt;++i) is[a[i]]=1;
int Ans=0;
for(int i=1;i<=cnt;++i) init(a[i],0),Ans=max(Ans,maxd[a[i]]);
int maxpre=0;
for(int i=1;i<=cnt;++i){
pre1[i]=max(pre1[i-1],i-1+dd[a[i]]);
pre2[i]=max(pre2[i-1],max(maxpre+dd[a[i]],maxd[a[i]]));
maxpre=max(maxpre,dd[a[i]])+1;
}
int maxsuf=0;
for(int i=cnt;i;--i){
suf1[i]=max(suf1[i+1],cnt-i+dd[a[i]]);
suf2[i]=max(suf2[i+1],max(maxsuf+dd[a[i]],maxd[a[i]]));
maxsuf=max(maxsuf,dd[a[i]])+1;
}
ans[b[cnt+1]]=pre2[cnt];
for(int i=2;i<=cnt;++i) ans[b[i]]=max(max(max(pre2[i-1],suf2[i]),pre1[i-1]+suf1[i]+1),Ans);
for(int i=1;i<=n;++i) wt(ans[i]),putchar('\n');
return 0;
}
D
考虑每个 \(0\) 的位置与时间的函数，大概是形成了一个折线，把这个折线向左上平移一个单位就能得到下一个 \(0\) 的限制位置，这样可以使用队列均摊 \(O(1)\) 维护折线即可。
Day 9
Test 8
point: \(100+70+30+0=200\)
rk: \(7\)
A
记 \(c\) 为当前乘的 \(2\) 的幂次。
如果 \(n\) 是偶数，\(n=n/2,c=c+1\)；
如果 \(n\) 是奇数，找到最大的 \(3^k\leq n\)，\(n=n-3^k\)。
由于 \(n<3^{k+1}\)，所以 \(k\) 是严格递减的；
又由于 \(n\) 是奇数时 \(3^k\) 也是奇数，所以 \(c\) 是严格递增的。
然后就做完了。
赛时：我的做法大概是，从高到低枚举 \(3\) 的次幂，再从小到大枚举一个 \(2\) 的次幂，设为 \(3^a2^b\)，如果 \((n-3^a2^b)\bmod 2^{b+1}=0\) 那么就选它。应该和上边的做法是差不多等价的。
点击查看代码
n=int(input())
k=1
ans=[0]
ans*=1001
cnt=0
while 3*k<=n:
k*=3
while n>0:
x=k
y=1
while x<=n:
if (n-x)%(2*y)==0:
ans[cnt]=x
n-=x
cnt+=1
break
x*=2
y*=2
k//=3
print(cnt)
for i in range(0,cnt):
print(ans[i],end=' ')
B
线性相关相当于是三个向量不共面。这样考虑算出每两个向量确定的平面的法向量，然后三个向量共面相当于两两确定的平面相同。
可以使用 unordered_map 来记录这些法向量（同一个平面的法向量可以通过 gcd 和正负号的统一搞成一样的），也可以直接对所有这些排序做。有点卡常。
赛时：70pts 暴力还是比较稳的。
C
\(O(n^3)\) 做法就是直接背包做，换根 dp 优化。
考虑把每个点的 dp 值的生成函数设为 \(F_u(x)=\sum_{i}dp(u,i)x^i\)，转移就是 \(F_u(x)=a_ux\prod_{v\in son(x)}(F_v(x)+1)\)，这个 \(F_{i}(x)\) 是 \(n\) 次多项式。
朴素的做法是直接 FFT 做到 \(O(n^2\log n)\)。其实每次算完不需要 IDFT 回来，一直带着点值算，最后拉插插出多项式就行。要求的是前 \(k\) 项和，好像是先预处理一波就行了。
赛时：\(O(n^2\log n)\) 没跑过 \(n\leq 1000\)，果然是人傻常数大。
D
首先需要对 \(T=t_1+t_2+\ldots +t_n\) 去重：对于任意 \(i
考虑设 \(dp(i,c)\) 表示已经处理了 \(i\) 个串，下一位可以是 \(c\) 的方案数。
在后缀自动机上跑这个东西，设每个节点对应的串是 \([l,p],[l+1,p],\ldots,[r,p]\)，对于某一条出边字符 \(c\)，那相当于 \(\forall j\in [l,r]\)，\(dp(i,s_{i,j})\) 不能转移到 \(dp(i+1,c)\)，这个贡献需要减去，可以使用前缀和维护。
对于所有没有出现在整个字符串 \(s_i\) 里的，直接开一个 tag 维护就行了。
赛时：不会。
Day 10
杂题选讲-dxm
《联赛冲刺》
Comet OJ Contest #12 E
\(O(n^3)\) 做法和区间颜色很像，每个颜色维护一个 pre。这个题最暴力就是维护三个数的 pre，这样做是 \(n^4\) 的。发现不需要关心它到底是这三个数中的哪个，那么只需要统计与 \(i\) 位置不同的两个 pre，这样就是 \(n^3\) 了。
它的转移是 \(dp[i][j][k]\to dp[i+1][j][k],dp[i+1][i][k],dp[i+1][i][j]\)
把 \(dp[i]\) 看作一个矩阵，则后两个操作可以看作把一行或一列的值加到一个点上。如果没有限制，直接维护每一行每一列的值就可以 \(O(n)\) 转移。对于限制的处理，相当于是矩阵中只有一个矩形有数，注意到清零的位置一旦清零以后不会再有数了，所以直接暴力清空零的位置，维护行列和就做完了。
Bytedance/Moscow Workshops Programming Camp-2020 Online Contest G
从 DAG 上和 AC 自动机上同时跑，要求不能走到 AC 自动机上某些节点。
设 \(dp[i][u]\) 表示在 DAG 的节点 \(i\) 上，在 AC 自动机的节点 \(u\) 上的方案数。转移就是枚举 \(i\) 出边 \(j\)，\(dp[j][trans(u,j)]\)。
如果 \((i,u)\) 合法，那么要么 \(u\) 是根，要么 \(edge(fa_u,u)\) 是 \(i\)。状态数是线性的。
暴力转移复杂度是不对的，考虑 fail 树，固定了 \(i,j\)，把 \(nxt[v][j]\) 不为空的 \(v\) 表示成特殊点。
……下午再讲/se
The 2017 China Collegiate Programming Contest,Qinhuangdao Site J
注意到 \(maxdep(A\cdot B)=maxdep(A)+maxdep(B)\)
在 \(C\) 中找到深度最深的点，枚举 \(A\cdot X\) 还是 \(B\cdot Y\) 取到这个点。
假设是 \(A\cdot X\)，那么从这个点往上跳 \(maxdep(A)\) 之后，整个子树就是 \(X\)。在 \(C\) 中减去 \(A\cdot X\) 之后再做一遍就行了。
XX OpenCup Grand Prix of Korea K
（CTSC2018 暴力写挂）
对第一棵树点分治，有了一个分治中心，这样相当于最小化 \(dist(T_2,i,j)+d_i+d_j,i,j\in V\)。注意，并不需要限制 \(i,j\) 不在同一个子树内。
\(O(|V|)\) 复杂度计算上面那个的最小值：直接在第二棵树上建虚树，类似于求树的直径的方式，在 LCA 处求最小值即可。
如果每一层都排一个序，可以做到线性建虚树，\(1\log\)。
Petrozavodsk Summer 2019.Songyang Chen Contest 2 K
最小化掉血大小。大概就是考虑 \((a_i,b_i)\) 和 \((a_j,b_j)\)，对于 \(b_i\geq a_i\)，那么考虑：
如果 \(i\) 在 \(j\) 前面，\(\max(a_i,a_i-b_i+a_j)\)；
如果 \(j\) 在 \(i\) 前面，\(\max(a_j,a_j-b_j+a_i)\)。
同理如果 \(b_i
对于非菊花图，考虑每次拿出最优的 \(u\)，如果父亲已经拿了那么直接拿，否则和父亲合并。
\((a_1,b_1)\) 与 \((a_2,b_2)\) 合并得 \((\max(a_1,a_1-b_1+a_2),b_1-a_1+b_2-a_2+\max(a_1,a_1-b_1+a_2))\)。
使用 set 维护这个东西，支持删除合并插入即可。
Petrozavodsk Winter 2019. Petrozavodsk SU Contest. J
考虑容斥，选择一个集合 \(S\)，令 \(x= \sum_{i\in S}b_i-c+1\)
剩下的随便选 \(\binom{n-1-x+m}{m}\) 看作 \(x\) 的 \(m\) 次多项式 \(F(x)\)
对于满足 \(x\leq n-1\) 的所有集合 \(S\) 和次数 \(k\) 计算出 \((-1)^{|S|}(\sum_{i\in S}b_i-c+1)^k\)
枚举集合大小 \(a\) 要求 \(\sum_{i\in S}b_i\leq n-1-a(1-c)\)，把后面这个数写成 \(b\) 进制的形式，然后数位 dp。
设 \(dp[i][j][k][0/1]\)：考虑到 \(\geq i\) 的位数，已经容斥 \(j\) 个，所有情况 \(k\) 次方之和，当前是不是一个前缀。后面这个东西就二项式定理爆拆：
\[(x+b^i+1-c)^k=\sum_{p=0}^k \binom{k}{p} x^p (b_i+1-c)^{k-p} \]这样做的复杂度是 \(O(m^5)\)，无法通过。
预处理 \(f[i][j][k]\) 表示考虑 \(\leq i\) 的位数，容斥了 \(j\) 个，所有情况的 \(k\) 次方之和。\(O(m^4)\)。
枚举 \(a\) 之后，枚举第一个和前缀不同的地方，后面的部分调用 \(f\) 即可。
总复杂度是 \(O(m^4)\)。
XX OpenCup. Grand Prix of Korea. E
二分直径，希望找到一种断边方式使得直径 \(\leq d\)。
在圆方树上 dp，设 \(dp[u]\) 表示考虑子树内直径 \(\leq d\) 的情况下，子树内最深的点到 \(u\) 的距离最小是多少。
对一个环进行决策的时候就用之前那道基环树删边使直径最小的题的做法，维护前后缀几个信息的 \(\max\)，枚举断边之后，如果它的直径 \(\leq d\) 那么再用它去更新环上其他点的 \(dp\) 值，这样做下去就做完了。
XVIII OpenCup. Grand Prix of Romania. B
如果 \(A[1]\) 没有在 \(C[1][\ldots]\) 中出现过，那么所有列都确定了；
如果 \(A[1]=x\)，且 \(C[1][i]=x\) 的 \(i\) 有 \(c_x\) 个，那么其他列都确定了，其他列直接递归求解。确定的列做完之后需要把底下的行也处理出来，这部分复杂度是 \(O(nm)\)。
复杂度：
\[f(n,m)=f(n-1,0)+\sum_x f(n-1,c_x)+nm \]\(\sum_{c_x}\) 是 \(O(m)\) 级别的，总复杂度 \(O(n^2m)\)。
XIX OpenCup. Grand Prix of Gomel. M
不考虑可重集，就考虑 \(a+b+c+d=s\)
设 \(f(x)\) 为 \(a+b=x\) 的 \((a,b)\) 数量，是 \(O(n^2)\) 段的分段函数。
要计算 \(\sum_x{f(x)\cdot f(s-x)}\)，两个 \(O(n^2)\) 段的分段函数每一段分别相乘即可，这部分复杂度约是 \(O(n^2\log n)\)。
讨论可重集元素的相等不相等情况，分别做上面那些东西就行了。
XVIII Open Cup. Grand Prix of Ukraine. A
对于任意 \(k\) 个点，到这 \(k\) 个点的距离都 \(\leq L\) 的点构成一个连通块。每个连通块本来应该算一次。
发现对于任意非空的连通块，都有点数 \(-1=\) 边数
这样可以用点的贡献减去边的贡献就不会被算重。
对于每个点，到这个点距离 \(\leq L\) 的点有 \(c\) 个，贡献为 \(c^k\)；
对于每条边，到两端距离都 \(\leq L\) 的点有 \(c\) 个，贡献为 \(-c^k\)。
还有一种做法：在连通块最小的点处计算，也就是用每个点的贡献减去它的父边的贡献（这些贡献应该祖先来做）。
上面分析完之后直接点分治就做完了。
Petrozavodsk Summer 2019. MEX Foundation Contest. D
平衡树维护第一个操作
考虑如何 pushup
只要能够维护：
\(i
\(j
最小的 \(a_i\)
最大的 \(a_k\)
对于第一个东西，相当于是在右子树里查 \(>x\) 的最小的 \(a_j\)。已知当前节点不存在 \(i
Petrozavodsk Winter 2020. Greengs from Japan. K
每个格子 \(wh(i,j)\) 和 \(wv(i,j)\) 分别表示横着或竖着涂了白色，\(bh(i,j)\) 和 \(bv(i,j)\) 分别表示横着或竖着涂了黑色；
这四种的贡献是 \(a\)；如果 \(wh(i,j)\) 且 \(!wh(i,j+1)\)，会多 \(b\) 的贡献。其他同理。
如果某个格子最终是黑色，那么 \(!wh(i,j)\) 且 \(!wv(i,j)\)，若 \(!bh(i,j)\) 且 \(!bv(i,j)\) 会有 \(c\) 的贡献。
不可能 \(wh(i,j)\) 和 \(bh(i,j)\) 为真。
还有一些 \(wh,wv,bh,bv\) 之后还需要一次单点操作的，贡献为 \(c\)。
然后怎么建个图跑个最小割做完了。
Petrozavodsk Winter 2020. Greengs from Japan. F
大部分时间 \(x\neq a_i\)，\(i\to e_i\) 连基环树。
如果两次同一个 \(i\) 碰到 \(x=a_i\) 直接无解。所以每个 \(x=a_i\) 都只会出现一次，对于每个 \(i\) 维护 \(x=a_i\) 基础上下一次 \(x=a_j\) 的 \(j\)，直接从 \(i\) 跳到 \(j\)。
考虑树上的部分，设当前点是 \(i\)，第一个满足的点是 \(j\)，一开始在 \(c_i\)，满足 \(a_j=a_i+b_i+dist_i-dist_j\) 的深度最深的，相当于是 \(a_j+dist_j=a_i+b_i+dist_i\) 的，这个很好处理。
在环上的话，记环上所有边的和为 \(s\)，\(x-dist_i+ks=a_j-dist_j(k\in N _ * )\)，即
\[x-dist_i\equiv a_j-dist_j\pmod s \]注意一些细节就行了。
Petrozavodsk Winter 2020. 300iq Contest 3. H
跳了。
Japan Alumni Group Summer Camp 2019. Day3. F
Day 11
Test 9
point: \(20+95+30+20=165\)
rk: \(72\)
10:30 才起来，一个半小时就挂了 85pts，挂分之王就是我……
A
先把同颜色的连通块缩成一个点，这个可以使用并查集实现。考虑这棵相邻点颜色都不同的树，从某一个点出发，最长的路径就是从这个点出发需要的操作次数。
很自然的想到，只需要找到树的直径，从直径的中点出发一定是最优的，操作次数为 \(\lfloor\frac{\text{直径长度}}{2}\rfloor\)。
赛时：找树的直径写错了……挂成 20pts。
点击查看代码
#include
#include
#include
const int N=1e6+13;
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
inline char rdchar(){
char c=getchar();
for(;c!='R'&&c!='B';c=getchar());
return c;
}
struct edge{int u,v;}E[N];
int n,Fa[N];
bool col[N];
int Find(int x){return Fa[x]==x?x:Fa[x]=Find(Fa[x]);}
struct Edge{int v,nxt;}e[N<<1];
int h[N],tot,dep[N];
inline void add_edge(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==fa) continue;
dfs(v,u);
}
}
int main(){
n=rd();
for(int i=1;i<=n;++i) col[i]=(rdchar()=='R');
for(int i=1;i<=n;++i) Fa[i]=i;
for(int i=1;idep[rt]) rt=i;
memset(dep,0,sizeof dep);
dfs(rt,0);
for(int i=1;i<=n;++i)
if(Find(i)==i&&dep[i]>dep[rt]) rt=i;
printf("%d\n",dep[rt]/2);
return 0;
}
B
首先考虑对于每一个位置，一定是先赋值、再加、最后乘。加的话，可以认为一定是先加大的，再加小的，赋值也相当于是加的操作，这样对于每个位置，使用某个加法操作之前已经使用的操作是固定的，假设在这之前这个位置的数为 \(x\)，那么可以认为这次加法操作 \(+y\) 相当于乘上了 \(\frac{x+y}{x}\)。
这样把所有操作都换成乘法之后，就可以直接对乘的数从大到小排序选前 \(m\) 个即可。
注意统计答案的时候，应该把它们重新按照先加再乘的方式排序，然后直接模拟。不能直接乘 \(\frac{x+y}{y}\)，因为这个 \(y\) 有可能会加到 \(10^9+7\)，它没有逆元，最后就会乘 \(0\) 导致答案错误。
赛时：没有想到最后一点，挂掉了 5pts。
点击查看代码
#include
#include
#include
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
typedef long long ll;
const int N=3e5+13,mod=1e9+7;
inline int qpow(int a,int k){int s=1;for(;k;k>>=1,a=(ll)a*a%mod)if(k&1)s=(ll)s*a%mod;return s;}
int n,m,q,a[N];
struct Node{int op,p;ll up,dn;}b1[N],b2[N],b3[N];
inline bool cmp1(const Node &a,const Node &b){return a.p!=b.p?a.pb.up;}
inline bool cmp2(const Node &a,const Node &b){return (__int128)a.up*b.dn>(__int128)a.dn*b.up;}
inline bool cmp3(const Node &a,const Node &b){
if(a.op!=b.op) return a.op(__int128)a.dn*b.up;
}
int main(){
// freopen("1.in","r",stdin);
n=rd(),m=rd(),q=rd();
for(int i=1;i<=n;++i) a[i]=rd();
int cnt1=0,cnt2=0,cnt3=0;
for(int i=1;i<=m;++i){
int op=rd(),pos=rd(),val=rd();
if(op==1&&a[pos]1) b3[++cnt3]=(Node){op,pos,val,1};
}
std::sort(b1+1,b1+cnt1+1,cmp1);
for(int i=1;i<=cnt1;++i){
if(b1[i].p==b1[i-1].p) continue;
int tmp=b1[i].up-a[b1[i].p];
b2[++cnt2]=(Node){1,b1[i].p,tmp,1};
}
std::sort(b2+1,b2+cnt2+1,cmp1);
ll sum=0;
for(int i=1;i<=cnt2;++i){
if(b2[i].p!=b2[i-1].p) sum=a[b2[i].p];
ll tmp=b2[i].up;
b2[i].dn=sum;
sum+=tmp;
}
for(int i=1;i<=cnt3;++i) b3[i].up--;
for(int i=1;i<=cnt2;++i) b3[++cnt3]=b2[i];
std::sort(b3+1,b3+cnt3+1,cmp2);
int l=std::min(cnt3,q);
std::sort(b3+1,b3+l+1,cmp3);
for(int i=1;i<=l;++i){
int x=b3[i].p;
if(b3[i].op<=2) a[x]=(a[x]+b3[i].up)%mod;
else a[x]=(ll)a[x]*(b3[i].up+1)%mod;
}
int ans=1;
for(int i=1;i<=n;++i) ans=(ll)ans*a[i]%mod;
printf("%d\n",ans);
return 0;
}
C
考虑一种构造方案：放弃掉 \(n\)，令 \(A_n=1\)，底下每个 \(i\) 都选 \(i+1\)，这样能够选到的 \(s\) 已经是最大的了，即 \(\frac{n(n-1)}{2}\)。考虑对于所有 \(s\leq\frac{n(n-1)}{2}\)，构造一种通法：
设 \(s=1+\sum_{i\in G}(G\subset \{2,3,\ldots,n-1\})\)，那么可以这样构造：
\(A_n=1,A_i=i(i=2,3,\ldots,n-1,i\not\in G)\)
对于所有 \(i\in (G\cup \{1\})\)，取 \(G\cup \{n\}\) 中剩余的最大的数，这样这些数就都能选到了。然后就做完了。
赛时：不会，打了 \(n\leq 3\) 和 \(s\leq 2\) 的 30pts。
点击查看代码
#include
#include
typedef long long ll;
const int N=1e6+13;
int ans[N];
int main(){
int n;ll s;
scanf("%d%lld",&n,&s);
if(s>(ll)n*(n-1)/2) return puts("SPFA is dead!"),0;
if(!s){
for(int i=1;i<=n;++i) printf("%d\n",i);
return 0;
}
if(n==1) return puts("SPFA is dead!"),0;
if(s==2){
if(n<=2) return puts("SPFA is dead!"),0;
puts("3"),puts("1"),puts("2");
for(int i=4;i<=n;++i) printf("%d\n",i);
return 0;
}
if(s==(ll)n*(n-1)/2-1){
if(n&1){
puts("3"),puts("1");
for(int i=3;is) ans[p]=p,--p;
ans[p]=pre,pre=p,s-=p,--p;
}
ans[1]=pre;
while(p>1) ans[p]=p,--p;
for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
return 0;
}
D
不相交的路径比较难算，考虑算相交的路径：
两条路径 \((a,b),(c,d)\) 相交有两种可能，\(lca(a,b)\) 在路径 \(c,d\) 上或 \(lca(c,d)\) 在路径 \((a,b)\) 上。相当于是要求以某个点为 \(lca\) 且长度为 \(p\) 的路径条数和经过某个点且长度为 \(q\) 的路径条数。
Day 12
Test 10
point: \(0+0+20+0=20\)
rk: \(123\)
挂了 200pts 可还行。
A
首先求出杀手到每个点的最短路 \(d_u\)。
二分答案 \(x\)，直接用 dij 求人出发的最短路，其中如果在某个点 \(dist_u>xd_u\)，那么不能走到这个点，也就是不能更新其他点。最后判断能不能走到终点即可。
注意只跑一遍 dij，每次二分答案 ban 掉 \(dist_u>xd_u\) 的点判联通是不对的，因为有可能某些 \(dist_u\) 取的路径上的点被 ban 掉了。
赛时：因为写了第二种错误做法，\(40\to 0\)。\(40\) 是因为 dij 边权用的 double 类型常数过大。
点击查看代码
#include
#include
#include
#include
#include
#define mp std::make_pair
#define fi first
#define se second
typedef std::pair pii;
const double eps=1e-6;
inline int rd(){
int res=0,flag=1;char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')flag=-1;
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res*flag;
}
const int N=1e4+13,M=5e5+13;
struct Edge{int v,w,nxt;}e[M<<1];
int n,m,ss,tt,h[N],tot,distp[N],dist[N];
bool vis[N];
inline void add_edge(int u,int v,int w){e[++tot]=(Edge){v,w,h[u]};h[u]=tot;}
inline void dijkstra1(int st){
std::priority_queue,std::greater > q;while(!q.empty())q.pop();
memset(distp,0x3f,sizeof distp);memset(vis,0,sizeof vis);
distp[st]=0,q.push(mp(0,st));
while(!q.empty()){
int u=q.top().se;q.pop();
if(vis[u]) continue;vis[u]=1;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(distp[v]>distp[u]+w){
distp[v]=distp[u]+w;
q.push(mp(distp[v],v));
}
}
}
}
inline bool check(double k){
std::priority_queue,std::greater > q;while(!q.empty())q.pop();
memset(dist,0x3f,sizeof dist);memset(vis,0,sizeof vis);
dist[ss]=0,q.push(mp(dist[ss],ss));
while(!q.empty()){
int u=q.top().se;q.pop();
if(vis[u]) continue;vis[u]=1;
if(dist[u]>k*distp[u]-eps){
if(u==tt) return 0;
continue;
}
if(u==tt) return 1;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
q.push(mp(dist[v],v));
}
}
}
return 0;
}
int main(){
// freopen("data_a.in","r",stdin);
// freopen("data_a.ans","w",stdout);
// double S=clock();
n=rd(),m=rd();
for(int i=1;i<=m;++i){
int u=rd(),v=rd(),w=rd();
add_edge(u,v,w),add_edge(v,u,w);
}
ss=rd();int p=rd();tt=rd();
if(ss==p||tt==p) return puts("-1"),0;
if(ss==tt) return puts("0.000000"),0;
dijkstra1(p);
// double T=clock();printf("time:%.0lfms\n",T-S);
double l=0,r=1e6;
if(!check(r)) return puts("-1"),0;
for(int T=1;T<=45;++T){
double mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}
printf("%.6lf\n",l);
// double TT=clock();printf("time:%.0lfms\n",TT-S);
return 0;
}
B
直接建反向图，只把在 \(a_i,b_i\) 中出现的点拿出来，排序之后相邻点建权值为编号差的边，所有边都反向之后从终点 \((1)\) 开始跑最短路，最后 lower_bound 或者双指针更新答案即可。
赛时：使用双指针但是没有对询问数组排序……我是 sb。
点击查看代码
#include
#include
#include
#include
#include
#define mp std::make_pair
#define fi first
#define se second
typedef std::pair pii;
inline int rd(){
int res=0,flag=1;char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')flag=-1;
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res*flag;
}
const int N=1e6+13,M=2e5+13;
struct edge{int u,v,w;}E[M];
int n,m,a[N],b[M];
struct Edge{int v,w,nxt;}e[M<<1];
int h[M],tot,dist[M];
bool vis[M];
inline void add_edge(int u,int v,int w){e[++tot]=(Edge){v,w,h[u]};h[u]=tot;}
inline void dijkstra(int st){
std::priority_queue,std::greater > q;while(!q.empty())q.pop();
memset(dist,0x3f,sizeof dist);
dist[st]=0,q.push(mp(0,st));
while(!q.empty()){
int u=q.top().se;q.pop();
if(vis[u]) continue;vis[u]=1;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
q.push(mp(dist[v],v));
}
}
}
}
int main(){
n=rd(),m=rd();
for(int i=1;i<=n;++i) a[i]=rd();
bool flagone=0;int cnt=0;
for(int i=1;i<=m;++i){
E[i].u=rd(),E[i].v=rd(),E[i].w=rd();
b[++cnt]=E[i].u,b[++cnt]=E[i].v;
if(E[i].u==1||E[i].v==1) flagone=1;
}
if(!flagone) b[++cnt]=1;
std::sort(b+1,b+cnt+1);
cnt=std::unique(b+1,b+cnt+1)-b-1;
for(int i=1;i<=m;++i){
int u=std::lower_bound(b+1,b+cnt+1,E[i].u)-b;
int v=std::lower_bound(b+1,b+cnt+1,E[i].v)-b;
add_edge(v,u,E[i].w);
}
for(int i=1;i C
首先可以根据每个红绿灯到起点的距离 \(\bmod (a+b)\) 建立线段树，通过区间最小值求出任意时间出发的汽车遇到的第一个红灯。
同样运用这种方式，设 \(f_i\) 表示在 \(i\) 位置遇到红灯之后到终点需要的时间，从后往前动态插入的过程中每次查询第一个红灯的位置 \(k\)，用 \(f_k\) 更新当前的 \(f\) 即可。
赛时：20pts暴力。
D
Day 13
Test 11
point: \(100+100+100+60=360\)
rk: \(15\)
A
四个因子说明有不超过 \(2\) 个质因子，如果只有一个 \(p\)，那么这个数是 \(p^3\)；如果有两个那么是 \(pq\)，其中 \(p\geq n+1,q\geq n+p\)。显然第二种比第一种都小。所以先预处理出质数来，然后每次 lower_bound 两次就完了。
赛时：过了。
点击查看代码
const int N=3e5+13;
int prm[N],m;
int main(){
//file();
Math::Onshai(prm,m,300000);
int T;read(T);while(T--){
int n;read(n);
int x=std::lower_bound(prm+1,prm+m+1,n+1)-prm;x=prm[x];
int y=std::lower_bound(prm+1,prm+m+1,n+x)-prm;y=prm[y];
println((ll)x*y);
}
return 0;
}
B
猜测答案能够达到理论上界 \(\lfloor\frac{n}{2}\rfloor\)。考虑如何构造。
对于偶数：增量构造，从 \(n-2\) 的方案推广到 \(n\) 的方案。对于已经有的所有生成树，在第 \(i\) 棵连 \(2i-1\to n-1,2i\to n\)；再新建一棵树，连 \(2i-1\to n,2i\to n-1,n-1\to n\) 就完了。
对于奇数：把最后一个点搞出来在第 \(i\) 棵树接到第 \(i\) 个点上。
赛时：过了，我的做法是考虑对偶数构造一个“之”字形，第 \(i\) 棵树从 \(i\) 开始，每次 \(+1,-2,+3,\ldots\)，这样一定能连出一些边不相交的树。
点击查看代码
int main(){
//file();
int T;read(T);for(int test=1;test<=T;++test){
int n;read(n);bool flag=(n&1);if(n&1) --n;
print("Case #"),print(test),print(": "),println(n>>1);
for(int i=0;i<(n>>1);++i){
int x=i,ad=1,f=1;
while(adC
二分答案之后可以直接贪心，把子树和都拿出来排序，从大到小断边直到和 \(\leq mid\)。\(O(n\log n\log v)\)。
赛时：过了。
点击查看代码
inline void clear(int *a,int n){for(int i=1;i<=n;++i)a[i]=0;}
const int N=1e5+13;
struct Edge{int v,nxt;}e[N<<1];
int n,m,a[N],h[N],tot,c[N];
ll rest[N];
inline void add_edge(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
void dfs(int u,int fa,ll lim){
std::vector son;son.clear();ll sum=a[u];
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==fa) continue;
dfs(v,u,lim);c[u]+=c[v],sum+=rest[v],son.push_back(rest[v]);
}
std::sort(son.begin(),son.end(),std::greater());
int j=0,l=son.size();
while(jlim) ++c[u],sum-=son[j],++j;
rest[u]=sum;
}
inline bool check(ll lim){
clear(c,n);
dfs(1,0,lim);
return c[1]>1;
if(check(mid)) R=mid;
else L=mid+1;
}
print("Case #"),print(test),print(": "),println(L);
}
return 0;
}
D
主席树维护 hash 求 lcp。然后用可持久化分块数组维护这个东西可以做到 \(2\log\)。很离谱。
赛时：\(O(n^3)\) 暴力打了 60pts。没人 A 掉这题。
Day 14
Test 12
point: \(100+0+0+0=100\)
rk: \(34\)
B 码了 20k 最后没调出来可还行。
A
枚举直径中点，对于直径长度 \(L\)，那么相当于是每个子树都可以选深度不超过 \(\frac{L}{2}\) 的点，并且钦定必须要选 \(2\) 个在不同子树并且深度都是 \(\frac{L}{2}\) 的点。这个可以直接树形 dp。
赛时：写了个奇怪换根 dp 写了俩小时……不过过了。
点击查看代码
const int N=2000+13;
struct edge{int u,v;}E[N];
struct Edge{int v,nxt;}e[N<<1];
int n,h[N],tot,dep[N];
int f[N][N],pr[N][N],dp[N][N],g[N][N],ans[N],two[N];
inline void init(){
two[0]=1;
for(int i=1;i<=n;++i) two[i]=two[i-1]*2%mod;
}
inline void add_edge(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
void dfs1(int u,int fa){
f[u][0]=1;dep[u]=dep[fa]+1;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==fa) continue;
dfs1(v,u);
for(int j=0;j>1)-1]]%mod;
if((k>>1)-2>=0) cnt=(cnt+g[v][(k>>1)-2])%mod;
}
int res=(all-two[cnt]+mod)%mod;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
res=(res-(two[dp[v][(k>>1)-1]]-1)*(ll)two[cnt]%mod+mod)%mod;
}
ans[k]=(ans[k]+res)%mod;
}
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
for(int k=0;k<=n;++k) dp[v][k]=tmp[v][k];
}
}
for(int j=1;jdep[v]) swap(u,v);
for(int k=0;k<=n;++k) tmpu[k]=dp[u][k],tmpv[k]=dp[v][k];
for(int k=0;k<=n;++k) dp[u][k]=pr[v][k],dp[v][k]=f[v][k];
g[u][0]=dp[u][0];
for(int j=1;j<=n;++j) g[u][j]=(g[u][j-1]+dp[u][j])%mod;
g[v][0]=dp[v][0];
for(int j=1;j<=n;++j) g[v][j]=(g[v][j-1]+dp[v][j])%mod;
for(int k=1;k>1]],allv=two[g[v][k>>1]],cnt=0;
if((k>>1)-1>=0) cnt=(g[u][(k>>1)-1]+g[v][(k>>1)-1])%mod;
int res=((ll)allu*allv%mod-two[cnt]+mod)%mod;
res=(res-(two[dp[u][k>>1]]-1)*(ll)two[cnt]%mod+mod)%mod;
res=(res-(two[dp[v][k>>1]]-1)*(ll)two[cnt]%mod+mod)%mod;
ans[k]=(ans[k]+res)%mod;
}
for(int k=0;k<=n;++k) dp[u][k]=tmpu[k],dp[v][k]=tmpv[k];
}
int q;read(q);
while(q--){int x;read(x);println(ans[x]);}
return 0;
}
B
考虑把两个马的坐标设为一个状态，相邻状态建边，由于相邻状态四个坐标加起来的奇偶性总是不同的，所以这个图是一个二分图。
现在就是要在二分图上做博弈。有一个结论是一定在二分图最大匹配上的点必胜，否则必败（有一种最大匹配不包含此点）。求法就是先用网络流跑出来一个最大匹配，对于左边集合的点，对所有的匹配边连左到右的有向边，对非匹配边连右到左的有向边，从每个左边非匹配的点开始跑 dfs，所有能跑到的点都是必败态（大概就是能跑到的点都可以从另外一边增广导致这个点不在最大匹配上）。右边集合的点同理。然后就直接统计必胜态状态数就行了。
还有一个细节是两个马是一样的，好像可以直接把答案除以二，也可以钦定每个状态的 \((x1,y1)<(x2,y2)\)，不过转移很麻烦。
赛时：考场上狂码 500+ 行（带缺省源）但是没调出来，原因是 Maxflow 里的 tot 和原图的 tot 搞混了……
点击查看代码
namespace Maxflow{
const int N=400000+13;
struct Edge{int u,v,w,nxt;}e[N*5];
int n,m,s=N-3,t=N-2,h[N],tot=1;
inline void clear(){h[s]=h[t]=0;tot=1;}
inline void add(int u,int v,int w){
e[++tot]=(Edge){u,v,w,h[u]};h[u]=tot;
e[++tot]=(Edge){v,u,0,h[v]};h[v]=tot;
}
int dep[N],cur[N];
bool vis[N];
inline bool bfs(){
memset(dep,0x7f,sizeof(dep));
memcpy(cur,h,sizeof(h));
memset(vis,0,sizeof(vis));
std::queueq;
q.push(t),dep[t]=0,vis[t]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i^1].w;
if(!vis[v]&&w) dep[v]=dep[u]+1,vis[v]=1,q.push(v);
}
}
return vis[s];
}
ll dfs(int u,ll minw){
if(u==t||!minw) return minw;
ll f,flow=0;
for(int &i=cur[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(dep[u]==dep[v]+1&&(f=dfs(v,min(minw,(ll)w)))){
minw-=f,flow+=f,e[i].w-=f,e[i^1].w+=f;
if(!minw) break;
}
}
return flow;
}
inline ll dinic(){
ll flow=0;
while(bfs()) flow+=dfs(s,INF);
return flow;
}
}
const int N=17;
int dx[8]={-2,-1,1,2,2,1,-1,-2},dy[8]={-1,-2,-2,-1,1,2,2,1};
int n,m,k;
bool no[N][N];
inline bool chk(int x,int y){return x>=1&&y>=1&&x<=n&&y<=n;}
namespace Sub1{
const int M=400000+13;
struct Edge{int v,nxt;}e[M<<1];
int h[M],tot=1;
inline void add_edge(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
int num[N][N],col[M],cc;
std::vector point,g[M];
bool vis[M],is[M];
void dfs(int u,int c){
col[u]=c;point.pb(u);
if(c==1) Maxflow::add(Maxflow::s,u,1);
else Maxflow::add(u,Maxflow::t,1);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(!col[v]){
is[i>>1]=1;
if(c==1) Maxflow::add(u,v,1);
else Maxflow::add(v,u,1);
dfs(v,3-c);
}
else if(!is[i>>1]){
is[i>>1]=1;
if(c==1) Maxflow::add(u,v,1);
else Maxflow::add(v,u,1);
}
}
}
void dfs2(int u,int c){
vis[u]=1;if(col[u]==c) ++cc;
for(auto v:g[u])
if(!vis[v]) dfs2(v,c);
}
inline void solve(){
int cnt=0;
for(int x=1;x<=n;++x){
for(int y=1;y<=n;++y){
if(no[x][y]) continue;
num[x][y]=++cnt;
}
}
for(int x=1;x<=n;++x){
for(int y=1;y<=n;++y){
if(no[x][y]) continue;
for(int i=0;i<4;++i){
int nx=x+dx[i],ny=y+dy[i];
if(chk(nx,ny)&&!no[nx][ny]) add_edge(num[x][y],num[nx][ny]),add_edge(num[nx][ny],num[x][y]);
}
}
}
int ans=0;
for(int i=1;i<=cnt;++i){
if(!col[i]){
dfs(i,1);int tmp=point.size(),res=Maxflow::dinic();
if(res*2==tmp) ans+=tmp;
else{
cc=0;std::vector now1,now2;now1.clear(),now2.clear();
for(int i=2;i<=Maxflow::tot;i+=2){
int u=Maxflow::e[i].u,v=Maxflow::e[i].v,w=Maxflow::e[i].w;
if(u==Maxflow::s){
if(w) now1.pb(v);
continue;
}
if(v==Maxflow::t){
if(w) now2.pb(u);
continue;
}
if(w) g[u].pb(v);
else g[v].pb(u);
}
for(auto u:now1)
if(!vis[u]) dfs2(u,1);
for(auto u:point) g[u].clear(),vis[u]=0;
for(int i=2;i<=Maxflow::tot;i+=2){
int u=Maxflow::e[i].u,v=Maxflow::e[i].v,w=Maxflow::e[i].w;
if(u==Maxflow::s||v==Maxflow::t) continue;
if(w) g[v].pb(u);
else g[u].pb(v);
}
for(auto u:now2)
if(!vis[u]) dfs2(u,2);
for(auto u:point) g[u].clear(),vis[u]=0;
ans+=tmp-cc;
}
for(auto u:point) Maxflow::h[u]=0,vis[u]=0;
Maxflow::clear();point.clear();
}
}
println(ans);
}
}
namespace Sub2{
const int M=4000000+13;
struct Edge{int v,nxt;}e[M<<1];
int h[M],tot=1;
inline void add_edge(int u,int v){e[++tot]=(Edge){v,h[u]};h[u]=tot;}
int num[N][N][N][N],col[M],cc;
std::vector point,g[M];
bool vis[M],is[M];
void dfs(int u,int c){
col[u]=c;point.pb(u);
if(c==1) Maxflow::add(Maxflow::s,u,1);
else Maxflow::add(u,Maxflow::t,1);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(!col[v]){
is[i>>1]=1;
if(c==1) Maxflow::add(u,v,1);
else Maxflow::add(v,u,1);
dfs(v,3-c);
}
else if(!is[i>>1]){
is[i>>1]=1;
if(c==1) Maxflow::add(u,v,1);
else Maxflow::add(v,u,1);
}
}
}
void dfs2(int u,int c){
vis[u]=1;if(col[u]==c) ++cc;
for(auto v:g[u])
if(!vis[v]) dfs2(v,c);
}
inline void solve(){
int cnt=0;
for(int x1=1;x1<=n;++x1){
for(int y1=1;y1<=n;++y1){
if(no[x1][y1]) continue;
for(int x2=x1;x2<=n;++x2){
for(int y2=1;y2<=n;++y2){
if(no[x2][y2]) continue;
if(x1==x2&&y1==y2) continue;
if(x2==x1&&y2nx2||(nx1==nx2&&ny1>ny2)) swap(nx1,nx2),swap(ny1,ny2);
add_edge(num[x1][y1][x2][y2],num[nx1][ny1][nx2][ny2]);
add_edge(num[nx1][ny1][nx2][ny2],num[x1][y1][x2][y2]);
}
for(int i=0;i<4;++i){
int nx1=x1,ny1=y1,nx2=x2+dx[i],ny2=y2+dy[i];
if(!chk(nx2,ny2)||no[nx2][ny2]||(nx1==nx2&&ny1==ny2)) continue;
if(nx1>nx2||(nx1==nx2&&ny1>ny2)) swap(nx1,nx2),swap(ny1,ny2);
add_edge(num[x1][y1][x2][y2],num[nx1][ny1][nx2][ny2]);
add_edge(num[nx1][ny1][nx2][ny2],num[x1][y1][x2][y2]);
}
}
}
}
}
int ans=0;
for(int i=1;i<=cnt;++i){
if(!col[i]){
dfs(i,1);int tmp=point.size(),res=Maxflow::dinic();
if(res*2==tmp) ans+=tmp;
else{
cc=0;std::vector now1,now2;now1.clear(),now2.clear();
for(int i=2;i<=Maxflow::tot;i+=2){
int u=Maxflow::e[i].u,v=Maxflow::e[i].v,w=Maxflow::e[i].w;
if(u==Maxflow::s){
if(w) now1.pb(v);
continue;
}
if(v==Maxflow::t){
if(w) now2.pb(u);
continue;
}
if(w) g[u].pb(v);
else g[v].pb(u);
}
for(auto u:now1)
if(!vis[u]) dfs2(u,1);
for(auto u:point) g[u].clear(),vis[u]=0;
for(int i=2;i<=Maxflow::tot;i+=2){
int u=Maxflow::e[i].u,v=Maxflow::e[i].v,w=Maxflow::e[i].w;
if(u==Maxflow::s||v==Maxflow::t) continue;
if(w) g[v].pb(u);
else g[u].pb(v);
}
for(auto u:now2)
if(!vis[u]) dfs2(u,2);
for(auto u:point) g[u].clear(),vis[u]=0;
ans+=tmp-cc;
}
for(auto u:point) Maxflow::h[u]=0,vis[u]=0;
Maxflow::clear();point.clear();
}
}
println(ans);
}
}
int main(){
//file();
read(n),read(m),read(k);
for(int i=1;i<=k;++i){
int x,y;read(x),read(y);
no[x][y]=1;
}
if(m==1) Sub1::solve();
else Sub2::solve();
return 0;
}
C
如果一条边的边权 \(>3\) 种，那么可以直接变成 \(3\) 种，因为已经可以保证和两边都不相同。直接考虑倍增，设 \(dp_{i,j,x,y}\) 表示从 \(i\) 开始跳 \(2^j\) 步，开始边权为 \(x\)，结束边权为 \(y\) 的最大边权改变数量，由于每条边边权种类最多只有 \(3\)，所以大概就过了。
赛时：不会，暴力 40pts 没时间打了。
D
首先有一个结论是在最小字典序的地方断环成链一定不会更劣，这个可以使用最小表示法解决。接下来如果没有循环节，直接后缀排序之后取前 \(k\) 小即可；如果有循环节，每一次取每个循环节都要取，所以只需要对一个循环节取最小的前 \(\lceil\frac{k}{\text{循环节个数}}\rceil\) 个就行了。
赛时：不会，不给暴力分，不会后缀排序，字符串知识荒漠……
Day 15
Test 13
point: \(100+20+10+20=150\)
rk: \(16\)
被人举报就离谱。
A
考虑一个暴力：枚举 \(and\) 和，设其为 \(t\)，拿出所有 \(x\subseteq t\) 的数出来跑异或背包，最后把异或和为 \(t\) 的方案数累加。有正确性是因为，异或和是 \(t\)，说明了个数一定是奇数；其他位置都是 \(0\)，说明一定至少有一个数这一位是 \(0\)，故这些数的 \(and\) 也一定是 \(t\)。
这样的复杂度是 \(O(n4^{13})\) 的。但是这个做法只能搞出 \(t>0\) 的，对于 \(t=0\) 的，异或和是 \(0\) 的集合大小不一定是奇数，所以实际上求出来的是 \(xor=0,and\supseteq 0\) 的个数。对于每个 \(t\) 都可以求出 \(xor=0,and\supseteq t\) 的数的个数。这样就可以容斥了：设 \(f_0\) 表示答案，\(g_t\) 表示 \(xor=0,and\supseteq t\) 的数的个数，那么有 \(f_0=\sum_{t}(-1)^{popcount(t)}g_t\)，这个可以在上面跑完背包之后搞出来。
继续考虑优化，发现上面那个背包跑的时候，已经钦定了选的所有数在 \(t\) 的所有 \(1\) 位都是 \(1\)，那么我们考虑把这些位扔掉，加入一个新的位置表示这些位，假设直接加在最低位，那么跑完背包之后异或出 \(1\) 的方案数就可以累计了。这个东西复杂度变成了 \(nv\sum_{i=0}^v popcount(v)=n3^{13}\)，可以通过。
还有一个更 nb 的 \(O(nv\log v)\) 做法，大概就是把上面那个东西用线性基优化一下，就插不进去的随便选，插进去的有唯一方式。
赛时：过了。
点击查看代码
const int N=50+13,M=(1<<13)+13;
int n,a[N],b[N];
ll f[M],g[M];
int main(){
//file();
read(n);
for(int i=1;i<=n;++i) read(a[i]);
ll ans=0,res=0;
for(int t=0;t<(1<<13);++t){
int m=0,c=0;
for(int j=0;j<13;++j) c+=!((t>>j)&1);if(t)++c;
for(int i=1;i<=n;++i){
bool ok=1;
for(int j=0;j<13;++j){
if(!((t>>j)&1)) continue;
if(!((a[i]>>j)&1)){ok=0;break;}
}
if(ok){
int x=0;
for(int j=0;j<13;++j){
if((t>>j)&1) continue;
x=(x<<1)+((a[i]>>j)&1);
}
if(t) b[++m]=((x<<1)|1);
else b[++m]=x;
}
}
for(int i=1;i<(1<B
考虑树的情况：从一个虚点向所有点连边，这样对于每个导出子图，生成树个数都等于这个子图的权值（每个连通块挑一个点和虚点相连）。基环树就是先用状压 dp 求出每个子图是环的方案数，然后把这个子图缩成一个点跑上面那个生成树计数就行了。生成树计数可以使用 Matrix-tree 定理做。
赛时：不会，拿了最低的 20pts 暴力。
C
考虑如果 \(\prod a_i>x\)，所有排列都可行。否则，只有 \(O(\log x)\) 个可用的 \(a_i\)（所有 \(a_i=1\) 的贡献都可以简单用组合数计算）。对于模数也是一样，由于操作过程中 \(x\) 不会变大，所以一开始就只有 \(O(x)\) 个有用的模数。
设 \(dp_{S,x}\) 表示选的除法集合是 \(S\)，当前数是 \(x\) 的方案数，看起来状态很多，其实把除数相同的压一压，然后 \(x\) 也不是每个都是 \(O(10000)\)，除一次就会降很多，所以复杂度是能冲过去的。每次除了一个之后，假设 \(x\to x'\)，那么所有取模的数在 \((x',x]\) 范围内的都没用了，乘个组合数就完了。
赛时：看错部分分性质了，\(20\to 10\)。
D
首先考虑 \(x_1=x_2\)，扫描线从左到右扫左端点，用单调栈维护每个 \(\max\) 和 \(\min\) 值相同的段，扫描线的时候动态维护 \(\max\cdot\min\) 的值，询问离线之后查就行了。
对于一般情况，考虑在 \(x\) 维上进行差分，这样只需要算线段树每个节点的历史值的和。再开一个标记 \(s_i\) 维护历史和，扫描线移动一次就加一个标记，表示 s_i+=max*min，然后 pushdown 的时候顺便维护一下这个标记就行了。
赛时：20pts 暴力。
Day 16
Test 14
point: \(100+0+60+0=160\)
rk: \(49\)
跑操比赛耽误了一会，不然还是能多拿点分。这场应该顺序开题的！
A
考虑从 \(i\) 到 \(i+1\) 的期望时间，设 \(E_i\) 表示从 \(i\) 开始到结尾的期望时间，有 \(E_{i+1}=\frac{E_i+1}{p_i}\)，这相当于很多一次函数复合起来。考虑差分，先求出前缀的一次函数复合的 \(k,b\)，每次询问一对 \((x,y)\)，用 \(y\) 的前缀减去 \(x\) 的前缀的贡献，这个就是复合的逆运算，总的复杂度加上逆元是 \(O(n\log p)\)。好像可以线性求一些数的逆元然后总复杂度去掉 \(\log\)。
赛时：过了。听过机房还有用线段树维护一次函数复合的，不过卡卡常也能过去。
点击查看代码
const int N=1e6+13;
int n,q,k[N],b[N];
int main(){
//file();
read(n),read(q);
int nowk=1,nowb=0;
for(int i=1;i<=n;++i){
int x;read(x);x=invv(x);
nowk=(ll)nowk*x%mod,nowb=((ll)nowb*x+x)%mod;
k[i]=nowk,b[i]=nowb;
}
while(q--){
int x,y;read(x),read(y);
int nowk=(ll)k[y]*invv(k[x-1])%mod,nowb=(b[y]-(ll)nowk*b[x-1]%mod+mod)%mod;
println(nowb);
}
return 0;
}
B
暴力就是说，枚举第一个字符的匹配位置，然后往后做 dp，把不合法的情况减去，复杂度 \(O(n^2m)\)。运用数据随机的性质，第一个位置 \(s_i=t_1\) 的位置 \(i\) 期望只有 \(O(\frac{n}{26})\) 个，同理，在 dp 的时候，如果 dp 到第 \(i\) 位，那么 \(s_i=t_j\) 的 \(j\) 也只有 \(O(\frac{m}{26})\) 个。所以这个暴力的期望复杂度是 \(O(\frac{n^2m}{26^2})\) 的，卡卡常是能过去的……
上面那个不是正常做法，正常做法是考虑分治，每次对 \(i_1\in[l,mid],i_m\in[mid+1,r]\) 的不合法情况进行处理，处理方式枚举 \(mid\) 对应的 \(t\) 中断点，从中间往两边跑个 dp，前缀和优化一下可以做到 \(O(nm^2\log n)\)。然后数据随机，所以跑的时候可以乘个 \(\frac{1}{26}\) 就过去了。
赛时：暴 力 写 挂。
点击查看代码
const int N=1e5+13,M=50+13,K=26;
int dp[M],n,m,k,pos[K][N],lim[K];
char s[N],t[M];
int main(){
//file();
read(n),read(m),read(k);
read(s+1),read(t+1);
dp[0]=1;
for(int i=1;i<=n;++i)
for(int j=m;j;--j)
if(s[i]==t[j]) dp[j]=(dp[j]+dp[j-1])%mod;
int ans=dp[m];
memset(dp,0,sizeof dp);
dp[0]=1;
for(int i=n-k+1;i<=n;++i)
for(int j=m;j;--j)
if(s[i]==t[j]) dp[j]=(dp[j]+dp[j-1])%mod;
ans=(ans-dp[m]+mod)%mod;
for(int i=m;i;--i) pos[t[i]-'a'][++lim[t[i]-'a']]=i;
for(int st=1;st<=n-k;++st){
if(s[st]!=t[1]) continue;
memset(dp,0,sizeof dp);
dp[1]=1;int tmp=0;
for(int i=st+1;i<=st+k-1;++i){
for(int j=1;j<=lim[s[i]-'a'];++j){
int x=pos[s[i]-'a'][j];
dp[x]=(dp[x]+dp[x-1])%mod;
}
}
ans=(ans-dp[m]+mod)%mod;
}
println(ans);
return 0;
}
C
《NOIP模拟赛》
当 \(n>2\) 时，若 \(n\) 有原根，则 \(f(n)=n-1\)，否则 \(f(n)=1\)。
证明：
当 \(n\) 有原根 \(g\) 时，\(n\) 以内所有与 \(n\) 互质的数可以表示为 \(g^0,g^1,\ldots,g^{\varphi(n)-1}\bmod n\)。于是
\[f_n=\prod_{i=0}^{\varphi(n)-1}g^i\equiv g^{\frac{\varphi(n)(\varphi(n)-1)}{2}}\pmod n \]哈哈，我写的是分段打表。
点击查看代码
const int N=1e5+13;
int prm[N],m;
ll n;
int table1[]={0,595990216,323642777,420657481,575190934,752947895,802015654,27457083,403353215,132641594,542119676,645758545,892514894,695817397,918986024,654419063,435632565,309168117,612274628,818934884,776909903,776508342,827097502,344478920,70925879,687536489,118028126,833100791,385923816,599022549,123506168,624517181,814117626,805066683,968853589,756098444,947778674,444890617,597220888,339464518,170313011,160268710,678380366,404884045,261111102,912177341,419729267,858899905,110001174,774232655,732926067,817972221,704686076,389717702,510154256,412197445,713072255,557855348,858088603,902915210,723217290,612818053,548970246,220989491,223560488,232919698,460345958,436883601,946005912,688670117,422727228,539678160,350808339,281269863,835045329,78426680,54724098,301108360,38229563,964628077,431470436,909285056,723473049,807184865,627001692,90484316,162316520,91038790,492832624,947282157,975498432,317115782,466878729,524537783,706638368,58068896,35201455,265543699,857002623,366653089,389987424,395093743,191684436,99333982,792297210,275675748,370928812,573418143,693784605,894928354,971400800,816049768,570539659,232367538,497690287,716376628,558087224,912135497,550697682,371302619,263197497,197848750,620741104,243110496,238851289,968968884,993036154,172635505,133509217,574724601,230039767,170288980,441288397,803056235,996526653,213865281,330936953,168551748,489702977,564993489,285067487,875594858,663110037,299025061,775763382,157497522,903456072,946947331,33984690,929239663,127823784,446578035,707573747,514980999,585651807,649716280,945849968,194864245,15300244,108822077,287495752,997965467,576873980,104349100,382717497,650001185,236622861,897876688,300329121,660660256,367516447,893619980,905909404,815802354,17393665,316278129,856578282,471080181,274906712,722243761,124793429,975531256,699491610,310659952,223049995,59194261,872629562,894065937,315919105,531041434,339686910,433842933,419671136,751974146,740302309,143758951,437944793,5406145,719854597,908565844,817382890,990366703,534402173,727007769,93595638,883704059,536374207,130538183,794211428,408593599,425666552,482582215,153356276,511827021,978992291,477565659,158894257,689258546,44106514,279107792,738402106,343347623,95688893,121086662,775269184,159722336,776838713,512678159,528843285,992313709,9639856,577327558,84019386,492867445,243100973,37860508,440757939,401897068,401036827,366319831,400988166,657442421,374839491,46164817,439904865,849705445,305561937,911887051,574073043,64500849,545086928,864762459,596801294,197671112,56839918,140898165,50507886,858352484,314743691,572014053,562062143,284131122,941733421,519537380,664221685,978624398,567515771,78159937,267090164,829500028,491267732,326007816,531429342,5786797,981663875,136932451,508607711,84520890,879440432,786191303,94100297,276896065,578308958,277324024,920421462,622706362,694442500,127106548,768911983,345993390,732937458,705419367,231014989,390032361,373566797,208948619,712323925,211854651,743234086,95764224,388628707,936017113,653395050,912407603,386549311,66366662,883302300,204082246,495344885,416380012,377485477,869299892,859953605,110913371,10966862,439968448,56666029,310265543,182744527,346499183,317446891,787997032,114797046,871177581,4822344,502925119,768781389,787758708,204528633,170547396,257712226,413318361,498288294,276410024,276148901,228181655,213040123,449037885,366311661,583125668,270138677,381063588,868563041,423945550,240016518,898075512,272003883,820989379,44752387,760955848,523125676,227932756,227637320,105270981,776053802,413576387,403471687,866393154,557361304,586937266,308526802,841412442,115524430,356943419,485699592,513160751,608526550,137575912,624835507,983255891,522946310,719107795,807386793,327125759,442964921,753550476,714002699,36132409,874998905,370853052,61390718,773866327,585071505,306486283,346428291,86202083,463344270,915430618,467213979,452689781,623754931,358415415,977257571,13774749,129378102,739634134,570002401,765192658,102900360,524932959,827122259,385589774,933979937,387885974,755403834,855298566,272508080,123024886,523498248,466646301,334287083,540905593,468385971,850563268,382406416,40210179,158859188,515822707,393474529,428661297,794026852,911690715,753965290,251886253,950331156,807402307,972017557,494361010,71258043,199878448,409474356,343451984,505443158,787521921,161079250,103830717,83029129,755341486,876878955,821670976,358656138,173342561,530234397,628784578,154108458,712200109,390001079,507808367,143117442,262263982,328829411,145844899,385406538,326035178,594257051,529415319,499370014,483317504,17143828,135440548,283018796,440824734,17201948,403297883,427228093,164243452,398678336,720098547,649144081,223310586,753463414,638863727,874639060,377218304,441579335,678605605,830420539,502995123,674224110,814804640,489571786,204328381,720667980,115986710,524602246,705276594,981348924,32578370,557102208,766442628,771188005,210845040,608199787,564661211,339537153,850566376,446773216,839698183,800747342,890908797,890526871,692984793,547970648,681587261,129273498,603890753,924816087,795596189,276501958,127113224,927278666,627203963,994793859,775551679,547060954,150056674,885431512,619497402,366523856,81885588,729041502,56309074,730127286,311412717,662274365,165428344,931564508,929753939,563258059,494216347,345932163,241302384,120445759,64129995,282140892,259375502,475915325,395559889,272624258,443877979,46735450,519128259,895194494,224212076,82528995,643525362,714531560,323838887,757432360,890584434,410201230,157135631,126364464,549848767,73220111,560051279,712338503,310187582,975627183,189972644,767747675,444282571,556251026,379460346,935266558,376890879,198278260,167459576,774632776,761128134,979259511,807736413,205617215,258547830,851683999,671399538,152451416,953817193,864780117,869171289,669509478,545817367,611632140,884975679,745501095,411432176,553457534,12393017,476528467,200702551,810154518,111252959,520573897,108681613,441372635,657630077,576377777,415695289,91115451,317546711,594853191,778574806,323198926,868896691,512858663,691527229,237468315,667447909,835914868,70129177,322592809,92842329,111404984,291068300,828488470,443270922,547577864,86752155,98902228,684196192,606837558,42224006,748916907,911423891,79927931,131233256,844949578,157849202,502994119,756641506,655650566,994414494,573724953,492551527,326836672,454963062,302967072,996120972,193344848,446043070,667393157,946747972,225053877,411372923,373115185,607335511,776099574,957326458,286572530,241838264,545289326,556542352,61168854,589683002,813636712,137840233,116482336,304885791,104821782,645375779,380940559,861696873,658763470,15188152,648657933,472302008,349443868,990552332,446513718,652652090,787638136,63714586,760817846,610641997,555305146,209689172,64004946,68767994,346113996,80684559,758645226,539089598,257255661,434962858,656579563,812297787,169645625,273294828,94743576,438273531,844900476,639611370,699384420,440148227,388807094,121532653,190058432,37883796,994786933,382190931,359689050,487000435,549253775,32572132,568506835,574427615,716975010,80123522,702033373,924639871,385607259,578384877,891286108,235159920,507904484,709309332,338674023,758609711,922162920,757884892,189103640,807352010,424365465,83394863,372266144,503408586,566320960,975945854,677091622,540489057,365673009,863616315,24616325,808018447,250926,329135791,736565524,355330411,377497388,348159916,764117260,871847626,775898578,892888919,759937666,149375650,94998686,202326022,17569856,26797092,851631533,773031823,957890738,138802221,803287805,128560676,225638481,368645781,246483639,269601952,321128009,782995733,470797092,606044488,902877174,271201408,367418009,378032747,983970194,414008404,300870194,345615413,382052572,332983668,259504632,663416151,191632056,197689934,210766693,846670613,900877395,742304395,686037255,109937189,726490309,445962057,85595331,51215351,934769348,565032336,505548756,204596839,446102774,410599178,828988016,773025713,669622148,868848200,815701799,28910235,129830473,474504952,843126989,504005873,446229077,320179146,102366063,283981068,817121328,908938695,121100006,622949796,496551209,618036322,414358595,812067287,383934640,976714881,982535608,160388948,128424941,987296985,601341095,952849615,261160570,338986836,662924465,586540137,284987480,616935549,622237606,780971248,158646575,390839276,701380706,893603791,881558177,351354254,888054644,647968566,60870792,374957570,337034806,665297778,463459189,538255667,29593090,32596101,362363613,84635229,876182855,31662087,899858182,978763774,588206619,294286801,894296512,873378349,949329341,37754511,980195408,363768217,630331489,13742252,741349217,307321808,286136130,114449923,613648854,923048174,757511367,648410239,571042934,450053299,832710012,40000636,333807471,821807279,899400859,192810563,237702569,944989730,486382958,974897211,799769144,105869913,454693188,162029247,501034784,723089707,724415556,61304683,589725177,83577262,566967974,100542159,553889324,214454299,28548691,558798415,592709874,722688422,785301355,427197918,643255017,581264766,552368981,352674949,221846525,795844031,507487144,384142268,464447554,366000655,240315994,672284713,21482485,620477956,669406907,339958873,942457118,244936621,707823439,647213893,291600949,210603025,473805050,574985550,475445458,824378579,38510401,328737680,550534273,183866027,613126068,557982123,30589540,494077680,120581885,653970205,384037120,47658098,926439752,745485902,390382825,631727587,107559477,276091009,178258270,278965663,104076595,730021518,230671685,176391542,879877191,802313286,109971558,819130336,202720966,881759876,287886841,479558201,658246201,550237030,280292014,257575313,804217498,790245045,189611155,600683136,406176152,746086729,304817194,611225620,909204028,783686790,363104470,6028172,531752796,32250684,697090532,501127875,118565435,148696734,741531851,73385811,870944509,890292012,170496184,798443191,45176189,439448526,788708968,414994078,1627142,630570087,268886592,720780357,634910427,516448518,948368495,896372137,800429078,192235784,771377607,606557370,466532339,837184012,499653644,578929957,147250267,162118931,369006591,969684694,506151448,813745499,354701489,513176023,284498518,185366339,797539012,130316883,827500794,85341243,464061103,41055463,562785305,574919815,288671377,723256798,286548114,806862144,722767536,754378595,982421001,109717594,803857269,980180635,55476505,592676409,613307528,735483425,759491537,870682079,9099120,370193580,435868012,495825069,132197007,31310193,908950243,580864366,917026097,591453956,516399576,180414578,993089102,721322991,946811229,117350311,514612980,745212000,867992249,561626857,820270051,929625496,597056744,46966449,867627407,321752539,448474000,405328515,100568241,761928124,247880144,812657013,809576879,828394381,492856211,934251018,124236786,401068424,95391416,975042995,502300321,101716679,224807175,913696089,445742432,794273443,572598419,967414570,482185359,734740164,82124254,748835423,189874445,773341241,863275864,453676823,699353302,688678200,566497140,836812159,683045058,659538709,855189033,834728503,193022250,232905769,703166429,544230081,139955918,822502354,92062177,556753652,627088509,813269747,550514987,45264688,459520956,466300834,358035492,393101378,306582298,371073900,866427975,43247044,609816908,372546921,112032329,607089397,428138763,824102694,869255097,774917886,925076809,456666285,720795224,921506817,359220295,967428548,703475841,664258802,434635049,871670897,681911632,428836771,858278116,689113840,702939089,254226951,143998081,189687490,31422609,901569794,853922902,744865535,753976752,628186929,746724502,199915595,335733914,112683610,99806616,805395307,902241774,579333660,983132518,945472357,680671256,627664201,161668744,397713497,480880694,462670665,964100744,594796644,26019124,844672434,418968965,697473533,633600716,702452890,974042224,276218955,195552479,952870580,879312844,821563132,586388290,252734497,982300238,229295632,849334739,566863397,833876618,348384744,211371488,810940162,726283924,524011879,147665945,937302772,492261979,924988957,376726600,74660995,559112620,544903936,475022585,330145202,494648601,667416167,415376961,23208067,267317183,529103822,131731645,729008455,298659263,161086749,290694382,143599906,192157371,689138892,135137991,446188062,990491751,399879886,309401825,118269800,289586522,807595604,201554875,311873173,854934559,871755632,381086624,224941485,510218104,477946337,361767105,634924509,880025210,24860094,131261349,139111823,826219481,260038622,435997202,998034823,150822739,29563925,1051498,596451553,548477189,203140299,942505773,378738791,421260004,1942137,179380275,963106399,352210752,818999118,455509832,844786380,695598963,898604722,262424574,325429644,114431554,937626229,609459728,793377657,512202769,190939978,502855312,817005524,496956598,595907964,60869443,423276595,754395407,33076333,37946844,824070140,100200183,455241094,229578380,694426872,711853315,233619652,25962398,727911816,711329755,23250699,970515674,418131136,264159306,91263201,128710078,247143703,54023640,140081527,813711422,236953806,93510865,591011105,156684893,24852044,182417505,755732743,251820161,967616541,397178811,180044069,971854877,459230677,923885448,861710179,610914209,637847807,236011013,786108125,542025876,444485775,780286861,77772449,321002966,83568926,25577681,53052498,155747876,882034123,581174813,390045288,408552000,947509974,617197619,338396110,354000165,635732847,196048488,567964147,538703250,434545582,232310998,930198880,619955750,768486831,202361453,777035861,879983599,547060572,943409136,119745461,348699430,541329374,736760558,254784521,502752823,799849230,688055685,596603856,537719504,707535186,802607125,793538250,754400837,125960221,742780833,286272750,159166986,514786932,362612616,848049239,535034481,324320992,779781025,510398897,388344130,368880534,694211866,355734869,43882534,333709297,360466774,688757326,356161747,956967118,426118890,685785543,353938181,590623110,831852997,569620582,54530861,252892691,247491413,379682706,767290366,9609051,500255609,832026369,623945596,110325128,943970416,604335720,977667508,91652335,292838028,359084219,128063111,738180296,511782702,220785509,148771560,179528969,12409035,319644591,206866235,492926875,59576790,165768788,235680661,493591012,173317836,357160870,881419028,545113478,162673,83980303,470385254,134289191,57668684,519153311,929993697,34680670,268993841,627302471,854885316,291436784,105486449,263484202,97304035,291639628,926850876,728459785,945384696,51904652,90905549,823940585,327757294,451327986,347497993,937592837,982947768,5835768,921284678,793069928,674519559,273874579,861559929,299874768,750289940,976820770,351155620,18835601,579745972,29146383,971103052,951548378,399561808,945749537,771215105,141927179,323589798,815469935,25252276,446406897,930566408,568036030,744141362,887322822,193875621,874013121,862310725,37724943,983249040,304857034,714560323,208120044,770670187,879379402,347366074,128672357,604251764,209482616,759249110,685584264,863424858,414491606,675089676,479379988,347302367,683059376,291917584,91046022,523221894,420247058,356052859,653142507,151608578,822769967,579440272,79646295,933256868,117733712,685260776,221152949,912037170,140466827,21190031,601732785,810039745,290514414,965324026,870001778,628453420,548448351,35929546,142756854,955653127,742303154,77181320,540384864,951983971,372307961,565836474,450370885,584538701,454836101,331855642,734198700,179723153,55003641,239793426,489410940,14217757,129683946,514770453,128878999,652974416,777448277,93268078,935964667,219507671,192844917,759958446,215414378,420034715,920568433,317058826,18995995,336720688,562473673,210858966,737522903,347705528,807893663,212237772,310236445,399922470,692488103,570688889,176134423,82322820,969571376,463309926,434242302,882171300,509301960,979790739,341344499,794156073,56068963,694124598,852053444,154881262,287335,399813432,16940839,214106679,920885314,784177571,4062360,465688030,379725241,977944912,946369082,739823107,665461074,575709593,678587498,695131697,955086371,719728847,713495945,723191663,156985557,269272802,306162210,915296320,208239321,918422190,587880568,298141050,125972190,961186824,298637273,887132180,985110076,308531430,679619216,265053411,718991119,148222605,581745635,467080426,337373003,532003046,635415560,270205937,126819247,789016965,424293012,858065830,561123962,143377448,245138636,401553425,609084503,145605166,940159054,572088000,259720729,135522110,394587642,553084270,179514873,48822851,967345773,654573583,29176073,176355333,712507062,620023203,578300598,275262393,234481165,830648969,48147938,626329985,815700812,841607989,435081502,911052138,230689444,916888471,294955297,878568910,305234306,778183917,593830068,993716671,232088682,367392947,165352316,160772848,276919082,516495350,84284900,660396577,93531219,310600406,583675729,197503055,862389849,703253798,616518950,961237269,258339205,383211765,157248551,670691633,27184348,367812890,687478462,394380334,5254908,644464453,931876661,662872725,262462547,770325649,589827436,41567894,890200255,577826503,860114611,461107021,965581046,192177977,202459537,833190603,473316889,915465145,767538626,215275869,109468836,856997920,348881273,764025755,18678645,517525806,390771806,1295161,76442354,279136635,510097012,389896806,130664930,77736950,31447687,938769149,285812717,956876156,682477769,589645112,40214902,147548536,194753270,683205802,243119537,964098888,576965533,988153025,7419727,804022542,826544629,901180027,728182416,727765328,951935664,741204726,261372407,837581546,211225850,460579616,804071391,168320121,254311074,906618005,990896764,783019689,664794331,201792445,537892444,973420608,858879906,369217876,827830929,377277008,715880979,851895371,45026830,573982857,61424637,406234370,841940385,744980982,820172725,314081413,352179587,185001153,258635591,801453366,193493739,588613401,300185161,483928673,81460059,656533929,512120379,542568517,544298413,642392310,45745196,537612787,706421614,833974631,798514751,921597107,3880852,420658005,938252195,732528756,34840026,269281365,894389282,797099767,369211836,706633082,148104490,749574288,614636547,901714029,400457099,865433932,786955350,956080126,56201607,537772527,458353355,693202274,114259748,99601510,975554819,451615517,700586814,668724876,811196064,612238219,222454295,529364028,339610314,910347340,223052963,158231111,826798781,290687557,58983246,878156587,995036269,80929096,615180378,978814956,445386198,391021059,878728996,906076482,133185218,780715554,501537634,480104792,58994788,895865752,86252900,381740066,746833892,126847045,654641335,625053156,324018084,542925122,673946869,953178803,363185103,876746620,210903000,652644620,158438268,583586702,947824806,527665352,92897636,704777744,938066706,621569525,671591965,914541079,239760511,979701688,370661350,549407595,833996988,226406174,264154987,774385074,594334972,129838880,379001631,786706237,237599305,310852891,568114706,608967234,317242378,113150269,216552450,83822965,439262352,355438231,201283132,115681638,528940571,474621092,820443545,197405343,159436153,128814978,129978206,454654104,502937751,200849924,364425977,16585463,762305410,973997366,992917413,665359089,149121286,858663277,126401184,558718912,665439846,940184049,18726180,37120405,677674873,228882022,635492439,582411077,506862537,244647595,66057462,930034806,35098154,337323128,783182188,62344979,718025043,810439666,998137153,736672814,411607092,29193607,259249366,892178395,16892058,792493111,57383869,10246426,825131321,201871807,367638343,484931883,302647682,629025896,934118201,452525696,982620104,176089909,686308354,883101494,675557182,438292076,342924823,113474187,203523336,949478519,195022125,365223329,504218135,727055297,925789617,87572244,865831439,389359626,577827729,692870004,119185804,880170956,237580103,749669025,823168916,213693686,38757711,319722729,402938574,79687234,98879906,530882577,955473355,991034073,990855848,142169180,73699139,125867304};
int table2[]={0,192677451,648614712,843256370,152923075,509027637,607747019,59207716,811573738,270719508,90241613,298081483,792154011,399315895,846208169,317626727,880603894,628223696,234983157,648849259,565342709,565082069,666801615,702103140,155535054,389293255,250812626,681492497,787672030,214402277,263901128,266453461,646184161,628611323,956713337,531730425,915618111,910367206,215552715,700564190,362783896,343218366,379963977,833492626,546467284,849120425,864743680,743603837,246325436,575306623,493210763,663820069,437763865,808342974,49731273,854332582,456596641,146676451,747656525,837822817,478939223,258652947,131469527,476019068,481671388,500900072,956262866,909847496,928601027,414438909,883061508,117471387,740239254,601669346,709727461,196996868,150098942,643373640,118121546,971423717,905613524,861747285,490627517,658555373,298692335,226161648,370329140,228276462,32366351,941768377,998702933,682439254,982466554,98285901,462988165,166349452,121115758,582300280,765717975,785518392,832686582,843397532,437077376,252874224,639299787,606554708,797559020,203035167,444265965,847049999,492298,690287517,199763611,523915784,55057139,492925853,176842791,885434697,163054445,804759682,589044400,458842458,305121089,550354334,542329354,3058424,51686752,411378626,333619334,216542709,527666324,408657542,951149134,675177111,62609930,497779258,732414240,408134980,50929441,202001911,642640836,824186557,399707877,672028202,625994853,389954070,882360477,969832571,144397354,935396983,333053930,971051246,493531925,108834981,250665565,379283255,972038881,470556286,111916994,299448394,657283862,78711302,237016327,292453748,849677998,384732143,558462530,881457323,686849062,407997935,822196826,874890081,899954481,720226351,123895106,722149996,803235279,32724073,640862248,536021447,341605288,43565510,491972327,714794238,540059156,212831814,840185983,883543203,727733058,158461763,776236762,965032486,937172904,602262611,579402207,386798586,975652746,111058968,540438605,918343911,736460841,82910756,171464305,557158041,290815918,871514879,177337043,366146474,693975273,923221174,957847804,72160477,414189666,131612577,66424548,64052339,427189784,488399989,198576604,669059860,588129145,798500656,303663592,354938826,663783867,433169426,667881891,140039581,172849391,100268386,135400262,271255591,285118238,103293973,604240150,194238440,511935,923268038,922026136,853070398,922885742,436271649,871544504,214673272,2631817,822710519,734900530,948028509,272878121,254210798,215861201,855690041,320244513,522461350,241277252,409870186,229566650,845732265,758991630,274008975,254580945,699195558,14877550,170961421,460805927,90087138,268345743,290110622,668446832,793742845,117753889,787709998,199028953,148219702,100448810,411460970,155286229,307587548,897901539,711878833,328171540,694237066,297537621,696042646,982712169,387756269,531703061,397505400,681589963,836226958,610589727,556027175,607692672,926201580,893743394,564980840,572205971,571740728,634973519,340508236,926710470,21960304,457189523,975687271,924444090,284551552,918896687,560928732,143926639,986469234,909153118,893254715,875034589,377425222,178004722,36479817,270347888,778019082,523448988,851429924,793797448,735369747,389441326,902673695,170434278,167111783,699295877,737722569,571733920,504242070,679042990,990725646,161136281,717850776,717799528,622335788,592523856,64990247,900009042,334107153,708603392,930923862,906393979,17628843,650241682,966829905,715156642,813596963,261592976,694469811,219279385,629363600,629242652,384979494,727014747,2529071,982789558,909102071,291507617,351129461,794778448,861018687,409711864,893018542,150999723,206390847,397591175,456159002,431146893,148456388,228305313,621096673,798123387,838069708,70216225,691855747,613228425,257955354,936157009,928333376,309877292,735296575,358174505,801471802,881823428,361838406,116590523,21231044,125265163,96684319,439282305,909071270,147222878,220724354,452398278,673378107,334581675,725429567,401312002,245844395,850689085,968092174,65339658,973619056,709121585,909377279,744262486,445763444,247176231,133938571,869686952,283390303,138816561,903637773,967789948,283863626,521627628,236020805,991790522,62630101,793826749,29621242,714636271,710944704,108300138,822907453,152602936,197754651,352013642,609720422,29377923,897798838,222246195,786868987,534448746,420416924,379279454,724368319,967908411,857957551,932392520,562229288,276478097,474043055,525155586,641803123,997870190,233948989,505031826,743789064,877384720,511880444,991467698,873189948,410098399,280880541,221253323,189611605,257729270,494786880,790407472,106483037,259700688,32357321,80680233,555175220,24508117,667812105,526366847,675162870,735931775,507196021,979209843,984831274,114017067,588532797,892625701,238238289,581159215,862783339,212780459,642755820,675898067,466998304,284692271,646503839,199111490,302032792,351543665,770686897,780639551,660416318,455588337,368972989,919187656,941709263,134585015,920898077,843457621,24242772,23940470,629318121,339752357,607448029,503282510,452978769,95291762,837314349,799587730,501271706,102065010,502377141,238019198,799996399,343477105,549930310,21141412,489734757,984249028,415433988,710207331,365203408,713300285,876332372,578516919,585286156,118019050,114859280,382327891,244705065,948597336,739798586,498546430,386375480,822857912,777788092,211328411,51077793,805667704,148635581,354811284,300057373,52650406,711146110,428240404,550692855,693164609,912239646,779886631,46650540,86343737,580672578,519590304,367018663,414221528,388344193,693378739,889536280,220875704,650025972,806035859,159565765,383962505,30840697,142912816,26621445,669855848,608677564,823483027,796932685,233655322,891068745,687289644,793610608,980342175,620232533,582795212,185985886,8370616,17611412,618746971,371822007,503910601,51056072,772565631,104886555,389396621,307726488,236455819,685262688,904625603,507280476,326380601,503054620,168895447,601867953,439821983,118915483,470214354,923535310,478605449,846507037,936212724,28067056,316448783,674243733,766583330,627001129,964393227,433280120,938665092,479621958,517205398,876990066,952288675,182312043,391383371,470189572,494947296,665992141,511732391,382961974,796805177,122276882,459742554,562811140,990701227,616957288,307704183,815456271,613931933,291917618,450995365,289105889,958133632,214843057,911308116,298072652,692977628,198830695,641987917,201154992,758223976,131318627,55259267,524156821,862141449,225051880,884000622,794988678,402347139,425310301,435020364,492504443,940867509,589730664,547471556,924734982,525063304,606627329,78212769,40182198,634771303,348076556,615473391,263217731,17957441,300630908,213009211,625741583,896169757,448778830,843439923,543544541,433326333,742550148,451637730,461618998,16767409,486363710,842740837,404085225,840872998,196742885,640431889,952324397,667476216,875229238,518582120,206097811,19807112,609684387,729685545,211669465,109442295,575348050,712855058,408961048,323222342,98485497,53936759,309014713,433977079,401069076,473393207,485689833,771239431,497991580,742266033,187933594,110323411,496333873,122591506,810793104,356737343,760000897,19184855,859511143,187071788,858969395,721861552,958812965,193294061,511806096,90003931,352743589,479023099,298727104,701472857,428722761,79545133,75886134,398339586,965597573,350517246,8741581,824055209,62038431,106826141,48605071,880973547,96887984,905443639,139877920,874430119,653760532,545460524,760569176,391510664,410419266,60541232,903795119,273966516,636243100,965668121,616666956,811276152,97744155,853873084,900563082,4068399,928257531,304313517,575261503,169380854,906482348,99368697,121051409,333379338,193908071,968084340,58027579,131355025,33669981,887165772,695441285,752326268,764895454,791501576,63761894,172628026,855935275,743853929,592105824,825664217,265059919,544779300,476471892,244033204,505011201,386497511,785046556,268510319,197956177,35186052,923713847,717358431,116263272,10422360,437291302,639584570,329385809,67081806,389291187,274189573,22542287,587367960,951049862,17782372,201868988,626643744,630795555,378450789,621873049,214969341,10838044,155024355,341036590,353129772,709288372,645812020,364007582,592548081,296016778,913091234,69195729,717522881,565206749,962551982,626899759,637955047,955874157,711676098,176512221,798046213,182943602,159303122,99346829,173199116,693478149,519733790,148359923,72965591,729942771,326716745,476761117,459886694,466344076,126329473,571323970,154870624,466279930,203122650,361384888,580721281,993333018,193804290,152419050,304771604,482072442,367405298,135000993,668577649,435850426,891515497,23910963,981990998,639070010,637918875,257167556,926544523,708793395,554509733,312981395,78744882,493776778,81841585,58291564,213928592,801197950,891432046,306456892,389693699,367173646,17367256,630018644,328115713,743238126,421698609,866258591,869359791,543588244,600879605,589033694,556264611,623862584,531006717,852586594,481225050,542174393,610448387,870855765,996530803,280773943,713338117,589807465,532465703,133527601,872320916,20765518,444500809,198260381,359320985,162877039,911958042,776344853,475189314,673629719,771936887,113490777,318936860,924344964,850568291,729797837,19021551,857476002,384329081,587139495,388507485,86824128,515536610,96439287,540482391,807594904,666564005,556725675,502389814,429816099,683273528,750499497,211082567,538773056,296784876,935326469,225569803,708707643,660820416,998332344,803115884,4979303,655650548,907990231,909739270,801627276,209046786,54367480,670132024,88898424,856528402,215054936,27757161,411548949,769372953,553804031,14362327,969376926,63109402,35612936,834793874,657385871,268820113,949089621,66998905,680263877,276668538,26082968,185366603,471663350,523560183,525004868,855132147,463654609,698978334,759688514,945806589,609962728,205528308,244671240,805527930,61869788,555783772,344776621,43745772,296763799,470477204,728811367,5892311,910126779,738834883,502358761,366645422,263100608,71662776,855724748,14456618,685264173,405661747,147412806,472799169,631798531,768886488,799071406,213294313,415097912,488478179,104114468,186473941,503870345,46962993,849146100,73937996,739941672,134756698,650885790,408772515,563208278,607115769,631831279,59781615,929399867,56429869,97505592,929763465,993432181,449963866,705004468,93731080,446824208,597863396,672710739,714419733,959218771,7682116,230509900,507790844,230426485,362222451,482583081,755773872,554447660,310174694,654449005,327219628,676521917,526860367,855336494,481131982,938047601,389470890,730995394,525967873,987612249,233618548,621334337,139067422,358224000,693533477,593798746,235567066,144264167,398153491,312309153,703235734,26401178,998751662,128751354,123037676,161119206,490488257,373724070,754141702,308251371,697342740,457092680,512053911,711332472,957959340,336182152,400721413,98229638,655326077,445404646,475392989,980948737,676162302,10031490,892555042,59933546,240249058,421497513,913295637,892390943,648474915,189550422,882461883,835895169,227641004,187165128,904199244,984412102,925378275,607951699,799849648,165388774,704953402,634782261,775897823,148706296,623642589,613587264,442545633,456550839,240465673,311043525,138451001,267879637,259033566,613116732,746701969,272607905,752024002,742582797,385126961,177500278,268251242,80021878,380785838,444410539,973113129,374981816,250853171,467714360,940254673,862265629,403464111,277980018,898906511,393201999,252529724,914646583,942742013,45762817,825749446,917573226,601488386,342226936,247378714,29708214,48375490,797240057,34760094,941587490,213668681,768012890,742703600,154325646,348463006,703091733,511134478,436257858,907100899,801530635,869984878,342518865,509298265,473323449,476628262,738463911,601352734,239104366,388141025,945594837,818294291,956441923,500065258,104862665,943974714,459055624,312384196,197328952,727423809,60559725,520136192,14570447,255093442,690595161,225066414,254528279,980945472,180526800,11658570,607558525,855310886,435028512,545390339,411288666,315207327,711520102,680867289,652893777,513574097,224263255,553714533,899694067,396060021,612166218,100827981,624845325,830544816,25542356,165288431,890586562,150245439,856500294,954058866,948467069,840909742,463454047,552504470,371725365,191212429,809391740,152468501,188930878,977292566,198373003,284939708,319024944,338130679,26284581,597281939,533181673,301266617,848024597,338669348,628782426,842027722,858172452,232831528,100912725,453272281,577791340,883810528,641736018,585153806,776398051,680893017,990662996,469837378,342746617,428232843,590039758,945359366,513254500,291906537,225926064,499390325,278386656,980454337,386908436,114991483,241444161,819890348,466723260,810833421,179112104,617205471,975122878,599396091,228139338,588483585,786829525,717195196,442452349,105131744,662936480,673120602,245809074,798511532,509036291,58153947,988292753,23588284,67564111,652691346,57032988,24311700,648596802,543568518,439242281,131741541,786391850,861728628,99039387,713242292,885800500,233503088,80430423,793987656,789430405,921219814,657996392,973569128,120642338,113259553,545295140,404862075,971035004,555098970,530292907,460046104,336137430,834987537,889297055,86065699,186702382,698980057,504341861,176386628,771799678,258702685,784277030,668736518,724126822,929960490,382975058,781698877,399882821,437337859,515696018,855512697,298351585,330001997,893908125,14980861,759254359,701175261,493301715,89273495,485491112,865447277,162951296,31143045,180933348,387270666,721866297,515006332,868120310,326470153,712172197,103475434,139963903,636342727,230977150,7831876,825369925,708043401,48115970,238701384,221004612,143171296,886731054,120814332,208238485,954468472,666150261,362242807,333557322,707968353,286983025,198345478,660023349,416354965,377869323,28972886,352460485,729196588,309291009,363247595,20270480,355519751,557571412,496315917,16091188,352837489,826648241,309549544,785525259,755787274,152953009,142591523,407414663,183070744,668149786,649883891,313866866,898146829,871346478,539077840,860249609,607354970,835765182,238578763,371512281,909910712,130586206,678232001,96678211,953091630,15046903,681248482,296160123,71043891,643605785,777345832,990171494,130436405,646697883,6592247,374718189,423675048,751504387,662043586,830119488,603370189,931618360,778817538,702227761,524348566,734163190,203229475,920287529,375893720,249436549,877976532,194413101,862493174,251604259,522466994,126125458,560415870,773896360,852338222,318849474,326923843,574505519,367285669,547914776,639064900,685281008,516618944,260629812,23969392,223119077,398930778,276001047,177272152,630774392,379884759,715685078,837945717,737186028,621539254,582870678,479337537,572151600,223522420,965386874,329152173,313353632,733358360,576107783,544867676,820246925,172898588,459700804,73246299,433961368,410996474,762264856,653753056,297409483,117255778,104814399,230355080,448212328,384625785,947678112,899276843,110179033,210151430,63261800,419382752,521956409,43591948,652611683,388896597,60850162,279006019,877701926,742493439,536983149,409034821,3653620,1025823,343788362,857567007,858418396,566079160,935471280,70965188,143188247,525396220,982694992,744581002,906106903,323160300,284548893,634607436,444402006,961744259,802174033,777575280,991669376,617901440,191640482,861836520,788681995,612319944,453407301,840903173,610410583,879185515,620219601,374698659,179823580,71311945,822311846,192330811,692004941,742057150,973429138,744040871,972697640,21328092,270714786,902793648,588626414,156150985,103264185,237929912,149280955,558960755,560467056,353886891,758200912,394089859,846035151,143244837,197011672,417816105,338630354,147757485,344194267,524004965,109574834,866414585,77744885,890560096,665495722,653411807,595716115,492013818,746713467,688128998,411675337,317737120,842001934,118551716,434848016,40942463,732192990,531684411,766377998,161148111,575143510,302167976,742376022,666066307,494579091,691457118,628744424,216092150,67806340,888741967,94936098,128462836,648810074,178533496,166506472,186335922,54362465,279375091,353592307,572298814,158623641,579428544,918784139,339742767,995843508,666711166,342049845,519478034,715871892,363153109,105766258,277073005,185385734,44287027,911772199,682879679,423902363,813600595,20863758,290883153,4547355,329380234,600370801,468354346,874909271,39854607,243815567,557083911,972584313,46063941,635609916,899905327,275608975,27649919,546219329,863649861,116949377,856003298,693486598,68380798,818024304,112821211,185562678,1032812,918024711,312386237,231262519,424035692,859471012,16272434,395452008,447703350,635088399,587467834,227180057,600016112,356587209,524252656,378021469,324359028,956088677,756299114,233480745,504526981,100882015,92161351,324891721,804481825,940498708,93159268,959866838,394442595,941030797,169123065,499333204,181498716,8465932,698339630,292982197,543164025,91674177,118997852,832421098,514116059,153884144,568125515,790312356,69168502,644430010,106859924,306477407,322640478,962081321,865999670,563701748,939392009,504406332,706827851,716213804,169844849,190845347,452743568,733433131,618167578,322752102,218663551,7486935,502982514,487185667,317911308,827654286,825785813,572714721,794198544,944930150,350755599,813112811,573149499,55122407,949703078,857561384,672641148,367164477,709728494,161369164,976141567,877717958,92822473,187668577,165010828,285275055,727670536,953840855,776652778,815622892,409264536,454745100,604452824,258893656,258496260,707273494,286248444,327021293,479876346,227601711,726746139,414166634,143100555,315518945,620569628,789563434,374246536,138232670,212665721,885302659,756795648,528150798,549263469,466925744,566254377,243898968,516363926,903063786,961411871,936731872,626787913,498635636,305153436,455972842,444226543,520859443,186939551,334645159,420716824,205234239,995910135,419489741,787413447,982911758,133495758,845105201,906438475,910334173,106958316,914100436,898271957,236325744,491868434,421385124,667986816,832990946,666981597,702605518,291595050,896653430,365972095,616624022,422481136,567141457,242420040,125799037,329174664,59735284,634326558,632249195,562639106,406117148,744802512,945482394,909060507,750657277,220790874,63342531,34462039,786804326,739361217,237739338,174451470,459829638,62348738,283216785,897473157,518400649,660309776,286157065,156948539,494520516,422734945,959761670,598544238,832739288,4961747,73900490,801605624,735184115,626889169,602741310,657871728,112526395,408022958,850102749,807673031,965888582,640067162,21276951,612686943,343309804,103771607,159795922,101055582,499421189,937671013,200150482,759049066,579496673,607055418,275803337,159722174,171744985,22476676,751387668,911504897,42404923,266600788,733614840,101056226,201536236,687869746,338743997,819062868,601417555,959344935,528958892,314213749,390146535,411042112,51376348,122819597,621580799,437425318,339646499,486588761,1547630,83687304,500673699,92924115,300163571,35139647,746453777,579241023,271365761,100598927,927551879,819348237,511427524,265785859,190282407,129475473,132237477,782024785,879026809,275285999,602874331,907627922,399502968,823322062,861597194,206915718,174875393,594394412,130305697,995376877,209252946,759176344,916695048,953918212,235462648,338312427,151968972,46241382,895578961,371584359,14838881,743229162,953790620,558676001,450829440,9590303,321385732,506649388,882478790,359984798,710288463,945896356,406442925,672735330,922597758,474233544,4449825,910610190,540814864,294730327,626697923,861719721,497586375,150777250,761397582,798646815,859269974,246644029,267515774,661536100,246881776,772787201,582487161,124019771,304552329,796897752,288419557,629256073,907680821,353789696,751693254,75692581,632645056,680136799,57506752,288025536,141091135,663496206,378749171,403361880,550795968,332280133,982842594,545206625,712073153,66004641,104824571,969264681,818879774,890435194,890513344,193574525,57069169,161839623};
const int Lim=5000000;
bool no[Lim+13];
inline void work(ll l,ll r){
for(int i=1;i<=m;++i)
for(ll j=max(2ll,(l-1)/prm[i]+1)*prm[i];j<=r;j+=prm[i]) no[j-l]=1;
}
int main(){
//file();
Math::Onshai(prm,m,100000);
read(n);
ll ans=(n-1)%mod;
for(int i=2;i<=m&&prm[i]<=n;++i){
ll x=(ll)prm[i]*prm[i];
while(x<=n){
ans+=x-2,ans%=mod;
if(2*x<=n) ans+=2*x-2,ans%=mod;
x*=prm[i];
}
}
ans+=table1[n/Lim],ans%=mod;
memset(no,0,sizeof no);
work(n/Lim*Lim+1,n);
if(n>1)/Lim],ans%=mod;
memset(no,0,sizeof no);
work((n>>1)/Lim*Lim+1,n>>1);
if((n>>1)>1)/Lim*Lim+1,i=l;i<=(n>>1);++i)
if(!no[i-l]) ans=(ans+(i<<1)-2)%mod;
println(ans);
return 0;
}
D
Day 16+1
Test ex1
A
点击查看代码
const int N=60+13;
int m;
ll l[N],r[N],w[N],ans[N],distl[N],distr[N],dist[N<<1][N<<1];
ll a[N],b[N],cnt[N];
ll dis(int p,ll u,ll v,int tp1,int tp2){
if(!p) return 0;
if(u==v) return 0;
if(tp1!=-1&&tp2!=-1&&dist[tp1][tp2]!=-1) return dist[tp1][tp2];
if(u>v) swap(u,v),swap(tp1,tp2);
if(v=cnt[l[p]]) return dis(r[p],u-cnt[l[p]],v-cnt[l[p]],tp1,tp2);
ll res=((dis(l[p],u,a[p],tp1,p)+w[p])%mod+dis(r[p],v-cnt[l[p]],b[p]-cnt[l[p]],tp2,p+m))%mod;
if(tp1!=-1&&tp2!=-1) dist[tp1][tp2]=res;
return res;
}
ll sol(int p,ll u){
if(!p) return 0;
if(u B
C
点击查看代码
T=int(input())
while T:
T-=1
useless,m=map(int,input().split())
prea=1
a=1
now=0
b=1
while 1:
if m-bDay 16+2
Test ex2
A
点击查看代码
int main(){
int n,m,k;
read(n),read(m),read(k);
if(k==1||k>n) return println(qpow(m,n)),0;
if(k==n) return println(qpow(m,(k+1)>>1)),0;
if(k&1) println((ll)m*m%mod);
else println(m);
return 0;
}
B
点击查看代码
const int N=1000+13,M=1e5+13;
int n,m,k,p;
int a[N][N],bx[M],by[M];
ll sumx[M],sumy[M];
int main(){
read(n),read(m),read(k),read(p);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) read(a[i][j]);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) bx[i]+=a[i][j],by[j]+=a[i][j];
std::priority_queue q;while(!q.empty())q.pop();
int cx=0;
for(int i=1;i<=n;++i) q.push(bx[i]);
while(cx C
Day 17
Test 15
point: \(100+100+0+50=250\)
rk: \(18\)
A
暴力是 \(O(n^2m)\) 的，考虑压位：把每个位置在第 \(i\) 次是否属于 \(X,Y\) 两个集合压成两个 ull，这样每次就直接 \(O(1)\) 判断：\((x_i\ \mathrm{and}\ y_j)\ \mathrm{or} (x_j\ \mathrm{and}\ y_i)\) 的 \(popcount\) 就是这条边翻的次数，使用 __builtin_popcountll 就可以过了。
赛时：过了。
点击查看代码
const int N=2e4+13;
int n,m;
char s[N];
ull a[N],b[N];
int main(){
//file();
// double st=clock();
read(n),read(m);
read(s+1);
for(int i=1;i<=n;++i){
int tmp=s[i]-'0';
a[i]=(tmp&1),b[i]=(tmp>>1);
}
for(int i=2;i<=m;++i){
read(s+1);
for(int j=1;j<=n;++j){
int tmp=s[j]-'0';
int x=(tmp&1),y=(tmp>>1);
a[j]=(a[j]<<1)|x;
b[j]=(b[j]<<1)|y;
}
}
int ans=0;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
ans+=(popcountll((a[i]&b[j])|(b[i]&a[j]))&1);
println(ans);
// double ed=clock();
// println(ed-st,0);
return 0;
}
B
考虑二分答案 \(v\)，那么把 \(a\) 中所有数减去 \(v\) 之后求一个前缀和，设其为 \(b\)，那么相当于是找 \(b\) 的最长上升子序列。直接做就是 \(O(n\log n\log v)\)，可以通过。
赛时：过了。
点击查看代码
const double eps=1e-6;
const int N=2e5+13;
int n,m,a[N];
double b[N],f[N];
bool check(double x){
for(int i=1;i<=n;++i) b[i]=b[i-1]+(a[i]-x);
if(b[n]+eps<0) return 0;
int st=1;while(st<=n&&b[st]+eps<0) ++st;
if(st>n) return 0;
f[1]=b[st];int cnt=1;
for(int i=st+1;i>1;
if(b[i]+eps>1;
if(b[n]+eps=m;
}
int main(){
//file();
read(n),read(m);
for(int i=1;i<=n;++i) read(a[i]);
double l=1-eps,r=100+eps;
for(int T=1;T<=40;++T){
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
println(l,5);
return 0;
}
C
在某一个节点，把每条相邻的边拆成两条，这个题相当于是你可以连其中一些边。这个方案数可以递推，也就是剩下 \(0/1/2\) 条边的情况直接 dp。
接下来考虑这样做算重了多少。对于一个有 \(l\) 个点的链，会算重 \(2^{l-1}\) 次（每条边都有两种），但是其中题目中那种开头和结尾点都一样的两条链，其实是没有算重这么多的。大概算一下，这个东西就是 \(2^{n-1-c}\) 次。所以把所有答案算出来之后，若要使每条边贡献 \(2^{-c}\) 只需要给全局乘一个 \(2^{n-1}\) 的逆元就行了。
赛时：不会。
D
首先有一个很显然的 \(O(n^4)\) dp，枚举从哪个点转移过来的就行。然后可以考虑一个前缀和优化，枚举一维，把另一维求一个前缀和，就可以做到 \(O(n^3)\)，然后用 cdq 分治搞一搞就 \(O(n^2\log^2 n)\) 了。用 cdq 切的时候横竖交替切就是 \(O(n^2\log n)\) 了。
赛时：打了 \(O(n^3)\) 的 50pts，有一个 10pts 的特殊性质写错了挂了 10pts。
Day 18
Test 16
point: \(40+100+0+0=140\)
rk: \(38\)
《NOI plus模拟赛》
A
考虑二分答案 \(v\)，每次从堆里边拿出来最小的，往里边加点，如果加完这个点权值和 \(>v\) 那么就不加，看最后一共能往堆里加多少个。复杂度 \(O(k \log k\log v)\)。
赛时：直接贪心取 \(k\) 个，复杂度是 \(O(nk\log k)\)，但是空间开不下。因为需要把 \(k\) 个的都扩展，在极限情况下堆里边的元素个数能达到几乎 \(O(nk)\)，空间承受不住，被卡了。
B
首先注意到， \(a\) 里边的每个值 \(a_i\in\{b_i,b_{i-1},b_{i-2}\}\) 就可以使得只要无解，所有情况都无解。证明也很好证，直接反证法就出来了。
这样可以直接 dp，设 \(dp_{i,j,k}\) 表示处理完前 \(i\) 位，第 \(i\) 位和第 \(i-1\) 位的分别选的是 \(x-0,x-1,x-2\) 的值的情况。暴力枚举三个位置的值转移即可，时间复杂度 \(O(3^3n)\)。输出方案的话再记录一个 \(pre\) 就行了。
赛时：过了。
点击查看代码
const int N=1e5+13;
int n,a[N],b[N],dp[N][3][3],pre[N][3][3];
inline int mid(int aa,int bb,int cc){
static int d[4];d[0]=aa,d[1]=bb,d[2]=cc;
std::sort(d,d+3);
return d[1];
}
int main(){
//file();
int T;read(T);while(T--){
read(n);bool game_over=0;
for(int i=1;i<=n-2;++i) read(b[i]);
for(int i=1;i<=n;++i)
for(int x=0;x<3;++x)
for(int y=0;y<3;++y) dp[i][x][y]=0;
dp[2][0][0]=1,dp[2][1][0]=1;
for(int i=3;i<=n;++i){
for(int x=0;x<3;++x){
if(i-x>n-2) continue;
for(int y=0;y<3;++y){
if(i-1-y>n-2||i-1-y<1) continue;
for(int z=0;z<3;++z){
if(i-2-z>n-2||i-2-z<1) continue;
if(mid(b[i-x],b[i-1-y],b[i-2-z])==b[i-2]&&dp[i-1][y][z]){
dp[i][x][y]=1;
pre[i][x][y]=z;
break;
}
}
}
}
}
if(dp[n][2][1]){
int now=n,x=2,y=1;
while(now>2){
a[now]=b[now-x];
int to=pre[now][x][y];
--now,x=y,y=to;
}
a[2]=b[2-x];a[1]=b[1];
for(int i=1;i<=n;++i) print(a[i]),print(' ');print('\n');
continue;
}
if(dp[n][2][2]){
int now=n,x=2,y=2;
while(now>2){
a[now]=b[now-x];
int to=pre[now][x][y];
--now,x=y,y=to;
}
a[2]=b[2-x];a[1]=b[1];
for(int i=1;i<=n;++i) print(a[i]),print(' ');print('\n');
continue;
}
println(-1);
}
return 0;
}
C
LGV引理+范特蒙德矩阵+FFT。太阴间了待补。
D
SAM+主席树。同样阴间，待补。
Day 19
Test 17
point: \(100+100+30+30=260\)
rk: \(21\)
stO zrz CCCCOrz!
A
首先注意到，如果开了一个环一定会全取完再开下一个环。直接猜测每个人开环都是从小到大开（感性理解，如果开的是不是小环，对面拿大环再开小环，可能不会很优），所以每个人可以留下 \(4\) 个不交换先后手或者直接全部拿走交换先后手。然后根据这两种方式 dp 即可。
赛时：看到 \(n\leq 100\)，没敢信那种可以 \(O(n)\) 做的结论。反正 \(\geq 8\) 的那些绳子肯定后手会留 \(4\) 个给先手，然后大小为 \(3\) 的一定会交换先后手，剩下 \(4,5,6,7\) 的直接四维 dp，设 \(f_{i,j,k,l,0/1}\) 为剩下 \(i\) 个 \(4\)，\(j\) 个 \(5\)，\(k\) 个 \(6\)，\(l\) 个 \(7\)，并且一开始先手的当前是先手或后手，先手能够拿的最大值。然后这个 dp 就是当前切 \(4/5/6/7\) 哪一个，注意先手会使自己尽可能大，后手会使先手尽可能小。太阴间了，调到十一点半过了。
点击查看代码
const int N=100+13;
int n,cnt[10];
ll f[N][N][N][2],g[N][N][N][2];
int main(){
//file();
read(n);ll sum=0;
for(int i=1;i<=n;++i){
int x;read(x);
if(x>=8) ++cnt[8],sum+=x;
else ++cnt[x];
}
if(cnt[8]) f[0][0][0][0]=4*(cnt[8]-1);else f[0][0][0][0]=0;
if(cnt[8]) f[0][0][0][1]=sum-4*(cnt[8]-1);else f[0][0][0][1]=0;
for(int j=0;j<=cnt[5];++j)
for(int k=0;k<=cnt[6];++k)
for(int l=0;l<=cnt[7];++l){
if(!j&&!k&&!l) continue;
f[j][k][l][0]=max(
max(
j?min(f[j-1][k][l][0]+4,f[j-1][k][l][1]):0,
k?min(f[j][k-1][l][0]+4,f[j][k-1][l][1]):0),
l?min(f[j][k][l-1][0]+4,f[j][k][l-1][1]):0);
f[j][k][l][1]=min(
min(
j?max(f[j-1][k][l][0]+5,f[j-1][k][l][1]+1):(ll)INF,
k?max(f[j][k-1][l][0]+6,f[j][k-1][l][1]+2):(ll)INF),
l?max(f[j][k][l-1][0]+7,f[j][k][l-1][1]+3):(ll)INF);
}
for(int i=1;i<=cnt[4];++i){
for(int j=0;j<=cnt[5];++j)
for(int k=0;k<=cnt[6];++k)
for(int l=0;l<=cnt[7];++l){
g[j][k][l][0]=max(
max(
min(f[j][k][l][0]+4,f[j][k][l][1]),
j?min(g[j-1][k][l][0]+4,g[j-1][k][l][1]):0),
max(k?min(g[j][k-1][l][0]+4,g[j][k-1][l][1]):0,
l?min(g[j][k][l-1][0]+4,g[j][k][l-1][1]):0));
g[j][k][l][1]=min(
min(
max(f[j][k][l][0]+4,f[j][k][l][1]),
j?max(g[j-1][k][l][0]+5,g[j-1][k][l][1]+1):(ll)INF),
min(k?max(g[j][k-1][l][0]+6,g[j][k-1][l][1]+2):(ll)INF,
l?max(g[j][k][l-1][0]+7,g[j][k][l-1][1]+3):(ll)INF));
}
for(int j=0;j<=cnt[5];++j)
for(int k=0;k<=cnt[6];++k)
for(int l=0;l<=cnt[7];++l)
for(int c=0;c<=1;++c)
f[j][k][l][c]=g[j][k][l][c];
}
ll sum1=f[cnt[5]][cnt[6]][cnt[7]][0];
ll summ=4*cnt[4]+5*cnt[5]+6*cnt[6]+7*cnt[7]+sum-sum1;
if(cnt[3]&1){
print(summ+3*(cnt[3]/2)),print(' '),println(sum1+3*((cnt[3]+1)/2));
}
else{
print(sum1+3*(cnt[3]/2)),print(' '),println(summ+3*(cnt[3]/2));
}
return 0;
}
B
两个齿轮卡住当且仅当有偶环。这样就直接用扩展域并查集或者带权并查集做掉了。注意两个齿轮的转速跟中间的所有齿轮都无关，只是中间有多少个决定速度是正是负。
赛时：真正的签到题，过了。
点击查看代码
#define un Union
const int N=2e5+13;
int n,m,a[N];
int main(){
//file();
read(n),read(m);
for(int i=1;i<=n;++i) read(a[i]);
un::init(n<<1);
while(m--){
int op,x,y,c,v;
read(op);
if(op==1){read(x),read(c);a[x]=c;}
else if(op==2){
read(x),read(y);
if(x==y) continue;
if(un::query(x,y)) un::is[un::find(x)]=un::is[un::find(x+n)]=1;
else un::merge(x,y+n),un::merge(x+n,y);
}
else{
read(x),read(y),read(v);
if(!un::query(x,y)&&!un::query(x,y+n)) println(0);
else{
if(un::is[un::find(x)]||un::is[un::find(x+n)]) println(0);
else{
if(un::query(x,y+n)) print('-');
ll up=(ll)v*a[x],dn=a[y];
ll g=gcd(up,dn);
print(up/g),print('/'),println(dn/g);
}
}
}
}
return 0;
}
C
注意到 \(C=\prod_{i=1}^n (d_i+i-1)\)，直接把 \(C\) 的所有因数拿出来，\(d_n\) 从小到大枚举答案，然后对于 \(i\in [1,n-1]\)，都需要满足 \(d_i\leq d_{i+1}-1\)，根据这个东西贪心构造后面的方案就行了，复杂度感觉挺对的。O(似乎能过)。
但这好像复杂度不对？待补。
赛时：dfs 剪枝不够，打了 30pts 暴力。
D
待补。
Day 20
Test 18
point: \(100+0+10+10=120\)
rk: \(31\)
A
点击查看代码
const int N=2e5+13;
struct Node{
int d[7];
Node(){memset(d,0,sizeof d);}
Node operator +(const Node &a)const{
Node ans;
for(int i=1;i<=6;++i) ans.d[i]=d[i]+a.d[i];
return ans;
}
Node operator -(const Node &a)const{
Node ans;
for(int i=1;i<=6;++i) ans.d[i]=d[i]-a.d[i];
return ans;
}
bool operator <(const Node &a)const{
for(int i=1;i<=6;++i)
if(d[i]!=a.d[i]) return d[i] t[N];
std::map ms;
int main(){
//file();
read(n);
for(int i=1;i<=n;++i){
Node tmp;
for(int j=1;j<=6;++j) read(a[i][j]);
for(int j=1;j<=6;++j) read(tmp[j]);
a[i]=a[i]-tmp;
tmpa=tmpa+a[i];
}
for(int i=1;i<=n;++i){
Node tmp;
for(int j=1;j<=6;++j) read(b[i][j]);
for(int j=1;j<=6;++j) read(tmp[j]);
b[i]=b[i]-tmp;
tmpb=tmpb+b[i];
}
for(int i=1;i<=6;++i)
if(tmpa[i]!=tmpb[i]) return println("No"),0;
ms[pre[1]]=1;m=1;
t[1].insert(1);
for(int i=2;i<=n;++i){
pre[i]=pre[i-1]+a[i];
if(!ms[pre[i]]) ms[pre[i]]=++m;
t[ms[pre[i]]].insert(i);
}
for(int i=1,bgn=1;i B
B原题
C
C原题
D
D原题