Bindian Signalizing
断环为链，令 \(l_i\) 表示 \(i\) 左边第一个高于 \(i\) 的，\(r_i\) 表示 \(i\) 右边第一个高于 \(i\) 的，\(cnt_i\) 表示区间 \([l_i,r_i]\) 中高度等于 \(i\) 的，因为为了防重，所以只记录右边高度等于 \(i\) 的。当 \(l_i\) 和 \(r_i\) 对应的位置时还有 \([l_i,i]\) 和 \([i,r_i]\) 两组，否则只有一组。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e6+10;
int n,l[N],r[N],a[N],b[N],cnt[N];
void solve(){
read(n);
int p=0;
for(int i=1;i<=n;i++){
read(a[i]);
if(a[i]>a[p]){
p=i;
}
}
for(int i=0;i<=n;i++){
b[i]=a[(i+p-1)%n+1];
}
for(int i=1;i<=n;i++){
l[i]=i-1;
while(l[i]&&b[i]>=b[l[i]]){
l[i]=l[l[i]];
}
}
for(int i=n-1;i>=0;i--){
r[i]=i+1;
while(r[i]<n&&b[i]>b[r[i]]){
r[i]=r[r[i]];
}
if(r[i]<n&&b[i]==b[r[i]]){
cnt[i]=cnt[r[i]]+1;
r[i]=r[r[i]];
}
}
ll ans=0;
for(int i=0;i<n;i++){
ans+=cnt[i];
if(b[i]<b[0]){
ans+=2;
if(l[i]==0&&r[i]==n){
ans--;
}
}
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[JLOI2015] 战争调度
令 \(f_{u,i}\) 表示子树 \(u\) 内选择 \(i\) 个叶子节点的最大贡献。类似于 HNOI2018 道路，将到点 \(i\) 的路径上选择的状态记录到 dfs 的状态中，剩下直接暴力 dp 即可。
这两道题也说明了将一些状态记录到 dfs 的状态中是一个很重要的 trick。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2010;
int n,m,a[N][20],b[N][20],f[N][N];
void dfs(int u,int dep,int S){
for(int i=0;i<=(1<<dep);i++){
f[u][i]=0;
}
if(!dep){
for(int i=1;i<n;i++){
if(S>>i&1){
f[u][1]+=a[u][i];
}
else{
f[u][0]+=b[u][i];
}
}
return;
}
dfs(u<<1,dep-1,S);
dfs(u<<1|1,dep-1,S);
for(int i=0;i<=(1<<dep);i++){
for(int j=0;j<=min(i,(1<<(dep-1)));j++){
f[u][i]=max(f[u][i],f[u<<1][j]+f[u<<1|1][i-j]);
}
}
dfs(u<<1,dep-1,S|(1<<dep));
dfs(u<<1|1,dep-1,S|(1<<dep));
for(int i=0;i<=(1<<dep);i++){
for(int j=0;j<=min(i,(1<<(dep-1)));j++){
f[u][i]=max(f[u][i],f[u<<1][j]+f[u<<1|1][i-j]);
}
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m);
for(int i=(1<<(n-1));i<(1<<n);i++){
for(int j=1;j<n;j++){
read(a[i][j]);
}
}
for(int i=(1<<(n-1));i<(1<<n);i++){
for(int j=1;j<n;j++){
read(b[i][j]);
}
}
dfs(1,n-1,0);
int ans=0;
for(int i=0;i<=m;i++){
ans=max(ans,f[1][i]);
}
write_endl(ans);
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
[POI2014] RAJ-Rally
先进行拓扑排序，求出拓扑序，以 \(i\) 为终点的最长路 \(f_i\) 和以 \(i\) 为起点的最长路 \(g_i\)。
把拓扑序小于 \(i\) 的节点的集合记为 \(A\)，把拓扑序大于 \(i\) 的节点的集合记为 \(B\)。那么显然删去点 \(i\) 后可能的最长路有三种情况：全部位于 \(A\) 集合内部，全部位于 \(B\) 集合内部，经过一条边从 \(A\) 集合到 \(B\) 集合。因为不会有环不会从 \(B\) 集合到 \(A\) 集合。使用一个数据结构维护 \(f_i(i\in A),g_i(i\in B),f_u+g_v+1(\text{存在边(u,v)})\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=5e5+10;
int n,m,head[N],first[N],deg[N],tot=1,cnt=1,pos[N],idx;
int f[N],g[N];
struct edge{
int v,nxt;
}e[N<<1],G[N<<1];
void add_e(int u,int v){
e[++tot].v=v;
e[tot].nxt=head[u];
head[u]=tot;
}
void add_G(int u,int v){
G[++cnt].v=v;
G[cnt].nxt=first[u];
first[u]=cnt;
}
struct node{
priority_queue<int>a,b;
void push(int x){
a.push(x);
}
void pop(int x){
b.push(x);
}
int top(){
while(b.size()&&a.top()==b.top()){
a.pop(),b.pop();
}
return a.top();
}
}p;
void solve(){
read(n),read(m);
for(int i=1;i<=m;i++){
int u,v;
read(u),read(v);
add_e(u,v);
add_G(v,u);
deg[v]++;
}
queue<int>q;
for(int i=1;i<=n;i++){
if(!deg[i]){
q.push(i);
}
}
while(!q.empty()){
int u=q.front();
q.pop();
pos[++idx]=u;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
deg[v]--;
if(!deg[v]){
q.push(v);
}
}
}
for(int i=1;i<=n;i++){
int u=pos[i];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
f[v]=max(f[v],f[u]+1);
}
}
for(int i=n;i;i--){
int u=pos[i];
for(int i=first[u];i;i=G[i].nxt){
int v=G[i].v;
g[v]=max(g[v],g[u]+1);
}
}
for(int i=1;i<=n;i++){
p.push(g[i]);
}
int ans=p.top(),ans_pos=0;
for(int i=1;i<=n;i++){
int u=pos[i];
p.pop(g[u]);
for(int j=first[u];j;j=G[j].nxt){
int v=G[j].v;
p.pop(f[v]+g[u]+1);
}
int sum=p.top();
if(sum<=ans){
ans=sum;
ans_pos=u;
}
for(int j=head[u];j;j=e[j].nxt){
int v=e[j].v;
p.push(f[u]+g[v]+1);
}
p.push(f[u]);
}
write_space(ans_pos),write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[JRKSJ R6] 第七学区
先考虑 \(O(\log V)\) 的做法怎么做，因为是求区间或的和，所以可以等价于 \(inf=2^{64}-1\) 减去每个区间或中为 \(0\) 部分。令 \(lst_i\) 表示当前位全是 \(0\) 的后缀的个数，\(sum\) 表示当前 \(\sum\limits_{i=0}^{63}lst_i\times 2^i\) 的值，即右端点为 \(i\) 的区间中需要减去的为 \(0\) 的部分的和。如果当前数第 \(i\) 位为 \(0\)，则 \(lst\rightarrow lst_i+1,sum\rightarrow sum+2^i\)，否则 \(sum\rightarrow sum-lst_i\times 2^i,lst_i\rightarrow 0\)。
把上述做法中的所有 \(lst_i\) 写成二进制形式，这样会形成一个大小为 \(64\times \log n\) 的矩阵。令 \(w_j\) 表示第 \(j\) 位哪些 \(lst_i\) 有值。对于当前数第 \(i\) 位为 \(0\)，直接做一个二进制加法即可；对于当前数第 \(i\) 位为 \(1\)，将 \(w_i\) 对应位清 \(0\) 即可。
点击查看代码
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
namespace READ
{
int Read()
{
char ch=getchar();
int s=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s;
}
int tp[10005];
int l,r;
int g1,g2;
void init(int &n)
{
int i,k;
n=Read(),k=Read(),l=1;
for(i=1;i<=k;i++)
tp[i]=Read();
}
int read()
{
if(l>r)
l=Read(),r=Read(),g1=Read(),g2=Read();
return tp[l++]*g1+g2;
}
}
int ans,w[100];
signed main()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int n,len=0,sum=0;
READ::init(n);
for(int i=0;i<n;i++){
int x;
x=READ::read();
sum+=(~x);
int ad=(~x),nxt_ad=0;
for(int j=0;j<=len;j++){
sum-=(w[j]&x)<<j;
w[j]&=(~x);
nxt_ad=ad&w[j];
w[j]^=ad;
ad=nxt_ad;
}
if((i&(-i))==i){
++len;
}
ans-=sum;
}
ans=ans-(n+1)*n/2;
cout<<ans<<endl;
return 0;
}
「SWTR-6」GCDs & LCMs
令 \(g\) 表示 \(\gcd(a,b)\)，则 \(a=xg,b=yg\)，其中 \(x\perp y\)。
原式可以表示为 \(xg+yg+g=xyg\)。
因为 \(g\ge 1\)，所以 \(x+y+1=xy\)。
移项得 \(y+1=x(y-1)\)。
若 \(x=1\) 或 \(y=1\) 或 \(x=y\)，无解。所以 \(x,y\ge 2\) 且 \(x\not= y\)。
\(x=\frac{y+1}{y-1}\ge 2\)，解得 \(y\le 3\)，所以 \(x:y=2:3\) 或 \(3:2\)。
剩下的直接做就行。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3e5+10;
int n,a[N];
map<int,int>cnt;
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
cnt[a[i]]++;
}
sort(a+1,a+n+1);
int ans=0;
for(int i=1;i<=n;i++){
int x=a[i],sum=0;
while(cnt[x]){
sum+=cnt[x]*x;
cnt[x]=0;
if(x%2==0){
x=x/2*3;
}
}
ans=max(ans,sum);
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
Three Days Grace
极差经典套路，枚举一个最小值，求最大值最小为多少。
这里采用dp求这个最大值，令 \(f_j\) 表示当最小值为 \(i\) 时，\(j\) 可以拆出来的数中最大的数最小为多少。
如果从 \(i+1\) 转移到 \(i\)，则可能会被影响的数 \(x\) 一定满足 \(x=ki(k\ge i)\)。用桶维护所有存在的数能分解出的数的最大值，在 \(i\) 变小时，该最大值并不会增加，所以可以用双指针维护。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e6+10,M=5e6+10;
int n,m,buc[M],a[N],f[M],vis[M];
void solve(){
read(n),read(m);
for(int i=1;i<=m;i++){
buc[i]=vis[i]=0;
}
for(int i=1;i<=n;i++){
read(a[i]);
vis[a[i]]=1;
}
int mx=m,ans=m,mn=m;
for(int i=1;i<=m;i++){
f[i]=i;
if(vis[i]){
buc[i]++;
mn=min(mn,i);
}
}
for(int i=m;i;i--){
if(1ll*i*i<=m){
for(int j=i*i;j<=m;j+=i){
if(vis[j]){
buc[f[j]]--;
}
f[j]=min(f[j],f[j/i]);
if(vis[j]){
buc[f[j]]++;
}
}
}
while(!buc[mx]){
mx--;
}
if(i<=mn){
ans=min(ans,mx-i);
}
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
Switch and Flip
对于这种排列问题，一般是对于一个值 \(a_i\)，连一条边 \((i,a_i)\)，这样会形成若干个环。
如果只生成了一个环，任取环上一个点 \(x\)，令 \(y=a_x\)，\(z=a_y\)，交换 \(a_x,a_y\)，再交换 \(a_y,a_z\)，此时 \(a_x'=z,a_y'=a_z,a_z'=y\)，且位置 \(x\) 和 位置 \(y\) 上的硬币是翻面的。接下来，每次操作交换一个翻面的硬币和对应的位置的硬币，且对应位置的硬币未被翻面，直到只剩下两个翻面的硬币，将这两个硬币进行一次操作即可，总操作数 \(n+1\)。
如果生成奇数个环，将任意三个环合并为一个环，剩下的两两合并一个环。如果只生成偶数个环，将所有环两两合并为一个环。令 \(x,y,z\) 分别为三个环上的任意一个点，交换 \(a_x,a_y\)，交换 \(a_y,a_z\)，可以得到上面一个环上有两个翻面的硬币的情况，对三个环的操作数为 \(\sum siz+1\)。如果只交换 \(a_x,a_y\)，可以合并两个环并得到一个环上有两个翻面硬币的情况，操作数为 \(\sum siz\)。总的操作数为 \(n+1\) 或 \(n\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10;
int n,nxt[N],fa[N],siz[N];
int getfa(int u){
if(fa[u]!=u){
fa[u]=getfa(fa[u]);
}
return fa[u];
}
void merge(int u,int v){
u=getfa(u),v=getfa(v);
if(u!=v){
fa[v]=u;
siz[u]+=siz[v];
}
}
vector<int>st;
vector<pii>ans;
void work(){
int pos=st.front();
int Nxt=nxt[pos];
ans.pb(mp(pos,Nxt));
swap(nxt[pos],nxt[Nxt]);
int NXT=nxt[pos];
ans.pb(mp(Nxt,NXT));
swap(nxt[Nxt],nxt[NXT]);
while(nxt[Nxt]!=pos){
ans.pb(mp(Nxt,nxt[Nxt]));
int to=nxt[Nxt];
swap(nxt[Nxt],nxt[to]);
}
while(nxt[pos]!=Nxt){
ans.pb(mp(pos,nxt[pos]));
int to=nxt[pos];
swap(nxt[to],nxt[pos]);
}
ans.pb(mp(Nxt,pos));
write_endl(ans.size());
for(auto x:ans){
write_space(x.first),write_endl(x.second);
}
}
void calc(int posu,int posv){
int x=posu;
while(nxt[x]!=posv){
ans.pb(mp(x,nxt[x]));
int Nxt=nxt[x];
swap(nxt[Nxt],nxt[x]);
}
x=posv;
while(nxt[x]!=posu){
ans.pb(mp(x,nxt[x]));
int Nxt=nxt[x];
swap(nxt[Nxt],nxt[x]);
}
ans.pb(mp(posu,posv));
}
void solve(){
read(n);
for(int i=1;i<=n;i++){
fa[i]=i;
siz[i]=1;
read(nxt[i]);
}
for(int i=1;i<=n;i++){
merge(i,nxt[i]);
}
for(int i=1;i<=n;i++){
if(fa[i]==i){
st.pb(i);
}
}
if(st.size()==1){
work();
return;
}
if(st.size()%2){
for(int i=0;i+3<st.size();i+=2){
ans.pb(mp(st[i],st[i+1]));
swap(nxt[st[i]],nxt[st[i+1]]);
calc(st[i],st[i+1]);
}
int a=st.size()-3,b=a+1,c=b+1;
ans.pb(mp(st[a],st[b]));
swap(nxt[st[a]],nxt[st[b]]);
ans.pb(mp(st[b],st[c]));
swap(nxt[st[b]],nxt[st[c]]);
calc(st[a],st[b]);
}
else{
for(int i=0;i<st.size();i+=2){
ans.pb(mp(st[i],st[i+1]));
swap(nxt[st[i]],nxt[st[i+1]]);
calc(st[i],st[i+1]);
}
}
write_endl(ans.size());
for(auto x:ans){
write_space(x.first),write_endl(x.second);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}