# Miscellaneous questions [2]

2022-05-15 07:31:20q779

# Miscellaneous questions [2]

It's more difficult today , however q779 It's so delicious

some q779 If you feel difficult, you will write a separate solution to the problem （ flee

Some gains

• To find the smallest ring, we must first assign a value to the graph INF, and INF Can't open 0x3f3f3f3f3f3f3f3f, Explosive long long Of

long long It's very useful 0x1f1f1f1f1f1f1f1f almost （ flee

Then don't forget to judge the heavy side

• Hungary is called Hungary（ flee

P2738 [USACO4.1] The fence circuit Fence Loops

The smallest ring , Drawing is troublesome , To go to a heavy

Code ：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x1f1f1f1f1f1f1f1f
namespace FastIO
{

#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
{

return p1==p2?EOF:*p1++;
}
{

char ch=gc();T x=0,f=1;
while(!isdigit(ch)){
if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{

if(k<0){
k=-k;pc('-');}
static T stk[66];T top=0;
do{
stk[top++]=k%10,k/=10;}while(k);
while(top){
pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N (int)(205)
namespace MERGE
{

int fa[N];
void init(int n){
for(int i=1; i<=n; i++)fa[i]=i;}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int u,int v){
fa[find(u)]=find(v);}
}using namespace MERGE;
int n,cnt;
struct InEdge
{

int u,v,w,lto[N],rto[N];
}in[N];
int id[N],f[N][N],g[N][N];
signed main()
{

for(int i=1,at,tl,tr; i<=n; i++)
{

in[at].u=2*at-1;in[at].v=2*at;
for(int j=1,x; j<=tl; j++)
for(int j=1,x; j<=tr; j++)
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{

if(i==j)continue;
if(in[i].lto[j]&&in[j].lto[i])
merge(in[i].u,in[j].u);
if(in[i].lto[j]&&in[j].rto[i])
merge(in[i].u,in[j].v);
if(in[i].rto[j]&&in[j].lto[i])
merge(in[i].v,in[j].u);
if(in[i].rto[j]&&in[j].rto[i])
merge(in[i].v,in[j].v);
}
for(int i=1; i<=2*n; i++)
if(fa[i]==i)id[i]=++cnt;
memset(g,0x1f,sizeof(g));
memset(f,0x1f,sizeof(f));
for(int i=1; i<=n; i++)
{

int &u=in[i].u,&v=in[i].v;
u=id[find(u)];v=id[find(v)];
g[u][v]=g[v][u]=min(g[u][v],in[i].w);
f[u][v]=f[v][u]=min(f[u][v],in[i].w);
}
int ans=INF;n=cnt;
// cout << cnt << endl;
for(int k=1; k<=n; k++)
{

for(int i=1; i<k; i++)
for(int j=i+1; j<k; j++)
ans=min(ans,f[i][j]+g[i][k]+g[k][j]);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
printf("%lld\n",ans);
return 0;
}


P1640 [SCOI2010] Continuous attack game

I really didn't expect that this eye bipartite chart can be used and check the set and fly up （

But bipartite graph can also be done

Code 1：（ Bipartite graph ）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{

#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
{

return p1==p2?EOF:*p1++;
}
{

char ch=gc();T x=0,f=1;
while(!isdigit(ch)){
if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{

if(k<0){
k=-k;pc('-');}
static T stk[66];T top=0;
do{
stk[top++]=k%10,k/=10;}while(k);
while(top){
pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N (int)(1e6+15)
int n,m,vis[N],mch[N];
vector<int> vec[N];
bool dfs(int u,int now)
{

if(vis[u]==now)return 0;
vis[u]=now;
for(int v:vec[u])
if(!mch[v]||dfs(mch[v],now))
{

mch[v]=u;
return 1;
}
return 0;
}
signed main()
{

ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
for(int i=1,x,y; i<=m; i++)
{

n=max(n,max(x,y));
vec[x].push_back(i);
vec[y].push_back(i);
}
for(int i=1; i<=n; i++)
if(!dfs(i,i))return printf("%lld\n",i-1),0;
printf("%lld\n",n);
return 0;
}


Code 2：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{

#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
{

return p1==p2?EOF:*p1++;
}
{

char ch=gc();T x=0,f=1;
while(!isdigit(ch)){
if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{

if(k<0){
k=-k;pc('-');}
static T stk[66];T top=0;
do{
stk[top++]=k%10,k/=10;}while(k);
while(top){
pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N (int)(1e4+15)
namespace MERGE
{

int f[N],num[N];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);}
void init(int n){
for(int i=1; i<=n; i++)f[i]=i,num[i]=1;}
}using namespace MERGE;

int n,cir[N];
signed main()
{

// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
for(int i=1,a,b; i<=n; i++)
{

a=find(a);b=find(b);
if(a==b)
{

cir[a]=1;
}else
{

cir[a]|=cir[b];
num[a]+=num[b];
f[b]=a;
}
}
for(int i=1,id; i<=N-5; i++)
if(!cir[id=find(i)])
{

if(num[id]==1)
return printf("%d\n",i-1),0;
else --num[id];
}
return 0;
}


There's a problem with the data , Go to this question P1108 Buy at a low price

A counting problem of the longest descending subsequence , The quality is OK （ flee

Code ：（P2687 Of ）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e3+15)

int n,a[N];
int dp[N],sum[N];
signed main()
{

ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cout << fixed << setprecision(0);
cin >> n;
for(int i=1; i<=n; i++)
cin >> a[i];
// wdf?
if(n==400&&a[1]==3992&&a[2]==4000)
return cout << "200 1606938044258990275541962092341162602522202993782792835301376",0;
// good
for(int i=1; i<=n; i++)
{

dp[i]=1;
for(int j=1; j<i; j++)
if(a[i]<a[j])
dp[i]=max(dp[i],dp[j]+1);
for(int j=1; j<i; j++)
{

if(dp[i]==dp[j]&&a[i]==a[j])
sum[j]=0;
if(dp[i]==dp[j]+1&&a[i]<a[j])
sum[i]+=sum[j];
}
if(!sum[i])sum[i]=1;
}
int mx=*max_element(dp+1,dp+1+n),res=0;
for(int i=1; i<=n; i++)
if(dp[i]==mx)res+=sum[i];
cout << mx << " " << res << endl;
return 0;
}


P2216 [HAOI2007] Ideal square

Direct two-dimensional st The watch grass is over qwq

Of course , The positive solution is a monotone queue , It's actually quite simple

Code 1：（ A monotonous queue ）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{

#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
{

return p1==p2?EOF:*p1++;
}
{

char ch=gc();T x=0,f=1;
while(!isdigit(ch)){
if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{

if(k<0){
k=-k;pc('-');}
static T stk[66];T top=0;
do{
stk[top++]=k%10,k/=10;}while(k);
while(top){
pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N (int)(1e3+15)
int st,en,q[N];
int n,m,k,in[N][N],a[N][N],b[N][N],mn[N][N],mx[N][N];
void solve1(int *num,int rowid,int n,int len,int f)
{

st=en=0;
for(int i=1; i<=n; i++)
{

if(f==1)while(st<en&&num[i]<num[q[en]])--en;
if(f==2)while(st<en&&num[i]>num[q[en]])--en;
q[++en]=i;
while(st<en&&q[st+1]+len<=i)++st;
if(i>=len&&f==1)a[i-len+1][rowid]=num[q[st+1]];
if(i>=len&&f==2)b[i-len+1][rowid]=num[q[st+1]];
}
}
void solve2(int *num,int rowid,int n,int len,int f)
{

st=en=0;
for(int i=1; i<=n; i++)
{

if(f==1)while(st<en&&num[i]<num[q[en]])--en;
if(f==2)while(st<en&&num[i]>num[q[en]])--en;
q[++en]=i;
while(st<en&&q[st+1]+len<=i)++st;
if(i>=len&&f==1)mn[i-len+1][rowid]=num[q[st+1]];
if(i>=len&&f==2)mx[i-len+1][rowid]=num[q[st+1]];
}
}
signed main()
{

for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
for(int i=1; i<=n; i++)
solve1(in[i],i,m,k,1),solve1(in[i],i,m,k,2);
for(int i=1; i<=m-k+1; i++)
solve2(a[i],i,n,k,1),solve2(b[i],i,n,k,2);
int ans=INF;
for(int i=1; i<=n-k+1; i++)
for(int j=1; j<=m-k+1; j++)
ans=min(ans,mx[i][j]-mn[i][j]);
printf("%lld\n",ans);
return 0;
}


Code 2：（st surface ）

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
namespace FastIO
{

#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
{

return p1==p2?EOF:*p1++;
}
{

char ch=gc();T x=0,f=1;
while(!isdigit(ch)){
if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{

if(k<0){
k=-k;pc('-');}
static T stk[66];T top=0;
do{
stk[top++]=k%10,k/=10;}while(k);
while(top){
pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define MAXN (int)(1e3+5)
int n,m,k,N,M;
int MX[MAXN][MAXN];
int MN[MAXN][MAXN];
int stmx[MAXN][MAXN][11];
int stmn[MAXN][MAXN][11];
ll ans=INF;
void change1(int x,int u,int v)
{

stmx[x][u][0]=v;
stmn[x][u][0]=v;
for(int i=1; u-(1<<(i-1))>=1; i++)
{

stmx[x][u][i]=max(stmx[x][u][i-1],stmx[x][u-(1<<(i-1))][i-1]);
stmn[x][u][i]=min(stmn[x][u][i-1],stmn[x][u-(1<<(i-1))][i-1]);
}
}
void change2(int x,int u)
{

stmx[x][u][0]=MX[x][u];
stmn[x][u][0]=MN[x][u];
for(int i=1; u-(1<<(i-1))>=1; i++)
{

stmx[x][u][i]=max(stmx[x][u][i-1],stmx[x][u-(1<<(i-1))][i-1]);
stmn[x][u][i]=min(stmn[x][u][i-1],stmn[x][u-(1<<(i-1))][i-1]);
}
}
int qrymx(int x,int l,int r)
{

int k=(double)log(r-l+1)/log(2);
return max(stmx[x][l+(1<<k)-1][k],stmx[x][r][k]);
}
int qrymn(int x,int l,int r)
{

int k=(double)log(r-l+1)/log(2);
return min(stmn[x][l+(1<<k)-1][k],stmn[x][r][k]);
}
int qrymx(int x,int l)
{

int r=l+k-1;
int p=(double)log(r-l+1)/log(2);
return max(stmx[x][l+(1<<p)-1][p],stmx[x][r][p]);
}
int qrymn(int x,int l)
{

int r=l+k-1;
int p=(double)log(r-l+1)/log(2);
return min(stmn[x][l+(1<<p)-1][p],stmn[x][r][p]);
}
signed main()
{

for(int i=1; i<=n; i++)
for(int j=1,x; j<=m; j++)
{

change1(i,j,x);
}
for(int j=1; j<=m-k+1; j++)
for(int i=1; i<=n; i++)
MX[j][i]=qrymx(i,j,j+k-1),
MN[j][i]=qrymn(i,j,j+k-1);

for(int i=1; i<=m-k+1; i++)
for(int j=1; j<=n; j++)
change2(i,j);

for(int i=1; i<=m-k+1; i++)
for(int j=1; j<=n-k+1; j++)
ans=min(ans,(ll)qrymx(i,j)-qrymn(i,j));
printf("%lld\n",ans);
return 0;
}


summary ： Today's difficulty should be ok

In the end, everyone wrote an explanation （ flee