刷题记录 --dp篇

最近在复习之前学过的算法，也有很多之前没接触过的。为了方便复习，把以后刷的题 不论难易都搬过来。
目前在洛谷上面做题，后面应该会做一做cf和leetcode上的比赛
这几天在做的是DP（动态规划），这个之前也没系统的刷过题，自己不看题解基本上是做不出来的，所以多刷一些，提升一下思维能力。
现在刷的这个题单，不从头记录了，就从今天开始把。
第一题：P1176 路径计数2
题目描述

一个N×N 的网格，你一开始在(1,1)，即左上角。每次只能移动到下方相邻的格子或者右方相邻的格子，问到达(N,N)，即右下角有多少种方法。
但是这个问题太简单了，所以现在有M个格子上有障碍，即不能走到这M个格子上。
从左上角走到右下角，每次只能向右或者向下，某些格子无法行走，求方案数。
本题是橙题，思路比较直接
对于正常格子 状态方程为 dp[i][j]=dp[i-1][j]+dp[i][j-1]
障碍格子 dp[i][j]=0;

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=100010;
const ll mod=100003;
int read(){//读入优化
	int x=0;bool f=0;char c=getchar();
	while (c<'0'||c>'9'){if (c=='-')f=1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f?-x:x;
}
ll qpow(ll base, ll n){ll ans = 1; while (n){if (n & 1) ans = ans * base % mod; base = base * base % mod; n >>= 1;} return ans;}
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}
int n,m;
bool a[1010][1010];
int dp[1010][1010]; 
int main(){
	cin>>n>>m;
	int x,y;
	memset(a,false,sizeof(a));
	for(int i=1;i<=m;i++) cin>>x>>y,a[x][y]=true;
    dp[0][1]=1;//可以这样初始化  也可以初始化dp[1][1],但对于出发点需要特判
    for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(!a[i][j]) dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
		}
	}
	cout<

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=100010;
const ll mod=100003;
int read(){//读入优化
	int x=0;bool f=0;char c=getchar();
	while (c<'0'||c>'9'){if (c=='-')f=1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f?-x:x;
}
ll qpow(ll base, ll n){ll ans = 1; while (n){if (n & 1) ans = ans * base % mod; base = base * base % mod; n >>= 1;} return ans;}
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}
int n;
int a[maxn];
int main(){
	int ans=-1,cnt=1;
	cin>>n;
	a[0]=-2;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		if(a[i]==a[i-1]+1)
		{
			cnt++;
		}
		else
		{
			if(cnt>ans) ans=cnt;
			cnt=1;
		}
	}
	cout<

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=100010;
const ll mod=998244353;
int read(){//读入优化
	int x=0;bool f=0;char c=getchar();
	while (c<'0'||c>'9'){if (c=='-')f=1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f?-x:x;
}
ll qpow(ll base, ll n){ll ans = 1; while (n){if (n & 1) ans = ans * base % mod; base = base * base % mod; n >>= 1;} return ans;}
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}
ll a1,b;
ll a2[1000];
ll getC(ll x,int t)//0-x中，  t出现的次数
{
	memset(a2,0,sizeof(a2));
	 ll  m=1;
	  while(mt) a2[t]+=(a+1)*m;
	  		else if(b==t) a2[t]+=a*m+c+1;
	  		else a2[t]+=a*m;
	  	}
	  	else
	  	{
	  		if(b) a2[t]+=a*m;
	  		else a2[t]+=(a-1)*m+c+1;
	  	}
	  	m*=10;
	  }
	  return a2[t];
}
int main(){
	cin>>a1>>b;
	for(int i=0;i<=9;i++)  //f(a-b) = f(0-b)-f(0-a-1)
	if(i!=0) cout<<" "<

#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=1000010;
const ll mod=998244353;
int read(){//读入优化
	int x=0;bool f=0;char c=getchar();
	while (c<'0'||c>'9'){if (c=='-')f=1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f?-x:x;
}
ll qpow(ll base, ll n){ll ans = 1; while (n){if (n & 1) ans = ans * base % mod; base = base * base % mod; n >>= 1;} return ans;}
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}
struct node{ //按结构体保存  
	int a,b;
}a[maxn]; 
bool cmp(node a,node b)  //按a排序  b其实也可以
{
	return a.a>n;
	for(int i=1;i<=n;i++) cin>>a[i].a>>a[i].b;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++) b[i]=a[i].b;
	for(int i=1;i<=n;i++)//求解最长上升子序列的过程    n^2  会超时，所以这里建一个额外数组二分进行查找
	{
       if(b[i]>c[cnt]) c[++cnt]=b[i];
       else
       {
       	  int site=upper_bound(c+1,c+1+cnt,b[i])-c;
		   c[site]=b[i];	       	
       }
	}
	cout<

#include
#include
using namespace std;
typedef long long ll;
const int maxn=100010;
const ll mod=998244353;
int n,m;
ll book[1000010];
vectora[maxn]; //vector存图 挺方便的
ll dfs(int x)
{
	if(book[x]!=-1) return book[x];
	book[x]=1;
	for(int i=0;i>n>>m;
	int x,y;
	memset(book,-1,sizeof(book));
	for(int i=1;i<=m;i++) cin>>x>>y,a[y].push_back(x); //这里是反向存图
	for(int i=1;i<=n;i++)
	cout<

#include
#include
using namespace std;
typedef long long ll;
const int maxn=100010;
const ll mod=998244353;
int n,m,ans=0;
vectorv[maxn];
bool book[maxn];
int dp[maxn];
int dfs(int x) //
{
	if(dp[x]!=-1) return dp[x];
	if(v[x].empty()) return 1;
	int ans=0;
	for(int i=0;i>n>>m;
	for(int i=1;i<=m;i++) cin>>a>>b,v[a].push_back(b);
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<=n;i++)
	{
		if(!book[i]&&v[i].size()>0) ans+=dfs(i);
	}
	cout<

#include
#include
using namespace std;
typedef long long ll;
const int maxn=200010;
const ll mod=998244353;
int n,m;
int topo[maxn];
int cnt=0,ans[maxn],head[maxn],in[maxn],out[maxn];
struct Edge{
	int u,v,next;
}e[maxn];
int total=0;
void add(int x,int y)
{
	e[++cnt].u=x;
	e[cnt].v=y;
	e[cnt].next=head[x];
	head[x]=cnt;
}
void topsort(int k)
{
	for(int i=head[k];i;i=e[i].next) 
	{
		ans[e[i].v]+=ans[k];
		if(!--in[e[i].v]) topsort(e[i].v);
	}
}
int main(){
	int a,b;
	cin>>n>>m;
	for(int i=1;i<=m;i++)  cin>>a>>b,add(a,b),++in[b],++out[a];
	
	for(int i=1;i<=n;i++) 
	{
		if(!in[i]&&out[i]&&!ans[i]) 
		{
			ans[i]=1;
			topsort(i);
		}
	}
	for(int i=1;i<=n;i++) if(!out[i])  total+=ans[i];
	cout<

#include
#include
using namespace std;
typedef long long ll;
const int maxn=200010;
const ll mod=998244353;
int n,p1,p2;
int cnt=0,ans[maxn],head[maxn],in[maxn],pre[maxn];
struct Edge{
	int u,v,next;
}e[maxn];
int total=0;
void add(int x,int y)
{
	e[++cnt].u=x;
	e[cnt].v=y;
	e[cnt].next=head[x];
	head[x]=cnt;
}
int main(){
	int a,b,t=0;
	cin>>n>>p1>>p2;
	for(int i=1;i<=p1;i++)  cin>>a>>b,add(a,b),++in[b];
    queueq;
    for(int i=1;i<=n;i++) if(in[i]==0) q.push(i);
    while(!q.empty())
    {
    	int x=q.front();
    	q.pop();
    	ans[x]=t++;
    	for(int i=head[x];i;i=e[i].next)
    	{
    		 --in[e[i].v];
    		 if(in[e[i].v]==0) q.push(e[i].v);
    	}
    }
	for(int i=1;i<=p2;i++)
	{
		cin>>a>>b;
		if(ans[a]