题单

P1117 无序字母对

P5240「NOIP2020」排水系统

P4042「NOIP2018」旅行

P5169「CSP-S 2020」函数调用

P4563 「NOIP2017」逛公园

题解

A

题面：

给定 \(n\) 个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。

请构造一个有 \(n+1\) 个字母的字符串使得每个字母对都在这个字符串中出现。

题解：

建图，欧拉路径模板.

欧拉路径这东西貌似没考过.

但是知道他可以dfs直接做就好了

（可能是因为复杂度太高）

代码：

#include <bits/stdc++.h>
#define ll long long
#define fs first
#define sc second
using namespace std;
const int N = 100, M = 52;
int n,deg[N],a[N*N],tp,flag=0,vt[N*N];
vector<pair<int,int> > g[N];
int ch_to_id(char c)
{
	assert(isalpha(c));
	if('A'<=c and c<='Z') return c-'A'+1;
	else return c-'a'+1+26;
}
int id_to_ch(int d)
{
	assert(1<=d and d<=52);
	if(d<=26) return d+'A'-1;
	else return d-27+'a';
}
void dfs(int u)
{
	//printf("%c ",id_to_ch(u));
	a[++tp]=u;
	if(tp>=n+1) { flag=1; return ; }
	for(auto e:g[u])
	{
		if(vt[e.sc]) continue;
		vt[e.sc]=1; dfs(e.fs); vt[e.sc]=0;
		if(flag) return;
	}
	if(flag) return;
	tp--;
}
int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		char s[4]; scanf("%s",s);
		int u=ch_to_id(s[0]),v=ch_to_id(s[1]);
		g[u].push_back({v,i}),g[v].push_back({u,i}); deg[u]++,deg[v]++;
	}
	for(int i=1; i<=M; i++) sort(g[i].begin(),g[i].end());
	//for(int i=1; i<=M; i++) if(g[i].size()) { for(auto e:g[i]) printf("(%c %c)",id_to_ch(i),id_to_ch(e.fs)); puts(""); }
	int cnt=0,st=0;
	for(int i=M; i; i--) if(deg[i]) st=i;
	for(int i=M; i; i--) if(deg[i]&1) st=i,cnt++;
	if(cnt!=0 and cnt!=2) { puts("No Solution"); return 0; }
	dfs(st);
	for(int i=1; i<=tp; i++) putchar(id_to_ch(a[i]));
	return 0;
}

B

题面：

DAG， \(1 \le n \le 10^5,1 \le m \le 10\)，入度为零的点初始有 \(1\) 的水，每个节点会均等地把水流向之后的点，问最后每个出度为零的点多少水.

题解：

拓扑排序模板，当年 NOIP 的时候我没做出来，实在太菜了ww）

按照拓扑序做就好了.

注意分数要开 __int128.

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5;
int n,m,deg_o[N],deg_i[N];

inline void prt(__int128_t x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        prt(x / 10);
    putchar(x % 10 + '0');
}

struct Misaka
{
	__int128_t p,q;
	void print() { prt(p),printf(" "),prt(q),puts(""); }
	friend Misaka yf(Misaka a)
	{
		if(a.p==0) return {0,1};
		__int128_t g=__gcd(a.p,a.q); if(g<0) g=-g;
		a.p/=g,a.q/=g; return a;
	}
	friend Misaka operator+ (Misaka a, Misaka b) { return yf((Misaka){a.p*b.q+b.p*a.q,a.q*b.q}); }
	friend Misaka operator/ (Misaka a, ll k) { return yf((Misaka){a.p,k*a.q}); }
}f[N];
vector<int> g[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++) 
	{
		scanf("%d",&deg_o[i]);
		for(int j=1,u; j<=deg_o[i]; j++) scanf("%d",&u),g[i].push_back(u),deg_i[u]++;
	}
	queue<int> q;
	for(int i=1; i<=m; i++) q.push(i),f[i]={1,1};
	for(int i=m+1; i<=n; i++) f[i]={0,1};
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		for(int v:g[u]) 
		{
			f[v]=f[v]+f[u]/deg_o[u]; deg_i[v]--;
			if(deg_i[v]==0) q.push(v);
		}
	}
	for(int i=1; i<=n; i++) if(deg_o[i]==0) f[i].print();
	return 0;
}

C

题面：

树或基环树，dfs序的字典序最小.

题解：

树很简单，每个点排个序直接dfs就好啦！

基环树也很简单，注意到 \(O(n^2)\) 可以过，所以直接暴力枚举删的一条边，转成树，再dfs也就好啦！

稍微有点小卡常..

代码：

#include <bits/stdc++.h>
#define ll long long
#define fs first
#define sc second
using namespace std;
const int N = 5005;
int n,m;
vector<int> g[N];
int ans[N],r[N],nr,vt[N];
pair<int,int> dlt;

int rd()
{
	int x; char ch;
	while(!isdigit(ch=getchar()));
	for(x=(ch^48); isdigit(ch=getchar()); x=(x<<1)+(x<<3)+(ch^48));
	return x;
}

bool check()
{
	for(int i=1; i<=n; i++)
		if(ans[i]<r[i]) return false;
		else if(ans[i]>r[i]) return true;
	return false;
}

void dfs1(int u)
{
	r[++nr]=u; vt[u]=1;
	for(int v:g[u])
	{
		if(vt[v] or (u==dlt.fs and v==dlt.sc) or (u==dlt.sc and v==dlt.fs)) continue;
		dfs1(v);
	}
}

void work2()
{
	for(int i=1; i<=n; i++) 
		for(int v:g[i])
		{
			if(i>v) continue; 
			nr=0; dlt={i,v};
			for(int i=1; i<=n; i++) vt[i]=0;
			dfs1(1); 
			if(nr!=n) continue;
			if(check()) for(int i=1; i<=n; i++) ans[i]=r[i];
		}
}

int main()
{
	n=rd(); m=rd();
	for(int i=1; i<=n; i++) ans[i]=n+1-i;
	for(int i=1,u,v; i<=m; i++)
	{
		u=rd(); v=rd();
		g[u].push_back(v); g[v].push_back(u);
	}
	for(int i=1; i<=n; i++) sort(g[i].begin(),g[i].end());
	if(m<n) { dfs1(1); for(int i=1; i<=nr; i++) printf("%d ",r[i]); }
	else { work2(); for(int i=1; i<=n; i++) printf("%d ",ans[i]); }
	return 0;
}

D

还没补..

E

题面：

有向图，边权非负，\(1 \le n \le 10^5,1 \le m \le 2\times 10^5,1 \le k \le 50\)，\(1\) 号点到 \(n\) 号点的最短路长为 \(d\)，求\(1\) 号点到 \(N\) 号点长度不超过 \(d + K\) 的路径个数

题解：

考虑 dp ，由于 \(k\) 很小，把 \(k\) 设为状态.

设 \(dis_u\) 表示 \(1\rightarrow u\) 最短路

\(f_{u,j}\) 表示 \(1\rightarrow u\) 等于 \(dis_u+j\) 的路径个数

使用 dijkstra+堆求出 \(dis_u\) ，再使用记忆化搜索转移 \(f\)

dp 时记录当前正在被 dp 的 \(f_{u,j}\) ，如果再次 dp 到了，说明出现了零环，输出 -1

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5, inf = 1e9;
int n,m,k,P,flag;
struct edge { int v,w; };
vector<edge> g[N],h[N];
int vt[N],dis[N];
int f[N][56],vf[N][56];
void dijk(int s)
{
	priority_queue<pair<int,int> > pq;
	for(int i=1; i<=n; ++i) dis[i]=inf;
    dis[s]=0; pq.push({-0,s});
    while(!pq.empty())
	{
        auto now=pq.top(); pq.pop();
        int val=now.first,u=now.second;
        if(dis[u]<val) continue;
        for(auto e:g[u])
		{
            if(dis[e.v]>dis[u]+e.w)
			{
                dis[e.v]=dis[u]+e.w;
                pq.push({-dis[e.v],e.v});
            }
        }
    }
}
int dp(int u, int j)
{
	if(~f[u][j]) return f[u][j];
	f[u][j]=0,vf[u][j]=1;
	for(auto e:h[u])
	{
		int t=dis[u]-dis[e.v]+j-e.w;
		if(t<0) continue;
		if(vf[e.v][t]) flag=1;
		f[u][j]=(f[u][j]+dp(e.v,t))%P;
	}
	vf[u][j]=0;
	return f[u][j];
}
int main()
{
	int T; scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d%d",&n,&m,&k,&P);
		for(int i=1; i<=n; i++) g[i].clear(),h[i].clear();
		for(int i=1,u,v,w; i<=m; i++)
		{
			scanf("%d%d%d",&u,&v,&w);
			g[u].push_back({v,w}),h[v].push_back({u,w});
		}
		dijk(1);
		memset(f,-1,sizeof(f)); flag=0;
		for(int i=0; i<=k; i++) dp(n,i);
		if(flag) puts("-1");
		else
		{
			memset(f,-1,sizeof(f)); f[1][0]=1; int ans=0;
			for(int i=0; i<=k; i++) ans=(ans+dp(n,i))%P;
			printf("%d\n",ans);
		}
		
	}
	return 0;
}

原文地址：http://www.cnblogs.com/copper-carbonate/p/16886212.html