Todo List (\(6/38\))
[3] abc 猜想
注意到 \(\lfloor\frac{a^{b}}{c}\rfloor\mod c=\lfloor\frac{a^{b}-kc^{2}}{c}\rfloor\mod c=\lfloor\frac{a^{b}\mod c}{c}\rfloor\mod c\)
快速幂即可
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
template<typename T>
void read(T& x){
x=0;bool sym=0;char c=getchar();
while(!isdigit(c)){sym^=(c=='-');c=getchar();}
while(isdigit(c)){x=x*10+c-48;c=getchar();}
if(sym)x=-x;
}
template<typename T,typename... Args>
void read(T& x,Args&... args){
read(x);read(args...);
}
#define int long long
int a,b,c;
int power(int a,int t,int p){
int base=a,ans=1;
while(t){
if(t&1){
ans=ans*base%p;
}
base=base*base%p;
t>>=1;
}
return ans;
}
signed main(){
read(a,b,c);
cout<<(power(a,b,c*c)/c+c)%c<<endl;
}
[3] 简单的排列最优化题
\(n^{2}\) 的解法是显然的
考虑如何 \(O(n)\) 做，需要我们从上一个状态转移到当前状态，我们把数和贡献分别分成 \(p_i\le i\) 和 \(p_i\gt i\) 两部分，首先简单手摸一下可以发现每次两部分答案的增加/减小量恰好就是两部分的数字之和，而每次两部分答案显然会一个增加 \(1\)，一个减小 \(1\)（排列的性质）
需要考虑的就是边界情况，边界有一个为最左端与最右端的转换，还有一个 \(p_i=i\) 时的转换，前者可以直接套式子，对于后者，因为我们只关心数量，因此考虑记录没一个时刻有几个到达该转换的值即可
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
template<typename T>
void read(T& x){
x=0;bool sym=0;char c=getchar();
while(!isdigit(c)){sym^=(c=='-');c=getchar();}
while(isdigit(c)){x=x*10+c-48;c=getchar();}
if(sym)x=-x;
}
template<typename T,typename... Args>
void read(T& x,Args&... args){
read(x);read(args...);
}
#define int long long
int a,b,c;
int power(int a,int t,int p){
int base=a,ans=1;
while(t){
if(t&1){
ans=ans*base%p;
}
base=base*base%p;
t>>=1;
}
return ans;
}
int n;
int p[10000001];
int rcnt,lcnt,rtot,ltot;
int dx[10000001];
signed main(){
read(n);
for(int i=1;i<=n;++i){
read(p[i]);
}
for(int i=1;i<=n;++i){
if(p[i]<=i){
lcnt++;
ltot+=(i-p[i]);
}
else{
dx[p[i]-i]++;
rcnt++;
rtot+=(p[i]-i);
}
}
int ans=ltot+rtot,ansid=0;
for(int i=1;i<=n-1;++i){
rtot-=rcnt;
rcnt-=dx[i];
ltot+=lcnt;
lcnt+=dx[i];
ltot-=n-p[n-i+1]+1;
lcnt--;
if(p[n-i+1]>1){
dx[p[n-i+1]+i-1]++;
rtot+=p[n-i+1]-1;
rcnt++;
}
else{
lcnt++;
}
if(ltot+rtot<ans){
ans=ltot+rtot;
ansid=i;
}
}
cout<<ansid<<" "<<ans<<endl;
}
[1] mine
设计 \(f_{i,0/1/2}\) 表示进行到第 \(i\) 位时，需要下一位是雷/不是雷，或者该位是雷的方案数
当该为是 \(0\) 时，应从上一位的 \(0\) 状态转移，并要求下一位为 \(0\)
当该位是 \(1\) 时，可以从上一位的 \(0\) 状态转移，并要求下一位为雷，或者从上一位的 \(2\) 状态转移，要求下一位为 \(0\)
当该为是 \(2\) 时，应从上一位的 \(2\) 状态转移，并要求下一位是雷
当该为是雷时，应从上一位的 \(1\) 状态转移
起始状态需要注意，起始的 \(i\) 需要特殊处理
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#ifdef ONLINE_JUDGE
#define endl '\n'
template<typename T>
void read(T& x){
x=0;bool sym=0;char c=getchar();
while(!isdigit(c)){sym^=(c=='-');c=getchar();}
while(isdigit(c)){x=x*10+c-48;c=getchar();}
if(sym)x=-x;
}
template<typename T,typename... Args>
void read(T& x,Args&... args){
read(x);read(args...);
}
//#else
//#include<hdk/lib.h>
//#endif
string s;
int f[1000001][3];
const int p=1e9+7;
/* 0 mine : 1 mine : is mine*/
signed main(){
cin>>s;
if(s[0]=='0' or s[0]=='?') f[0][0]=1;
if(s[0]=='1' or s[0]=='?') f[0][1]=1;
if(s[0]=='*' or s[0]=='?') f[0][2]=1;
for(int i=1;i<=s.length()-1;++i){
if(s[i]=='0' or s[i]=='?'){
f[i][0]+=f[i-1][0];
}
if(s[i]=='1' or s[i]=='?'){
f[i][0]+=f[i-1][2];
f[i][1]+=f[i-1][0];
}
if(s[i]=='2' or s[i]=='?'){
f[i][1]+=f[i-1][2];
}
if(s[i]=='*' or s[i]=='?'){
f[i][2]+=f[i-1][1]+f[i-1][2];
}
f[i][0]%=p;
f[i][1]%=p;
f[i][2]%=p;
// cout<<f[i][0]<<" "<<f[i][1]<<" "<<f[i][2]<<endl;
}
cout<<(f[s.length()-1][0]+f[s.length()-1][2])%p;
}
[2] 序列
从 \(1\) 到 \(n\) 枚举 \(r\) ，设 \(f_{i}\) 表示区间 \([i,r]\) 中仅出现一次的数的个数，考虑 \(r\) 到
\(r+1\) 的变化
- 若 \(a_{r+1}\) 还未出现过，则 \([1,r+1]\) 内的 \(f\) 都加 \(1\)
- 否则记 \(a_{r+1}\) 上次出现时的下标为 \(j\),上上次出现时的下标为 \(k\)，则 \([j+1,r+1]\) 内的 \(f\) 值都加 \(1\), \([k+1,j]\) 内的 \(f\) 值都减 \(1\)
序列的合法条件即为任意时刻 \(f_{i}\) 的值均大于零, 用线段树维护加减操作和区间最小值,同时记录每个值前两次出现的位置即可
这个做法是很经典的套路,可以用来统计具有某种特征的区间的数量,枚举区间右端点 ,在所有左端点维护区间的信息,即可快速统计所有区间.
点击查看代码
#include<bits/stdc++.h>
using namespace std;
//#ifdef ONLINE_JUDGE
#define endl '\n'
template<typename T>
void read(T& x){
x=0;bool sym=0;char c=getchar();
while(!isdigit(c)){sym^=(c=='-');c=getchar();}
while(isdigit(c)){x=x*10+c-48;c=getchar();}
if(sym)x=-x;
}
template<typename T,typename... Args>
void read(T& x,Args&... args){
read(x);read(args...);
}
//#else
//#include<hdk/lib.h>
//#endif
struct tree{
int l,r;
int lazy;
int minn;
}t[800001];
#define tol (id*2)
#define tor (id*2+1)
#define mid(l,r) mid=((l)+(r))/2
void build(int id,int l,int r){
t[id].l=l;t[id].r=r;
t[id].lazy=t[id].minn=0;
if(l==r){
return;
}
int mid(l,r);
build(tol,l,mid);
build(tor,mid+1,r);
}
void pushdown(int id){
if(t[id].lazy){
t[tol].lazy+=t[id].lazy;
t[tor].lazy+=t[id].lazy;
t[tol].minn+=t[id].lazy;
t[tor].minn+=t[id].lazy;
t[id].lazy=0;
}
}
void change(int id,int l,int r,int k){
// cout<<"change "<<id<<" "<<l<<" "<<r<<" "<<t[id].l<<" "<<t[id].r<<" "<<k<<endl;
if(l<=t[id].l and t[id].r<=r){
t[id].minn+=k;
t[id].lazy+=k;
return;
}
pushdown(id);
if(r<=t[tol].r) change(tol,l,r,k);
else if(l>=t[tor].l) change(tor,l,r,k);
else{
int mid(t[id].l,t[id].r);
change(tol,l,mid,k);
change(tor,mid+1,r,k);
}
t[id].minn=min(t[tol].minn,t[tor].minn);
}
int ask(int id,int l,int r){
if(l<=t[id].l and t[id].r<=r){
return t[id].minn;
}
pushdown(id);
if(r<=t[tol].r){
return ask(tol,l,r);
}
else if(l>=t[tor].l){
return ask(tor,l,r);
}
else{
int mid(t[id].l,t[id].r);
return min(ask(tol,l,mid),ask(tor,mid+1,r));
}
}
map<int,int>mp;
int cnt=0;
int T,n;
int a[200001];
int last[200001],l_last[200001];
int main(){
cin>>T;
while(T--){
cnt=0;
read(n);
build(1,1,n);
memset(last,0,sizeof last);
memset(l_last,0,sizeof l_last);
mp.clear();
for(int i=1;i<=n;++i){
read(a[i]);
if(!mp.count(a[i])) mp[a[i]]=++cnt;
a[i]=mp[a[i]];
}
bool flag=false;
for(int i=1;i<=n;++i){
if(!last[a[i]]){
// cout<<"add [1,"<<i+1<<"]"<<1<<endl;
last[a[i]]=i;
change(1,1,i,1);
}
else{
change(1,last[a[i]]+1,i,1);
// cout<<"add ["<<last[a[i]]+1<<","<<i+1<<"]"<<1<<endl;
change(1,l_last[a[i]]+1,last[a[i]],-1);
// cout<<"add ["<<l_last[a[i]]+1<<","<<last[a[i]]<<"]"<<-1<<endl;
l_last[a[i]]=last[a[i]];
last[a[i]]=i;
}
if(ask(1,1,i)<=0){
// cout<<i<<" "<<ask(1,1,i)<<" ";
cout<<"boring"<<endl;
flag=true;
break;
}
}
if(!flag){
cout<<"non-boring"<<endl;
}
}
}
[2] Leagcy
线段树优化建图板子题
考虑到，如果我们需要从节点 \(x\) 向 \([l,r]\) 中的所有节点连边，我们可以考虑建一颗线段树，分别将 \(x\) 与符合要求的区间节点连边，再将区间节点与其子节点连边权为 \(0\) 的边即可
本题既有单点连接区间，也有区间连接单点，对两种情况分别建一颗线段树即可，区间连接单点则需要建儿子指向父亲的线段树
点击查看代码
#include<bits/stdc++.h>
using namespace std;
//#ifdef ONLINE_JUDGE
#define endl '\n'
template<typename T>
void read(T& x){
x=0;bool sym=0;char c=getchar();
while(!isdigit(c)){sym^=(c=='-');c=getchar();}
while(isdigit(c)){x=x*10+c-48;c=getchar();}
if(sym)x=-x;
}
template<typename T,typename... Args>
void read(T& x,Args&... args){
read(x);read(args...);
}
//#else
//#include<hdk/lib.h>
//#endif
#define int long long
struct tree{
int l,r;
}t[400001];
int n,m,st;
int dis[1000001];
int leaf[100001];
bool vis[1000001];
#define mid(l,r) mid=((l)+(r))/2
#define tol (id*2)
#define tor (id*2+1)
const int dx=5e5;
struct edge{
int to,w;
};
vector<edge>e[1000001];
void build(int id,int l,int r){
t[id].l=l;t[id].r=r;
if(l==r){
leaf[l]=id;
return;
}
int mid(l,r);
e[id].push_back({tol,0});
e[id].push_back({tor,0});
e[tol+dx].push_back({id+dx,0});
e[tor+dx].push_back({id+dx,0});
build(tol,l,mid);
build(tor,mid+1,r);
}
void connect(int id,int l,int r,int to,int w,int tp){
if(l<=t[id].l and t[id].r<=r){
if(tp){
e[id+dx].push_back({to,w});
}
else{
e[to].push_back({id,w});
}
return;
}
int mid(t[id].l,t[id].r);
if(r<=mid) connect(tol,l,r,to,w,tp);
else if(l>mid) connect(tor,l,r,to,w,tp);
else{
connect(tol,l,mid,to,w,tp);
connect(tor,mid+1,r,to,w,tp);
}
}
struct node{
int id,val;
bool operator <(const node &A)const{
return val>A.val;
}
};
void dij(int s){
priority_queue<node>q;
memset(dis,0x3f,sizeof dis);
dis[leaf[s]+dx]=0;
q.push({leaf[s]+dx,dis[leaf[s]+dx]});
while(!q.empty()){
node u=q.top();
q.pop();
if(vis[u.id]) continue;
for(edge i:e[u.id]){
if(dis[i.to]>dis[u.id]+i.w){
dis[i.to]=dis[u.id]+i.w;
q.push({i.to,dis[i.to]});
}
}
}
}
signed main(){
read(n,m,st);
build(1,1,n);
for(int i=1;i<=m;++i){
int op,from,to,l,r,val;
read(op);
if(op==1){
read(from,to,val);
e[leaf[from]].push_back({leaf[to],val});
}
else{
read(to,l,r,val);
connect(1,l,r,leaf[to],val,op&1);
}
}
for(int i=1;i<=n;++i){
e[leaf[i]].push_back({leaf[i]+dx,0});
e[leaf[i]+dx].push_back({leaf[i],0});
}
dij(st);
for(int i=1;i<=n;++i){
if(dis[leaf[i]]==0x3f3f3f3f3f3f3f3f) cout<<"-1 ";
else cout<<dis[leaf[i]]<<" ";
}
}
[2] DP 搬运工 2
考虑从 \(1\) 到 \(n\) 插入所有数到序列中
这样做的话就会有一个很好的性质，就是不管这个数插到哪里，它总是最大的数，所以总会使合法的状态增加 \(1\)（除非插在两边）
反例就是当插入的这个数破坏了原来合法的一组的时候，同时会让答案减一，这样就相当于不变了
设 \(f_{i,j}\) 表示考虑前 \(i\) 位，合法 \(j\) 组的方案数，考虑从 \(i-1\) 转移，当我们插入 \(i\) 的时候，一共有 \(2j\) 个位置（在 \(j\) 个本来合法的位置两边插入）能够增加答案的同时破坏一个答案，一共有 \(2\) 个位置（在整个序列首尾插入）能不增加答案，其余都是增加 \(1\) 的方案
直接转移即可
点击查看代码
#include<bits/stdc++.h>
using namespace std;
//#ifdef ONLINE_JUDGE
#define endl '\n'
template<typename T>
void read(T& x){
x=0;bool sym=0;char c=getchar();
while(!isdigit(c)){sym^=(c=='-');c=getchar();}
while(isdigit(c)){x=x*10+c-48;c=getchar();}
if(sym)x=-x;
}
template<typename T,typename... Args>
void read(T& x,Args&... args){
read(x);read(args...);
}
//#else
//#include<hdk/lib.h>
//#endif
int n,k;
int f[2001][2001];
const int p=998244353;
int main(){
read(n,k);
f[1][0]=1;f[2][0]=2;
for(int i=3;i<=n;++i){
for(int j=0;j<=min(i/2,k);++j){
f[i][j]=(f[i][j]+f[i-1][j]*1ll*(2*j+2))%p;
f[i][j+1]=(f[i][j+1]+f[i-1][j]*1ll*(i-2*j-2))%p;
}
}
cout<<(f[n][k]+p)%p<<endl;
}