[数据结构与算法]Codeforces Round #731 (Div. 3) （E (dp) + F(二分+st表) + G(dfs判环) ）

E. Air Conditioners

（dp）

对于第i个格子，如果我们单独考虑其右边的所有空调（包括第i格的空调，如果有的话），那么可以通过dp解决。
r[i]=min(c[i],r[i+1]+1) r[i]表示i以及i右边的空调影响下，i位置的最低温度。

同理可以求出l[i] ，那么第i个位置的答案就是min(l[i],r[i])

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define ll long long
#define pii pair<int,int>
#define re register
const int maxn = 3e5+10;
const int mx = 40;
const int mod = 1e9+7;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
int n,k;
ll r[maxn],l[maxn],c[maxn];//只考虑右边 /左边 包括自己的空调 最优解 dp
//r[i]=min(r[i+1]+1,c[i])
//l[i]=min(l[i-1]+1,c[i])
int a[maxn];
ll t[maxn];
int main()
{
    int T;cin>>T;
    while(T--) 
    {
        scanf("%d %d",&n,&k);
        for(int i=1;i<=n;i++) c[i]=inf;
        for(int i=1;i<=k;i++) scanf("%d",a+i);
        for(int i=1;i<=k;i++) 
        {
            scanf("%I64d",t+i);
            c[a[i]]=t[i];
        }
        r[n]=c[n];
        for(int i=n-1;i>=1;i--) r[i]=min(r[i+1]+1,c[i]);
        l[1]=c[1];
        for(int i=2;i<=n;i++) l[i]=min(l[i-1]+1,c[i]);
        for(int i=1;i<=n;i++) 
        {
            cout<<min(l[i],r[i])<<' ';
        }
        puts("");
    }
    return 0;
} 

G. How Many Paths?

给定有向图，输出1到各个顶点的路径数 ，无数条则输出-1 ， 大于1条则输出2，等于1条输出1，否则输出0 。无重边，有自环。

刚开始以为需要tarjan然后在dag上dp…但是这个dp实在想不到，不是tle就是mle…

看了答案才明白原来直接dfs判环+剪枝就可以了。

• 因为环上的点一定是无数条。所以我们如果找到了环上一个点，那么往后搜到的所有的点都是无数条。我们在有向图中找环可以用数组标记这个点是否在栈中，如果在，那么此时栈内的点就在一个环上。

• 剪枝：①如果某个点的答案更新为-1了，那么就不需要再往下搜，因为以后的点在以前的dfs过程中已经被更新成-1了。②如果一个点的答案大于1，也不需要继续往下，因为我们大于1条只需要输出2即可，后面的点肯定也是已经大于1了。

由于每个点的答案最多经历1 2 -1三个状态的转变，所以时间复杂度是O(3N)

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define ll long long
#define pii pair<int,int>
#define re register
const int maxn = 4e5+10;
const int mx = 40;
const int mod = 1e9+7;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
int n,m;
vector<int> g[maxn];
//给定有向图 输出1到各个顶点的路径数  无数则1  大于1条则2 
//dfs的过程找环 如果v在栈中的时候 又被dfs到了 那么说明v是环上一点
//从环上某点开始dfs  后面的答案都是-1 
//dfs到-1的点 就不需要继续dfs了 因为后面的点之前都被更新成-1 
//dfs到大于1的点 也不需要继续dfs 因为后面的点也都大于1 且还不能更新成-1
//每个点最多经历 1 2 -1三种状态 所以答案是3*O(n)
//这种dfs判环 仅限于有向图 且可以判自环 
//无向图判环需要并查集
int ans[maxn];
bool instk[maxn];
void init()
{
	for(int i=0;i<=n;i++)
	{
		ans[i]=instk[i]=0;
		g[i].clear();
	}
}
void dfs(int u,bool cycle)//cycle=1 表示该点在环上或者前驱中存在环
{
	instk[u]=1;//入栈
	if(ans[u] != -1) ans[u]++;//搜到的次数+1
	for(int &i:g[u]) 
	{
		if(ans[i] == -1) continue;
		if(cycle) ans[i]=-1,dfs(i,1);//前驱中存在环 答案是-1
		else if(instk[i]) ans[i]=-1,dfs(i,1);//本身就是在环上  答案是-1
		else if(ans[i]<2) dfs(i,0);//剪枝 大于1就没必要搜了 因为此时不可能把他更新为无穷
	}
	instk[u]=0;//出栈
}
int main()
{
	int t;cin>>t;
	while(t--)
	{
		scanf("%d %d",&n,&m);
		init();
		for(int i=1;i<=m;i++) 
		{
			int u,v;
			scanf("%d %d",&u,&v);
			g[u].push_back(v);
		}
		dfs(1,0);
		for(int i=1;i<=n;i++) printf("%d ",ans[i]);
		puts("");
	}
	return 0;	
}

F. Array Stabilization (GCD version)

对于b[1]，执行x步后 b[1]=gcd(a[1],a[2]...,a[1+x])，b[i]同理，所以n步之后b数组各元素一定都相等，且等于gcd(a[1],a[2]...,a[n]) .

我们发现执行的步数具有单调性，也就是说，如果x步之后b数组元素都相等，那么x+1步也一定相等，据此我们可以二分答案，然后利用st表求区间gcd，在O（N）时间完成检验。

时间复杂度是O（nlogn）

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define ll long long
#define pii pair<int,int>
#define re register
const int maxn = 4e5+10;
const int mx = 40;
const int mod = 1e9+7;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
int n;
int lg[maxn];
int f[maxn][30];
int a[maxn];
void st()//预处理区间gcd
{
    for(int i=1;i<=n;i++)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    for(int i=1;i<=n;i++)
        f[i][0]=a[i];
    for(int i=1;(1<<i)<=n;i++)
    {
        for(int j=1;j+(1<<i)-1<=n;j++)
        {
            int a=f[j][i-1];
            int b=f[j+(1<<(i-1))][i-1];
            f[j][i]=__gcd(a,b);
        }
    }
}
int rmq(int l,int r)
{
    int k=lg[r-l+1]-1;
    int a=f[l][k];
    int b=f[r-(1<<k)+1][k];
    return __gcd(a,b); 
}
bool check(int mid) 
{
	int ret=rmq(1,1+mid);
	for(int i=2;i<=n/2;i++) 
	{
		if(rmq(i,i+mid) != ret) return 0;
	}
	return 1;
}
int main()
{
	int t;cin>>t;
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) 
		{
			scanf("%d",a+i);
			a[i+n]=a[i];
		}
		n<<=1;//把环变成链  n变为了2n
		st();
		int l=0,r=n/2;//最多走n/2次
		int ans=0;
		while(l <= r) 
		{
			int mid=(l+r)>>1;
			if(check(mid)) 
			{
				ans=mid;
				r=mid-1;
			}
			else l=mid+1;
		}
		printf("%d\n",ans);
	}
	return 0;	
}