省选模拟3.26
A. 灯
一开始读错题了，以为要维护极长的连续段最长的长度，然后看了 \(1h\) 不会做
又读了一遍题，发现是简单根号分治
个数少的直接暴力改，个数多的预处理出来相互贡献的关系
然后在修改少的的时候，把大的的贡献修改
Code
#include
#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define rint signed
#define meow(args...) fprintf(stderr,args)
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int B=300;
int n,m,q,ans;
int a[100010],b[100010],cnt[100010],p;
int id[100010],C;
int v[310][310],V[100010];
vectorvec,pos[100010];
bool on[100010];
inline void solve(int x){
if(cnt[x]=B) V[a[L-1]]--;
if(cnt[a[L+1]]>=B) V[a[L+1]]--;
}
}else{
ans+=cnt[x];
for(auto L:pos[x]){
if(on[a[L-1]]) ans--;
if(on[a[L+1]]) ans--;
if(cnt[a[L-1]]>=B) V[a[L-1]]++;
if(cnt[a[L+1]]>=B) V[a[L+1]]++;
}
}
}else{
if(on[x]){
ans-=cnt[x];ans+=V[x];
for(auto L:vec) if(on[L]) ans+=v[id[x]][id[L]];
}else{
ans+=cnt[x];ans-=V[x];
for(auto L:vec) if(on[L]) ans-=v[id[x]][id[L]];
}
}
on[x]^=1;
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("light.in","r",stdin);
freopen("light.out","w",stdout);
n=read(),m=read(),q=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) if(a[i]!=a[i-1]) b[++p]=a[i];n=p;memset(a,0,sizeof(a));
for(int i=1;i<=n;i++) a[i]=b[i];
for(int i=1;i<=n;i++) cnt[a[i]]++;
for(int i=1;i<=m;i++) if(cnt[i]>=B){
vec.emplace_back(i);id[i]=++C;
}
for(int i=1;i<=n;i++) if(cnt[a[i]]=B){
if(cnt[a[i-1]]>=B) v[id[a[i]]][id[a[i-1]]]++;
if(cnt[a[i+1]]>=B) v[id[a[i]]][id[a[i+1]]]++;
}
for(int i=1,x;i<=q;i++){
x=read();solve(x);
printf("%lld\n",ans);
}
return 0;
}
B. 十字路口
对于同一盏灯在两个不同时间都是红灯
设剩余时间分别是 \(a,b\) ，观测时间分别是 \(A,B\) ，周期是 \(T\)
那么存在这样的关系 \(A+a\equiv B+b\mod T\) ，将这样的关系由时间大的向时间小的连边
如果最后出现了环的话，那么就形成了周期，那么最小的环就是最小的周期
可以暴力连边跑 \(floyd\) 求最小环
也可以前缀和优化建边，这时用 \(dfs\) 求出的环就是最小环
Code
#include
#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define rint signed
#define meow(args...) fprintf(stderr,args)
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,m,ans;
int a[100010],now;
int dis[100010];
int head[100010],ver[2000010],to[2000010],edge[2000010],tot;
bool in[100010],vis[100010];
vectorvec[100010];
mapmp[100010];
inline bool cmp(int x,int y){return vec[x][now]>vec[y][now];}
inline void add(int x,int y,int z){
if(mp[x].find(y)!=mp[x].end()) return;mp[x][y]=1;
ver[++tot]=y;edge[tot]=z;to[tot]=head[x];head[x]=tot;
}
void dfs(int x,int d){
if(ans||vis[x]) return ;
dis[x]=d;in[x]=1;vis[x]=1;
for(int i=head[x];i;i=to[i]){
int y=ver[i];
if(in[y]){
ans=d-dis[y]+edge[i];
if(ans) return;
}else dfs(y,d+edge[i]);
if(ans) return;
}
in[x]=0;
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("crossing.in","r",stdin);
freopen("crossing.out","w",stdout);
m=read(),n=read();
for(int i=1;i<=n;i++){
vec[i].emplace_back(0);
for(int j=1;j<=m;j++) vec[i].emplace_back(read());
}
for(int i=1;i<=n;i++) a[i]=i;
for(int i=1;i<=m;i++){
now=i;sort(a+1,a+1+n,cmp);
for(int i=1;i C. 密室逃脱
人的操作是可逆的
于是把能走都一起的人都合并在一起
于是设 \(f_{i,j}\) 表示考虑 \(i\) 个点，在第 \(i\) 个点恰好存在 \(j\) 个人时，最多能有多少人
转移时分类讨论
-
\(j
-
\(a_i\leq j
-
\(a_i+b_i\leq j\) 时，可以随便走转移到 \(f_{i+1,j}\)
Code
#include
#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define rint signed
#define meow(args...) fprintf(stderr,args)
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,m,V,ans;
int f[1010][20010];
int a[1010],b[1010];
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("escape.in","r",stdin);
freopen("escape.out","w",stdout);
n=read(),V=m=read();
for(int i=1;i