8.19/8/21 [4/4]
A.模拟 B.贪心 C.贪心第一个>=5的,模拟
E.线段树维护矩阵快速幂结果,每个节点保存一个2x2的递推矩阵,利用矩阵乘法结合律a*b+a*c=a*(b+c)区间维护
#include<bits/stdc++.h>
#define ll long long
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
using namespace std;
const int maxn=1e5+10;
const ll mod=1e9+7;
int n,m;
class matrix{public://mod
ll x[2][2];
void e(){memset(x,0,sizeof x);x[0][0]=x[1][1]=1;}
void fill(){x[0][0]=x[1][0]=x[0][1]=1;x[1][1]=0;}
matrix operator *(matrix &m){
matrix ans;memset(ans.x,0,sizeof ans.x);
rep(i,0,1)rep(j,0,1)rep(k,0,1)if(x[i][k]&&m.x[k][j])
ans.x[i][j]=(ans.x[i][j]+x[i][k]*m.x[k][j])%mod;
return ans;
}
matrix operator +(matrix &m){
matrix ans;
rep(i,0,1)rep(j,0,1)ans.x[i][j]=(x[i][j]+m.x[i][j])%mod;
return ans;
}
matrix pow(ll p){
matrix ans;ans.e();matrix t;t.fill();
while(p){if(p&1) ans=t*ans;t=t*t;p>>=1;}return ans;
}
}xx,x0;
matrix getp(ll n){return x0.pow(n);}
class segtree{public:
#define nd node[now]
#define ndl node[now<<1]
#define ndr node[now<<1|1]
struct segnode {int l,r;matrix x,tag;}node[maxn<<2|3];
inline void pushup(int now){nd.x=ndl.x+ndr.x;}
inline void pushdown(int now){
ndl.tag=ndl.tag*nd.tag;
ndr.tag=ndr.tag*nd.tag;
ndl.x=ndl.x*nd.tag;
ndr.x=ndr.x*nd.tag;
nd.tag.e();
}
void maketree(int s,int t,int now=1){
nd.l=s,nd.r=t;nd.tag.e();
if(s==t) {
int x;cin>>x;
nd.x=x0.pow(x-1);
return ;
}
maketree(s,(s+t)/2,now<<1);
maketree((s+t)/2+1,t,now<<1|1);
pushup(now);
}
void update(int s,int t,int now=1){
if(s<=nd.l&&t>=nd.r) {
nd.tag=nd.tag*xx;
nd.x=nd.x*xx;
return ;
}
pushdown(now);
if(s<=ndl.r) update(s,t,now<<1);
if(t>ndl.r) update(s,t,now<<1|1);
pushup(now);
}
ll query(int s,int t,int now=1){
if(s<=nd.l&&t>=nd.r) return nd.x.x[0][0];
pushdown(now);
ll sum=0;
if(s<=ndl.r) sum+=query(s,t,now<<1);
if(t>ndl.r) sum+=query(s,t,now<<1|1);
return sum%mod;
}
}tree;
int main(){
x0.fill();
cin>>n>>m;
tree.maketree(1,n);
int x,a,b;
while(m--){
cin>>x>>a>>b;
if(x==1){
cin>>x;xx=x0.pow(x);
tree.update(a,b);
}else cout<<tree.query(a,b)<<endl;
}
}
7.19/8/11
#578Div2 [6/6]
A.模拟 B.贪心 C.先让n,m互质,然后每次看是否在同一段内
D.二维差分前缀和,取一个最大值
#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
#define per(ii,a,b) for(int ii=b;ii>=a;--ii)
using namespace std;//head
const int maxn=2e3+10,maxm=1e3+10;
int casn,n,m,k;
int pz[maxn][maxn],sum[maxn][maxn];
int main() {IO;
cin>>n>>k;
if(n==k){cout<<2*n;return 0;}
rep(i,1,n){
string s;cin>>s;
rep(j,1,n) pz[i][j]=(s[j-1]=='B');
}
rep(i,1,n){
int mn=n+1,mx=0;
per(j,1,n) if(pz[i][j])mn=j;
rep(j,1,n) if(pz[i][j])mx=j;
if(mx==0){
sum[1][1]++;
continue;
}
if(mx-mn+1<=k){
int x1,x2,y1,y2;
x1=max(1,i-k+1),x2=i+1;
y1=max(1,mx-k+1),y2=mn+1;
++sum[x1][y1];
--sum[x1][y2];
--sum[x2][y1];
++sum[x2][y2];
}
}
rep(i,1,n){
int mn=n+1,mx=0;
per(j,1,n) if(pz[j][i])mn=j;
rep(j,1,n) if(pz[j][i])mx=j;
if(mx==0){
sum[1][1]++;
continue;
}
if(mx-mn+1<=k){
int x1,x2,y1,y2;
x1=max(1,mx-k+1),x2=mn+1;
y1=max(1,i-k+1),y2=i+1;
++sum[x1][y1];
--sum[x1][y2];
--sum[x2][y1];
++sum[x2][y2];
}
}
rep(i,1,n) rep(j,1,n)
sum[i][j]+=sum[i][j-1];
rep(i,1,n) rep(j,1,n)
sum[i][j]+=sum[i-1][j];
int ans=0;
rep(i,1,n) rep(j,1,n) ans=max(ans,sum[i][j]);
cout<<ans<<endl;
}
E.维护ans的哈希,暴力匹配str的前缀和ans的后缀
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
using namespace std;//head
const int maxn=3e6+10,maxm=1e3+10,mod=2520;
int casn,n,m,k;
int val[maxm],g[maxm][20],e[maxm],flag[maxm][mod+10];
int to[maxm][mod+10],vis[maxm][mod+10];
unordered_set<int> cnt;
stack<pii> stk;
int dfs(int now,int sum,int d=1){
if(vis[now][sum]!=0) return vis[now][sum];
stk.push(mp(now,d));
if(flag[now][sum]!=0) {
cnt.clear();
while(!stk.empty()){
pii x=stk.top();stk.pop();
if(x.se<flag[now][sum]) break;
cnt.insert(x.fi);
}
return vis[now][sum]=cnt.size();
}
flag[now][sum]=d;
int x=(sum+val[now])%mod;
return vis[now][sum]=dfs(to[now][x],x,d+1);
}
int main() {IO;
cin>>n;
rep(i,1,n) cin>>val[i];
rep(i,1,n) val[i]=(val[i]%mod+mod)%mod;
rep(i,1,n){
cin>>k;e[i]=k;
rep(j,0,k-1) cin>>g[i][j];
}
rep(i,1,n)rep(j,0,mod-1) to[i][j]=g[i][j%e[i]];
rep(i,1,n)rep(j,0,mod-1){
while(!stk.empty()) stk.pop();
dfs(i,j);
}
cin>>m;
while(m--){
int x,y;cin>>x>>y;
cout<<vis[x][(y%mod+mod)%mod]<<endl;
}
}
6.19/8/12
#375Div2 [5/5]
A.快速幂取模 B.a^b=x 转化为 a^x=b C.求出所有的环长的LCM即可,注意长度为偶数的环要/2
D. 并查集+裸背包DP E.每隔2加一条边,然后跑黑白染色
5.19/8/11
#376Div2 [6/6]
A.模拟即可 B.贪心,先把奇数变成偶数 C.并查集,每个集合取最多颜色
D.每两个相邻字符串,有一个合法的操作次数区间,区间求交
E.问题转化为两个人轮流向后取一个前缀和,变成一个dp问题
F.枚举起点,不断翻倍,取最大的和
4.19/8/10
#377Div2 [6/6]
A.最大-最小 B.字符串模拟 C.$O(n^2)$暴力填数 D.贪心每一个连通块
E.奇数点必定为偶数个,两两建边,然后fleury求欧拉回路
#include <bits/stdc++.h>
#define endl '
'
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
using namespace std;
const int maxn=2e2+10,maxm=1e5+10;
int casn,n,m,k;
struct node{int to,next;};
node e[maxm];int head[maxn],nume;
void init(int n=maxn-5){nume=0;fill_n(head,n+1,0);}
void add(int a,int b){e[++nume]={b,head[a]};head[a]=nume;}
stack<int> stk;
vector<int>que;
int cnt[maxn],used[maxm],vis[maxn];
bool eg1[maxn][maxn],w[maxm],eg2[maxn][maxn],egv[maxn][maxn];
void dfs(int now){
stk.push(now);
for(int i=head[now];i;i=e[i].next)if(!used[i]){
int id=(i+1)/2;
used[id*2]=used[id*2-1]=1;
if(w[i]) {
eg1[now][e[i].to]=1;
eg2[now][e[i].to]=0;
eg2[e[i].to][now]=0;
}
dfs(e[i].to);
break;
}
}
void dfss(int now){
vis[now]=1;
que.push_back(now);
rep(i,1,n) if(!vis[i]&&eg2[i][now]) dfss(i);
}
void fleury(int now){
stk.push(now);
while(!stk.empty()){
int flag=0;
rep(i,1,n) if(eg2[stk.top()][i]>0) {
flag=1;break;
}
if(!flag) stk.pop();
else {
int to=stk.top();
stk.pop();
dfs(to);
}
}
}
int main(){IO;
cin>>casn;
while(casn--){
cin>>n>>m;
memset(eg1,0,sizeof eg1);
memset(eg2,0,sizeof eg2);
memset(egv,0,sizeof egv);
memset(cnt,0,sizeof cnt);
init(n+2);
int ans=n;
rep(i,1,m) {
int a,b;cin>>a>>b;
eg2[a][b]=eg2[b][a]=1;
egv[a][b]=egv[b][a]=1;
cnt[a]++,cnt[b]++;
add(a,b);used[nume]=0,w[nume]=1;
add(b,a);used[nume]=0,w[nume]=1;
}
memset(vis,0,sizeof vis);
rep(i,1,n){
if(vis[i]) continue;
que.clear();
dfss(i);
int la=0;
rep(j,0,que.size()-1)if(cnt[que[j]]&1){
ans--;
if(la){
add(que[j],la);used[nume]=0,w[nume]=0;
add(la,que[j]);used[nume]=0,w[nume]=0;
la=0;
}else la=que[j];
}
while(!stk.empty()) stk.pop() ;
fleury(que[0]);
}
cout<<ans<<endl;
rep(i,1,n)rep(j,1,n) if(egv[i][j]&&!eg1[j][i]) {
cout<<i<<' '<<j<<endl;
}
}
}
F.先移除s,t,求出森林,然后连接必须连s/t的,然后再连接s/t都可以的,最后连接st
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
using namespace std;
const int maxn=5e5+20,maxm=1e6+10;
int casn,n,m,k;
vector<int>g[maxn];
pii e[maxn];
vector<pii> ans;
int d[maxn];
class ufs{public:
int fa[maxn];
void init(int n){rep(i,1,n+1) fa[i]=i;}
int find(int now){return fa[now]==now?now:fa[now]=find(fa[now]);}
inline void unite(int a,int b){fa[find(b)]=find(a);}
inline bool same(int a,int b){return find(a)==find(b);}
}dsu;
int viss[maxn],vist[maxn],vis[maxn];
int main(){
int s,t,ds,dt;
cin>>n>>m;
dsu.init(n);
rep(i,1,m) {
int a,b;cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
e[i]={a,b};
}
cin>>s>>t>>ds>>dt;
rep(i,1,m){
int a=e[i].fi,b=e[i].se;
if(a==s||a==t)continue;
if(b==s||b==t)continue;
if(!dsu.same(a,b)){
dsu.unite(a,b);
d[a]++;
d[b]++;
ans.push_back(e[i]);
}
}
for(auto i:g[s])viss[dsu.find(i)]=1;
viss[s]=1,vist[t]=1;
for(auto i:g[t])vist[dsu.find(i)]=1;
rep(i,1,n) if(!(viss[dsu.find(i)]||vist[dsu.find(i)]))
{cout<<"No";return 0;}
rep(i,1,m){
int a=e[i].fi,b=e[i].se;
if(a==s&&b!=t){
int fa=dsu.find(b);
if(!dsu.same(a,b)&&viss[fa]&&!vist[fa]&&!vis[fa]){
dsu.unite(a,b);
ans.push_back(e[i]);
d[a]++,d[b]++;
vis[fa]=1;
}
}else if(b==s&&a!=t){
int fa=dsu.find(a);
if(!dsu.same(a,b)&&viss[fa]&&!vist[fa]&&!vis[fa]){
dsu.unite(a,b);
d[a]++,d[b]++;
ans.push_back(e[i]);
vis[fa]=1;
}
}
}
rep(i,1,m){
int a=e[i].fi,b=e[i].se;
if(a==t&&b!=s){
int fa=dsu.find(b);
if(!dsu.same(a,b)&&!viss[fa]&&vist[fa]&&!vis[fa]){
dsu.unite(a,b);
ans.push_back(e[i]);
d[a]++,d[b]++;
vis[fa]=1;
}
}else if(b==t&&a!=s){
int fa=dsu.find(a);
if(!dsu.same(a,b)&&!viss[fa]&&vist[fa]&&!vis[fa]){
dsu.unite(a,b);
d[a]++,d[b]++;
ans.push_back(e[i]);
vis[fa]=1;
}
}
}
rep(i,1,m){
int a=e[i].fi,b=e[i].se;
if(a==s&&b==t) continue;
if(a==t&&b==s) continue;
if(!dsu.same(a,b)){
if(a==s&&d[s]>=ds)continue;
if(b==s&&d[s]>=ds)continue;
if(a==t&&d[t]>=dt)continue;
if(b==t&&d[t]>=dt)continue;
dsu.unite(a,b);
d[a]++;
d[b]++;
ans.push_back(e[i]);
}
}
rep(i,1,m){
int a=e[i].fi,b=e[i].se;
if(!dsu.same(a,b)){
dsu.unite(a,b);
d[a]++;
d[b]++;
ans.push_back(e[i]);
}
}
rep(i,1,m){
int a=e[i].fi,b=e[i].se;
if(!dsu.same(a,b)){
cout<<"No";
return 0;
}
}
if(d[s]>ds||d[t]>dt)cout<<"No";
else {
cout<<"Yes"<<endl;
for(auto p:ans)cout<<p.fi<<' '<<p.se<<endl;
}
}
3.19/8/9
#377Div2 [4/6]
A.模拟情况 B.贪心,先优先变成偶数
C.并查集,把一个集合都变成集合内数量最多的颜色
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define pii pair<int,int>
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
using namespace std;
const int maxn=4e5+20,maxm=1e6+10;
int casn,n,m,k;
class ufs{public:
int fa[maxn];
void init(int n){rep(i,1,n) fa[i]=i;}
int find(int now){return fa[now]==now?now:fa[now]=find(fa[now]);}
void unite(int a,int b){
int fx=find(a),fy=find(b);
fa[fy]=fx;
}
}dsu;
int c[maxn],vis[maxn];
int mx[maxn];
pii e[maxn];
unordered_map<int,int> cnt[maxn];
int main(){
cin>>n>>m>>k;
dsu.init(n);
rep(i,1,n)cin>>c[i];
rep(i,1,m){
int a,b;cin>>a>>b;e[i]={a,b};
dsu.unite(a,b);
}
rep(i,1,m){
int a=e[i].fi,b=e[i].se;
if(!vis[a])vis[a]=1,cnt[dsu.find(a)][c[a]]++;
if(!vis[b])vis[b]=1,cnt[dsu.find(a)][c[b]]++;
}
rep(i,1,n){
int mxx=0,mxid=c[i];
for(auto j:cnt[i]) if(j.se>mxx) mxx=j.se,mxid=j.fi;
mx[i]=mxid;
}
int ans=0;
rep(i,1,n){
if(c[i]!=mx[dsu.find(i)]) ans++;
}
cout<<ans<<endl;
}
F.前缀和乱搞
#include <bits/stdc++.h>
#define ll long long
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
using namespace std;
const int maxn=2e5+20,maxm=1e6+10;
int casn,n,m,k;
ll dp[maxn];
int main(){
cin>>n;
rep(i,1,n){
cin>>k;dp[k]++;
}
rep(i,1,maxn-10) dp[i]+=dp[i-1];
ll ans=0;
rep(i,1,maxn-10) if(dp[i]!=dp[i-1]){
ll tmp=0;
for(int j=i;j<maxn-10;j+=i) tmp+=j*(dp[min(maxn-11,j+i-1)]-dp[j-1]);
ans=max(tmp,ans);
}
cout<<ans;
}
2.19/8/8
zoj 月赛18/1
A.贪心即可 J.滑窗+记忆化
E.线段树维护区间乘积,区间取幂,区间乘法,需要用费马大定理降幂
#include<bits/stdc++.h>
#define ll long long
using namespace std;//head
const int maxn=2e5+10,maxm=2e6+10;
const ll INF=0x3f3f3f3f,mod=1e9+7;
int casn,n,m,k;
ll pow_mod(ll a,ll b,ll ans=1) {
while(b) {
if(b&1) (ans*=a)%=mod;
(a*=a)%=mod,b>>=1;
}
return ans;
}
class segtree{public:
#define nd node[now]
#define ndl node[now<<1]
#define ndr node[now<<1|1]
struct segnode{int l,r;ll sum,pw,mul;}node[maxn<<2|3];
inline void pushup(int now){nd.sum=ndl.sum*ndr.sum%mod;}
inline void pushdown(int now){
if(nd.pw>1){
(ndl.pw*=nd.pw)%=mod-1;(ndr.pw*=nd.pw)%=mod-1;
ndl.mul=pow_mod(ndl.mul,nd.pw);ndr.mul=pow_mod(ndr.mul,nd.pw);
ndl.sum=pow_mod(ndl.sum,nd.pw);ndr.sum=pow_mod(ndr.sum,nd.pw);
nd.pw=1;
}
if(nd.mul>1){
(ndl.mul*=nd.mul)%=mod;(ndr.mul*=nd.mul)%=mod;
(ndl.sum*=pow_mod(nd.mul,ndl.r-ndl.l+1))%=mod;
(ndr.sum*=pow_mod(nd.mul,ndr.r-ndr.l+1))%=mod;
nd.mul=1;
}
}
void maketree(int s,int t,int now=1){
nd={s,t,0,1,1};
if(s==t){cin>>nd.sum;return ;}
maketree(s,(s+t)>>1,now<<1);
maketree(((s+t)>>1)+1,t,now<<1|1);
pushup(now);
}
void mul(int s,int t,ll x,int now=1){
if(s<=nd.l&&t>=nd.r){
(nd.mul*=x)%=mod;
(nd.sum*=pow_mod(x,nd.r-nd.l+1))%=mod;
return ;
}
pushdown(now);
if(s<=ndl.r) mul(s,t,x,now<<1);
if(t>ndl.r) mul(s,t,x,now<<1|1);
pushup(now);
}
void pow(int s,int t,ll x,int now=1){
if(s<=nd.l&&nd.r<=t){
(nd.pw*=x)%=mod-1;
nd.sum=pow_mod(nd.sum,x);
nd.mul=pow_mod(nd.mul,x);
return ;
}
pushdown(now);
if(s<=ndl.r) pow(s,t,x,now<<1);
if(t>ndl.r) pow(s,t,x,now<<1|1);
pushup(now);
}
ll query(int s,int t,int now=1){
if(s<=nd.l&&t>=nd.r)return nd.sum;
pushdown(now);
ll sum=1;
if(s<=ndl.r) sum=query(s,t,now<<1);
if(t>ndl.r) (sum*=query(s,t,now<<1|1))%=mod;
return sum;
}
}tree;
ll read(ll ret=0){
char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9'){
ret=ret*10+ch-'0';ch=getchar();
}return ret;
}
int main() {
casn=read();
while(casn--){
n=read();m=read();
tree.maketree(1,n);
while(m--){
int a=read(),b=read(),c=read();
if(a==1) tree.mul(b,c,read());
else if(a==2) tree.pow(b,c,read());
else printf("%lld
",tree.query(b,c));
}
}
return 0;
}
1.19/8/7
#377Div2 [6/6]
A.枚举数量 B.贪心满足 C.枚举情况 D.二分答案
E.sort后从小到大贪心,u_map记录答案
F.求出边双连通分量之后,从最大的边双作为根,bfs所有剩余点,最大的边双内部单独再dfs一下就行
#include <bits/stdc++.h>
#define endl '
'
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
using namespace std;
const int maxn=4e5+20,maxm=1e6+10;
int casn,n,m,k;
int stk[maxn],top,cnt,dfn[maxn],low[maxn],numc,belong[maxn],vis[maxn],sz[maxn];
struct node {int to,next;}e[maxm];int head[maxn],nume;
inline void add(int a,int b){e[++nume]=(node){b,head[a]};head[a]=nume;}
void tdfs(int now,int pre){
dfn[now]=low[now]=++cnt;
stk[top++]=now,vis[now]=1;
for(int i=head[now];i;i=e[i].next){
int to=e[i].to;
if(to==pre) continue;
if(!dfn[to]){tdfs(to,now);low[now]=min(low[now],low[to]);}
else low[now]=min(low[now],dfn[to]);
}
if(low[now]==dfn[now]){
numc++;
int to;
do{to=stk[--top];
belong[to]=numc;
sz[numc]++;
}while(to!=now);
}
}
pii ge[maxn];
map<pii,pii> ed;
queue<int> que;
void dfs(int now,int pre){
if(vis[now]) return ;
vis[now]=1;
int bn=belong[now];
for(int i=head[now];i;i=e[i].next){
int to=e[i].to;
if(belong[to]!=bn){
que.push(to);
vis[to]=1;
pii x=mp(min(to,now),max(to,now));
ed[x]=mp(to,now);
}else {
pii x=mp(min(to,now),max(to,now));
if(ed.find(x)==ed.end()){
ed[x]=mp(now,to);
}
dfs(to,now);
}
}
}
int main(){IO;
cin>>n>>m;
rep(i,1,m){
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
if(a>b) swap(a,b);
ge[i]={a,b};
}
for(int i=1;i<=n;i++) if(!dfn[i]) tdfs(i,i);
int mxid=1;
memset(vis,0,sizeof vis);
rep(i,1,numc) if(sz[mxid]<sz[i])mxid=i;
rep(i,1,n)if(belong[i]==mxid) {dfs(i,i);break;}
while(!que.empty()){
int now=que.front();que.pop();
for(int i=head[now];i;i=e[i].next){
int to=e[i].to;
pii x=mp(min(to,now),max(to,now));
if(belong[to]==mxid)continue;
if(!vis[to]) {
vis[to]=vis[now]+1;
que.push(to);
}
if(vis[to]>vis[now])ed[x]={to,now};
else ed[x]={now,to};
}
}
cout<<sz[mxid]<<endl;
rep(i,1,m) {
pii x=ed[ge[i]];
cout<<x.fi<<' '<<x.se<<endl;
}
}